s******t
发帖数: 169 | 1 PhD念得不开心，刚来就被老板push到死，对研究的兴趣逐渐转变为每个星期的汇报任
务，感觉不爽，准备工作去。本来以为基础还凑合，国内参加过ACM拿过一个小奖，平
常也捣捣自己写的小project，但是基础不牢，从来做题需要哈希的时候就直接map，要
二分的时候直接lower_bound。这样的习惯直接导致我看career cup反感觉不适应。。
。做题目什么的时候从来就没用过链表之类的东西，写个删除结点能写半天。
然后就这样的状态面google，感觉答得还不错，不知道咋的就被刷了。
google的题目：
在一个平面(N*M的grid）上有W个点，求在这N*M个点中跟W个点距离和最小的一个点。
似乎这个是个经典题目，一开始没想出来，提示了一下做出来了。
另外一个问的：
直接递归法求fib（N）的复杂度是多少
还有很多杂的，各种数据结构复杂度是多少之类的。
一星期之后催HR结果被拒。悲剧。
然后急了，本来找得就比较晚，２月才开始准备，于是各种乱投简历，多数石沉大海。
本来都有点绝望了，准备好好准备一年算法搞一年竞赛明年直接申工作得了，结果拿到
了一个start up的intern。
其实是之前有一个公司的VP来学校讲了个lecture，聊了聊，要了张名片，也给他发了
个简历。刚好做的东西比较对口，但是直到１个多月以后才回我邮件说要面试。
面试也面得跟Google之类的不太一样，直接问以前做的相关东西，然后问我细节。但是
一个算法之类的问题也没有，呵呵。也许算是聊得比较投机外加做的东西确实很match
吧。
被G拒后的这两个月也没闲着，把以前最薄弱的动态规划的题目做了很多，topcoder里
div 2的动归题基本做了一遍，因为我感觉我不是那种当下能脑子转得很快的人（我有
的同学就可以，当场解决一个他从来没见过的问题，甚至于类似问题都没见过的问题）
，于是我只有多练。只有过度练习才能保证表现平常，今天早上做的topcoder居然破天
荒把三个题都做出来了。能一点点看见自己的进步，实在是让人高兴得不行。
下个星期还面amazon，但是应该不会去了，因为现在准备去的公司做的东西实在是有趣
，钱虽然少点，但是以后还可以挣嘛。
希望版上有跟我一样绝望过的同学保持希望，也许明天你就会感觉到自己强大的进步。 |
d****z
发帖数: 314 | 2 zan bless
【在 s******t 的大作中提到】
: PhD念得不开心，刚来就被老板push到死，对研究的兴趣逐渐转变为每个星期的汇报任
: 务，感觉不爽，准备工作去。本来以为基础还凑合，国内参加过ACM拿过一个小奖，平
: 常也捣捣自己写的小project，但是基础不牢，从来做题需要哈希的时候就直接map，要
: 二分的时候直接lower_bound。这样的习惯直接导致我看career cup反感觉不适应。。
: 。做题目什么的时候从来就没用过链表之类的东西，写个删除结点能写半天。
: 然后就这样的状态面google，感觉答得还不错，不知道咋的就被刷了。
: google的题目：
: 在一个平面(N*M的grid）上有W个点，求在这N*M个点中跟W个点距离和最小的一个点。
: 似乎这个是个经典题目，一开始没想出来，提示了一下做出来了。
: 另外一个问的：
|
H**********y
发帖数: 7928 | 3 赞
PhD念得不开心，刚来就被老板push到死，对研究的兴趣逐渐转变为每个星期的汇报任
务，感觉不爽，准备工作去。本来以为基础还凑合，国内参加过ACM拿过一个小奖，平
常也捣捣自己写的小project，但是基础不牢，从来做题需要哈希的时候就直接map，要
二分的时候直接lower_bound。这样的习惯直接导致我看career cup反感觉不适应。。
。做题目什么的时候从来就没用过链表之类的东西，写个删除结点能写半天。
然后就这样的状态面google，感觉答得还不错，不知道咋的就被刷了。
google的题目：
在一个平面(N*M的grid）上有W个点，求在这N*M个点中跟W个点距离和最小的一个点。
似乎这个是个经典题目，一开始没想出来，提示了一下做出来了。
另外一个问的：
直接递归法求fib（N）的复杂度是多少
还有很多杂的，各种数据结构复杂度是多少之类的。
一星期之后催HR结果被拒。悲剧。
然后急了，本来找得就比较晚，２月才开始准备，于是各种乱投简历，多数石沉大海。
本来都有点绝望了，准备好好准备一年算法搞一年竞赛明年直接申工作得了，结果拿到
了一个start up的intern。
其实是之前有一个公司的VP来学校讲了个lecture，聊了聊，要了张名片，也给他发了
个简历。刚好做的东西比较对口，但是直到１个多月以后才回我邮件说要面试。
面试也面得跟Google之类的不太一样，直接问以前做的相关东西，然后问我细节。但是
一个算法之类的问题也没有，呵呵。也许算是聊得比较投机外加做的东西确实很match
吧。
被G拒后的这两个月也没闲着，把以前最薄弱的动态规划的题目做了很多，topcoder里
div 2的动归题基本做了一遍，因为我感觉我不是那种当下能脑子转得很快的人（我有
的同学就可以，当场解决一个他从来没见过的问题，甚至于类似问题都没见过的问题）
，于是我只有多练。只有过度练习才能保证表现平常，今天早上做的topcoder居然破天
荒把三个题都做出来了。能一点点看见自己的进步，实在是让人高兴得不行。
下个星期还面amazon，但是应该不会去了，因为现在准备去的公司做的东西实在是有趣
，钱虽然少点，但是以后还可以挣嘛。
希望版上有跟我一样绝望过的同学保持希望，也许明天你就会感觉到自己强大的进步。
【在 s******t 的大作中提到】
: PhD念得不开心，刚来就被老板push到死，对研究的兴趣逐渐转变为每个星期的汇报任
: 务，感觉不爽，准备工作去。本来以为基础还凑合，国内参加过ACM拿过一个小奖，平
: 常也捣捣自己写的小project，但是基础不牢，从来做题需要哈希的时候就直接map，要
: 二分的时候直接lower_bound。这样的习惯直接导致我看career cup反感觉不适应。。
: 。做题目什么的时候从来就没用过链表之类的东西，写个删除结点能写半天。
: 然后就这样的状态面google，感觉答得还不错，不知道咋的就被刷了。
: google的题目：
: 在一个平面(N*M的grid）上有W个点，求在这N*M个点中跟W个点距离和最小的一个点。
: 似乎这个是个经典题目，一开始没想出来，提示了一下做出来了。
: 另外一个问的：
|
g**********y
发帖数: 14569 | 4 super zan!
【在 s******t 的大作中提到】
: PhD念得不开心，刚来就被老板push到死，对研究的兴趣逐渐转变为每个星期的汇报任
: 务，感觉不爽，准备工作去。本来以为基础还凑合，国内参加过ACM拿过一个小奖，平
: 常也捣捣自己写的小project，但是基础不牢，从来做题需要哈希的时候就直接map，要
: 二分的时候直接lower_bound。这样的习惯直接导致我看career cup反感觉不适应。。
: 。做题目什么的时候从来就没用过链表之类的东西，写个删除结点能写半天。
: 然后就这样的状态面google，感觉答得还不错，不知道咋的就被刷了。
: google的题目：
: 在一个平面(N*M的grid）上有W个点，求在这N*M个点中跟W个点距离和最小的一个点。
: 似乎这个是个经典题目，一开始没想出来，提示了一下做出来了。
: 另外一个问的：
|
r********g
发帖数: 1351 | 5 lz心态很好啊，congrats!
【在 s******t 的大作中提到】
: PhD念得不开心，刚来就被老板push到死，对研究的兴趣逐渐转变为每个星期的汇报任
: 务，感觉不爽，准备工作去。本来以为基础还凑合，国内参加过ACM拿过一个小奖，平
: 常也捣捣自己写的小project，但是基础不牢，从来做题需要哈希的时候就直接map，要
: 二分的时候直接lower_bound。这样的习惯直接导致我看career cup反感觉不适应。。
: 。做题目什么的时候从来就没用过链表之类的东西，写个删除结点能写半天。
: 然后就这样的状态面google，感觉答得还不错，不知道咋的就被刷了。
: google的题目：
: 在一个平面(N*M的grid）上有W个点，求在这N*M个点中跟W个点距离和最小的一个点。
: 似乎这个是个经典题目，一开始没想出来，提示了一下做出来了。
: 另外一个问的：
|
m****i
发帖数: 650 | 6 在一个平面(N*M的grid）上有W个点，求在这N*M个点中跟W个点距离和最小的一个点。
似乎这个是个经典题目，一开始没想出来，提示了一下做出来了。
这个除了 brute force还有啥好的方法 |
l***i
发帖数: 1309 | 7 congrats.
The (NxM) with W points problem is to find median with L1 norm. Let (xi,yi)
be the (row,col) index of each point. Sort all xi and Sort all yi, then pick
median (xi, yi) is your answer. |
P******x
发帖数: 259 | 8 cong!
【在 s******t 的大作中提到】
: PhD念得不开心，刚来就被老板push到死，对研究的兴趣逐渐转变为每个星期的汇报任
: 务，感觉不爽，准备工作去。本来以为基础还凑合，国内参加过ACM拿过一个小奖，平
: 常也捣捣自己写的小project，但是基础不牢，从来做题需要哈希的时候就直接map，要
: 二分的时候直接lower_bound。这样的习惯直接导致我看career cup反感觉不适应。。
: 。做题目什么的时候从来就没用过链表之类的东西，写个删除结点能写半天。
: 然后就这样的状态面google，感觉答得还不错，不知道咋的就被刷了。
: google的题目：
: 在一个平面(N*M的grid）上有W个点，求在这N*M个点中跟W个点距离和最小的一个点。
: 似乎这个是个经典题目，一开始没想出来，提示了一下做出来了。
: 另外一个问的：
|
s******n
发帖数: 3946 | 9 http://www.geomidpoint.com/calculation.html
Center of minimal distance?
)
pick
【在 l***i 的大作中提到】
: congrats.
: The (NxM) with W points problem is to find median with L1 norm. Let (xi,yi)
: be the (row,col) index of each point. Sort all xi and Sort all yi, then pick
: median (xi, yi) is your answer.
|
z****4
发帖数: 194 | 10 我在wiki上看到的是这个：
Despite being an easy to understand concept, computing the geometric median
poses a challenge. The centroid or center of mass, defined similarly to the
geometric median as minimizing the sum of the squares of the distances to
each sample, can be found by a simple formula — its coordinates are the
averages of the coordinates of the samples — but no such formula is known
for the geometric median, and it has been shown that no explicit formula,
nor an exact algorithm involving only arithmetic operations and kth roots
can exist in general. Therefore only numerical or symbolic approximations to
the solution of this problem are possible under this model of computation.[
3]
)
pick
【在 l***i 的大作中提到】
: congrats.
: The (NxM) with W points problem is to find median with L1 norm. Let (xi,yi)
: be the (row,col) index of each point. Sort all xi and Sort all yi, then pick
: median (xi, yi) is your answer.
|
|
|
f*********y
发帖数: 376 | 11 you are lucky...your advisor at least allow you to do internship...he/she is
not so puch...
【在 s******t 的大作中提到】
: PhD念得不开心，刚来就被老板push到死，对研究的兴趣逐渐转变为每个星期的汇报任
: 务，感觉不爽，准备工作去。本来以为基础还凑合，国内参加过ACM拿过一个小奖，平
: 常也捣捣自己写的小project，但是基础不牢，从来做题需要哈希的时候就直接map，要
: 二分的时候直接lower_bound。这样的习惯直接导致我看career cup反感觉不适应。。
: 。做题目什么的时候从来就没用过链表之类的东西，写个删除结点能写半天。
: 然后就这样的状态面google，感觉答得还不错，不知道咋的就被刷了。
: google的题目：
: 在一个平面(N*M的grid）上有W个点，求在这N*M个点中跟W个点距离和最小的一个点。
: 似乎这个是个经典题目，一开始没想出来，提示了一下做出来了。
: 另外一个问的：
|
c******4
发帖数: 4896 | |
P*A
发帖数: 189 | 13 找个近似的中点，keep一个candidate stack，然后search?
【在 m****i 的大作中提到】
: 在一个平面(N*M的grid）上有W个点，求在这N*M个点中跟W个点距离和最小的一个点。
: 似乎这个是个经典题目，一开始没想出来，提示了一下做出来了。
: 这个除了 brute force还有啥好的方法
|
f*******t
发帖数: 7549 | |
n****a
发帖数: 1069 | 15 太牛X了，我第一次看见有人说做得东西实在有趣。这就是真的乐在其中吧。我真羡慕
LZ，神马时候工作对我来说也变的有趣就好了。 |
e**d
发帖数: 750 | |
w****o
发帖数: 2260 | 17 很牛
【在 s******t 的大作中提到】
: PhD念得不开心，刚来就被老板push到死，对研究的兴趣逐渐转变为每个星期的汇报任
: 务，感觉不爽，准备工作去。本来以为基础还凑合，国内参加过ACM拿过一个小奖，平
: 常也捣捣自己写的小project，但是基础不牢，从来做题需要哈希的时候就直接map，要
: 二分的时候直接lower_bound。这样的习惯直接导致我看career cup反感觉不适应。。
: 。做题目什么的时候从来就没用过链表之类的东西，写个删除结点能写半天。
: 然后就这样的状态面google，感觉答得还不错，不知道咋的就被刷了。
: google的题目：
: 在一个平面(N*M的grid）上有W个点，求在这N*M个点中跟W个点距离和最小的一个点。
: 似乎这个是个经典题目，一开始没想出来，提示了一下做出来了。
: 另外一个问的：
|
A**u
发帖数: 2458 | 18 在一个平面(N*M的grid）上有W个点，求在这N*M个点中跟W个点距离和最小的一个点。
这题目怎么做 |
a****o
发帖数: 298 | 19 最小距离的题。答案是什么？是这样子解吗？
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
【在 s******t 的大作中提到】
: PhD念得不开心，刚来就被老板push到死，对研究的兴趣逐渐转变为每个星期的汇报任
: 务，感觉不爽，准备工作去。本来以为基础还凑合，国内参加过ACM拿过一个小奖，平
: 常也捣捣自己写的小project，但是基础不牢，从来做题需要哈希的时候就直接map，要
: 二分的时候直接lower_bound。这样的习惯直接导致我看career cup反感觉不适应。。
: 。做题目什么的时候从来就没用过链表之类的东西，写个删除结点能写半天。
: 然后就这样的状态面google，感觉答得还不错，不知道咋的就被刷了。
: google的题目：
: 在一个平面(N*M的grid）上有W个点，求在这N*M个点中跟W个点距离和最小的一个点。
: 似乎这个是个经典题目，一开始没想出来，提示了一下做出来了。
: 另外一个问的：
|
s******n
发帖数: 3946 | 20 最小距离的做法：先算一个近似点。以近似点为中心找8个方向半径为r的点，如果有更
优解则替代，否则将r/2继续找。
http://www.geomidpoint.com/calculation.html |
|
|
p*******e
发帖数: 746 | |
l*****o
发帖数: 19235 | |
h********e
发帖数: 1972 | 23 平面距离那题，如果是L_1 distance，就是中位数。 X，Y独立. 时间O(|W|). 证明很简单，随便画个1维的case |
z****4
发帖数: 194 | 24 ms没那么简单，2D以上和1D不同：
http://en.wikipedia.org/wiki/Geometric_median
很简单，随便画个1维的case
【在 h********e 的大作中提到】
: 平面距离那题，如果是L_1 distance，就是中位数。 X，Y独立. 时间O(|W|). 证明很简单，随便画个1维的case
|
m****i
发帖数: 650 | 25 平面距离那题，如果是L_1 distance，就是中位数。 X，Y独立. 时间O(|W|). 证明很
简单，随便画个1维的case
什么是L_1 distance.
做法就风别求 x,y 的 medium 就可以了么
eg.
[1, 1], [2,4], [1, 100], [4, 200],[2, 500]
的答案是[2, 100] 么？ |
h********e
发帖数: 1972 | 26 一样的。。。。。L_2 square距离就用重心。。L_1就是median。。 你可以求个导数证明出来的. 你贴的wikilink 牛头不对马嘴，不是同一个问题, 他问的是L_2 distance，算起来麻烦些。 L_1就是格点距离在这里，就是X的距离+Y的距离。 所以X和Y可以分开做的。互不影响。 |
h********e
发帖数: 1972 | 27 偶数个点，要取两个medians的平均值。
【在 m****i 的大作中提到】
: 平面距离那题，如果是L_1 distance，就是中位数。 X，Y独立. 时间O(|W|). 证明很
: 简单，随便画个1维的case
: 什么是L_1 distance.
: 做法就风别求 x,y 的 medium 就可以了么
: eg.
: [1, 1], [2,4], [1, 100], [4, 200],[2, 500]
: 的答案是[2, 100] 么？
|
g**********y
发帖数: 14569 | 28 楼主的问题很特殊，因为解必须在空间：0<=x
一样。
【在 z****4 的大作中提到】
: ms没那么简单，2D以上和1D不同：
: http://en.wikipedia.org/wiki/Geometric_median
:
: 很简单，随便画个1维的case
|
s**m
发帖数: 4340 | |
z****4
发帖数: 194 | 30 举个最简单的例子，假设所有点只能取(0,0),(0,1),(1,1),(1,0)四个值，假设(0,0)有
一万个点，(1,1)有一万零一个点，(1,0)有一万个点，(0,1)有1万个点，那么x,y方向
的median就都是1，那么得到的2D median就是(1,1)，这显然不是到这四万零一个点的
距离和最小的点
证明出来的. 你贴的wikilink 牛头不对马嘴，不是同一个问题, 他问的是L_2
distance，算起来麻烦些。 L_1就是格点距离在这里，就是X的距离+Y的距离。 所以X
和Y可以分开做的。互不影响。
【在 h********e 的大作中提到】
: 一样的。。。。。L_2 square距离就用重心。。L_1就是median。。 你可以求个导数证明出来的. 你贴的wikilink 牛头不对马嘴，不是同一个问题, 他问的是L_2 distance，算起来麻烦些。 L_1就是格点距离在这里，就是X的距离+Y的距离。 所以X和Y可以分开做的。互不影响。
|
|
|
z****4
发帖数: 194 | 31 M和N足够大，点的个数足够多，总可以构造出接近实数解的问题
【在 g**********y 的大作中提到】
: 楼主的问题很特殊，因为解必须在空间：0<=x: 一样。
|
h********e
发帖数: 1972 | 32 你题目没看清楚。人家要你找个整数坐标的点，而且距离不是平方开根号，是L_1
distance. 显然就用median
X
【在 z****4 的大作中提到】
: 举个最简单的例子，假设所有点只能取(0,0),(0,1),(1,1),(1,0)四个值，假设(0,0)有
: 一万个点，(1,1)有一万零一个点，(1,0)有一万个点，(0,1)有1万个点，那么x,y方向
: 的median就都是1，那么得到的2D median就是(1,1)，这显然不是到这四万零一个点的
: 距离和最小的点
:
: 证明出来的. 你贴的wikilink 牛头不对马嘴，不是同一个问题, 他问的是L_2
: distance，算起来麻烦些。 L_1就是格点距离在这里，就是X的距离+Y的距离。 所以X
: 和Y可以分开做的。互不影响。
|
