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


一亩三分地论坛

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

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

google uber bb 面经 以及一些资料

[复制链接] |试试Instant~ |关注本帖
池大侠 发表于 2016-4-17 02:20:35 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 硕士 全职@Google - 内推 - 技术电面 Onsite 其他 |Fail其他

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

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

x
谷歌onsite 5轮
1: 一个maze 你有一个出发点和一个终点 问怎么样最快走道终点
具体题目是什么样子 google 一下maze 就知道了
要点是怎么表达这个图
有两种方式 一种是
class Position(object):
    def __init__(self):
        upWall = False
        downWall = False
        leftWall = False. Waral 鍗氬鏈夋洿澶氭枃绔,
        rightWall = False    另外一种是 用两个4个bit来表示 每个position
然后进行搜索。 题目大概就是这些。。  剩下讨论具体怎么approach..写起来还挺麻烦。。。
建议准备的同学好好去做一遍 类似的题目还有怎么生成一个maze

2. add one leetcode
  BST find next larger node,这题的key是 要有个parent node

3. find TOPK players and corresponding score, the score will change over time
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

     heap hashmap. or hashmap with quickselect
4. split BST with a target number into two trees, left tree are all lower equal to target right tree are all greater than target.1point3acres缃

.鏈枃鍘熷垱鑷1point3acres璁哄潧
5. leetcode island 2



hc据了 说我code 不够clean.... 方向是对的 但是做题比较慢


uber 只是店面了 跪了 题目现在看看还真简单 具体看题目吧 一个dfs其实可以解决
. from: 1point3acres.com/bbs
还有一个uber 店面是要求 写一个leetcode phone book 可以 比如你输入10 可以产生10位数以内的所有对应字母组合

follow up是你有3 台5 台20台机器 机器之前不能通信 怎么distribute work
  1. # Given a dictionary of a directed graph, representing nested groups and their members, flatten the structure and return all the groups a user belongs to directly and indirectly.

  2. # Group0 ------+--+--> Group3 ---> Group4
  3. #             /  /
  4. # Group1 ----+  /
  5. #             /
  6. # Group2 ----+
  7. #       \
  8. #        +-------------> Group5


  9. # users_by_groups
  10. # Group -> [user1, user2, ..., usern].1point3acres缃
  11. . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

  12. # Example input
  13. MEMBERS_BY_GROUPS = {-google 1point3acres
  14.     'Group0': {
  15.         'NestedGroups': ['Group3'],
  16.         'Members': ['User0', 'User1']. more info on 1point3acres.com
  17.     },
  18.     'Group1': {
  19.         'NestedGroups': ['Group3'],
  20.         'Members': ['User2', 'User3', 'User4']
  21.     }, 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  22.     'Group2': {
  23.         'NestedGroups': ['Group3', 'Group5'],
  24.         'Members': ['User4', 'User5']
  25.     },
  26.     'Group3': {
  27.         'NestedGroups': ['Group4'],
    . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  28.         'Members': ['User6', 'User7']  
  29.     },
  30.     'Group4': {. 1point 3acres 璁哄潧
  31.         'NestedGroups': [],.鐣欏璁哄潧-涓浜-涓夊垎鍦
  32.         'Members': ['User8', 'User9']
  33.     },
  34.     'Group5': {. more info on 1point3acres.com
  35.         'NestedGroups': [],
  36.         'Members': ['User10', 'User11']
  37.     }
  38. }
  39. .鐣欏璁哄潧-涓浜-涓夊垎鍦
  40. # Example output:

  41. GROUPS_BY_USERS = {'User6': ['Group1', 'Group0', 'Group3', 'Group2'],
  42.        'User7': ['Group1', 'Group0', 'Group3', 'Group2'],
  43.        'User4': ['Group1', 'Group2'],
  44.        'User5': ['Group2'],
  45.        'User2': ['Group1'],
  46.        'User3': ['Group1'],
  47.        'User0': ['Group0'],
  48.        'User1': ['Group0'],
  49.        'User8': ['Group4', 'Group1', 'Group0', 'Group3', 'Group2'],
  50.        'User9': ['Group4', 'Group1', 'Group0', 'Group3', 'Group2'],
  51.        'User10': ['Group5', 'Group2'],
  52.        'User11': ['Group5', 'Group2']
  53. }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴


  54. . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  55. def getGroup(data):
  56.     res = {}.鐣欏璁哄潧-涓浜-涓夊垎鍦
  57.     for elem in data:
  58.         for member in data[elem]['Members']:
  59.             if member not in res:
  60.                 res[member] = []
  61.                 stack = [elem]
  62.                 while stack:
  63.                     top = stack.pop()
    .鐣欏璁哄潧-涓浜-涓夊垎鍦
  64.                     res[member].append(top)
  65.                     for subelem in data:. From 1point 3acres bbs
  66.                         if top in data[subelem]['NestedGroups']:. 1point3acres.com/bbs
  67.                             stack.append(subelem).鏈枃鍘熷垱鑷1point3acres璁哄潧
  68.     for a in res:
  69.         print a, res[a]
  70.     #return res. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  71.             
  72. getGroup(MEMBERS_BY_GROUPS)
复制代码
bb 店面小哥问了 那题股票。。。 然后treenode next 那道。。后面那题装一下不懂 用了两种方法。。
不知道为什么还没给我onsite.. 所以发一下赞人品。。
附录一个自己整理的bb面经 记得用文本打开 我只是把他后缀变成pdf而已 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
-google 1point3acres

补充内容 (2016-4-17 17:29):
下载完记得 mv bb.pdf bb.txt

bb.pdf

37.16 KB, 阅读权限: 1, 下载次数: 120, 下载积分: 大米 -1 升

bb 资料 清用txt打开

评分

5

查看全部评分

 楼主| 池大侠 发表于 2016-4-18 02:26:38 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
命苦啊 发表于 2016-4-17 03:19. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
LZ我刚才下了附件,发现没法打开,那个bb.pdf是不是坏掉了。我下了两次都是不能打开

把文件格式改成txt就可以了。。。 mv bb.pdf bb.txt
回复 支持 1 反对 0

使用道具 举报

命苦啊 发表于 2016-4-17 12:19:16 | 显示全部楼层
关注一亩三分地微博:
Warald
LZ我刚才下了附件,发现没法打开,那个bb.pdf是不是坏掉了。我下了两次都是不能打开
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-4-23 01:16:49 | 显示全部楼层
想问下楼主划分BST那道题是怎么做的呢?谢谢了
回复 支持 反对

使用道具 举报

duduhaha 发表于 2016-4-23 08:59:26 | 显示全部楼层
split BST with a target number into two trees, left tree are all lower equal to target right tree are all greater than target. 1point3acres.com/bbs

这题怎么做的? 有啥follow up吗?
回复 支持 反对

使用道具 举报

dartmoor 发表于 2016-4-24 08:14:21 | 显示全部楼层
分割BST那题,稍微写了一下,用几个Test case测过
做法是return两个TreeNode,第一个是小于等于target的Tree,第二个是大于target的Tree

大家觉得这样写对吗??
  1.         public TreeNode[] split(TreeNode root, int target){
  2.                 if(root == null){ return new TreeNode[]{null, null}; }
  3.                 TreeNode left, right = null;
  4.                 if(root.val <= target){
  5.                         left = root;
  6.                         TreeNode[] rightSplit = split(root.right, target);
  7.                         root.right = rightSplit[0]; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  8.                         right = rightSplit[1];
  9.                 }else{
  10.                         right = root;. 鍥磋鎴戜滑@1point 3 acres
  11.                         TreeNode[] leftSplit = split(root.left, target);. 1point 3acres 璁哄潧
  12.                         root.left = leftSplit[1];
  13.                         left = leftSplit[0];
  14.                 }
  15.                 return new TreeNode[]{left, right};
  16.         }
复制代码
回复 支持 反对

使用道具 举报

spxlovecoding 发表于 2016-5-3 12:15:11 | 显示全部楼层
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!

想支持楼主,请点击帖子下方的"好苗""分享""收藏"键,酌情给楼主加大米(系统不扣你自己的分)。
积分不够看不了帖子,请参考论坛导航里的"帮助","新手提纲"里有攒积分指南
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-5-26 15:59

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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