f****n
发帖数: 208 | 1 It's my second time on-site interview with Google at Mountain View. The
first time was four years ago. I feel the place is more crowded, the traffic
was red on Hwy101 at 10am.
Here are the questions:
White GG: find words in a string (recursive), optimize using previous
results.
Korean MM: black box analysis (thoughts only), schedules overlapping problem. | j*****g
发帖数: 223 | 2 能不能把题目讲清楚一点? 谢谢
traffic
problem.
【在 f****n 的大作中提到】
: It's my second time on-site interview with Google at Mountain View. The
: first time was four years ago. I feel the place is more crowded, the traffic
: was red on Hwy101 at 10am.
: Here are the questions:
: White GG: find words in a string (recursive), optimize using previous
: results.
: Korean MM: black box analysis (thoughts only), schedules overlapping problem.
| f****n
发帖数: 208 | 3 1。给出一无空格长字符串，找出所有的单词，假设给定字典。（单词须连续，存在多
解或无解）
2。黑盒子若干时间间隔给出一整数，如何分析结果。
给出若干个行程表，如何判定每个行程表是否和其他行程表冲突。
3。给出若干矩形的重叠关系，如何找出一个矩形集合包含最多个矩形，集合内所有矩形都重叠。
4。 给出两个整数数组，如何找出交集。（返回值为数组，只允许一次分配内存，不可
改变输入数组）
5。给出一整数，转换为罗马数字。
【在 j*****g 的大作中提到】
: 能不能把题目讲清楚一点? 谢谢
:
: traffic
: problem.
| y*****o
发帖数: 36 | 4 楼主能说说第一题是怎么做的吗？
我能想到的就是用greedy的方法从string开头找，找到最长的word（在dictionary中存
在），然后再用同样的方法处理剩下的string。。。不知道还有什么好方法，多谢先！
！ | y*****o
发帖数: 36 | 5 第二题黑盒子是分析什么结果啊？不是很理解的说... | c********v
发帖数: 21 | 6 请教第3题怎么做？
assume a retangle 1 to n
form a graph M[n*n], if rect i intersect with j, then M[i,j] and M[j,i]=1
othwise =0
Then get a longest path of between rect i,j
assume path[i] is the longest path ending at rect i
Is this correct?
矩形都重叠。
【在 f****n 的大作中提到】
: 1。给出一无空格长字符串，找出所有的单词，假设给定字典。（单词须连续，存在多
: 解或无解）
: 2。黑盒子若干时间间隔给出一整数，如何分析结果。
: 给出若干个行程表，如何判定每个行程表是否和其他行程表冲突。
: 3。给出若干矩形的重叠关系，如何找出一个矩形集合包含最多个矩形，集合内所有矩形都重叠。
: 4。 给出两个整数数组，如何找出交集。（返回值为数组，只允许一次分配内存，不可
: 改变输入数组）
: 5。给出一整数，转换为罗马数字。
| s*****s
发帖数: 157 | 7 给出两个整数数组，如何找出交集。（返回值为数组，只允许一次分配内存，不可 改
变输入数组）
这个是sorted的array吗? 或者说是否我们要先sort一下, 然后再找交集? | f****n
发帖数: 208 | 8 第一题，我写的是greedy的代码，找到第一个解返回，用recursive calls. 并不用从
最长的开始，也可以从最短的开始。面官说如何提高效率，发现利用已知解是个好办法
。s(1..n) = (s(1) + s(2..n)) U (s(1..2) + s(3..n)) U .... 没时间再改进code.
第二题是open question, 我的想法是把结果放入数据库（table schema...)，用一些
query分析.
第四题不可以先 sort, 因为不可以改变输入变量和分配内存，应该没有什么好方法，O
(2*m*n). 第一遍计算size, 第二遍插入。考虑到break statement, O(1.9*m*n). | f****n
发帖数: 208 | 9 If you model this way, the answer is not the longest path, but the shape.
Since it wants the rectangles that all overlapping. In the following setup,
the answer is (1, 2, 5)
The longest path is 3,1,2,4,5
Rect ID (Overlap with ID)
1 (2, 3, 5)
2 (1, 4, 5)
3 (1)
4 (2, 5)
5 (1, 2, 4)
【在 c********v 的大作中提到】
: 请教第3题怎么做？
: assume a retangle 1 to n
: form a graph M[n*n], if rect i intersect with j, then M[i,j] and M[j,i]=1
: othwise =0
: Then get a longest path of between rect i,j
: assume path[i] is the longest path ending at rect i
: Is this correct?
:
: 矩形都重叠。
| h****n
发帖数: 2094 | 10 第一次如果知道最长的word多长可以每次取那么长到字典里找（Hash table）。没找到
length - 1再试。都没找到。后移再试。
第三题应该是在图里找最大团的算法。 |
|
