r*******g
发帖数: 1335 | 1 还是用bst的方法，但是每个节点要维护它下面节点的个数，也许segment tree也能做。
思路：
root就是第一个节点。对数组从左到右遍历，假设当前值为N，意味着，当把这个数插
入bst时候，有N个数比他大，也就是说有N个数在它插入后在它右边。因为每个节点维
护了它下面节点的个数，因此可以通过bst以lgN时间找到该节点应该插入的位置，这个
比较复杂，程序不好写。
最后得到了bst，也就得到了数值。 |
|
d****t
发帖数: 748 | 2 Thursday 26 April
First round matches (best of 19 frames)
1430 BST
John Higgins (Sco) v Michael Holt (Eng)
1900 BST
Ali Carter (Eng) v Andy Hicks (Eng)
Second round matches (best of 25 frames)
1430 BST
Shaun Murphy (Eng) v John Parrott (Eng)
1900 BST
Anthony Hamilton (Eng) v Ian McCulloch (Eng) |
|
d****t
发帖数: 748 | 3 顺便预测一下 （其实就是瞎猜）
Saturday's second round matches (best of 25 frames):
1000 BST:
Anthony Hamilton (Eng) 10-13 Ian McCulloch (Eng)
Mathew Stevens (Wal) 8-8 Mark Allen (NI)
1430 BST:
Stephen Maguire (Sco) 13-7 Joe Swail (NI)
Stephen Hendry (Sco) 5-3 Ali Carter (Eng)
1900 BST:
John Higgins (Sco) 6-2 Fergal O'Brien (Ire)
Mathew Stevens (Wal) v Mark Allen (NI)
(这个就不猜了，万一上午的错了，就瞎搞了)
Saturday's second round matches (best of 25 frames):
1000 BST:
Anthony Hamilton (Eng) 8-8 Ian McCulloch (Eng)
Mathew Stev |
|
d****t
发帖数: 748 | 4 John Higgins (Sco) 12-4 Fergal O'Brien (Ire)
(resumes Monday 1430 BST)
Stephen Hendry (Sco) 4-12 Ali Carter (Eng)
(resumes Monday 1430 BST)
Ronnie O'Sullivan (Eng) 6-2 Neil Robertson (Aus)
(resumes Monday 1000 BST)
Peter Ebdon (Eng) 4-4 Mark Selby (Eng)
(resumes Monday 1000 BST)
hendry啊，真是无语了，两个session让人弄俩6-2真是状态太差了！！ |
|
c****p
发帖数: 6474 | 5 你说的应该是二叉搜索树BST。
有些数据结构的底层实现实际上是用BST及其变种实现的，你没有直观地看到BST而已。
就我所知，C++里面的set是用红黑树（平衡BST）实现的。
FORTRAN |
|
q**j
发帖数: 10612 | 6 type： warning
line: line 1
message: Labels may have changed. Return to get cross-reference right.
今天突然出现这么一句话。我就是改了改bst file。不知道为什么这样。请教请教。多
谢了。
这个bst是jf.bst with harvard package. 我如果把 bst改成plain就没有问题了。 |
|
j**********n
发帖数: 527 | 7 \bibliography{yourBibFile}%the .bib file
name only
\bibliographystyle{yourJournalStyle}%the .bst file name only
如果没有现成的 bst
找相近的bst改，或者用命令自己做。
latex makebst
如果journal要求内嵌\bibitem，用bst编译好后，所有的\bibitem都在同名的bbl这个文
件里面。 |
|
d***a
发帖数: 13752 | 8 你用的bst就是这样format的。可以换bst，或自己改bst。 |
|
|
B*********e
发帖数: 86 | 9 GL2017 (GL2017)同学/老师，
对不起，垃圾俺最想知道的是你在phone interview。。。两次回答这个问题：
Will you fit into the culture and working environment of our department
easily?
的时候，是怎么回答的呢？？~~。。。@@[email protected]@... … ..
能写一下么？？~~。。。@@[email protected]@ … … ..
垃圾俺实在是有一颗酷爱八进制的心~~。。。欧不，俺没心没肺的。。。@@[email protected]@。。。
：（（。。。555… … .. ------ 应该是 ----- 垃圾俺实在是酷爱八进制。。。@@[email protected]
@。。。：（（。。。555。。。：）） … … ..
GL2017 (GL2017)同学/老师，你就写一下吧，刑部？？~~。。。@@[email protected]@。。。：））…
… ..
先谢谢了。。。：））… … ..
祝好~~。... 阅读全帖 |
|
B*********e
发帖数: 86 | 10 http://www.mitbbs.com/article_t/Faculty/31894869.html
jiayou17 ()同学/老师，你说 -----
“被系主任assign了一门课，他把课件全部share给我了。
。。。。。。。。”
你的意思是说你们系主任(??)assign(??)给你的这一门课（？？）是有历史、有传承、
有。。。？？~~。。。什么的？？~~。。。@@[email protected]@。。。：））… … ..
对了，你在教这门课/上这门课的过程中能记录一下。。。历程。。。等等啊什么的么
？？~~blog博客或者连载个系列贴子啥的？？~~。。。@@[email protected]@。。。：））… … ..
祝好~~。。。：））… … ..
[email protected] BST.
To be [email protected]@2315 BST.
To be [email protected]@2325 BST.
([email protected])
发信人: jiayou17 (), 信... 阅读全帖 |
|
B*********e
发帖数: 86 | 11 (2018-05-29#1952-)
回帖_BiggeyIssue_to onewayticket et al_mitbbs_2018-03-08 ~ 05-16__05-26#
1727-1845_s#1846_05-29#1952-.docx
(2018-05-26#1730)
回帖_BiggeyIssue_to onewayticket et al_mitbbs_2018-03-08 ~ 05-16__05-26#
1727-.docx
另见：
2018-05-22#2309.doc
Copy of 2018-05-22#2309 [2018-05-22#2309 ~ 2018-05-23#0344b 中国时间，小米
手机 WPS app应用 上面记写，#2018-05-23#1604 BST QQ传输到我的电脑，c#1606].
doc
[[2018-05-26#1733]]
(2018-05-23#0206中国时间)
2018-05-22#2309.doc
(2018-05-23#0207中国时间)
onewayticket 老师/同学，
祝贺你收到(至少？~..)三... 阅读全帖 |
|
x****g
发帖数: 109 | 12 Hi everyone,
I just had my first round technical phone interview with Google three days
ago for summer intern.
But I did not get any feedback, nor information about the time of my second
round.
Does this mean I failed the first round?
Here is the question I had and my answer, I think I answered them correctly.
1. Suppose there is a binary search tree, and you are given the in-order
traversal result of this BST, how to re-construct the BST?
My answer: the BST can't be re-constructed, because the |
|
s********l
发帖数: 998 | 13 来自主题: JobHunting版 - AMZ面经 在本版收益颇多
发面经，攒人品
很多记不得了，能记住的都写出来了
Phone 1:
1.Hash table vs bst
2. 给一个array, 找出相加等于给定sum的2个数
3. 一个array, 里面的item全都even number 重复，只有一个odd number重复，找出这
个数
4. 给几个字母，给个algo，来查看是否可以由这几个字母组成个存在的word
5.coding 2个array 的intersection
3天后phone 2
1. 给1-5的random generator, 写1-7的random generator
2. 找出所有，只能由2，3，5除开的小于某个给定值的所有数,coding
1周+3天后安排onsite
见了5个人
第一个
1. 找k大数
2. Bst的一个什么题，忘了
每个都给algo,然后coding
第二个
1.让我估计apple webpage 访问量
2. coding 给出任意二个年月日，看是否在一个月内
第三个
Lunch 忘了问了什么了
第四个
Hash table vs bst |
|
i*****e
发帖数: 113 | 14 VOD组，不过应该没有什么参考意义，因为题目太简单了。不知道能不能进入第二面。
怎么说也不要第一面就把我拍死吧
美白
- why amazon
- your experience/strength/etc
- what is BST, the complexity in best case and worst case, how to know the
BST is in worst case
- write code: recursively visit a binary tree
- how to find a key in BST
- write code: given an array, find the second maximum value
- do you have any questions
奇怪的是一点C++的东西都没问我
如果失败那一定是英语表达的问题，在念代码的时候，我还老改，不知道他明白没有 |
|
n*****g
发帖数: 16 | 15 感觉你那个merge 2 BST的程序有点问题。看看下面这个code：
Node* MostLeft(Node *root)
{
if(root->left == NULL)
return root;
else
return MostLeft(root);
}
// Merge two BST in to one BST.
Node* MergeTwoBST(Node* root1, Node* root2)
{
Node *left, *right, *mostLeft;
if(root1 == NULL)
return root2;
if(root2 == NULL)
return root1;
if(root1->value > root2->value)
return MergeTwoBST(root2, root1);
if(root1->value < root2->value)
{
right = root1->r |
|
p********7
发帖数: 549 | 16 给楼主补充几个题吧
BST转为双链表
双链表转为平衡BST
求leaf之间最大距离
由inorder和preorder的序列，重建BST |
|
i**********e
发帖数: 1145 | 17 leaf 之间最大的距离？不是很懂。leaf之间必须是同一个level的吗？如果不是同一个
level的应该怎样？
我知道preorder序列能重建BST。但inorder序列不能重建原来的那个BST吧。是不是
inorder序列建一个平衡的BST？
感谢你的补充题，我会研究研究下。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
P*******b
发帖数: 1001 | 18 记得问过，不过没有搞定。
给一个bst，用递归求第kth节点。要求返回node
不能用额外的空间。bst是普通的bst，node没有子节
点的数目。
thanks |
|
s*****n
发帖数: 5488 | 19 #include
use namespace std;
void k-bst(Node * root, int k)
{
static int i = 0;
if ( root )
{
K-BST(root->left, k);
if (++i == k)
cout << root->data;
k-bst(root->right,k);
}
} |
|
d**e
发帖数: 6098 | 20 我没测试，改写独孤九剑同学的
Node * k-bst(Node * root, int k)
{
static int i = 0;
Node * p = 0;
if ( root )
{
if((p = K-BST(root->left, k)) != 0)
;
else if (++i == k)
p = root;
else
p = k-bst(root->right,k);
}
return p;
} |
|
s*******e
发帖数: 93 | 21 Does this still work if there can be negative numbers?
E.g. 1, -2, 3, -4, 5?
Could you please explain the FIFO sub array in more detail?
What I was thinking about is quite similar to hopen's idea
We can calculate the sum from a[0] to a[i] for each a[i]. (Say b[i]=a[0]+a[1
]+...+a[i])
In the meantime, maintain a BST to store the b[i] values
After getting b[i], we search if the node in the BST which is the most close
to t - b[i].
Then add b[i] to the BST (together with i).
It is nlogn, and one sca... 阅读全帖 |
|
g*********s
发帖数: 1782 | 22 后面那道写代码的题我说错了！他让我写的是 创建我所说的bst that each node
contains the number of descendants in the subtree rooted at this node，就
是一个创建二叉排序数的过程，很简单。
what is "创建二叉排序数"? u mean creating a bst given an array, or given
the bst, calculate each node's sub-tree size? the former is not that
straightforward while the latter is easy.
n-
度应该是多
少？ |
|
g*********s
发帖数: 1782 | 23 with unbalanced bst, you can't query the median in O(lgN). so the bst you
created doesn't meet the requirement of (2).
for creation of a balanced bst, there's extra work to do. that's why i say
it's not straightforward.
http://en.wikipedia.org/wiki/Binary_search_tree#Insertion, set
numOfDescendents of the newly added node to 1 and increment
numOfDescendents of the nodes along the insertion path by 1. |
|
X*********n
发帖数: 570 | 24 背景: cs fresh phd 菜鸟 无任何industry 经验
从10月14号第一次校园面试到今天正式签了offer letter寄回给公司, 整整三个月的找
工总算是告一段落了.
也不记得是9月底还是10月初的时候, 学校career fair, 那时候还没有正式准备找工作
, 或者说刚有找工的想法, 还没有开始复习, 就打印了几分简历, 折成纸飞机, 对准了
几个大公司投射了过去. 这次career fair, 促成了我头两个面试. 一个是M, 另一个是
A.
说起来M的面试真是搞, 面试前几天HR给我发信让我给想要的职位排个队. 那form上白
纸黑字写的清清楚楚, 只是给各个职位列个先后顺序, 还说无论怎么选, 都会考虑
Software Engineer 也就是传说中的码工. 这次我土了, 我想PH.D好歹选个Project
Manager吧, 然后把码工列在了第二位. 交了表约了10月14号面. 结果面试当天去到现
场, 面试官是个老印, 说你面Project Manager啊, 我说是啊. 那说说怎么给Kids
design一个vehicle吧. 我大脑先短路了大概... 阅读全帖 |
|
g*********s
发帖数: 1782 | 25 我感觉即使是bst也不能保证O(N)，虽然一下构造不出反例。
但是反过来，你怎么证明bst下是O(N)？
关键做DFS，即使是balanced bst，你遇到的current_path路径可能仍然恰好是严格单
增的，这样
你要反复清空max_path再复制current_path。这里有个sigma。 |
|
d***8
发帖数: 1552 | 26 题目和解法如下。 没看懂解法。
Question: Axis Aligned Rectangles
Describe an algorithm that takes an unsorted array of axis‐aligned
rectangles and returns any pair of rectangles that overlaps, if there is such
a pair.
Axis‐aligned means that all the rectangle sides are either parallel or
perpendicular to the x‐ and y‐axis. You can assume that each rectangle
object has two variables in it: the x‐y coordinates of the upper‐left corner
and the bottom‐right corner.
Good Answer: Create a sorted array of the x coord... 阅读全帖 |
|
i**9
发帖数: 351 | 27 合并2个BST, 要求O(n)time,
flatten two bst by in order traversal ,and rebuild a bigger bst, 有更直接的
办法吗
replace( |
|
h**********d
发帖数: 4313 | 28 how do you do a balanced bst? from your randomly generated new numbers?
notice we are inserting new numbers into a bst here, not create a bst |
|
b*******8
发帖数: 37364 | 29 如果要现场Coding，涉及到BST的操作可以用伪函数代替吧，如果是平衡BST那就更是如
此。其他部分并不复杂。要展开写平衡BST的构造维护，那就是一个专门的面试题目了
。 |
|
s**x
发帖数: 7506 | 30 这个怎么样？
也用 BST, every node has extra info to remember how many nodes on its left
subtree, and original index in the array. then scan the array from right to
left, so we can easily build a whole BST as the array tells us how many
nodes are less than a node.
at the end scan the BST by in-order and fill the numbers from 1 to n. |
|
s*****n
发帖数: 5488 | 31 1. heap sort, then you are done.
2. recursive call,
fin max in bst,
swap root the most right one
do it for left bst, do it for right bst.
no |
|
g**********y
发帖数: 14569 | 32 你说的是array到balanced BST算法吧？Balanced BST怎么保存在原数组里，满足堆条
件和BST条件：
parent(i) = (i-1)/2
left(i) = 2*i + 1
right(i) = 2*i + 2
a[left(i)] < a[i] < a[right(i)]
法. |
|
k****n
发帖数: 1334 | 33 来自主题: JobHunting版 - 一道G家题 bst(a, low, high):
if (low >= high) 找到了就
mid=(low+high)/2;
if(a[mid]-a[low]>mid - low)
bst(a, low, mid)
else
bst(a, mid, high) |
|
s*****n
发帖数: 5488 | 34 来自主题: JobHunting版 - 一道G老题 this should be open. you can either use
inorder travesal of bst and sequantial scan of arry
or
use
search each element in arry in bst.
or use
inorder traversal of bst and binary search of array |
|
s*****n
发帖数: 5488 | 35 来自主题: JobHunting版 - 一道G老题 this should be open. you can either use
inorder travesal of bst and sequantial scan of arry
or
use
search each element in arry in bst.
or
inorder traversal of bst and binary search of array |
|
k****n
发帖数: 369 | 36 来自主题: JobHunting版 - 一道G老题 You must be cautious and get enough information before giving an answer.
Such as, how large is the bst and the array, is the bst balanced ...
After all, the BST provides no more information than a sorted array.
So this problem is just the same as "intersection of two sorted arrays"
which should be easy to answer... |
|
f****4
发帖数: 1359 | 37 来自主题: JobHunting版 - 一道G老题 If the BST has parent pointer, you can find the smallest element, then use
next_element() to iterate BST.
In the same time you can iterate the array. Compare the current node and
current index, if same, you find intersection. Otherwise if current index is
bigger, iterate BST. Otherwise increase current index. Stop when tree is
iterated or array is iterated.
No matter they have duplicate elements or tree is very big, you have O(n)
speed with O(1) space |
|
N*******7
发帖数: 14 | 38 MS刚毕业，没有任何工作经历, 前天去P公司onsite，其实蛮早就拿到了onsite通知，
结果因为自己月底要搬去湾区，所以就和公司商量改到了八月初，顺便可以有时间再准
备一下。
下午一点到四点半，一共五轮. 第一个白人主要是考查一些high level的东西，brain
teaser, 他貌似很喜欢那种题目，竟然连续给了四道，都是比较经典的（比如三盏灯问
题），比较轻松地解决了。
正当自信心不断增长时，第二个老中给了我一个下马威，一来就上coding, 打印螺旋矩
阵,当时就有点傻了，这种题目平时基本就疏忽了，边界问题刚好是弱项，然后临场就
开始紧张了，写了第一个loop 后竟然不知道怎么样去递归了，汗……给了一点提示，
最后竟然也没有写出让他满意地结果，太菜了，心态也不好……
第三个老中准时到达，问我要不要休息，心想反正也受到打击了，还休息什么，上题吧
……先是问了一些project 地东西，然后就开始各种拓展了，答得不是很理想，剩半个
小时的时候终于上题了，
非平衡BT找LCA，由于本人比较懒，只练过BST，对于BT还是比较生疏，然后就说了一种
算法，结果那人说不对，汗……然后... 阅读全帖 |
|
r******n
发帖数: 170 | 39 贴个tree的版本，不过空string对应空tree的时候，似乎空指针处理的有些ugly，求更
简洁版本。
struct BNode
{
char c;
BNode* left;
BNode* right;
BNode():c(0){}; //avoid uninitialized value for c
BNode(char _c):c(_c),left(NULL),right(NULL){};
};
void pre2bst(string pre, size_t& start, size_t len, BNode* &p)
{
if(start
{
p=new BNode(pre[start]);
size_t curr=start;
start++;
if(pre[curr]=='+'||pre[curr]=='-'||pre[curr]=='*'||pre[curr]=='/')
{
pre2bst(pre,s... 阅读全帖 |
|
v***a
发帖数: 365 | 40
冲突
多谢分享！比atoi有意思多了。。。。
感觉32位Unicode字符统计BST或许会好点。
分布的情况貌似可以这样：
1）所有机器的Top 1% freqent unicodes. 得到这些集合的交集 X。
2）如果 X 是空集，扩展到2%，重做，直到X不是空集。
3）频率最高的在 X 中，统计X中所有unicodes的频率，取最高
肯定code不出来了，涉及到了BST, Heap, Hash, Disjoint Set and splay tree.
而且最坏情况还是传输了所有机器的 BST……比 hash 还糟糕点，呵呵
攒点字数，RP守恒！ |
|
z****u
发帖数: 104 | 41 这个应该就是一个 BST 的变种吧
按照 span 的 begin 值建立 BST
每次插入一个新的 span 的时候，如果这个span的 begin 值在某个 node 的范围之内
，合并，否则就是按照 BST 的规则进行插入
值得注意的是，合并的时候，需要判断合并后的 span 跟它的右儿子有没有相交，有的
话，继续合并，然后删除右儿子 |
|
g*********e
发帖数: 14401 | 42
我答的是这样的，请大家指正。
我谈了做实习时给图做优化，sign extension的问题。eda的东西，他听了似乎不是太
有兴趣。
hashtable O(1) access time， no order，通过key来map
bst O(logn) time, but can retain the order of stored item
我一开始说bst是balanced tree. 他指出不是。又问bst不balance会怎么样，worst
time analysis. 以及有啥方法balance. 我跟他说avl tree 或者红黑树，但没要求写
具体代码。
接着还追问了hash collision怎么处理，我说可以弄个list append上去，或者probing
(然后稍微解释了下probing)
我首先想到的是debug statement的副作用，可能里面执行了什么函数。其他我说想不
出来。他说加了一行code会改变什么？我说executable大小会改变，load到内存位置也
会不一样。我说可能是内存某一块坏了，刚好load到了那块。接着他问还会改变什么？
我说可能... 阅读全帖 |
|
P*******U
发帖数: 203 | 43 The first one is BST or just binary tree? What do you mean by the next
greatest value? Is it the second largest value?
If BST and next means second largest, then easy.
Node* p=givenNode;
if(p->rightChild==null)
return FindLargestInLeftSubtree();
while(p->rightChild->rightChild!=null)
p=p->rightChild;
return p;
If not BST, you have to traverse the tree?
The second one can be solved with a stack. Once seen a "(", push into
stack;
seen a ")", pop. If the stack is empty when operating pop, ret... 阅读全帖 |
|
y******n
发帖数: 67 | 44 so every time when doing a match, a BST is created? if that has to be the
way, how about creating a max-heap?
can we not creating BST frequently? I am looking for something that is more
efficient in run-time! creating BST in run time is memory-consuming and time
-consuming given large # of data sets.
thanks! |
|
z********c
发帖数: 72 | 45 F的：
1. BTree求高度，宽度，某节点中序遍历下的Next，有parent节点
2 单链表倒序输出
3. Dutch Flag Problem
4. 给出一个排序好的字符串数组，给prefix，求所有前缀为prefix的字符串
5. 初始N个人，站在ROOM外，给一个move(i)函数，如果i在外面，move以后就到room里
，如果在里面，就移动到外面，要你给出一个move函数，使得N个人的所有子集在房间
中出现且仅出现一次，比如两个人，
初始 {}
move(1): {1}
move{2}: {1, 2}
move{1}: {2}
G的：
1. BST求某个节点的next节点，有parent指针
2. 两个BST，求他们merge后的BST
3. 一个硬盘上全是文件，求把同样文件不同文件名去重怎么做
4. 一堆数求最大1000个
5. sleep sort，跟我讨论os kernel进程调度的实现和复杂度
6. 拓扑排序
7. scramble string，对一个string，比如tiger，可以随便找一个partition tree
tiger
/ ... 阅读全帖 |
|
c***p
发帖数: 221 | 46 我的方法是分别把每个BST按照in-order转换成linked list; 然后merge;从merge后的
linked list 建立新的BST.创建新的BST的时候，把list的中点作为root,这样就尽可能
使得tree是balanced. |
|
l****i
发帖数: 230 | 47 这周周二的onsite，一共五轮面试。安排比较混乱，其中一个interviewer，我干等了
半个小时，no show。联系HR，才知道这个interviewer已经休假5个月。所以后来又加
了一个interviewer。
感觉google的面试根本不考虑candidate的背景和经历，只考coding。我有朋友做到了
CS Top-4的正教授，去google面试仍然是一样的流程。这个确实让人非常frustrated。
1. Thesis discussion：老印，data base出身，鸡同鸭讲，面得很费劲，互相感觉都
不是很好。
2. 老中，coding：给一个N个node的BST，给一个Key，返回与key最接近的m个node(m
).
我开始说可以做inorder traverse，用一个priority queue保存跟key最近的m个value
，复杂度O(n)；存在average O(log n)的算法，但不好写。结果还是被要求写O(log n)
的code。
这个算法不是很难(不确定是不是最优)，但是在30分钟写出来确实不容易。
我的基本思路还是用priority... 阅读全帖 |
|
G******i
发帖数: 5226 | 48 ☆─────────────────────────────────────☆
ctozlm (ctozlm) 于 (Sun Dec 18 00:08:10 2011, 美东) 提到:
电面第二天通知onsite.先说一下对b家的印象。我觉得他家还挺厚道的，hr比较nice，
酒店不错。办公楼和其他大it公司比，小福利一般，但是装修要fancy得多。
深夜两点钟才到宾馆时差没怎么倒就起来去面试了，hr还把时间搞错了。。。就是传说
中的俩小兵。一个三哥，一个白人。说话都很清楚。
btw，之前看他家一般都要考brain teaser.所以特地去quant版准备了一下，然后去
careercup上做他家的brain t。发现他家稍微难点的题都是经典题，其他的基本现想就
能知道答案的。难度在brain t里并不算高，可惜电面和onsite一个都没问。
面试官上来先问了why bloomberg热身？然后就是简历谈research。枉费我讲了大半天
，小印问你这个能用在哪。我给他解释了一下，发现他对kinect的理解还停留在
windows画图的层次就知道白讲了。有说了不同的项目，他俩... 阅读全帖 |
|
r*****e
发帖数: 146 | 49 For BST case, time: O(N), space: O(N)
1) in-order scan the tree into an array,
2) 2sum scan the array
弱问一下，若是用get_next(), get_pre()从两边往中间扫。
具体的get_next()和get_pre()的实现是什么？
(1) 存个临时变量，以及相应的栈？ 若是如此，每次get_next()的时间是O(1),stack
takes O(N) space.
(2) 不存临时变量，每次binary search the next closest value? time is O(logN),
space is O(1)
If we adopt option (1),for bst case, time is O(N), space is O(N)
If we adopt option (2),for bst case, time is O(NlogN), space is O(1)
不知理解是否正确，请指教 |
|
O******i
发帖数: 269 | 50 多谢，不过这题我之前没见过，未能在规定时间内想到，他也没有给太多提示。
其实Bitmap之前我就向面试官提到用BST, 不过我每个节点是一个数，所以查找是要O(N
* logN), 比Bitmap的O(N)还差，就自己轻易否决了。
有序数组要插入删除一个元素，操作是O(N), 但是对应的平衡BST, 插入删除一个元素
是O(logN)，那么什么场合下有序数组比对应的平衡BST要好？ |
|
