我先開始一個問題
91 views
Skip to first unread message
sjgau02
Jun 27, 2008, 7:31:07 AM6/27/08
to 程式之美技術論壇
朋友上個月去 台灣Google 面試，
出了一道題目：
有兩個字串的陣列，如何找出兩個字串陣列中相同的元素？
不可以排序，又要最有效率。
大家 動動腦吧！
出了一道題目：
有兩個字串的陣列，如何找出兩個字串陣列中相同的元素？
不可以排序，又要最有效率。
大家 動動腦吧！
Bleed
Jun 27, 2008, 7:39:51 AM6/27/08
to 程式之美技術論壇
設兩個int c1[255], c2[255];
所有元素初值皆為0
for迴圈跑兩個字串紀錄ascii code 出現的加1
再跑for迴圈 大於0的即為相同
方法很爛 僅供參考
Bleed
所有元素初值皆為0
for迴圈跑兩個字串紀錄ascii code 出現的加1
再跑for迴圈 大於0的即為相同
方法很爛 僅供參考
Bleed
鮪魚
Jun 27, 2008, 7:41:39 AM6/27/08
to 程式之美技術論壇
元素是指char嗎？還是？
如果是char的話
弄一個map (p.s. STL)
開始把東西往裡面丟
兩個字串長度分別是n, m好了。
k = max(n,m)
將最長的那個先往map裡面丟，建出二元樹。
之後，再拿出短的出來比較。
這樣會是 klogk，主要是花在建tree。查詢一個char需要 logk，所以共花了min(n,m)logk
用DP的話，應該是n*m的時間複雜度吧。
如果是char的話
弄一個map (p.s. STL)
開始把東西往裡面丟
兩個字串長度分別是n, m好了。
k = max(n,m)
將最長的那個先往map裡面丟，建出二元樹。
之後，再拿出短的出來比較。
這樣會是 klogk，主要是花在建tree。查詢一個char需要 logk，所以共花了min(n,m)logk
用DP的話，應該是n*m的時間複雜度吧。
Bleed
Jun 27, 2008, 7:42:02 AM6/27/08
to 程式之美技術論壇
修正一下
兩陣列要皆大於0
> > 大家 動動腦吧！- 隱藏被引用文字 -
>
> - 顯示被引用文字 -
兩陣列要皆大於0
>
> - 顯示被引用文字 -
鮪魚
Jun 27, 2008, 7:42:58 AM6/27/08
to 程式之美技術論壇
Bleed
Jun 27, 2008, 7:44:42 AM6/27/08
to 程式之美技術論壇
可是題目沒定義元素到底是一個word還是單一char
第一句：I am a dog
第二句：u r a dog
如果以word來找
這樣的話是 a 和 dog
也許題目可以再定義清楚些
第一句：I am a dog
第二句：u r a dog
如果以word來找
這樣的話是 a 和 dog
也許題目可以再定義清楚些
Bleed
Jun 27, 2008, 8:15:19 AM6/27/08
to 程式之美技術論壇
對不起 我看錯題目了 字串陣列意思應該是有很多字串
用C++解
如果皆是英文的話
都是小寫則設26個vector
抓首字母加入vector 比如
s字串陣列
abs
bcd
adc
abc的s[0][0]-'a'為0 push_back進index為0的vector
bcd的s[1][0]-'a'為1 puch_back進index為1的vector
以此類推
然後第二個字串陣列用一樣的方法求出index 再找該vector
比對的方式我只想到循序
Bleed
用C++解
如果皆是英文的話
都是小寫則設26個vector
抓首字母加入vector 比如
s字串陣列
abs
bcd
adc
abc的s[0][0]-'a'為0 push_back進index為0的vector
bcd的s[1][0]-'a'為1 puch_back進index為1的vector
以此類推
然後第二個字串陣列用一樣的方法求出index 再找該vector
比對的方式我只想到循序
Bleed
鮪魚
Jun 27, 2008, 8:20:21 AM6/27/08
to 程式之美技術論壇
看來應該是用suffix tree來解比較快了…
只是，suffix tree最快到底是花多少時間啊？怎麼印象中好像有 O(n) 的演算法呢？
sj gau
Jun 27, 2008, 9:54:11 AM6/27/08
to bofp...@googlegroups.com
對不起，我沒有轉述的 很清楚
有兩個字串的陣列，假設 陣列的長度約 10000
字串的長度約 20, 沒有空白字元
不准 sort, 找出 兩個陣列的 交集合，放到 第三個陣列。
so, Google 在面試完之後，有提示答案。
等大家討論的 差不多，我再來公佈答案，
答案，不見得是 正確的，有討論的 空間。
Vincent Chen
Jul 1, 2008, 5:53:20 AM7/1/08
to 程式之美技術論壇
還有個疑問，所謂交集合有順序嗎？
假如陣列1中有單詞BB DD CC AA BB AA
而陣列2中是AA BB CC BB DD AA
那么交集合是AA BB CC DD呢？
還是BB CC BB AA。
如果是後者，這題有點像LCS問題的加強版 :)
On 6月27日, 下午9時54分, "sj gau" <sjgau4...@gmail.com> wrote:
> 對不起，我沒有轉述的 很清楚
>
> 有兩個字串的陣列，假設 陣列的長度約 10000
>
> 字串的長度約 20, 沒有空白字元
>
> 不准 sort, 找出 兩個陣列的 交集合，放到 第三個陣列。
>
> so, Google 在面試完之後，有提示答案。
> 等大家討論的 差不多，我再來公佈答案，
> 答案，不見得是 正確的，有討論的 空間。
>
假如陣列1中有單詞BB DD CC AA BB AA
而陣列2中是AA BB CC BB DD AA
那么交集合是AA BB CC DD呢？
還是BB CC BB AA。
如果是後者，這題有點像LCS問題的加強版 :)
On 6月27日, 下午9時54分, "sj gau" <sjgau4...@gmail.com> wrote:
> 對不起，我沒有轉述的 很清楚
>
> 有兩個字串的陣列，假設 陣列的長度約 10000
>
> 字串的長度約 20, 沒有空白字元
>
> 不准 sort, 找出 兩個陣列的 交集合，放到 第三個陣列。
>
> so, Google 在面試完之後，有提示答案。
> 等大家討論的 差不多，我再來公佈答案，
> 答案，不見得是 正確的，有討論的 空間。
>
> 在 2008/6/27，Bleed <bleed1...@gmail.com> 撰寫：
>
>
>
> > 可是題目沒定義元素到底是一個word還是單一char
>
> > 第一句：I am a dog
> > 第二句：u r a dog
>
> > 如果以word來找
> > 這樣的話是 a 和 dog
>
> > 也許題目可以再定義清楚些
>
> > On 6月27日, 下午7時42分, 鮪魚 <aecho1...@gmail.com> wrote:
> > > 呵，你的比較快 XDD
>
> > > On 6月27日, 下午7時39分, Bleed <bleed1...@gmail.com> wrote:
>
> > > > 設兩個int c1[255], c2[255];
> > > > 所有元素初值皆為0
>
> > > > for迴圈跑兩個字串紀錄ascii code 出現的加1
>
> > > > 再跑for迴圈 大於0的即為相同
>
> > > > 方法很爛 僅供參考
>
> > > > Bleed
>
> > > > On 6月27日, 下午7時31分, sjgau02 <sjgau4...@gmail.com> wrote:
>
> > > > > 朋友上個月去 台灣Google 面試，
> > > > > 出了一道題目：
>
> > > > > 有兩個字串的陣列，如何找出兩個字串陣列中相同的元素？
>
> > > > > 不可以排序，又要最有效率。
>
> > > > > 大家 動動腦吧！- 隱藏被引用文字 -
>
> > > - 顯示被引用文字 -
>
> --
> sjgau4...@gmail.comhttp://sjgau.javaeye.com>
>
>
> > 可是題目沒定義元素到底是一個word還是單一char
>
> > 第一句：I am a dog
> > 第二句：u r a dog
>
> > 如果以word來找
> > 這樣的話是 a 和 dog
>
> > 也許題目可以再定義清楚些
>
> > On 6月27日, 下午7時42分, 鮪魚 <aecho1...@gmail.com> wrote:
> > > 呵，你的比較快 XDD
>
> > > On 6月27日, 下午7時39分, Bleed <bleed1...@gmail.com> wrote:
>
> > > > 設兩個int c1[255], c2[255];
> > > > 所有元素初值皆為0
>
> > > > for迴圈跑兩個字串紀錄ascii code 出現的加1
>
> > > > 再跑for迴圈 大於0的即為相同
>
> > > > 方法很爛 僅供參考
>
> > > > Bleed
>
> > > > On 6月27日, 下午7時31分, sjgau02 <sjgau4...@gmail.com> wrote:
>
> > > > > 朋友上個月去 台灣Google 面試，
> > > > > 出了一道題目：
>
> > > > > 有兩個字串的陣列，如何找出兩個字串陣列中相同的元素？
>
> > > > > 不可以排序，又要最有效率。
>
> > > > > 大家 動動腦吧！- 隱藏被引用文字 -
>
> > > - 顯示被引用文字 -
>
> --
sjgau02
Jul 1, 2008, 8:14:12 PM7/1/08
to 程式之美技術論壇
Google 的面試官，提示給我的朋友的答案，
只有簡單的 一句話，
建議使用 hash
所以，應該是 不用 把答案做 排序的動作。
> > sjgau4...@gmail.comhttp://sjgau.javaeye.com- 隱藏被引用文字 -
>
> - 顯示被引用文字 -
只有簡單的 一句話，
建議使用 hash
所以，應該是 不用 把答案做 排序的動作。
>
> - 顯示被引用文字 -
Vincent Chen
Jul 1, 2008, 11:28:23 PM7/1/08
to 程式之美技術論壇
这种规模的数据，用hash一般是时间上比较优的解
应用场景应该是判断两篇文章中同时出现的词汇，计算文本similarity的时候用
应用场景应该是判断两篇文章中同时出现的词汇，计算文本similarity的时候用
Reply all
Reply to author
Forward
0 new messages