谷歌实习电面

去年10月份左右投的简历，然后一直没动静，结果1月初突然有人联系我说要面试，背靠背两轮约在今天早上，然后跪了……
第一轮印度小哥，上来先分别自我介绍了有10分钟，题是能否通过一次交换从第一个string变换到第二个，converse

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

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

问了几个问题他就have a great day了。。。

第一次电面，leetcode刷了才30题不到，跪的妥妥的，还是要多刷题啊……_(:з」∠)_

第二题用递减栈 可以O(N)

您好！
本帖隐藏的内容需要积分高于 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

devilnut 发表于 2018-1-31 06:17
第二题用递减栈 可以O(N)

worst case还是nlgn, 因为要全部入栈

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

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

楼主能说下第一题具体怎么变换么？

爱学习的鼠哥 发表于 2018-2-12 11:36
楼主能说下第一题具体怎么变换么？

给一个string，能否通过交换其中的两个char来得到第二个string，仅限一次交换，比如conserve, 交换v和s，可以得到converse，要求返回v和s的index

oneexy 发表于 2018-2-12 10:51
worst case还是nlgn, 因为要全部入栈

如果是01似乎是可以O(n)
判断四种情况 00 01 10 11 就可以
但是我不太明白怎么用hashmap或者stack

请指教

oneexy 发表于 2018-2-12 10:51
worst case还是nlgn, 因为要全部入栈

如果是01似乎是可以 O(n)
判断四种情况 00 01 10 11 就可以
但是我不太明白怎么用hashmap或者stack

请指教

greynut 发表于 2018-2-13 04:26
如果是01似乎是可以 O(n)
判断四种情况 00 01 10 11 就可以
但是我不太明白怎么用hashmap或者stack

1. import java.util.*;
   
2. class solution{
   
3.         public static void main(String[] args) {
   
4.                 int[] in = new int[]{8, 3, 3, 5, 9, 4};
   
5.                 int[] res = find(in);
   
6.                 System.out.println(Arrays.toString(res));
   
7.         }
   
8. 
   
9.         public static int[] find(int[] arr){
   
10.                 int[] res = new int[arr.length];
    
11.                 Queue<Integer[]> heap = new PriorityQueue<>((a,b)->a[0]-b[0]);
    
12.                 for(int i=0; i<arr.length; i++){
    
13.                         while(!heap.isEmpty() && heap.peek()[0] < arr[i]){
    
14.                                 Integer[] pair = heap.poll();
    
15.                                 res[pair[1]] = i - pair[1];
    
16.                         }
    
17.                         heap.add(new Integer[]{arr[i], i});
    
18.                 }
    
19.                 return res;
    
20.         }
    
21. 
    
22. }

复制代码

O(nlgn)解法