一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 6894|回复: 70
收起左侧

google 电面 挂经

[复制链接] |试试Instant~ |关注本帖
simplessssss 发表于 2016-4-1 03:24:08 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Google - 猎头 - 技术电面 |Failfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
第二轮电面跪经,面试官迟到7-8分钟。 说是手机找不到了。 大概聊了一下以前做的project,开始做题。题目是给你一个board,里面存储user的信息,user有id和socre。
board有adduser(id, score)(返回add进去的user当前的rank), findByRank(k) (这个返回id)。
Add如果本身已经有id在board中,需要对这个id的score进行update。
开始想的是用map加binary search中,中途脑子短路,写到一半发现似乎做不出来了。。。。(面完之后想想,这个方法应该是做的出来的。). 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
面试官说应该要用binary search tree做,听到这里 基本就知道gg了。
然后就是悲剧的开始,只会做binary search tree的添加点的操作,update和delete 操作基本忘干净了,不记得具体的步骤了。


写代码的时候 struggle在了 delete 操作上,还有10分钟左右面试官说不用写了,就这样了。最后就是问一些问题了。

还是基本功不够扎实,发个面经,攒点rp。。。顺便求内推!!!!!

评分

2

查看全部评分

本帖被以下淘专辑推荐:

cx00001 发表于 2016-4-1 23:21:51 | 显示全部楼层
我得想法是用binary search tree的话,节点是按score来存,id存在一个arraylist里头,如果有相同的score,就加入到arraylist里,再加上左右孩子和自己的个数。这样update和findbyrank都能在logn的复杂度完成
回复 支持 1 反对 0

使用道具 举报

柔柔0310 发表于 2016-4-1 13:08:23 | 显示全部楼层
谢谢楼主。这个题真的挺实用的。祝好!
回复 支持 反对

使用道具 举报

cx00001 发表于 2016-4-1 13:43:30 | 显示全部楼层
binary search tree的话是默认 没有重复的score么,这样就可以用treemap了呀,不过update需要遍历map。或者再加一个hashmap
回复 支持 反对

使用道具 举报

 楼主| simplessssss 发表于 2016-4-1 21:36:06 | 显示全部楼层
cx00001 发表于 2016-4-1 13:43
binary search tree的话是默认 没有重复的score么,这样就可以用treemap了呀,不过update需要遍历map。或者 ...

有重复的score的,我写的时候寸的id,注意你还要存左边电的个数和右边电的个数,不然findrank(int k),就要O(n)了,他要2个func都是O(logn)的
回复 支持 反对

使用道具 举报

cx00001 发表于 2016-4-1 23:03:30 | 显示全部楼层
如果存id的话 那怎么能在lgn找到第k个点呢?
回复 支持 反对

使用道具 举报

 楼主| simplessssss 发表于 2016-4-1 23:04:30 | 显示全部楼层
cx00001 发表于 2016-4-1 23:03
如果存id的话 那怎么能在lgn找到第k个点呢?

我在建表的过程中存了 左右子树节点的个数
回复 支持 反对

使用道具 举报

cx00001 发表于 2016-4-1 23:05:22 | 显示全部楼层
但并没有按照score大小来存节点呀
回复 支持 反对

使用道具 举报

 楼主| simplessssss 发表于 2016-4-1 23:06:16 | 显示全部楼层
cx00001 发表于 2016-4-1 23:05
但并没有按照score大小来存节点呀

有一个hash table对应id和score,这样比较的时候按score比较就行了
回复 支持 反对

使用道具 举报

cx00001 发表于 2016-4-1 23:22:56 | 显示全部楼层
cx00001 发表于 2016-4-1 23:21
我得想法是用binary search tree的话,节点是按score来存,id存在一个arraylist里头,如果有相同的score, ...

还需要加个hashmap,存id和原来的score,这样更新score的时候能先通过id获得原来的score
回复 支持 反对

使用道具 举报

aden_dou 发表于 2016-4-1 23:30:40 | 显示全部楼层
谁能解释一下怎么做
回复 支持 反对

使用道具 举报

adiggo 发表于 2016-4-1 23:42:22 | 显示全部楼层
这个用bst worst running time也是n^2吧 没办法保证self balanced?
回复 支持 反对

使用道具 举报

 楼主| simplessssss 发表于 2016-4-1 23:43:16 | 显示全部楼层
adiggo 发表于 2016-4-1 23:42
这个用bst worst running time也是n^2吧 没办法保证self balanced?

建成balanced tree就可以了
回复 支持 反对

使用道具 举报

hkc593 发表于 2016-4-2 00:57:37 | 显示全部楼层
simplessssss 发表于 2016-4-1 23:43
建成balanced tree就可以了
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
怎么能保证是balanced?adduser的顺序是未知的。除非每次在add sore之后都balance一下?

补充内容 (2016-4-2 00:59):
或者用red–black tree?
回复 支持 反对

使用道具 举报

cx00001 发表于 2016-4-2 01:29:34 | 显示全部楼层
  1. public class Node{
  2.     public int score;
  3.     public HashSet<String> IDSet;
  4.     public int size;
  5.     public Node left;
  6.     public Node right;
  7.     Node(String ID, int score){
  8.         IDSet = new HashSet<String>();
  9.         IDSet.add(ID);
  10.         this.score = score;
  11.     }. 1point 3acres 璁哄潧
  12. }
  13. public class BinarySearchTree{
  14. public HashMap<String,Node> scoreIDMap;
  15. Node root;
  16.     BinarySearchTree(){
  17.            scoreIDMap = new HashMap<String,Node>();
  18.    }
  19. public void update(String ID, int score){
  20.         if(scoreIDMap.containsKey(ID)){
  21.                 Node  node = scoreIDMap.get(ID);
  22.                 if(node.IDSet.size()>1){
  23. IDSet.remove(ID);
  24. }
  25. else{
  26.         delete(node);
  27. }
  28.         Node newNode =insert(ID, score);
  29.         scoreIDMap.put(ID,newNode);
  30. }
  31. public void insert(String ID, int score){
  32.         . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  33. }. more info on 1point3acres.com
  34. public void insert(Node n, String ID, int score){
  35.         if(n==null){
  36.                 n =new Node(ID,score);
  37. }else{
  38.         if(n.score==score){. Waral 鍗氬鏈夋洿澶氭枃绔,
  39.                 n.IDSet.add(ID);
  40. }
  41. else if(n.score>score){
  42.         n.size++;
  43.         insert(n.left,ID,score);. 1point3acres.com/bbs
  44. }
  45. else{
  46.         insert(n.right,ID,score);
  47. }
  48. }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  49. }
  50. public void delete(Node node){
  51. //find parent of node
  52. //check three case: leaf, one child, two children
  53. Node parent = findParent(node);       
  54. if(parent==null){. more info on 1point3acres.com
  55.         if( node.left==null&& node.right==null) root=null;
  56.         else if(node.left ==null){. 1point 3acres 璁哄潧
  57.                 root= node.right;
  58. }
  59. else if(node.right == null){.1point3acres缃
  60. root = node.left;

  61. }
  62. else{
  63.         //find leftmost node of right subtree
  64. Node rootCand = findLeftmost(root.right);
  65. rootCand.left = root.left;. from: 1point3acres.com/bbs
  66. rootCand.size = root.size;
  67. rootCand.right = root.right;. 鍥磋鎴戜滑@1point 3 acres
  68. } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  69. }
  70. else{ 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  71.         if(node.left == null && node.right == null){. Waral 鍗氬鏈夋洿澶氭枃绔,
  72.                 if(parent.left == node) parent.left =null;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  73.                         else parent.right = null;
  74. }
  75. else if(node.left == null){
  76.         if(parent.left == node)parent.left = node.right;
  77.         else parent.right = node.right;
  78. }
  79. else if(node.right == null){
  80.         if(parent.right == node) parent.right = node.left;
  81.         else parent.left = nodel.left;
  82. }
  83. else{
  84.         Node candidate = findLefmMost(node.right);
  85.         candidate.left = node.left;
  86.         candidate.size = node.size;. 1point 3acres 璁哄潧
  87.         candidate.right = node.right;
  88.         if(parent.right = node) parent.right = candidate;
  89.         Else parent.left = candidate;
  90. }. more info on 1point3acres.com

  91. }. visit 1point3acres.com for more.
  92. }
  93. public Node findLeftmost(Node node){
  94.         if(node.left==null) return node;
  95.         Node.size--; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  96.         return findLeftmose(node.left);
  97. }

  98. public Node findParent(Node node){
  99.         if(root==node) return null;
  100.         Node prev = root;
  101.         Node cur = root;. 1point 3acres 璁哄潧
  102.         while(cur!=node){       
  103. if(cur.score>node.score){
  104. cur =cur.right;
  105. . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  106. }. more info on 1point3acres.com
  107. else{. from: 1point3acres.com/bbs
  108.         Cur.size--;. 1point 3acres 璁哄潧
  109.         Cur = cur.left;
  110. }
  111. }
  112. }


  113. public List<String> findByRank(int k){
  114.         if(k<0) return new ArrayList<String>();.鐣欏璁哄潧-涓浜-涓夊垎鍦
  115.         Return findByRank(root,k);
    . 1point3acres.com/bbs
  116. }. Waral 鍗氬鏈夋洿澶氭枃绔,
  117. public List<String> findByRank(Node node,int k){
  118.         if(node ==null) return new ArrayList<String>();
  119. if(node.size>k) return findByRank(node.left,k);. 1point 3acres 璁哄潧
  120. else if(node.size<k && node.size+IDSet.size()>k){
  121.         ArrayList<String> ans = new ArrayList<>();
  122.         ans.addAll(IDSet);
  123.         return ans;
  124. }
  125. else return findByRank(node.right,k-node.size-IDSet.size());
  126. .鏈枃鍘熷垱鑷1point3acres璁哄潧

  127. }
  128. . 1point 3acres 璁哄潧
  129. }. 1point 3acres 璁哄潧
复制代码


写了一下,不是平衡的,需要用avl或者red black替换一下。。。不过店面就45分钟。。。怎么可能写得完
回复 支持 反对

使用道具 举报

adiggo 发表于 2016-4-2 03:06:34 | 显示全部楼层
simplessssss 发表于 2016-4-1 23:43. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
建成balanced tree就可以了
. 1point3acres.com/bbs
店面  写成balanced tree 或者avl tree时间有点 太紧张了。。我觉得意思到了 就行。。。
回复 支持 反对

使用道具 举报

newbiee 发表于 2016-4-2 05:35:21 | 显示全部楼层
这种电面,感觉时间好紧张。。。
回复 支持 反对

使用道具 举报

jerry_lin324 发表于 2016-4-3 21:05:50 | 显示全部楼层
楼主想问下google的面试的大概流程。我已经跟一个hr约了电话面试,这个应该是跟hr聊聊,相当于第一轮电面了吧。接下来就应该是楼主你这样的写code的电面了吧。还望指教,祝楼主offer多多!
回复 支持 反对

使用道具 举报

xblwyc 发表于 2016-4-4 01:01:37 | 显示全部楼层
关键词:名次树
这题在45分钟内解决很难啊。。估计要用treap来实现才可能。。
回复 支持 反对

使用道具 举报

Alice0701 发表于 2016-4-4 06:52:43 | 显示全部楼层
店面写这个真心觉得很坑哎。。。。。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-4 14:52

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表