U*****R
发帖数: 60 | 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两个位置就可以了
，中间什么字符出现在什么位置都不用记录。 |
e***s
发帖数: 799 | |
U*****R
发帖数: 60 | 3 对于前面1)2)3)小问题，我没有什么疑问。都是比较基本的。
继续顶，看看大家对coding那题有什么看法。 |
z*********8
发帖数: 2070 | 4 coding题： 要么你没理解面试官的意图， 要么他在瞎扯
必须知道char的index，详解看大神的网站：
http://www.leetcode.com/2011/05/longest-substring-without-repea
【在 U*****R 的大作中提到】
: 昨天和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上的限制，我就假设这些都
|
U*****R
发帖数: 60 | 5 明白了。多谢！
【在 z*********8 的大作中提到】
: coding题： 要么你没理解面试官的意图， 要么他在瞎扯
: 必须知道char的index，详解看大神的网站：
: http://www.leetcode.com/2011/05/longest-substring-without-repea
|
S******y
发帖数: 1330 | 6 从打www.google.com到你看到网页发生了什么?? |
x*******1
发帖数: 28835 | 7 www.google.com send this to dns, dns send ip address you request backs.
your browser sends a http connect request to the "IP" address( Google server
).
Google accept your request and build a connection to you.
Google server push a web page(html file) to your client(browser)
You browser reads and explain the html to display format. |
y**********u
发帖数: 6366 | 8 1. dns request
2. http get session
3. browser render
没什么难得啊。。
server
【在 x*******1 的大作中提到】
: www.google.com send this to dns, dns send ip address you request backs.
: your browser sends a http connect request to the "IP" address( Google server
: ).
: Google accept your request and build a connection to you.
: Google server push a web page(html file) to your client(browser)
: You browser reads and explain the html to display format.
|
x*******1
发帖数: 28835 | 9 动态网页了？ 比如Input some words inside google search 到google 给出结果 |
y**********u
发帖数: 6366 | 10 https get啊
脚本网页(javascript)产生get的url
【在 x*******1 的大作中提到】
: 动态网页了？ 比如Input some words inside google search 到google 给出结果
|
|
|
z*y
发帖数: 1311 | 11
erase all是败笔啊
【在 U*****R 的大作中提到】
: 对于前面1)2)3)小问题，我没有什么疑问。都是比较基本的。
: 继续顶，看看大家对coding那题有什么看法。
|
d******a
发帖数: 238 | 12 你那个编程题，要是没提前见过的话，很难在电话面试写好的。 |
l***i
发帖数: 1309 | 13 this one is easier than most problems on this board
【在 d******a 的大作中提到】
: 你那个编程题，要是没提前见过的话，很难在电话面试写好的。
|
g*********e
发帖数: 14401 | 14
这题挺简单的吧
【在 d******a 的大作中提到】
: 你那个编程题，要是没提前见过的话，很难在电话面试写好的。
|
p*****2
发帖数: 21240 | 15
就是一道简单题，虽然我没写过。
【在 g*********e 的大作中提到】
:
: 这题挺简单的吧
|
r********9
发帖数: 1116 | 16 这个也不是最优。O(2n)可以简化成O(n)：hashtable exist[256]的值不需要每经过一
个substring都还原一次。
具体的说，把exist[256]定义成int的数组，每次访问完一个字符，就更新对应字符在
exist[256]中对应位置的值为visited（而不是true）。当开始一个新的substring时，
let visited=visited+1.
characters.html
【在 z*********8 的大作中提到】
: coding题： 要么你没理解面试官的意图， 要么他在瞎扯
: 必须知道char的index，详解看大神的网站：
: http://www.leetcode.com/2011/05/longest-substring-without-repea
|
w****x
发帖数: 2483 | 17 其实fork那道题因该答基于操作系统虚拟内存页面的Copy-On-Write机制, 主要是创建
进程开销不大 |
w****x
发帖数: 2483 | 18 其实fork那道题因该答基于操作系统虚拟内存页面的Copy-On-Write机制, 主要是创建
进程开销不大 |
