I**A
发帖数: 2345 | 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******4
发帖数: 729 | 2 我google 2面已经挂了，今天接到据信
bless楼主吧 |
h**6
发帖数: 4160 | 3 第三题用栈就可以解决吧。左括号压栈，右括号出栈，出栈的和字符串的括号必须对应
，不能尝试弹出空栈，字符串结束后栈必须为空。
就这几条要点，半分钟就能说完，写起来恐怕没二十分钟不好搞定啊。 |
I**A
发帖数: 2345 | 4 哭死
我就是忘记了check"字符串结束后栈必须为空"
interviewer说，最后你return的时候有些case没有考虑到。。
我立刻就明白了，把这个check给加上了。。
平时这种低级错误根本就不会犯，今天不知道是怎么了？TNND..
【在 h**6 的大作中提到】
: 第三题用栈就可以解决吧。左括号压栈，右括号出栈，出栈的和字符串的括号必须对应
: ，不能尝试弹出空栈，字符串结束后栈必须为空。
: 就这几条要点，半分钟就能说完，写起来恐怕没二十分钟不好搞定啊。
|
I**A
发帖数: 2345 | 5 pat pat
thanks thanks
【在 l******4 的大作中提到】
: 我google 2面已经挂了，今天接到据信
: bless楼主吧
|
d**e
发帖数: 6098 | 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****n
发帖数: 579 | |
g*******y
发帖数: 2114 | 8 第一题可以说 以时间换空间吗
【在 d**e 的大作中提到】
: 能说说第一题吗？
: 比如说"只对10个数排序"算不算？
:
: nlg
: or
|
I**A
发帖数: 2345 | 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**A
发帖数: 2345 | 10 this is the first one that i mentioned
he said it is good, what else?
【在 g*******y 的大作中提到】
: 第一题可以说 以时间换空间吗
|
|
|
P********l
发帖数: 452 | |
I**A
发帖数: 2345 | 12 hmm, nice, this is a point/direction...
【在 P********l 的大作中提到】
: #1) n2 provides stable sort.
: http://en.wikipedia.org/wiki/Sorting_algorithm#Stability
|
z****e
发帖数: 2024 | 13 大赞大赞，google freeze的谣言不攻自破。 |
I**A
发帖数: 2345 | 14 hmm, this phone interview was set up 10 days ago....
when did this google freeze saying start?
【在 z****e 的大作中提到】
: 大赞大赞，google freeze的谣言不攻自破。
|
p*u
发帖数: 136 | 15 题目看起来都很厚道，祝LZ好运！
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,{}[]()
: 题目超级简单
|
f*********5
发帖数: 576 | 16 why there are 2 parameters of Issue 3)
O(nlg
or
valid,{}[]()
【在 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,{}[]()
: 题目超级简单
|
I**A
发帖数: 2345 | 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*******t
发帖数: 248 | 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**A
发帖数: 2345 | 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*********i
发帖数: 628 | 20 能把问题2的code分享一下吗，如何解决多个重复的字母，比如abaabbbacc这种应该返
回3而不是4 |
|
|
d*********i
发帖数: 628 | 21 For instance change ”abbcccdda” to “abcda” and return 4(the number of
characters deleted). |
I**A
发帖数: 2345 | 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**A
发帖数: 2345 | 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*********i
发帖数: 628 | 24
这个是我的解法，很简单就能实现。我之前觉得ccc不应该被算2次，count结果为3.不
过题目没要求，就无所谓了。
【在 I**A 的大作中提到】
: two pointers moving from the start.
: use a while loop.
: you can try to write it
|
d*********i
发帖数: 628 | 25
恩，我知道了。我想的是重复的字符（c,c）只算一次，返回3
多谢说明
【在 I**A 的大作中提到】
: we deleted, b, c, c, d， so it will return 4
|
y****n
发帖数: 579 | 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(index
if(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**A
发帖数: 2345 | 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******c
发帖数: 2555 | 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**A
发帖数: 2345 | 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****n
发帖数: 1237 | 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****n
发帖数: 579 | 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******e
发帖数: 12192 | 32 如果是这样，不是很简单么
【在 I**A 的大作中提到】
: it is the stupid kth element from the tail
|
I**A
发帖数: 2345 | 33 是很简单哪
我说了嘛
最主要的是我给了答案之后老印提出的新问题（而我，完全没听懂他想问什么）。。
【在 l******e 的大作中提到】
: 如果是这样，不是很简单么
|
G*******l
发帖数: 281 | 34 rrdw，what is LRU?
答之后的延续问题（而我，完全没明白他问的是什么）。
nlg
【在 I**A 的大作中提到】
: 是很简单哪
: 我说了嘛
: 最主要的是我给了答案之后老印提出的新问题（而我，完全没听懂他想问什么）。。
|
I**A
发帖数: 2345 | 35 Least Recently Used
http://en.wikipedia.org/wiki/Cache_algorithms
【在 G*******l 的大作中提到】
: rrdw，what is LRU?
:
: 答之后的延续问题（而我，完全没明白他问的是什么）。
: nlg
|
i***1
发帖数: 95 | 36 楼主 comfort.
电话面试遇到老印，交流有障碍，是运气不好。
改天再去面，一定没问题的！
【在 I**A 的大作中提到】
: 是很简单哪
: 我说了嘛
: 最主要的是我给了答案之后老印提出的新问题（而我，完全没听懂他想问什么）。。
|
D***h
发帖数: 183 | |
y*********e
发帖数: 518 | 38 第一题，什么情况下favor O(n^2) over O(nlogn)
得考虑常数因子阿，比如，一个是O(n^2)但是其实是2n^2，另外一个是O(nlogn)但是是
44nlog(n)。当n比较小的时候，O(n^2)就比O(nlogn)要快了。 |
