脸书onsite

lz 能简单说下第3题的思路？

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也是一种方案不是吗

hrl1991 发表于 2016-10-22 15:51
第三轮task schedule第一问你的space complexity是多少? 我用的hashmap的方法做space compexity是O(n) inte ...

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

第四题的思路
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)

楼主，请问第三问optimal是做法是怎么样的？

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都是什么吗，感谢感谢

whitney94 发表于 2016-10-30 10:02
谢谢分享～请问一下你的思路里dp不是二维的嘛，怎么用一维的就可以啊～谢谢啦

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

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

第三题类似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

复制代码

我感觉第二题挺难的啊，而且题意也不是很好理解，楼主能提供一下思路么

lz为什么面了四轮呀