一亩三分地论坛

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

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

google uber bb 面经 以及一些资料

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

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

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

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

x
谷歌onsite 5轮. 1point 3acres 璁哄潧
1: 一个maze 你有一个出发点和一个终点 问怎么样最快走道终点
具体题目是什么样子 google 一下maze 就知道了 .1point3acres缃
要点是怎么表达这个图
有两种方式 一种是
class Position(object):
    def __init__(self):
        upWall = False
        downWall = False
        leftWall = False
        rightWall = False    另外一种是 用两个4个bit来表示 每个position.鐣欏璁哄潧-涓浜-涓夊垎鍦
然后进行搜索。 题目大概就是这些。。  剩下讨论具体怎么approach..写起来还挺麻烦。。。. more info on 1point3acres.com
建议准备的同学好好去做一遍 类似的题目还有怎么生成一个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
. from: 1point3acres.com/bbs

     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. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
. Waral 鍗氬鏈夋洿澶氭枃绔,

5. leetcode island 2 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

.鏈枃鍘熷垱鑷1point3acres璁哄潧

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


uber 只是店面了 跪了 题目现在看看还真简单 具体看题目吧 一个dfs其实可以解决
. From 1point 3acres 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]


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

  38. # Example output:

  39. GROUPS_BY_USERS = {'User6': ['Group1', 'Group0', 'Group3', 'Group2'],
  40.        'User7': ['Group1', 'Group0', 'Group3', 'Group2'],
  41.        'User4': ['Group1', 'Group2'],
  42.        'User5': ['Group2'],
  43.        'User2': ['Group1'],
  44.        'User3': ['Group1'],.鐣欏璁哄潧-涓浜-涓夊垎鍦
  45.        'User0': ['Group0'],
  46.        'User1': ['Group0'],
  47.        'User8': ['Group4', 'Group1', 'Group0', 'Group3', 'Group2'],. From 1point 3acres bbs
  48.        'User9': ['Group4', 'Group1', 'Group0', 'Group3', 'Group2'],
  49.        'User10': ['Group5', 'Group2'],
  50.        'User11': ['Group5', 'Group2']
  51. }


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


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

bb.pdf

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

bb 资料 清用txt打开

评分

5

查看全部评分

 楼主| 池大侠 发表于 2016-4-18 02:26:38 | 显示全部楼层
命苦啊 发表于 2016-4-17 03:19. visit 1point3acres.com for more.
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
.鐣欏璁哄潧-涓浜-涓夊垎鍦
大家觉得这样写对吗??
  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;
  11.                         TreeNode[] leftSplit = split(root.left, target);
  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!

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-1-17 23:10

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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