s***c
发帖数: 50 | 1 关于"求两个演员链接"的题，楼主的答案似乎有问题。
我的思路也是用DFS，然后用一个map()来代表predecessor关系。
Set<> actor_set;
Set<> movie_set;
Map< actor, pair > map; //predecessor map
findActorLink(Actor a, Actor b)
{
int flag = 0;
if (a==b) return 1;
for each movie m in getMoviesOfActor(a)
{
if movie_set.contains(m) continue;
movie_set.add(m);
for each actor x in getActorsOfMovie(m)
{
if( actor_set.contains(x) ) continue;
actor_set.add(x);
map... 阅读全帖 |
|
S*****e
发帖数: 229 | 2 多谢分享
的说吧。废话不说，直接上题：
的地方。有一道程序改错题，程序大概是替换一个字符串里面的pattern，不知道是谁
写的，不是很organized，估计是其他面试的同学的程序，我看了半天虽然觉的code写
得很别扭，但也没找出什么大错，面试官看我卡住了，就说我们继续吧。好在后来的题
都答得比较顺利。
session，项目中有没有多线程，怎么实现。
是cyclic，所以一开始我理解成{123456456}，后来email问了才明白题意）。
的地方。因为是常见题，很快完成，run了一下没什么问题就发过去了。 |
|
g**********y
发帖数: 14569 | 3 1, 9, 3, 0
相当于 3 -> 0 -> 1 - > 9
按题意这是一个cycle，见原题: 出界的也算cycle。 |
|
P*********r
发帖数: 487 | 4 text justification的题网上搜搜就有了，看了就明白你到底挂在哪里了。
sql那个题varchar不是重点，重点是人家想看你怎么设计table怎么join。我觉得
你没有特别理解题意，而且确实也还不是很ready for这种interview。这个事情
我觉得更大程度上是给你做phone screening的人不太负责任，不应该让这样的
事情发生。一般公司做了这样的事自己也不会很好受的，我们公司就曾经跟我们
讲过多次，前面screening一定要keep bar high，不然如果发生terminate onsite
的事情大家都很难受。但是既然事情都过去了就让它过去，不要再想了，更重要
的是总结经验，好好复习准备下一个面试。前面有人说过，象L这种刚上市的公司
现在需要进去的人马上能干活，会要求更高一些，如果觉得自己经验不是太足的
话，试试已经成熟的大公司，可能更适合一些。 |
|
g**********y
发帖数: 14569 | 5 1. 你有一种语言的dictionary,你有一大串string,没有delimit,你如何interpret成字
典中的字呢？
http://www.mitbbs.com/article/JobHunting/31488093_3.html
这个刚讨论过，就是把一个句子分拆成单词，既可以用Trie, 也可以DP。去search
ihasleetcode的帖子。
2. 给你一个字典array of strings (you may preprocess it if necessary)
任意一个单词，求最小的edit distance
一个单位的distance定义为:
a. replace a letter
b. delete a letter
c. insert a letter (also at any position)
这个我不知道有什么高效的办法，我就brutal force: 反复调用minimumEditDistance(
String a, String b)，求最小值。
求最小值的时候可以加点智能，比如已知现在最小值为k, 那么word.length() +/- k... 阅读全帖 |
|
m**q
发帖数: 189 | 6
1. 你有一种语言的dictionary,你有一大串string,没有delimit,你如何interpret成字
典中的字呢？
http://www.mitbbs.com/article/JobHunting/31488093_3.html
这个刚讨论过，就是把一个句子分拆成单词，既可以用Trie, 也可以DP。去search
ihasleetcode的帖子。
=> 收到，多谢啦
应该是trie + backtracking 或者 trie + DP吧
2. 给你一个字典array of strings (you may preprocess it if necessary)
任意一个单词，求最小的edit distance
一个单位的distance定义为:
a. replace a letter
b. delete a letter
c. insert a letter (also at any position)
这个我不知道有什么高效的办法，我就brutal force: 反复调用minimumEditDistance(
String a, String b)，求最小值。
... 阅读全帖 |
|
g**********y
发帖数: 14569 | 7 1. 你有一种语言的dictionary,你有一大串string,没有delimit,你如何interpret成字
典中的字呢？
http://www.mitbbs.com/article/JobHunting/31488093_3.html
这个刚讨论过，就是把一个句子分拆成单词，既可以用Trie, 也可以DP。去search
ihasleetcode的帖子。
2. 给你一个字典array of strings (you may preprocess it if necessary)
任意一个单词，求最小的edit distance
一个单位的distance定义为:
a. replace a letter
b. delete a letter
c. insert a letter (also at any position)
这个我不知道有什么高效的办法，我就brutal force: 反复调用minimumEditDistance(
String a, String b)，求最小值。
求最小值的时候可以加点智能，比如已知现在最小值为k, 那么word.length() +/- k... 阅读全帖 |
|
m**q
发帖数: 189 | 8
1. 你有一种语言的dictionary,你有一大串string,没有delimit,你如何interpret成字
典中的字呢？
http://www.mitbbs.com/article/JobHunting/31488093_3.html
这个刚讨论过，就是把一个句子分拆成单词，既可以用Trie, 也可以DP。去search
ihasleetcode的帖子。
=> 收到，多谢啦
应该是trie + backtracking 或者 trie + DP吧
2. 给你一个字典array of strings (you may preprocess it if necessary)
任意一个单词，求最小的edit distance
一个单位的distance定义为:
a. replace a letter
b. delete a letter
c. insert a letter (also at any position)
这个我不知道有什么高效的办法，我就brutal force: 反复调用minimumEditDistance(
String a, String b)，求最小值。
... 阅读全帖 |
|
|
m****t
发帖数: 555 | 10 最后一道题感觉不难，就是根据字符个数先算出矩阵宽度，再把字符映射到矩阵对应位
置。
根据题意，1234567890应该是这样的
1 3 6
2 5 9
4 8
7 0
假设矩阵行数为ROW, 处理过的字符串长N,存放在A[0..N-1].
则矩阵宽度为COL= ceiling of N/ROW;
int pos=0;
int x, y;
int xb=0;
for (c=0; c<= ROW+COL-2; c++) {
x = xb;
y = c-x;
while (x >= 0 && y <= COL-1 && pos
B[x][y] = A[pos];
pos++;
x--;
y++;
}
if (xb < ROW-1 ) xb++;
if (pos>=N) break;
}
output B[i][j]; |
|
c*****m
发帖数: 315 | 11 从题意来看，这个题肯定是假设KEY 的范围很有限，但是数很多， 也就是N>>K， 所以
ASYMPTOTICALLY, 复杂度应该是O(N)。
我猜解题的关键是用一个好的数据结构做BUCKET 来计数，可以COMBINE HASHMAP 和
LINKED LIST。稍后贴上我的代码。 |
|
d*******l
发帖数: 338 | 12 客观上单个字符也算palindrome的。不过我理解题目的意思应该是说，如果那个byte流
在某个时刻构成回文数，那题意保证该回文数一定长度是偶数。 |
|
d*******l
发帖数: 338 | 13 我没太明白，每次新来一个数，最多只跟栈顶比较一次，然后不是pop就是push，整体
不就是O(n)的吗？还是题意理解的不一样？ |
|
B*******1
发帖数: 2454 | 14 是的，但是一开始的时候给出一堆电话号码，然后他们全部都在取出那里，但是未取出
是空的
然后用户call GiveMeANumber（） 去申请一个号码，但是你的未取出hashtable还是空
的，你怎么找一个没有人的用户呢？ 难道我题意理解错了。 |
|
B*******1
发帖数: 2454 | 15 是的，但是一开始的时候给出一堆电话号码，然后他们全部都在取出那里，但是未取出
是空的
然后用户call GiveMeANumber（） 去申请一个号码，但是你的未取出hashtable还是空
的，你怎么找一个没有人的用户呢？ 难道我题意理解错了。 |
|
d*******l
发帖数: 338 | 16 我就是顺着楼上那么一说。。如果题意真的是那样，这些实现细节就影响不大了 |
|
d*******l
发帖数: 338 | 17 我就是顺着楼上那么一说。。如果题意真的是那样，这些实现细节就影响不大了 |
|
n******n
发帖数: 49 | 18 我对题意的理解是：
比如
the list of words with the same size: abc, def, ghi
the big string: xxxdefghiabcxxxxxx
应该返回3，因为defghiabc是一个(abc, def, ghi)的permutation, 它在big string中
起始index是3. |
|
n******n
发帖数: 49 | 19 我对题意的理解是：
比如
the list of words with the same size: abc, def, ghi
the big string: xxxdefghiabcxxxxxx
应该返回3，因为defghiabc是一个(abc, def, ghi)的permutation, 它在big string中
起始index是3. |
|
|
r**********1
发帖数: 13 | 21 对的，
偶题意理解错了，还以为可以从几个字母开始往上涨，原来是需要从1个字母开始往上涨 |
|
r*******g
发帖数: 1335 | 22 还是没看看懂题
题目是说，要求生成的是一个string，这个string是由原始若干string构成，并且不能
break原始的string，也就是说，原始的string假设是ABD,你不能只把AB选出来构成生
成的string，对不对？
这样的话，不但要求起始letter构成了单增，而且每个string内部也必须单增。
不知道我理解题意对不对。 |
|
b**********e
发帖数: 100 | 23 找工作结束，onsite面过G，F，M，最后拿到G的offer，碰上的题大多数都是老题，而
且不难。我碰上的有点难的，而且没见过的题，我在最后列出来。
我总体的感觉是准备题只是一个基础，大家还应该注意沟通和表达能力。面试官如果问
我们会的题，争取做到communication方面不会扣分。比如说，面试官给你一个题，多
数情况他们会故意把题说的比较含糊，然后让你主动来问问题clarify，而我们有的时
候会主观的加一些假设，来向我们会的问题上靠。
等把面试官的题意弄清楚之后，我们一般会选一种数据结构来解这个问题，但是面试官
如果问你为什么选这个数据结构，我们应该解释清楚，或者面试官会暗示你这个数据结
构他认为不对，我们应该能够随机应变，说出他想要的。
数据结构和算法确定了以后，写code应该是bug free的，有bug会make a big
difference
写完code，最好在板上演示一个简单的例子，这样也能帮助我们找到bug。
最后一般都会问时间空间复杂度，我觉得最好先跟面试观clarify一下N代表什么。我是
吃过这方面亏的，我说O(N),面试官说N square，结果后来发... 阅读全帖 |
|
r*******g
发帖数: 1335 | 24 我仔细想了下，对题意有点不理解了,到底上面的线段是不是就是盖子？如果没有盖子
，那液体可以到处流动，这个题就很奇怪了。
假设选的是如下的线段
(1,3),(2,2),(3,3)，那么容积是5，是不是？
再比如
(1,3),(2,2),(3,0.5)，左边部分的水会往下流吗
我倾向于上面的线段就是盖子,这样的话，每相邻两条线段的面积，就可以等效于一个
直方图，然后，回到那个经典题目。 |
|
H***e
发帖数: 476 | 25 祝福！
第二题你怎么做的？ circular array?
以秒为最小单位 （不考虑半秒之类的），array共24*60*60格子，各keep一个window为
上一分钟，一小时，一天，，并且有三个计数，每次有新一秒的数据来，就update三个
计数为 current_total+#of new events-#of_out_of_boundary_ones.
我题意理解对吗？ |
|
r****t
发帖数: 10904 | 26 I like the way you describe the problem. but I doubt the solution is legal.
题意我理解的是不能问这样的问题：
is the ship on x at t \in {t!=2} when t=2
在 t=2 我们只能问
is the ship on x at t=2? 这里 x 是可选的。 |
|
S*********r
发帖数: 5693 | 27 【 以下文字转载自 Joke 讨论区 】
发信人: athome (athome), 信区: Joke
标 题: 三个小伙子比赛打手枪，因为他们同时爱上了一个姑娘
发信站: BBS 未名空间站 (Fri Dec 30 14:03:01 2011, 美东)
【1】假设有一个池塘，里面有无穷多的水。现有2个空水壶，容积分别为5升和6升。问
题是如何只用这2个水壶从池塘里取得3升的水。
【2】周雯的妈妈是水泥厂的化验员。一天，周雯来到化验室做作业。做完后想出去玩
。“等等，妈妈还要考你一个题目。”她接着说，“你看这6只做化验
用的玻璃杯，前面3只盛满了水，后面3只是空的。你能只移动1只玻璃杯，就把盛满水
的杯子和空杯子间隔起来吗？”爱动脑筋的周雯是学校里有名的“小机灵&#
8221;，她只想了一会儿就做到了。请你想想看，“小机灵”是怎样做的？
【3】三个小伙子同时爱上了一个姑娘，为了决定他们谁能娶这个姑娘，他们决定用手
枪进行一次决斗。小李的命中率是30％，小黄比他好些，命中率是50％，最出色的枪手
是小林，他从不失误，命中率是100％。由于这个显而易见的事实，为公平起见，他们
决定按这样... 阅读全帖 |
|
f********t
发帖数: 6999 | 28 【 以下文字转载自 Joke 讨论区 】
发信人: athome (athome), 信区: Joke
标 题: 三个小伙子比赛打手枪，因为他们同时爱上了一个姑娘
发信站: BBS 未名空间站 (Fri Dec 30 14:03:01 2011, 美东)
【1】假设有一个池塘，里面有无穷多的水。现有2个空水壶，容积分别为5升和6升。问
题是如何只用这2个水壶从池塘里取得3升的水。
【2】周雯的妈妈是水泥厂的化验员。一天，周雯来到化验室做作业。做完后想出去玩
。“等等，妈妈还要考你一个题目。”她接着说，“你看这6只做化验
用的玻璃杯，前面3只盛满了水，后面3只是空的。你能只移动1只玻璃杯，就把盛满水
的杯子和空杯子间隔起来吗？”爱动脑筋的周雯是学校里有名的“小机灵&#
8221;，她只想了一会儿就做到了。请你想想看，“小机灵”是怎样做的？
【3】三个小伙子同时爱上了一个姑娘，为了决定他们谁能娶这个姑娘，他们决定用手
枪进行一次决斗。小李的命中率是30％，小黄比他好些，命中率是50％，最出色的枪手
是小林... 阅读全帖 |
|
r****t
发帖数: 10904 | 29 cracking coding interview. I copy/paste the question below
4.8
You are given a binary tree in which each node contains a value. Design an
algorithm to print all paths which sum up to that value. Note that it can be
any path in the tree - it does not have to start at the root.
读得气不打一处：does "that value" refer to "a value" in the previous
sentence? If it is, on which node? if that does not matter (why the hell
would it not matter?), would every node contain the same value as "a value"?
看来必须看答案才能明白题... 阅读全帖 |
|
l**********1
发帖数: 415 | 30 今天看到几道a家onsite不太懂，求讨论，求大牛给code
1)写一段代码，给一个字符串，例如"30*(5+10)",输出计算结果。
知道大概是用两个stack，但有好多细节不懂，如怎么只扫描一个这个字符串就把数字
和operator放在两个stack里？还有就是如何在存operator的stack中定义优先级？
2）现在给定一个函数，f(x),x在某值之前是非递减的，在某值之后是非递增的。设计一
个算法快速查找这个值。
知道应该改binary search,但具体的判定array[middle]的条件有什么好的想法？怎么
选择仍哪一半啊？因为array[middle]可能同时大于或小于array[start],array[end]
3)有一个奇怪的linkedlist,除了next pointer还有一个random pointer指向一个随机
的节点。问如何实现clone函数。
这个题貌似很多地方都考，没大看懂题意，是问如何实现linkedlist里的clone函数？
如果是，怎么做是最好呢？ |
|
i******r
发帖数: 793 | 31 这题我也不是很理解
那两个数字里面，哪一个是超车的概率，哪一个是正常的概率，似乎题目没有说明白。
很不喜欢这种靠猜测题意的题目
* |
|
r****t
发帖数: 10904 | 32 来自主题: JobHunting版 - 问道概率题 题意飞镖应该是同分布的 |
|
S**I
发帖数: 15689 | 33 ☆─────────────────────────────────────☆
gzou (gzou) 于 (Thu May 12 02:26:35 2011, 美东) 提到:
马上就要G on site了，
求祝福。
下面是从本版收集到的Google的试题，便于大家查询。
申明：有的附带有解释说明的，也来自于本版或者网络，大家自己看， 不保证真确
http://www.mitbbs.com/article_t1/JobHunting/31847453_0_1.html
本人ECE fresh PhD，背景是电路/EDA，跟G业务基本没什么关系
同学内部推荐的，很简单的一次电面就给了onsite
题都不难，但是自己没把握好机会，出了一些小bug。
总的感觉，出错就是硬伤，宁可从最简单的算法写起，也不能出错。
电面：
1，Skip list， http://en.wikipedia.org/wiki/Skip_list
写code实现struct skip_list * find(struct skip_list *head, int value)
2，sorted array... 阅读全帖 |
|
S**I
发帖数: 15689 | 34 ☆─────────────────────────────────────☆
gzou (gzou) 于 (Thu May 12 02:26:35 2011, 美东) 提到:
马上就要G on site了，
求祝福。
下面是从本版收集到的Google的试题，便于大家查询。
申明：有的附带有解释说明的，也来自于本版或者网络，大家自己看， 不保证真确
http://www.mitbbs.com/article_t1/JobHunting/31847453_0_1.html
本人ECE fresh PhD，背景是电路/EDA，跟G业务基本没什么关系
同学内部推荐的，很简单的一次电面就给了onsite
题都不难，但是自己没把握好机会，出了一些小bug。
总的感觉，出错就是硬伤，宁可从最简单的算法写起，也不能出错。
电面：
1，Skip list， http://en.wikipedia.org/wiki/Skip_list
写code实现struct skip_list * find(struct skip_list *head, int value)
2，sorted array... 阅读全帖 |
|
|
|
i**********e
发帖数: 1145 | 37 你没说清楚题意啊，那个 general tree 里面的 representation 是怎样的？
我也不是很清楚你的题目的意思。。所以就也没继续想了。
难道不是我贴那个连接的思路吗？
不是general tree和binary tree的特殊关系？ |
|
s*******n
发帖数: 97 | 38 找到一张图片里面所有的word 的bounding box |
|
|
|
g**********y
发帖数: 14569 | 41 这是我做模式识别的研究方向。专门有好多牛人做这个。
简单地说，比如一张扫描进去的地图，上面有很多字符，象街道名，山脉，河流。问题
是要把这些字符识别出来，然后跟路/山/河流联系起来，digitize map。为了识别这些
字符，需要把单词提取出来，然后用模式匹配。bounding box就是来计算包含单词的最
小矩阵。简单情况是，字符只要纵向或横向，但实际情况，不仅可以斜着，还可以弯曲
，而且字符可能和图形相交。所以这个bounding box的计算在实际里很复杂。一般的步
骤是先计算图的connected component。然后尝试连接component的中心，形成线，延长
，看是不是包含几个类似大小的component, 里面会采用一些估计和猜测。然后用几何
算bounding box。
现在可能有更好的办法做，但我也没去跟踪过进展。
问这种很无聊。做过的就很清楚，没做过的，面试那点时间，想的方向可能都不对。 |
|
|
g**********y
发帖数: 14569 | 43 不清楚题意，只能存256种颜色是什么意思？有内存限制？
每种颜色有3-byte, 这就足够表示24-bit颜色。 |
|
j*****j
发帖数: 201 | 44 这不是一般的队列，这是双端队列，不合题意吧？
the |
|
i**********e
发帖数: 1145 | 45 这题大家写写看，虽然没什么算法，但是很考基本功。
另外，这是一道很好的面试题。因为题意可以很含糊，但是里边有很多细节需要搞清楚
，设计输入和输出。还有 corner cases 也有，很容易没考虑周全。
题目参考以下链接：
http://www.cs.rpi.edu//academics/courses/fall09/ds/hw/01_text_j
我对题目的理解，简短的述说：
"Text Justification"
Given an array of words and a length L, format the text such that each line
has exactly L characters and is fully (left and right) justified.
You should pack your words in a greedy approach; that is, pack as many words
as you can in each line. Pad extra spaces ' ' when necessary so that ... 阅读全帖 |
|
i**********e
发帖数: 1145 | 46 这题大家写写看，虽然没什么算法，但是很考基本功。
另外，这是一道很好的面试题。因为题意可以很含糊，但是里边有很多细节需要搞清楚
，设计输入和输出。还有 corner cases 也有，很容易没考虑周全。
题目参考以下链接：
http://www.cs.rpi.edu//academics/courses/fall09/ds/hw/01_text_j
我对题目的理解，简短的述说：
"Text Justification"
Given an array of words and a length L, format the text such that each line
has exactly L characters and is fully (left and right) justified.
You should pack your words in a greedy approach; that is, pack as many words
as you can in each line. Pad extra spaces ' ' when necessary so that ... 阅读全帖 |
|
l*****a
发帖数: 14598 | 47 根据题意，实际上可以看成一个有序一维数组。一遍binary search will work
bool contains(int a[][],int index,int target)
{
int y=index%n;
int x=index/n;
return target==a[x][y];
}
bool Search(int a[][],int m,int n,int target)
{
int lo=0;
int hi=m*n-1;
int x,y;
while(lo
{
int mid=lo+(hi-lo)>>1;
if(contains(a,mid,target) return true;
if(target
else lo=mid;
}
if(contains(a,hi,target) return true;
if(contains(a,lo,target) return true;
return false;
} |
|
i**********e
发帖数: 1145 | 48 不是。
读清楚题意，这个是每一列的第一个值大于之前一行的最后一个值。
Young tableau 是某一列的值不小于之前一行同一列的值。 |
|
l*****a
发帖数: 14598 | 49 确实题意说的太不清楚了
但是猜测一下吧。。
估计是用IP address/MAC Address等unique信息作为key,算出hash code,
然后因为用户众多，assume 一台server放不下
通过那个hash code Map reduce到不同的server
然后在不同server的hashmap中查看是否新user...
然后。。。 |
|
l*****a
发帖数: 14598 | 50 要track ,起码得先识别出来吧。
等LZ的题意说明 |
|
