Google实习三轮电面面经

大概去年十月找人内推的，约了12月面试
比较意外的是他们排了3 round的phone interview (一般都是2 round)

第一round是个美国小哥，口音纯正，问怎么判断valid parenthesis input
(google) rocks
(goo) (gle) () rocks
goo (( gle )) rocks

都是valid的

google ((rocks ) 不valid

给了一个用stack的解法，遇到(就push进去，但这边不小心犯了低级错误
把一个condition里面的 || 写成了 &&
抓bug抓了有点久时间，估计是跪在这里
问有没有別的解法，回答recursive，但时间不够没有写代码，大概讲思路
看地里有人这题答到第三个follow-up是输出所有可能的pa

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

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

quicksort，他说他没想过可以用sorting解，所以估计这题应该还有其他方法可以解，不过我说quicksort的时候也快45min了，所以也差不多结束问了些问题

大致上感觉运气不错，遇到简单的题，印象中每题也都给了两种解法并且分析time/space complexity
本来感觉良好，后来还是掛了，估计第一面犯了低级错误可能扣了不少分

希望大家都能找到好工作！求大米

好文 Thanks for sharing! good luck

感觉可能是第三题错了，个人感觉用哈希表可以到O(N)。

1. import java.util.HashMap;
   
2. import java.util.Map;
   
3. 
   
4. public class Couple {
   
5.     public static void main(String[] args) {
   
6.         int[] arr = new int[]{2, 1, 3, 1, 3, 2, 4, 4};
   
7.         
   
8.         System.out.println(coupleSort(arr));
   
9.     }
   
10.    
    
11.     public static int coupleSort(int[] arr) {
    
12.         int numSwaps = 0;
    
13.         Map<Integer, Integer> int2index = new HashMap<>();
    
14.         for (int i = 0; i < arr.length; i++) {
    
15.             if (!int2index.containsKey(arr[i])) {
    
16.                 int2index.put(arr[i], i);
    
17.             }
    
18.             else {
    
19.                 if (i % 2 == 1 && int2index.get(arr[i]) == i - 1) {
    
20.                     continue;
    
21.                 }
    
22.                 else {
    
23.                     // swapping
    
24.                     if (int2index.get(arr[i]) % 2 == 0) {
    
25.                         swap(i, int2index.get(arr[i]) + 1, arr);
    
26.                     }
    
27.                     else {
    
28.                         swap(i, int2index.get(arr[i]) - 1, arr);
    
29.                     }
    
30.                     
    
31.                     numSwaps++;
    
32.                     int2index.remove(arr[i]);
    
33.                     i--;
    
34.                 }
    
35.             }
    
36.         }
    
37.         
    
38.         return numSwaps;
    
39.     }
    
40.    
    
41.     public static void swap(int i, int j, int[] arr) {
    
42.         int tmp = arr[i];
    
43.         arr[i] = arr[j];
    
44.         arr[j] = tmp;
    
45.     }
    
46. }

复制代码

感觉是不是这样就可以了
用一个map存char及它首次出现的position;
对于每个char，如果它之前没有出现过，就把它存到map里；如果出现过，就将它与之前出现过的该char后面一个char互换。

1.         public void minimumSwap(char[] chars){
   
2.                 Map<Character, Integer> map = new HashMap();
   
3.                 for(int i = 0; i < chars.length; i ++){
   
4.                         if(! map.containsKey(chars[i]))
   
5.                                 map.put(chars[i], i);
   
6.                         else{
   
7.                                 char c = chars[i];
   
8.                                 int index = map.get(c);
   
9.                                 chars[i] = chars[index + 1];
   
10.                                 chars[index+1] = c;
    
11.                                 map.put(chars[i], i);
    
12.                         }
    
13.                 }
    
14.         }

复制代码

第三题，或许用HashMap？记录Character和该字符第二次出现index

mk01 发表于 2015-2-20 10:30
感觉可能是第三题错了，个人感觉用哈希表可以到O(N)。

请问可以详细讲一下吗？为什么会分index的奇偶讨论呢？谢谢！

mk01 发表于 2015-2-20 10:30
感觉可能是第三题错了，个人感觉用哈希表可以到O(N)。

大牛，这个题目可以麻烦你再讲详细点嘛？谢谢了。

第三题怎么做。。Greedy可行吗?

mk01 发表于 2015-2-20 10:30
感觉可能是第三题错了，个人感觉用哈希表可以到O(N)。

Couple swap确实很难啊，能讲讲思路以及为啥是minimum swap么？

没看懂楼上的Couple Sort的解法，感觉这个解法是在数一种swap的方案有多少次交换，但没能解释是否是最优。因为似乎该答案是碰到重复的看第一次出现的字母是奇数index还是偶数index，奇数向前换偶数向后换，这样的话以下这个例子就不成立了：FABCCDDAB。A是第一个需要swap的，而由于第一次出现的A是index == 1，是奇数，所以它会换到F处，而最优解应该是AB相换。