a********a
发帖数: 219 | 1 我说话虽然难听，但我不刻薄，也不做作。我只说事实。
当人们为自己在言语上占了上风而得意的时候，有多少人会想到除了言语上的快感他其
实并没有得到任何东西呢？
随便说一句吧。Greedy第一原则：
If you cannot prove your greedy is correct, it is wrong. |
|
b***e
发帖数: 1419 | 2 You are mixing up provability with tautology. A statement cannot be
proved does not mean it is proved to be wrong. As an instance, you cannot
prove greedy works does not imply that you can disprove greedy works. |
|
h*******d
发帖数: 387 | 3 these USCIS trash spend the money, most from our (H1B )application fee and
H4 renewal, in a word, from all foregners' etc.
even i got back from Canada, the Customer officer of Champlain Port, NY,
charged me US$6.00 for issuing me a new I-94 card.
toooooooo greedy. their eyes become much green just like their money.
go to hell these greedy rats. |
|
k***e
发帖数: 556 | 4 我提一个算法，用greedy algorithm for the min-max condition
1. make a guess of the max segment length for dividing a[i:j] into x
sections. suppose it is y, i.e, we want to answer the following question:
Q: is it possible to divide a[i:j] into x sessions with each session <= y?
To answer the question, we will use greedy algorithm. find the maximal j_0
such that: sum_{s=j}^{j_0} a[s] <= y then
f(a,i,j,y,x) = f(a,j_0+1,j,y,x-1)
Thus, we can answer Q in time n for each specific x.
2. note that: max{a[i]} <= |
|
B*****t
发帖数: 335 | 5 where is the greedy choice property in this problem? I doubt the greedy
approach. |
|
c*********n
发帖数: 1057 | 6 greedy有的时候不行的吧
比如硬币：24 10 1
要求30
那最优是 10 10 10
greedy的话是24 1 1 1 1 1 1 |
|
h**6
发帖数: 4160 | 7 如果在最大面值的两倍以内，DP和greedy解都是一样的，那么对于所有的数额，DP和
greedy解都是相同的。 |
|
w*****p
发帖数: 215 | 8 应该是greedy。
上面错了，应该是这样的
n f(n) g(n)
1 1 0
2 2 0
3 3 0
4 4 0
5 5 0
6 6 0
7 8 4
8 10 5
9 12 6
10 16 7
11 20 8
12 24 9
13 30 10
14 40 11
15 48 12
16 64 13
n>6, f(n)=2f(n-3). 这个具有greedy 的结构。数学可以证明。
首先证明 f(n)>=f(n-1)+1, 很简单，不写了。
然后 f(n)=max(f(n-1)+1, f(n-2)+2,, 2*f(n-4)+1, ....) 但是 2f(n-3)>= 2f(n-4)+
1, 所以 f(n)=max(f(n-1)+1, f(n-2)+2,f(n-3)*2)。
最后，归纳证明 f(n)=2f(n-3).
Trace back 就是一堆 Ctrl+A, Ctrl+C, Ct... 阅读全帖 |
|
c**y
发帖数: 172 | 9 For this problem, greedy algo. works. Always choose the largest coin that is
allowed.
However,for some special sets of coins, such as 25, 10, 7, 5, 1, the greedy
algo. doesn't work. So we need to use dynamical programming to solve this
problem. |
|
e****a
发帖数: 449 | 10 . 在版上潜水快一年了 收获非常大 现在拿到了比较满意的offer, 中型IT公司，环境
还不错，非
湾区和NYC， 一年8万多。发找工作的经历回馈本版, 给还在找工或者将要找工的同学
参考.主要针
对转行的，没有经验的同学，如果有说的不对的或者废话的, 大家可以直接忽略,因为
本人是菜鸟.
背景: 生物phd, WSN, 计算机 master.毫无工作经验，无实际project经验. 面过的
公司:
Blackrock, BOA, Morgan stanley, GS, Facebook, Google 和给offer的公司。 有一
点统计和 ML的知识背景,后来证明毫无用处. c++和 java比较熟悉 没有大project经验
,
j2ee, .net, LAMP 知道一些, 后来突击学习了操作系统和网络的基本知识, 还有就是
经常在
mitbbs 学习大牛们的帖子. 整理了版上一年内的 和 careercup 上的一些面经, 比较
乱, 大家
可以参考下, 基本上概括了店面的所有题，onsite的大部分题. 非常感谢版上的常驻大
牛小牛们给
我的帮助，现在牛牛们都忙着发财... 阅读全帖 |
|
l******t
发帖数: 2243 | 11 congrats!
发信人: evaeva (evaeva), 信区: JobHunting
标 题: 生物PHD 转行找CS， 报Offer和罗嗦的面经
发信站: BBS 未名空间站 (Sat Mar 19 06:10:37 2011, 美东)
. 在版上潜水快一年了 收获非常大 现在拿到了比较满意的offer, 中型IT公司，环境
还不错，非
湾区和NYC， 一年8万多。发找工作的经历回馈本版, 给还在找工或者将要找工的同学
参考.主要针
对转行的，没有经验的同学，如果有说的不对的或者废话的, 大家可以直接忽略,因为
本人是菜鸟.
背景: 生物phd, WSN, 计算机 master.毫无工作经验，无实际project经验. 面过的
公司:
Blackrock, BOA, Morgan stanley, GS, Facebook, Google 和给offer的公司。 有一
点统计和 ML的知识背景,后来证明毫无用处. c++和 java比较熟悉 没有大project经验
,
j2ee, .net, LAMP 知道一些, 后来突击学习了操作系统和网络的基本知识, 还有就是... 阅读全帖 |
|
g*********s
发帖数: 1782 | 12 那个实在太长了。我提炼了一下。似乎很难啊。
啥是soduko test？
最长回文的算法到底是啥？
sum of square是哪个经典算法？
发信人: evaeva (evaeva), 信区: JobHunting
标 题: 生物PHD 转行找CS， 报Offer和罗嗦的面经
发信站: BBS 未名空间站 (Sat Mar 19 06:10:37 2011, 美东)
背景: 生物phd, WSN, 计算机 master.毫无工作经验，无实际project经验
不在Google总部，面了５个人，
第一个负责论文讨论，ＥＥ背景，写底层code, 工作性质类似于打杂。
第二个问了简单的SODUKO ＴＥＳＴ。 我写了一白板，和他讨论了下各种方法的复杂
度，就混过
去了。他自己做的东西也很简单，不懂ＭＬ，就做做数据库，写C 的。
第三个ＡＵＴＯＭＡＴＩＯＮ背景，做ADword。做题找最长回文。反转找最长相同加
suffix tree
不对。用简单的方法，n2 和n3。最好方法就是suffix tree。
第四个是JAVA person. 问把整数分成 sum of square的经典问题。... 阅读全帖 |
|
l*********y
发帖数: 142 | 13 第四个是JAVA person. 问把整数分成 sum of square的经典问题。递归解法。然后优
化，我给
了greedy的想法，他提示说可以用greedy 的解做bound。
Could you please elaborate the question and solution?
Is this a classic question?
Thanks. |
|
f***g
发帖数: 214 | 14 如果要求员工只参加一次，这肯定是greedy的。
先按照员工时间排序，在第一个结束的天放一个event，然后去掉那些能够覆盖着一天
的员工，继续找下一个结束点。
如果要求参加两次，我觉得也是greedy的。
待求证 |
|
l*****g
发帖数: 685 | 15 可不可以用下面的算法？借鉴了前面mercuriusl的思路
1）所有工人在original set setA里; create setB 用来存放已经找到one date的工人
2）create a set resultDates 用于存放找到的dates
3）用个sorted dictionary datePersonCounts统计出每天overlap
的人数
接下去就做以下循环：
4）从datePersonCounts中选择overlap人数最多的一天，maxDate，把它放进
resultDates，然后把dictionary中maxDate对应的entry删除
5) 在setB中找出maxDate那天available的工人，把他从setB删除；同时把工人的
available range中的所有dates, 从dictionary中减去：
datePersonCounts[date] -= 1;
6）在setA中找maxDate那天available的工人, 把他们从setA move to setB
（4）-（6）循环，直... 阅读全帖 |
|
g**********y
发帖数: 14569 | 16 很怀疑有O(n)的解，网上讨论这个题的，有一个很好的质疑：O(n)就意味着你不能扫描所有的点。但是矩阵里的任何一个点，好象都可以设计成最佳路径的必过点。
换个角度说，对n^2个元素的matrix, O(n)的解必然是局部最优就导致全局最优的，只能是greedy, 或者greedy的变种。 |
|
d*******l
发帖数: 338 | 17 同意，昨天想了半天，觉得无法从本质上排除任何一条可能的路径。如果不加别的限制
条件，那O(n)的方法应该无法消除所有的不确定性，结果就是不能保证正确性
描所有的点。但是矩阵里的任何一个点，好象都可以设计成最佳路径的必过点。
只能是greedy, 或者greedy的变种。 |
|
f*********i
发帖数: 197 | 18 有一堆的工作,每个工作有开始和结束时间,假设表示为[2,3],[3,7]等等,现在要求在[1
,n]的时间段内选出尽可能多的工作.
如果用按照开始时间排序的方法,greedy是无法保证最多的.我也考虑过把这些interval
按照开始和结束时间分别排序,然后比较,但是这个本质上也还是greedy.
一种方法是找出所有interval的combination,用recursive写程序是很简单,但是时间复
杂度太高了,虽然很多情况可以减枝.
求高人解答 |
|
|
|
c*****t
发帖数: 13 | 21 本人CS硕士名校非牛人,一年前去了一家中型软件公司做SD,不喜欢,刚刚跳去一家小HF.面试
的过程好像西游记一样,路途遥遥,艰险不断,怪物层出不穷,自己的本领也日渐增长,2年来承蒙
版上各路豪杰照顾分享,今日也算有个结果;特此拿出小弟所见所闻共勉,纪念找工作的艰辛,愿
大家早日心想试成,取到真经!
/***********************
小测验
***********************/
首先来个小测验,看你能看懂多少
1.array,list,BST,Hashtable,queue,stack,suffix tree,collection...
2.BFS,DFS,DP,D&C,Greedy,Dijkstra,tree traversal,recursion,quick
sort...
3.A,F,G,L,M,O,T,Y...
4.OOP,GC,Polymorphism,interface,abstract class,singleton...
5.bar raiser,white board programming,lunch interview..... 阅读全帖 |
|
i**d
发帖数: 357 | 22
你这个greedy的取值条件不对。
应该是首先按照结束时间排序，然后greedy的每次取最早结束的presentation.
并且remove有overlap的presentation
按照这个例子应该首先排序成
[0,2],[3,7],[3,12],[8,15],[14,15]
首先取 [0,2]
然后取 [3,7] 并remove有overlap的[3,12]
最后取 [8,15], 并remove掉[14,15]
结果就是[0,2],[3,7],[8,15] |
|
G******i
发帖数: 5226 | 23 ☆─────────────────────────────────────☆
currant (葡萄干) 于 駡 提到:
/***********************
小测验
***********************/
首先来个小测验,看你能看懂多少
1.array,list,BST,Hashtable,queue,stack,suffix tree,collection...
2.BFS,DFS,DP,D&C,Greedy,Dijkstra,tree traversal,recursion,quick
sort...
3.A,F,G,L,M,O,T,Y...
4.OOP,GC,Polymorphism,interface,abstract class,singleton...
5.bar raiser,white board programming,lunch interview...
如果以上任何概念不能熟练给出详细解答,请在往下面看之后抓紧复习1.数据结构(这个如果一
个没看懂可以按后退关窗口了)2.算法3.公司背景4.面向对象编程5.on... 阅读全帖 |
|
k***t
发帖数: 276 | 24 Isn't test() function use Greedy approach?
Can some one explain the reason why the greedy algorithm work?
Any link to algorithm explanation?
附Link上火鸡的Code:
Java code =>
public class MaxMinDiff {
public int max(int[] a, int k) {
int N = a.length;
if (N < k || k < 2) return -1;
int lo = 0;
int hi = (a[N-1] - a[0]) / (k-1) + 1;
while (hi > lo+1) {
int mid = (hi + lo) / 2;
if (test(a, mid, k)) {
lo = m... 阅读全帖 |
|
n*******w
发帖数: 687 | 25 要提高communication的确mock interview是很有效的。一般career center都有人提供
这个服务。只要愿意，可以多去预约mock几次。
几个题大概写了下想法。
1. social graph
两个想法。
第一个，允许suboptimal solution的话，用greedy。标准就是前面有人说的，选邻边
的时候，选没有收到消息的邻边最多的那个节点。一个足够scalable的network，这样
做应该能非常接近最优解。
第二个，要最优解得exhaustive遍历了。dfs + backtrace。走到不能走了，记录长度
跟路径。backtrace回去。遍历完所有可能性。
很容易证明，这题用greedy或者dp都不work。
2. search FB status
好像就是google那篇paper里边的那一套，inverted index + map/reduce。先index每
个status中每个关键字，建inverted index。每个关键字可以hash到一个整数上。然后
每个机器负责一个range的关键字。
如果某个range的关键字太多，某个机... 阅读全帖 |
|
k***t
发帖数: 276 | 26 Isn't test() function use Greedy approach?
Can some one explain the reason why the greedy algorithm work?
Any link to algorithm explanation?
附Link上火鸡的Code:
http://www.mitbbs.com/article/JobHunting/31959819_0.html
Java code =>
public class MaxMinDiff {
public int max(int[] a, int k) {
int N = a.length;
if (N < k || k < 2) return -1;
int lo = 0;
int hi = (a[N-1] - a[0]) / (k-1) + 1;
while (hi > lo+1) {
int mid = (hi + lo) / 2;
... 阅读全帖 |
|
b***u
发帖数: 12010 | 27 最讨厌greedy问题了。方法简单但是证明麻烦，难想到。dp比greedy容易多了。 |
|
b***u
发帖数: 12010 | 28 最讨厌greedy问题了。方法简单但是证明麻烦，难想到。dp比greedy容易多了。 |
|
w****x
发帖数: 2483 | 29
greedy 又不能保证最优, 这题就考个DP, 别折腾啦, 还没见过哪家面试考greedy的 |
|
a********m
发帖数: 15480 | 30 你的程序检查每个点，不算尽量往远跳的greedy。greedy是:
start = 0;
end = 0;
while (end < n) {
end = array[start];
} |
|
d*****8
发帖数: 38 | 31 这个稍微不同于最少硬币找零, greedy算法，
1. 目标是最多的满桶;
2. 可以溢出桶
不满足greedy的条件：当前的最优解不受子问题影响.
像用在traveling salesman problem，
反例：
50， 70， 50， 31
用50+50, 70+31。最多2个桶 |
|
C***U
发帖数: 2406 | 32 能说下你的反例得意思吗？
这个稍微不同于最少硬币找零, greedy算法，1. 目标是最多的满桶;2. 可以溢出桶不
满足greedy的条件：当前的最优解不受子问题影响.像用在traveling sale........
★ Sent from iPhone App: iReader Mitbbs 7.56 - iPad Lite |
|
C***U
发帖数: 2406 | 33 明白你的意思了。 但是我的解法刚好可以解决你的问题。 不是反例。
每个桶需要的水量数组是A： 30，50， 50，69
每个桶现有水量得数组B：31， 50， 50， 70
从31开始， 把A里面第一桶满了。从A和B里面去掉，然后第二个桶去填充A里面剩下得
不是他自己得桶。
这个稍微不同于最少硬币找零, greedy算法，1. 目标是最多的满桶;2. 可以溢出桶不
满足greedy的条件：当前的最优解不受子问题影响.像用在traveling sale........
★ Sent from iPhone App: iReader Mitbbs 7.56 - iPad Lite |
|
g***s
发帖数: 3811 | 34 "如果greedy可以找到正好满桶100的解，那么每次找最大的不溢出的桶；"
88+4+4+4=100
88+9+4=101
你到底greedy是先找正好１００优先，还是最大不溢出优先？
两者都有反例 |
|
j********x
发帖数: 2330 | 35 greedy只有在每门只是至多另一门课的先修课程的情况下是正确的，证明在下面的论文
里：
http://www.jstor.org/stable/pdfplus/167050.pdf?acceptTC=true
845页以后的部分，比较麻烦。
如果是任意的先后关系，则问题是np hard。经典的scheduling问题。
一般的算法分析可以大概猜出这道题在一般情况下是np hard这个结论。greedy应该是
一个很明显的近似算法，至于其他就看面试官心情了。
另外lz面什么方向的职位，怎么问这么奇葩的算法。。。
后面的document查重我以前问过类似的题，我提到的做法是从文件里的任意位置取少量
字符做digest。用digest做hash key，将放到hash table里，另设一个
table存放（这里假设ID是线性排列的整数，如果不是同样做hash table
）。找重在两个表里搜索就行。
假设160bit，20byte的digest，ID为4byte，每个表大概是10G内存，总共消耗20G，看
情况吧。
数据量更大就上mapred... 阅读全帖 |
|
j********e
发帖数: 1192 | 36 这是greedy的做法，不能保证最优吧.
例如1, 2, 3, 6, 7分两组，这样做的结果会得到(1,2,3,6), (7)吧？
当然，这肯定是个NP问题，这个greedy解法也不错了，应该能保证
是2/1-aprroximation了。 |
|
p*****2
发帖数: 21240 | 37 我记得在我没学过DP以前，Google一位大哥电面给我出了一道最简单的DP。那是我第一
次见DP，上来先晕了一下，用greedy来解的（当时也不知道greedy算法，只是思路自然
想的）。然后他说不对，给了我个反例，我突然发现需要用recursion来做。最后写了
一个recursion的过了。
后来才知道这种题就是DP。 |
|
i***e
发帖数: 452 | 38 上周二去的狗狗家onsite, 今天发信问HR update, HR说还在收集feedback, 说明天可
以给个update. 真心求bless! 希望这次可以成了， 谢谢大家！
----------------------
Update: hr今天打电话说明天hiring committee 出结果！ 还说透露点feedback： ＂
some are good, some are not consistent ", 然后说coding is good！ 看来有一些
不好的feedback 了！ 继续求bless 了！只能看人品爆发了！谢谢
--------------------------------------------------
update2： 写个面经了。。
1） int pow(int n, int m)
2) 写一个类是timer 的东西， 例如给个数值t和函数，等t时间之后call 这个函数。
（然后问有多个这些如果支持多次调用怎么办， 有哪些问题之类的）
3）给一个函数 void f(){.... return;} 然后问在return 语句的时候程序cl... 阅读全帖 |
|
S*********r
发帖数: 4729 | 39 你说的很多是greedy方法。DP经常用greedy方法解决子问题。所以这两个概念比较容易
混淆。
不过，话说回来，你只要知道怎么解决实际问题就行 没必要硬记得这些概念吧
Recursion |
|
P**********c
发帖数: 3417 | 40 我说的这个其实跟greedy algorithm不完全一样. Greedy algorithm是只看一步。而我
是说站在那个时间点上，一般人都会走当时觉得最优的路。当时的最优不一定是以后的
最优，是因为外界因素的变化。你能说老顾及着以前的东西不白费对以后就好么，
我觉得也不见得。主要是这世界人为能控制的因素太少了。 |
|
h**********9
发帖数: 3252 | 41 来自主题: JobHunting版 - 请问G一题
客气点好吗？我又不是全职解题的，拖家带口的有点时间不容易.
还有一些地方没想通，就当这个是 heuristic greedy 解，不一定能算出最优解，先给
个 O((Max(x) - Min(x))*N^2） 的 code, 谁能帮忙验证一下？ 如果可行我再解析O((
Max(x) - Min(x))*N*LG(N))。
import java.util.Arrays;
public class Partition {
public static int getMinDifference(int input[]) {
assert (input.length % 2 == 0) : "Input must have even number of
items.";
Arrays.sort(input);
int x[] = new int[input.length / 2];
int y[] = new int[input.length / 2];
for(int i = 0; i < x.... 阅读全帖 |
|
h**********9
发帖数: 3252 | 42 来自主题: JobHunting版 - 请问G一题
客气点好吗？我又不是全职解题的，拖家带口的有点时间不容易.
还有一些地方没想通，就当这个是 heuristic greedy 解，不一定能算出最优解，先给
个 O((Max(x) - Min(x))*N^2） 的 code, 谁能帮忙验证一下？ 如果可行我再解析O((
Max(x) - Min(x))*N*LG(N))。
import java.util.Arrays;
public class Partition {
public static int getMinDifference(int input[]) {
assert (input.length % 2 == 0) : "Input must have even number of
items.";
Arrays.sort(input);
int x[] = new int[input.length / 2];
int y[] = new int[input.length / 2];
for(int i = 0; i < x.... 阅读全帖 |
|
D**********d
发帖数: 849 | 43 需要说明的是 题目要求结合运算满足结合律（环表），不满足交换律, 不然干脆是两
个 sets,
为什么叫 lists?
所以 Greedy 不能解第二题，见以下反例
按 Greedy 算法
( (2 3) 4 ) ( 6 (5 4) ) ) = 62
但是有一解法 （把 2 3 4 移到末位）
（（6 5） （（4 2）（3 4） ）） = 61
可用二维 DP 解, O(N^2)
对于第一题， 可对 B 用 二进制表示(所以 log(B) ), 利用
(a mod c)^n mod c = a^n mod c
求解 |
|
o****i
发帖数: 1706 | 44 对的，用greedy感觉不能做到最小cost吧，比如说3个t,2个s,最左边的那个s cost2,
只覆盖1个t,第二个s cost 5，不过覆盖所有3个t.如果greedy的话，那不是最优解就要
两个s都被加入子集了吗？其实只要第二个s就够了。 |
|
p*****2
发帖数: 21240 | 45
感觉是test case的问题。没有包含worst case。按说这题DP应该也能过才对。感觉DP
比Greedy更有编程含量。Greedy有点凑出来的感觉。 |
|
w****a
发帖数: 710 | 46 用greedy能O(n)，用DP达不到O(n)
研究了三种DP的办法，有一种能四十多毫秒过大集合，有一种超时，一种要一千多毫秒
greedy的解jump game是最好的 |
|
B********t
发帖数: 147 | 47 搞了半天DP，还是通不过大集合。原来就这么几行就解决了
int jump(int A[], int n) {
int hops = 0;
int end = n-1;
while(end)
{
for(int i = 0; i <= end; i++)
{
if((A[i]+i)>=end)
{
hops++;
end = i;
}
}
}
return hops;
}
这算是greedy吗？不熟悉greedy。准备去看看算法导论上的那章。 |
|
h*******8
发帖数: 29 | 48 多谢回复，不过诚如二爷所说，这题是greedy。
你的思路也是greedy。
放在dp底下的确有点误导，待会重写个。 |
|
y*******o
发帖数: 6632 | 49 1 loop method:
class Solution {
public:
int jump(int A[], int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(n<=1){
return 0;
}
int iend=A[0];
int stepCount=1;
int nextEnd=A[0];
int i=1;
while(i
if(iend
return -1;
}
while(i<=iend){
if(nextEnd阅读全帖 |
|
c****7
发帖数: 4192 | 50 我这样是greedy吗？
public int jump(int[] A) {
int i=A.length-1;
int step=0;
while(i>0){
for(int j=0;j
if(A[j]+j>=i){
step++;
i=j;
break;
}
}
}
return step;
}
从最后一个开始，看从最前面哪一个可以跳到最后，找到就break，算一步。再从前往
后找，找到第一个就break，算第2步，直到第一个。我这个greedy是从后往前，好像没
有逻辑错误呀。
then
in
s |
|
