|
|
x******3
发帖数: 245 | 3 store the subtree size in each node, lgN time complexity |
|
P*******b
发帖数: 1001 | 4 记得问过，不过没有搞定。
给一个bst，用递归求第kth节点。要求返回node
不能用额外的空间。bst是普通的bst，node没有子节
点的数目。
thanks |
|
b********h
发帖数: 119 | 5 似乎没啥问题啊。
函数的局部静态变量在第一次调用的时候初始化。
一旦找到kth节点之后，它就会被不断的返回到上层的调用，直到根节点，结束函数的
执行。 |
|
x**y
发帖数: 70 | 6 换句话说,
O() = n*logn + n/2*log(n/2) + n/4 * log(n/4) + ... + 1
最后是 O(nlogn) 吗?
类似思想: 找 kth largest element in int array 是:
n + n/2 + n/4 + ... 1
最后是 O(N) |
|
l*****o
发帖数: 214 | 7 两个都是Amazon的，但是不同的组，都不是Amazon总部，全是分支。个人我也是喜欢分
支部门，比较有独立性，也能学到挺多东西～
1. Cupertino,CA
Kindle group, 做UI,实话实说我自己在UI方面也是刚入门，组比较稳定，现在Kindle
销量不错，书卖的也不错，本身还在扩张。据说只有这个部门有自己独立的recruiter
和HR。E-ink技术还有Kindle本身的平台其实都比较有吸引力，但是用JavaSE感觉有点
陈旧，黑白的肯定不如彩色的有趣啦。。。不知道以后还能不能用在其他地方。
2. Orange County, CA
A2Z group, 做网络游戏平台的，我自己也是做web service有些小经验，公司以前是
start-up,被Amazon买了然后合并到A2Z.面试的时候跟组里的人聊天，每个都是挺厉害
的那种，有时候都感觉有点压力。似乎上层有些信任危机，新调来的头儿扭转了局势，
但是以后不知道如何。。。人都不错，但是20个都是男的。。。以后岂不是一个女性伙
伴都没有了。。。有点害怕～
我有几个考虑就是：
要是搬家，老公也要一起搬，当然希望他能... 阅读全帖 |
|
|
|
c**m
发帖数: 535 | 10 这个题目就是online median selection, 我觉得two priority queues (min-heap &
max-heap)应该是目前比较理想的办法了，而且也好理解。
hopen的解释很详细了。
对于题目二，如果单纯一次性找到一个array的mean，并且不用sorting的话，可以用
kth element selection method。但这方法又不能用在data stream上。
面试官的提示很奇怪呀，莫非他只是让你找mean，而不是median？
Anyway, bless~~ |
|
y*********e
发帖数: 518 | 11 Let's say we don't use a single array for storage. Instead, we use a list of
arrays.
Let each storage array to be size of M, which is a constant.
To access the Kth element, we can know in which storage array and in which
position in that array the element is located.
Accessing array is constant. If we can indexing the storage arrays and find
which one it is located in a constant time, then everything could be done in
constant time.
That would be simple. Maintain an array that stores the pointer ... 阅读全帖 |
|
i**********e
发帖数: 1145 | 12 最近非常热门的一道 google 题，大家讨论讨论.
Two reverse sorted arrays A and B have been given.
such that size of A is m and size of B is n
You need to find the k th largest sum (a+b) where a is taken from A and b is
taken from B. such that k < m*n
本版又讨论过，但是好像没什么结果。
http://www.mitbbs.com/article_t/JobHunting/31684697.html
这题其实可以转换成另外以下的题目（杨式矩阵）：
Given a N*N Matrix.
All rows are sorted, and all columns are sorted.
Find the Kth Largest element of the matrix.
我想到一个利用堆的解法，可以达到 O(k log min(m, n)).
但看网上 google 要求的最优解法好... 阅读全帖 |
|
c****e
发帖数: 2 | 13 Given a N*N Matrix. All rows are sorted, and all columns are sorted. Find
the
Kth Largest element of the matrix. |
|
M**********e
发帖数: 211 | 14 row and column sorted array, how to find medium?
more general, how to find the kth number? |
|
n********5
发帖数: 323 | 15 reverse sorted arrays 是不是可以 divide and conquer同时比较两个array的值..
. 例如：
a1
b1
可以比较a2<>= b2..
因为找Kth max,同时是reverse sorted. |
|
n*******s
发帖数: 482 | 16 Sigh... can't figure out a net solution.
想了一个需要改变Young Tableu 得法子，每次删除当前最小M[0][0]，然后花费M(行)+N（列）的代价重组YoungTableu 作K次 返回M[0][0] |
|
|
s******s
发帖数: 3694 | 18 C 的话， function params, reference 很少用或者基本不用。 有些编译器支持， 有些不支持， 你这个问题应该是失分比较多。 C++ 的话， 就随便搞了。
bst 这个指明需要找到数第二个而不是 kth， 用两个临时指针交换就可以了， 这个基本没有得分， 应该
cache 的这实际应用可能比较多一些， 客户端的 cache 应该也是很重要一部分， I/O 和 serialization 应该对性能会有帮助 , 服务器端的话， 就需要经验了， 可能需要内存，文件映射或者数据库的高手回答了 |
|
f*********i
发帖数: 197 | 19 Given two arrays A and B in ascending order with size m and n, respectively,
question:
find the Kth largest sum(a+b) where a in A and b in B, 1 |
|
|
f*********i
发帖数: 197 | 21 Given two arrays A and B in ascending order with size m and n, respectively,
question:
find the Kth largest sum(a+b) where a in A and b in B, 1 |
|
|
f********3
发帖数: 210 | 23 如果节点里面没存the number of nodes，有啥好办法么？(一个人的面经里面说，面
试官指出节点里面没存the number of nodes under a root)
或者直接中序遍历？
欢迎讨论&&指点 :) |
|
c**y
发帖数: 172 | 24 define two helper functions first.
1. min_BST(root)
2. succ_BST(curr)
then traverse the BST in the following way
for (node = min_BST(root); node; node = succ_BST(node)) {
// do something for each node
}
This is how a BST is traversed. |
|
i******t
发帖数: 158 | 25 按right-root-left 的顺序中序遍历, 第k个数就是 |
|
v*********u
发帖数: 4 | 26 顶三楼.
有个地方要注意
1.如果允许静态/全局变量,问题很容易,找到传值回来就行
2.如果1不行,需要自定义类,里面包含counter,返回值,数到k以后的直接返回,而且不去
其他分支
面试一般很有可能开始允许你用static,然后等你全对了问你不准的情况 |
|
m**q
发帖数: 189 | 27 不需要static吧，直接传参数记录当前第几个就行了
PS. 这个题应该也可以用分治来做，期望复杂度应该也是O(N)。
(和在数组中找第k大数是类似的） |
|
|
f****4
发帖数: 1359 | 29 节点里面存the number of nodes of current tree/subtree是
clrs 14.1
BST min & BST Succ
clrs 12.2
clrs(Introduction to algorithms 2nd) |
|
|
x*********s
发帖数: 2604 | 31 void findKthLargestInBST(Node* p, int& counter, int k)
{
if(!p || k < 0)
return;
findKthLargestInBST(p->right,counter,k);
counter++;
if(counter == k)
{
cout<value;
return;
}
findKthLargestInBST(p->left,counter,k);
} |
|
|
g**********y
发帖数: 14569 | 33 A/G都问的一道：Find kth smallest number in union of two sorted arrays
好象网上公认的最佳解是logM+logN。我写完code, 感觉log(min(M,N))就够了，如果错了，请指正。
思路是用的ihasleetcode的：i+j=k, 既然k是固定的，那我只需要找出i, 这个i我当然可以挑一个短的序列找。以下code是找针对数组a的指针i, 要是b是短的，稍改一下程序就行。
public int get(int[] a, int[] b, int k) {
int lower = Math.max(0, k-b.length-1);
int upper = Math.min(a.length-1, k-1);
int i = (lower + upper) / 2;
return get(a, b, k, lower, i, upper);
}
private int get(int[] a, int[] b, int k, int lower, int i, int upper) {
int j = k - i - 2;
... 阅读全帖 |
|
g***s
发帖数: 3811 | 34 no.
scan once, use 20 variables to count each color. (n)
Then use 20 pointers and in-place swap to scan. (n*2) -- similar with the
algo to swap k to kth. but here swap k to k-th block.
space O(20) |
|
f********3
发帖数: 210 | 35 攒下rp哈。
1st
1. Introduction. (education, experience)
2. Your project
3. Do you have any experience of OOP? Tell me something about OOP
4. What is the advantage of polymorphism?
5. Write a function which returns a bool value. The parameters are two
integers. fun(8, 4) returns 1. Because 8 is 1000 in binary. And 4 returns
the fourth element from right to left. Also, fun(8, 3) returns 0.
6. How to find the first k smallest elements in an array?(i.e. find the
1st, 2nd, 3rd, … kth s... 阅读全帖 |
|
m**q
发帖数: 189 | 36 Looks like an old question, but failed to find a better solution than O(klg(
m+n)). Any ideas?
The question is quoted from a comment on ihas1337code website
------
1.Two reverse sorted arrays A and B have been given. such that size of A is
m and size of B is n
You need to find the k th largest sum (a+b) where a is taken from A and b is
taken from B. such that k < m*n It can be done in O(n*n) but i believe it
can be done in a very efficient way. I heard someone say there is a paper
from SODA. I... 阅读全帖 |
|
c*******w
发帖数: 63 | 37 Programming Pearls里面Column2, Problem8有这道题.
用Random_Select找出the kth element. Check数组前K个元素的和
是不是<=X, if yes, return true, otherwise return false.
因为Random_Selection算法之后, 数组的数据分布是: K个数之前的,都小于A[k], K个
数之后的,都大于A[k].
所以, 如果前K个数不<=X, 那么就肯定找不到其他K个数<=X了.
不过复杂度是O(n) |
|
r*******g
发帖数: 1335 | 38 1，Given a n-ary tree. A random leaf node will be selected.Imagine that you
are now holding the tree with your hand from that node. All other nodes will
now fall under gravity. Write a function to perform this transformation.
n-ary tree又不是bst，这题什么意思，怎么也无法想象把一个节点提起来是什么感觉
2，Given two lists, each containing numbers, how would you find the
intersection of these two lists? What if these two lists are read from a
huge file that cannot fit in memory?
如果文件很大该怎么办，我能想到的是尝试一个number对应一位，但是如果memory实在
有限，numbe... 阅读全帖 |
|
S**I
发帖数: 15689 | 39 a brute force solution to the third problem:
1. Let n = 0, m = 1;
2. Find all permutations of i, j and k such that i+j+k = m. Compute product
of 2^i * 3^j * 5^k of each permutation, put all the products in a set S.
3. Suppose the number of permutations found in the previous step is p (it
can be shown that p = (m+1)*(m+2)/2); then m++, n += p.
4. If k > n, go back to step 2; otherwise, the kth number in set S is the
solution. |
|
g**********y
发帖数: 14569 | 40 Find kth p,q,r's composition number (assume p
public long find(int p, int q, int r, int k) {
PriorityQueue pq = new PriorityQueue();
long t = p;
pq.add(t);
for (int i=0; i
t = pq.remove();
add(pq, p*t);
add(pq, q*t);
add(pq, r*t);
}
return t;
}
private void add(PriorityQueue pq, long n) {
if (!pq.contains(n)) pq.add(n);
} |
|
f****4
发帖数: 1359 | 41 原帖：http://www.mitbbs.com/article_t/Programming/31198701.html
Two reverse sorted arrays A and B have been given.such that size of A is m
and size of B is n You need to find the k th largest sum (a+b) where a is
taken from A and b is taken from B. such that k < m*n
有O(n)的解么？怎么转化成杨矩啊？
谢谢 |
|
l*****a
发帖数: 14598 | 42 为什么非往矩阵上靠
跟N有什么关系？
assume求最小的吧
obviously a[0]+b[0] is the least
we can create a minimum heap with the size of k
each time ,pop up the smallest as a[i]+b[j]
then we can insert a[i+1]+B[j],a[i]+b[j+1] into the heap
each time adjust the heap need lgk
we need to do k times.
so time complexity will be O(klgk)
another tricky here,think about it at first |
|
f****4
发帖数: 1359 | 43 k
最坏的情况： n=m，k=n^2，你的方法是O(n^2*lgn)
我问的是有没有O(n)的解法。
有人说能转换成杨矩，有点不明白：对一个满的n*m杨矩，有O(n)的解法找到第k大数么？ |
|
H****s
发帖数: 247 | 44 貌似这题O(n)不大可能， 我也想知道O(n)的解法， 帮顶！ |
|
|
|
f****4
发帖数: 1359 | 47 能够解释一下么？
这个link，在49匹马的赛马题里面已经有人给过了
不过在这怎么用？
谢谢 |
|
f****4
发帖数: 1359 | 48 Median of Medians algorithm
就是这个wiki的例子，当47找到之后，如果我们是要找第80大的数，
是不是要把大于47的数中，再找第32大数（重新按5行分列，重新计算medians，再算
median of medians）。直到找到那个数？
但是49匹马的赛马题能套这个方法，但我不能证明这个办法赛马次数最少。。。 |
|
f****4
发帖数: 1359 | 49 找到一个对的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... 阅读全帖 |
|
g*****i
发帖数: 2162 | 50 只有2个数组的话不需要用heap吧,就每个数组维系1个pointer,当前最大值是a[i]+b[j]
的话,第二大值只会在a[i]+b[j+1]或者a[i+1]b[j]里面产生,只有一个pointer要移动 |
|
