由买买提看人间百态

topics

全部话题 - 话题: algo
首页 上页 1 2 3 4 5 6 7 8 9 10 下页 末页 (共10页)
a****n
发帖数: 230
m********i
发帖数: 298
2
来自主题: JobHunting版 - 让人沮丧的Goog电话面试
Solve Problem 1:
1. Sort to continuous memory block.
2. !memcmp(a,b) (which is much faster than you do element compare).
or even faster:
3. http://www-igm.univ-mlv.fr/~lecroq/string/index.html
check for Boyer-Moore algorithm
in terms of performance:
a.memcmp 530ms
b.bm algo 70ms
w******1
发帖数: 520
3
如果想讨论这个问题的话, 我们从招聘的过程来分析,而不是凭着感觉瞎猜。
用女程序员来举例:
1. resume : 无论你漂亮与否, 人家要看你的教育,做过的项目。就是你张的像张曼
玉, 但是你不会C,C++,JAVA,OS , ALGO...也没做过什么项目。那你这关就过不了。
2. PHONEINTERVIEW: 这个过程,看的是1, 你的RESUME 的真实性, 2, 你的电话沟
通能力, 3,你的技术水平和智力水平。 所以,好看在这个环节没作用。
3. ONSITE: 这个环节,如果你符合他们的审美要求, 估计有点作用,但是,面试不是
一个人, 而是几组人。 那么你要符合大多数人对你的评价。 如果张三喜欢瘦的, 李
四喜欢胖的, 那么你的容貌还有什么优势呢?除非所有的面试的人都是一个审美标准
。 另外, ONSITE 要在白板写代码, 要回答一些问题,面试的人要如实记录。 那么
, 你如果技术不过关, 人家也不能要你。除非你就是技术强, 沟通能力好。 。。。
。。
容貌唯一可能有优势的情况如下:现在一个名额有N个人在竞争,其他方面都势均力敌,
但是你在容貌上有比其他人有优势。那
J*****n
发帖数: 4859
4
来自主题: JobHunting版 - how to solve this google interview question
对sequence取差,然后用Kadane Algo,从头到尾,再从尾到头的各用一遍就可以了。
时间复杂度是线性的。
d****2
发帖数: 6250
5
太弱了,就是一个经典的randomized algo,外加divide-and-conquer,还用背吗?最多5分钟搞
定,哈哈.
s*******e
发帖数: 93
6
来自主题: JobHunting版 - 一个容易记忆的permutation算法
This website has mentioned a way to consider duplicates,
http://n1b-algo.blogspot.com/2009/01/string-permutations.html
but I have tried it, and it seems to have some bugs. Anyone else try this
method?
Basically it maintains a "previous" variable for the s[i],and check if s[i]
equals to previous before doing the first swapping.
a*u
发帖数: 97
7
看你去找什么样的工作了,如果目标是research lab, top school+publication最重要
。其他就主要是algo and coding了。一两个月突击复习一下,祝好运!
s********l
发帖数: 998
8
来自主题: JobHunting版 - Amazon二面
cong & bless~
第一题 是客户有选择的看这些log还是全都看?
第二题 我觉得 是不是可以用lock free algo

了。
~~
c******n
发帖数: 4965
9
来自主题: JobHunting版 - 算法一问
did u pass ur algo course ?
B*******g
发帖数: 1593
10
来自主题: JobHunting版 - 说说flextrade 的 onsite 经历
呵呵 pat pat..recruiter也给我找了这家 当时就不太愿意 不过网上做题就做挂了 也
省得on site被羞辱 hoho
他们应该是个algo trading workshop吧。。不知道trader/developer比例如何
p******r
发帖数: 2999
11
来自主题: JobHunting版 - 新鲜Amazon电面经
you don't understand the algo at all.
j*****g
发帖数: 223
12
来自主题: JobHunting版 - 一些面经
For the sorting w/ k elements problem, it's easy to achieve O(n) time
complexity and O(1) space complexity by using counting/frequency sort:
step 0: initialize counting/freq array k, where k0 ... kn elements can be
indexed into 0 to n of the array. And array is initialized to be 0.
step 1: scan the array, and for each a[i] do k[a[i]]++;
step 2: rescan the array and put final sorted element back in.
count = 0;
for (i = 0; i < k; i++)
for (j = 0; j < k[i]; j++)
a[count++] = i;
(a bit simpli... 阅读全帖
M******q
发帖数: 94
13
来自主题: JobHunting版 - 刚收到狗狗电话,被拒
是一个游戏题,用dp也是后来他让我问问题的时候告诉我的。我当时一开始想到用
greedy algo.当然事先也没怎么好好准备dp.
收到电话,我也没太大反应。 that's fine, thank you就完了
p******r
发帖数: 2999
14
来自主题: JobHunting版 - 要去google onsite的同学们
。。。
牛啊,能写出inplace的O(n)的selection algo
A********l
发帖数: 184
15
来自主题: JobHunting版 - 攒人品,twitter电话面经
median那题应该是selection algo在并行机上的直接应用
吧。

候。
substring
match
a****n
发帖数: 1887
16
来自主题: JobHunting版 - 终于拿到offer了
trading 一般分为三部分,
1. 从exchange拿price pdate, 这个部分一般也被称为 market data, price
gateway
2. 负责发送order, 并更新order的status,计算PNL,和risk manage 这个部分一般也被称为order routing gateway
3. trading算法, 这个职位一般称为quant developer, 主要是和quant或者trader打交道, 基于1, 2 的server实现算法 自动trading
其实我都做, 但是主要focus在2上
1,2 每个trading company 都在做, 但是就像放在桌子上的金币, 谁眼疾手快
, 谁就抢得到金币, 所以主要工作就是性能优化
从price update -》 algo -》 place order 总时间越低越好, 一般都是用微秒或者clock tick计算latency。
g***s
发帖数: 3811
17
来自主题: JobHunting版 - 这个算法题算难吗
DP is another algo to solve this question.
a****n
发帖数: 1887
18
来自主题: JobHunting版 - 弱问一个c++编程题
STL 的东西绝大多数都在这里。。。包括所有container,algo
STL其他部分还有 auto_ptr 和 make_pair 之类的一些toolkit,应该也在这里
a****n
发帖数: 1887
19
来自主题: JobHunting版 - twitter电面
from algo book
a***c
发帖数: 2443
20
来自主题: JobHunting版 - 准备面试准备的很郁闷
how are you guys preparing?
Do you already have a list of questions or a list of topics (from resume and
/or job descriptions), then you just go over textbook chapters that cover
those questions/topics?
Is there a more systematic approach?
I just started a personal wiki to help organize all the related materials,
but there's just too much stuff!!
My main menu has the following items already and it's quickly expanding:
1. Hardware - Circuit design, digital design, blah blah blah
2. Software - OS ... 阅读全帖
j*****g
发帖数: 223
21
done/ihasleetcode你们是不是专业interviewee啊??//佩服!
从来没贴过图,不知道贴对了没。done的想法是对的:
step 1: suppose we've already done the scan for step 1, and how we have the
max length MAX at point a.
step 2: no need to compare one by one, just jump to MAX position b, and do
an adjacent comparison. If >=, then we know there won't be anything before
could satisfy "increasing" as well as beat MAX. So in this case, keep
jumping MAX ahead.
step 3: suppose we're at MAX place b, and adjacent comparision is <, great!
we have a p... 阅读全帖
j********x
发帖数: 2330
22
来自主题: JobHunting版 - ~~问两道AMAZON电面题
第一题主要考虑稀疏图的存储吧,sparse matrix相关的可以看看
第二题,可以考虑random algo;
任选一列,排除有“1”的行;
在余下的行继续这么搞;
复杂度取决于“1”分布的比例;worst case当然是N^2
d**e
发帖数: 6098
23
☆─────────────────────────────────────☆
gfdymd (hui) 于 (Fri Mar 26 11:17:40 2010, 美东) 提到:
我知道容貌好在中国是有优势的。
假如相同工作能力,形象好的会被优先录用吗?
☆─────────────────────────────────────☆
fzzh24 (fzz) 于 (Fri Mar 26 11:19:01 2010, 美东) 提到:
这个算是坑么?
还是跳一下吧
老美审美观和我们是反过来的吧
如果你是大美女,那毕业后回国找工作
不然就在这找
两头不吃亏啊
说个正经的,如同楼下女程序员的分析
你与其show外貌;不如show性格。性格好的人,哪都吃的开
☆─────────────────────────────────────☆
gfdymd (hui) 于 (Fri Mar 26 11:20:47 2010, 美东) 提到:
如果你认为是坑就填,认为不是坑就请认真回答一下。

☆─────────────────────────────────────☆
... 阅读全帖
s******n
发帖数: 57
24
来自主题: JobHunting版 - Google onsite question
Bitwise shift right cyclic
Execute command on linux cluster
Check two leafs of graph connected or not, how we can optimize algo
More new question:
http://www.careertea.com/techforum/forum.aspx?KeyWord=all
g**u
发帖数: 583
25
来自主题: JobHunting版 - CS interview questions
Q14:
why the prob is not the same? since it is a fair coin, the H and T is
interchangable.
Q15:
I do not understand it. Why not directly using Xor OXFF(1111 1111), then
all the bits 1 will be 0, all the bits 0 will be 1.
Could you please elaborate your algo?
c******n
发帖数: 4965
26
来自主题: JobHunting版 - 一道Google面试题
young试tableau
same algo as heapify
d********w
发帖数: 363
27
来自主题: JobHunting版 - [Algo]dutch flag problem
简单型:sort 0, 1数组, O(n)时间,可以使用头尾两个pointer,
i = 0;
j = n-1;
while( i < j){
while( array[i] == 0 && i < j )
i++;
while( array[j] == 1 && j > i )
j--;
if ( i < j )
swap( a[i], a[j] );
}
如果是排序0,1,2数组,就是dutch flag问题, http://en.wikipedia.org/wiki/Dutch_national_flag_problem,跟quicksort中的partition类似
void threeWayPartition(int data[], int size, int low, int high) {
int p = -1;
int q = size;
for (int i = 0; i < q;) {
if (data[i] < low) {
swap(data[i], data[++p]);
++i;... 阅读全帖
d********w
发帖数: 363
28
来自主题: JobHunting版 - [Algo]dutch flag problem
扩展3,找到一个这么写的,http://pastebin.com/f41fe39d1
大家看看对不
d********w
发帖数: 363
29
来自主题: JobHunting版 - [Algo]dutch flag problem
扩展3如果能计数的话,就简单了,只要把1的个数,0的个数统计出来,就知道最后留
几个,前面就直接按01打印了,如果限定不能计数呢
还想到一个问题,如果是求最少的交换次数,例如三色问题,不一定要求0放在最前,
只是相同数字聚在一起。01间隔打印的话,不一定0101,1010也行。该怎么思考呢
i**********e
发帖数: 1145
30
来自主题: JobHunting版 - [Algo]dutch flag problem
这道题 FB 面试有人贴过,而且听说代码写起来很麻烦.
在网上尝试找关于 Dutch National Flag Problem (DNFP) 的扩展至 k 种颜色的解法
,找了老半天都没找着(连四种颜色的也没找到),代码只好自己写了.
今天写 DNFP 四种颜色排序基本写对了,但是某些 test cases 不能通过。主要难度在
于当此颜色为第一颜色的时候应该怎么交换。研究了老半天,终于开窍了。原来是忘掉
了一个很重要不变量(invariant),就是 0 <= r <= w <= b < n (这里指的是原题
的三种颜色,r=red, g=green, b=blue,扩展至 k 种颜色的不变量为 0 <= mid[0] <=
mid[1] <= ... <= mid[k-1] < n).
DNFP 四种颜色写对了之后,思路就清晰了,非常容易扩展至 k 种颜色。利用一个内循
环,来保持不变量 0 <= mid[0] <= mid[1] <= ... <= mid[k-1] < n. 这内循环似乎
很耗时,但少了这内循环,我又不知道怎样才能保持以上的不变量,望高手指教.
顺便介绍一个写... 阅读全帖
j********x
发帖数: 2330
31
来自主题: JobHunting版 - [Algo]dutch flag problem
2, O(n) space radix sort is stable
3, "no extra memory" is ill-defined, is index considered "extra"?
g*********s
发帖数: 1782
32
来自主题: JobHunting版 - [Algo]dutch flag problem
i think O(1) space is fine.
g*********s
发帖数: 1782
33
no, the commonly asked one is the stack, not the queue.
the hardness of queue is due to the fact the queue has 2 ends to take care
while the stack only have one.
it's an interesting variant of the classical one. but i don't feel there's
any good algo.

all
d********w
发帖数: 363
34
First, we can consider 2 numbers, which is O(n) time. We can use 2 two
pointers to process the sorted array or use hashtable to find whether T-cur
in it.
If k = 3, the running time is O(n^2), wiki describes the algorithm http://en.wikipedia.org/wiki/3SUM, it also mentions an optimization
"When the integers are in the range [−u ... u], 3SUM can be solved in
time O(n + u lg u) by representing S as a bit vector and performing a
convolution using FFT." but it is hard to follow.
How about numb... 阅读全帖
g*********s
发帖数: 1782
35
subset sum, npc.

T-cur
http://en.wikipedia.org/wiki/3SUM, it also mentions an optimization
in
z****o
发帖数: 78
36
When value range is limited, it is a DP-able problem.
j********x
发帖数: 2330
37
k is a fixed number... subset sum considers the case that k is not fixed,
which forces to explore all possible combinations.
I believe the complexity is n^(k-1) just guess
P********l
发帖数: 452
38
http://www.sureinterview.com/shwqst/98001
At least, it can be done within n^(k/2). Seems still room to improve.
d********w
发帖数: 363
39
来自主题: JobHunting版 - [Algo] 检查一个树是另一个的子树
bool isSubTree(Tree* large, Tree * small);
假设就是二叉树吧,想到一个思路,把两个树按先序和中序打印出来,然后查看是否是
substr,能证明这样是对么?或者还有什么其他思路?感觉树的查找是个挺难的问题,
之前我在工作中就遇到过在一个domtree中,如何比较树的相似度,
就是比如把网页按dom解析,形成一个树,判断两个网页的duplicate,可以转化成求这
两个树的相似度,这又有2个问题,如何做树的查找,如何计算相似。不知大家有没有
做过这方面研究的
它的一个简化版本就是这题
g*********s
发帖数: 1782
40
来自主题: JobHunting版 - [Algo] 检查一个树是另一个的子树
recursion.
i**********e
发帖数: 1145
41
来自主题: JobHunting版 - [Algo] 检查一个树是另一个的子树
这题没那么容易。
我想了想,似乎很难用 bottom dfs 来解。
top down dfs 肯定可以,但是效率没那么好(有很多重复的扫描)
还有,有一个要弄清楚的是 subtree 的定义。。。
根据 wikipedia 里 subtree 的定义,
A subtree of a tree T is a tree consisting of a node in T and all of its
descendants in T.
不知道你想的 subtree 是一个 tree 里面任何一小部分,或是所有子节点都必须吻合
才行?
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
h**********c
发帖数: 4120
42
来自主题: JobHunting版 - [Algo] 检查一个树是另一个的子树
应该搜索树吧,
一边遍历一边hash,
g*********s
发帖数: 1782
43
来自主题: JobHunting版 - [Algo] 检查一个树是另一个的子树
u make a good point. i think all nodes must be identical.
i**********e
发帖数: 1145
44
来自主题: JobHunting版 - [Algo] 检查一个树是另一个的子树
Yes, they must all be identical,
but the question i'm asking is:
tree A)
2
/ \
1 3
tree B)
3
/
2
/ \
1 3
/
4
tree A) could or could not be a subtree of tree B) depending on the
definition of "subtree".
According to wikipedia's definition, tree A) is NOT a subtree of tree B),
because there is an extra node(4) at the bottom, even all nodes match
exactly.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
j*****u
发帖数: 1133
45
来自主题: JobHunting版 - [Algo] 检查一个树是另一个的子树
good point,如果子树的叶节点必须在原树中也是叶节点,可不可以这样:
原树和子树bottom->up算每个node的hash,这个hash function考虑到当前node的data和
location, i.e. hash(node)=f1(data),f2(hash(node.left)),f3(hash(node.right))
算hash是O(n)
然后foreach node,比较hash跟子树root的hash,也是O(n)
h**********c
发帖数: 4120
46
来自主题: JobHunting版 - [Algo] 检查一个树是另一个的子树
先查小树的高度,
查大树相同高度的全部节点,得若干个子树,
子树与小树hash 对比。
j***u
发帖数: 152
47
来自主题: JobHunting版 - [Algo] 检查一个树是另一个的子树
用DFS 如果小树是大树的子树 那么小树的开始和结束时间一定被包括在大树的开始和
结束时间内
T_start <= t_start <= t_end <= T_end
d****2
发帖数: 12
48
来自主题: JobHunting版 - 请问一道google面试题
Can you explain what a[1~n] means? If it is sum, does not look right.
On the other hand, your non-DP algo (i.e. 如果只是以拿得比对方多为目的,就简
单一些...) seems to be the right answer, considering your opponent is trying
to max his return.
d********w
发帖数: 363
49
来自主题: JobHunting版 - [Google算法题] reconstruct sector
http://geeksforgeeks.org/forum/topic/google-interview-question-
software-engineerdeveloper-about-algorithms-15
There is a file system on the disc. the disc has many sectors. Always
the first sector has the information about all the files.
A file data is divided into sectors. Each sector can have data from a
single file.
Each sector has 2 parts, data and the pointer to the next sector of the
file. Every last sector in the file has next pointer as null.
say a disk has 18 sectors numbered 1 to 18.
... 阅读全帖
d****2
发帖数: 12
50
来自主题: JobHunting版 - CS interview question
The time complexity is O(n^3), not n^2. for each pair of points (n^2), you
have to check with the rest of the points (n). so total O(n^3). Don't know
whether there is any algo can do better than this though.
首页 上页 1 2 3 4 5 6 7 8 9 10 下页 末页 (共10页)