[3/8] Google Onsite

今天面了google，也是最近面试非常重要的一次，从昨天晚上就非常紧张，地里的面经看了好多遍。非常有帮助，今天的面试总结下来，有难有简单，总体来说是meidum 难度偏上，有几道hard。晚上见证了alphaGo战胜了李世石，感慨科技进步飞快啊卧槽

第一轮，linkedlist,找出最大的两个, 然后swap，不是swap value，swap reference。

第二轮，刚开始主要谈论了一下现在项目，然后写了一个topological sort。
第三轮，RGB颜色转换比如现有#2f3d13，有16进制的00,33,66,99，cc, ff.要把现有的数字转成最close to这几个数字。比如#2f3d13 -> #333300；
              第二题是findNthsmallest element in BST
第四轮，三道题啊。。。。1. one edit distance 2. wall, flower, matrix找到能看见最多flower的点，地里高频题 3. count of smaller number before itself
第五轮， 给一个API，

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

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

总体来说题目有难有简单吧，我觉得多多准备看看面经还是可以的，还有推荐九章的高级算法班（对有一定算法基础的同学），我觉得非常有帮助，至少我觉得有些题，上课老师的讲解和题目对我的帮助很大。

再谢谢地里的栽培哈

machen982003 发表于 2016-3-13 04:12
那这个题是扫四遍的做法么? 做一遍右一遍, 上一遍下一边, 然后求和最大?

分享下代码吧

1. public class FlowersInGarden {
   
2. 
   
3.         public static void main(String[] args) {
   
4.                 char[][] matrix = {{'f', 'x', 'x', 'w', 'f'},
   
5.                                      {'f', 'f', 'x' ,'x' ,'x'},
   
6.                                      {'x', 'x', 'f', 'w', 'f'},
   
7.                                      {'f', 'f', 'x', 'w', 'x'}};
   
8.                 maxFlowersInGarden(matrix);
   
9.         }
   
10.        
    
11.         public static int maxFlowersInGarden(char[][] matrix) {
    
12.                 if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
    
13.                         return 0;
    
14.                 }
    
15.                 int m = matrix.length;
    
16.                 int n = matrix[0].length;
    
17.                
    
18.                 int[][] res = new int[m][n];
    
19.                 for (int i = 0; i < m; i++) {
    
20.                         int count = 0;
    
21.                         int j = 0;
    
22.                         int start = 0;
    
23.                         while (j < n) {
    
24.                                 if (matrix[i][j] == 'f') {
    
25.                                         count++;
    
26.                                 } else if (matrix[i][j] == 'w') {
    
27.                                         for (int k = start; k < j; k++) {
    
28.                                                 res[i][k] = count;
    
29.                                         }
    
30.                                         start = j + 1;
    
31.                                         count = 0;
    
32.                                 }
    
33.                                 j++;
    
34.                         }
    
35.                         for (int k = start; k < j; k++) {
    
36.                                 res[i][k] = count;
    
37.                         }
    
38.                 }
    
39.                 for (int j = 0; j < n; j++) {
    
40.                         int count = 0;
    
41.                         int i = 0;
    
42.                         int start = 0;
    
43.                         while (i < m) {
    
44.                                 if (matrix[i][j] == 'f') {
    
45.                                         count++;
    
46.                                 } else if (matrix[i][j] == 'w') {
    
47.                                         for (int k = start; k < i; k++) {
    
48.                                                 res[k][j] += count;
    
49.                                         }
    
50.                                         start = i + 1;
    
51.                                         count = 0;
    
52.                                 }
    
53.                                 i++;
    
54.                         }
    
55.                         for (int k = start; k < i; k++) {
    
56.                                 res[k][j] += count;
    
57.                         }
    
58.                 }
    
59.                 for (int i = 0; i < m; i++) {
    
60.                         for (int j = 0; j < n; j++) {
    
61.                                 if (matrix[i][j] == 'f') {
    
62.                                         res[i][j] -= 1;
    
63.                                 }
    
64.                         }
    
65.                 }
    
66.                 int max = 0;
    
67.                 for (int i = 0; i < m; i++) {
    
68.                         for (int j = 0; j < n; j++) {
    
69.                                 System.out.print(res[i][j] + " ");
    
70.                                 max = Math.max(max, res[i][j]);
    
71.                         }
    
72.                         System.out.println();
    
73.                 }
    
74.                
    
75.                
    
76.                 return max;
    
77.         }
    
78. }
    

复制代码

hanabeast 发表于 2016-3-10 09:30
能不能问下wall flower是啥题

给一个two D garden , 每一个slot可以是flower或者Wall. 找一个合适的位置，让游客可以看到最多的flower.可以站在flower上，不能站在墙上。。
如果被墙挡了，就看不到墙后面的花。然后游客只能竖直或者水瓶看，不能看对角线。。比如
[ [f, x, x, w, f],
[f, f, x ,x ,x],
[x, x, f, w, f],
[f, f, x, w, x]]
这样，{3, 0} 和 {1,4}都能看到四朵花。

找一个点能看到最多的花

能不能问下wall flower是啥题

lz: #2f3d13 -> #333300可以解释一下怎么转换吗？ findNthsmallest element in BST每个节点除了有子节点，还有rank吗？

第一轮是用四个指针？还有别的办法么？

guixi107 发表于 2016-3-10 14:41
lz: #2f3d13 -> #333300可以解释一下怎么转换吗？ findNthsmallest element in BST每个节点除了有子节点， ...

比如2f 最接近 33对吧，所以就转换成33， 3d 最接近33也转换成33，比如5a->66
findNthsmallest element in BST 就是inorder search 呀

cascade15 发表于 2016-3-10 15:10
第一轮是用四个指针？还有别的办法么？

对就是用四个指针

论坛匿名用户 发表于 2016-3-11 06:22
给一个two D garden , 每一个slot可以是flower或者Wall. 找一个合适的位置，让游客可以看到最多的flower. ...

那这个题是扫四遍的做法么? 做一遍右一遍, 上一遍下一边, 然后求和最大?

感谢楼主0.0 请教一下第一题的四个指针做法具体是什么意思呢？谢谢！

lawinse 发表于 2016-3-15 17:55
感谢楼主0.0 请教一下第一题的四个指针做法具体是什么意思呢？谢谢！

就是把scan一遍，找到第一大和第二大node的父亲节点并记录下来，然后swap就好了