一亩三分地论坛

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

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

google uber bb 面经 以及一些资料

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

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

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

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

x
谷歌onsite 5轮
1: 一个maze 你有一个出发点和一个终点 问怎么样最快走道终点
具体题目是什么样子 google 一下maze 就知道了
要点是怎么表达这个图
有两种方式 一种是
class Position(object):. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
    def __init__(self):
        upWall = False
        downWall = False
        leftWall = False
        rightWall = False    另外一种是 用两个4个bit来表示 每个position. From 1point 3acres bbs
然后进行搜索。 题目大概就是这些。。  剩下讨论具体怎么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


5. leetcode island 2

. from: 1point3acres.com/bbs
. visit 1point3acres.com for more.
hc据了 说我code 不够clean.... 方向是对的 但是做题比较慢


uber 只是店面了 跪了 题目现在看看还真简单 具体看题目吧 一个dfs其实可以解决

还有一个uber 店面是要求 写一个leetcode phone book 可以 比如你输入10 可以产生10位数以内的所有对应字母组合
. visit 1point3acres.com for more.
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. .鐣欏璁哄潧-涓浜-涓夊垎鍦
  3. # Group0 ------+--+--> Group3 ---> Group4. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  4. #             /  /.1point3acres缃
  5. # Group1 ----+  /
  6. #             /. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  7. # Group2 ----+
  8. #       \.1point3acres缃
  9. #        +-------------> Group5


  10. # users_by_groups
  11. # Group -> [user1, user2, ..., usern]


  12. # Example input
  13. MEMBERS_BY_GROUPS = {
  14.     'Group0': {
  15.         'NestedGroups': ['Group3'],
  16.         'Members': ['User0', 'User1']
  17.     },
  18.     'Group1': {
  19.         'NestedGroups': ['Group3'],
  20.         'Members': ['User2', 'User3', 'User4']
  21.     },
  22.     'Group2': {
  23.         'NestedGroups': ['Group3', 'Group5'],. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  24.         'Members': ['User4', 'User5']. from: 1point3acres.com/bbs
  25.     },
  26.     'Group3': {
  27.         'NestedGroups': ['Group4'],
  28.         'Members': ['User6', 'User7']  
  29.     },
  30.     'Group4': {
  31.         'NestedGroups': [],. more info on 1point3acres.com
  32.         'Members': ['User8', 'User9']
  33.     },
  34.     'Group5': {
  35.         'NestedGroups': [],
  36.         'Members': ['User10', 'User11']
  37.     }
  38. }

  39. # Example output:

  40. GROUPS_BY_USERS = {'User6': ['Group1', 'Group0', 'Group3', 'Group2'],. visit 1point3acres.com for more.
  41.        'User7': ['Group1', 'Group0', 'Group3', 'Group2'],
  42.        'User4': ['Group1', 'Group2'],
  43.        'User5': ['Group2'],
  44.        'User2': ['Group1'],
  45.        'User3': ['Group1'],.鏈枃鍘熷垱鑷1point3acres璁哄潧
  46.        'User0': ['Group0'],
  47.        'User1': ['Group0'],. from: 1point3acres.com/bbs
  48.        'User8': ['Group4', 'Group1', 'Group0', 'Group3', 'Group2'],
  49.        'User9': ['Group4', 'Group1', 'Group0', 'Group3', 'Group2'],
  50.        'User10': ['Group5', 'Group2'],
  51.        'User11': ['Group5', 'Group2']
  52. }


  53. def getGroup(data):. From 1point 3acres bbs
  54.     res = {}
  55.     for elem in data:
  56.         for member in data[elem]['Members']:
  57.             if member not in res:
  58.                 res[member] = []
  59.                 stack = [elem]. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  60.                 while stack:
  61.                     top = stack.pop()
  62.                     res[member].append(top)
  63.                     for subelem in data:
  64.                         if top in data[subelem]['NestedGroups']:
  65.                             stack.append(subelem)
  66.     for a in res:
  67.         print a, res[a]-google 1point3acres
  68.     #return res
  69.             . Waral 鍗氬鏈夋洿澶氭枃绔,
  70. getGroup(MEMBERS_BY_GROUPS)
复制代码
bb 店面小哥问了 那题股票。。。 然后treenode next 那道。。后面那题装一下不懂 用了两种方法。。
不知道为什么还没给我onsite.. 所以发一下赞人品。。
附录一个自己整理的bb面经 记得用文本打开 我只是把他后缀变成pdf而已


补充内容 (2016-4-17 17:29): 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
下载完记得 mv bb.pdf bb.txt

bb.pdf

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

bb 资料 清用txt打开

评分

5

查看全部评分

 楼主| 池大侠 发表于 2016-4-18 02:26:38 | 显示全部楼层
命苦啊 发表于 2016-4-17 03:19
LZ我刚才下了附件,发现没法打开,那个bb.pdf是不是坏掉了。我下了两次都是不能打开

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

使用道具 举报

命苦啊 发表于 2016-4-17 12:19:16 | 显示全部楼层
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

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

使用道具 举报

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

大家觉得这样写对吗??
  1.         public TreeNode[] split(TreeNode root, int target){
  2.                 if(root == null){ return new TreeNode[]{null, null}; }
  3.                 TreeNode left, right = null;
    . From 1point 3acres bbs
  4.                 if(root.val <= target){
  5.                         left = root;
  6.                         TreeNode[] rightSplit = split(root.right, target);. Waral 鍗氬鏈夋洿澶氭枃绔,
  7.                         root.right = rightSplit[0];. Waral 鍗氬鏈夋洿澶氭枃绔,
  8.                         right = rightSplit[1];
  9.                 }else{
  10.                         right = root;
  11.                         TreeNode[] leftSplit = split(root.left, target);
  12.                         root.left = leftSplit[1];
  13.                         left = leftSplit[0];
  14.                 }. visit 1point3acres.com for more.
  15.                 return new TreeNode[]{left, right}; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  16.         }
复制代码
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 19:24

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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