狗去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 s

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

复制代码

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

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

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

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

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

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

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

请问楼主第四题你是怎么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？

按照分隔符分割。