s****n
发帖数: 220 | |
c***2
发帖数: 838 | 2 do you mean "Art of Computer Programming" or "Beautiful codes"?
you can find both from baidu or csdn (need a free account) |
s****n
发帖数: 220 | 3 多谢回复，我找的是微软亚研院的那边面试题集，在网上找了挺多的，都是不全的版本
，包括 ishare.sina.com.cn, baidu, google, csdn，verycd这些，所以想在这里求下
完整的版本，呵呵 |
l*****a
发帖数: 14598 | 4 the name in the book is
Beauty of Programming
【在 c***2 的大作中提到】
: do you mean "Art of Computer Programming" or "Beautiful codes"?
: you can find both from baidu or csdn (need a free account)
|
c****o
发帖数: 41 | |
b*********9
发帖数: 14 | |
s****n
发帖数: 220 | |
d********w
发帖数: 363 | |
s*******n
发帖数: 499 | 9 如何下载pdf版本呢，这个只能在线看？点了下载没反应，已经登陆用户了的
【在 d********w 的大作中提到】
: 百度文库上有完整版
: http://wenku.baidu.com/view/dc61ffec102de2bd96058850.html
: 分6卷下载
|
s****n
发帖数: 220 | |
|
|
v*******2
发帖数: 12 | |
H******7
发帖数: 1728 | 12 刚才下了这个书看了看 感觉不适合美国的面试。个人意见。：） |
m****i
发帖数: 650 | 13 一本很好的书，基本把现在面试的基本题题目有了解答和代码，但是不足是没有给出算
法分类，比如dynamic, backtracking。 |
z***e
发帖数: 5393 | 14 下下来看了看，随便翻了个求2D平面最近两点的问题，没搞懂他说的，如下图:
他说用中间那条线分区之后，就只要考虑CD那条线是不是最短？BD/AD/etc.都不必考虑
？？
what意思哦，CD最多只是在X-axis上的距离有可能最短而已，2D距离显然BD可能比CD短，
不晓得这是啥高深理论，或者他自己没说清楚？
【在 s****n 的大作中提到】
: rt,不胜感激～
|
z***e
发帖数: 5393 | 15 上面我对其中一个有疑问，马上又翻了里面一个例子。
题目是给出string s1和s2，问s2能否通过rotate s1得到，比如abc => cab之类的，书
里面的解答如下：
显然作者对programming pearl里面如何O(n)来rotate string一无所知，如果是美国这
边的Interview，fail掉的可能极大（采用programming pearl的方法，首先找s2[0]在
s1中的index比如s1[i]，然后尝试从s1[i]来rotate，如果不对，再找下一个i；而不是
从s1[0...n]全部来试.
这都是小trick，但是最大问题在他的第二种方法“可以用strstr()一次得到结果"----
他不知道strstr是O(n)的么？这样两个方法同样都是O(n*n)，哪来什么“提高空间复杂
度，降低时间复杂度”？这边面试的话，善良的Interviewer会问他strstr的复杂度是
多少，mean一点的一句话不说，下来绝对就涮掉了.
【在 H******7 的大作中提到】
: 刚才下了这个书看了看 感觉不适合美国的面试。个人意见。：）
|
j*****u
发帖数: 1133 | 16 帮作者(我的朋友)说几句，他们基本上都是用工作之余的私人时间写的这本书，当时时
间很仓促，我觉得第一版这个水准已经很不错了。
另外我觉得这个题在下一页解释的还是比较清楚的。
以中线二分的时候，已经知道了左右两区间的最小距离，MDist是其中的小者，那么考虑
过中线的pair时就可以排除所有在中线左右MDist之外的所有点，因为他们之间的距离肯
定大于MDist。所以BD可能比CD距离更小，但是BD不可能小于MDist所以可以不予考虑。
这样，每次二分我们只需要考虑中线左右MDist区间的点，对左边MDist内的每个点，在
右边区间最多只可能有6个点距离
直维护一个按y坐标sort的点的list，在中间区域找最小点对就是O(n)的
所以整个算法是O(nlogn)的
不知道我解释清楚了没有。
短，
【在 z***e 的大作中提到】
: 下下来看了看，随便翻了个求2D平面最近两点的问题，没搞懂他说的，如下图:
: 他说用中间那条线分区之后，就只要考虑CD那条线是不是最短？BD/AD/etc.都不必考虑
: ？？
: what意思哦，CD最多只是在X-axis上的距离有可能最短而已，2D距离显然BD可能比CD短，
: 不晓得这是啥高深理论，或者他自己没说清楚？
|
j*****u
发帖数: 1133 | 17 这个题我觉得书里写的没错
programming pearl作者可能没看过，我也没看过
第二种方法code大概类似这样：
bool CanBeRotated(string s1, string s2)
{
return strstr(s1 + s1, s2);
}
strstr只被call了一次，你自己也说了它是O(n)的 (not for worse case)。
另外，多数公司再中国的hiring bar比美国的都要高(原因很明显)。所以你说“如果是
美国的interview，fail掉可能性极大”。同样的candidate在国内恐怕连海选和笔试都
过不了，连interview机会都没有。
【在 z***e 的大作中提到】
: 上面我对其中一个有疑问，马上又翻了里面一个例子。
: 题目是给出string s1和s2，问s2能否通过rotate s1得到，比如abc => cab之类的，书
: 里面的解答如下：
: 显然作者对programming pearl里面如何O(n)来rotate string一无所知，如果是美国这
: 边的Interview，fail掉的可能极大（采用programming pearl的方法，首先找s2[0]在
: s1中的index比如s1[i]，然后尝试从s1[i]来rotate，如果不对，再找下一个i；而不是
: 从s1[0...n]全部来试.
: 这都是小trick，但是最大问题在他的第二种方法“可以用strstr()一次得到结果"----
: 他不知道strstr是O(n)的么？这样两个方法同样都是O(n*n)，哪来什么“提高空间复杂
: 度，降低时间复杂度”？这边面试的话，善良的Interviewer会问他strstr的复杂度是
|
z***e
发帖数: 5393 | 18 嗯，对的，昨晚上发晕了，这个没仔细看。
【在 j*****u 的大作中提到】
: 这个题我觉得书里写的没错
: programming pearl作者可能没看过，我也没看过
: 第二种方法code大概类似这样：
: bool CanBeRotated(string s1, string s2)
: {
: return strstr(s1 + s1, s2);
: }
: strstr只被call了一次，你自己也说了它是O(n)的 (not for worse case)。
: 另外，多数公司再中国的hiring bar比美国的都要高(原因很明显)。所以你说“如果是
: 美国的interview，fail掉可能性极大”。同样的candidate在国内恐怕连海选和笔试都
|
z***e
发帖数: 5393 | 19 多谢。
画了画图，明白他的意思了，6个点是极限的可能，因为比较距离的时候是根据sort后
的Y坐标来，最大可能情况是有3个(Py-m,Py,Py+m) (Py是左边p点的Y,m是min(left,
right)），而每个Y Projection最多可以对应两个在[Px,Px+m]这个区间内的点（再多
就不必考虑了）。
考虑
离肯
sort一
【在 j*****u 的大作中提到】
: 帮作者(我的朋友)说几句，他们基本上都是用工作之余的私人时间写的这本书，当时时
: 间很仓促，我觉得第一版这个水准已经很不错了。
: 另外我觉得这个题在下一页解释的还是比较清楚的。
: 以中线二分的时候，已经知道了左右两区间的最小距离，MDist是其中的小者，那么考虑
: 过中线的pair时就可以排除所有在中线左右MDist之外的所有点，因为他们之间的距离肯
: 定大于MDist。所以BD可能比CD距离更小，但是BD不可能小于MDist所以可以不予考虑。
: 这样，每次二分我们只需要考虑中线左右MDist区间的点，对左边MDist内的每个点，在
: 右边区间最多只可能有6个点距离: 直维护一个按y坐标sort的点的list，在中间区域找最小点对就是O(n)的
: 所以整个算法是O(nlogn)的
|
