n*********r
发帖数: 24 | 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。还问了别的题，都不难
。 |
s*********s
发帖数: 318 | 2 多谢.能不能详细说一下“给出一些扩展的方法”？
>第三个是SDE，从多个数中找到最大的k个。开始用的是max heap，被指出后，改
>正为min heap。还问了些别的，都不难。
programming perl上好像用quicksort的变形。比min heap快。 |
l*****a
发帖数: 14598 | 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，计算权重之和，
: 返回权重之和最大的。面试官听了，没什么表情，问了问时间复杂度，说这样大概可行
|
t*********n
发帖数: 89 | 4 第二题不是经典dp吗？ LZ的图算法看不太懂啊。 |
p*******4
发帖数: 45 | 5 怎么最近amazon的onsite一个比一个难！！ |
l****i
发帖数: 2772 | 6 第二题，有点像背包问题的变型。
第三题，也可以用quickselect。 |
r**h
发帖数: 1288 | 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，计算权重之和，
: 返回权重之和最大的。面试官听了，没什么表情，问了问时间复杂度，说这样大概可行
|
l*****a
发帖数: 14598 | 8 1) sort by endTime
2) f(n)= f(n-1)+list.get(n).value
//if list.get(n-1).endTime
max(f(n-1),f(k)+list.get(n).value)
//if list.get(k).endTime
btw,权值可以为负数吗？
【在 l****i 的大作中提到】
: 第二题，有点像背包问题的变型。
: 第三题，也可以用quickselect。
|
x*****0
发帖数: 452 | |
t*****h
发帖数: 137 | 10 这个是set covering problem, NP Complete.
难道是我对题的理解有误？
【在 t*********n 的大作中提到】
: 第二题不是经典dp吗？ LZ的图算法看不太懂啊。
|
|
|
a*********0
发帖数: 2727 | 11 谁说dp解就不能使np-complete呢
【在 t*****h 的大作中提到】
: 这个是set covering problem, NP Complete.
: 难道是我对题的理解有误？
|
a*********0
发帖数: 2727 | 12 第三个为什么是min heap？难道我脑抽了？ |
l*****a
发帖数: 14598 | 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？难道我脑抽了？
|
a*********0
发帖数: 2727 | 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
|
t*****h
发帖数: 137 | 15 Optimization is NP Hard, right?
【在 a*********0 的大作中提到】
: 谁说dp解就不能使np-complete呢
|
n*******w
发帖数: 687 | 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} }
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]
2. 使用A[i]，所以任意与A[i]有overlap的都要舍去，所以要找k
3. k找不到，因为A[i]的start time比第一个record的ending time都要小
【在 t*****h 的大作中提到】
: 这个是set covering problem, NP Complete.
: 难道是我对题的理解有误？
|
l*****a
发帖数: 14598 | 17 it is nlgk, isn't it?
辑吧
【在 a*********0 的大作中提到】
: 那不是要poll n-k次？如果只是选k，复杂度是klgn， 现在成了nlgn了。不是这种逻辑吧
|
t*****h
发帖数: 137 | 18 HEAP的size是K。
辑吧
【在 a*********0 的大作中提到】
: 那不是要poll n-k次？如果只是选k，复杂度是klgn， 现在成了nlgn了。不是这种逻辑吧
|
a*********0
发帖数: 2727 | 19 opt问题多了，怎么会全是np解
【在 t*****h 的大作中提到】
: Optimization is NP Hard, right?
|
a*********0
发帖数: 2727 | 20 n+klgn or k+nlgk, which one is better?
【在 t*****h 的大作中提到】
: HEAP的size是K。
:
: 辑吧
|
|
|
l*****a
发帖数: 14598 | 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]
|
n*******w
发帖数: 687 | 22 是的。你看DP[i]那个大括号里边包含了D[i-1]
max虽然写了很多，但是只有n个子问题。仔细看。
【在 l*****a 的大作中提到】
:
: i]
: 怎么会有这么多子问题？
: dp[k]不是递增的吗？
|
l*****a
发帖数: 14598 | 23 我仔细看了
我认为dp[k]是递增的 ，下面的max是不需要的
max { DP[k]+A[i].cost} }
当然找max(k)是需要的
【在 n*******w 的大作中提到】
: 是的。你看DP[i]那个大括号里边包含了D[i-1]
: max虽然写了很多，但是只有n个子问题。仔细看。
|
n*******w
发帖数: 687 | 24 哦，是的。我写的时候不知道怎么表达。
【在 l*****a 的大作中提到】
: 我仔细看了
: 我认为dp[k]是递增的 ，下面的max是不需要的
: max { DP[k]+A[i].cost} }
: 当然找max(k)是需要的
|
n*********r
发帖数: 24 | 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。 |
s****i
发帖数: 37 | 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，计算权重之和，
: 返回权重之和最大的。面试官听了，没什么表情，问了问时间复杂度，说这样大概可行
|
s****i
发帖数: 37 | |
s****i
发帖数: 37 | 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，计算权重之和，
: 返回权重之和最大的。面试官听了，没什么表情，问了问时间复杂度，说这样大概可行
|
d****m
发帖数: 1008 | 29 第二题不是教科书上的经典knapsack problem吗。。。DP入门题。。 |
n*********r
发帖数: 24 | 30 有人提到用Knapsack DP的方法解。可是，在面试的时候，我说想用DP的方法来考虑这
个问题的时候，直接就被打断，说dynamic programming不正确。 |
|
|
f********4
发帖数: 988 | 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，计算权重之和，
: 返回权重之和最大的。面试官听了，没什么表情，问了问时间复杂度，说这样大概可行
|
J*****a
发帖数: 4262 | 32 这不是背包 不懂装懂 说入门说明你还没入门呢
背包问题复杂度是伪多项式，是NP的 这个题就是多项式复杂度
这是带权重的scheduling problem，康奈尔的算法教材上的例题原题
【在 d****m 的大作中提到】
: 第二题不是教科书上的经典knapsack problem吗。。。DP入门题。。
|
J*****a
发帖数: 4262 | 33 此题可以用DP 只不过DP前要对任务排下序
有的面试官水平不怎的
【在 n*********r 的大作中提到】
: 有人提到用Knapsack DP的方法解。可是，在面试的时候，我说想用DP的方法来考虑这
: 个问题的时候，直接就被打断，说dynamic programming不正确。
|
d**********x
发帖数: 4083 | 34 algorithm design这本书如果习题都给出答案就好了。。。
【在 J*****a 的大作中提到】
: 这不是背包 不懂装懂 说入门说明你还没入门呢
: 背包问题复杂度是伪多项式，是NP的 这个题就是多项式复杂度
: 这是带权重的scheduling problem，康奈尔的算法教材上的例题原题
|
P******r
发帖数: 842 | 35 第二题能用longest increasing subsequence解吗。先用ending time排序。再keep一
个array
A[i] 就是ending到i的weight sum最大的interval sequence的sum |
d****m
发帖数: 1008 | 36 我也没明白你的喷点在哪里。也没明白你是喷不是DP还是不是knapsack。
这题是algorithm design 第六章DP的第一个例题，你自己去看。我说是DP入门题不对
？题目我也没仔细看，好像比knapsack还简单些。
也是非常的逗：）
【在 J*****a 的大作中提到】
: 这不是背包 不懂装懂 说入门说明你还没入门呢
: 背包问题复杂度是伪多项式，是NP的 这个题就是多项式复杂度
: 这是带权重的scheduling problem，康奈尔的算法教材上的例题原题
|
n*******w
发帖数: 687 | 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前要对任务排下序
: 有的面试官水平不怎的
|
x*****0
发帖数: 452 | |
n*********r
发帖数: 24 | 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。还问了别的题，都不难
。 |
s*********s
发帖数: 318 | 40 多谢.能不能详细说一下“给出一些扩展的方法”？
>第三个是SDE，从多个数中找到最大的k个。开始用的是max heap，被指出后，改
>正为min heap。还问了些别的，都不难。
programming perl上好像用quicksort的变形。比min heap快。 |
|
|
l*****a
发帖数: 14598 | 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，计算权重之和，
: 返回权重之和最大的。面试官听了，没什么表情，问了问时间复杂度，说这样大概可行
|
t*********n
发帖数: 89 | 42 第二题不是经典dp吗？ LZ的图算法看不太懂啊。 |
p*******4
发帖数: 45 | 43 怎么最近amazon的onsite一个比一个难！！ |
l****i
发帖数: 2772 | 44 第二题，有点像背包问题的变型。
第三题，也可以用quickselect。 |
r**h
发帖数: 1288 | 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，计算权重之和，
: 返回权重之和最大的。面试官听了，没什么表情，问了问时间复杂度，说这样大概可行
|
l*****a
发帖数: 14598 | 46 1) sort by endTime
2) f(n)= f(n-1)+list.get(n).value
//if list.get(n-1).endTime
max(f(n-1),f(k)+list.get(n).value)
//if list.get(k).endTime
btw,权值可以为负数吗？
【在 l****i 的大作中提到】
: 第二题，有点像背包问题的变型。
: 第三题，也可以用quickselect。
|
x*****0
发帖数: 452 | |
t*****h
发帖数: 137 | 48 这个是set covering problem, NP Complete.
难道是我对题的理解有误？
【在 t*********n 的大作中提到】
: 第二题不是经典dp吗？ LZ的图算法看不太懂啊。
|
a*********0
发帖数: 2727 | 49 谁说dp解就不能使np-complete呢
【在 t*****h 的大作中提到】
: 这个是set covering problem, NP Complete.
: 难道是我对题的理解有误？
|
a*********0
发帖数: 2727 | 50 第三个为什么是min heap？难道我脑抽了？ |
|
|
l*****a
发帖数: 14598 | 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？难道我脑抽了？
|
a*********0
发帖数: 2727 | 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
|
t*****h
发帖数: 137 | 53 Optimization is NP Hard, right?
【在 a*********0 的大作中提到】
: 谁说dp解就不能使np-complete呢
|
n*******w
发帖数: 687 | 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} }
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]
2. 使用A[i]，所以任意与A[i]有overlap的都要舍去，所以要找k
3. k找不到，因为A[i]的start time比第一个record的ending time都要小
【在 t*****h 的大作中提到】
: 这个是set covering problem, NP Complete.
: 难道是我对题的理解有误？
|
l*****a
发帖数: 14598 | 55 it is nlgk, isn't it?
辑吧
【在 a*********0 的大作中提到】
: 那不是要poll n-k次？如果只是选k，复杂度是klgn， 现在成了nlgn了。不是这种逻辑吧
|
t*****h
发帖数: 137 | 56 HEAP的size是K。
辑吧
【在 a*********0 的大作中提到】
: 那不是要poll n-k次？如果只是选k，复杂度是klgn， 现在成了nlgn了。不是这种逻辑吧
|
a*********0
发帖数: 2727 | 57 opt问题多了，怎么会全是np解
【在 t*****h 的大作中提到】
: Optimization is NP Hard, right?
|
a*********0
发帖数: 2727 | 58 n+klgn or k+nlgk, which one is better?
【在 t*****h 的大作中提到】
: HEAP的size是K。
:
: 辑吧
|
l*****a
发帖数: 14598 | 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]
|
n*******w
发帖数: 687 | 60 是的。你看DP[i]那个大括号里边包含了D[i-1]
max虽然写了很多，但是只有n个子问题。仔细看。
【在 l*****a 的大作中提到】
:
: i]
: 怎么会有这么多子问题？
: dp[k]不是递增的吗？
|
|
|
l*****a
发帖数: 14598 | 61 我仔细看了
我认为dp[k]是递增的 ，下面的max是不需要的
max { DP[k]+A[i].cost} }
当然找max(k)是需要的
【在 n*******w 的大作中提到】
: 是的。你看DP[i]那个大括号里边包含了D[i-1]
: max虽然写了很多，但是只有n个子问题。仔细看。
|
n*******w
发帖数: 687 | 62 哦，是的。我写的时候不知道怎么表达。
【在 l*****a 的大作中提到】
: 我仔细看了
: 我认为dp[k]是递增的 ，下面的max是不需要的
: max { DP[k]+A[i].cost} }
: 当然找max(k)是需要的
|
n*********r
发帖数: 24 | 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。 |
s****i
发帖数: 37 | 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，计算权重之和，
: 返回权重之和最大的。面试官听了，没什么表情，问了问时间复杂度，说这样大概可行
|
s****i
发帖数: 37 | |
s****i
发帖数: 37 | 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，计算权重之和，
: 返回权重之和最大的。面试官听了，没什么表情，问了问时间复杂度，说这样大概可行
|
d****m
发帖数: 1008 | 67 第二题不是教科书上的经典knapsack problem吗。。。DP入门题。。 |
n*********r
发帖数: 24 | 68 有人提到用Knapsack DP的方法解。可是，在面试的时候，我说想用DP的方法来考虑这
个问题的时候，直接就被打断，说dynamic programming不正确。 |
f********4
发帖数: 988 | 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，计算权重之和，
: 返回权重之和最大的。面试官听了，没什么表情，问了问时间复杂度，说这样大概可行
|
J*****a
发帖数: 4262 | 70 这不是背包 不懂装懂 说入门说明你还没入门呢
背包问题复杂度是伪多项式，是NP的 这个题就是多项式复杂度
这是带权重的scheduling problem，康奈尔的算法教材上的例题原题
【在 d****m 的大作中提到】
: 第二题不是教科书上的经典knapsack problem吗。。。DP入门题。。
|
|
|
J*****a
发帖数: 4262 | 71 此题可以用DP 只不过DP前要对任务排下序
有的面试官水平不怎的
【在 n*********r 的大作中提到】
: 有人提到用Knapsack DP的方法解。可是，在面试的时候，我说想用DP的方法来考虑这
: 个问题的时候，直接就被打断，说dynamic programming不正确。
|
d**********x
发帖数: 4083 | 72 algorithm design这本书如果习题都给出答案就好了。。。
【在 J*****a 的大作中提到】
: 这不是背包 不懂装懂 说入门说明你还没入门呢
: 背包问题复杂度是伪多项式，是NP的 这个题就是多项式复杂度
: 这是带权重的scheduling problem，康奈尔的算法教材上的例题原题
|
P******r
发帖数: 842 | 73 第二题能用longest increasing subsequence解吗。先用ending time排序。再keep一
个array
A[i] 就是ending到i的weight sum最大的interval sequence的sum |
d****m
发帖数: 1008 | 74 我也没明白你的喷点在哪里。也没明白你是喷不是DP还是不是knapsack。
这题是algorithm design 第六章DP的第一个例题，你自己去看。我说是DP入门题不对
？题目我也没仔细看，好像比knapsack还简单些。
也是非常的逗：）
【在 J*****a 的大作中提到】
: 这不是背包 不懂装懂 说入门说明你还没入门呢
: 背包问题复杂度是伪多项式，是NP的 这个题就是多项式复杂度
: 这是带权重的scheduling problem，康奈尔的算法教材上的例题原题
|
n*******w
发帖数: 687 | 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前要对任务排下序
: 有的面试官水平不怎的
|
x*****0
发帖数: 452 | |
s********n
发帖数: 53 | |
c********p
发帖数: 1969 | |
s********n
发帖数: 53 | |
g*********e
发帖数: 14401 | 80 是nlogk
辑吧
【在 a*********0 的大作中提到】
: 那不是要poll n-k次？如果只是选k，复杂度是klgn， 现在成了nlgn了。不是这种逻辑吧
|
|
|
g*********e
发帖数: 14401 | 81 我的那本书不知被谁借去了一直没还 郁闷
【在 J*****a 的大作中提到】
: 这不是背包 不懂装懂 说入门说明你还没入门呢
: 背包问题复杂度是伪多项式，是NP的 这个题就是多项式复杂度
: 这是带权重的scheduling problem，康奈尔的算法教材上的例题原题
|
C****y
发帖数: 77 | 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，计算权重之和，
: 返回权重之和最大的。面试官听了，没什么表情，问了问时间复杂度，说这样大概可行
|
C****y
发帖数: 77 | 83 在highscalability上找到一篇好文
http://highscalability.squarespace.com/blog/2012/9/19/the-4-bui
【在 C****y 的大作中提到】
: 同问第四题scale up system.
: 想知道比较好的答案是什么样的
:
: long
|
l*********d
发帖数: 78 | |
