由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 报F和G的offer+面经
相关主题
问个简单算法题请教Google offer negotiation
Amazon offer + 面经 ... How to negotiate effectively?Google offer接受了后发现股票给的比别人少,怎么办?
报个fresh的offer,兼面经顺便求建议stock option in an offer
offer 选择, facebook VS google ?Facebook还是Google?
关于版上报的offer的一点疑问Offer选择Facebook & Google 更新,能给一家看另一家的offer le
找工作结束,报offerG家进去多久能到20万刀?
报G的offer,咨询一下各位G大神关于offer细节报个G家的offer, 同时求建议!
现在进facebook能发多少GSU呀?说说最近几个offer
相关话题的讨论汇总
话题: bmin话题: amin话题: 链表话题: cmin话题: cmax
进入JobHunting版参与讨论
1 (共1页)
t*****s
发帖数: 39
1
找工作算告一段落了,这一个多月从版上学到了很多,非常感谢大家,也分享点儿自己
的情况。本人cs fresh phd,投了F和G,准备主要是leetcode,做了50题左右,还有就
是板上的面经。强烈推荐leetcode,特别是对于准备时间有限的同学,基本覆盖了各式
各样的题。虽然最后面试没遇到做过的coding题,但基本都差不多。
0. 给定一个双向链表,以及一个数组。数组里存着一部分链表节点的指针。问数组里
的指针们指向的节点在双向列表中可以分成几个连续的blocks。接着问如果是单向链表
怎么做。算法复杂度分别是什么。
1. coke machines。大中小三个可乐机,每按一次出可乐量分别在[Amin,Amax], [Bmin
, Bmax], [Cmin, Cmax]之间,但不能确定具体容量是多少,现在想通过按这三个可乐
机,达到容量为[D, E]之间的可乐,问能否做到。也就是能否找到非负整数x, y, z使
得x*Amin+y*Bmin+z*Cmin>=D并且x*Amax+y*Bmax+z*Cmax<=E。感觉是个扩展的背包问题
,我给了穷举法和DP的解法,不过面试官最后说有个复杂度不依赖于D和E的解法,现在
也不知道怎么做。
2. 二叉树遍历。每个节点有left/right/parent指针,只允许使用O(1)空间而不用栈。
3. 含有大量URL的文件里查找频率最高的K个URL。先给单机哈希表的解法,内存不够的
情况,给了按哈希值把大文件拆成小文件的解法。接着被问并行化,给了MapReduce的
解法。接着被问哈希表相关的计算题,M个slots的哈希表(哈希值范围是1~M,用链表
处理冲突),往里放了N个元素,假设他们的哈希值是随机的均匀分布,问slots里元素
个数的分布,也就是balls and bins的问题。不用coding。
4. 链表的插入,删除等,基本没算法,而是看coding的细节。
5. 多线程和多进程。包括哪些状态是线程间共享的哪些状态是每个线程自己的等等。
不用coding。
6. 设计题。设计web crawler。包括网页的存储,crawler任务调度等。不用coding。
package方面F和G差不多。
G: 127k base, 15% bonus, 45k sign-on, 300 GSU.
F: 130k base, 10% semi-annual bonus, 100k sign-on, $180k RSU.
祝大家面试顺利拿到好offer!
r**h
发帖数: 1288
2
100k sign on,300gsu...
楼主太牛了,超级膜拜呀,应该是牛校phd吧
cong!!

Bmin

【在 t*****s 的大作中提到】
: 找工作算告一段落了,这一个多月从版上学到了很多,非常感谢大家,也分享点儿自己
: 的情况。本人cs fresh phd,投了F和G,准备主要是leetcode,做了50题左右,还有就
: 是板上的面经。强烈推荐leetcode,特别是对于准备时间有限的同学,基本覆盖了各式
: 各样的题。虽然最后面试没遇到做过的coding题,但基本都差不多。
: 0. 给定一个双向链表,以及一个数组。数组里存着一部分链表节点的指针。问数组里
: 的指针们指向的节点在双向列表中可以分成几个连续的blocks。接着问如果是单向链表
: 怎么做。算法复杂度分别是什么。
: 1. coke machines。大中小三个可乐机,每按一次出可乐量分别在[Amin,Amax], [Bmin
: , Bmax], [Cmin, Cmax]之间,但不能确定具体容量是多少,现在想通过按这三个可乐
: 机,达到容量为[D, E]之间的可乐,问能否做到。也就是能否找到非负整数x, y, z使

h********5
发帖数: 114
3
看来楼主本身的实力够强,leetcode只做了50题就拿了两个大offer

Bmin

【在 t*****s 的大作中提到】
: 找工作算告一段落了,这一个多月从版上学到了很多,非常感谢大家,也分享点儿自己
: 的情况。本人cs fresh phd,投了F和G,准备主要是leetcode,做了50题左右,还有就
: 是板上的面经。强烈推荐leetcode,特别是对于准备时间有限的同学,基本覆盖了各式
: 各样的题。虽然最后面试没遇到做过的coding题,但基本都差不多。
: 0. 给定一个双向链表,以及一个数组。数组里存着一部分链表节点的指针。问数组里
: 的指针们指向的节点在双向列表中可以分成几个连续的blocks。接着问如果是单向链表
: 怎么做。算法复杂度分别是什么。
: 1. coke machines。大中小三个可乐机,每按一次出可乐量分别在[Amin,Amax], [Bmin
: , Bmax], [Cmin, Cmax]之间,但不能确定具体容量是多少,现在想通过按这三个可乐
: 机,达到容量为[D, E]之间的可乐,问能否做到。也就是能否找到非负整数x, y, z使

c******t
发帖数: 1500
4
太牛了!
恭喜!
f*******b
发帖数: 520
5
太牛了
y*******n
发帖数: 19
6


Bmin

【在 t*****s 的大作中提到】
: 找工作算告一段落了,这一个多月从版上学到了很多,非常感谢大家,也分享点儿自己
: 的情况。本人cs fresh phd,投了F和G,准备主要是leetcode,做了50题左右,还有就
: 是板上的面经。强烈推荐leetcode,特别是对于准备时间有限的同学,基本覆盖了各式
: 各样的题。虽然最后面试没遇到做过的coding题,但基本都差不多。
: 0. 给定一个双向链表,以及一个数组。数组里存着一部分链表节点的指针。问数组里
: 的指针们指向的节点在双向列表中可以分成几个连续的blocks。接着问如果是单向链表
: 怎么做。算法复杂度分别是什么。
: 1. coke machines。大中小三个可乐机,每按一次出可乐量分别在[Amin,Amax], [Bmin
: , Bmax], [Cmin, Cmax]之间,但不能确定具体容量是多少,现在想通过按这三个可乐
: 机,达到容量为[D, E]之间的可乐,问能否做到。也就是能否找到非负整数x, y, z使

f*******t
发帖数: 7549
7
大牛!

★ 发自iPhone App: ChineseWeb 7.8

【在 t*****s 的大作中提到】
: 找工作算告一段落了,这一个多月从版上学到了很多,非常感谢大家,也分享点儿自己
: 的情况。本人cs fresh phd,投了F和G,准备主要是leetcode,做了50题左右,还有就
: 是板上的面经。强烈推荐leetcode,特别是对于准备时间有限的同学,基本覆盖了各式
: 各样的题。虽然最后面试没遇到做过的coding题,但基本都差不多。
: 0. 给定一个双向链表,以及一个数组。数组里存着一部分链表节点的指针。问数组里
: 的指针们指向的节点在双向列表中可以分成几个连续的blocks。接着问如果是单向链表
: 怎么做。算法复杂度分别是什么。
: 1. coke machines。大中小三个可乐机,每按一次出可乐量分别在[Amin,Amax], [Bmin
: , Bmax], [Cmin, Cmax]之间,但不能确定具体容量是多少,现在想通过按这三个可乐
: 机,达到容量为[D, E]之间的可乐,问能否做到。也就是能否找到非负整数x, y, z使

c********e
发帖数: 186
8
牛,强烈恭喜!

Bmin

【在 t*****s 的大作中提到】
: 找工作算告一段落了,这一个多月从版上学到了很多,非常感谢大家,也分享点儿自己
: 的情况。本人cs fresh phd,投了F和G,准备主要是leetcode,做了50题左右,还有就
: 是板上的面经。强烈推荐leetcode,特别是对于准备时间有限的同学,基本覆盖了各式
: 各样的题。虽然最后面试没遇到做过的coding题,但基本都差不多。
: 0. 给定一个双向链表,以及一个数组。数组里存着一部分链表节点的指针。问数组里
: 的指针们指向的节点在双向列表中可以分成几个连续的blocks。接着问如果是单向链表
: 怎么做。算法复杂度分别是什么。
: 1. coke machines。大中小三个可乐机,每按一次出可乐量分别在[Amin,Amax], [Bmin
: , Bmax], [Cmin, Cmax]之间,但不能确定具体容量是多少,现在想通过按这三个可乐
: 机,达到容量为[D, E]之间的可乐,问能否做到。也就是能否找到非负整数x, y, z使

c******o
发帖数: 534
9
niu
a********m
发帖数: 15480
10
cong! + 赞!
0. 要求复杂度和空间不?
1. dp咋弄?感觉还是dfs呀。不依赖DE是比较神奇。
相关主题
找工作结束,报offer请教Google offer negotiation
报G的offer,咨询一下各位G大神关于offer细节Google offer接受了后发现股票给的比别人少,怎么办?
现在进facebook能发多少GSU呀?stock option in an offer
进入JobHunting版参与讨论
f*****g
发帖数: 74
11
不相信。这是别有用心的哄抬物价。

Bmin

【在 t*****s 的大作中提到】
: 找工作算告一段落了,这一个多月从版上学到了很多,非常感谢大家,也分享点儿自己
: 的情况。本人cs fresh phd,投了F和G,准备主要是leetcode,做了50题左右,还有就
: 是板上的面经。强烈推荐leetcode,特别是对于准备时间有限的同学,基本覆盖了各式
: 各样的题。虽然最后面试没遇到做过的coding题,但基本都差不多。
: 0. 给定一个双向链表,以及一个数组。数组里存着一部分链表节点的指针。问数组里
: 的指针们指向的节点在双向列表中可以分成几个连续的blocks。接着问如果是单向链表
: 怎么做。算法复杂度分别是什么。
: 1. coke machines。大中小三个可乐机,每按一次出可乐量分别在[Amin,Amax], [Bmin
: , Bmax], [Cmin, Cmax]之间,但不能确定具体容量是多少,现在想通过按这三个可乐
: 机,达到容量为[D, E]之间的可乐,问能否做到。也就是能否找到非负整数x, y, z使

f*********m
发帖数: 726
12
Fresh Ph.D.,
G: 127k base, 15% bonus, 45k sign-on, 300 GSU.
F: 130k base, 10% semi-annual bonus, 100k sign-on, $180k RSU.
这才是大牛啊!!!

Bmin

【在 t*****s 的大作中提到】
: 找工作算告一段落了,这一个多月从版上学到了很多,非常感谢大家,也分享点儿自己
: 的情况。本人cs fresh phd,投了F和G,准备主要是leetcode,做了50题左右,还有就
: 是板上的面经。强烈推荐leetcode,特别是对于准备时间有限的同学,基本覆盖了各式
: 各样的题。虽然最后面试没遇到做过的coding题,但基本都差不多。
: 0. 给定一个双向链表,以及一个数组。数组里存着一部分链表节点的指针。问数组里
: 的指针们指向的节点在双向列表中可以分成几个连续的blocks。接着问如果是单向链表
: 怎么做。算法复杂度分别是什么。
: 1. coke machines。大中小三个可乐机,每按一次出可乐量分别在[Amin,Amax], [Bmin
: , Bmax], [Cmin, Cmax]之间,但不能确定具体容量是多少,现在想通过按这三个可乐
: 机,达到容量为[D, E]之间的可乐,问能否做到。也就是能否找到非负整数x, y, z使

P****2
发帖数: 197
13
这个能不能用整数规划?随便加个目标函数。。要是IP的LP relaxation没解,IP直接就
是没解了。。不然用整数规划分支定界做。。每次用LP relaxation求bound剪枝,解LP
比如单纯形法和DE的确没关系

【在 a********m 的大作中提到】
: cong! + 赞!
: 0. 要求复杂度和空间不?
: 1. dp咋弄?感觉还是dfs呀。不依赖DE是比较神奇。

d*********2
发帖数: 10
14
膜拜楼主!小弱苦逼刷题中。。。
a********m
发帖数: 15480
15
lp不懂。。。。就知道把数据扔给resolver算就完了,但是按说应该不会这么考算法吧。

LP

【在 P****2 的大作中提到】
: 这个能不能用整数规划?随便加个目标函数。。要是IP的LP relaxation没解,IP直接就
: 是没解了。。不然用整数规划分支定界做。。每次用LP relaxation求bound剪枝,解LP
: 比如单纯形法和DE的确没关系

h********5
发帖数: 114
16
同弱,同刷

【在 d*********2 的大作中提到】
: 膜拜楼主!小弱苦逼刷题中。。。
t*****s
发帖数: 39
17
0. 我是从array构造了个set,然后每次从set里弹出一个节点指针后,在双向列表里从
该节点往两边检索并不断从set里删除元素。问了这个算法的复杂度,应该就是时间空
间都是O(size(array)).
1. 我当时是用(lower, upper)作为DP状态,以(D,E)作为起始值,然后检查(D-Amin, E
-Amax), (D-Bmin, E-Bmax), (D-Cmin, E-Cmax) 并递归下去,如果达到某个(a, b)状
态其中a是非正数而b是非负数的话,就是有解,如果某个状态开始的所有分支达到的状
态都是a,b都是负数的话就记录该状态为失败。直接的dfs而不记录失败的状态好像会有
些搜索重复吧?

【在 a********m 的大作中提到】
: cong! + 赞!
: 0. 要求复杂度和空间不?
: 1. dp咋弄?感觉还是dfs呀。不依赖DE是比较神奇。

w***y
发帖数: 6251
18
大牛 ,膜拜!!!
m******s
发帖数: 1469
19
Zan!

Bmin

【在 t*****s 的大作中提到】
: 找工作算告一段落了,这一个多月从版上学到了很多,非常感谢大家,也分享点儿自己
: 的情况。本人cs fresh phd,投了F和G,准备主要是leetcode,做了50题左右,还有就
: 是板上的面经。强烈推荐leetcode,特别是对于准备时间有限的同学,基本覆盖了各式
: 各样的题。虽然最后面试没遇到做过的coding题,但基本都差不多。
: 0. 给定一个双向链表,以及一个数组。数组里存着一部分链表节点的指针。问数组里
: 的指针们指向的节点在双向列表中可以分成几个连续的blocks。接着问如果是单向链表
: 怎么做。算法复杂度分别是什么。
: 1. coke machines。大中小三个可乐机,每按一次出可乐量分别在[Amin,Amax], [Bmin
: , Bmax], [Cmin, Cmax]之间,但不能确定具体容量是多少,现在想通过按这三个可乐
: 机,达到容量为[D, E]之间的可乐,问能否做到。也就是能否找到非负整数x, y, z使

r*********n
发帖数: 4553
20
2 cents for the coke machine problem
Let x = [x1, x2, x3]', where x1, x2, x3 is the number of times you push
machine A, B, C respectively.
The following needs to be satisfied:
[Amax, Bmax, Cmax]*x <= E,
[Amin, Bmin, Cmin]*x >= D,
x >= 0, x is an integer vector
A necessary and sufficient condition for the answer to the original question
being equal to yes is that the following optimization problem has a
solution:
min c'x
st Ax <= b, x >= 0, x is an integer vector
where
c = [1, 1, 1]', b = [E, -D]' and
A = [Amax, Bmax, Cmax;
-Amin, -Bmin, -Cmin ]
This is an integer programming problem, which is in general NP-hard. Since
the dimension is small for this problem, I think we can simply do an
exhaustive search (dfs or bfs) starting from the origin.
相关主题
Facebook还是Google?报个G家的offer, 同时求建议!
Offer选择Facebook & Google 更新,能给一家看另一家的offer le说说最近几个offer
G家进去多久能到20万刀?报一个google的offer吧
进入JobHunting版参与讨论
c********p
发帖数: 1969
21
奇怪,怎么会问多线程的?
l*******0
发帖数: 63
22
为啥我感觉,应该是a是非负,b是非正时说明存在呢?请您在解释一下?谢谢。

E

【在 t*****s 的大作中提到】
: 0. 我是从array构造了个set,然后每次从set里弹出一个节点指针后,在双向列表里从
: 该节点往两边检索并不断从set里删除元素。问了这个算法的复杂度,应该就是时间空
: 间都是O(size(array)).
: 1. 我当时是用(lower, upper)作为DP状态,以(D,E)作为起始值,然后检查(D-Amin, E
: -Amax), (D-Bmin, E-Bmax), (D-Cmin, E-Cmax) 并递归下去,如果达到某个(a, b)状
: 态其中a是非正数而b是非负数的话,就是有解,如果某个状态开始的所有分支达到的状
: 态都是a,b都是负数的话就记录该状态为失败。直接的dfs而不记录失败的状态好像会有
: 些搜索重复吧?

n**e
发帖数: 116
23
恭喜+膜拜
a********m
发帖数: 15480
24
0. 这方法不错。既然已经构造了set,从链表头开始扫描应该就可以了吧。这样单向双
向也无所谓,也不需要删除操作。
1. 恩。明白了。那么做的话确实算dp。复杂度是D/Amin*D/Bmin*D/Cmin?只是不知道是
不是比dfs好。因为dfs最后一个可以直接算,不需要递归,所以D/Amin*D/Bmin就可以了
。而且ABC可以改变顺序让Amin和Bmin大,少计算一些。

E

【在 t*****s 的大作中提到】
: 0. 我是从array构造了个set,然后每次从set里弹出一个节点指针后,在双向列表里从
: 该节点往两边检索并不断从set里删除元素。问了这个算法的复杂度,应该就是时间空
: 间都是O(size(array)).
: 1. 我当时是用(lower, upper)作为DP状态,以(D,E)作为起始值,然后检查(D-Amin, E
: -Amax), (D-Bmin, E-Bmax), (D-Cmin, E-Cmax) 并递归下去,如果达到某个(a, b)状
: 态其中a是非正数而b是非负数的话,就是有解,如果某个状态开始的所有分支达到的状
: 态都是a,b都是负数的话就记录该状态为失败。直接的dfs而不记录失败的状态好像会有
: 些搜索重复吧?

s*******n
发帖数: 305
25
牛人
s**********m
发帖数: 1263
26
恭喜 排包子

找工作算告一段落了,这一个多月从版上学到了很多,非常感谢大家,也分享点儿自己
的情况。本人cs fresh phd,投了F和G,准备主要是leetcode,做了50题左右,还有就
........

【在 t*****s 的大作中提到】
: 找工作算告一段落了,这一个多月从版上学到了很多,非常感谢大家,也分享点儿自己
: 的情况。本人cs fresh phd,投了F和G,准备主要是leetcode,做了50题左右,还有就
: 是板上的面经。强烈推荐leetcode,特别是对于准备时间有限的同学,基本覆盖了各式
: 各样的题。虽然最后面试没遇到做过的coding题,但基本都差不多。
: 0. 给定一个双向链表,以及一个数组。数组里存着一部分链表节点的指针。问数组里
: 的指针们指向的节点在双向列表中可以分成几个连续的blocks。接着问如果是单向链表
: 怎么做。算法复杂度分别是什么。
: 1. coke machines。大中小三个可乐机,每按一次出可乐量分别在[Amin,Amax], [Bmin
: , Bmax], [Cmin, Cmax]之间,但不能确定具体容量是多少,现在想通过按这三个可乐
: 机,达到容量为[D, E]之间的可乐,问能否做到。也就是能否找到非负整数x, y, z使

a********m
发帖数: 15480
27
a=D-k1Amin - k2Bmin - k3Cmin. 非正是 >=D

【在 l*******0 的大作中提到】
: 为啥我感觉,应该是a是非负,b是非正时说明存在呢?请您在解释一下?谢谢。
:
: E

a********m
发帖数: 15480
28
嗯。0 俺这个不对。复杂度是链表的长度了,不是array长度。

【在 a********m 的大作中提到】
: 0. 这方法不错。既然已经构造了set,从链表头开始扫描应该就可以了吧。这样单向双
: 向也无所谓,也不需要删除操作。
: 1. 恩。明白了。那么做的话确实算dp。复杂度是D/Amin*D/Bmin*D/Cmin?只是不知道是
: 不是比dfs好。因为dfs最后一个可以直接算,不需要递归,所以D/Amin*D/Bmin就可以了
: 。而且ABC可以改变顺序让Amin和Bmin大,少计算一些。
:
: E

A*********5
发帖数: 340
29
妈呀,人和人差别咋那么大。。。。。。
p**********g
发帖数: 378
30
好专业实在是太重要啦...

Bmin

【在 t*****s 的大作中提到】
: 找工作算告一段落了,这一个多月从版上学到了很多,非常感谢大家,也分享点儿自己
: 的情况。本人cs fresh phd,投了F和G,准备主要是leetcode,做了50题左右,还有就
: 是板上的面经。强烈推荐leetcode,特别是对于准备时间有限的同学,基本覆盖了各式
: 各样的题。虽然最后面试没遇到做过的coding题,但基本都差不多。
: 0. 给定一个双向链表,以及一个数组。数组里存着一部分链表节点的指针。问数组里
: 的指针们指向的节点在双向列表中可以分成几个连续的blocks。接着问如果是单向链表
: 怎么做。算法复杂度分别是什么。
: 1. coke machines。大中小三个可乐机,每按一次出可乐量分别在[Amin,Amax], [Bmin
: , Bmax], [Cmin, Cmax]之间,但不能确定具体容量是多少,现在想通过按这三个可乐
: 机,达到容量为[D, E]之间的可乐,问能否做到。也就是能否找到非负整数x, y, z使

相关主题
请问 大公司给 RSU 的问题Amazon offer + 面经 ... How to negotiate effectively?
求问谷歌待遇 (转载)报个fresh的offer,兼面经顺便求建议
问个简单算法题offer 选择, facebook VS google ?
进入JobHunting版参与讨论
t*****s
发帖数: 39
31

其实直接穷举x, y然后判断是否存在z的话,复杂度应该就是D/Amin*D/Bmin吧

【在 a********m 的大作中提到】
: 0. 这方法不错。既然已经构造了set,从链表头开始扫描应该就可以了吧。这样单向双
: 向也无所谓,也不需要删除操作。
: 1. 恩。明白了。那么做的话确实算dp。复杂度是D/Amin*D/Bmin*D/Cmin?只是不知道是
: 不是比dfs好。因为dfs最后一个可以直接算,不需要递归,所以D/Amin*D/Bmin就可以了
: 。而且ABC可以改变顺序让Amin和Bmin大,少计算一些。
:
: E

a********m
发帖数: 15480
32
是。

【在 t*****s 的大作中提到】
:
: 其实直接穷举x, y然后判断是否存在z的话,复杂度应该就是D/Amin*D/Bmin吧

e*****n
发帖数: 316
33
牛~ 同弱刷题中。。。
l*********s
发帖数: 55
34
好厉害,赞!!cong!

Bmin

【在 t*****s 的大作中提到】
: 找工作算告一段落了,这一个多月从版上学到了很多,非常感谢大家,也分享点儿自己
: 的情况。本人cs fresh phd,投了F和G,准备主要是leetcode,做了50题左右,还有就
: 是板上的面经。强烈推荐leetcode,特别是对于准备时间有限的同学,基本覆盖了各式
: 各样的题。虽然最后面试没遇到做过的coding题,但基本都差不多。
: 0. 给定一个双向链表,以及一个数组。数组里存着一部分链表节点的指针。问数组里
: 的指针们指向的节点在双向列表中可以分成几个连续的blocks。接着问如果是单向链表
: 怎么做。算法复杂度分别是什么。
: 1. coke machines。大中小三个可乐机,每按一次出可乐量分别在[Amin,Amax], [Bmin
: , Bmax], [Cmin, Cmax]之间,但不能确定具体容量是多少,现在想通过按这三个可乐
: 机,达到容量为[D, E]之间的可乐,问能否做到。也就是能否找到非负整数x, y, z使

l***2
发帖数: 486
35
大牛!
膜拜。
沾喜气好运气,上帝也给我这么个大offer吧!

Bmin

【在 t*****s 的大作中提到】
: 找工作算告一段落了,这一个多月从版上学到了很多,非常感谢大家,也分享点儿自己
: 的情况。本人cs fresh phd,投了F和G,准备主要是leetcode,做了50题左右,还有就
: 是板上的面经。强烈推荐leetcode,特别是对于准备时间有限的同学,基本覆盖了各式
: 各样的题。虽然最后面试没遇到做过的coding题,但基本都差不多。
: 0. 给定一个双向链表,以及一个数组。数组里存着一部分链表节点的指针。问数组里
: 的指针们指向的节点在双向列表中可以分成几个连续的blocks。接着问如果是单向链表
: 怎么做。算法复杂度分别是什么。
: 1. coke machines。大中小三个可乐机,每按一次出可乐量分别在[Amin,Amax], [Bmin
: , Bmax], [Cmin, Cmax]之间,但不能确定具体容量是多少,现在想通过按这三个可乐
: 机,达到容量为[D, E]之间的可乐,问能否做到。也就是能否找到非负整数x, y, z使

y*c
发帖数: 904
36
牛啊
l*****e
发帖数: 1374
37
"往两边检索并不断从set里删除元素",set本身的操作可以不考虑么?

E

【在 t*****s 的大作中提到】
: 0. 我是从array构造了个set,然后每次从set里弹出一个节点指针后,在双向列表里从
: 该节点往两边检索并不断从set里删除元素。问了这个算法的复杂度,应该就是时间空
: 间都是O(size(array)).
: 1. 我当时是用(lower, upper)作为DP状态,以(D,E)作为起始值,然后检查(D-Amin, E
: -Amax), (D-Bmin, E-Bmax), (D-Cmin, E-Cmax) 并递归下去,如果达到某个(a, b)状
: 态其中a是非正数而b是非负数的话,就是有解,如果某个状态开始的所有分支达到的状
: 态都是a,b都是负数的话就记录该状态为失败。直接的dfs而不记录失败的状态好像会有
: 些搜索重复吧?

J*******o
发帖数: 741
38
恭喜大牛, 沾沾喜气
s****p
发帖数: 124
39
请问如果是单向链表怎么做?

E

【在 t*****s 的大作中提到】
: 0. 我是从array构造了个set,然后每次从set里弹出一个节点指针后,在双向列表里从
: 该节点往两边检索并不断从set里删除元素。问了这个算法的复杂度,应该就是时间空
: 间都是O(size(array)).
: 1. 我当时是用(lower, upper)作为DP状态,以(D,E)作为起始值,然后检查(D-Amin, E
: -Amax), (D-Bmin, E-Bmax), (D-Cmin, E-Cmax) 并递归下去,如果达到某个(a, b)状
: 态其中a是非正数而b是非负数的话,就是有解,如果某个状态开始的所有分支达到的状
: 态都是a,b都是负数的话就记录该状态为失败。直接的dfs而不记录失败的状态好像会有
: 些搜索重复吧?

s****p
发帖数: 124
40
如果单向链表,你怎么知道哪个是连表头节点?而且如果不删除,你怎么知道哪个节点
属于哪个block?

【在 a********m 的大作中提到】
: 0. 这方法不错。既然已经构造了set,从链表头开始扫描应该就可以了吧。这样单向双
: 向也无所谓,也不需要删除操作。
: 1. 恩。明白了。那么做的话确实算dp。复杂度是D/Amin*D/Bmin*D/Cmin?只是不知道是
: 不是比dfs好。因为dfs最后一个可以直接算,不需要递归,所以D/Amin*D/Bmin就可以了
: 。而且ABC可以改变顺序让Amin和Bmin大,少计算一些。
:
: E

相关主题
offer 选择, facebook VS google ?报G的offer,咨询一下各位G大神关于offer细节
关于版上报的offer的一点疑问现在进facebook能发多少GSU呀?
找工作结束,报offer请教Google offer negotiation
进入JobHunting版参与讨论
s****p
发帖数: 124
41
请问coke machine这题,如果不用recursion,而用DP,能否简单给出代码?
非常感谢!

E

【在 t*****s 的大作中提到】
: 0. 我是从array构造了个set,然后每次从set里弹出一个节点指针后,在双向列表里从
: 该节点往两边检索并不断从set里删除元素。问了这个算法的复杂度,应该就是时间空
: 间都是O(size(array)).
: 1. 我当时是用(lower, upper)作为DP状态,以(D,E)作为起始值,然后检查(D-Amin, E
: -Amax), (D-Bmin, E-Bmax), (D-Cmin, E-Cmax) 并递归下去,如果达到某个(a, b)状
: 态其中a是非正数而b是非负数的话,就是有解,如果某个状态开始的所有分支达到的状
: 态都是a,b都是负数的话就记录该状态为失败。直接的dfs而不记录失败的状态好像会有
: 些搜索重复吧?

s****p
发帖数: 124
42
如果输入只是一个linked list node的array,而不给出头节点,autumnworms的解法就
不适用了。

【在 s****p 的大作中提到】
: 如果单向链表,你怎么知道哪个是连表头节点?而且如果不删除,你怎么知道哪个节点
: 属于哪个block?

a********m
发帖数: 15480
43
这样的话是需要删除。

【在 s****p 的大作中提到】
: 如果输入只是一个linked list node的array,而不给出头节点,autumnworms的解法就
: 不适用了。

b********e
发帖数: 43
44
0 题我怎么不太明白, 这样一个双向链表 (head:a, tail : i)
Array里面存的是{b, d, g}的话 那连续的block不就是 (b,d) (d,g) (g, b)么?
null <--- a ---> b ---> c---> d---> e---> f---> g ---> i ---> null
<--- <--- <--- <--- <--- <--- <---
s****p
发帖数: 124
45
请问第3题,balls and bins,是说有盒子出现一个球,两个球,到n个球,每种情况的
概率?请问怎么求这个?
这个完全还给老师了。

Bmin

【在 t*****s 的大作中提到】
: 找工作算告一段落了,这一个多月从版上学到了很多,非常感谢大家,也分享点儿自己
: 的情况。本人cs fresh phd,投了F和G,准备主要是leetcode,做了50题左右,还有就
: 是板上的面经。强烈推荐leetcode,特别是对于准备时间有限的同学,基本覆盖了各式
: 各样的题。虽然最后面试没遇到做过的coding题,但基本都差不多。
: 0. 给定一个双向链表,以及一个数组。数组里存着一部分链表节点的指针。问数组里
: 的指针们指向的节点在双向列表中可以分成几个连续的blocks。接着问如果是单向链表
: 怎么做。算法复杂度分别是什么。
: 1. coke machines。大中小三个可乐机,每按一次出可乐量分别在[Amin,Amax], [Bmin
: , Bmax], [Cmin, Cmax]之间,但不能确定具体容量是多少,现在想通过按这三个可乐
: 机,达到容量为[D, E]之间的可乐,问能否做到。也就是能否找到非负整数x, y, z使

t******i
发帖数: 483
46
mark
y*c
发帖数: 904
47
If the list is singly linked, we need to use a hashmap to
keep the blocks number. When we scan to the right, we may meet one with a
block number already, then all nodes scanned so far (in both array and
linked list) is added to that block. Otherwise, form a new block.
y*c
发帖数: 904
48

这题挺有意思。搞清题意后就是两个for loop. 但是理解题意搞了很久,然后dfs搞了
很久。

【在 t*****s 的大作中提到】
:
: 其实直接穷举x, y然后判断是否存在z的话,复杂度应该就是D/Amin*D/Bmin吧

y*c
发帖数: 904
49

binomial distribution

【在 s****p 的大作中提到】
: 请问第3题,balls and bins,是说有盒子出现一个球,两个球,到n个球,每种情况的
: 概率?请问怎么求这个?
: 这个完全还给老师了。
:
: Bmin

1 (共1页)
进入JobHunting版参与讨论
相关主题
说说最近几个offer关于版上报的offer的一点疑问
报一个google的offer吧找工作结束,报offer
请问 大公司给 RSU 的问题报G的offer,咨询一下各位G大神关于offer细节
求问谷歌待遇 (转载)现在进facebook能发多少GSU呀?
问个简单算法题请教Google offer negotiation
Amazon offer + 面经 ... How to negotiate effectively?Google offer接受了后发现股票给的比别人少,怎么办?
报个fresh的offer,兼面经顺便求建议stock option in an offer
offer 选择, facebook VS google ?Facebook还是Google?
相关话题的讨论汇总
话题: bmin话题: amin话题: 链表话题: cmin话题: cmax