f****4
发帖数: 1359 | 1 来自主题: JobHunting版 - 问道排序题 给的是
reverse(i); // 0~i reverse
除非说是 reverse(i) O(1)
不然很怀疑有 nlgn |
|
g***s
发帖数: 3811 | 2 //nlgn
public class BTree {
Node root;
public BTree(int n) {
root = makeTree(n, 0);
}
private Node makeTree(int number, int base) {
if (number == 0) return null;
Node node = new Node((number + 1) / 2 + base);
node.numOfLeftChildren = (number - 1) / 2;
node.left = makeTree(node.numOfLeftChildren, base);
node.right = makeTree(number / 2, node.value);
return node;
}
public Node remove(int index) {
return remove(... 阅读全帖 |
|
n********y
发帖数: 66 | 3 Idea
3 0 1 0
Step 1: use any nlgn Alg to sort and memorize old position
3 1 0 0
Step 2: count same from left to right O(n)
1 1 2
Step 3: place # (in this order: 2 1 1) O(n)
index: 0 1 2 3
1
1 2
3 1 2
4 3 1 2
Step 4: access using old position |
|
w*****3
发帖数: 101 | 4 2个数careercup给了nlgn的就是先排序在两端向中间扫， |
|
a********m
发帖数: 15480 | 5 还好。每个点处理一次。添加的时候需要排序.总时间应该小于nlgn |
|
a********m
发帖数: 15480 | 6 dijistra可以是nlgn或者n2(连接多的话)， dp是什么复杂度？ 另外感觉dj算法和dp思
想很象。 |
|
m**q
发帖数: 189 | 7 这个思路我当场肯定想不到...
不过想了想，所有小矩形最多可能有O(n^2)个，
对它们进行排序需要O(n^2*lgn)
如果用sweepling line algorithm，用一个set记录
过程中的端点，应该可以O(nlgn) |
|
g*****k
发帖数: 623 | 8 只能想到O(nlgn)的stable 算法，O(n)的没啥思路 |
|
g*****k
发帖数: 623 | 9 只能想到O(nlgn)的stable 算法，O(n)的没啥思路 |
|
m**q
发帖数: 189 | 10 O(nlgn)的code好像是挺麻烦的
想了想可以用一个multi-map，key是y坐标，val是x坐标，因为
有可能两个点y坐标相同，所以不能用普通的set或者map。
比较麻烦的代码是查找map内 [y-h,y+h]区间内的点，这个好像
map没有现成的操作。或者不用map自己写一个BST来处理.. |
|
m**q
发帖数: 189 | 11 第5题我看编程之美/算法导论上有用分治的方法的，也是O(nlgn），
主要是合并子问题的时候要达到O(n)比较麻烦，需要把两个子问题
按y轴排序的结果合并，还有在合并前的结果中要找到与x轴划分点
水平距离h以内的元素序列，实现起来感觉比sweeping line还要复杂些 |
|
m**q
发帖数: 189 | 12 O(nlgn)的code好像是挺麻烦的
想了想可以用一个multi-map，key是y坐标，val是x坐标，因为
有可能两个点y坐标相同，所以不能用普通的set或者map。
比较麻烦的代码是查找map内 [y-h,y+h]区间内的点，这个好像
map没有现成的操作。或者不用map自己写一个BST来处理.. |
|
m**q
发帖数: 189 | 13 第5题我看编程之美/算法导论上有用分治的方法的，也是O(nlgn），
主要是合并子问题的时候要达到O(n)比较麻烦，需要把两个子问题
按y轴排序的结果合并，还有在合并前的结果中要找到与x轴划分点
水平距离h以内的元素序列，实现起来感觉比sweeping line还要复杂些 |
|
m**q
发帖数: 189 | 14 同样，当检查一个新的点时，需要把x-h之前的点从map中去掉,
其实可以用一个map存[x-h,x]中的点，key是y坐标。在向map中
添加一个新的点时，先检查map里是否有y坐标相同的点，有则删除；
同时把x-h之前的点依据它们的y坐标，把它们从map中删除。
总复杂度不超过O(nlgn)。
#include
#include |
|
m**q
发帖数: 189 | 15 赞！这个in-place的rotate在这类题目里面还是挺有用的
略微扩展一下，如果原题目要把数组划分成负数，0，整数，
并保持原来的顺序，可以先把0从数组中删掉，然后用
这个分治的算法，最后再把0加进来就行。
刚想起来一个以前看过的类似的问题，也是用分治的方法解决，
复杂度O(nlgn)
把数组A1, A2, ..., An, B1, B2, ..., Bn 变为
A1, B1, A2, B2, ..., An, Bn，
一个例子: abcdefg1234567 -> a1b2c3d4e5f6g7
用O(n)的in-place rotate方法,把数组分成两半
abcd1234 efg567
然后递归处理每个子问题就可以了，区别是这里
要先rotate再分治，原题是先分治再rotate |
|
|
k*j
发帖数: 153 | 17 想请教一下各位，这个dino提出的in-place rotate的方法为什么是O(n)的？
f(n) = 2f(n/2)+O(n),应该是O(nlgn)吧？ |
|
k*j
发帖数: 153 | 18 对。不好意思，我那是笔误，O(nlgn)都错写成了O(lgn)
谢谢。我才意识到merge k个array需要一个heap(size k)来找当前最小值，所以每一步都需要lg(k)时间。总共是nk个元
素，nkO(lgk) |
|
m****t
发帖数: 555 | 19
这个感觉不对。设想m=1000000, n=10, 则复杂度绝对不会是O(nlgn)+O(n) |
|
k****n
发帖数: 369 | 20 攒rp。兄弟们一起努力，共度时艰。
五轮技术加一个午饭。
第一轮主要问project。还问了怎么改进page rank算法。
这个是老本行，不过都忘差不多了。吭哧半天想起来一些，不是很爽。
最后出了一道简单coding题，就是两个dim都分别有序的
matrix，怎么查找。我先说了binary search，用master theorem估算了一下
发现是大于linear的，就说了正常的算法。然后是实现。
这个发挥一般，open questin让我准备不足。
第二轮两道比较简单的题，一个是识别一个字符串是否是一个合法的utf-8串。
因为合法utf8字符可能是变长字节的，就是1/2/3字节都有可能
先用状态机做了，看是否会跳到合法的结束，还是跳到非法状态。
写完代码经过提示才发现可以直接用一个256大小的数组判断是否合法。
弄完了之后暗骂自己，这么明显的空间换时间都没看出来。发挥太差了
第二题是设计一个数据结构存储soduku，目标是判断没有完全填好的行/列/方块
是否合法。因为有第一题地教训，我直接就往那边想了，说存三份数据，一共
才243个字节，更新的时候更新三份，方便又简洁。估计... 阅读全帖 |
|
c******r
发帖数: 225 | 21 3. read n lines of random numbers(space as delimiter) from a file, lines
with same numbers are treated as duplicated lines, regardless of the order.
check and print non-duplicate lines. performance time analysis.
sort the n line based on the # of numbers in each line o(nlgn)
only lines that have the same # of numbers will be compared
suppose we have a set of m lines of length k
for each line in line_set:
sort numbers in each line ~ o(klgk)
then build a hashmap as a helper data structure
for al... 阅读全帖 |
|
m**q
发帖数: 189 | 22 这个好像直接做就行了
pre-order遍历，在每一个节点判断一下本节点值和给定值的差距，
小于当前的最小差值则更新
为了处理多个最小差值的情况，先遍历一次把从root到给定节点的
路径上的所有节点存到vector里面，同时计算出最小的差值是多少。
然后pre-order遍历，同时记录root到当前节点的路径，在每个节点
判断一下差值，如果等于最小差值，则计算距离是否小于当前的
最小距离，如果小于则更新。
预期复杂度O(n),最坏复杂度O(nlgn)，对应于每个节点都要查找路径
的情况
点的差距最小（如
最小公共祖 |
|
s***h
发帖数: 662 | 23 贡献一点面经.
我准备的时间还不够, 今天这二面有点忐忑.面我的人是个白人小伙子, 说话很快, 不
停的提附加问题.
1. how to pick first k maximum numbers in an array.
me: most straightforward, sort then pick, nlgn + k
he: ok...
me: better way, quick select, n * k
he: what is quick select, why is it linear time?
me: talking...
he: what if array is way bigger than the memory, can this work?
me:...yes...but slower due to swapping...
he: anything better?
me: ...
我不太明白他想问什么,所以没答上这一问,最后他问我有什么问题的时候我就
问了他,他说,你可以构造一个size k heap. then it is nlogk. 哎, 我当时真
没往... 阅读全帖 |
|
m**q
发帖数: 189 | 24 O(nlgn)应该可行
1) 用merge sort，在merge的过程中计算ar_low[]的值。
2) 或者先记录下每个元素在数组中的index，然后用稳定排序
sort原数组，然后从头遍历数组，用一个set维护ar[0]
~ar[i-1]的元素在原数组中的index，对于每一个元素
用原来的index在set中二分查找，并把原来的index
插入到set中
equal |
|
m****t
发帖数: 555 | 25 从partial ranking得到原来的数组，O(n)做不到，应该是O(nlgn).这个以前本版有这
个题的讨论。
array |
|
|
s*********t
发帖数: 1663 | 27 第二题什么都没说，merge完要sort么? time complexity要比nlgn好的话只能是n了，
也就是遍历一次。不许用hashtable，咋记录什么数是重复的？不能记录重复的数，只
能遍历找了，不可能在n内解决。估计题目没理解对？ |
|
m**q
发帖数: 189 | 28 考古到一道老题：
给个string,判断这个string是否是某个pattern的周期循环
（这个pattern不确定）要nlgn复杂度 我给了算法 ，
不能cover所有情况，提醒后，给了正确算法，然后code,没错
我的思路是用suffix array，创建后sort，然后在sorted array中
比较相邻的元素，如果前面的字符串长度小于后面，则后面的字符串
应该包含前面的，且两个字符串的差就是循环的pattern - 如果对于
所有的相邻元素都成立，则可以确定原string是这个pattern的循环
大家看看有更好的思路么
abcdabcd:
abcdabcd abcd
bcdabcd abcdabcd
cdabcd bcd
dabcd --> bcdabcd
abcd cd
bcd cdabcd
cd d
d dabcd
ababab:
ababab ab
... 阅读全帖 |
|
m**q
发帖数: 189 | 29 Right t is no more than O(lgn)
But we still need to walk through all these
(k1+1)(k2+1)...(kt+1) numbers, so seems the complexity
for this is not going to be O(nlgn) with this method... |
|
m**q
发帖数: 189 | 30 直接sort是O(nlgn)， 用heap或者partition的方法是O(nlgk)更优啊 |
|
g*******e
发帖数: 61 | 31 昨天完成了A家的on-site, 一共四轮，最后一轮表现非常差，肯定挂掉了，继续海投吧
。之前在版上求了bless，现在攒RP，分享面经。
第一轮，美国小伙，说之前在MS，现在来A9个月了，Kindle组。目前参与A家的神秘项
目，不能讲太多项目内容，其实大家心里都知道是A的Tablet。
技术问题之前随意的聊了聊，然后问了一些很基本的CS问题。剩下20分钟，正式开始
tech question。很简单，给一本杂志，从里面剪字，看能不能找到指定的字符串。
我先给了brute force，O(n*m)，然后说如果用hash table, O(n)。然后说不让用额外
的buffer，怎么做？想了想，sort之后找substring，O(nlgn)。讨论完之后，说让我挑
其中一个写code。我说brute force简单，写的快，给了code后，挑了挑毛病，按时完
成。
第二轮，美国小伙。那个组不记得了。主要是面我OOD方面的问题。先问了我熟悉不熟
悉Java，答道还OK吧，刚想说很久不用Java了，问题直接就出来了。描述一下Java的GC
机制。说实话还真是记不太清楚了，现在主要写Pyth... 阅读全帖 |
|
h*********n
发帖数: 915 | 32 第一问谁看懂了？什么叫杂志里剪字？
发信人: glorywine (glorywine), 信区: JobHunting
标 题: Amazon On-site 最新面经
发信站: BBS 未名空间站 (Sat Sep 17 10:51:50 2011, 美东)
第一轮，给一本杂志，从里面剪字，看能不能找到指定的字符串。brute force O(n*m)
，hash table O(n)。不用额外buffer，sort后找substring，O(nlgn)。brute force写
code。
第二轮，OOD问题。描述Java的GC机制。reference counting蒙对了。设计餐馆订餐系
统。
我给了需要那些class，那些functions。指定其中一个方法，伪代码实现。
第三轮，binary tree找common ancestor。给字符串，每个字符出现的频率。从高到低
输出。
第四轮，hash table的实现。Boggle code实现，给game board，找所有valid word。 |
|
h*********n
发帖数: 915 | 33 第一问谁看懂了？什么叫杂志里剪字？
发信人: glorywine (glorywine), 信区: JobHunting
标 题: Amazon On-site 最新面经
发信站: BBS 未名空间站 (Sat Sep 17 10:51:50 2011, 美东)
第一轮，给一本杂志，从里面剪字，看能不能找到指定的字符串。brute force O(n*m)
，hash table O(n)。不用额外buffer，sort后找substring，O(nlgn)。brute force写
code。
第二轮，OOD问题。描述Java的GC机制。reference counting蒙对了。设计餐馆订餐系
统。
我给了需要那些class，那些functions。指定其中一个方法，伪代码实现。
第三轮，binary tree找common ancestor。给字符串，每个字符出现的频率。从高到低
输出。
第四轮，hash table的实现。Boggle code实现，给game board，找所有valid word。 |
|
m**q
发帖数: 189 | 34 第三题就是young tableaux
用一个最大堆，复杂度为O(nlgn)；
或者不断调用youngify，复杂度为O(n^2)
Here
ves |
|
i*******h
发帖数: 216 | 35 I feel that a sort is necessary, so at least O(NlgN). After that, a brutal
force can solve it in O((N**2)*lgN). Can remove the lgN if hash table is
used.
Simply put, for each element Ai, for each element Aj after Ai, get their
delta, and then check if Aj+delta is in.
Maybe DP is better? |
|
s****j
发帖数: 67 | 36 就是最长上升序列，比如1,6,2,3,5 其中最长的上升序列是1,2,3,5
这个n^2的完全可以写出来，nlgn的有点难度，不过应该也可以写出来 |
|
s****j
发帖数: 67 | 37 就是最长上升序列，比如1,6,2,3,5 其中最长的上升序列是1,2,3,5
这个n^2的完全可以写出来，nlgn的有点难度，不过应该也可以写出来 |
|
n*******w
发帖数: 687 | 38 sort的代价有点大，O（nlgn ）。
比较常规考虑，hashmap其中小的那个string list并且remove dups。然后把大的merge
进来。
如果考虑到hashmap可能overflow，换ties。还不够的话，先用hash function把
string list split到小文件上，然后再用hashmap来remove dups。最后直接合并成大
文件。
进一步，如果容许小概率出错，可以上bloom filter。 |
|
s******n
发帖数: 226 | 39 每次只取一个 a（当前最大），然后push a所在数组的下一个，如果数组空，任选一个
数组，选取最近的一个数
因为要选m次，所以有mlgn,再加上最开始的nlgn |
|
s******n
发帖数: 226 | 40 每次只取一个 a（当前最大），然后push a所在数组的下一个，如果数组空，任选一个
数组，选取最近的一个数
因为要选m次，所以有mlgn,再加上最开始的nlgn |
|
f***s
发帖数: 112 | 41 大家给看看
1.对于N个数组的最大元素排序建二叉树，树除了左右指针还有一个指针指向对应的
ARRAY
2.取一个最大元素（最右叶节点），更新节点为对应次大值，摘除并且重新插入上面的
二叉树，直到K个值都被耗尽。（存在重新平衡树的要求）
3.重复2.）直到 m个节点都得到了返回。
复杂度 1） nlgn 2)单个需要 lgn 总体最坏 (m-1)lgn
加起来 O((m+n)lgn)
1.因为N个数组都是SORTED，每次取得单个数组的最大值是CONSTANT time
2 |
|
|
a*****n
发帖数: 158 | 43 能不能讲解一下算法，代码不容易看。。。我能想到最坏O(nlgn)，有点想LIS算法。O(
n)好象不太可能 |
|
a********m
发帖数: 15480 | 44 按x排序nlgn. 然后hash+斜率也许有机会，还没完全想好。 |
|
b******e
发帖数: 52 | 45 来自主题: JobHunting版 - 这题咋做？ O(NlgN) |
|
m*******y
发帖数: 904 | 46 谢谢分享.很能理解.
我昨天也是一个很想去的公司第二轮onsite, 只需要再见两个人,仍然是Engineers. 第
二个人, 30多一白人,从一开始就感觉不太友好.先问的一个一般知识性的东西,问题提
得模棱两可,自己还变来变去,感觉他自己概念就不清楚,很难让人搞明白他到底要问什
么,怎么回答都象打在棉花球上. 第二个讨论算法的问题,他自己一个很基本的复杂度问
题搞错了(build heap O(n), 他非说是O(nlgn)), 和我纠缠了很长时间, 浪费了很多时
间也影响我的心情.整个过程我一再告诉自己要控制自己情绪, 不管他怎么问, 要积极
的应对.
晚上回来,想到之前经历了两轮phone, 一轮onsite.也是历时几个月.最后差一点点的时
候,很可能就栽在这么一个自己桨糊的人身上, 忍不住大哭一场.
该努力的都努力了. 面试这种东西, 还是我为鱼肉, 自己out of control 的因素太多
了. 真是悲从心中来.
recruiter |
|
m*******y
发帖数: 904 | 47 昨天一个很想去的公司第二轮onsite, 只需要再见两个人,仍然是Engineers. 第
二个人, 一白人小年轻, 从一开始就感觉不太友好.先问的一个一般知识性的东西,问题
提得模棱两可,还变来变去,感觉他自己概念就不清楚,很难让人搞明白他到底要问什么,
怎么回答都象打在棉花球上. 第二个讨论算法的问题,他自己一个很基本的复杂度问题
搞错了(build heap O(n), 他非说是O(nlgn)), 和我纠缠了很长时间, 浪费了很多时间
也影响我的心情.整个过程我一再告诉自己要控制自己情绪, 不管他怎么问, 要积极的
应对.
晚上回来,想到之前经历了两轮phone, 一轮onsite, 历时几个月.最后差一点点的时候,
很可能就栽在这么一个自己桨糊的人身上, 忍不住大哭一场.
该努力的都努力了. 面试这种东西, 还是我为鱼肉, 自己out of control 的因素太多
了. 真是悲从心中来.
虽然不抱太大希望了,还是求大家的blessings,希望能过最后这关. 过一阵子心情平复
了我也写点这段时间找工作的心得体会. 祝福这里的兄弟姐妹们,不管在找工作的那个
阶段,都继续坚持,... 阅读全帖 |
|
q****x
发帖数: 7404 | 48 来自主题: JobHunting版 - 问一道题目 按x/y分别排序。
任何一个点只需检查其x坐标上下六个和y坐标上下六个点。
这样是O(nlogn)+O(12n) = O(nlgn)。 |
|
S**I
发帖数: 15689 | 49 ☆─────────────────────────────────────☆
happymermaid (娆) 于 (Wed Apr 6 14:03:00 2011, 美东) 提到:
加recruiter一共6人
4个白男，午饭是一个组的经理 像是 土耳其／印度？ 人
除了最后一个都比较nice
另外每个人有时间都问一遍我RA做的项目，说到想吐
1. java keyword
实现浮点数的平方根，经提醒搞出来了。要考虑小于1的特殊情况； 还要想time
complexity，相对于小数点后精确位数算如何时间复杂度
2. paint fill (toggle)。关键是要考虑space complexity，主要是method stack实时
一共有多少
说了组里的相关一个问题，大概说说TRIE，有一个improvement方法不好答，他说的
用一个计算load balance function，我吐
午饭是其中一个经理，详细讲了下组里的东西，基本和我做的有点相关，感觉他们招人还是很看背景的
3. 给一个数据结构数组，（parent, child）， 重建二叉数，... 阅读全帖 |
|
i***h
发帖数: 12655 | 50 hash是O(N)
BST要O(NlgN)吧? |
|
