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 | | f*******b 发帖数: 520 | | 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 | | a********m 发帖数: 15480 | 10 cong! + 赞!
0. 要求复杂度和空间不?
1. dp咋弄?感觉还是dfs呀。不依赖DE是比较神奇。 | | | 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 | | 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 | | 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. | | | c********p 发帖数: 1969 | | 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 | | 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 | | 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 | | 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使
| | | 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 | | 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 | | 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 | | 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
| | | 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 | | 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
|
|