May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 10737|回复: 70
收起左侧

google 电面 挂经

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

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

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 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
我得想法是用binary search tree的话,节点是按score来存,id存在一个arraylist里头,如果有相同的score,就加入到arraylist里,再加上左右孩子和自己的个数。这样update和findbyrank都能在logn的复杂度完成
回复 支持 1 反对 0

使用道具 举报

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

使用道具 举报

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;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  3.     public HashSet<String> IDSet;
  4.     public int size;
  5.     public Node left;. 1point3acres.com/bbs
  6.     public Node right;
  7.     Node(String ID, int score){. 1point3acres.com/bbs
  8.         IDSet = new HashSet<String>();
  9.         IDSet.add(ID);
  10.         this.score = score;
  11.     }
  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){. 1point3acres.com/bbs
  20.         if(scoreIDMap.containsKey(ID)){
  21.                 Node  node = scoreIDMap.get(ID);. Waral 鍗氬鏈夋洿澶氭枃绔,
  22.                 if(node.IDSet.size()>1){
  23. IDSet.remove(ID);
  24. }. 1point3acres.com/bbs
  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. }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  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){
  39.                 n.IDSet.add(ID);.鐣欏璁哄潧-涓浜-涓夊垎鍦
  40. }
  41. else if(n.score>score){
  42.         n.size++;. 鍥磋鎴戜滑@1point 3 acres
  43.         insert(n.left,ID,score);
  44. }
  45. else{
  46.         insert(n.right,ID,score);. From 1point 3acres bbs
  47. }
  48. }
  49. }
  50. public void delete(Node node){
  51. //find parent of node
  52. //check three case: leaf, one child, two children. 鍥磋鎴戜滑@1point 3 acres
  53. Node parent = findParent(node);        .鐣欏璁哄潧-涓浜-涓夊垎鍦
  54. if(parent==null){
  55.         if( node.left==null&& node.right==null) root=null;
  56.         else if(node.left ==null){
  57.                 root= node.right;. visit 1point3acres.com for more.
  58. }
  59. else if(node.right == null){
  60. root = node.left;
  61. . from: 1point3acres.com/bbs
  62. }
  63. else{
  64.         //find leftmost node of right subtree
  65. Node rootCand = findLeftmost(root.right);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  66. rootCand.left = root.left;
  67. rootCand.size = root.size;
    . visit 1point3acres.com for more.
  68. rootCand.right = root.right;
  69. }
  70. }-google 1point3acres
  71. else{
  72.         if(node.left == null && node.right == null){. From 1point 3acres bbs
  73.                 if(parent.left == node) parent.left =null;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  74.                         else parent.right = null;
  75. }
  76. else if(node.left == null){
  77.         if(parent.left == node)parent.left = node.right;
  78.         else parent.right = node.right;
  79. }
  80. else if(node.right == null){
  81.         if(parent.right == node) parent.right = node.left;
  82.         else parent.left = nodel.left;
  83. }
  84. else{
  85.         Node candidate = findLefmMost(node.right);
  86.         candidate.left = node.left;
  87.         candidate.size = node.size;. 1point 3acres 璁哄潧
  88.         candidate.right = node.right;
  89.         if(parent.right = node) parent.right = candidate;
  90.         Else parent.left = candidate;
  91. }. Waral 鍗氬鏈夋洿澶氭枃绔,

  92. }
  93. }
  94. public Node findLeftmost(Node node){
  95.         if(node.left==null) return node;
  96.         Node.size--;
  97.         return findLeftmose(node.left);. From 1point 3acres bbs
  98. }

  99. public Node findParent(Node node){. 鍥磋鎴戜滑@1point 3 acres
  100.         if(root==node) return null;
  101.         Node prev = root;
  102.         Node cur = root;-google 1point3acres
  103.         while(cur!=node){       
  104. if(cur.score>node.score){
  105. cur =cur.right;

  106. }
    鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  107. else{
  108.         Cur.size--;
  109.         Cur = cur.left;. from: 1point3acres.com/bbs
  110. }
  111. }
  112. }-google 1point3acres


  113. public List<String> findByRank(int k){
  114.         if(k<0) return new ArrayList<String>();
  115.         Return findByRank(root,k);
  116. }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  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);
  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. }
  127. . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  128. }
复制代码


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

使用道具 举报

adiggo 发表于 2016-4-2 03:06:34 | 显示全部楼层
simplessssss 发表于 2016-4-1 23:43. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
建成balanced tree就可以了

鏉ユ簮涓浜.涓夊垎鍦拌鍧. 店面  写成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 | 显示全部楼层
店面写这个真心觉得很坑哎。。。。。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-5-28 12:59

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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