📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
楼主: sheepmiemies
跳转到指定楼层
上一主题 下一主题
收起左侧

刚结束的google onsite/Seattle office

 
🔗
CrossTheWall 2016-5-9 13:01:43 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

🔗
jeremy_sea 2016-5-9 14:44:37 | 只看该作者
全局:
4.1题 应该有多种解法,不同操作的trade off。 其实和2d matrix mutable有点点像。 随便写了下
  1. from collections import defaultdict
  2. class StrOldIndex:
  3.     def __init__(self, s):
  4.         self.str = s
  5.         self.index_map = {}
  6.         for i, c in enumerate(s):
  7.             self.index_map[i] = i

  8.     # O(n) to add str. But O(1) to read the str
  9.     def add(self, i, c):
  10.         idx = self.index_map[i]
  11.         self.str = self.str[:idx] + c +self.str[idx:]
  12.         for k, v in self.index_map.iteritems():
  13.             if k >= i:
  14.                 self.index_map[k] += 1

  15.     # O(n) in str replace
  16.     def replace(self, i, c):
  17.         idx = self.index_map[i]
  18.         self.str = self.str[:idx] + c + self.str[idx+1:]

  19.     # O(n) in delete, need to update indexes after i
  20.     def delete(self,i):
  21.         self.replace(i, '')
  22.         for k, v in self.index_map.iteritems():
  23.             if k >= i:
  24.                 self.index_map[k] -= 1

  25. class StrOldIndex2:
  26.     def __init__(self,s):
  27.         self.str = s
  28.         self.str_lst = defaultdict(list)
  29.         for i, c in enumerate(s):
  30.             self.str_lst[i].append(c)

  31.     # O(1) in add. But read takes O(n)
  32.     def add(self, i, c):
  33.         self.str_lst[i].append(c)

  34.     def replace(self, i, c):
  35.         old_list = self.str_lst[i]
  36.         new_list = [c].extend(old_list[1:])
  37.         self.str_lst[i] = new_list

  38.     def delete(self, i):
  39.         self.replace(i, '')

  40. s=StrOldIndex('abc')
  41. s.add(1,'a')
  42. assert s.str == 'aabc'
  43. s.add(2,'c')
  44. assert s.str == 'aabcc'

复制代码

回复

使用道具 举报

🔗
jeremy_sea 2016-5-9 14:51:25 | 只看该作者
全局:
第三题非常straightforward. 代码如下,有需要的拿去
  1. class Solution:
  2.     def __init__(self, a1, a2):
  3.         self.index_mapping = {}
  4.         self.pattern_mapping = {}
  5.         assert len(a1) == len(a2)
  6.         for i, d in enumerate(a1):
  7.             self.index_mapping[d] = i

  8.         for i, d in enumerate(a2):
  9.             self.pattern_mapping[i] = self.index_mapping[d]


  10.     def matching(self, input):
  11.         res = []
  12.         assert len(input)==len(self.index_mapping)
  13.         for i, d in enumerate(input):
  14.             res.append(input[self.pattern_mapping[i]])
  15.         return res


  16. a1 = [4,3,2,1]
  17. b1 = [1,2,3,4]
  18. s=Solution(a1, b1)
  19. assert s.matching([5,6,7,8]) == [8,7,6,5]
  20. a1 = [1,2,3,4]
  21. b1 = [2,4,1,3]
  22. s2=Solution(a1, b1)
  23. assert s2.matching([5,6,7,8]) == [6,8,5,7]
复制代码
回复

使用道具 举报

🔗
jeremy_sea 2016-5-9 14:57:46 | 只看该作者
全局:
感觉第二题考点是get random index in a list. 可以用O(1)来做.
the key factor to make every team happy is log is randomly/fairly distributed. 有不同意见欢迎指正
回复

使用道具 举报

🔗
stellari 2016-5-9 15:14:11 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

🔗
 楼主| sheepmiemies 2016-5-9 23:06:26 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

🔗
 楼主| sheepmiemies 2016-5-9 23:19:18 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

🔗
CrossTheWall 2016-5-9 23:21:38 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

🔗
 楼主| sheepmiemies 2016-5-9 23:25:55 | 只看该作者
全局:
stellari 发表于 2016-5-9 15:14
或者这样怎么样?一开始先向右转3次(也就是转到左边),然后forward到不能再前进为止,再向右转1次,然 ...

嗯嗯,感觉这个方法不错,没有墙就先找到一堵墙!我当时要是反应过来就好了。。。暂时想不出什么反例了
回复

使用道具 举报

🔗
 楼主| sheepmiemies 2016-5-9 23:31:32 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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