n******n
发帖数: 49 | 1 发Yahoo MS Amazon面经
我碰到的 也都是一些还算中规中矩的题 所以 也算是来给各位找工作的打打气！
Yahoo 电面 印度人
1.电话键盘上1-》abc 2->cde... 现在来一堆数，未知长度，比如123456..... 请输出
序列可能对应的所有字符串
比如 123 输出acf, acg, ach, bcf...
2.检测链表是否有环
3.sql语句
employee(id(primary key),name)
employee_bonus(id(primary key), bonus) （现在觉得这题 似乎有点问题，因为他和
我说 id可以对应多个bonus, 那这还算是primary key吗。。。）
请写sql 输出name和这个人bonus总和。
MS on campus interview - first round
1. 简历问题
2. 给一个字符串检测是否是valid ip address, 这题他似乎是想看看我的思路，我说
regular express, 他说要code, 我就写了一些，解释了一下。总之，这题真要追究起
来，细节颇多，但因为我们每个人都只有30分钟，所以他没有要求完美的答案。
我知道的其他ms校园面试题
1. bst删除一个节点
2. 矩阵，每行从左到右递增，每列从上到下递增，找一个数。
Amazon所有轮的题目
1. 数一个字符串中的单词数。
2. 经典的 一堆数只有一个出现2次 其他数出现一次 怎么找出那个重复的数。请给出4
种以上解法。。。包括brute force...
3. longest palindrome.
4. design restaurant reservation system.
5. atoi, 只能用一个loop. 要考虑-213， 2-13， a2-13....各种情况。。 这题看似
简单，但是要小心，容易出错。
6. design a phonebook, 要求输入人名的时候电话随之更新。比如a给出一个电话，
abc给一个，abcd再更新给出一个电话。trie的implementation, 假设每个节点存一个
数据和26个指针。
7. c++中static和virtual keyword, 请解释用法。
amazon给我的感觉就是算法不一定很难，但喜欢考oo design.
因为上面很多题目 都是经典的题目 所以不在这里班门弄斧了，网上都可以找到答案，
但是欢迎讨论！希望大家都面试好运！ |
d*****t
发帖数: 41 | 2 employee_bonus里的id应该是foreign key吧~ primary key不存在重复的情况~ |
a***c
发帖数: 2443 | 3 "2. 给一个字符串检测是否是valid ip address, 这题他似乎是想看看我的思路，我说
regular express, 他说要code, 我就写了一些，解释了一下。总之，这题真要追究起
来，细节颇多，但因为我们每个人都只有30分钟，所以他没有要求完美的答案。"
what are the complications in this one?
The obvious is to make sure all the octets are within the 0-255 range,
what else is there to check? reserved addresses?
【在 n******n 的大作中提到】
: 发Yahoo MS Amazon面经
: 我碰到的 也都是一些还算中规中矩的题 所以 也算是来给各位找工作的打打气！
: Yahoo 电面 印度人
: 1.电话键盘上1-》abc 2->cde... 现在来一堆数，未知长度，比如123456..... 请输出
: 序列可能对应的所有字符串
: 比如 123 输出acf, acg, ach, bcf...
: 2.检测链表是否有环
: 3.sql语句
: employee(id(primary key),name)
: employee_bonus(id(primary key), bonus) （现在觉得这题 似乎有点问题，因为他和
|
n******n
发帖数: 49 | 4 嗯 你说的那个是一个
另一个是 dot 可能出现在任意位置，其中可能有非数字字符，dot的个数不是3.。。
所以我一开始就说regular expression.
【在 a***c 的大作中提到】
: "2. 给一个字符串检测是否是valid ip address, 这题他似乎是想看看我的思路，我说
: regular express, 他说要code, 我就写了一些，解释了一下。总之，这题真要追究起
: 来，细节颇多，但因为我们每个人都只有30分钟，所以他没有要求完美的答案。"
: what are the complications in this one?
: The obvious is to make sure all the octets are within the 0-255 range,
: what else is there to check? reserved addresses?
|
a***c
发帖数: 2443 | 5 oh, of course, thanks.
sitting in front of the computer writing thesis all day makes you dull,
you know. lol
【在 n******n 的大作中提到】
: 嗯 你说的那个是一个
: 另一个是 dot 可能出现在任意位置，其中可能有非数字字符，dot的个数不是3.。。
: 所以我一开始就说regular expression.
|
i**********e
发帖数: 1145 | 6 可以考虑用 tokenization 吗？(The tokens are separated by a single dot).
确认总共有四个token，然后每一个token再检测是不是0-255的号码。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 n******n 的大作中提到】
: 嗯 你说的那个是一个
: 另一个是 dot 可能出现在任意位置，其中可能有非数字字符，dot的个数不是3.。。
: 所以我一开始就说regular expression.
|
s*****s
发帖数: 157 | 7 ip address那个, 用strtok好像容易些, 下面的code能否完成:
int foo(char *IP)
{
if(strlen(IP) > 16)
return false;
if(strlen(IP) < 8)
return false;
for (int i = 0 ; i < strlen(IP); i++)
{
if (!(IP[i] >= '0' && IP[i] <= '9' || IP[i] == '.'))
return false;
}
char * range = strtok(IP, ".");
short c = 0;
while ((range != NULL) && (c < 4))
{
if((strlen(range) <= 3) && (atoi(range) >= 0 &&(atoi(range) <= 255))
++c;
else
break;
range = strtok(NULL, ".");
}
return (c == 4);
} |
D***h
发帖数: 183 | 8 thanks for sharing!
Bless!
【在 n******n 的大作中提到】
: 发Yahoo MS Amazon面经
: 我碰到的 也都是一些还算中规中矩的题 所以 也算是来给各位找工作的打打气！
: Yahoo 电面 印度人
: 1.电话键盘上1-》abc 2->cde... 现在来一堆数，未知长度，比如123456..... 请输出
: 序列可能对应的所有字符串
: 比如 123 输出acf, acg, ach, bcf...
: 2.检测链表是否有环
: 3.sql语句
: employee(id(primary key),name)
: employee_bonus(id(primary key), bonus) （现在觉得这题 似乎有点问题，因为他和
|
n******n
发帖数: 49 | 9 发Yahoo MS Amazon面经
我碰到的 也都是一些还算中规中矩的题 所以 也算是来给各位找工作的打打气！
Yahoo 电面 印度人
1.电话键盘上1-》abc 2->cde... 现在来一堆数，未知长度，比如123456..... 请输出
序列可能对应的所有字符串
比如 123 输出acf, acg, ach, bcf...
2.检测链表是否有环
3.sql语句
employee(id(primary key),name)
employee_bonus(id(primary key), bonus) （现在觉得这题 似乎有点问题，因为他和
我说 id可以对应多个bonus, 那这还算是primary key吗。。。）
请写sql 输出name和这个人bonus总和。
MS on campus interview - first round
1. 简历问题
2. 给一个字符串检测是否是valid ip address, 这题他似乎是想看看我的思路，我说
regular express, 他说要code, 我就写了一些，解释了一下。总之，这题真要追究起
来，细节颇多，但因为我们每个人都只有30分钟，所以他没有要求完美的答案。
我知道的其他ms校园面试题
1. bst删除一个节点
2. 矩阵，每行从左到右递增，每列从上到下递增，找一个数。
Amazon所有轮的题目
1. 数一个字符串中的单词数。
2. 经典的 一堆数只有一个出现2次 其他数出现一次 怎么找出那个重复的数。请给出4
种以上解法。。。包括brute force...
3. longest palindrome.
4. design restaurant reservation system.
5. atoi, 只能用一个loop. 要考虑-213， 2-13， a2-13....各种情况。。 这题看似
简单，但是要小心，容易出错。
6. design a phonebook, 要求输入人名的时候电话随之更新。比如a给出一个电话，
abc给一个，abcd再更新给出一个电话。trie的implementation, 假设每个节点存一个
数据和26个指针。
7. c++中static和virtual keyword, 请解释用法。
amazon给我的感觉就是算法不一定很难，但喜欢考oo design.
因为上面很多题目 都是经典的题目 所以不在这里班门弄斧了，网上都可以找到答案，
但是欢迎讨论！希望大家都面试好运！ |
v***n
发帖数: 562 | |
|
|
p*******4
发帖数: 516 | |
r******n
发帖数: 170 | 12 赞。
随便问问下面2题：
3. longest palindrome.
这题要求写出O(n)的算法吗？还是O(n^2)就OK.
6. design a phonebook, 要求输入人名的时候电话随之更新。比如a给出一个电话，
abc给一个，abcd再更新给出一个电话。trie的implementation, 假设每个节点存一个
数据和26个指针。
那么这个Trie只能用来搜索人名了？对应的电话号码怎么存？ 每个trie的node存一个
指向电话号码list的指针？
【在 n******n 的大作中提到】
: 发Yahoo MS Amazon面经
: 我碰到的 也都是一些还算中规中矩的题 所以 也算是来给各位找工作的打打气！
: Yahoo 电面 印度人
: 1.电话键盘上1-》abc 2->cde... 现在来一堆数，未知长度，比如123456..... 请输出
: 序列可能对应的所有字符串
: 比如 123 输出acf, acg, ach, bcf...
: 2.检测链表是否有环
: 3.sql语句
: employee(id(primary key),name)
: employee_bonus(id(primary key), bonus) （现在觉得这题 似乎有点问题，因为他和
|
a**********2
发帖数: 340 | 13 3.O(n)使用suffix tree，写个伪代码就可以了吧
6.存leaf上不就行了么？从当前节点开始做一个dfs，找到就返回
【在 r******n 的大作中提到】
: 赞。
: 随便问问下面2题：
: 3. longest palindrome.
: 这题要求写出O(n)的算法吗？还是O(n^2)就OK.
: 6. design a phonebook, 要求输入人名的时候电话随之更新。比如a给出一个电话，
: abc给一个，abcd再更新给出一个电话。trie的implementation, 假设每个节点存一个
: 数据和26个指针。
: 那么这个Trie只能用来搜索人名了？对应的电话号码怎么存？ 每个trie的node存一个
: 指向电话号码list的指针？
|
r******n
发帖数: 170 | 14 leaf上存一个电话号码（代表那个人的电话号码）？似乎说的通。
但trie里面所有node结构不都一样吗？leaf存，别的地方不存？
简单变化下要求，比如输入一个A,把trie里面A开头的人名的电话都输出，假如还得把
子树都搜索一遍，trie的prefix优势就没出来了吧
【在 a**********2 的大作中提到】
: 3.O(n)使用suffix tree，写个伪代码就可以了吧
: 6.存leaf上不就行了么？从当前节点开始做一个dfs，找到就返回
|
a**********2
发帖数: 340 | 15 难怪面试没通过，我当时就这样答的，不过每个trie的node存一个指向电话号码list的
指针会不会太占空间了？
【在 r******n 的大作中提到】
: leaf上存一个电话号码（代表那个人的电话号码）？似乎说的通。
: 但trie里面所有node结构不都一样吗？leaf存，别的地方不存？
: 简单变化下要求，比如输入一个A,把trie里面A开头的人名的电话都输出，假如还得把
: 子树都搜索一遍，trie的prefix优势就没出来了吧
|
e***s
发帖数: 799 | 16 电话键应该1是什么都没有，2才开始"abc"啊。。。。 |
S*C
发帖数: 161 | 17 re..观察仔细
这个题递归一下就出来了吧
【在 e***s 的大作中提到】
: 电话键应该1是什么都没有，2才开始"abc"啊。。。。
|
b*****c
发帖数: 1103 | |
v***n
发帖数: 562 | |
p*******4
发帖数: 516 | |
|
|
r******n
发帖数: 170 | 21 赞。
随便问问下面2题：
3. longest palindrome.
这题要求写出O(n)的算法吗？还是O(n^2)就OK.
6. design a phonebook, 要求输入人名的时候电话随之更新。比如a给出一个电话，
abc给一个，abcd再更新给出一个电话。trie的implementation, 假设每个节点存一个
数据和26个指针。
那么这个Trie只能用来搜索人名了？对应的电话号码怎么存？ 每个trie的node存一个
指向电话号码list的指针？
【在 n******n 的大作中提到】
: 发Yahoo MS Amazon面经
: 我碰到的 也都是一些还算中规中矩的题 所以 也算是来给各位找工作的打打气！
: Yahoo 电面 印度人
: 1.电话键盘上1-》abc 2->cde... 现在来一堆数，未知长度，比如123456..... 请输出
: 序列可能对应的所有字符串
: 比如 123 输出acf, acg, ach, bcf...
: 2.检测链表是否有环
: 3.sql语句
: employee(id(primary key),name)
: employee_bonus(id(primary key), bonus) （现在觉得这题 似乎有点问题，因为他和
|
a**********2
发帖数: 340 | 22 3.O(n)使用suffix tree，写个伪代码就可以了吧
6.存leaf上不就行了么？从当前节点开始做一个dfs，找到就返回
【在 r******n 的大作中提到】
: 赞。
: 随便问问下面2题：
: 3. longest palindrome.
: 这题要求写出O(n)的算法吗？还是O(n^2)就OK.
: 6. design a phonebook, 要求输入人名的时候电话随之更新。比如a给出一个电话，
: abc给一个，abcd再更新给出一个电话。trie的implementation, 假设每个节点存一个
: 数据和26个指针。
: 那么这个Trie只能用来搜索人名了？对应的电话号码怎么存？ 每个trie的node存一个
: 指向电话号码list的指针？
|
r******n
发帖数: 170 | 23 leaf上存一个电话号码（代表那个人的电话号码）？似乎说的通。
但trie里面所有node结构不都一样吗？leaf存，别的地方不存？
简单变化下要求，比如输入一个A,把trie里面A开头的人名的电话都输出，假如还得把
子树都搜索一遍，trie的prefix优势就没出来了吧
【在 a**********2 的大作中提到】
: 3.O(n)使用suffix tree，写个伪代码就可以了吧
: 6.存leaf上不就行了么？从当前节点开始做一个dfs，找到就返回
|
a**********2
发帖数: 340 | 24 难怪面试没通过，我当时就这样答的，不过每个trie的node存一个指向电话号码list的
指针会不会太占空间了？
【在 r******n 的大作中提到】
: leaf上存一个电话号码（代表那个人的电话号码）？似乎说的通。
: 但trie里面所有node结构不都一样吗？leaf存，别的地方不存？
: 简单变化下要求，比如输入一个A,把trie里面A开头的人名的电话都输出，假如还得把
: 子树都搜索一遍，trie的prefix优势就没出来了吧
|
e***s
发帖数: 799 | 25 电话键应该1是什么都没有，2才开始"abc"啊。。。。 |
S*C
发帖数: 161 | 26 re..观察仔细
这个题递归一下就出来了吧
【在 e***s 的大作中提到】
: 电话键应该1是什么都没有，2才开始"abc"啊。。。。
|
b*****c
发帖数: 1103 | |
q******1
发帖数: 310 | |
