狗去onsite

#Google onsite

1. Given a stream of data that only contians integer, you need to calculate the average of numbers in a time window. Assume you have multiple replicated numbers, how could you transfer the stream from producer to con

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

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

e path and a int value K. The file contains all messages from users in a hangout chatting session. Find the top k talktive users.

第三题应该是在bfs基础上加状态，就是到达当前位置且更改次数为0或者1的情况下的最短路径。这个思想可以扩展到任意次数的修改

第三题followup应该是dijkstra的思路吧？
heap里push进{i,j,steps,walls}.
bfs过程中每次只push进 走到下一个点number of break walls <= 1的点，
最后poll出来的点能到destination就直接返回那个step

1. public static int shortest(int[][] M, int[] start, int[] end){
   
2.                 int m = M.length;
   
3.                 int n = M[0].length;
   
4.                 Integer[][] dist = new Integer[m][n];
   
5.                 PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> (a[2] - b[2]));
   
6.                 heap.offer(new int[]{start[0], start[1], 0, 0});
   
7.                 int[][] dirs = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
   
8.                 while(!heap.isEmpty()){
   
9.                         int[] cur = heap.poll();
   
10.                         int i = cur[0];
    
11.                         int j = cur[1];
    
12.                         int steps = cur[2];
    
13.                         int walls = cur[3];
    
14.                         dist[i][j] = steps;
    
15.                         if(i == end[0] && j == end[1]){
    
16.                                 return steps;
    
17.                         }
    
18.                         for(int[] dir : dirs){
    
19.                                 int ni = i + dir[0];
    
20.                                 int nj = j + dir[1];
    
21.                                 if(ni >= 0 && ni < m && nj >= 0 && nj < n && dist[ni][nj] == null && (walls + M[ni][nj] <= 1)){
    
22.                                         int nwalls = walls + M[ni][nj];
    
23.                                         heap.offer(new int[]{ni, nj, steps + 1, nwalls});
    
24.                                 }
    
25.                         }
    
26.                 }
    
27.                 return -1;
    
28.         }

复制代码

woderegou 发表于 2018-4-28 05:35
第三题的follow up感觉就是先bfs一次，记录下最短路径，然后看1里面有没有一个1被3个属于最短路径的0包围， ...

我的想法是，先找出最短路径，然后对于最短路径上的每一个墙，看我们能不能打通它来穿墙而过。这种case就是墙的厚度是1，然后墙两边都是最短路径

比如最短路径是

00000
11110
00000

那打掉第二行第一个1就可以了。我们的目标就是找出被最短路径夹住的墙，然后去掉每一个看是否是路径缩短

其他case貌似缩短不了，不知道我是不是少想了case

比如墙的厚度是2，那没法减少，如果墙没有被最短路径夹住，比如

0000000
1111110
0000010
1111110
0000000

那打通任意一个都没办法是路径缩短

补充内容 (2018-4-28 14:41):
我给的例子是从左上角走到左下角的最短路径

谢谢楼主:)
第二题 的timestamp有什么用？
top candidate定义怎样的？
第四题 talktive 怎么定义？出现次数最多么？

第三题 follow up是不是还有可以 让k个1变为0

第三题的follow up咋做的？从起点和终点开始双向BFS?

jxpisces 发表于 2018-4-25 10:23
谢谢楼主:)
第二题 的timestamp有什么用？
top candidate定义怎样的？

第二题给了两个条件 要找某一时间之前的top candidates
第四题是talktive出现次数最多
第三题感觉要用DP，但是额没有solve出来

请问楼主第四题你是怎么process这个文件的？怎么从文件中拿user id？

ruiwanbing 发表于 2018-4-27 01:51
第二题给了两个条件 要找某一时间之前的top candidates
第四题是talktive出现次数最多
第三题感觉要用D ...

第三题应该不是DP，BFS或者两次扫描。

楼主请问下第一题的follow up 的解法是加个counter 把相同number重复的次数记录下来吗？这样可以不用每个number都记录？

neverlandzzy 发表于 2018-4-27 10:15
楼主请问下第一题的follow up 的解法是加个counter 把相同number重复的次数记录下来吗？这样可以不用每个nu ...

是的 就是压缩string

idatascience 发表于 2018-4-27 07:42
请问楼主第四题你是怎么process这个文件的？怎么从文件中拿user id？

按照分隔符分割。