M7
发帖数: 219 | 1 来自主题: JobHunting版 - MS面经。 非名校CS PHD, 5月毕业。去年12月网投的，一周后说要电面。
电面：
1. 博士做什么题目？最挑战的部分是什么？
2. If you started this (your research) over, what do you want to do first fo
r the same project?
3. What is a good program?
4. Why do you rate your preferences for SDE, SDET and PM. 我当时perfer SDE。
面试官要我be flexible.
5. A game is about to ship, how do you want to to test it?
6. Given a year and unlimited funding, what do you want to do?
没有coding问题。说是三到四周给回音。结果两天后（而且是在周末）recruiter就说通
过了。要onsite SDET。
Onsite:
10:30和recruiter聊了一下: why MS?
11... 阅读全帖 |
|
x*****3
发帖数: 25 | 2 电面第一个是烙印面试官
1. reverse a string很简单
2. Assume we have n people. Each one has a starting time and ending
time. For any people, set flag to true if his/her time range overlaps
with anyone else's.
3. Find a connection between two people if there is one, or return
false. Each people has father and mother and the connection means if
there's any common relatives. This problem is to find the common node of
two binary trees.
电面第二个是中国人面试官
1. print a binary tree level by level
2. how to represent a tree in... 阅读全帖 |
|
i*****f
发帖数: 578 | 3 括号那题.基本思路是一个stack，遇到（就push，）就pop，如果stack空了，就不能继
续append ）。一共给N个（和N个），用完就不能再用。
递归来做.
'''List all legal combination of N pairs of parentheses.'''
def F(B, A0, A1):
if A0>0:
for res in F(B+[1], A0-1, A1):
yield [0]+res
if A1>0 and len(B):
for res in F(B[:-1], A0, A1-1):
yield [1]+res
if A0==A1==0: yield []
#### tests #####
def print_as_parentheses(a):
for b in a:
if b == 0: print '(',
else: print ')',
print
N = 4
for x in F... 阅读全帖 |
|
x****1
发帖数: 118 | 4 1.print a binary tree level by level
1.print all the legal combinations of n parentheses. (()()) is legal; )
(())( is not.
2. how to design data structures for a facebook network and how to
design an algorithm to find connection? How to optimize it if data is
distributed into multiple computers?
3.design a deck class and member function to randomly select a card from
those cards which haven't been selected before. (You can assume the
number of this function call will never be larger than the num... 阅读全帖 |
|
x****3
发帖数: 62 | 5 刚拿到书, 还没看. 题是从http://www.crackingthecodinginterview.com考的. 感觉跟第4版差别不大.
Chapter 1 Arrays and Strings
1.1 Unique Characters in String
1.2 Reverse String in C
1.3 Check Permutation
1.4 Replace Spaces
1.5 String Compression
1.6 Rotate Image / Matrix
1.7 Set Row or Column to 0
1.8 Check Rotation Using isSubstring
Chapter 2 Linked Lists
2.1 Remove Duplicates
2.2 Find kth to Last Element
2.3 Delete Node from Middle
2.4 Partition List
2.5 Add Two Lists
2.6 Get Front of Loop in Circular List
2.7 Check ... 阅读全帖 |
|
x****3
发帖数: 62 | 6 刚拿到书, 还没看. 题是从http://www.crackingthecodinginterview.com考的. 感觉跟第4版差别不大.
Chapter 1 Arrays and Strings
1.1 Unique Characters in String
1.2 Reverse String in C
1.3 Check Permutation
1.4 Replace Spaces
1.5 String Compression
1.6 Rotate Image / Matrix
1.7 Set Row or Column to 0
1.8 Check Rotation Using isSubstring
Chapter 2 Linked Lists
2.1 Remove Duplicates
2.2 Find kth to Last Element
2.3 Delete Node from Middle
2.4 Partition List
2.5 Add Two Lists
2.6 Get Front of Loop in Circular List
2.7 Check ... 阅读全帖 |
|
f*******t
发帖数: 7549 | 7 这次申full-time两轮电面后被拒，干脆把面经发出来攒rp。因为没有on-site经验，题
目参考作用一般吧。
首先是申summer intern时的两次电面。记不清楚了，能想起多少coding题就写多少，
杂七杂八的问题就忽略了。当时准备得不充足，答得不太好，居然能过电面，实在幸运。但最终也没
能去成……
第一面，三哥：
1. A string consists of parentheses and brackets for example "(()([]))",
check if it is well formed. 经典题，我用stack做的。刚才顺手看了下当时写的代码，发
现还是有bug……
2.Given strings like "CB", "BD", "DE", find the sequence of alphabets.
The result is "CBDE" for the example. 当时完全没头绪，后来跟朋友讨论，解法是基本
算法Topsort。
第二面，大概是老美：
1. Verify whether a string contains all t... 阅读全帖 |
|
n*******w
发帖数: 687 | 8 1. A string consists of parentheses and brackets for example "(()([]))",
check if it is well formed.
用stack。遇到( 和 [ 入栈，遇到 ) 或者 ] 查栈顶是不是匹配。不匹配return false
。否则pop栈顶继续。到string结束，return true。
2. Given strings like "CB", "BD", "DE", find the sequence of alphabets.
The result is "CBDE" for the example.
topsort。重点是考虑node的入度和出度。有环的话可以检测出来。
3. Verify whether a string contains all the characters of another
string.
简单的数组，当做hashtable用。
4. Given two strings that one string contains the other string, while
th... 阅读全帖 |
|
S**I
发帖数: 15689 | 9 ☆─────────────────────────────────────☆
gzou (gzou) 于 (Thu May 12 02:26:35 2011, 美东) 提到:
马上就要G on site了，
求祝福。
下面是从本版收集到的Google的试题，便于大家查询。
申明：有的附带有解释说明的，也来自于本版或者网络，大家自己看， 不保证真确
http://www.mitbbs.com/article_t1/JobHunting/31847453_0_1.html
本人ECE fresh PhD，背景是电路/EDA，跟G业务基本没什么关系
同学内部推荐的，很简单的一次电面就给了onsite
题都不难，但是自己没把握好机会，出了一些小bug。
总的感觉，出错就是硬伤，宁可从最简单的算法写起，也不能出错。
电面：
1，Skip list， http://en.wikipedia.org/wiki/Skip_list
写code实现struct skip_list * find(struct skip_list *head, int value)
2，sorted array... 阅读全帖 |
|
S**I
发帖数: 15689 | 10 ☆─────────────────────────────────────☆
gzou (gzou) 于 (Thu May 12 02:26:35 2011, 美东) 提到:
马上就要G on site了，
求祝福。
下面是从本版收集到的Google的试题，便于大家查询。
申明：有的附带有解释说明的，也来自于本版或者网络，大家自己看， 不保证真确
http://www.mitbbs.com/article_t1/JobHunting/31847453_0_1.html
本人ECE fresh PhD，背景是电路/EDA，跟G业务基本没什么关系
同学内部推荐的，很简单的一次电面就给了onsite
题都不难，但是自己没把握好机会，出了一些小bug。
总的感觉，出错就是硬伤，宁可从最简单的算法写起，也不能出错。
电面：
1，Skip list， http://en.wikipedia.org/wiki/Skip_list
写code实现struct skip_list * find(struct skip_list *head, int value)
2，sorted array... 阅读全帖 |
|
|
b******t
发帖数: 965 | 12 leetcode online judge上的题
各位大拿说说看 |
|
s********y
发帖数: 40 | 13 正走一遍，反走一遍？ 写了个C++的：
int longestValidParentheses(string s)
{
int counter = 0;
int ret = 0;
int curr_max = 0;
//forward path
for(size_t i = 0 ; i < s.length() ; i++)
{
if(s[i] == '(')
{
counter++;
curr_max++;
}
else if(s[i] == ')')
{
counter--;
curr_max++;
}
if(counter == 0)
ret = ret >= curr_max ? ret : curr_max;
else if(counter < 0)
{
... 阅读全帖 |
|
|
|
|
w****x
发帖数: 2483 | 17 int longestValidParentheses(const char* str) {
assert(str);
int nMax = 0;
const char* p = str;
stack stk;
while (*p != 0)
{
if (*p == '(')
stk.push(p);
else if (*p == ')')
{
if (!stk.empty() && *stk.top() == '(')
{
stk.pop();
nMax = max(p - (stk.empty() ? str-1 : stk.top()), nMax);
}
else stk.push(p);
}
p++;
}
return nMax... 阅读全帖 |
|
c*****e
发帖数: 3226 | 18 那也不需要阿。 比如：((()
扫描到 最后一个"(", count = 3; len = 3;
扫描下一个")", count = 2; len = 4;
因此，最长的字串就应该是 len - count = 2;
再比如：((()()
接着上面的例子，
扫描到 最后一个"(", count = 3; len = ５;
扫描下一个")", count = 2; len = ６;
因此，最长的字串就应该是 len - count = ４;
因此扫描２遍似乎不需要,只要cout < 0 的时候重新reset 就好了。
ｃｏｄｅ:
public static int longestValidParentheses(String s) {
int n = s.length();
int maxl = 0;
int count = 0;
int len = 0;
for(int i = 0;i < n;i++){
if(s.charAt(i) == '('){
count++;
len++... 阅读全帖 |
|
|
c*****e
发帖数: 3226 | 20 哦，对的。不过还是觉得扫描２次这个方法很蠢。
搜了一下，网上有别的解法，而且通过了leetcode online judge.
public static int longestValidParentheses(String s) {
Stack stack = new Stack();
int len = 0;
int maxLen = 0;
int startIndex = s.length();
for(int i = 0; i < s.length(); ++i) {
if(s.charAt(i) == '(') {
stack.push(i);
continue;
}
if(stack.isEmpty()) {
startIndex = s.length();
} else {
... 阅读全帖 |
|
d****n
发帖数: 233 | 21 I like wwwyhx's solution |
|
|
w*********0
发帖数: 48 | 23 O(n)
import java.util.*;
public class Solution {
public int longestValidParentheses(String s) {
// Start typing your Java solution below
// DO NOT write main() function
if (s == null || s.length() == 0) return 0;
ArrayList pos = new ArrayList();
HashMap pair = new HashMap();
int len = s.length();
int max = 0;
for (int i = 0; i < len; i++) {
if (s.charAt(i) == '(')... 阅读全帖 |
|
l**********1
发帖数: 415 | 24 use stack , every easy to get O(n) |
|
b******t
发帖数: 965 | 25 leetcode online judge上的题
各位大拿说说看 |
|
s********y
发帖数: 40 | 26 正走一遍，反走一遍？ 写了个C++的：
int longestValidParentheses(string s)
{
int counter = 0;
int ret = 0;
int curr_max = 0;
//forward path
for(size_t i = 0 ; i < s.length() ; i++)
{
if(s[i] == '(')
{
counter++;
curr_max++;
}
else if(s[i] == ')')
{
counter--;
curr_max++;
}
if(counter == 0)
ret = ret >= curr_max ? ret : curr_max;
else if(counter < 0)
{
... 阅读全帖 |
|
|
|
|
w****x
发帖数: 2483 | 30 int longestValidParentheses(const char* str) {
assert(str);
int nMax = 0;
const char* p = str;
stack stk;
while (*p != 0)
{
if (*p == '(')
stk.push(p);
else if (*p == ')')
{
if (!stk.empty() && *stk.top() == '(')
{
stk.pop();
nMax = max(p - (stk.empty() ? str-1 : stk.top()), nMax);
}
else stk.push(p);
}
p++;
}
return nMax... 阅读全帖 |
|
c*****e
发帖数: 3226 | 31 那也不需要阿。 比如：((()
扫描到 最后一个"(", count = 3; len = 3;
扫描下一个")", count = 2; len = 4;
因此，最长的字串就应该是 len - count = 2;
再比如：((()()
接着上面的例子，
扫描到 最后一个"(", count = 3; len = ５;
扫描下一个")", count = 2; len = ６;
因此，最长的字串就应该是 len - count = ４;
因此扫描２遍似乎不需要,只要cout < 0 的时候重新reset 就好了。
ｃｏｄｅ:
public static int longestValidParentheses(String s) {
int n = s.length();
int maxl = 0;
int count = 0;
int len = 0;
for(int i = 0;i < n;i++){
if(s.charAt(i) == '('){
count++;
len++... 阅读全帖 |
|
|
c*****e
发帖数: 3226 | 33 哦，对的。不过还是觉得扫描２次这个方法很蠢。
搜了一下，网上有别的解法，而且通过了leetcode online judge.
public static int longestValidParentheses(String s) {
Stack stack = new Stack();
int len = 0;
int maxLen = 0;
int startIndex = s.length();
for(int i = 0; i < s.length(); ++i) {
if(s.charAt(i) == '(') {
stack.push(i);
continue;
}
if(stack.isEmpty()) {
startIndex = s.length();
} else {
... 阅读全帖 |
|
d****n
发帖数: 233 | 34 I like wwwyhx's solution |
|
|
w*********0
发帖数: 48 | 36 O(n)
import java.util.*;
public class Solution {
public int longestValidParentheses(String s) {
// Start typing your Java solution below
// DO NOT write main() function
if (s == null || s.length() == 0) return 0;
ArrayList pos = new ArrayList();
HashMap pair = new HashMap();
int len = s.length();
int max = 0;
for (int i = 0; i < len; i++) {
if (s.charAt(i) == '(')... 阅读全帖 |
|
l**********1
发帖数: 415 | 37 use stack , every easy to get O(n) |
|
l*****a
发帖数: 559 | 38 这题大家都给的是代码，没有给讲解。
O（n）one pass的解法看着挺费劲的。 |
|
l*****a
发帖数: 14598 | 39 简单说就用ArrayList存字符的index,
如果当前字符是')', s.charAt(list.size()-1)=='('
remove the end of list
最后你会得到一个保存那些没有match的index的list
比方说[2,5,12] 字符串长度 len
then 0,1 is a match, 3,4 is a match 6,7,8,9,10,11 is a match
len-12-1 is a match
pick up the largest among them |
|
s****0
发帖数: 117 | 40 O(n). 其实挺tricky的。写的时候没注意到()()这种情况。
public int longestValidParentheses(String pr) {
int[] lv = new int[pr.length() + 1];
int curLv = 0;
char[] p = pr.toCharArray();
int len = 0;
lv[0] = -1;
for (int i = 0; i < pr.length(); i++) {
if (p[i] == '(') {
curLv++;
lv[curLv] = i;
} else if (p[i] == ')') {
if (curLv == 0) {
lv[0] = i;
continue;... 阅读全帖 |
|
l*****a
发帖数: 14598 | 41
为什么没注意到
不是有match就popup吗 |
|
s****0
发帖数: 117 | 42 写的时候觉得match（*）完了就完了，没注意到后面还有一个()。
所以在计算的时候，要从下一层算起。就像这样
(****()
i i+1
在层i+1的时候，****部分一定是matched，只要从层i的开头算就对了。 |
|
s******e
发帖数: 146 | 43 我今天也正好做到这个。
想法是存上每个‘（’之前已经匹配的括号数量。
比如
（）（（）（）（（）
第1次遇到前括号，入栈数字是0，然后遇到后括号，现在的长度是2+0
第2次遇到前括号，入栈数字是2，当前长度重设为0
第3次遇到前括号，入栈数字是当前长度0.然后后括号，出栈，长度是2+0，
第4次遇到前括号，入栈数字是当前长度2.然后后括号，出栈，长度是2+2，
第5次遇到前括号，入栈数字是当前长度4，当前长度重设为0
第6次遇到前括号，入栈数字是当前长度0，遇到后括号，出栈，长度是2.
如果栈内仍有数字，目前是2，4，则全部出栈，和当前长度2比。取最长为4.
public class Solution {
public int longestValidParentheses(String s) {
// Start typing your Java solution below
// DO NOT write main() function
Stack stack = new Stack();
... 阅读全帖 |
|
w***o
发帖数: 109 | 44 拿这个练练DP：
public int longestValidParentheses(String s) {
int n = s.length();
int[] dp = new int[n+1];
int max = 0;
for(int i = n-2; i >= 0; i--) {
if(s.charAt(i) == '(') {
int j = i+1+dp[i+1];
if(j < n && s.charAt(j) == ')') {
dp[i] = 2+dp[i+1]+dp[j+1];
max = Math.max(max, dp[i]);
}
}
}
return max;
} |
|
j******s
发帖数: 48 | 45 扫描两遍的好处是constant space... |
|
l*****a
发帖数: 559 | 46 这题大家都给的是代码，没有给讲解。
O（n）one pass的解法看着挺费劲的。 |
|
l*****a
发帖数: 14598 | 47 简单说就用ArrayList存字符的index,
如果当前字符是')', s.charAt(list.size()-1)=='('
remove the end of list
最后你会得到一个保存那些没有match的index的list
比方说[2,5,12] 字符串长度 len
then 0,1 is a match, 3,4 is a match 6,7,8,9,10,11 is a match
len-12-1 is a match
pick up the largest among them |
|
s****0
发帖数: 117 | 48 O(n). 其实挺tricky的。写的时候没注意到()()这种情况。
public int longestValidParentheses(String pr) {
int[] lv = new int[pr.length() + 1];
int curLv = 0;
char[] p = pr.toCharArray();
int len = 0;
lv[0] = -1;
for (int i = 0; i < pr.length(); i++) {
if (p[i] == '(') {
curLv++;
lv[curLv] = i;
} else if (p[i] == ')') {
if (curLv == 0) {
lv[0] = i;
continue;... 阅读全帖 |
|
l*****a
发帖数: 14598 | 49
为什么没注意到
不是有match就popup吗 |
|
s****0
发帖数: 117 | 50 写的时候觉得match（*）完了就完了，没注意到后面还有一个()。
所以在计算的时候，要从下一层算起。就像这样
(****()
i i+1
在层i+1的时候，****部分一定是matched，只要从层i的开头算就对了。 |
|
