logo
Redian新闻
>未名空间
>JobHunting - 待字闺中
>
Amazon面试题
avatar
Amazon面试题# JobHunting - 待字闺中
n*r
1 楼
上周面的，已杯具。有些题不记得了，说点记得的。
第一个是Sr manager，问了工作经历，然后让设计Facebook的news feed，回答用long
polling来达到实时性。被问到这样的话连接太多，回答说用pub/sub来接收消息，再用
long polling来把消息传给web。面得一般，不好也不是太坏。
第二个是Sr SDE。有一组records，每个record由三个参数组成，开始时间，结束时间
，权重。找到一个set，这个set包含的records在时间上没有重叠，并且set的权重之和
最大。一下子想不到好解法，被一直催着写代码，结果连最简单的都写错。还和面试官
争论。面试结束时想到把这个问题变化成图来解决，每个record是图中的节点，如果两
个records没有时间上的重叠，就有一条边，最后找到所有的clique，计算权重之和，
返回权重之和最大的。面试官听了，没什么表情，问了问时间复杂度，说这样大概可行
。这个是面的最差的，我觉得他大概都想把我给直接赶出去。
第三个是SDE，从多个数中找到最大的k个。开始用的是max heap，被指出后，改正为
min heap。还问了些别的，都不难。
第四个是Sr SDE。问如何scale up一个系统，有web前端，数据库，后端模块通过消息
通信。给出一些扩展的方法，看起来他比较满意，相互讨论多过问问题。然后让设计一
个系统，通过电话号码找到人，用了B+ tree，让解释B+ tree的创建和优化。
第五个是Sr SDE，给一个数组，一个数X，找到数组中每一对加起来等于X的数。先给出
经典答案，用hash，时间复杂度O(n)。追问如果不允许用额外的内存，讲了两个解法，
一个是扫描数组，如果这个数小于X的一半，用X减去这个数的差来代替这个数，然后排
序，再扫描数组，找到临近值相等的数。另一个是排序，扫描数组，对每一个数Y，折
半查找X-Y。然后让白板写程序，还不错，一次写对，没有bug。还问了别的题，都不难
。
avatar
s*s
2 楼
多谢.能不能详细说一下“给出一些扩展的方法”？
>第三个是SDE，从多个数中找到最大的k个。开始用的是max heap，被指出后，改
>正为min heap。还问了些别的，都不难。
programming perl上好像用quicksort的变形。比min heap快。
avatar
l*a
3 楼
号码找人有什么需求？一般来说用trie吧

long

【在 n*********r 的大作中提到】
: 上周面的，已杯具。有些题不记得了，说点记得的。
: 第一个是Sr manager，问了工作经历，然后让设计Facebook的news feed，回答用long
: polling来达到实时性。被问到这样的话连接太多，回答说用pub/sub来接收消息，再用
: long polling来把消息传给web。面得一般，不好也不是太坏。
: 第二个是Sr SDE。有一组records，每个record由三个参数组成，开始时间，结束时间
: ，权重。找到一个set，这个set包含的records在时间上没有重叠，并且set的权重之和
: 最大。一下子想不到好解法，被一直催着写代码，结果连最简单的都写错。还和面试官
: 争论。面试结束时想到把这个问题变化成图来解决，每个record是图中的节点，如果两
: 个records没有时间上的重叠，就有一条边，最后找到所有的clique，计算权重之和，
: 返回权重之和最大的。面试官听了，没什么表情，问了问时间复杂度，说这样大概可行
avatar
t*n
4 楼
第二题不是经典dp吗？ LZ的图算法看不太懂啊。
avatar
p*4
5 楼
怎么最近amazon的onsite一个比一个难！！
avatar
l*i
6 楼
第二题，有点像背包问题的变型。
第三题，也可以用quickselect。
avatar
r*h
7 楼
感觉题目不简单呀

long

【在 n*********r 的大作中提到】
: 上周面的，已杯具。有些题不记得了，说点记得的。
: 第一个是Sr manager，问了工作经历，然后让设计Facebook的news feed，回答用long
: polling来达到实时性。被问到这样的话连接太多，回答说用pub/sub来接收消息，再用
: long polling来把消息传给web。面得一般，不好也不是太坏。
: 第二个是Sr SDE。有一组records，每个record由三个参数组成，开始时间，结束时间
: ，权重。找到一个set，这个set包含的records在时间上没有重叠，并且set的权重之和
: 最大。一下子想不到好解法，被一直催着写代码，结果连最简单的都写错。还和面试官
: 争论。面试结束时想到把这个问题变化成图来解决，每个record是图中的节点，如果两
: 个records没有时间上的重叠，就有一条边，最后找到所有的clique，计算权重之和，
: 返回权重之和最大的。面试官听了，没什么表情，问了问时间复杂度，说这样大概可行
avatar
l*a
8 楼
1) sort by endTime
2) f(n)= f(n-1)+list.get(n).value
//if list.get(n-1).endTimemax(f(n-1),f(k)+list.get(n).value)
//if list.get(k).endTimebtw,权值可以为负数吗？

【在 l****i 的大作中提到】
: 第二题，有点像背包问题的变型。
: 第三题，也可以用quickselect。
avatar
x*0
9 楼
mark
avatar
t*h
10 楼
这个是set covering problem, NP Complete.
难道是我对题的理解有误？

【在 t*********n 的大作中提到】
: 第二题不是经典dp吗？ LZ的图算法看不太懂啊。
avatar
a*0
11 楼
谁说dp解就不能使np-complete呢

【在 t*****h 的大作中提到】
: 这个是set covering problem, NP Complete.
: 难道是我对题的理解有误？
avatar
a*0
12 楼
第三个为什么是min heap？难道我脑抽了？
avatar
l*a
13 楼
min heap means each time you can poll the minimum of the heap out
then u will keep the max K

【在 a*********0 的大作中提到】
: 第三个为什么是min heap？难道我脑抽了？
avatar
a*0
14 楼
那不是要poll n-k次？如果只是选k，复杂度是klgn， 现在成了nlgn了。不是这种逻辑吧

【在 l*****a 的大作中提到】
: min heap means each time you can poll the minimum of the heap out
: then u will keep the max K
avatar
t*h
15 楼
Optimization is NP Hard, right?

【在 a*********0 的大作中提到】
: 谁说dp解就不能使np-complete呢
avatar
n*w
16 楼
不是。DP解是n * lgn
1. sort array by ending time （n*lgn time ）
2. 递归式
DP[i] = max { A[i].cost, DP[i-1], max { DP[k]+A[i].cost} }
kmax{k} where end time of A[k] <= start time of A[i]
n个subproblem，找k的时候可以binary search，lgn time
最后还是 n*lgn time
处理i的是时候有三种情况
1. 不使用A[i]
2. 使用A[i]，所以任意与A[i]有overlap的都要舍去，所以要找k
3. k找不到，因为A[i]的start time比第一个record的ending time都要小

【在 t*****h 的大作中提到】
: 这个是set covering problem, NP Complete.
: 难道是我对题的理解有误？
avatar
l*a
17 楼
it is nlgk, isn't it?

辑吧

【在 a*********0 的大作中提到】
: 那不是要poll n-k次？如果只是选k，复杂度是klgn， 现在成了nlgn了。不是这种逻辑吧
avatar
t*h
18 楼
HEAP的size是K。

辑吧

【在 a*********0 的大作中提到】
: 那不是要poll n-k次？如果只是选k，复杂度是klgn， 现在成了nlgn了。不是这种逻辑吧
avatar
a*0
19 楼
opt问题多了，怎么会全是np解

【在 t*****h 的大作中提到】
: Optimization is NP Hard, right?
avatar
a*0
20 楼
n+klgn or k+nlgk, which one is better?

【在 t*****h 的大作中提到】
: HEAP的size是K。
:
: 辑吧
avatar
l*a
21 楼

i]
怎么会有这么多子问题？
dp[k]不是递增的吗？

【在 n*******w 的大作中提到】
: 不是。DP解是n * lgn
: 1. sort array by ending time （n*lgn time ）
: 2. 递归式
: DP[i] = max { A[i].cost, DP[i-1], max { DP[k]+A[i].cost} }
: k: max{k} where end time of A[k] <= start time of A[i]
: n个subproblem，找k的时候可以binary search，lgn time
: 最后还是 n*lgn time
: 处理i的是时候有三种情况
: 1. 不使用A[i]
avatar
n*w
22 楼
是的。你看DP[i]那个大括号里边包含了D[i-1]
max虽然写了很多，但是只有n个子问题。仔细看。

【在 l*****a 的大作中提到】
:
: i]
: 怎么会有这么多子问题？
: dp[k]不是递增的吗？
avatar
l*a
23 楼
我仔细看了
我认为dp[k]是递增的 ，下面的max是不需要的
max { DP[k]+A[i].cost} }
当然找max(k)是需要的

【在 n*******w 的大作中提到】
: 是的。你看DP[i]那个大括号里边包含了D[i-1]
: max虽然写了很多，但是只有n个子问题。仔细看。
avatar
n*w
24 楼
哦，是的。我写的时候不知道怎么表达。

【在 l*****a 的大作中提到】
: 我仔细看了
: 我认为dp[k]是递增的 ，下面的max是不需要的
: max { DP[k]+A[i].cost} }
: 当然找max(k)是需要的
avatar
n*r
25 楼
看来我没有把题说清楚。
min heap那道题的前提是这组数非常多，没法全读入内存。我当时能想到的就是heap了。
set的那道题是这样的。比如这组records是r1=<10,50,20>,r2=<35,80,100>,r3=<55,
100,50>。r1的开始时间是10，结束时间是50，权重是20，以此类推r2和r3。那么，在
这种情况下，保证成员record在时间上不交叉而且权重和最大的set是{r2}。把这个问
题抽象成图的方法是参考http://mathoverflow.net/questions/98651/how-to-get-the-largest-subset-of-a-set-of-sets-of-intervals-with-no-overlapping-i。
avatar
s*i
26 楼
Mark

long

【在 n*********r 的大作中提到】
: 上周面的，已杯具。有些题不记得了，说点记得的。
: 第一个是Sr manager，问了工作经历，然后让设计Facebook的news feed，回答用long
: polling来达到实时性。被问到这样的话连接太多，回答说用pub/sub来接收消息，再用
: long polling来把消息传给web。面得一般，不好也不是太坏。
: 第二个是Sr SDE。有一组records，每个record由三个参数组成，开始时间，结束时间
: ，权重。找到一个set，这个set包含的records在时间上没有重叠，并且set的权重之和
: 最大。一下子想不到好解法，被一直催着写代码，结果连最简单的都写错。还和面试官
: 争论。面试结束时想到把这个问题变化成图来解决，每个record是图中的节点，如果两
: 个records没有时间上的重叠，就有一条边，最后找到所有的clique，计算权重之和，
: 返回权重之和最大的。面试官听了，没什么表情，问了问时间复杂度，说这样大概可行
avatar
s*i
27 楼
Mark
avatar
s*i
28 楼
Mark

long

【在 n*********r 的大作中提到】
: 上周面的，已杯具。有些题不记得了，说点记得的。
: 第一个是Sr manager，问了工作经历，然后让设计Facebook的news feed，回答用long
: polling来达到实时性。被问到这样的话连接太多，回答说用pub/sub来接收消息，再用
: long polling来把消息传给web。面得一般，不好也不是太坏。
: 第二个是Sr SDE。有一组records，每个record由三个参数组成，开始时间，结束时间
: ，权重。找到一个set，这个set包含的records在时间上没有重叠，并且set的权重之和
: 最大。一下子想不到好解法，被一直催着写代码，结果连最简单的都写错。还和面试官
: 争论。面试结束时想到把这个问题变化成图来解决，每个record是图中的节点，如果两
: 个records没有时间上的重叠，就有一条边，最后找到所有的clique，计算权重之和，
: 返回权重之和最大的。面试官听了，没什么表情，问了问时间复杂度，说这样大概可行
avatar
d*m
29 楼
第二题不是教科书上的经典knapsack problem吗。。。DP入门题。。
avatar
n*r
30 楼
有人提到用Knapsack DP的方法解。可是，在面试的时候，我说想用DP的方法来考虑这
个问题的时候，直接就被打断，说dynamic programming不正确。
avatar
f*4
31 楼

long
第二题，它那个record，开始时间，结束时间好像就是一段数，比如1-5
一个vector, 每个struct除了有开始结束时间还有权重
假设第二个record是2-4,就像insert internal 一样，发现conflict，比较权重，去掉
小的那个
[发表自未名空间手机版 - m.mitbbs.com]

【在 n*********r 的大作中提到】
: 上周面的，已杯具。有些题不记得了，说点记得的。
: 第一个是Sr manager，问了工作经历，然后让设计Facebook的news feed，回答用long
: polling来达到实时性。被问到这样的话连接太多，回答说用pub/sub来接收消息，再用
: long polling来把消息传给web。面得一般，不好也不是太坏。
: 第二个是Sr SDE。有一组records，每个record由三个参数组成，开始时间，结束时间
: ，权重。找到一个set，这个set包含的records在时间上没有重叠，并且set的权重之和
: 最大。一下子想不到好解法，被一直催着写代码，结果连最简单的都写错。还和面试官
: 争论。面试结束时想到把这个问题变化成图来解决，每个record是图中的节点，如果两
: 个records没有时间上的重叠，就有一条边，最后找到所有的clique，计算权重之和，
: 返回权重之和最大的。面试官听了，没什么表情，问了问时间复杂度，说这样大概可行
avatar
J*a
32 楼
这不是背包 不懂装懂 说入门说明你还没入门呢
背包问题复杂度是伪多项式，是NP的 这个题就是多项式复杂度
这是带权重的scheduling problem，康奈尔的算法教材上的例题原题

【在 d****m 的大作中提到】
: 第二题不是教科书上的经典knapsack problem吗。。。DP入门题。。
avatar
J*a
33 楼
此题可以用DP 只不过DP前要对任务排下序
有的面试官水平不怎的

【在 n*********r 的大作中提到】
: 有人提到用Knapsack DP的方法解。可是，在面试的时候，我说想用DP的方法来考虑这
: 个问题的时候，直接就被打断，说dynamic programming不正确。
avatar
d*x
34 楼
algorithm design这本书如果习题都给出答案就好了。。。

【在 J*****a 的大作中提到】
: 这不是背包 不懂装懂 说入门说明你还没入门呢
: 背包问题复杂度是伪多项式，是NP的 这个题就是多项式复杂度
: 这是带权重的scheduling problem，康奈尔的算法教材上的例题原题
avatar
P*r
35 楼
第二题能用longest increasing subsequence解吗。先用ending time排序。再keep一
个array
A[i] 就是ending到i的weight sum最大的interval sequence的sum
avatar
d*m
36 楼
我也没明白你的喷点在哪里。也没明白你是喷不是DP还是不是knapsack。
这题是algorithm design 第六章DP的第一个例题，你自己去看。我说是DP入门题不对
？题目我也没仔细看，好像比knapsack还简单些。
也是非常的逗：）

【在 J*****a 的大作中提到】
: 这不是背包 不懂装懂 说入门说明你还没入门呢
: 背包问题复杂度是伪多项式，是NP的 这个题就是多项式复杂度
: 这是带权重的scheduling problem，康奈尔的算法教材上的例题原题
avatar
n*w
37 楼
+1
面试官也都是跟我们一样的平常人。本来就是从工作的同事中间选出来的。也有不懂的
东西。那题是典型的DP。
有人pm问DP[k]可能并不以A[k]的值结尾。
不同的题DP[k]的意思不尽相同。
LIS那题，DP[k]表示以A[k]结尾的LIS
这一题，DP[k]表示排序后前k个task的最大值，所以并不一定包含A[k]
如果想对DP有很深刻的理解，个人觉得CLRS那本书里边好像详细讲解了如何证明DP。
greedy algorithm也讲到了。会证明了，应该就会写几乎任何DP递归式了。

【在 J*****a 的大作中提到】
: 此题可以用DP 只不过DP前要对任务排下序
: 有的面试官水平不怎的
avatar
x*0
38 楼
mark
avatar
n*r
39 楼
上周面的，已杯具。有些题不记得了，说点记得的。
第一个是Sr manager，问了工作经历，然后让设计Facebook的news feed，回答用long
polling来达到实时性。被问到这样的话连接太多，回答说用pub/sub来接收消息，再用
long polling来把消息传给web。面得一般，不好也不是太坏。
第二个是Sr SDE。有一组records，每个record由三个参数组成，开始时间，结束时间
，权重。找到一个set，这个set包含的records在时间上没有重叠，并且set的权重之和
最大。一下子想不到好解法，被一直催着写代码，结果连最简单的都写错。还和面试官
争论。面试结束时想到把这个问题变化成图来解决，每个record是图中的节点，如果两
个records没有时间上的重叠，就有一条边，最后找到所有的clique，计算权重之和，
返回权重之和最大的。面试官听了，没什么表情，问了问时间复杂度，说这样大概可行
。这个是面的最差的，我觉得他大概都想把我给直接赶出去。
第三个是SDE，从多个数中找到最大的k个。开始用的是max heap，被指出后，改正为
min heap。还问了些别的，都不难。
第四个是Sr SDE。问如何scale up一个系统，有web前端，数据库，后端模块通过消息
通信。给出一些扩展的方法，看起来他比较满意，相互讨论多过问问题。然后让设计一
个系统，通过电话号码找到人，用了B+ tree，让解释B+ tree的创建和优化。
第五个是Sr SDE，给一个数组，一个数X，找到数组中每一对加起来等于X的数。先给出
经典答案，用hash，时间复杂度O(n)。追问如果不允许用额外的内存，讲了两个解法，
一个是扫描数组，如果这个数小于X的一半，用X减去这个数的差来代替这个数，然后排
序，再扫描数组，找到临近值相等的数。另一个是排序，扫描数组，对每一个数Y，折
半查找X-Y。然后让白板写程序，还不错，一次写对，没有bug。还问了别的题，都不难
。
avatar
s*s
40 楼
多谢.能不能详细说一下“给出一些扩展的方法”？
>第三个是SDE，从多个数中找到最大的k个。开始用的是max heap，被指出后，改
>正为min heap。还问了些别的，都不难。
programming perl上好像用quicksort的变形。比min heap快。
avatar
l*a
41 楼
号码找人有什么需求？一般来说用trie吧

long

【在 n*********r 的大作中提到】
: 上周面的，已杯具。有些题不记得了，说点记得的。
: 第一个是Sr manager，问了工作经历，然后让设计Facebook的news feed，回答用long
: polling来达到实时性。被问到这样的话连接太多，回答说用pub/sub来接收消息，再用
: long polling来把消息传给web。面得一般，不好也不是太坏。
: 第二个是Sr SDE。有一组records，每个record由三个参数组成，开始时间，结束时间
: ，权重。找到一个set，这个set包含的records在时间上没有重叠，并且set的权重之和
: 最大。一下子想不到好解法，被一直催着写代码，结果连最简单的都写错。还和面试官
: 争论。面试结束时想到把这个问题变化成图来解决，每个record是图中的节点，如果两
: 个records没有时间上的重叠，就有一条边，最后找到所有的clique，计算权重之和，
: 返回权重之和最大的。面试官听了，没什么表情，问了问时间复杂度，说这样大概可行
avatar
t*n
42 楼
第二题不是经典dp吗？ LZ的图算法看不太懂啊。
avatar
p*4
43 楼
怎么最近amazon的onsite一个比一个难！！
avatar
l*i
44 楼
第二题，有点像背包问题的变型。
第三题，也可以用quickselect。
avatar
r*h
45 楼
感觉题目不简单呀

long

【在 n*********r 的大作中提到】
: 上周面的，已杯具。有些题不记得了，说点记得的。
: 第一个是Sr manager，问了工作经历，然后让设计Facebook的news feed，回答用long
: polling来达到实时性。被问到这样的话连接太多，回答说用pub/sub来接收消息，再用
: long polling来把消息传给web。面得一般，不好也不是太坏。
: 第二个是Sr SDE。有一组records，每个record由三个参数组成，开始时间，结束时间
: ，权重。找到一个set，这个set包含的records在时间上没有重叠，并且set的权重之和
: 最大。一下子想不到好解法，被一直催着写代码，结果连最简单的都写错。还和面试官
: 争论。面试结束时想到把这个问题变化成图来解决，每个record是图中的节点，如果两
: 个records没有时间上的重叠，就有一条边，最后找到所有的clique，计算权重之和，
: 返回权重之和最大的。面试官听了，没什么表情，问了问时间复杂度，说这样大概可行
avatar
l*a
46 楼
1) sort by endTime
2) f(n)= f(n-1)+list.get(n).value
//if list.get(n-1).endTimemax(f(n-1),f(k)+list.get(n).value)
//if list.get(k).endTimebtw,权值可以为负数吗？

【在 l****i 的大作中提到】
: 第二题，有点像背包问题的变型。
: 第三题，也可以用quickselect。
avatar
x*0
47 楼
mark
avatar
t*h
48 楼
这个是set covering problem, NP Complete.
难道是我对题的理解有误？

【在 t*********n 的大作中提到】
: 第二题不是经典dp吗？ LZ的图算法看不太懂啊。
avatar
a*0
49 楼
谁说dp解就不能使np-complete呢

【在 t*****h 的大作中提到】
: 这个是set covering problem, NP Complete.
: 难道是我对题的理解有误？
avatar
a*0
50 楼
第三个为什么是min heap？难道我脑抽了？
avatar
l*a
51 楼
min heap means each time you can poll the minimum of the heap out
then u will keep the max K

【在 a*********0 的大作中提到】
: 第三个为什么是min heap？难道我脑抽了？
avatar
a*0
52 楼
那不是要poll n-k次？如果只是选k，复杂度是klgn， 现在成了nlgn了。不是这种逻辑吧

【在 l*****a 的大作中提到】
: min heap means each time you can poll the minimum of the heap out
: then u will keep the max K
avatar
t*h
53 楼
Optimization is NP Hard, right?

【在 a*********0 的大作中提到】
: 谁说dp解就不能使np-complete呢
avatar
n*w
54 楼
不是。DP解是n * lgn
1. sort array by ending time （n*lgn time ）
2. 递归式
DP[i] = max { A[i].cost, DP[i-1], max { DP[k]+A[i].cost} }
kmax{k} where end time of A[k] <= start time of A[i]
n个subproblem，找k的时候可以binary search，lgn time
最后还是 n*lgn time
处理i的是时候有三种情况
1. 不使用A[i]
2. 使用A[i]，所以任意与A[i]有overlap的都要舍去，所以要找k
3. k找不到，因为A[i]的start time比第一个record的ending time都要小

【在 t*****h 的大作中提到】
: 这个是set covering problem, NP Complete.
: 难道是我对题的理解有误？
avatar
l*a
55 楼
it is nlgk, isn't it?

辑吧

【在 a*********0 的大作中提到】
: 那不是要poll n-k次？如果只是选k，复杂度是klgn， 现在成了nlgn了。不是这种逻辑吧
avatar
t*h
56 楼
HEAP的size是K。

辑吧

【在 a*********0 的大作中提到】
: 那不是要poll n-k次？如果只是选k，复杂度是klgn， 现在成了nlgn了。不是这种逻辑吧
avatar
a*0
57 楼
opt问题多了，怎么会全是np解

【在 t*****h 的大作中提到】
: Optimization is NP Hard, right?
avatar
a*0
58 楼
n+klgn or k+nlgk, which one is better?

【在 t*****h 的大作中提到】
: HEAP的size是K。
:
: 辑吧
avatar
l*a
59 楼

i]
怎么会有这么多子问题？
dp[k]不是递增的吗？

【在 n*******w 的大作中提到】
: 不是。DP解是n * lgn
: 1. sort array by ending time （n*lgn time ）
: 2. 递归式
: DP[i] = max { A[i].cost, DP[i-1], max { DP[k]+A[i].cost} }
: k: max{k} where end time of A[k] <= start time of A[i]
: n个subproblem，找k的时候可以binary search，lgn time
: 最后还是 n*lgn time
: 处理i的是时候有三种情况
: 1. 不使用A[i]
avatar
n*w
60 楼
是的。你看DP[i]那个大括号里边包含了D[i-1]
max虽然写了很多，但是只有n个子问题。仔细看。

【在 l*****a 的大作中提到】
:
: i]
: 怎么会有这么多子问题？
: dp[k]不是递增的吗？
avatar
l*a
61 楼
我仔细看了
我认为dp[k]是递增的 ，下面的max是不需要的
max { DP[k]+A[i].cost} }
当然找max(k)是需要的

【在 n*******w 的大作中提到】
: 是的。你看DP[i]那个大括号里边包含了D[i-1]
: max虽然写了很多，但是只有n个子问题。仔细看。
avatar
n*w
62 楼
哦，是的。我写的时候不知道怎么表达。

【在 l*****a 的大作中提到】
: 我仔细看了
: 我认为dp[k]是递增的 ，下面的max是不需要的
: max { DP[k]+A[i].cost} }
: 当然找max(k)是需要的
avatar
n*r
63 楼
看来我没有把题说清楚。
min heap那道题的前提是这组数非常多，没法全读入内存。我当时能想到的就是heap了。
set的那道题是这样的。比如这组records是r1=<10,50,20>,r2=<35,80,100>,r3=<55,
100,50>。r1的开始时间是10，结束时间是50，权重是20，以此类推r2和r3。那么，在
这种情况下，保证成员record在时间上不交叉而且权重和最大的set是{r2}。把这个问
题抽象成图的方法是参考http://mathoverflow.net/questions/98651/how-to-get-the-largest-subset-of-a-set-of-sets-of-intervals-with-no-overlapping-i。
avatar
s*i
64 楼
Mark

long

【在 n*********r 的大作中提到】
: 上周面的，已杯具。有些题不记得了，说点记得的。
: 第一个是Sr manager，问了工作经历，然后让设计Facebook的news feed，回答用long
: polling来达到实时性。被问到这样的话连接太多，回答说用pub/sub来接收消息，再用
: long polling来把消息传给web。面得一般，不好也不是太坏。
: 第二个是Sr SDE。有一组records，每个record由三个参数组成，开始时间，结束时间
: ，权重。找到一个set，这个set包含的records在时间上没有重叠，并且set的权重之和
: 最大。一下子想不到好解法，被一直催着写代码，结果连最简单的都写错。还和面试官
: 争论。面试结束时想到把这个问题变化成图来解决，每个record是图中的节点，如果两
: 个records没有时间上的重叠，就有一条边，最后找到所有的clique，计算权重之和，
: 返回权重之和最大的。面试官听了，没什么表情，问了问时间复杂度，说这样大概可行
avatar
s*i
65 楼
Mark
avatar
s*i
66 楼
Mark

long

【在 n*********r 的大作中提到】
: 上周面的，已杯具。有些题不记得了，说点记得的。
: 第一个是Sr manager，问了工作经历，然后让设计Facebook的news feed，回答用long
: polling来达到实时性。被问到这样的话连接太多，回答说用pub/sub来接收消息，再用
: long polling来把消息传给web。面得一般，不好也不是太坏。
: 第二个是Sr SDE。有一组records，每个record由三个参数组成，开始时间，结束时间
: ，权重。找到一个set，这个set包含的records在时间上没有重叠，并且set的权重之和
: 最大。一下子想不到好解法，被一直催着写代码，结果连最简单的都写错。还和面试官
: 争论。面试结束时想到把这个问题变化成图来解决，每个record是图中的节点，如果两
: 个records没有时间上的重叠，就有一条边，最后找到所有的clique，计算权重之和，
: 返回权重之和最大的。面试官听了，没什么表情，问了问时间复杂度，说这样大概可行
avatar
d*m
67 楼
第二题不是教科书上的经典knapsack problem吗。。。DP入门题。。
avatar
n*r
68 楼
有人提到用Knapsack DP的方法解。可是，在面试的时候，我说想用DP的方法来考虑这
个问题的时候，直接就被打断，说dynamic programming不正确。
avatar
f*4
69 楼

long
第二题，它那个record，开始时间，结束时间好像就是一段数，比如1-5
一个vector, 每个struct除了有开始结束时间还有权重
假设第二个record是2-4,就像insert internal 一样，发现conflict，比较权重，去掉
小的那个
[发表自未名空间手机版 - m.mitbbs.com]

【在 n*********r 的大作中提到】
: 上周面的，已杯具。有些题不记得了，说点记得的。
: 第一个是Sr manager，问了工作经历，然后让设计Facebook的news feed，回答用long
: polling来达到实时性。被问到这样的话连接太多，回答说用pub/sub来接收消息，再用
: long polling来把消息传给web。面得一般，不好也不是太坏。
: 第二个是Sr SDE。有一组records，每个record由三个参数组成，开始时间，结束时间
: ，权重。找到一个set，这个set包含的records在时间上没有重叠，并且set的权重之和
: 最大。一下子想不到好解法，被一直催着写代码，结果连最简单的都写错。还和面试官
: 争论。面试结束时想到把这个问题变化成图来解决，每个record是图中的节点，如果两
: 个records没有时间上的重叠，就有一条边，最后找到所有的clique，计算权重之和，
: 返回权重之和最大的。面试官听了，没什么表情，问了问时间复杂度，说这样大概可行
avatar
J*a
70 楼
这不是背包 不懂装懂 说入门说明你还没入门呢
背包问题复杂度是伪多项式，是NP的 这个题就是多项式复杂度
这是带权重的scheduling problem，康奈尔的算法教材上的例题原题

【在 d****m 的大作中提到】
: 第二题不是教科书上的经典knapsack problem吗。。。DP入门题。。
avatar
J*a
71 楼
此题可以用DP 只不过DP前要对任务排下序
有的面试官水平不怎的

【在 n*********r 的大作中提到】
: 有人提到用Knapsack DP的方法解。可是，在面试的时候，我说想用DP的方法来考虑这
: 个问题的时候，直接就被打断，说dynamic programming不正确。
avatar
d*x
72 楼
algorithm design这本书如果习题都给出答案就好了。。。

【在 J*****a 的大作中提到】
: 这不是背包 不懂装懂 说入门说明你还没入门呢
: 背包问题复杂度是伪多项式，是NP的 这个题就是多项式复杂度
: 这是带权重的scheduling problem，康奈尔的算法教材上的例题原题
avatar
P*r
73 楼
第二题能用longest increasing subsequence解吗。先用ending time排序。再keep一
个array
A[i] 就是ending到i的weight sum最大的interval sequence的sum
avatar
d*m
74 楼
我也没明白你的喷点在哪里。也没明白你是喷不是DP还是不是knapsack。
这题是algorithm design 第六章DP的第一个例题，你自己去看。我说是DP入门题不对
？题目我也没仔细看，好像比knapsack还简单些。
也是非常的逗：）

【在 J*****a 的大作中提到】
: 这不是背包 不懂装懂 说入门说明你还没入门呢
: 背包问题复杂度是伪多项式，是NP的 这个题就是多项式复杂度
: 这是带权重的scheduling problem，康奈尔的算法教材上的例题原题
avatar
n*w
75 楼
+1
面试官也都是跟我们一样的平常人。本来就是从工作的同事中间选出来的。也有不懂的
东西。那题是典型的DP。
有人pm问DP[k]可能并不以A[k]的值结尾。
不同的题DP[k]的意思不尽相同。
LIS那题，DP[k]表示以A[k]结尾的LIS
这一题，DP[k]表示排序后前k个task的最大值，所以并不一定包含A[k]
如果想对DP有很深刻的理解，个人觉得CLRS那本书里边好像详细讲解了如何证明DP。
greedy algorithm也讲到了。会证明了，应该就会写几乎任何DP递归式了。

【在 J*****a 的大作中提到】
: 此题可以用DP 只不过DP前要对任务排下序
: 有的面试官水平不怎的
avatar
x*0
76 楼
mark
avatar
s*n
77 楼
mark
avatar
c*p
78 楼
mark
avatar
s*n
79 楼
mark
avatar
g*e
80 楼
是nlogk

辑吧

【在 a*********0 的大作中提到】
: 那不是要poll n-k次？如果只是选k，复杂度是klgn， 现在成了nlgn了。不是这种逻辑吧
avatar
g*e
81 楼
我的那本书不知被谁借去了一直没还 郁闷

【在 J*****a 的大作中提到】
: 这不是背包 不懂装懂 说入门说明你还没入门呢
: 背包问题复杂度是伪多项式，是NP的 这个题就是多项式复杂度
: 这是带权重的scheduling problem，康奈尔的算法教材上的例题原题
avatar
C*y
82 楼
同问第四题scale up system.
想知道比较好的答案是什么样的

long

【在 n*********r 的大作中提到】
: 上周面的，已杯具。有些题不记得了，说点记得的。
: 第一个是Sr manager，问了工作经历，然后让设计Facebook的news feed，回答用long
: polling来达到实时性。被问到这样的话连接太多，回答说用pub/sub来接收消息，再用
: long polling来把消息传给web。面得一般，不好也不是太坏。
: 第二个是Sr SDE。有一组records，每个record由三个参数组成，开始时间，结束时间
: ，权重。找到一个set，这个set包含的records在时间上没有重叠，并且set的权重之和
: 最大。一下子想不到好解法，被一直催着写代码，结果连最简单的都写错。还和面试官
: 争论。面试结束时想到把这个问题变化成图来解决，每个record是图中的节点，如果两
: 个records没有时间上的重叠，就有一条边，最后找到所有的clique，计算权重之和，
: 返回权重之和最大的。面试官听了，没什么表情，问了问时间复杂度，说这样大概可行
avatar
l*d
84 楼
第五题能先排序，然后从两头往中间找吗？
相关阅读
Twitter's SDE openningsJ2到美国一般多久找到工作？twitter不是e-verify？opt莫名其妙被拒 同一份申请给了两个WAC号 不知道有没有这种情况问个opt问题,进来的都能找到工作!@贴个朋友的amazon面经Software Engineers Are In Demand, And GitHub Is How You Fifresh grad 去不是e-verify的公司是不是不靠谱？求Zynga refergoogle电面面经only when mitbbs is down do i realize how i miss it加州的老中软工，interview 喜欢问些啥？刚才想了想大牛们选择加入三星很make sense强烈申请本年度找工作最坑爹榜首排名两小时就电面A了。。谁能解释下espp找人update网站请问salesforce onsiteiit人也不多吧?怎么面试全是他们?收到F的口头offer, 【包子已发】 谢谢大家！
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。