g****y
发帖数: 240 | 1 第二题，只需要把第一个string中的数字map到第二个string的order就好了。
def reorder(str, order_str):
d = {c:i for i, c in enumerate(order_str)}
str = [c for c in str]
def get_key(c):
if c in d:
return d[c]
else:
return len(d)
str.sort(key=get_key)
return "".join(str) |
|
p*****2
发帖数: 21240 | 2 第一题bfs，第三题trie
第二题忘记spaning tree的算法了。
这是什么公司？ |
|
p*****2
发帖数: 21240 | 3 第一题bfs，第三题trie
第二题忘记spaning tree的算法了。
这是什么公司？ |
|
s*****1
发帖数: 134 | 4 这leetcode 新题 Palindrome Partitioning 我的算法时间是O(N^2)
Palindrome Partitioning2 如果用1的方法做，似乎也就是O(N^2),
但用DP做，似乎要O(N^3),反正我没通过大测试
请问，第二题有没有比第一题简单快速的方法额~DP复杂度也在O(N^2)内
谢谢 |
|
n*******w
发帖数: 687 | 5 第一题可以DP
其实本质上是把set分成两部分使得两部分的差的绝对值最接近0
google MIT balanced partition
第二题是longest increasing sequence的变形
先假设w_j全为非负数
假设L[j]表示ending position在 j 的时候找到的longest increasing sequence
DP[j]表示L[j]这个sequence里边所有元素对应的w之和。
递归式为
DP[j] = max {DP[i]} + w_j
i = [0, j-1] && A[i]
返回结果 max { DP[j] } where j = [0, n-1]
如果所有w_j都等于1，那原题退化成求longest increasing sequence，因为递归式一
模一样。复杂度都是n^2
如果w_j可能为负数，那么上面的递归式里边的w_j 改成 max(0, w_j)
find
.. |
|
l*******g
发帖数: 82 | 6 第一题，suffixtree的话要看如何分词了。而且，suffixtree主要是搜索和搜索的精确
度有帮助，如果已经有neg词典的话就map就好了，然后先确定nag词，然后左右察看临
近词，比如is, not, yet, but之类的。这个感觉更像是machine learning sentiment
analysis。
第二题，那个数学的做法，那位再受累解释一下。没太明白。
第三题我觉得可以用conqure merge的做法，一般题目说有一个大数组，大文件，潜台
词就是最好提供一个可以parallel的处理方式，而且不要试图用用memory来存储太多东
西。
前些天面的EBay， onsite。 |
|
l*******g
发帖数: 82 | 7 第一题，suffixtree的话要看如何分词了。而且，suffixtree主要是搜索和搜索的精确
度有帮助，如果已经有neg词典的话就map就好了，然后先确定nag词，然后左右察看临
近词，比如is, not, yet, but之类的。这个感觉更像是machine learning sentiment
analysis。
第二题，那个数学的做法，那位再受累解释一下。没太明白。
第三题我觉得可以用conqure merge的做法，一般题目说有一个大数组，大文件，潜台
词就是最好提供一个可以parallel的处理方式，而且不要试图用用memory来存储太多东
西。
前些天面的EBay， onsite。 |
|
w****2
发帖数: 3 | 8 请问你做了他家的online test么， 我明天做， 可以问下你做的是啥题目么？
我同学12月面的做了
第一题： leetcode 原题 single number I
第二题： 找出一个矩阵里“平衡数”的总个数 |
|
z*****u
发帖数: 3010 | 9 第二题
第一次 肯定能够选一个 概率 1， 期望1/1
第二次 5个选4个 4/5 5/4
3 5 3 3/5 5/3
...... |
|
w********s
发帖数: 1570 | 10 来自主题: JobHunting版 - T店面两题 很老的题了，第一题起码给个Olgn吧
第二题不就是计算C(m + n, n)么 |
|
l***i
发帖数: 1309 | 11 topcoder上这么难的题不是也有一堆人10分钟就能写完通过的
简单题确实应该一遍过，不然第二题就没时间了。 |
|
w********0
发帖数: 377 | 12 他当时说不用考虑相等的情况。那个return可能我写的时候太紧张，写错了。他当时说
的，不要管syntax error，因为这个在IDE里很容易检测出来。莫非是因为这个code的
没写好？ 他也没说不要用递归。当时写完之后，他说，第一道题，就是一个小题，很
简单。没啥。 然后就给我第二题了。 |
|
w****a
发帖数: 710 | 13 第二题G考过，也是高频题之一，
在glass door上看过完整题：
After given clearly definition of UTF-8 format. ex: 1-byte : 0b0xxxxxxx 2-
bytes:.... Asked to write a function to validate whether the input is valid
UTF-8. Input will be string/byte array, output should be yes/no.
基本上就是bit manipulation的题目
你可以看下这个答案能不能用
http://stackoverflow.com/a/13161464/2954435 |
|
|
B********4
发帖数: 7156 | 15 我认为第二题肯定不是O(1)。
比如一个已经排序数组 1，2，3，4，5，6，7，8，9.
按照代码，如果我要搜索1，
第一步，找到5，不对，往下挪一个，
第二步找到4，不对，往下挪一个，
。。。。
第五步找到1.
如果有1000个数，那就要找500次。 |
|
c****a
发帖数: 50 | 16 第一次的电面题版上有版友发过了
开始5分钟左右互相自我介绍
第一题
设计hashtable，考虑线程安全，数据增加的时候怎么办，不用写代码只要说就行了
大概用了十分钟
第二题
implement Arrays.sort(Object[] a);
//1. Mutate input or return your own array
//2. I value run time over memory usage. Ideally both should be as minimal
as possible, but I prefer faster runtime.
//3. You can assume that all the objects in the array 'a' all implement the
comparable interface.
我折腾了半个多小时写了个merge sort
估计没有戏了，心哇凉哇凉的 |
|
c******h
发帖数: 46 | 17 问一道L家烂大街的题 nestedint reversed weighted sum
Compute the reverse depth sum of a nested list meaning the reverse depth of
each node (ie, 1 for leafs, 2 for parents of leafs, 3 for parents of parents
of leafs, etc.) times the value of that node.
这个例子应该怎么算?
{{1,2}, 1, {2, {2,1}}} = ?
{1,2}的weight应该是1 还是2?按照定义它应该是leaf吧 所以应该是
(1+2)*1 + 1 * 3 + (2*2 + (2+1) * 1) = 13?
对说好的FG面经
F考了个BST里面找successor 就一题 各种变 有parent 没parent 用stack不用stack
G家考了俩 第一个是给了两个有重复元素的list 求差集 第二题是LC min stack变种
维护最小次小元素 |
|
c******h
发帖数: 46 | 18 问一道L家烂大街的题 nestedint reversed weighted sum
Compute the reverse depth sum of a nested list meaning the reverse depth of
each node (ie, 1 for leafs, 2 for parents of leafs, 3 for parents of parents
of leafs, etc.) times the value of that node.
这个例子应该怎么算?
{{1,2}, 1, {2, {2,1}}} = ?
{1,2}的weight应该是1 还是2?按照定义它应该是leaf吧 所以应该是
(1+2)*1 + 1 * 3 + (2*2 + (2+1) * 1) = 13?
对说好的FG面经
F考了个BST里面找successor 就一题 各种变 有parent 没parent 用stack不用stack
G家考了俩 第一个是给了两个有重复元素的list 求差集 第二题是LC min stack变种
维护最小次小元素 |
|
e*******g
发帖数: 1488 | 19 第二题...我能弱弱得说一下么？这题是我当年面试我老板研究生出的题，怎么会一模
一样...我当时选得就是1-10. |
|
r*g
发帖数: 186 | 20 第二题第二问 下午发了删了 朋友说是对的就又发上来了
bool canIWin(int, std::vector &v, int sum, int obj)
{
for(int i = 1; i < v.size(); ++i){
if(v[i]){
if(sum + i >= obj){
return true;
}else{
v[i] = false;
bool res = canIWin(2, v, sum + i, obj);
v[i] = true;
if(!res){
return true;
}
}
}
}
return false;
}
int main()
{
std::vector... 阅读全帖 |
|
t********n
发帖数: 611 | 21 不好意思，代码很乱很丑哈，反正做作业，只关心结果和运行时间。
是那门algorithms: design and analysis, part 2 的 第二周课后编程作业第二题。 |
|
j*********5
发帖数: 362 | 22 我就是写得不好。
我有两道题解得一般。第一题是真心没见过比较难，一开始走错路了，浪费15分钟，所
以最后没写完，但思路肯定是对的（虽然未必是最优解）；
第二题就更可惜了，我面经见过，但当时没有细写，所以最后写得板书比较乱，解法肯
定没错，但评价不高；
所以我觉得我之所以fail，还是因为练习不够，写得不好。电脑上刷题跟黑板上写还是
有点不一样的，没处理好。
当然，有一个原因也是，最近工作实在太忙了，根本没时间练习。
此外，我个人觉得，纠结于科班不科班意义不大。尤其是有工作经验的，其实这些大公
司都非常精明的，更多是看基本功和能不能干活。
google
cs |
|
发帖数: 1 | 23 来自主题: JobHunting版 - 求3题思路 第一题：类似于求Subset问题(不包含重复元素)。时间复杂度O(2^n)
第二题：Celebrity问题，一头一尾指针分别从头、尾两个方向向中间靠拢，每次都可
以淘汰一个元素，拿到备选元素之后再扫一遍原来的数组来确认找到的元素为最终结果
。时间复杂度O(n), n为数组长度。
第三题：分别从左往右、从右往左扫描两遍字符串即可，时间复杂度O(n), n为字符串
长度。
,3
follow |
|
f****n
发帖数: 399 | 24 yep，第一题我现在都会，第二题十年前的我才会。 |
|
m**********7
发帖数: 2191 | 25 靠，你个撮鸟真是小人之心。俺要是不知道俺下次爬着进SVTTC。你那个第二题基本是
裁判考试必考题。
其实考个umpire大都是这些少见的非常规情况，如果一场常规的比赛没有意外哪有什么
可说道的，不就是数数吗？
interrupted |
|
i*********s
发帖数: 8706 | 26 第一二题不会
第三题连题都没看明白
100的。 |
|
c*******s
发帖数: 6 | 27 【 以下文字转载自 JobHunting 讨论区 】
发信人: HNM (如是我闻), 信区: JobHunting
标 题: 这个Binary Tree的题来看看
发信站: BBS 未名空间站 (Sun Dec 20 19:47:42 2009, 美东)
1. given a binary tree ,find the largest sub-tree which is a BST...(largest
mea
ns subtree having largest no of nodes in it)
我的理解是subtree就是说是一个子树,比如要到原来树的leaf,而不能把原来树的inter
nal nodes做leaf.也就是不能中间截一块,是这样的吗?
有什么好方法.我写的特别繁琐.if else 很多,用recursion.
2. 第二题说,design n stacks in an array of N. 这个我想愿意肯定不是让一个
stack分派固定的.感觉是要综合调配的,比如,如果array还有空,就不能说某个stack不
能加入了.我
想法是keep一个free l |
|
a*******s
发帖数: 79 | 28 第一题可以用hash,只要26个表元就行，复杂度O(n)
第二题就是个图的遍历算法，DFS,stack实现比较简单，主要就是看看你API的定义能力
第三题是不是考格式调整？左对齐，右对齐和左右都对齐？我觉得这个不是太难，就是
计算子串在绘图空间里面的实际长度，注意切分字串时考虑远东语言等情况。 |
|
a*******s
发帖数: 79 | 29 第一题可以用hash,只要26个表元就行，复杂度O(n)
第二题就是个图的遍历算法，DFS,stack实现比较简单，主要就是看看你API的定义能力
第三题是不是考格式调整？左对齐，右对齐和左右都对齐？我觉得这个不是太难，就是
计算子串在绘图空间里面的实际长度，注意切分字串时考虑远东语言等情况。 |
|
z****e
发帖数: 54598 | 30 【 以下文字转载自 JobHunting 讨论区 】
发信人: qdream (q dream), 信区: JobHunting
标 题: Re: T店面两题
发信站: BBS 未名空间站 (Thu Jun 12 20:22:07 2014, 美东)
第二题有个很简单的公式，( m+n-2) choose (m-1) |
|
l*********8
发帖数: 4642 | 31 逐个扫描数组元素，依次插入下面这样的二叉树
struct BinaryTreeNode {
int subNodeCount;
int val;
BinaryTreeNode * left;
BinaryTreeNode * right;
};
在插入元素x[i]的同时，也容易求得二叉树中比x[i]小的元素的数目k[i], 也就是比x[
i]小，并且位于x[i]之前的元素个数.
swap总数就是： sum(x[i] - k[i]), i from 0 to n-1
每次插入二叉树， O(logn)
n个元素， 总共 O(n*logn) |
|
e****e
发帖数: 2010 | 32 第一题没包子了，第二题，First答出的有5个包子 |
|
q*********u
发帖数: 280 | 33 hash恐怕那些整数不适合当key, 如果是后面名字当key的话，没办法做value1+value2=
sum了，其实这个题复习了，可惜就是没事先写出来，写出来就能抄了。
好像跟范围也没太大关系吧？
或者空间没限制，直接用hash，不用sort |
|
a**********s
发帖数: 588 | 34 第一题不知道，瞎说的话我会说是3
第二题应该是17
这样的题目好像有点运气的成分 |
|
m*****g
发帖数: 226 | 35 第一题如果没有特别范围的话，只是1million的话可以直接在内存里面搞了。
第二题，32bit的int,一共也就4billion多点。是否可以二分法。
第三提不知
第四 二分 |
|
x****k
发帖数: 2932 | 36 第一题应该是 static const int SIZE = 100;（Effective C++, 3rd edition
, item 2）
具体结果depends compiler和编译选项。32 24是可能值之一。g++下是28 20，static
const int size不占sizeof的空间，按照4byte alignment。
可以用 -fdump-class-hierarchy dump出class的layout文件。
第二题在C++ compiler下应该是不确定。但我见过的编译器都是从右到左进行参数计算
，但g++会给warning “test.cpp:28: warning: operation on ‘i’ may be
undefined”，
test.cpp line 28 is like "fun(i++, i++)"
Effective C++, 3rd edition, item 17, P76
C++ compilers are granted considerable latitude in determining the ord |
|
w*****e
发帖数: 158 | 37 来自主题: JobHunting版 - 两道算法题 1) given the whole range of 6 digit numbers, design an algorithm which
prints out numbers which have the sum of the right 3 digits equal the left
3 digits? like 123600, 345435 etc.
2）design an algorithm to find square_root of a float? how do you make the
algorithm efficient?
第一题：除了每个数检验之外，还有什么更快得方法吗？
第二题：貌似可以用bisection method 或者 Newton method， Newton method 收敛的
更快
一些。有什么地方需要注意或者可以改进，使得算法更有效？
希望大家指正，先谢谢了。 |
|
j********x
发帖数: 2330 | 38 第一题主要考虑稀疏图的存储吧，sparse matrix相关的可以看看
第二题，可以考虑random algo；
任选一列，排除有“1”的行；
在余下的行继续这么搞；
复杂度取决于“1”分布的比例；worst case当然是N^2 |
|
s*******e
发帖数: 93 | 39 第二题应该可以把这个array的index % 3
=0的存一个stack
=1的存一个stack
=2的存一个stack
3个int分别用来记录3个end
不知道还会不会接着考比如一个stack空间用光了怎么从另一个借？
第一题我猜方向是用 quickselect algorithm 找大小排第 N^2/2的数，
复杂度应该是O(N^2)。
然后可以利用young tableaux的特性省略一些比较来加速。
比如第一次选m为x=N/2, y=N/2的位置的数，
然后只要满足 (x<=N/2 && y<=N/2)的数都一定小于m.
满足 (x>=N/2 && y>=N/2)的数都一定大于m.
还有一种想法是把young's tableaux merge成一个sorted array. 有点像N－way merge
但可以更快，因为两个方向都有排序。
以上都是我的猜测。有没有谁知道最好的答案呢？ |
|
X*********n
发帖数: 570 | 40 你这两个方法也是我想的 但是
第二题,如果一个stack用的太快,worst case array的利用率只有1/3, 我想的是两个
stack从两头开始,第三个从中间开始,然后左右交替向两边扩展,但是这样worst case也
只有1/2的利用率
第一题,有没有nlogn的方法? 我想是不是能把矩阵切成四份,
|a b|
|c d|
那median只会在矩阵中心或者是b和c自矩阵中,剪掉了一半, 但是接下去似乎就不行了.
希望版上大牛给些意见 |
|
s*******e
发帖数: 93 | 41 我不知道以前讨论的结果，不过第一题用suffix tree 应该就可以了吧
*
j i m
i m
m
第二题反查的话需要做到用号码的一部分也查出人名吗？如果只需要通过完整的号查出
人名就hash就好了吧（好像iPhone 4就只能这样）。 |
|
l********y
发帖数: 1327 | 42 之前有人发过：
1. 写一个程序，模拟投硬币的过程，每次投硬币，直到出现正面为止，返回之前出现
反面的次数
2. 重复N次上述的过程，问一共出现多少次反面
第一题比较简单，第二题算一个期望值，就是一个等比数列的求和问题，
还有人贴个解：
1. E(Xi)=1/2 + 1/4 + 1/8 + ... = 1
2. E(Xn) = SUM_i(E(Xi) = N
这个解没看懂，重复N次投硬币，每次不都是1/2吗？那总共N/2？
和求期待值什么关系？ |
|
l********y
发帖数: 1327 | 43 之前有人发过：
1. 写一个程序，模拟投硬币的过程，每次投硬币，直到出现正面为止，返回之前出现
反面的次数
2. 重复N次上述的过程，问一共出现多少次反面
第一题比较简单，第二题算一个期望值，就是一个等比数列的求和问题，
还有人贴个解：
1. E(Xi)=1/2 + 1/4 + 1/8 + ... = 1
2. E(Xn) = SUM_i(E(Xi) = N
这个解没看懂，重复N次投硬币，每次不都是1/2吗？那总共N/2？
和求期待值什么关系？ |
|
|
|
s***n
发帖数: 459 | 46 来自主题: JobHunting版 - 两个店面题 1－ 倒着打印单链表
2－ SQL里每个公司对应多条销售额，输出一条总销售额。例如：
Amazon 200
eBay 500
Amazon 300
eBay 250
输出：
Amazon 500
eBay 750
第一题另做了一个倒向链表，第二题先sort后遍历另做了一个表。估计挂了。
不知道还能有啥好办法。 |
|
P**l
发帖数: 3722 | 47 第一题yes
第二题map跟后面那两没啥关系吧。区别是没顺序？
vector跟array有啥区别不知道。是不是应该跟不同语言/库的实现有关啊
(n) can be
n) = |
|
p****e
发帖数: 37 | 48 楼上两个都对。
第一题我觉的比较tricky的地方是两个人可能没有关系，disjointed set是比较适合的
data structure。
我一开始用了一些图的算法来处理这个问题，折腾到最后才想到disjointed set。。
后来一翻书algorithm in C第一章就讨论了一个差不多的问题（更简单些），懊恼啊。。
第二题想到用LCS就没什么难度了。。 |
|
t******e
发帖数: 98 | 49 要我解的话，
第一题transitive closure
第二题edit distance |
|
