r*******k
发帖数: 1423 | 1 bst额外记一个小于等于当前key的点的个数
也就是左子树的节点个数，就可以了吧 |
|
a********r
发帖数: 217 | 2 但是树已经是建好的,重建的话至少要O (n)
时间。所以说能不能优化, 整数inorder search的时间是关键。 |
|
s**x
发帖数: 7506 | 3
参见 augmented data structure in algorithm introduction, 楼上已给出答案。
I do not think they ask you not modifying the tree. |
|
l*********b
发帖数: 65 | 4 我在想能不能通过level order的遍历 然后数数 大概判断一下kth在左还是在右 这样
大概就是logN了 但是仔细想了半天 思路不通。。。 而且恐怕事先不知道有多少个
node且bst不是balanced
。。。个人觉得 可能就还是线性时间复杂度吧- - |
|
r*******k
发帖数: 1423 | 5 要是balanced或者是满的
倒是可以猜猜
否则，普通的bst，必然是线性的 |
|
b********r
发帖数: 620 | 6 对头。如果BST退化成一个单链表，没法再LOGN里面完成。 |
|
M*****M
发帖数: 20 | 7 第三题
内部数据结构用BST，不用array?以便void store(int input)时lgN？
boolean test(int val)内部先inorder BST,然后two sum？ |
|
M*****M
发帖数: 20 | 8 第三题
内部数据结构用BST，不用array?以便void store(int input)时lgN？
boolean test(int val)内部先inorder BST,然后two sum？ |
|
c*****m
发帖数: 271 | 9 能不能讲第三题怎么做呢？要twosum得排好序才能O(N)，关键是用什么数据结构来保证
store()是O(lgn)的呢？ |
|
C********e
发帖数: 492 | 10 肯定不行啊
这样的话lgN都是O（1）的space了么？
而且如果我这个函数输入很大很大呢？或者需要在很多地方执行呢？ |
|
l**********1
发帖数: 415 | 11 lintcode 上的一个题， 要求时间复杂度是 O(lgn)
There is an integer array which has the following features:
* The numbers in adjacent positions are different.
* A[0] < A[1] && A[A.length - 2] > A[A.length - 1].
We define a position P is a peek if A[P] > A[P-1] && A[P] > A[P+1].
Find a peak in this array. Return the index of the peak.
Note
The array may contains multiple peeks, find any of them.
Example
[1, 2, 1, 3, 4, 5, 7, 6]
return index 1 (which is number 2) or 6 (which is number 7) |
|
c**s
发帖数: 159 | 12 转载一个大家共勉。
由于之前Amazon已经发了offer，deadline也快到了，所以不管这次Google on-site结
果如何，都不想再继续折腾，Amazon or Google。求职季到此结束，所以，是时候写点
东西回报地里了。本人NYU-POLY，EE专业，作为一个转行的，感觉自己的求职之路还算
挺顺利，希望自己的经历经验能对各位尤其是非CS的各位有所帮助。
一。
感谢一亩三分地，mitbbs, 米群网（QQ群：320065698，可能满了，但是管理员会清理
，大家可以加加试试，另外米群网也是一个非常不错的求职平台，大家可以通过这个链
接去注册下http://www.meetqun.com/member.php?mod=register&x=12）提供的求职信息，内推信息及面经，当然也得感谢LeetCode和CC150。充分利用上述资源十分必要，而且感觉这些已经足够了。
二。
觉得有必要介绍下自己的准备情况，也算给大家涨点自信。
前面说了我是EE的，所学课程，包括本科的课，都没有什么和计算机相关的。去年暑假
决定开始自学CS，为了毕业好找工作，也就是那时候我才写出了自己第... 阅读全帖 |
|
f*********s
发帖数: 34 | 13 Use last bit to separate numbers into two groups, then use the next last bit
to further separate them, remove any single number, keep doing it, the last
pair is the even number.
Complexity is still n*lgn though. |
|
w**********o
发帖数: 140 | 14 我目前只能做到O(n)
當然, 如果能用額外空間, 比如BST來做index的話, 可以做O(lgN) |
|
g**4
发帖数: 863 | 15 多谢LZ分享！
google第2题，当找到第一个triplet后，k也应该返回末尾，j加1，重新开始吧。这样
应该是O(n^3).应该可以用二分降到O(N^2 * lgN)
但是既然面试官给了个总数量大于1m的数组，是否是要求有别的解法？还得等高手来回
答。
另外请问下LZ，google第2题要求把完整代码写出来，bug free吗？
0 |
|
b******i
发帖数: 914 | 16 不懂，为什么说这个API会fail？
int myRandom(int n, vector bl)
{
//.....
}
另外，如果map的话建立map的过程需要O(n)的复杂度，怎么实现O(lgn)? |
|
b******i
发帖数: 914 | 17 不懂，为什么说这个API会fail？
int myRandom(int n, vector bl)
{
//.....
}
另外，如果map的话建立map的过程需要O(n)的复杂度，怎么实现O(lgn)? |
|
r*******e
发帖数: 340 | 18 时间复杂度的问题,
假设 共有N层楼梯， 鸡蛋在T层及以上会碎
你的方法类似binary search
需要lgN个鸡蛋， 平均复杂度是 lg(N)
原来的方法需要lgT个鸡蛋，平均复杂度是 sqrt(T) |
|
r*******h
发帖数: 315 | 19 treemap是bst，一样O(lgn)的插入，所以还是O(nlogn)
我倒是想到了一点优化，因为n很大的时候算power会overflow，所以一个做法是取对数
，这样就变成了k*log2 vs. k*log3 vs. k*log5，因为log保持了单调递增，所以就好
处理多了。 |
|
s******7
发帖数: 1758 | 20 treemap从头到尾只有三个元素（3个篮子），是lg3常数，那里需要lgn的插入 |
|
|
s******7
发帖数: 1758 | 22 这个题很莫名呀，O（n）很简单
lgn貌似不可能呀，任何一个都有可能是，怎么排除 |
|
n*****5
发帖数: 984 | 23 电话1；
How many distinct path to go from left upper corner to bottom right corner
in a matrix. input(row, col) --原题在glassdoor上都能找到的。
follow up 存这个中间结果矩阵啥的浪费空间，是否可以压缩一下。
How to save the internal results . -- In hashmap
How to implement the hash map key/values what the structure, how to
override hashcode & equals
deep structure of hashmap
Build the own equals method and talk about hashcode
What happened if there using default hashcode and equals method
equals 结构:
public boolean equals(Object o) {
... 阅读全帖 |
|
e***i
发帖数: 231 | 24 looks good! my 2cents in comments:
class LRUCache{ // maybe it's better to be templated key instead of 'int'?
public:
typedef map::iterator> > KVType; // map O(lgn)
vs unordered_map O(n) ??
LRUCache(int capacity) {
mCapacity = capacity;
}
int get(int key) {
KVType::iterator it = mKeyValuePair.find(key); //auto it = ...
if (it == mKeyValuePair.end()) {
return -1;
}
int result = it->second.first;
... 阅读全帖 |
|
c********5
发帖数: 26 | 25 我看paper能力不太行，不过看起来data stream里面是无序的，那样的话是要用堆加
count的，只是时间复杂度做不到O(lgn)
这里是有序数组，如果是n/k的话时间复杂度O(klgn)，空间复杂度本来就是O(k)啊
这里这道题比paper里面的简单吧，如果是那道题我应该写不出完整代码的，heapify什
么都没有写过 |
|
r****7
发帖数: 2282 | 26 电话号码的话，都是数字，用count sort的思路，binary search干这些事，最后复杂
度 > lgn 小于 n |
|
g******d
发帖数: 152 | 27 靠，有那么复杂吗？
< O(N) 有 O(lgN)
有没有插入删除，直接就来一个sorted array 就可以了
binary search |
|
e***i
发帖数: 231 | 28 geohash O(1)
k-d tree O(lgn) |
|
k******4
发帖数: 7 | 29 你想复杂了。这题不用看左右两个子树的返回值，只要一路DFS下去，看到比目前最大
值大的点，更新一下path就可以了。的确更新path是要O(LgN)的时间，在非最差情况下
可以忽略不计。
dfs(TreeNode* node, vector& path, int& maxNode, vector&
maxNodePath) {
path.push_back(node->val);
if (node->val > maxNode) {
maxNode = node->val;
maxNodePath = path;
}
if (node->left) dfs(node->left, path, maxNode, maxNodePath);
if (node->right) dfs(node->right, path, maxNode, maxNodePath);
path.pop_back();
} |
|
l******s
发帖数: 3045 | 30 二楼的思路我觉得有可能做到O(2 * lgN * N2)，只是那个第二步的B-Search有点麻烦
，因为是B-search一块Matrix。 |
|
l******s
发帖数: 3045 | 31 想做成O(m*lgm*lgn)超级烦，我放弃了 |
|
r*******g
发帖数: 1335 | 32 还是用bst的方法，但是每个节点要维护它下面节点的个数，也许segment tree也能做。
思路：
root就是第一个节点。对数组从左到右遍历，假设当前值为N，意味着，当把这个数插
入bst时候，有N个数比他大，也就是说有N个数在它插入后在它右边。因为每个节点维
护了它下面节点的个数，因此可以通过bst以lgN时间找到该节点应该插入的位置，这个
比较复杂，程序不好写。
最后得到了bst，也就得到了数值。 |
|
r*******g
发帖数: 1335 | 33 还是用bst的方法，但是每个节点要维护它下面节点的个数，也许segment tree也能做。
思路：
root就是第一个节点。对数组从左到右遍历，假设当前值为N，意味着，当把这个数插
入bst时候，有N个数比他大，也就是说有N个数在它插入后在它右边。因为每个节点维
护了它下面节点的个数，因此可以通过bst以lgN时间找到该节点应该插入的位置，这个
比较复杂，程序不好写。
最后得到了bst，也就得到了数值。 |
|
w****5
发帖数: 46 | 34 第三题用interval tree,对每个优先级建立一棵interval tree，对任意一个alarm，在
所有比它优先级高的interval tree中搜索，看有没有起始时间小于等于它，结束时间
大于等于它的alarm，如有，则该alarm在其生存期中从未成为过最高alarm，如无，则
该alarm当过最高alarm。但复杂度的精确值分析起来比较麻烦，用拉格朗日乘子法列出
来的对数方程组很不好解。一个非常rough的upper bound是O(k*k*n*lgn),k是优先级的
数量，n是alarm数量 |
|
j**********3
发帖数: 3211 | 35 以前狗家的一个问题：
怎么判断一个点在多边形里？o(n), o(lgn)
这个怎么做啊？
由此，我想到相关的问题：
1. 给你一堆多边形的顶点，无序，你怎么知道某个点的下一个点是哪个点？也就是说
，你怎么从这些点中找到边缘？
2. 怎么判断两个多边形是否有交集？
3. 怎么判断两个多边形合并后的顶点？
4. 怎么求多边形面积
一头雾水，忘有大牛解答。。。 |
|
r*******g
发帖数: 1335 | 36 union find, n*lgn可以解决问题，第一遍给出所有的集合的parent id，第二遍就简单
了。 |
|
l****u
发帖数: 1764 | 37 哪种数据结构search最高效？
我觉得是binary search tree，因为如果是balanced BST，O(lgN)的复杂度就能找到一
个element
哪种数据结构sort最高效？
这个我就不知道怎么答了，只听过哪种algorithm，没听过哪种数据结构的。基本上
sort一组数据，最快也得要O(NlgN)吧，用quick sort或者merge sort的话。但这几种
algorithm都能针对各种不止一种data structure吧，比如 array， ArrayList，
linkedlist
求大神指点 |
|
f****e
发帖数: 923 | 38 逆序输出一个单链表，要求空间复杂度为O(lgn)，不能修改链表结构（也就是不可以
reverse链表，然后再reverse回去），可以适当牺牲时间复杂度（其实就是O(nlgn)的
意思）
stock follow 可以随便交易很多次，可以同时买很多股票，但是一旦卖就要把手里的
股票全部卖了，问怎样最大化收益。比如[1, 2,3], 前2天都买，第三天全部卖，收益
就是(3-1)+(3-2). |
|
k***a
发帖数: 1199 | 39 第一题典型的divide and conquer, O(n)把链表切成两半,然后分别递归,和quick sort
一样,时间复杂度nlgn,空间lgn
第二题定义不清 |
|
s**********g
发帖数: 14942 | 40 set里为啥还能有重复出现的。。
估计是另一个数据结构吧
一种办法是统计一共有多少个
然后按照顺序group排列
例如Ax5 Bx3 Cx6
那就是14个
A是1-5 B是6-8 C是9-14
然后每次生成一个1-14的随机数
直接lookup
这样是O(1)的时间（或者O(lgn)，看你用多少memory存储了；时间换空间）
虽然初始的setup要O(n)时间 |
|
发帖数: 1 | 41 不在树上也是lgn。这个函数在树里，每层只看一个元素。所以树的高度就是复杂度 |
|
t****b
发帖数: 2484 | 42 1 没能与时俱进 提升算法能力
2 因为没有提升算法能力 有个O(lgN)的算法被我图省事写成O(N^2)了 |
|
|
z*********n
发帖数: 1451 | 44
这个正好说反了。
学生时面过G挂了，后来又面过G过了。从题的难度来讲，一样，甚至以前更难。当年挂
的一题现在记忆犹新，trap rain water。那时候LC根本没这题（还是压根就没LC来着
）。第一次见，自己生想了7分钟(看着表想的，印象深刻），写了需要O(n)空间解法，
结果follow up问有没有更优解法，我想当然的以为没可能O(1)空间或者O(lgN)时间,就
说没有，还试图证明来着，结果当然没证出来，丢人现眼，果断悲剧。如果当时有LC，
我当时可能就过了。
后来再面G的题难度，没觉着因为LC的出现难度就升高，反而能遇到1 2道原题（所以难
度降低了）。
所以这些刷题网站绝对是有帮助的。
学生时代真的是想努力不知道往哪使劲，有了这些网站，终于有个着力点了。 |
|
z*********n
发帖数: 1451 | 45 这是面试题吗？还是实际工程问题？
单纯追求更高速度，只能牺牲空间。
基于这个前提：“同一个data，findIndices会被执行多次”
最简单暴力的办法：
提前预处理计算好所有两两组合的结果，你的例子里，
预处理完后，应该有一项长成这样：
[100, 157] - [0,3,5,7]
至于输入的（100, 200）怎么map到[100,157],这个trivial吧。
这样的话预处理大概是n^3logn的时间，查询是logn的。
上面做法空间大小是 unique(A)^2*n (~=O(n^3))，按lz的数据规模，大了点
那就只能考虑牺牲查询时间，节约空间和欲处理时间：
考虑建个segment tree吧（按你的例子）：
[100, 300, 25, 123, 3, 157, 9, 103, 304]
排序后：
[3, 9, 25, 100, 103, 123, 157, 300, 304]
把上面这个数组建成segment tree，每个节点存对应range的坐标集合
类似：
（3...304)
[0,1,2,...,... 阅读全帖 |
|
a********h
发帖数: 819 | 46 What is lgns?
How to get to 80m oz covering from the table?
Thanks a lot |
|
|
t*******y
发帖数: 11968 | 48 【 以下文字转载自 Basketball 讨论区 】
发信人: Rafer (Alston), 信区: Basketball
标 题: Breaking News: Tracy closer to NY
发信站: BBS 未名空间站 (Mon Feb 15 18:11:35 2010, 美东)
http://sports.yahoo.com/nba/news;_ylt=AtnYWLqrSYsgb4ziym_lfYK8vLYF?
slug=ys-knicksrocketstrade021510&prov=yhoo&type=lgns
The New York Knicks are getting closer to reaching the Houston Rockets’
demands for Tracy McGrady(notes) and his $23 million expiring contract,
league sources told Yahoo! Sports.
The Knicks and Rockets have designed the framework |
|
i********6
发帖数: 4766 | 49 en, they have a famous library, and some art gallery in the beach line town.
I like LGN better than LJ, plus they have quite a few good restaurants in
town too.
taking amtak is a good idea, but driving alone the coast line is very enjoyable too. |
|
|
