GC收到一周了沃尔玛的钱还没扣啊# Money - 海外理财
U*R
1 楼
昨天和Yelp打了个电话。
对方先问了简历上的东西和项目，接着是一些常见technical小问题
1）从打www.google.com到你看到网页发生了什么
2）process和thread区别是什么，fork做了什么，父进程和子进程的代码一样否
3）mysql query很慢的时候需要做什么，我说explain；又问index好为什么不给每个
column都建一个index
接着一道coding题目
Find the longest substring with non-repeating characters.
for example: ""->0, "a"->1, "aaa"->1, "baabababa"->2, "abcda"->4
面试官没有说要给出time complexity和space complexity上的限制，我就假设这些都
是越少越好。
[更新]此题已解，做法参照http://www.leetcode.com/2011/05/longest-substring-without-repeating-characters.html
请大牛指点一下这道题!!
我的解法是
1)用hash_map记录字符和字符上次出现的地方。最开始hash_map为空。
2)go through the string, 思路用伪代码表示如下，
start = 0; // start points to the start of the result string
for each character c in string s:
check if c has already appeared in hashmap
if not found: // c is a new character
insert a pair (c, c's position) into hashmap
else:
// c has appeared before
erase all characters within [start, hashmap[c]) from hashmap
// "erase" step will finish in O(1) time if the size of the
character set is limited (for example, only 26 characters)
update start to be hashmap[c]+1
hashmap[c] = c's current position
update greatest length if (c's position - start + 1) is greater
我觉得面试官对这个O(n)解法不满意，他认为只要keep start 和end两个位置就可以了
，中间什么字符出现在什么位置都不用记录。
对方先问了简历上的东西和项目，接着是一些常见technical小问题
1）从打www.google.com到你看到网页发生了什么
2）process和thread区别是什么，fork做了什么，父进程和子进程的代码一样否
3）mysql query很慢的时候需要做什么，我说explain；又问index好为什么不给每个
column都建一个index
接着一道coding题目
Find the longest substring with non-repeating characters.
for example: ""->0, "a"->1, "aaa"->1, "baabababa"->2, "abcda"->4
面试官没有说要给出time complexity和space complexity上的限制，我就假设这些都
是越少越好。
[更新]此题已解，做法参照http://www.leetcode.com/2011/05/longest-substring-without-repeating-characters.html
请大牛指点一下这道题!!
我的解法是
1)用hash_map
2)go through the string, 思路用伪代码表示如下，
start = 0; // start points to the start of the result string
for each character c in string s:
check if c has already appeared in hashmap
if not found: // c is a new character
insert a pair (c, c's position) into hashmap
else:
// c has appeared before
erase all characters within [start, hashmap[c]) from hashmap
// "erase" step will finish in O(1) time if the size of the
character set is limited (for example, only 26 characters)
update start to be hashmap[c]+1
hashmap[c] = c's current position
update greatest length if (c's position - start + 1) is greater
我觉得面试官对这个O(n)解法不满意，他认为只要keep start 和end两个位置就可以了
，中间什么字符出现在什么位置都不用记录。
