[职场感言] 工作一年了,聊聊三件事

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 13055|回复: 70
收起左侧

google 电面 挂经

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

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

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

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

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


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

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

评分

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。或者 ...
-google 1point3acres
有重复的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. more info on 1point3acres
如果存id的话 那怎么能在lgn找到第k个点呢?

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

使用道具 举报

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

使用道具 举报

 楼主| 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);. more info on 1point3acres
  10.         this.score = score;.1point3acres网
  11.     }
  12. }.1point3acres网
  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){. 1point 3acres 论坛
  23. IDSet.remove(ID);
  24. }
  25. else{
  26.         delete(node);
  27. }
  28.         Node newNode =insert(ID, score);-google 1point3acres
  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){.1point3acres网
  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++;
  43.         insert(n.left,ID,score);
  44. }. 牛人云集,一亩三分地
  45. else{
  46.         insert(n.right,ID,score);. from: 1point3acres
  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){
  55.         if( node.left==null&& node.right==null) root=null;
  56.         else if(node.left ==null){
  57.                 root= node.right;
  58. }
  59. else if(node.right == null){. 1point 3acres 论坛
  60. root = node.left;
  61. . 牛人云集,一亩三分地
  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;
  68. rootCand.right = root.right;
  69. }
  70. }. Waral 博客有更多文章,
  71. else{
  72.         if(node.left == null && node.right == null){
  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;
    . From 1point 3acres bbs
  83. }
  84. else{-google 1point3acres
  85.         Node candidate = findLefmMost(node.right);. 1point 3acres 论坛
  86.         candidate.left = node.left;
  87.         candidate.size = node.size;. 一亩-三分-地,独家发布
  88.         candidate.right = node.right;
  89.         if(parent.right = node) parent.right = candidate;
  90.         Else parent.left = candidate;. 一亩-三分-地,独家发布
  91. }

  92. }
  93. }
  94. public Node findLeftmost(Node node){
  95.         if(node.left==null) return node;
  96.         Node.size--;. 牛人云集,一亩三分地
  97.         return findLeftmose(node.left);
  98. }

  99. public Node findParent(Node node){
  100.         if(root==node) return null;
  101.         Node prev = root;
  102.         Node cur = root;
  103.         while(cur!=node){       
  104. if(cur.score>node.score){
  105. cur =cur.right;

  106. }
  107. else{. 围观我们@1point 3 acres
  108.         Cur.size--;. 留学申请论坛-一亩三分地
  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);
  116. }
  117. public List<String> findByRank(Node node,int k){
  118.         if(node ==null) return new ArrayList<String>();. From 1point 3acres bbs
  119. if(node.size>k) return findByRank(node.left,k);. 1point3acres
  120. else if(node.size<k && node.size+IDSet.size()>k){
  121.         ArrayList<String> ans = new ArrayList<>();
  122.         ans.addAll(IDSet);. visit 1point3acres for more.
  123.         return ans;
  124. }
  125. else return findByRank(node.right,k-node.size-IDSet.size());

  126. . from: 1point3acres
  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 | 显示全部楼层
店面写这个真心觉得很坑哎。。。。。
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-24 14:33

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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