楼主: yzlwjs
跳转到指定楼层
上一主题 下一主题
收起左侧

脸书onsite

🔗
timpark4 2016-10-26 05:42:15 | 只看该作者
全局:
lz 能简单说下第3题的思路?
回复

使用道具 举报

🔗
speciallei 2016-10-26 23:21:18 | 只看该作者
全局:
dowhatyoufear 发表于 2016-10-25 00:42
这个多少种可能走法,比如1开始走两步,最后1-6-1,1-6-7,1-8-1,1-8-3 应该是有1,7,3三个Positions. 结 ...

如果算0的话, 0在8下面, 6也可以到达0的啊,160也是一种方案不是吗
回复

使用道具 举报

🔗
mengmeng88717 2016-10-28 09:43:09 | 只看该作者
全局:
hrl1991 发表于 2016-10-22 15:51
第三轮task schedule第一问你的space complexity是多少? 我用的hashmap的方法做space compexity是O(n) inte ...

可以只储存size(interval)的窗口吧,一个queue + 一个map, 两个都是size (interval)
回复

使用道具 举报

🔗
mengmeng88717 2016-10-28 10:01:01 | 只看该作者
全局:
第四题的思路
res = sum(dp[i][k])
dp[i][j] = sum { dp[m][j - 1] | if canReach[i][m]}
canReach : boolean[10][10]
canReach[1][6], canReach[1][8], [2][7], [2][9], [3][4], [3][8], [4][3], [4][9], [4][0], [6][1], [6][7], [6][0], [7][2], [7][6], [8][1], [8][3], [9][2], [9][4] = true
init : dp[1][0] = 1;
一维dp就可以,时间应该是O(steps), 空间O(steps + 100)
回复

使用道具 举报

🔗
weii 2016-10-28 14:01:24 | 只看该作者
全局:
楼主,请问第三问optimal是做法是怎么样的?
回复

使用道具 举报

🔗
whitney94 2016-10-30 10:02:58 | 只看该作者
全局:
mengmeng88717 发表于 2016-10-28 10:01
第四题的思路
res = sum(dp[k])
dp[j] = sum { dp[m][j - 1] | if canReach[m]}

谢谢分享~请问一下你的思路里dp不是二维的嘛,怎么用一维的就可以啊~谢谢啦

补充内容 (2016-10-30 10:05):
抱歉还有一个问题,就是得出来这个dp之后我们怎么return 所有的可能性的数量啊,我看你写了res= sum(dp[i][k]) 能问一下这里i,k都是什么吗,感谢感谢
回复

使用道具 举报

🔗
mengmeng88717 2016-10-30 13:21:52 | 只看该作者
全局:
whitney94 发表于 2016-10-30 10:02
谢谢分享~请问一下你的思路里dp不是二维的嘛,怎么用一维的就可以啊~谢谢啦

补充内容 (2016-10-30 10: ...

i指当前数字,j指走到第几部,j仅依赖j-1啊,所以可以一维,个人想法哈
回复

使用道具 举报

🔗
jacky841102 2016-10-30 19:59:59 | 只看该作者
全局:
第三题类似leetcode 358 Rearrange String k Distance Apart?
写了一下
  1. def optimalRunningTime(tasks, k):
  2.     heap = [(-v, 0, c) for c, v in collections.Counter(tasks).items()]
  3.     heapify(heap)
  4.     t = 0
  5.     lst = []
  6.     while heap:
  7.         cache = []
  8.         offset = k
  9.         tmp = None
  10.         while heap and heap[0][1] > t:
  11.             cache.append(heappop(heap))
  12.             if not tmp or cache[-1][1] < tmp[1]:
  13.                 tmp = cache[-1]
  14.         v, i, c = 0, 0, ''
  15.         if not heap:
  16.             v, i, c = tmp
  17.             t = i + 1
  18.         else:
  19.             v, i, c = heappop(heap)
  20.             t += 1
  21.         if v + 1 < 0:
  22.             heappush(heap, (v + 1, t + k, c))
  23.         lst.append(c)
  24.         for ca in cache:
  25.             if ca[2] != c:
  26.                 heappush(heap, ca)
  27.     print(lst)
  28.     return t
复制代码
回复

使用道具 举报

🔗
tamitito 2016-10-30 21:30:49 | 只看该作者
全局:
我感觉第二题挺难的啊,而且题意也不是很好理解,楼主能提供一下思路么
回复

使用道具 举报

🔗
pawprinter 2016-10-31 00:39:07 | 只看该作者
全局:
lz为什么面了四轮呀
回复

使用道具 举报

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

本版积分规则

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