Linkedin phone interview

题目是Shortest Word Distance

followup: two word distance 改成three word distance, 目的

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

用额外的memory，应该是O（n^2）吧

最优解应该只需要从左往右走一边就行。

1.   public int shortestDistance(String[] words, String word1, String word2, String word3) {
   
2. 
   
3.         //preid is needed to duplicate case
   
4.         int w1_preid = -1;
   
5.         int w2_preid = -1;
   
6.         int w3_preid = -1;
   
7.       
   
8.         //curid
   
9.         int w1_id = -1;
   
10.         int w2_id = -1;
    
11.         int w3_id = -1;
    
12.       
    
13.       
    
14.         int min = Integer.MAX_VALUE;
    
15.         for (int i = 0 ; i < words.length ; i++){
    
16.          
    
17.           //update possilbe length
    
18.           //only two the same [w1, w2] , [w2, w3], [w1, w3]
    
19.           if (word1.equals(word2) && !word1.equals(word3) &&  words[i].equals(word3)){
    
20. 
    
21.             if (w1_preid != -1 && w1_id!= -1)
    
22.               min = Math.min(i- w1_preid,  min);
    
23. 
    
24.           }
    
25.           else if (word1.equals(word3)  &&  !word1.equals(word2) && words[i].equals(word2)){
    
26. 
    
27.             if (w1_preid != -1 && w1_id!= -1)
    
28.               min = Math.min(i- w1_preid,  min);
    
29. 
    
30.           }
    
31.           else if (word2.equals(word3)  &&  !word2.equals(word1) && words[i].equals(word1)){
    
32.             if (w2_preid != -1 && w2_id!= -1)
    
33.               min = Math.min(i- w2_preid,  min);
    
34.           }
    
35.           // all the same
    
36.           // order does not matter but three different are necessary
    
37.           else if (word1.equals(word2)  &&  word2.equals(word3) && words[i].equals(word1)){
    
38.             if (w1_preid != -1 && w1_id!= -1)
    
39.               min = Math.min(i- w1_preid,  min);
    
40.           }
    
41.           // all different
    
42.           else if (words[i].equals(word1)){
    
43.             if (w2_id != -1 && w3_id!= -1)
    
44.               min = Math.min(i- Math.min(w2_id, w3_id), min);
    
45.           }
    
46.           else if (words[i].equals(word2)){
    
47.             if (w1_id != -1 && w3_id!= -1)
    
48.               min = Math.min(i- Math.min(w1_id, w3_id), min);
    
49.           }
    
50.           else if (words[i].equals(word3)){
    
51.             if (w1_id != -1 && w2_id!= -1)
    
52.               min = Math.min(i- Math.min(w1_id, w2_id), min);
    
53.           }
    
54.          
    
55.          
    
56.           //update cur index to id /preid
    
57.           if (words[i].equals(word1)){
    
58.             w1_preid = w1_id;
    
59.             w1_id = i;
    
60.           }
    
61.           if (words[i].equals(word2)){
    
62.             w2_preid = w2_id;
    
63.             w2_id = i;
    
64.           }
    
65.           if (words[i].equals(word3)){
    
66.             w3_preid = w3_id;
    
67.             w3_id = i;
    
68.           }
    
69. 
    
70.         }
    
71.         return min;
    
72.     }

复制代码

写了个代码considering duplication 有点complicate 有错烦指正

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

从左往右 分别记录三个word最后出现的index 然后 distance和 取最大值？

嗯，应该是的

mututu 发表于 2016-10-8 13:38
嗯，应该是的

如果w1 w2 w3 都重复 要输出为0吗? 最近也要面linkedlin 怕没坑了 thanks 指教....

请问楼主怎么拿到的面试啊

bbsbbstry 发表于 2016-10-8 23:21
请问楼主怎么拿到的面试啊

找同学的同学refer的

不懂，这个三个词的做法和两个词的做法能有不同吗？应该是一样的啊

bananapancake 发表于 2016-10-9 10:35
不懂，这个三个词的做法和两个词的做法能有不同吗？应该是一样的啊

对啊，就是update index的时候麻烦一点，方法是一样的吧。