G家已跪，发个面经 - 未名空间MITBBS历史存档

m*g2013-04-07 07:04

1 楼

继续做题，最近一段时间不投简历了。
G家题不难。面试的核心是看你是不是足够smart。很好的语言沟通能力会加分的。不过
这个就不是短期能提高的了。还有，国人面试官mm还是帮忙的。
1.merge interval。输入是一个sorted interval list和一个target interval。
2.2维0，1矩阵。判断有多少个封闭的全是0的area。DFS，BFS的方法都要写。
3. power（x，n）
4. 1个正确的sentence-去掉空格。字符位置打乱成另一个string。判断这两个string
那个是原始sentence。提供dictionary。要自己定义判断的方法。考虑各种情况。
5。判断两个集合中的共有element。

A*u2013-04-07 07:04

2 楼

on site题目
不简单啊

m*g2013-04-07 07:04

3 楼

也就第4题难点。其他本版都讨论过。
还有，国人mm的题因为太简单，就没贴。

G*A2013-04-07 07:04

4 楼

第一题是leetcode上的么？我怎么找不到
之前一家公司homework assignment就出了这道题，我花了整整2小时才完整解答。
菜鸟本质暴露无遗

【在 m*********g 的大作中提到】

: 也就第4题难点。其他本版都讨论过。
: 还有，国人mm的题因为太简单，就没贴。

f*m2013-04-07 07:04

5 楼

第四题：
step 1.看两个string是否存在某种分割使得分割后的单词都在字典中。若其中一个找
不到，则返回那个存在某种分割的。若都能找到，到step 2。
step 2. 制定规则，对string 1和2的所有分割判断是否违反这些规则，若存在一个分
割满足规则，则为原string。这也许要涉及到一些英语的grammer规则了。
不知对否。第二步好像很不容易。
楼主怎么做的？

string

【在 m*********g 的大作中提到】

: 继续做题，最近一段时间不投简历了。
: G家题不难。面试的核心是看你是不是足够smart。很好的语言沟通能力会加分的。不过
: 这个就不是短期能提高的了。还有，国人面试官mm还是帮忙的。
: 1.merge interval。输入是一个sorted interval list和一个target interval。
: 2.2维0，1矩阵。判断有多少个封闭的全是0的area。DFS，BFS的方法都要写。
: 3. power（x，n）
: 4. 1个正确的sentence-去掉空格。字符位置打乱成另一个string。判断这两个string
: 那个是原始sentence。提供dictionary。要自己定义判断的方法。考虑各种情况。
: 5。判断两个集合中的共有element。

e*a2013-04-07 07:04

6 楼

do you use Java?

string

【在 m*********g 的大作中提到】

: 继续做题，最近一段时间不投简历了。
: G家题不难。面试的核心是看你是不是足够smart。很好的语言沟通能力会加分的。不过
: 这个就不是短期能提高的了。还有，国人面试官mm还是帮忙的。
: 1.merge interval。输入是一个sorted interval list和一个target interval。
: 2.2维0，1矩阵。判断有多少个封闭的全是0的area。DFS，BFS的方法都要写。
: 3. power（x，n）
: 4. 1个正确的sentence-去掉空格。字符位置打乱成另一个string。判断这两个string
: 那个是原始sentence。提供dictionary。要自己定义判断的方法。考虑各种情况。
: 5。判断两个集合中的共有element。

r*h2013-04-07 07:04

7 楼

第一题能clarify一下吗？
是找到list里面的interval的一个子集，使得他们的并正好是target interval？
要求是最小个数的interval吗？这些要是合并后的interval比target interval大是否
可以？

string

【在 m*********g 的大作中提到】

: 继续做题，最近一段时间不投简历了。
: G家题不难。面试的核心是看你是不是足够smart。很好的语言沟通能力会加分的。不过
: 这个就不是短期能提高的了。还有，国人面试官mm还是帮忙的。
: 1.merge interval。输入是一个sorted interval list和一个target interval。
: 2.2维0，1矩阵。判断有多少个封闭的全是0的area。DFS，BFS的方法都要写。
: 3. power（x，n）
: 4. 1个正确的sentence-去掉空格。字符位置打乱成另一个string。判断这两个string
: 那个是原始sentence。提供dictionary。要自己定义判断的方法。考虑各种情况。
: 5。判断两个集合中的共有element。

f*e2013-04-07 07:04

8 楼

第4题考的好像是linear algebraic equation integer solution。

string

【在 m*********g 的大作中提到】

: 继续做题，最近一段时间不投简历了。
: G家题不难。面试的核心是看你是不是足够smart。很好的语言沟通能力会加分的。不过
: 这个就不是短期能提高的了。还有，国人面试官mm还是帮忙的。
: 1.merge interval。输入是一个sorted interval list和一个target interval。
: 2.2维0，1矩阵。判断有多少个封闭的全是0的area。DFS，BFS的方法都要写。
: 3. power（x，n）
: 4. 1个正确的sentence-去掉空格。字符位置打乱成另一个string。判断这两个string
: 那个是原始sentence。提供dictionary。要自己定义判断的方法。考虑各种情况。
: 5。判断两个集合中的共有element。

m*g2013-04-07 07:04

9 楼

第一题就是合并interval。如果list中的interval和target interval有重合，就合并
他们。得到的是一个新的interval list。
第4题还有个延伸问题-如果给的是n个string，你怎么做。这个题没有写code。就是和
面试官讨论。
首先应该定义一个function。f(string) = ?
如果string中有substring在字典里，这个函数返回所有substring的总长度。最长的
string就是所求的。

m*g2013-04-07 07:04

10 楼

我用的是C++。这个和语言没有关系吧。

w*p2013-04-07 07:04

11 楼

收藏楼主的帖子先。
第一题就是合并interval。如果list中的interval和target interval有重合，就合并
假设我对题意的理解是对的。
list 1: {1, 3} {12, 14}
list 2: {2, 4} {13, 15} {5, 10}
new List: {1, 4}, {12, 15} {5, 10}
solution:
step 1: Sort all points:
1S, 2S, 3E, 4E, 5S, 10E, 12S, 13S, 14E, 15E
step 2: group the interval: two model : (S E) or ( S S S.... E E E ...)
for S count++; for E count--; group it from count 0 to count 0
(1S, 2S, 3E, 4E), (5S, 10E), (12S, 13S, 14E, 15E)
step 3: {1, 4}, {5, 10}, {12, 15}

w*p2013-04-07 07:04

12 楼

第4题我第一反应就是cc150上的，给一个string. 看你能不能把它break成几个单词。
延伸问题-如果给的是n个string。我不是很理解。觉得和一个还是俩个String没有差。
“最长的 string就是所求的”，这个我很怀疑。一个句子，是不是合理的原来的句子和
最后的substring的总长度，或者是word的个数，应该没有必然的关系。只能说是有可
能。

【在 m*********g 的大作中提到】

: 第一题就是合并interval。如果list中的interval和target interval有重合，就合并
: 他们。得到的是一个新的interval list。
: 第4题还有个延伸问题-如果给的是n个string，你怎么做。这个题没有写code。就是和
: 面试官讨论。
: 首先应该定义一个function。f(string) = ?
: 如果string中有substring在字典里，这个函数返回所有substring的总长度。最长的
: string就是所求的。

x*w2013-04-07 07:04

13 楼

string
第4题是啥意思？？？
如果都能分割成单词，岂不是还要自然语言处理相关的知识才能判断是否是正确的
sentence?
怎么coding??? 楼主能不能把题目详细说说，最好给个例子啥的

【在 m*********g 的大作中提到】

: 继续做题，最近一段时间不投简历了。
: G家题不难。面试的核心是看你是不是足够smart。很好的语言沟通能力会加分的。不过
: 这个就不是短期能提高的了。还有，国人面试官mm还是帮忙的。
: 1.merge interval。输入是一个sorted interval list和一个target interval。
: 2.2维0，1矩阵。判断有多少个封闭的全是0的area。DFS，BFS的方法都要写。
: 3. power（x，n）
: 4. 1个正确的sentence-去掉空格。字符位置打乱成另一个string。判断这两个string
: 那个是原始sentence。提供dictionary。要自己定义判断的方法。考虑各种情况。
: 5。判断两个集合中的共有element。

n*w2013-04-07 07:04

14 楼

整体看偏难啊
第一次做interval没两小时搞不定吧。interval很多特例。比如插入的interval夹在两
个node中间，插入到最后一个node之后，插入的node范围覆盖了很多node所以要删掉一
些nodes等等。
用python写了个，16行就可以搞定。使用一个dummy node非常有用。

string

【在 m*********g 的大作中提到】

: 继续做题，最近一段时间不投简历了。
: G家题不难。面试的核心是看你是不是足够smart。很好的语言沟通能力会加分的。不过
: 这个就不是短期能提高的了。还有，国人面试官mm还是帮忙的。
: 1.merge interval。输入是一个sorted interval list和一个target interval。
: 2.2维0，1矩阵。判断有多少个封闭的全是0的area。DFS，BFS的方法都要写。
: 3. power（x，n）
: 4. 1个正确的sentence-去掉空格。字符位置打乱成另一个string。判断这两个string
: 那个是原始sentence。提供dictionary。要自己定义判断的方法。考虑各种情况。
: 5。判断两个集合中的共有element。

n*w2013-04-07 07:04

15 楼

target interval是一个interval不是一个list吧。
另外肯定要in-place的做，否则空间代价有点大啊。当然用额外空间会简化很多。

【在 w********p 的大作中提到】

: 收藏楼主的帖子先。
: 第一题就是合并interval。如果list中的interval和target interval有重合，就合并
: 假设我对题意的理解是对的。
: list 1: {1, 3} {12, 14}
: list 2: {2, 4} {13, 15} {5, 10}
: new List: {1, 4}, {12, 15} {5, 10}
: solution:
: step 1: Sort all points:
: 1S, 2S, 3E, 4E, 5S, 10E, 12S, 13S, 14E, 15E
: step 2: group the interval: two model : (S E) or ( S S S.... E E E ...)

M*n2013-04-07 07:04

16 楼

第一题可以用压栈出战的方法吧。
根据start排序，
碰到Start，压栈，
碰到end出战，检查top空否，空了，是个新itnerval
非空，继续下一个。
不知可行否

r*72013-04-07 07:04

17 楼

好难啊。。

j*22013-04-07 07:04

18 楼

我跟你的感觉一样。如果是scramble，那也还是有可能scramble出来的句子还是可以分
割成词。只能用150上的解法找出invalid字符为0的那个。n个string也是如此。但是因
为只要返回bool，对错误的string可以early termination。

差。
子和

【在 w********p 的大作中提到】

: 第4题我第一反应就是cc150上的，给一个string. 看你能不能把它break成几个单词。
: 延伸问题-如果给的是n个string。我不是很理解。觉得和一个还是俩个String没有差。
: “最长的 string就是所求的”，这个我很怀疑。一个句子，是不是合理的原来的句子和
: 最后的substring的总长度，或者是word的个数，应该没有必然的关系。只能说是有可
: 能。

w*p2013-04-07 07:04

19 楼

请教
2维0，1矩阵。判断有多少个封闭的全是0的area
这个封闭的area是要长方形的还是任意不规则形状的。

string

【在 m*********g 的大作中提到】

: 继续做题，最近一段时间不投简历了。
: G家题不难。面试的核心是看你是不是足够smart。很好的语言沟通能力会加分的。不过
: 这个就不是短期能提高的了。还有，国人面试官mm还是帮忙的。
: 1.merge interval。输入是一个sorted interval list和一个target interval。
: 2.2维0，1矩阵。判断有多少个封闭的全是0的area。DFS，BFS的方法都要写。
: 3. power（x，n）
: 4. 1个正确的sentence-去掉空格。字符位置打乱成另一个string。判断这两个string
: 那个是原始sentence。提供dictionary。要自己定义判断的方法。考虑各种情况。
: 5。判断两个集合中的共有element。

a*02013-04-07 07:04

20 楼

第二题不那么简单，如何track已经查过的点，这样找下一个封闭区域就不用检查已经
查过了的点了

p*22013-04-07 07:04

21 楼

第四题我也没看明白。谁能给个例子？

c*f2013-04-07 07:04

22 楼

第五题判断两个集合共有的element 大家都有什么好的方法呢？？

c*f2013-04-07 07:04

23 楼

第五题判断两个集合共有的element 大家都有什么好的方法呢？？

string

【在 m*********g 的大作中提到】

: 继续做题，最近一段时间不投简历了。
: G家题不难。面试的核心是看你是不是足够smart。很好的语言沟通能力会加分的。不过
: 这个就不是短期能提高的了。还有，国人面试官mm还是帮忙的。
: 1.merge interval。输入是一个sorted interval list和一个target interval。
: 2.2维0，1矩阵。判断有多少个封闭的全是0的area。DFS，BFS的方法都要写。
: 3. power（x，n）
: 4. 1个正确的sentence-去掉空格。字符位置打乱成另一个string。判断这两个string
: 那个是原始sentence。提供dictionary。要自己定义判断的方法。考虑各种情况。
: 5。判断两个集合中的共有element。

a*02013-04-07 07:04

24 楼

bit map AND?

【在 c***f 的大作中提到】

: 第五题判断两个集合共有的element 大家都有什么好的方法呢？？
:
: string

l*a2013-04-07 07:04

25 楼

思路不错
具体实现呢?两个集合的相同元素怎么放在同一个bit上

【在 a*********0 的大作中提到】

: bit map AND?

c*f2013-04-07 07:04

26 楼

用bloom filter 考虑将元素hash 到bitmap上吗？？

【在 l*****a 的大作中提到】

: 思路不错
: 具体实现呢?两个集合的相同元素怎么放在同一个bit上

c*f2013-04-07 07:04

27 楼

第五题判断两个集合共有的element
大家都有些什么思路呢

s*i2013-04-07 07:04

28 楼

Mark

string

【在 m*********g 的大作中提到】

: 继续做题，最近一段时间不投简历了。
: G家题不难。面试的核心是看你是不是足够smart。很好的语言沟通能力会加分的。不过
: 这个就不是短期能提高的了。还有，国人面试官mm还是帮忙的。
: 1.merge interval。输入是一个sorted interval list和一个target interval。
: 2.2维0，1矩阵。判断有多少个封闭的全是0的area。DFS，BFS的方法都要写。
: 3. power（x，n）
: 4. 1个正确的sentence-去掉空格。字符位置打乱成另一个string。判断这两个string
: 那个是原始sentence。提供dictionary。要自己定义判断的方法。考虑各种情况。
: 5。判断两个集合中的共有element。

s*i2013-04-07 07:04

29 楼

Mark

string

【在 m*********g 的大作中提到】

: 继续做题，最近一段时间不投简历了。
: G家题不难。面试的核心是看你是不是足够smart。很好的语言沟通能力会加分的。不过
: 这个就不是短期能提高的了。还有，国人面试官mm还是帮忙的。
: 1.merge interval。输入是一个sorted interval list和一个target interval。
: 2.2维0，1矩阵。判断有多少个封闭的全是0的area。DFS，BFS的方法都要写。
: 3. power（x，n）
: 4. 1个正确的sentence-去掉空格。字符位置打乱成另一个string。判断这两个string
: 那个是原始sentence。提供dictionary。要自己定义判断的方法。考虑各种情况。
: 5。判断两个集合中的共有element。

x*02013-04-07 07:04

30 楼

mark