h******8
发帖数: 55 | 1 fail了，说说记得的吧
- You have two arrays X and Y. Each are having say M and N elements already
sorted increasingly. We have to find the k-th largest one of the whole set
M + N elements.
- Simple regular expression match，可以match的符号只有3种：
a-z : match a-z
a+ : match any numbers of a
.+ : repeat 1 - arbitrary times
和没用过regex的同学解释一下 例如
a+b 可以match : ab, aab, aaaaaaaaaaab
b.+b 可以match : bb, bab, b12345b
- boggle puzzle 找到里面所有的单词，写code
- Given preorder of a binary tree, print out all the binary trees
感觉回朔考的很多啊。。。 |
f*******t
发帖数: 7549 | |
x*******6
发帖数: 262 | 3 请问lz regular expression 那题到底问的是什么？ |
t*****g
发帖数: 113 | 4 给个链接吧 谢谢
【在 f*******t 的大作中提到】
: 都是经典题，你有没答上的吗？
|
p*****2
发帖数: 21240 | 5 第一题要求O(n)还是O(logn)呀？ logn的很不好写呀。
.+ : repeat 1 - arbitrary times
这个是repeat 0-arbitrary times吧？ |
w****x
发帖数: 2483 | 6 Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark
Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark
Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark
Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark
Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark
Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark
Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark
Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark
Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark
Mark Mark Mark Mark Mark Mark Mark |
a***o
发帖数: 1182 | 7 可以1呀
【在 p*****2 的大作中提到】
: 第一题要求O(n)还是O(logn)呀？ logn的很不好写呀。
: .+ : repeat 1 - arbitrary times
: 这个是repeat 0-arbitrary times吧？
|
p*****2
发帖数: 21240 | 8
是可以1,我的意思0是最小吧。
【在 a***o 的大作中提到】
: 可以1呀
|
p*****2
发帖数: 21240 | 9
三道题应该练练。
【在 w****x 的大作中提到】
: Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark
: Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark
: Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark
: Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark
: Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark
: Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark
: Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark
: Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark
: Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark
: Mark Mark Mark Mark Mark Mark Mark
|
s********9
发帖数: 586 | 10 O(logn)是怎样的思路？
【在 p*****2 的大作中提到】
: 第一题要求O(n)还是O(logn)呀？ logn的很不好写呀。
: .+ : repeat 1 - arbitrary times
: 这个是repeat 0-arbitrary times吧？
|
|
|
w****x
发帖数: 2483 | 11 这是OnSite的题吧。
1. 有Merge的解法是O(m+n), 可以用二分解法，取median每次淘汰1/4.这题写起code来
edgecase超多
int GetMedian(int a[], int n, int b[], int m, int k)
{
assert(a && b);
if (n <= 0) return b[k-1];
if (m <= 0) return a[k-1];
if (k <= 1) return min(a[0], b[0]);
if (b[m/2] >= a[n/2])
{
if ((n/2 + 1 + m/2) >= k)
return GetMedian(a, n, b, m/2, k);
else
return GetMedian(a + n/2 + 1, n - (n/2 + 1), b, m, k - (n/2 + 1)
);
}
else
{
if ((m/2 + 1 + n/2) >= k)
return GetMedian(b, m, a, n/2, k);
else
return GetMedian(b + m/2 + 1, m - (m/2 + 1), a, n, k - (m/2 + 1)
);
}
}
第二题还算简单
第三题只知道是catalan number算个数, 要打印就是递归把， 但是把树给“打印”出
来。。。。。 |
p*****2
发帖数: 21240 | 12 最后一题，打印很麻烦呀。还没想到好思路。面试肯定挂了。 |
p*****2
发帖数: 21240 | 13
我写了一个打印的练了练手。
def dfs(l,start,end):
if start>end:
return [[]]
else:
ret=[]
for i in xrange(start,end+1):
l1=dfs(l,start+1,i)
l2=dfs(l,i+1,end)
for x in l1:
x.append(l[start])
for y in l2:
tmp=[]
tmp.extend(x)
tmp.extend(y)
ret.append(tmp)
return ret
【在 p*****2 的大作中提到】
: 最后一题，打印很麻烦呀。还没想到好思路。面试肯定挂了。
|
b***e
发帖数: 383 | 14
你也太激动了吧，呵呵。
【在 w****x 的大作中提到】
: Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark
: Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark
: Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark
: Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark
: Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark
: Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark
: Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark
: Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark
: Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark
: Mark Mark Mark Mark Mark Mark Mark
|
M*********n
发帖数: 506 | |
t**5
发帖数: 127 | |
d******a
发帖数: 238 | 17 能否写个c++的并加些注释，这个真看的不太懂。
btw, 这几道题我觉得即使当场写bug-free代码难度也太高了些。
【在 p*****2 的大作中提到】
:
: 我写了一个打印的练了练手。
: def dfs(l,start,end):
: if start>end:
: return [[]]
: else:
: ret=[]
: for i in xrange(start,end+1):
: l1=dfs(l,start+1,i)
: l2=dfs(l,i+1,end)
|
w****x
发帖数: 2483 | 18 打印是打印中序遍历吧, 要么就是打印level by level, 把树打印出来怎么打印??
不管怎么整都得把所有的组合保存下来吧 |
p*****2
发帖数: 21240 | 19
对。inorder打印就行了。
【在 w****x 的大作中提到】
: 打印是打印中序遍历吧, 要么就是打印level by level, 把树打印出来怎么打印??
: 不管怎么整都得把所有的组合保存下来吧
|
p*****2
发帖数: 21240 | 20
C++我不会呀。
其实既然有了preorder了。把inorder打印出来就行了。
preorder+inorder决定了一棵树
【在 d******a 的大作中提到】
: 能否写个c++的并加些注释，这个真看的不太懂。
: btw, 这几道题我觉得即使当场写bug-free代码难度也太高了些。
|
|
|
d******a
发帖数: 238 | |
p*****2
发帖数: 21240 | 22
明天晚上吧。决定用python最后一天了。
【在 d******a 的大作中提到】
: 写个java的也行
|
d******a
发帖数: 238 | 23 好啊，不过我觉得您做题用java好些，不是所有面试官都懂python的 |
p*****2
发帖数: 21240 | 24
我主要是学学python，申请几个python的职位试试。
【在 d******a 的大作中提到】
: 好啊，不过我觉得您做题用java好些，不是所有面试官都懂python的
|
p*****2
发帖数: 21240 | 25 - Simple regular expression match，可以match的符号只有3种：
a-z : match a-z
a+ : match any numbers of a
.+ : repeat 1 - arbitrary times
和没用过regex的同学解释一下 例如
a+b 可以match : ab, aab, aaaaaaaaaaab
b.+b 可以match : bb, bab, b12345b
这道题有个疑问。+是1到多吧？
.+就是任意字符，但是至少要有一个任意字符吧？这样的话，bb就不match "b.+b"了吧？
*是0到多个，所以bb match "b.*b"
我的理解有问题吗？ |
p*****2
发帖数: 21240 | 26
还有a-z也是一个符号吗？
比如a-z+ match a, az, z, abcdefg?
【在 p*****2 的大作中提到】
: - Simple regular expression match，可以match的符号只有3种：
:
: a-z : match a-z
: a+ : match any numbers of a
: .+ : repeat 1 - arbitrary times
:
: 和没用过regex的同学解释一下 例如
: a+b 可以match : ab, aab, aaaaaaaaaaab
: b.+b 可以match : bb, bab, b12345b
: 这道题有个疑问。+是1到多吧？
|
W******g
发帖数: 887 | 27 我觉得吧，这个年代，
Java/C#, Python, C/C++三种语言，连基本语法都不懂的稍有经验的程序员，还是非常
少的。
【在 d******a 的大作中提到】
: 好啊，不过我觉得您做题用java好些，不是所有面试官都懂python的
|
w**z
发帖数: 8232 | 28 完全不懂python
【在 W******g 的大作中提到】
: 我觉得吧，这个年代，
: Java/C#, Python, C/C++三种语言，连基本语法都不懂的稍有经验的程序员，还是非常
: 少的。
|
W******g
发帖数: 887 | 29 你日常用的script语言是什么？Bash? Perl? PowerShell?
非常
【在 w**z 的大作中提到】
: 完全不懂python
|
w****x
发帖数: 2483 | 30
要是有dup呢
【在 p*****2 的大作中提到】
:
: 还有a-z也是一个符号吗？
: 比如a-z+ match a, az, z, abcdefg?
|
|
|
p*****2
发帖数: 21240 | 31
good question. 这个应该跟面试官communicate一下了。你有什么好idea吗？
【在 w****x 的大作中提到】
:
: 要是有dup呢
|
w**z
发帖数: 8232 | 32 script主要用来做build吧。以前用ant,后来用maven就不太写了。新公司用apple,可能
要写些bash.大家都在啥时候用script?coding本身不太用得上。
【在 W******g 的大作中提到】
: 你日常用的script语言是什么？Bash? Perl? PowerShell?
:
: 非常
|
w****x
发帖数: 2483 | 33
我不知道原题是什么, 如果是"打印"二叉树, 那么就不存在这个问题,如果只是输出中
序, 这个就没法区分, 如果真的是"打印", 我就跪了
【在 p*****2 的大作中提到】
:
: good question. 这个应该跟面试官communicate一下了。你有什么好idea吗？
|
h*u
发帖数: 122 | |
l****p
发帖数: 397 | 35 这题如果外层判断用if m/2 + n/2 < k会省点事：
def look_for k, a, b
return b[k] if a.empty?
return a[k] if b.empty?
return a[0]
return a[0]>b[0]? a[0]: b[0] if k == 1
if m/2 + n/2 < k
return look_for k-m/2-n/2, a[m/2+1...a.size], b[n/2+1...b.size]
else # m/2 + n/2 >= k
if b[n/2] > a[m/2]
return look_for k, a, b[0..n/2]
else
return look_for k, a[0..m/2], b
end
end
end
【在 w****x 的大作中提到】
: 这是OnSite的题吧。
: 1. 有Merge的解法是O(m+n), 可以用二分解法，取median每次淘汰1/4.这题写起code来
: edgecase超多
: int GetMedian(int a[], int n, int b[], int m, int k)
: {
: assert(a && b);
: if (n <= 0) return b[k-1];
: if (m <= 0) return a[k-1];
: if (k <= 1) return min(a[0], b[0]);
: if (b[m/2] >= a[n/2])
|
l****p
发帖数: 397 | 36 我觉得这题主要是考怎么构建树，至于树建起来了，怎么展现比较漂亮那是另一回事了
。这年头很少人会考用ASCII字符在控制台上打图形吧。顺便贴上我的实现：
class TreeNode
attr_accessor :value
attr_accessor :left
attr_accessor :right
def initialize value
@value = value
end
end
def get_trees preorder, head=0, tail=preorder.size
return [nil] if tail <= head
trees = []
for right_root in (head+1..tail)
left_trees = get_trees preorder, head+1, right_root
right_trees = get_trees preorder, right_root, tail
left_trees.each do |lt|
right_trees.each do |rt|
root = TreeNode.new preorder[0]
root.left = lt
root.right = rt
trees << root
end
end
end
trees
end
【在 w****x 的大作中提到】
:
: 我不知道原题是什么, 如果是"打印"二叉树, 那么就不存在这个问题,如果只是输出中
: 序, 这个就没法区分, 如果真的是"打印", 我就跪了
|
l****p
发帖数: 397 | 37 我有一次面试最后跟面试官聊过面试语言的问题，我说好像大家推荐用Java，因为比较
通用，他说他比较prefer用Ruby, Python这种比较像伪代码的语言，比较简洁清楚，像
Java, C这些好多花括号看起来吃力。所以我之后练手都用Ruby了
【在 d******a 的大作中提到】
: 好啊，不过我觉得您做题用java好些，不是所有面试官都懂python的
|
w****x
发帖数: 2483 | 38 //Get all trees according to preorder
struct NODE
{
int nVal;
NODE* pLft;
NODE* pRgt;
NODE(int n) : nVal(n), pLft(NULL), pRgt(NULL) {}
};
void GetComb(int a[], int n, vector& vec)
{
if (n <= 0)
return ;
if (n == 1)
{
vec.push_back(new NODE(a[0]));
return;
}
vector vecTmp1;
GetComb(a+1, n-1, vecTmp1);
for (vector::iterator it = vecTmp1.begin();
it != vecTmp1.end(); it++)
{
NODE* pRoot = new NODE(a[0]);
pRoot->pRgt = *it;
vec.push_back(pRoot);
pRoot = new NODE(a[0]);
pRoot->pLft = *it;
vec.push_back(pRoot);
}
for (int i = 1; i < n-1; i++)
{
vector vecLft;
GetComb(a+1, i, vecLft);
vector vecRgt;
GetComb(a+1+i, n-1-i, vecRgt);
for(vector::iterator itl = vecLft.begin();
itl != vecLft.end(); itl++)
{
for(vector::iterator itr = vecRgt.begin();
itr != vecRgt.end(); itr++)
{
NODE* pNode = new NODE(a[0]);
pNode->pLft = *itl;
pNode->pRgt = *itr;
vec.push_back(pNode);
}
}
}
} |
p*****2
发帖数: 21240 | 39
这是ruby吗？
【在 l****p 的大作中提到】
: 我觉得这题主要是考怎么构建树，至于树建起来了，怎么展现比较漂亮那是另一回事了
: 。这年头很少人会考用ASCII字符在控制台上打图形吧。顺便贴上我的实现：
: class TreeNode
: attr_accessor :value
: attr_accessor :left
: attr_accessor :right
:
: def initialize value
: @value = value
: end
|
p*****2
发帖数: 21240 | 40
真牛呀。不过用这些语言写算法的确可以focus在算法本身上。不过有些算法的考点就
体现不出来了。
【在 l****p 的大作中提到】
: 我有一次面试最后跟面试官聊过面试语言的问题，我说好像大家推荐用Java，因为比较
: 通用，他说他比较prefer用Ruby, Python这种比较像伪代码的语言，比较简洁清楚，像
: Java, C这些好多花括号看起来吃力。所以我之后练手都用Ruby了
|
|
|
l****p
发帖数: 397 | 41 Yes
【在 p*****2 的大作中提到】
:
: 真牛呀。不过用这些语言写算法的确可以focus在算法本身上。不过有些算法的考点就
: 体现不出来了。
|
n*******w
发帖数: 687 | 42 都很经典啊。
二维排序矩阵搜索，在leetcode看过各种详细解法。最快是logN。
regex跟boggle都可以递归写出很graceful的代码。
already
set
【在 h******8 的大作中提到】
: fail了，说说记得的吧
: - You have two arrays X and Y. Each are having say M and N elements already
: sorted increasingly. We have to find the k-th largest one of the whole set
: M + N elements.
: - Simple regular expression match，可以match的符号只有3种：
:
: a-z : match a-z
: a+ : match any numbers of a
: .+ : repeat 1 - arbitrary times
:
|
j********e
发帖数: 1192 | 43 二维排序矩阵的搜索有logN的解法呀？我只知道O(M+N)的
【在 n*******w 的大作中提到】
: 都很经典啊。
: 二维排序矩阵搜索，在leetcode看过各种详细解法。最快是logN。
: regex跟boggle都可以递归写出很graceful的代码。
:
: already
: set
|
n*******w
发帖数: 687 | 44 刚搜了下，记错了。
应该一般情况是 O(N)。
某些情况，O(lg n)^2。
http://www.leetcode.com/2010/10/searching-2d-sorted-matrix.html
【在 j********e 的大作中提到】
: 二维排序矩阵的搜索有logN的解法呀？我只知道O(M+N)的
|
w****x
发帖数: 2483 | 45
用二分的方法搜索每个拐点是不是可以到logM + logN
【在 j********e 的大作中提到】
: 二维排序矩阵的搜索有logN的解法呀？我只知道O(M+N)的
|
j*********2
发帖数: 1 | 46 求regex跟boggle都可以递归写出很graceful的代码
【在 n*******w 的大作中提到】
: 都很经典啊。
: 二维排序矩阵搜索，在leetcode看过各种详细解法。最快是logN。
: regex跟boggle都可以递归写出很graceful的代码。
:
: already
: set
|
l****p
发帖数: 397 | 47 弱弱地问，这题跟二维排序矩阵搜索什么关系？
【在 n*******w 的大作中提到】
: 都很经典啊。
: 二维排序矩阵搜索，在leetcode看过各种详细解法。最快是logN。
: regex跟boggle都可以递归写出很graceful的代码。
:
: already
: set
|
n*******w
发帖数: 687 | 48 1. regex
test过了，要源码的话站内吧。
bool regex(char* str, char* pattern)
if(!str && !pattern) return true;
if(!str || !pattern) retrun false;
if(pattern+1 && *(pattern+1) == '-' && pattern+2) //handle a-z
return *str >= *pattern && *str <= *(pattern+2) && regex(str+1,
pattern+3);
if(pattern+1 && *(pattern+1) == '+')
if(*pattern == '.') //handle .+
bool tmp = false;
char* iter = pattern;
while(iter) //iterater over all possible repeated times
++iter;
tmp = tmp || regex(iter, pattern+2);
return tmp; //can optimize here, return true once tmp is true in
loop
else //handle a+
if(*str == *pattern)
//repeat 1 or more times
return regex(str+1, pattern+2) || regex(str+1, pattern);
return false;
return *str == *pattern && regex(str+1, pattern+1);
2. boggle
这个太经典。没做过的话感觉面试只能考虑递归。以前做过的话，可以用数据结构提高
效率。我做过7*7的方格，字典100万单词，需要0.2秒多点，包括所有时间。下面给个
递归的。需要源码的站内。
boggle(char[][] char_map, dict_t dict)
//status_map记录每个位置是不是已经走过
bool[][] status_map = false; //initilized to false
string cur_str;
vector results;
//for each position as starting
for(x is from 0 to char_map.length -1)
for(y is from 0 to char_map[0].length -1)
cur_str=char_map[x][y];
status_map[x][y] = true;
search(char_map, status_map, dict, x, y, cur_str, results);
status_map[x][y] = false;
search(char[][] char_map, bool[][] status_map, dict_t dict, int x, int y,
string cur_str, vector results)
if(dict.contains(cur_str)) results.push_back(cur_str);
if(cur_str.length == MAX_WORD_LEN) return;
for (all 8 possible directions)
next_pos(status_map, x, y, next_x, next_y);
cur_str.append(char_map[next_x][next_y]);
status_map[next_x][next_y] = true;
search(char_map, status_map, dict, next_x, next_y, cur_str, results
);
status_map[next_x][next_y] = false;
next_pos函数需要考虑某一个位置相邻的8个位置是不是valid。并且需要查status_map
，已经走过的地方不valid。
【在 j*********2 的大作中提到】
: 求regex跟boggle都可以递归写出很graceful的代码
|
n*******w
发帖数: 687 | 49 没关系。哈哈。。。
看太快了，看成了矩阵搜索。
不过这个比矩阵搜索还简单。
【在 l****p 的大作中提到】
: 弱弱地问，这题跟二维排序矩阵搜索什么关系？
|
l****p
发帖数: 397 | 50 这段regex的代码是假设必须从字符串的第一个字母开始区配吧，但题中好像没这么要
求。
比如regex("abcdef", "d-f")应该是true，但这个却是false
【在 n*******w 的大作中提到】
: 1. regex
: test过了，要源码的话站内吧。
: bool regex(char* str, char* pattern)
: if(!str && !pattern) return true;
: if(!str || !pattern) retrun false;
: if(pattern+1 && *(pattern+1) == '-' && pattern+2) //handle a-z
: return *str >= *pattern && *str <= *(pattern+2) && regex(str+1,
: pattern+3);
: if(pattern+1 && *(pattern+1) == '+')
: if(*pattern == '.') //handle .+
|
