G onsite 2015/02/09

斗胆面了谷歌，小弟很弱，不出意外挂了，因为每轮只面我一道题。
1. 给你一个target number，和一个list，list里面装的都是整数。问是否能用list里面的所有数字，只用四则运算和括号之类的，问能不能得到target number。很像24点，不过是它的扩展。
2. 给你一堆input，每一个input是一条边，表示谁和谁是朋友，例如
    1 - 2

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

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

         bar        30
4. 给两组点，第一组的点都在圆上，第二组的点都在圆外，从第一组里面和第二组里面分别找一点，这两点之间的距离最小。

小弟技术浅薄，经验少，估计要挂了……希望各位大大集思广益~

lklk1986fa 发表于 2015-2-10 15:06
请问第四题有什么比较好的方法呢

可不可以把圆上每个点用与x轴夹角表示，然后对圆外每个点，取其与圆心连线相对于x轴的夹角，找与这个夹角最近的圆上的点（二分查找，因为圆上点也是夹角表示的），算距离，这个就是对于当前圆外点与所有圆上点的距离的最小值了，比较所有圆外点算得的最小值来得到全局最小值，复杂度是O(NLogM), 如果圆外N个点圆上M个点的话

sunfish 发表于 2015-2-11 13:09
谁能讲下第三题怎么做吗？谢谢了

终于有人问这个了……我觉得这道题我当时写了好久，现在没人问，是不是我水平太低了……
我就直接贴代码吧。

1. class Entry {
   
2.         public String funcName;
   
3.         public int timeStamp;
   
4.         public boolean isStart;
   
5.         public Entry(String funcName, int timeStamp, boolean isStart) {
   
6.                 super();
   
7.                 this.funcName = funcName;
   
8.                 this.timeStamp = timeStamp;
   
9.                 this.isStart = isStart;
   
10.         }
    
11. }
    
12. class Node {
    
13.         public String funcName;
    
14.         public int start;
    
15.         public int end;
    
16.         public int indentLevel;
    
17.         public Node(String funcName, int indentLevel) {
    
18.                 super();
    
19.                 this.funcName = funcName;
    
20.                 this.indentLevel = indentLevel;
    
21.         }
    
22. }
    
23. public class ProgramProfile {
    
24.         public static void printProfile(List<Entry> input) {
    
25.                 Stack<Node> stack = new Stack<Node>();
    
26.                 List<Node> res = new LinkedList<Node>();
    
27.                 for (int i = 0; i < input.size(); i++) {
    
28.                         Entry curr = input.get(i);
    
29.                         if (curr.isStart) {
    
30.                                 Node node = new Node(curr.funcName, stack.size());
    
31.                                 node.start = curr.timeStamp;
    
32.                                 stack.push(node);
    
33.                                 res.add(node);
    
34.                         } else {
    
35.                                 Node node = stack.pop();
    
36.                                 node.end = curr.timeStamp;
    
37.                         }
    
38.                 }
    
39.                
    
40.                 for (Node node : res) {
    
41.                         for (int i = 0; i < node.indentLevel * 4; i++) {
    
42.                                 System.out.print(" ");
    
43.                         }
    
44.                         System.out.println(node.funcName + "    " + (node.end - node.start));
    
45.                 }
    
46.         }
    
47.         /**
    
48.          * @param args
    
49.          */
    
50.         public static void main(String[] args) {
    
51.                 // TODO Auto-generated method stub
    
52.                 List<Entry> input = new ArrayList<Entry>();
    
53.                 input.add(new Entry("main", 0, true));
    
54.                 input.add(new Entry("foo", 5, true));
    
55.                 input.add(new Entry("g", 10, true));
    
56.                 input.add(new Entry("g", 20, false));
    
57.                 input.add(new Entry("foo", 50, false));
    
58.                 input.add(new Entry("bar", 60, true));
    
59.                 input.add(new Entry("main", 90, false));
    
60.                 input.add(new Entry("main", 100, false));
    
61.                 ProgramProfile.printProfile(input);
    
62.         }
    
63. 
    
64. }

复制代码

tianyangche 发表于 2015-2-10 05:51
不知道何为并查集~小弟把这道题看作是一道图题，每个人建一个Person类，里面有他的id，还有一个list，用 ...

实现了一遍

1. graph = {1:[2],2:[1],3:[4],4:[3],4:[5],5:[4]}
   
2. def find(graph):
   
3.         visit = {}
   
4.         res = []
   
5.         for key in graph.keys():
   
6.                 visit[key] = False
   
7.         for key in graph.keys():
   
8.                 if visit[key] == True:
   
9.                         continue
   
10.                 que = [key]
    
11.                 temp = []
    
12.                 while que:
    
13.                         cur = que.pop()
    
14.                         temp.append(cur)
    
15.                         visit[cur] = True
    
16.                         for item in graph[cur]:
    
17.                                 if not visit[item]:
    
18.                                         que.append(item)
    
19.                 res.append(temp)
    
20. 
    
21.         return  res
    
22. 
    
23. print find(graph)

复制代码

看了一趟，感觉第一题蛮有趣的。
除了recursion暂时想不到其他方法了...当时楼主怎么解决的？这道题就是耗一轮的节奏，不要担心，祝有offer

赞一个！G家onsite录取率确实不高，据说大概1/4－1/7。。。不过感觉楼主还是挺有希望的，他家每轮一题的节奏很正常啊，祝楼主早日拿到offer！

对了请问楼主是在Mountain View面的么？

感觉这些题好题。楼主运气不太好。

babysor 发表于 2015-2-10 11:15
看了一趟，感觉第一题蛮有趣的。
除了recursion暂时想不到其他方法了...当时楼主怎么解决的？这道题就是耗 ...

对的~我是用的recursion解法~

茕茕梦 发表于 2015-2-10 11:50
赞一个！G家onsite录取率确实不高，据说大概1/4－1/7。。。不过感觉楼主还是挺有希望的，他家每轮一题的节 ...

嗯，没关系，小弟本着不抱希望的心态去，反而很放松。是的，我是在mountain view面的。

Linzertorte 发表于 2015-2-10 12:25
感觉这些题好题。楼主运气不太好。

我也不知道啦，刚开始想了几个方法，他们说不够优化，就在他们的提示下最后反正都写出来了，结果如何看天意了

求问第二题的思路，感觉可以用并查集，但也蛮复杂的，LZ有别的方法吗，比如用啥data structure存的

YY大帝 发表于 2015-2-10 13:36
求问第二题的思路，感觉可以用并查集，但也蛮复杂的，LZ有别的方法吗，比如用啥data structure存的

不知道何为并查集~小弟把这道题看作是一道图题，每个人建一个Person类，里面有他的id，还有一个list，用来存所有的他的friends。假如有n个人，那么
1.首先建立一个n大小的Person数组persons，里面的每个元素对应一个人。并且建立一个n大小的visited的boolean数组，用于判断某一个人是否已经处理过
2.然后处理输入，对于每个输入，把这个边的两个点分别加入到相应的人的friends里面去。
3.遍历数组。如果某一个人被放问过，那么略过，处理下一个。如果没有被放问过，分为两种情况
   a. 没有friends，那么单独成为一个group,加入到一个tempList里面，然后存进最终的结果list
   b. 有friends，把所有的未被放问过的friends放入一个queue里面，并且放入tempList里面，之后把这个person的visited标志为已访问。然后遍历这个queue。遍历这个queue的时候，基本上是和b步骤累死的过程，直到queue为空。