k***e
发帖数: 556 | 1 你加了一个checkCircle，对于每个新grey的点再做bfs于已变色的vertices上，看是否
会回到该点。应该是正确的，时间复杂度为O(V^2).
ps,你说下伪码就可以了，我最怕读别人的代码来 ：） |
|
m****n
发帖数: 145 | 2 我来一个汽车design的粗浅解法，大家讨论一下，共同进步。
附件是UML图。下面是Factory中Test方法的C#伪码：
// t should be one of the subclass of class Part
Void Test(Type t)
{
foreach(var car in Cars)
{
foreach(var part in car.Parts)
{
if(part is t)
part.test();
}
}
}
以上程序可以用Linq简化。由于手头没有编译器就不做了。 |
|
z*******y
发帖数: 578 | 3 都是说思路，说说伪码就可以了
面试好象更在乎你的思路
估计到了onsite就得写了，电话不方便让写，就说了思路 |
|
f***g
发帖数: 214 | 4 我看的第三版
1.伪码对于我来说，更容看懂了。比如说对于Binary Search Tree,
第二版表示一个child是，left[x]
第三版表示的是x.left.
2. 再比如赋值在第三版中用=了。判断用==了。
我看到一半。有一些改变，但是不大。手上有哪本就看哪本吧。
不过AMAZON上，第三版还便宜些。 |
|
s*******t
发帖数: 248 | 5 谢谢分享你的经验！
关于第3部分，编程的基础练习，有没有比较好的书或网站来辅佐一下？
另外，你所推荐的书是否都要看英文版的比较好，担心效率上可能会有一些折扣。
就不多说了。可能有人觉得，我天天写C++写几年了，还用看primer吗。我觉得这个就
仁者见仁了，看你对语言到底有多熟了，看你到底有多少信心了。至少我觉得看primer
之前我也会写code，但是看了几遍后，写code信心增加了很多，不用有诸如用法语法等
方面的担忧。
好应该是默认要求了吧，这个就像是你招一个学物理的人要求他量子力学学扎实一样...
边练习把所有的数据结构写一遍，把所有的不是特别复杂的算法写一遍，不要看书上的
伪码，自己在白板上画画草图然后看着写。要写完整的，可以运行的code，写完后想想
如何测试，一般刚开始练的时候多半是bug频出的，尽量多找找bug，多反思一下吸取教
训。btw，有的公司，比如微软，dev懂得一些测试的知识(黑盒白盒,stress,load,
equivanlenc partition, spec-driven testing等等等)肯定是有加分的，了解一些常
见的错误/bug也利于你避免 |
|
r****o
发帖数: 1950 | 6 赞！
就不多说了。可能有人觉得，我天天写C++写几年了，还用看primer吗。我觉得这个就
仁者见仁了，看你对语言到底有多熟了，看你到底有多少信心了。至少我觉得看primer
之前我也会写code，但是看了
好应该是默认要求了吧，这个就像是你招一个学物理的人要求他量子力学学扎实一样...
边练习把所有的数据结构写一遍，把所有的不是特别复杂的算法写一遍，不要看书上的
伪码，自己在白板上画画草图然后看着写。要写完整的，可以运行的code，写完后想想
如何测试，一般刚开始练的
高的关键。多想想有没有没考虑完善的情况，有没有bug，有没有很冗余的地方，有没
有能节省一些空间时间的地方，有没有可以优化code看上去更简洁干净，比如若干个if
else，能不能想办法找个等
便你。我想重复说一点我以前说过的话，就是多思考。一个题目你做出来了，不代表你
做对了；你做对了，不代表你做的最优；你做的最优了，不代表你coding完美；你
coding完美了，不代表你速度 |
|
o***e
发帖数: 497 | 7 感谢总结，觉得好夸张啊，楼主一共花了多少时间准备啊？感觉如果是RA或者TA的估计
不会有太多空闲时间啊
就不多说了。可能有人觉得，我天天写C++写几年了，还用看primer吗。我觉得这个就
仁者见仁了，看你对语言到底有多熟了，看你到底有多少信心了。至少我觉得看primer
之前我也会写code，但是看了
好应该是默认要求了吧，这个就像是你招一个学物理的人要求他量子力学学扎实一样...
边练习把所有的数据结构写一遍，把所有的不是特别复杂的算法写一遍，不要看书上的
伪码，自己在白板上画画草图然后看着写。要写完整的，可以运行的code，写完后想想
如何测试，一般刚开始练的
高的关键。多想想有没有没考虑完善的情况，有没有bug，有没有很冗余的地方，有没
有能节省一些空间时间的地方，有没有可以优化code看上去更简洁干净，比如若干个if
else，能不能想办法找个等
便你。我想重复说一点我以前说过的话，就是多思考。一个题目你做出来了，不代表你
做对了；你做对了，不代表你做的最优；你做的最优了，不代表你coding完美；你
coding完美了，不代表你速度 |
|
q*****n
发帖数: 311 | 8 Thanks for sharing!
就不多说了。可能有人觉得，我天天写C++写几年了，还用看primer吗。我觉得这个就
仁者见仁了，看你对语言到底有多熟了，看你到底有多少信心了。至少我觉得看primer
之前我也会写code，但是看了
好应该是默认要求了吧，这个就像是你招一个学物理的人要求他量子力学学扎实一样...
边练习把所有的数据结构写一遍，把所有的不是特别复杂的算法写一遍，不要看书上的
伪码，自己在白板上画画草图然后看着写。要写完整的，可以运行的code，写完后想想
如何测试，一般刚开始练的
高的关键。多想想有没有没考虑完善的情况，有没有bug，有没有很冗余的地方，有没
有能节省一些空间时间的地方，有没有可以优化code看上去更简洁干净，比如若干个if
else，能不能想办法找个等
便你。我想重复说一点我以前说过的话，就是多思考。一个题目你做出来了，不代表你
做对了；你做对了，不代表你做的最优；你做的最优了，不代表你coding完美；你
coding完美了，不代表你速度 |
|
n**h
发帖数: 237 | 9 好贴！赞！
就不多说了。可能有人觉得，我
天天写C++写几年了，还用看primer吗。我觉得这个就仁者见仁了，看你对语言到底有
多熟了，看你到底有多少信心
了。至少我觉得看primer之前我也会写code，但是看了几遍后，写code信心增加了很多
，不用有诸如用法语法等方面
的担忧。
好应该是默认要求了吧，这个就
像是你招一个学物理的人要求他量子力学学扎实一样...
边练习把所有的数据结构写一
遍，把所有的不是特别复杂的算法写一遍，不要看书上的伪码，自己在白板上画画草图
然后看着写。要写完整的，可以
运行的code，写完后想想如何测试，一般刚开始练的时候多半是bug频出的，尽量多找
找bug，多反思一下吸取教训。
btw，有的公司，比如微软，dev懂得一些测试的知识(黑盒白盒,stress,load,
equivanlenc partition, spec-driven
testing等等等)肯定是有加分的，了解一些常见的错误/bug也利于你避免犯这些错误。
高的关键。多想想有没有没考虑
完善的情况，有没有bug，有没有很冗余的地方，有没有能节省一些空间时间的地方，
有没有可以优化c |
|
s**********o
发帖数: 105 | 10 赞极
就不多说了。可能有人觉得，我天天写C++写几年了，还用看primer吗。我觉得这个就
仁者见仁了，看你对语言到底有多熟了，看你到底有多少信心了。至少我觉得看primer
之前我也会写code，但是看了几遍后，写code信心增加了很多，不用有诸如用法语法等
方面的担忧。
好应该是默认要求了吧，这个就像是你招一个学物理的人要求他量子力学学扎实一样...
边练习把所有的数据结构写一遍，把所有的不是特别复杂的算法写一遍，不要看书上的
伪码，自己在白板上画画草图然后看着写。要写完整的，可以运行的code，写完后想想
如何测试，一般刚开始练的时候多半是bug频出的，尽量多找找bug，多反思一下吸取教
训。btw，有的公司，比如微软，dev懂得一些测试的知识(黑盒白盒,stress,load,
equivanlenc partition, spec-driven testing等等等)肯定是有加分的，了解一些常
见的错误/bug也利于你避免犯这些错误。
高的关键。多想想有没有没考虑完善的情况，有没有bug，有没有很冗余的地方，有没
有能节省一些空间时间的地方，有没有可以优化code看上去更简 |
|
s**********o
发帖数: 105 | 11 把你前前后后发的帖子都大致看了一下
非常佩服
非常受鼓舞
上来冒个泡
就不多说了。可能有人觉得，我天天写C++写几年了，还用看primer吗。我觉得这个就
仁者见仁了，看你对语言到底有多熟了，看你到底有多少信心了。至少我觉得看primer
之前我也会写code，但是看了几遍后，写code信心增加了很多，不用有诸如用法语法等
方面的担忧。
好应该是默认要求了吧，这个就像是你招一个学物理的人要求他量子力学学扎实一样...
边练习把所有的数据结构写一遍，把所有的不是特别复杂的算法写一遍，不要看书上的
伪码，自己在白板上画画草图然后看着写。要写完整的，可以运行的code，写完后想想
如何测试，一般刚开始练的时候多半是bug频出的，尽量多找找bug，多反思一下吸取教
训。btw，有的公司，比如微软，dev懂得一些测试的知识(黑盒白盒,stress,load,
equivanlenc partition, spec-driven testing等等等)肯定是有加分的，了解一些常
见的错误/bug也利于你避免犯这些错误。
高的关键。多想想有没有没考虑完善的情况，有没有bug，有没有很冗余的地方，有 |
|
o**********t
发帖数: 406 | 12 不对啊，你把伪码在纸上划划就知道了。
数组移位是可以 O(N) 的，不管移多远。
但是，partition 在哪里，几个 partition 是由负数的个数决定的。
也就是说：
1,2,3,4,5, -1 只需要分区一次，移位一次。
1,-2,3,-4,5,6 需要分区 2 次，移位 2 次。
1,-2,3,-4, 5, -6 需要分区 3 次，移位 3 次。
总的来说还是 O(N*K) k 是负数的个数。综合一下，还是 O(n*n)，不是线性的操作。
这个问题其实很简单。可以反证，如果能实现，就意味着 merge sort 不需要额外空间
--- stable sort, O(N*LogN) time, O(1) space ...可以发论文啦！ |
|
o**********t
发帖数: 406 | 13 你先把思路说说，写写伪码，算算复杂度。
比上来就扔出大块 code 强。 |
|
h*****g
发帖数: 312 | 14 请问各位大牛
coding 时对方会指定你使用某种语言吗？可不可以自己选？（Java or C++）或者 直
接写伪码？
十分感谢！！ |
|
c********t
发帖数: 1756 | 15 啥语言面试的人不关心。逻辑清晰，语法正确就行。伪码估计要问一下面试官，我写的
时候连typo都让我改好。 |
|
d**e
发帖数: 6098 | 16 为什么要用笨法子呢？
brute force应该没问题啊。我没具体验证，我想大概应该是这样，
从string_1的第一个char开始循环，比如index是i，和string_2的
第一个char开始比较，index是j，遇到相同，侧两个string的index
都增一，否则看是否得到最长的的substring，然后string_1的index
复位回i，j侧增一，直到j=length(string_2)，然后到下一热循环(i+1)
下面为伪码
int len1 = length(string_1)
int len2 = length(string_2)
int max_len = 0
int left_idx = -1
int right_idx = -1
for i = 0 to len1 - 1
loop
k = i
tmp_max_len = 0
for(j = 0; j < len2 - 1; )
if string_1[k] == string_2[j]
then
k++
j++
|
|
t******e
发帖数: 1293 | 17 没有看Programming Pearls了吧，看了你就知道了
不过我也有点怀疑，按道理来说发表binary search的那篇paper
里面就会有接近实际代码的伪码的了
里面的证明要verify这个code的正确性，就需要用到啥循环的
pre-condition, post-condition，和loop invariant的 |
|
s*x
发帖数: 3328 | 18 恭喜.
BTW:sliding window 的那个题目,前面不是有人贴链接了,楼上还有没看懂的? 用线性
结构,单纯的链表或者数组肯定不行,必须用到树形结构.堆可以.问题是这里有两个值,
一个是数组的位置,要保存好更新窗口,一个是数组元素的值,这个好取最大最小.所以就
是一个优先队列了,存的元素是数组元素下标,更新的时候将下标和当前窗口边界比较,
超出的就删除;而优先级用数组元素的值来表示.同时取最大和最小,所以一共需要俩优
先队列,伪码大概是这个样子:
for i from 1 to k 窗口的大小
add i with priority v[i] into PQ1, PQ2
max[i],min[i] 分别从 PQ1, PQ2 根的优先级得到
//上面这步是初始化,当然还要考虑窗口比数组还大的特例
// PQ1, PQ2 一个是按顺序, 一个是按逆序来的, 分别得到最大最小值
for i from k+1 to n 数组长度, 1-based index
add i with priority v[i] into PQ1, PQ2
while PQ1 根的值超出窗... 阅读全帖 |
|
l******x
发帖数: 225 | 19 总结一下吧，大家基本都找到了答案，还有问题的有：
国女数路径的题，原来大家都assume我不会直接算嘛。。我倒是assume大家都会的。。
问的就是这样有什么问题，怎么解决。
三男转矩阵的题，ls有人给出了wiki的转置的链接，其实我觉得转置和旋转，难度上是
一样的。虽然我之前不知道这个转置算法，但是我感觉提前知道跟不知道差别也不太大，
该纠结还是纠结。首先是wiki上算转换坐标的公式，也太fancy了吧，直接死算不行吗。
而且，wiki上这个算法，并没有解决我的纠结。这个算法，还真不是像2*n的那样是个
有个性的漂亮解法，它的基本想法不就是straightforward的转圈吗？那个转圈，它那里
伪码一写很轻松，真的写代码，到底怎么转？n*n好转，是因为永远在同一个border上
转，一个border上转的不会hurt到其他的，所以不用记录谁转过谁没转过。这m*n一转
起来全乱了，一个不是圈的圈转完了，如果不记录谁转过谁没转过，下一个从哪转起谁
知道？wiki上的做法，也是用log n的空间记录一下谁转过，这个严格来说算 in place
吗？反正，这题的名字就叫纠结！
btw, 原... 阅读全帖 |
|
i**c
发帖数: 26 | 20 这个问题已经讨论过很多次了,其实就是和尚多稀粥少,公司拿这个来卡人.
有的题是ACM的决赛hard题,给你半个钟头做.你要是实现没见过,估计连伪码都写不出来 |
|
g*********s
发帖数: 1782 | 21 发信人: uglyduke (一苇居士), 信区: JobHunting
标 题: 绝对精华，offer＋面经
发信站: BBS 未名空间站 (Wed Mar 30 21:34:37 2011, 美东)
Amazon的offer，95k+15k
基本情况：
国内大学cs本科，杭州小公司SDE工作1年半，L1来了公司美国总部作PM。工作不到2年
离职开始找工作。L1签证到今年2月就过期了，算是黑着身份找的，挺不容易。
google电面。大我10多届的学长打来，问题范围比较广，但内容基础，考察面：
1 基本数据结构，如array和list
2 十六进制的基本题
3 多线程，线程与进程的区别，windows下的多线程编程基础，livelock技术，读写者
4 给了几个数比大小
5 c++的基本知识，多态，vptable，引用，常，构造析构，static的用法等等小东西
6 浏览器里输入URL后发生什么
on site在santa monica
1 behavior+60秒点击最多的问题，coding。
2 coding，实现一个DFS，不过缺一些条件。
3 大规模问题，有点特殊性的字串排序... 阅读全帖 |
|
r******n
发帖数: 170 | 22 我也理解成一个两重循环了
getLinkMovie(Actor a, Actor b)
{
foreach m in a.movieList
{
foreach (act in m.actorList)
{
if (act==b)
result.push_back(m)
}
}
}
假如按照graph来dfs/bfs来写，careercup上的写法似乎都没有edge的概念。这里得保
持edge的list,而且还可能有多条路径，是不是得递归的写？那个牛人能给个伪码讲讲
吗？
另外觉得这题，是不是跟在SNS里找出两个人的朋友连接关系是一样的吧？
似乎还没想到比较好的写法。 |
|
|
|
m*****n
发帖数: 171 | 25 20道选择题，考他们自己家那个奇怪的语言。然后5道programing的题目，可以用任何
一种语言，或者伪码。 |
|
n*******w
发帖数: 687 | 26 这个复杂度多少?
其实写个循环就能解决上下层dependent的关系。每一次循环都相当于dp一次。伪码如
下。
modified = true；
while(modified){
modified = false；
从start point开始由内向外一圈一圈计算每个节点的最小cost。每个节点要考虑8
个方向的相邻节点。如果有更短路径，modified设为true，更新cost。
}
dependent的原因是因为下一层如果有更短的路径了，上一层不知道下一层的结果。
但是在下一个循环的时候上层可以得到下层的计算结果。 |
|
|
r******n
发帖数: 170 | 28 一直没弄请怎么解这题，正好从topcoder tutorial上看到有相关讲解：
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=
不过还是没太清楚，这个伪码里的J=1是怎么选出来的？是直接选结束时间最早的那个
事件吗？记得版上似乎有讨论过，不过没翻出来。哪位知道在哪里吗？
Let N denote the number of activities and
{I} the activity I ( 1 <= I <= N )
For each {I}, consider S[I] and F[I] its starting and finishing time
Sort the activities in the increasing order of their finishing time
- that is, for every I < J we must have F [I] <= F [J]
// A denotes the set of the activities that will be... 阅读全帖 |
|
n*******w
发帖数: 687 | 29 用递归很简洁的。
如果a[i]是operator，从a[i+1]开始递归print左子树并返回左子树的最后一个元素的
index。然后从a[index+1]开始print右子树，最后打印operator。
伪码
print（arr[], index）{
if(arr[index] is operator){
i = print(arr, index+1);
i = print(arr, i+1);
print(arr[index]);
return i;
}
else{
print(arr[index]);
return index;
}
} |
|
n*******w
发帖数: 687 | 30 来自主题: JobHunting版 - 问个算法题 那个伪码有一些bug吧。改好了能比较准确的说具体的问题。不然不是完全了解怎么
work。 |
|
n*******w
发帖数: 687 | 31 能写个伪码么？
我记得这个解法有严重的bug。
far
far
maximal |
|
s******n
发帖数: 3946 | 32 写计算器代码少于100行不太可能，只能大概写个伪码。
找数组random这种东西作为考试真没意思，看过的人马上知道怎么做，没看过的人能当
场30分钟内想的出来的太少了。至少得有点变化。 |
|
q****x
发帖数: 7404 | 33 写了个递归的完整版，120行，用wiki上的例子测试通过，共用一个多小时。
面试肯定要写伪码。其实递归函数本身也就15行。 |
|
q****x
发帖数: 7404 | 34 搞理论的只会写伪码可以理解。如果搞系统的也是如此，显然是理论与实践脱节。
编程是基本功。CS很多研究想法要做实现验证，编程又好又快的人效率高很多。
程序当然是越快越好。可读性高也不等于篇幅长。说白了，写程序和写文章差不多，高
手可以做到简洁高效。 |
|
b******v
发帖数: 1493 | 35 submit answer之后可以看到官方解答，里面有伪码
也许它的论坛里还有别人贴的代码吧 |
|
|
|
w*****e
发帖数: 28 | 38 这道题是否可以用sampling来做？
如果采样m个样本，m本身足够大，又足够放到内存里，应该可以拿m个样本的uniq
count来估算整个stream input的uniq count
这样就转化成了经典题目怎么在stream data里均匀采样m个样本
伪码：
int array[m];
int cur_cnt = 0;
while read num {
if (cur_cnt < m) {
array[cur_cnt++] = num;
} else {
int hash_code = rund() % N;
if (hash_code < m) array[hash_code] = num;
}
}
//count uniq number using hashmap or sth.... |
|
d*******d
发帖数: 2050 | 39 sigh,怎么会这样。好吧，详细说一下面试这些intern的过程吧。
这是个algorithm & coding section（也就是说还有其他section).
2个coding题，题目是公司指定的，顺序问法面试官自己掌握。
1个小时。
最开始5分钟，自我介绍，说说你上过的课，说说你最喜欢的课程（有一半人说的是算
法和数据结构），做过的project等等。
然后5-10分钟，问做过的project，看看是不是真参与了，弄懂了。到目前为止，大多
还不错，个别人很腼腆，问一句答一句。
然后10-15分钟，第一个coding题，10到20行。很简单，没有任何tricky,考察是否能用
简历上claim会的语言编程。版上的混2个星期都该没问题。但是，目前为止，没见过一
个bug free的。一半以上的人，完全不考虑任何edge case。
这个时候，因该已经过去大约25分钟了。
第二个coding题，也是版上反复出现过的经典入门级题目，是个人都该会。要用到
recursion。coding 10-15行。
为了引导candiate的思路到recursion上来，我会花10分钟问问他们学过的... 阅读全帖 |
|
s****J
发帖数: 161 | 40 完了，我一直以为可以写伪码。但是电话面试的时候说不会编程没关系，到时候会有几
个月的时间培训啥的。我申请的是SD，给我发配到TS了。 |
|
s****J
发帖数: 161 | 41 你电话打回去没，是去onsite么？我考得不行，不过确实可以用伪码，我后来时间不够
用了一些。有一题整个想错了。都是我没有见过的题 |
|
r*****e
发帖数: 146 | 42 谢谢分享！lz好运！！
“2. 设计一个检索系统。讨论了如果有unicode怎么办，怎么优化，数据量大怎么办，检
索表存在哪里。写了一些code。”
第二题，到底应该如何处理unicode？检索表存在多个地方？不太明白这样的设计题，
需要写什么样的code.只是伪码？还是具体功能的实现？ 谢谢！ |
|
s*******y
发帖数: 44 | 43 题目中说是set，我不放心问了是否允许重复，说允许。hash的办法可以处理这个重复
的情况。否则的话可以排序后用线性时间先去重，不影响最后的时间复杂度。
他面试还有个特点，在你写code的时候，不停地发问你这里好像不对吧，是不是应该这
样那样，思路很容易被打乱。也许边写边解释是一个应付面试官的办法，或者先写注释
伪码？这个实际中该怎么对付比较好？ |
|
r********g
发帖数: 14 | 44
string 遍历一遍即可
伪码：
for each char in string str
if char in hashtable
change the value of key char in hashtable( key char value 2)
next char
else
linkedlist.tail->next.value= char
tail = tail->next;
add char to hashtable( key char value 1)
end of loop for string // just one time
//now let us deal with the linkedlist
while( header != null){
if header value in hashtable is 2 ( hashtable.get(header)==2) // header is
duplicate
header = header->next;
else return header->value // first non-duplicate ch... 阅读全帖 |
|
l***n
发帖数: 89 | 45 嗯，很有帮助。谢谢。
不管OO是不是未来的方向，面试的时候，还是挺容易遇到这样子的问题的。
贡献一个onsite问到的题目吧。
让设计一个游戏，animal game，可以参看这个链接 http://www.animalgame.com/
就是让用户心里想一个动物，现在系统什么都不知道，可能只知道一种动物，tiger，
然后它会问是tiger么？如果不是，那这次猜测就fail，系统就问你，请你说出一个你
想的的动物和tiger的区别feature。而且告诉它你的动物是什么。这样他就学习到一个
新知识。
比如你想的是兔子，告诉他feature是long ear。
那么重新开始游戏，你重新想一种动物，然后系统开始发问 它会问是long ear么？ 你
说不是，他会问，是tiger么？不是。那你就再提供新的feature和新的动物信息。
类似一个decision tree的结构，让你设计主要的类，方法，以及这些方法的逻辑，伪
码ok。 |
|
l***n
发帖数: 89 | 46 嗯，很有帮助。谢谢。
不管OO是不是未来的方向，面试的时候，还是挺容易遇到这样子的问题的。
贡献一个onsite问到的题目吧。
让设计一个游戏，animal game，可以参看这个链接 http://www.animalgame.com/
就是让用户心里想一个动物，现在系统什么都不知道，可能只知道一种动物，tiger，
然后它会问是tiger么？如果不是，那这次猜测就fail，系统就问你，请你说出一个你
想的的动物和tiger的区别feature。而且告诉它你的动物是什么。这样他就学习到一个
新知识。
比如你想的是兔子，告诉他feature是long ear。
那么重新开始游戏，你重新想一种动物，然后系统开始发问 它会问是long ear么？ 你
说不是，他会问，是tiger么？不是。那你就再提供新的feature和新的动物信息。
类似一个decision tree的结构，让你设计主要的类，方法，以及这些方法的逻辑，伪
码ok。 |
|
z*******3
发帖数: 13709 | 47 就是原题，给一个只能产生0和1的rand()
那么要求做出一个能产生0到n-1的随机函数
看了一堆解法，突然想到一个暴力解法
效率比较低，但是应该从理论上说是没有错的
首先把0到n-1改成1到n
几率是一样的
其次，用给好的rand()生成一串n位的数组
要求，这串数组里面只能有一个1，其它都是0
如果出现其它情况，重做这一步
拿到这一串数组之后，计算那一个1出现的位置
这个1可能出现在第一位也可能出现在最后一位
也就是[1,n]之间的自然数
最后再把得到的数字减1
效率比较低，但是这个伪码实现起来很容易，也便于阅读 |
|
z*******3
发帖数: 13709 | 48 第四版一堆错误
很多代码都无法执行，完全就是一个伪码 |
|
B**********2
发帖数: 923 | 49 首先感谢microleo，给我推荐
电话两轮，一个聊天，一个简单的电面。
Coding Test 一轮，题目为Spread Sheet，大家可以自行Google
得到Positive Feedback
5月8号 On site
分别两个工程师两个项目经理
鉴于每个人多聊了一会我以前的Project，所以每个人问1到3个问题不等。
----------------- 割割割割割割割割 -----------------------------
Q: Spread Sheet 如果太大，不能整个Load进内存来处理。但是可以有多个
机器按照一定的信息读本机文件。假设Spread Sheet每个连通片的计算量
一个机器能够处理
A: Virtually的建立无向连通图，用DFS获得连通片，每个连通片交给一个主机来计算
----------------- 割割割割割割割割 -----------------------------
Q: 给一个森林和已知两个节点，求最近公共祖先，如果没有，返回NULL
A: 我说啥语言没有什么区别，先上伪码，MIT Press Algorithm ... 阅读全帖 |
|
n****r
发帖数: 120 | 50 Q: 给一个森林和已知两个节点，求最近公共祖先，如果没有，返回NULL
A: 我说啥语言没有什么区别，先上伪码，MIT Press Algorithm notation
CommonAncestor(A, B)
1. A' <- A
2. B' <- B
3. a <- 0
4. b <- 0
5. while(A') do
6. a <- a + 1
7. A' <- A'.parent
8. while(B') do
9. b <- b + 1
10. B' <- B'.parent
11. d <- a - b
12. for i <- 1 to |d|
13. if (a > b) A <- A.parent
14. else B <- B.parnet
15. while ( A.parnet and B.parent and A.parent != B.parent )
16. A <- A.parent
17. B <- B.parent
18. return A.parent
在向上遍历到根的时候，难道不需要判断A所在... 阅读全帖 |
|
