c*r
发帖数: 278 | 1 That is completely different than the regular binary search.
In binary search, from the comparison result, we know the sub problem to
solve (which part to continue searching).
To find this 分界点, if a[i] < a[i+1], what is the next step (the sub problem)?
So the solution is not looking for 分界点, but which part to continue searching. That us not much different from regular binary search. |
|
A*********3
发帖数: 70 | 2 Phone:
SSL, for example a -> b (A refer B)
d -> c (D refer C)
c -> a (C refer A)
find a data structure to save these information and print the following
result: d->c->a->b
Onsite:
1. design public interfaces for cache (like cache for string)
2. design public interfaces for router
3. merge two binary search tree
4. 爬楼梯，每次可以一个step，或者两个step，问有多少种走法？
5. 如何实现一个queue? 怎么分别通过stack,linked list, heap实现？
6. preorder binary search tree.
判断两个binary search tree的pre |
|
i**********e
发帖数: 1145 | 3 二叉树是面试里常见的问题种类，大家在面试前必须熟悉这一类的问题。以下是我收集的一些常见二叉树面试问题（包括我亲身经历的）。多做多练习，相信你一定可以掌握好。
Determine if a Binary Tree is a Binary Search Tree
这题很常见，microsoft,amazon, google的面试都有人被问过。这题也是二叉树的好题
，必须得对BST的定义搞清楚。有一个常见的陷阱，就是把current node的value和left
node, right node比较；这是不正确的解法。也有一个很容易想到的brute force解法
，但是每个node会被遍历很多次。正确的优解是 （O(N)解，N=number of nodes)有两
种，面试者必须对这题熟悉。
Binary Search Tree In-Order Traversal Iterative Solution
这题应该是 google 电面经常问的问题吧。我那时候就是google电面没答好这问题，所
以就fail了，超级后悔啊。强烈推荐的问题。In-Order traversal能很轻松地用递 |
|
A*********3
发帖数: 70 | 4 两个阿三
1.问research
2. 一个Master node，一个Slave node。Master node给Slave node发message， slave
node回答ack。如果master node在5秒内收到3个以上的ack，那么master node就认为
slave node是好的；如果5秒内，收到少于3个的ack,slave node是坏的。
请设计算法和数据结构帮助master node判断slave node是好还是坏
3. 判断一个binary tree是不是binary search tree 给出空间复杂度时间复杂度分析
4. hashtable优点和缺点，binary search tree优点和缺点
5. 一个Master node，连接到外界，可以接收外界的request。Master node还连接了许
多台slave node，这些slave node连接成grid状。并且slave nodes连接到一个数据服
务器，所有的slave node都可以从数据服务器读data。
如果Master node接收到了一个请求:select * r1 |
|
n*****y
发帖数: 361 | 5 因为赶着年底毕业，九月底才开始投简历。这个offer来的太快，小startup就是动作快
，从十月初联系我，到 offer, 就两周。那几个大公司的 on-campus interview还都没
开始。也算是 hot startup,但这里肯定没人知道的，移民版知道这个公司的更多些。
就不透露公司的名字和考题了，见谅。
HR 联系之后，先是组里的头直接电面，问了一个他们实践中的问题，我没想出答案，
但还是扯了扯。后来就在谈公司做什么，我有准备，问了很多问题。刚放下电话,HR问
我什么时候作 coding test, 可以马上把题发给我, 就是fill Java class, 实现某些
功能，一般给 2-3个小时。我想这么大工作量，不能拖，否则牵扯时间和精力，就说马
上作，决定不准备了，冒一定风险。结果一个小时做完发给他们，小impress了一下。
然后另一个 team lead 马上打电话二面，顺便考察一下是不是真是我自己写的程序。
这就是一天三面，两电一编程，然后就给 onsite了。面了组里的4个lead,HR 和
Founder。前两个基本都在问我的 research和 big ... 阅读全帖 |
|
n*****y
发帖数: 361 | 6 因为赶着年底毕业，九月底才开始投简历。这个offer来的太快，小startup就是动作快
，从十月初联系我，到 offer, 就两周。那几个大公司的 on-campus interview还都没
开始。也算是 hot startup,但这里肯定没人知道的，移民版知道这个公司的更多些。
就不透露公司的名字和考题了，见谅。
HR 联系之后，先是组里的头直接电面，问了一个他们实践中的问题，我没想出答案，
但还是扯了扯。后来就在谈公司做什么，我有准备，问了很多问题。刚放下电话,HR问
我什么时候作 coding test, 可以马上把题发给我, 就是fill Java class, 实现某些
功能，一般给 2-3个小时。我想这么大工作量，不能拖，否则牵扯时间和精力，就说马
上作，决定不准备了，冒一定风险。结果一个小时做完发给他们，小impress了一下。
然后另一个 team lead 马上打电话二面，顺便考察一下是不是真是我自己写的程序。
这就是一天三面，两电一编程，然后就给 onsite了。面了组里的4个lead,HR 和
Founder。前两个基本都在问我的 research和 big ... 阅读全帖 |
|
V*****i
发帖数: 92 | 7 For the first one, do three binary searches. My code as follows. It is easy
to combine three binary searches into one routines through a flag, I wrote
this way for clearance.
int binary_search(int* num, int left, int right, int K) {
// find any pos such that num[pos] == K
if (left > right) return -1;
int mid = (left+right)/2;
if (K == num[mid]) return mid;
if (K < num[mid]) return binary_search(num, left, mid-1, K);
else return binary_search(num, mid+1, r... 阅读全帖 |
|
j*******a
发帖数: 61 | 8 Thanks for all posts. Just want to confirm I understand right, let me repeat
your ideas.
Assume input: 4, -1, 5, 2, 0, -2.
looks for the closest sub array for 3
0 1 2 3 4 5 get sums sort BS for 3
------------------------------------
0 | 4 3 8 10 10 8 n nlgn lgn
1 | -1 4 6 6 4 lgn lgn
2 | 5 7 7 5 lgn lgn
3 | 2 2 0 lgn lgn
4 | 0 -2... 阅读全帖 |
|
n*s
发帖数: 752 | 9 strcmp()
binary search
find an element in a rotated sorted array (binary search)
given an integer array, check if a + b + c = 0
binary tree, print elements by level |
|
b*m
发帖数: 34 | 10 似乎现在的解法都不太完美。
ihasleetcode 的算法有点诡异。
Using binary search, we found the smallest j that satisfies the condition
sorted_cum[i]+k >= sorted_cum[j]
这里 为什么用这个不等式sorted_cum[i]+k >= sorted_cum[j]
使你打错了造成了我们的误解吗？
假设i〉j s[i]-s[j]>=k 才是我们要的， 还是 这里有什么深意呢？求解释？
然后你是要找刚好满足条件的，这个binary search 似乎不能保证找的的是刚好满足条
件的临界位置，只能保证满足条件，所以这里要找到刚好满足条件的那个按你的算法似
乎还是要n*n。
然后
你这里的
min_index[] = {1, 1, 1, 1, 1, 1, 1, 6, 6, 10, 10}
max_index[] = {11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 10}
的实际物理意义是当前sorted cum array 当前对应的坐标后的元素中... 阅读全帖 |
|
E***n
发帖数: 166 | 11 上周1周2连面了2个人，各50分钟吧
第一个人，
1.最挑战的project
2.如何设计一个停车场？停车场里有n个车位，每个车位离入口有个距离，当一辆新车
进来以后，给他安排最近的车位。
3.写一个程序，计算给定字符串中单词的数目，如何测试？
第二个人，
1.最挑战的project
2.设计一个电话本，如果内存不够，你用binary tree还是hashtable? (我答的binary
search tree，不知道对否？) 如果想把电话本里面所有的item按字母顺序输出，如何
实现（binary tree 和hashtable都要回答）？
3.如何寻找文件中所有的电话号码？123-456-7890
4.有一个array,每个元素是一个string,给定一个string s,查询s的reverse string是
否出现在array当中。
现在还在等消息，不知道结局怎样 |
|
f****v
发帖数: 5 | 12 本人在东岸，申了加州小start up。第一轮电面题如下
1.What is the complexity of insertion in a hash table?
2.What is the complexity of searching in a balanced binary search tree?
3.Why use binary search tree when hash table is faster?
4.How many bits will be used in the binary representation of 100,000?
5.How to sort large amount of numbers when memory is limited?
6.What is the difference between thread and process?
题并不难, 但是因为工作太忙, 没有时间复习，大概只回答上来一半。但是又收到信约
了第二轮电
面, 结果被放了鸽子. 其实心里庆幸， 能多几天时间准备. 骑驴找马不容易啊。 |
|
|
g******0
发帖数: 221 | 14 I am sorry, I don't quite understand what the problem is:
Given a binary Search Tree, find two biggest same subtrees.???
二叉树 是 binary search tree, or binary tree?
industry recruiting team，不知道是不是有转机？ 觉得industry recruiting应该更
难吧？ 求祝福！ |
|
g***s
发帖数: 3811 | 15 非负整数数组 is ok for binary search..
yes if all x[i] are non-negative numbers (integer is not required)
same.
O(K*N*N)
Non-negative numbers can be handled by binary search in O(N*N).
sum(i,j) : sum of (a_i, a_i+1,..,a_j) O(n*n)
sort sum(i,j) O(nlogn)
binary search in the sorted sum(i,j) O( n log n)
Total time is O(n^2) |
|
c********1
发帖数: 161 | 16 楼主，我觉得这道题可以做到 O（lg N）, 用两边binary search，两次都不是找
target的value， 而是找与这连续几个value交接的joining points，第一次binary
search找比他大的最小数和value的joining point，第二次找比value小的最大数的
point，然后返回这两个point的index，就可以知道value的个数了。代码不难写，就是
简单的binary search稍加改进就可以。 |
|
c**y
发帖数: 172 | 17 AMZ 两轮店面
第一轮：
1.实现一个hash函数，输入string，输出一个hash值。
考虑复杂了，面试官提示说不用考虑太复杂的hash函数实现。
2.实现一个hash table用来存储strings。
这个后来用STL的map做的。
第二轮：
1.口述array, linked list, binary tree, hash table的区别和特点
随便说了说，这个问题被不同的公司问过好多次了。
2.给定一个binary tree，判断是不是一个binary search tree
google一下，网上有比较好的code，很简单，用recursive方法
3.实现a deck of cards class，具体要求实现两个函数(1) DealACard (2) Shuffle
DealACard就是从当前deck中抽取一张card，怎么抽自己定义，我就说从top抽
Shuffle就是洗排。
两个面试官都很nice。 |
|
x*****3
发帖数: 25 | 18 电面第一个是烙印面试官
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... 阅读全帖 |
|
g***s
发帖数: 3811 | 19 I replied the 2 lou(who mentioned to use sort+binary search to delete
first) and i agreed. (if string2 is very small, scan could be faster
because of binary search overhead)
After enough chars(26 or 52 or 256) are deleted, we can compact it and
use the deleted space.
All we assume is that string1 is very large.
二十六
复的字母怎
么办？抑或是 string1 产生重复的个别字母不超过 string2 的长度？那这基本上就跟
worst
case 一样，26*n 的比较次数，那还不如把 string2 排好序，然后做 binary search。 |
|
i**********e
发帖数: 1145 | 20 LZ，32 的 super cool 应该是 32 才对吧？
因为 32 = 2^5.
刚写了一个程序，利用 binary search 的思路.
首先选定一个 upper bound，也就是 ceiling(log(n)).
然后再 i=2 到 upper bound 每一个做 binary search.
例如，n=32，upper bound = log(32) = 5.
i=2，从 low = 1 到 high = ceiling(n^(1/2))
i=3, 从 low = 1 到 high = ceiling(n^1/3))
..
以此类推...
binary search 的 invariant 就是比较 target 和 middle and middle's next，看哪
一个比较近。如果是离 middle 比较近，那就 middle's next 和它上边的值都可以抛
掉了。相反，那就 middle 和它下边的值就可以抛掉。
这里，我们确保 middle's next 不会大于 high。这个条件可以保证，因为取的是
lower middle = (L+H)/2.
... 阅读全帖 |
|
a********m
发帖数: 15480 | 21 背景：
5月底layoff。layoff那天请假和朋友出门挖贝壳了，没赶上开会。。。然后就开始了漫长的找工作（心理感觉）长征。知道消息一下就晕菜了。赶快查了h1b的规定还有写信问hr和律师公司的规定。律师真是忙，写邮件要几天才恢复，约后几天的半小时时间谈谈，结果错过了两次。。。干脆不理it了，先转b2再说。
申请：
一些公司猎头闻风而来，公司hr也帮俺们这帮倒霉蛋群发申请工作邮件，开始还是感觉良好的。折了几个电面和programming test以后走向另外一个极端。。。主要就是还从打击中恢复，还没准备好面试就被突然袭击。其中有几个非常想去的公司都挂了，郁闷的要死。还好6月中混到2个onsite.开始集中精力准备onsite,也暂停发简历。
面试:
先说折掉的D. 飞德州晚点2小时，11点多才到旅馆，晚上，照常出门逛一下，看看热闹，自己安慰自己是熟悉环境，实际是不喜欢看书。。。话说austin真热。。。下午走的时候是108度。。面试非常顺利。题目难度一般。真正算法也就是A*寻路算法。其他都是实际应用中的问题。还有点到直线距离一类的几何问题。总的来说游戏行业对算法要求不高，有实际经验再准... 阅读全帖 |
|
b*******y
发帖数: 2048 | 22 强贴前排就座
了漫长的找工作（心理感觉）长征。知道消息一下就晕菜了。赶快查了h1b的规定还有
写信问hr和律师公司的规定。律师真是忙，写邮件要几天才恢复，约后几天的半小时时
间谈谈，结果错过了两次。。。干脆不理it了，先转b2再说。
觉良好的。折了几个电面和programming test以后走向另外一个极端。。。主要就是还
从打击中恢复，还没准备好面试就被突然袭击。其中有几个非常想去的公司都挂了，郁
闷的要死。还好6月中混到2个onsite.开始集中精力准备onsite,也暂停发简历。
闹，自己安慰自己是熟悉环境，实际是不喜欢看书。。。话说austin真热。。。下午走
的时候是108度。。面试非常顺利。题目难度一般。真正算法也就是A*寻路算法。其他
都是实际应用中的问题。还有点到直线距离一类的几何问题。总的来说游戏行业对算法
要求不高，有实际经验再准备下都不太难。后来挂的地方是午饭时间一个俗到不能再俗
的问题。。。你的弱点是什么。。。俺找了一个n年前年轻时候的不好的习惯，然后强
调这n年都在不断注意和改进。。。结果it只听了前半: 句。另外一个是complishment
。本着谦虚... 阅读全帖 |
|
P**********c
发帖数: 3417 | 23 赞。
了漫长的找工作（心理感觉）长征。知道消息一下就晕菜了。赶快查了h1b的规定还有
写信问hr和律师公司的规定。律师真是忙，写邮件要几天才恢复，约后几天的半小时时
间谈谈，结果错过了两次。。。干脆不理it了，先转b2再说。
觉良好的。折了几个电面和programming test以后走向另外一个极端。。。主要就是还
从打击中恢复，还没准备好面试就被突然袭击。其中有几个非常想去的公司都挂了，郁
闷的要死。还好6月中混到2个onsite.开始集中精力准备onsite,也暂停发简历。
闹，自己安慰自己是熟悉环境，实际是不喜欢看书。。。话说austin真热。。。下午走
的时候是108度。。面试非常顺利。题目难度一般。真正算法也就是A*寻路算法。其他
都是实际应用中的问题。还有点到直线距离一类的几何问题。总的来说游戏行业对算法
要求不高，有实际经验再准备下都不太难。后来挂的地方是午饭时间一个俗到不能再俗
的问题。。。你的弱点是什么。。。俺找了一个n年前年轻时候的不好的习惯，然后强
调这n年都在不断注意和改进。。。结果it只听了前半: 句。另外一个是complishment
。本着谦虚的态度。... 阅读全帖 |
|
r******n
发帖数: 170 | 24 店面：
1) 做他家books，有很多scan page，如何发现有duplicate page? 说用hashset,然后
有扩展，包括hash function怎么设计，2G RAM具体能放多少页等等
2）online doc写binary search,就是原始的binary search
3）两个数组求中值的变体（改为2台机器减少通讯）
onsite
1)开始以为是要写个singleton class实现，后来发现他是要写一个shared pointer的
实现，做reference counting, 要求overload copy constructor和opeartor =
2）机器人走迷宫题，可以往4领域走，中间有障碍,白板coding， 然后扩展讨论，
memory装不下等等；unit-testing讨论; 一个字符串，中间没空格，有字典，如何断词
3)binary tree serialization and de-serialization 白板coding; 讨论题：给数据
结构，能够快速返回一个没有用过的电话号码，而且可以给一批比如408打头的电话号码
4)花... 阅读全帖 |
|
f****4
发帖数: 1359 | 25 找到一个对的O(N)的解法
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=ri
This is a pretty good puzzle. You can actually find the cutoff and a
description of exactly which pairs are in the solution in less than O(N)
time, but outputting all the solutions takes O(N) time, so it doesn't help
you overall. This won't be much of a hint, but finding the cutoff point can
be done in O(sqrt(N)*log2N) time. Forgive me for not writing code, but this
gets pretty nitty-gritty in spots.
I think of the pro... 阅读全帖 |
|
f****4
发帖数: 1359 | 26 找到一个对的O(N)的解法
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=ri
This is a pretty good puzzle. You can actually find the cutoff and a
description of exactly which pairs are in the solution in less than O(N)
time, but outputting all the solutions takes O(N) time, so it doesn't help
you overall. This won't be much of a hint, but finding the cutoff point can
be done in O(sqrt(N)*log2N) time. Forgive me for not writing code, but this
gets pretty nitty-gritty in spots.
I think of the pro... 阅读全帖 |
|
S**I
发帖数: 15689 | 27 ☆─────────────────────────────────────☆
fengzhongdi (fzd) 于 (Fri May 27 14:30:18 2011, 美东) 提到:
A的onsite,我尽量客观写,大家帮我分析一下
第一个 美国人, 两个string,问第一个是否包含第二个的全部character,扩展是求第一
个string最短的substring包含第二个中所有的character.
我的解法是hashtable, 然后扩展问题是O(n)那个,先找到第一个包含全部的,然后从头
开始删除,接着从尾巴增加那个.面试官表示满意.
OOD是设计card game
交流过程很融洽.
第二个 hiring manage,印度人, 这个人带我去吃饭,然后问了我电梯设计问题,纠缠在
什么时候读楼层,还有如何判断要不要停下来接人.说了快50分钟.我个人感觉还好,反正
他也是都是笑到最后
第三个,白人,一开始问我LRU cache的设计,我直接告诉他double linked list + hash
table,他很吃惊问我是不是准备过,我说是,然后换了一题Bian... 阅读全帖 |
|
y*******g
发帖数: 6599 | 28 没这么夸张了，这些熟练掌握其实很不错了。
我的经历 google的电面就只有一个coding 题目，linear scan array然后binary
search优化. 我承认我土，没有第一步写出binary search, 不过也让我通过了
版上讨论的一道google题 shuffle large file其实code和merge sort几乎一样
linkedin onsite有一轮也只有一个merge，还不用递归sort，后来拓展用一个binary
search来优化
考coding的基本功这些题目就够了。 考高难度算法另谈 |
|
y*******g
发帖数: 6599 | 29 没这么夸张了，这些熟练掌握其实很不错了。
我的经历 google的电面就只有一个coding 题目，linear scan array然后binary
search优化. 我承认我土，没有第一步写出binary search, 不过也让我通过了
版上讨论的一道google题 shuffle large file其实code和merge sort几乎一样
linkedin onsite有一轮也只有一个merge，还不用递归sort，后来拓展用一个binary
search来优化
考coding的基本功这些题目就够了。 考高难度算法另谈 |
|
S**I
发帖数: 15689 | 30 ☆─────────────────────────────────────☆
hehe123 (hehe) 于 (Wed May 4 22:12:56 2011, 美东) 提到:
面经：
1. 两个sorted的数组merge
2. Binary Tree的Serialization和Deserialization, 随便用什么方法实现
3. 设计一DVD出租系统，database table, 类和接口等
4. Large file, multiple lines, how to get any line in equal probablity, 文件
太大内存无法装入
5. 用pre-order in-order sequence重构binary tree.
6. 大量behavior问题。每个人几乎问了15分钟这样的问题，然后只30分钟做题。
Offer：
Base： $116K
Stock: 320
Sign on: $32K
比现在的好不了太多，不过A家忙多了。请问怎么能多要点？
☆─────────────────────────────────... 阅读全帖 |
|
g*********8
发帖数: 64 | 31 第一题ihascode1337的确给出了两个数组不一样的长度的情况，如果一样的长度可以参
考Algorithm Design (by Kleinberg) Chapter 5 Exercise 1,其实也很简单，就是
binary search 的variant，但是这两道的题的coding都很tricky，要非常注意，主要
是递归函数调用的参数传入
他们的coding让我想起了由tree的in-order, pre-order， reconstruct the
binary tree的题，也是一样的tricky编程，也是递归函数调用的参数传递
另外amazon好像还有很好玩的新题：
1）Given a tree preorder sequence such as “NNNLLLL” where N denotes non-
leaf node and L denotes leaf node, with the constraint that no nodes has 1
child. Rebuild the binary tree
2） Given post order traver... 阅读全帖 |
|
g*********8
发帖数: 64 | 32 第一题ihascode1337的确给出了两个数组不一样的长度的情况，如果一样的长度可以参
考Algorithm Design (by Kleinberg) Chapter 5 Exercise 1,其实也很简单，就是
binary search 的variant，但是这两道的题的coding都很tricky，要非常注意，主要
是递归函数调用的参数传入
他们的coding让我想起了由tree的in-order, pre-order， reconstruct the
binary tree的题，也是一样的tricky编程，也是递归函数调用的参数传递
另外amazon好像还有很好玩的新题：
1）Given a tree preorder sequence such as “NNNLLLL” where N denotes non-
leaf node and L denotes leaf node, with the constraint that no nodes has 1
child. Rebuild the binary tree
2） Given post order traver... 阅读全帖 |
|
i**********e
发帖数: 1145 | 33 这题主要考察重建 general tree，不是 binary tree。然后就是怎么把 general tree
用 binary tree 来表示。
还有要注意给的是 preorder 和 postorder.在 binary tree 里 preorder 和
postorder 是不可能重建树的。
不过我认为这题作为面实题，给不到你对 candidate 很有用的signal。个人意见。 |
|
f*******n
发帖数: 12623 | 34 可以 O(k*log(n)^2)
Binary search in the first array for the index closest to the median. At
each step, binary search in the other (k-1) arrays for the current value in
the first array. Then add the indexes to see if we are before or after the
median. At the end, we are down to one element and we also know the index in
the other arrays. The answer is in one of these.
The bigger binary search is log(n), at each step, we need to do (k-1) * log(
n), so multiplied together we get O(k*log(n)^2) |
|
l*********8
发帖数: 4642 | 35 It we use binary search for two arrays, we need binary search on the
second array for each elements from the first array.
If there are NOT many common elements in the first two array, binary
search on the third array could be faster than iterating thought array 3.
But I agree that my method can perform worse in some cases. |
|
l*********8
发帖数: 4642 | 36 worst case of binary search ( O(n) ) happens on extreme unbalanced binary
tree but not in this case. Here we do binary search on an array. It costs
at most log2(n) comparisons. |
|
g**u
发帖数: 504 | 37 If there are two much shorter arrays, we can first find common elements for
those short ones and then binary search the long one.
If one array is much shorter than other two arrays, for each element in the
first array, we first binary search that element in the second shortest
array, if there exists, we then binary search it in the longest one.
It really depends. |
|
s*********d
发帖数: 2406 | 38 没什么好说的，还是自己不行。
第一题
abstract class absClass
{
public int AddTwoNumbers(int Num1, int Num2)
{
return Num1 + Num2;
}
public abstract int MultiplyTwoNumbers(int Num1, int Num2);
}
实例化 absclass
interviewer 说 不需要用考到任何算法知识。只考java。
answer ：
public class aaClass extends absClass {
public int MultiplyTwoNumbers(int Num1, int Num2){
int multiplyresult = 0 ;
multiplyresult=Num1*Num2;
return multiplyresult;
}
这个有什么问题？
Q2:经典题
Q2:
Given a sorted 2-D array (M x N) con... 阅读全帖 |
|
r*****e
发帖数: 792 | 39 binary->GrayCode
GrayCode = binary ^ (binary>>1); |
|
e****e
发帖数: 418 | 40 Apply binary search on diagonal elements (0,0), ... (m-1,n-1).
When the number is not on the diagonal line, we can do the binary search
until:
A[r][s] < num < A[r+1][q]
Then we know num must be either in array A[r][s+1],... A[r][N-1] or A[r+1][0
],...A[r+1][q-1] if the matrix has the element.
The we do binary search on those two one-dimensional arrays one by one.
The running time is O(log(N+M)) |
|
p****x
发帖数: 23 | 41 为后天On site 攒人品。On site完了再发面经
A 家round 1 电面：
1. Talk about your research project.
2. Explain what is hash table. How to implement. Method for resolve
collision. Good Hash function property.
3. Find max value in Binary tree. Time complexity, how to optimize.
How about BST, the worst case time complexity.
4. Coding. Given an positive integer value, search a binary tree to find the
number of nodes, that start from the node there exist a path that the sum
of on the path is equal to the given numbe... 阅读全帖 |
|
j********2
发帖数: 82 | 42 Given preorder of a binary tree, generate all the possible binary trees.
Note that it is not necessarily a binary search tree. |
|
k***g
发帖数: 8 | 43 mazon SDE test第一轮电面，三道题：
1 介绍下之前的工作经验
2 difference btw array and linked list,
write a function to find the first share node for two linked list
3 difference btw binary tree and binary search tree
Given a binary tree and a sum, find a path from the root
down to a leaf, such that adding up all the values along the path
equals the given sum.
面试官应该是中国童鞋，人很nice，给了很多时间和提示，奈何本人真的是没有coding
经验啊，当时就是随便申一下，浪费了机会。祝你在amazon一切顺利。
两三个月了，不想待着了，回国工作，顺便攒人品。顺祝各位好运。 |
|
y****t
发帖数: 23 | 44 读一个binary文件，里面都是binary数字
写一个程序就是算所有数字的合(sum)
限制是 sum 只能有 64-bit bits of precision.
每一个数字是little-endian 32-bit unsigned integers
里面的数字可能有超过1千万个
一定要把里面数字读出来，转成10进制吗？
有没有可能直接用 bit shift之类的，直接在binary数字上互相加？
最快的方法是什么？
都说说想法吧 |
|
l****p
发帖数: 397 | 45 第一通电话：
听口音应该是老印的，有点口音，面试过程中好几次我都没听清反复问。
上来没寒暄几句就写代码：
找出一个树中最深的结点。
明显留了好多细节让我问，于是我开始clarify:
1. 是不是binary tree。答：good question, yes, assume it's a binary tree
2. 是不是balanced binary tree。答：does that matter? 我边想边说，好像没关系
然后我再也想不出其它问题了。开始想算法。想一半，他才提醒我说还有一个细节我没
问：如果有多个最深结点怎么办。回答是返回最右的。这是一个失分的点
然后解释算法，可以用深度优先遍历也可以用广度优先遍历，记录所有叶节点的深度，
然后找出最深的。他问复杂度，我说时间是O(N), 空间是O(N). 他说空间能优化吗？我
说能， 在遍历过程中只记录最深的就行。他问这下的空间复杂度，我说是O(1) 。然后
让我开始写代码，我说深度优先呢还是广度优先，他说有什么区别，我说差不多，然后
想想不对，广度优先需要一个queue，这是O(N)的空间，深度的只要O(lgN)的空间，这
... 阅读全帖 |
|
M******e
发帖数: 103 | 46 网投。2轮电面. on-site后两天收到电话被拒
第1轮电面 白男
问了排序算法的复杂度和如何根据数据特点设计排序
编程题是那个ransom text. 就是从magazine找组成ransom的字母。Hash table完成
第2轮电面 白男
出了三道编程题
1）shuffling
2) least common ancestor of binary tree
3) 一道判断整数能否被3， 5， 15整除的题，具体什么 忘了
On-site
第1轮 三哥
先问了c++多态性基本问题。
编程题1是检查binary tree是否mirror
编程题2 是输出一个集合的subset (CC150上的题)
编程题3 是LRU (没写code, 只说设计，没时间了)
第2轮 白男manager
先问了20分钟的behavior问题
编程题1是数组中连续数字的最大和(CC150上的题)
编程题2是binary tree的serialize and deserialize
第3轮 白男manager
先问了10分钟的behavior问题
问了一个设计题，关于如何查找一个用户在过去10秒钟内访问网... 阅读全帖 |
|
p*****2
发帖数: 21240 | 47 面试题总结(2) - Two/Three pointers
简称two pointers吧。大概把分类粗略的搞了一遍（http://leetcode.cloudfoundry.com/), 发现利用two pointers解决的题目数量很大。two pointers我指的是一类题，而不一定是真正的two pointers, 比如可能是three pointers, 也可能不是pointer， 而是index。这类题基本上就是发生在array, string, linked list这三种数据结构上，是一种基本的算法和编程技巧，同样超高频率的出现，可以说是面试必遇的题。
two pointers常常和其他的算法混杂起来出现。比如binary search本身也可以归类为
two pointers的。如果这样算的话，Leetcode上边1/4的题目都跟它相关。因此，two
pointers是必须熟练掌握的基本编程技巧。
Two pointers大概分三种类型
1. 两个pointers从头往后走：感觉绝大多数的linked list的题目都涉及到这个操作，
当然还有array。
Imple... 阅读全帖 |
|
r*********n
发帖数: 4553 | 48 idea:
first use rand5() to generate a binary random function with p = 1/7 as
follows
express 1/7 in base 5
e.g. 0.abc......
(Note if x can be expressed in base 5 with finite digits, after the last
digit, we assume an infinite number of 0s are padded)
check first digit a:
if rand5() < a return 1
else if rand5() > a return 0
else proceed to the next digit
similarly generate binary random functions with p=1/6, 1/5, ..... 1/2
denote these binary random functions as rand(), N = 2,3,...,7
if rand<7... 阅读全帖 |
|
l**d
发帖数: 746 | 49 一个任意的数组，找出一个严格单调递增的最长子序列。
例如: { 3, 0, 1, 7, 2, 4, 9, 10, 5, 6, 8 } –> output： {0, 1, 2, 4, 5, 6, 8}
网上看到人说有个很简洁巧妙的算法，能在O(N log N)时间和O(N)空间做出来！方法就
是始终保持一个单增的序列，然后新来的数如果比当前最大还大就append在后面，否则
在单增序列里面做binary search，替换相应位置的数。
比如给定src[ ]:
3, 0, 1, 7, 2, 4, 9, 10, 5, 6, 8
定义一个新数组，value a[i]是当前数src[i]在包含自己的最长序列里的index。如果
src[i] > src[i-1], 那么a[i] = a[i-1] + 1, 否则，binary search 找到src[i] <
src[k-1],
src: 3, 0, 1, 7, 2, 4, 9, 10, 5, 15, 8
a: 1 1 2 3 3 4 5 6 5 7 6
... 阅读全帖 |
|
s**x
发帖数: 7506 | 50 Solution 2:
O(n log k) algorithm. K is the length of We have elements.
Assume we already have an increasing sequence: A1, A2, A3, …., for any
given element E, we either
can simply append E to make the list longer,
Do a binary search to find a position j such that A[j] < E < A[j+1], update
A[j+1] to E, so A[1..j+1] can get longer later with new element.
Another list P is used to stores the position of the predecessor element
in the longest increasing subsequence.
#include
using namesp... 阅读全帖 |
|
