回馈本版，贴GOOGLE电话面经 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

回馈本版，贴GOOGLE电话面经

回馈本版，贴GOOGLE电话面经# JobHunting - 待字闺中

I*A2010-07-26 07:07

1 楼

45分钟，问了三道题目
（1）Give some scenarios where you might favor O(n^2) algorithm over a O(nlg
(n)) one
（2）Implement an algorithm int removeDuplicate(char[] s)
For instance change ”abbcccdda” to “abcda” and return 4(the number of
characters deleted).
（3）Implement an algorithm to check whether brace expressions are valid or
not
boolean isGood(String s, String braces); //assume braces are valid,{}[]()
题目超级简单
可是CODE第三题的时候犯了两个小的超级低级的错误
interviewer一问，我立刻就明白了忘了check。。。
郁闷死

l*42010-07-26 07:07

2 楼

我google 2面已经挂了，今天接到据信
bless楼主吧

h*62010-07-26 07:07

3 楼

第三题用栈就可以解决吧。左括号压栈，右括号出栈，出栈的和字符串的括号必须对应
，不能尝试弹出空栈，字符串结束后栈必须为空。
就这几条要点，半分钟就能说完，写起来恐怕没二十分钟不好搞定啊。

I*A2010-07-26 07:07

4 楼

哭死
我就是忘记了check"字符串结束后栈必须为空"
interviewer说，最后你return的时候有些case没有考虑到。。
我立刻就明白了，把这个check给加上了。。
平时这种低级错误根本就不会犯，今天不知道是怎么了？TNND..

【在 h**6 的大作中提到】

: 第三题用栈就可以解决吧。左括号压栈，右括号出栈，出栈的和字符串的括号必须对应
: ，不能尝试弹出空栈，字符串结束后栈必须为空。
: 就这几条要点，半分钟就能说完，写起来恐怕没二十分钟不好搞定啊。

I*A2010-07-26 07:07

5 楼

pat pat
thanks thanks

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

: 我google 2面已经挂了，今天接到据信
: bless楼主吧

d*e2010-07-26 07:07

6 楼

能说说第一题吗？
比如说"只对10个数排序"算不算？

nlg
or

【在 I**A 的大作中提到】

: 45分钟，问了三道题目
: （1）Give some scenarios where you might favor O(n^2) algorithm over a O(nlg
: (n)) one
: （2）Implement an algorithm int removeDuplicate(char[] s)
: For instance change ”abbcccdda” to “abcda” and return 4(the number of
: characters deleted).
: （3）Implement an algorithm to check whether brace expressions are valid or
: not
: boolean isGood(String s, String braces); //assume braces are valid,{}[]()
: 题目超级简单

y*n2010-07-26 07:07

7 楼

bless

g*y2010-07-26 07:07

8 楼

第一题可以说以时间换空间吗

【在 d**e 的大作中提到】

: 能说说第一题吗？
: 比如说"只对10个数排序"算不算？
:
: nlg
: or

I*A2010-07-26 07:07

9 楼

这“只对10个数排序”还是没有说出你为什么favor O(n^2)吧
我说了几个。。
1. If O(nlg(n)) requires space, while O(n^2) doesn’t
2. If O(nlg(n)) is difficult to understand and implement, while O(n^2) is
easier
3. If O(n^2) has a general running time less than O(nlg(n)) instead, like
Quicksort
他后来提了一点 what about if there are multiple machines...
欢迎讨论～～～

【在 d**e 的大作中提到】

: 能说说第一题吗？
: 比如说"只对10个数排序"算不算？
:
: nlg
: or

I*A2010-07-26 07:07

10 楼

this is the first one that i mentioned
he said it is good, what else?

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

: 第一题可以说以时间换空间吗

P*l2010-07-26 07:07

11 楼

#1) n2 provides stable sort.
http://en.wikipedia.org/wiki/Sorting_algorithm#Stability

I*A2010-07-26 07:07

12 楼

hmm, nice, this is a point/direction...

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

: #1) n2 provides stable sort.
: http://en.wikipedia.org/wiki/Sorting_algorithm#Stability

z*e2010-07-26 07:07

13 楼

大赞大赞，google freeze的谣言不攻自破。

I*A2010-07-26 07:07

14 楼

hmm, this phone interview was set up 10 days ago....
when did this google freeze saying start?

【在 z****e 的大作中提到】

: 大赞大赞，google freeze的谣言不攻自破。

p*u2010-07-26 07:07

15 楼

题目看起来都很厚道，祝LZ好运！

nlg
or

【在 I**A 的大作中提到】

f*52010-07-26 07:07

16 楼

why there are 2 parameters of Issue 3)

O(nlg
or
valid,{}[]()

【在 I**A 的大作中提到】

I*A2010-07-26 07:07

17 楼

well, first, he gave me the String s, only, as a parameter.
then, I asked him, "can I assume that the braces are limited and fixed? or
do you want me to make it extensible?"
after that, he said:"since you are already thinking about this, let's do it
with braces as a parameter."

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

: why there are 2 parameters of Issue 3)
:
: O(nlg
: or
: valid,{}[]()

s*t2010-07-26 07:07

18 楼

I guess the braces parameter should be given by pairs, like "()[]{}" or"()[]
", rather than "{()}".
then in the function, you can check the brace pair by index.
Am I right?

it

【在 I**A 的大作中提到】

: well, first, he gave me the String s, only, as a parameter.
: then, I asked him, "can I assume that the braces are limited and fixed? or
: do you want me to make it extensible?"
: after that, he said:"since you are already thinking about this, let's do it
: with braces as a parameter."

I*A2010-07-26 07:07

19 楼

[]
this is right

【在 s*******t 的大作中提到】

: I guess the braces parameter should be given by pairs, like "()[]{}" or"()[]
: ", rather than "{()}".
: then in the function, you can check the brace pair by index.
: Am I right?
:
: it

d*i2010-07-26 07:07

20 楼

能把问题2的code分享一下吗，如何解决多个重复的字母，比如abaabbbacc这种应该返
回3而不是4

d*i2010-07-26 07:07

21 楼

For instance change ”abbcccdda” to “abcda” and return 4(the number of
characters deleted).

I*A2010-07-26 07:07

22 楼

we deleted, b, c, c, d， so it will return 4

【在 d*********i 的大作中提到】

: For instance change ”abbcccdda” to “abcda” and return 4(the number of
: characters deleted).

I*A2010-07-26 07:07

23 楼

two pointers moving from the start.
use a while loop.
you can try to write it

【在 d*********i 的大作中提到】

: 能把问题2的code分享一下吗，如何解决多个重复的字母，比如abaabbbacc这种应该返
: 回3而不是4

d*i2010-07-26 07:07

24 楼

这个是我的解法，很简单就能实现。我之前觉得ccc不应该被算2次，count结果为3.不
过题目没要求，就无所谓了。

【在 I**A 的大作中提到】

: two pointers moving from the start.
: use a while loop.
: you can try to write it

d*i2010-07-26 07:07

25 楼

恩，我知道了。我想的是重复的字符（c,c）只算一次，返回3
多谢说明

【在 I**A 的大作中提到】

: we deleted, b, c, c, d， so it will return 4

y*n2010-07-26 07:07

26 楼

int RemoveConsecutiveDuplicates(char* s){
if(s==NULL)return 0;
int len = strlen(s);
if(len==1)return 0;
int index = 1;int tail = 0;
while(indexif(s[index]==s[tail]){
index++;
}else{
tail++;
s[tail] = s[index];
index++;
}
}
s[tail+1]='\0';
return len-strlen(s);
}

【在 d*********i 的大作中提到】

: 能把问题2的code分享一下吗，如何解决多个重复的字母，比如abaabbbacc这种应该返
: 回3而不是4

I*A2010-07-26 07:07

27 楼

挂电话之前扔给我一道题，让我have fun (nnd, 这个我倒是听懂了）
怎么实现找kth element of a linkedlist, 条件是steps少于n+n-k
大家一起have fun吧

答之后的延续问题（而我，完全没明白他问的是什么）。
nlg

【在 I**A 的大作中提到】

: two pointers moving from the start.
: use a while loop.
: you can try to write it

l*c2010-07-26 07:07

28 楼

interesting, but looks like the stupid kth element from the tail.
Is this to find kth largest element?

【在 I**A 的大作中提到】

: 挂电话之前扔给我一道题，让我have fun (nnd, 这个我倒是听懂了）
: 怎么实现找kth element of a linkedlist, 条件是steps少于n+n-k
: 大家一起have fun吧
:
: 答之后的延续问题（而我，完全没明白他问的是什么）。
: nlg

I*A2010-07-26 07:07

29 楼

it is the stupid kth element from the tail

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

: interesting, but looks like the stupid kth element from the tail.
: Is this to find kth largest element?

s*n2010-07-26 07:07

30 楼

试了一下，如果
char string1[] = "ccc";
RemoveConsecutiveDuplicates(string1); 是可以的。
但是
char *string2 = "aaa";
RemoveConsecutiveDuplicates(string2); 是不行的，虽然complier不会报错，但是
run的时候在s[index]赋值的地方报 Access violation writing location 的错。
所以需要检验这个input到底是char * 还是char []。不过没有想出来怎么检验。

【在 y****n 的大作中提到】

: int RemoveConsecutiveDuplicates(char* s){
: if(s==NULL)return 0;
: int len = strlen(s);
: if(len==1)return 0;
: int index = 1;int tail = 0;
: while(index: if(s[index]==s[tail]){
: index++;
: }else{
: tail++;

y*n2010-07-26 07:07

31 楼

char *string2 = "aaa";
This is a char pointer pointing to a const char array.
No modification is allowed. That is why the error pop up.

【在 s****n 的大作中提到】

: 试了一下，如果
: char string1[] = "ccc";
: RemoveConsecutiveDuplicates(string1); 是可以的。
: 但是
: char *string2 = "aaa";
: RemoveConsecutiveDuplicates(string2); 是不行的，虽然complier不会报错，但是
: run的时候在s[index]赋值的地方报 Access violation writing location 的错。
: 所以需要检验这个input到底是char * 还是char []。不过没有想出来怎么检验。

l*e2010-07-26 07:07

32 楼

如果是这样，不是很简单么

【在 I**A 的大作中提到】

: it is the stupid kth element from the tail

I*A2010-07-26 07:07

33 楼

是很简单哪
我说了嘛
最主要的是我给了答案之后老印提出的新问题（而我，完全没听懂他想问什么）。。

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

: 如果是这样，不是很简单么

G*l2010-07-26 07:07

34 楼

rrdw，what is LRU?

答之后的延续问题（而我，完全没明白他问的是什么）。
nlg

【在 I**A 的大作中提到】

: 是很简单哪
: 我说了嘛
: 最主要的是我给了答案之后老印提出的新问题（而我，完全没听懂他想问什么）。。

I*A2010-07-26 07:07

35 楼

Least Recently Used
http://en.wikipedia.org/wiki/Cache_algorithms

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

: rrdw，what is LRU?
:
: 答之后的延续问题（而我，完全没明白他问的是什么）。
: nlg

i*12010-07-26 07:07

36 楼

楼主 comfort.
电话面试遇到老印，交流有障碍，是运气不好。
改天再去面，一定没问题的！

【在 I**A 的大作中提到】

: 是很简单哪
: 我说了嘛
: 最主要的是我给了答案之后老印提出的新问题（而我，完全没听懂他想问什么）。。

D*h2010-07-26 07:07

37 楼

cmft
希望接下来顺利

y*e2010-07-26 07:07

38 楼

第一题，什么情况下favor O(n^2) over O(nlogn)
得考虑常数因子阿，比如，一个是O(n^2)但是其实是2n^2，另外一个是O(nlogn)但是是
44nlog(n)。当n比较小的时候，O(n^2)就比O(nlogn)要快了。