l*****a
发帖数: 559 | 1 I tried. Your code is not working.
#include
#include
#include
#include
#include
#include
using namespace std;
double GetMedian (int* a, int n, int* b, int m, int k)
{
assert(a && b);
if (n <= 0) return b[k-1];
if (m <= 0) return a[k-1];
if (k <= 1) return min(a[0], b[0]);
if (b[m/2] >= a[n/2])
{
if ((n/2 + 1 + m/2) >= k)
return GetMedian(a, n, b, m/2, k);
else
return GetMe... 阅读全帖 |
|
w****x
发帖数: 2483 | 2 半年前觉得挺不好写, 现在写也挺快的
int GetMedian(int a[], int n, int b[], int m, int k)
{
assert(a && b);
if (n <= 0) return b[k-1];
if (m <= 0) return a[k-1];
if (k <= 1) return min(a[0], b[0]);
if (b[m/2] >= a[n/2])
{
if ((n/2 + 1 + m/2) >= k)
return GetMedian(a, n, b, m/2, k);
else
return GetMedian(a + n/2 + 1, n - (n/2 + 1), b, m, k - (n/2 + 1)
);
}
else
{
if ((m/2 + 1 + n/2) >= k)
return GetMedian(b, m, a, n/2, ... 阅读全帖 |
|
w****x
发帖数: 2483 | 3 我觉得我的这个解法是不是要干净些, 还是每次去1/4 part:
int GetMedian(int a[], int n, int b[], int m, int k)
{
assert(a && b);
if (n <= 0) return b[k-1];
if (m <= 0) return a[k-1];
if (k <= 1) return min(a[0], b[0]);
if (b[m/2] >= a[n/2])
{
if ((n/2 + 1 + m/2) >= k)
return GetMedian(a, n, b, m/2, k);
else
return GetMedian(a + n/2 + 1, n - (n/2 + 1), b, m, k - (n/2 + 1)
);
}
else
{
if ((m/2 + 1 + n/2) >= k)
return GetMedian(... 阅读全帖 |
|
w****x
发帖数: 2483 | 4 这是OnSite的题吧。
1. 有Merge的解法是O(m+n), 可以用二分解法，取median每次淘汰1/4.这题写起code来
edgecase超多
int GetMedian(int a[], int n, int b[], int m, int k)
{
assert(a && b);
if (n <= 0) return b[k-1];
if (m <= 0) return a[k-1];
if (k <= 1) return min(a[0], b[0]);
if (b[m/2] >= a[n/2])
{
if ((n/2 + 1 + m/2) >= k)
return GetMedian(a, n, b, m/2, k);
else
return GetMedian(a + n/2 + 1, n - (n/2 + 1), b, m, k - (n/2 + 1)
);
}
else
{
if ((m/2 +... 阅读全帖 |
|
g*******y
发帖数: 1930 | 5 at first glance, use balanced BST like red-black tree can achieve
logN insert, and O(1) getmedian().
To achieve getmedian() in O(1), additional information might be added into tree node, like prev, next pointers
|
|
k***t
发帖数: 276 | 6 #3 GetMedian() 感觉写得有点复杂，insert()应该还可以简化。
==============
#include
#include
#include
#include
using namespace std;
class Median {
public:
Median() : maxhc(0), minhc(0) {}
~Median() {}
void insert (int v) {
if (maxhc==minhc) {
if (maxh.empty() || maxh.top()>=v)
_enQ(true, v);
else _enQ(false, v);
} else if (maxhc>minhc) {
if (maxh.top()>v) {
_enQ(false, _deQ(true));
_enQ(true, v);
} e... 阅读全帖 |
|
w***y
发帖数: 6251 | 7 我就是自己做了一个main部分测试了一下, 其他部分都是copy书上的
import java.util.Comparator;
import java.util.PriorityQueue;
public class heap {
/*
* careercup里答案部分
*/
private Comparator maxHeapComparator, minHeapComparator;
private static PriorityQueue maxHeap;
private static PriorityQueue minHeap;
public static void addNewNumber(int randomNumber) {
if (maxHeap.size() == minHeap.size()) {
if ((minHeap.peek() != null) && randomNumber > minHeap.peek()) {... 阅读全帖 |
|
M******7
发帖数: 30 | 8 public Node getMedian(Node head){
if(head==null)return head;
Node p1=head;
Node p2=head;
while(p2.next!=null&&p2.next.next!=null){
p1=p1.next;
p2=p2.next.next;
}
return p1;
}
public Node Merge(Node n1, Node n2){
Node cur=new Node(-1);
Node head=cur;
while(n1!=null&&n2!=null){
if(n1.value<=n2.value){
cur.next=n1;
n1=n1.next;
}else{
... 阅读全帖 |
|
b*********n
发帖数: 1258 | 9 You have a data structure of integers, which can be negative, zero, or
positive, and you need to support an API with two public methods, insert(int
) and getmedian(). Describe a data structure you would use to support this
API and describe the running time of the two methods. |
|
H*M
发帖数: 1268 | 10 a data structure augmented from red-black tree
also store the value in each node of the total number of elements of the
subtree (including that node itself)
insertion/deletion will be o(lgn)
getmedian will be o(lgn)
int |
|
H*M
发帖数: 1268 | 11 how can u getmedian by o(1)??
tree node, like prev, next pointers\ |
|
k*k
发帖数: 49 | 12 i was asked this question
i proposed solution mentioned in this post except max+min heap.
seems max+min heap is the best solution....
sigh... wish i saw this post earlier....
in the end, they asked for the board-coding of a simpler getMedian() for a
collection in which the value of elements are constrained such as (1..100) |
|
b*********n
发帖数: 1258 | 13 what's the algorithm for your white-board getMedian() function?
Anything special?
heap or selection algo?
Thank you |
|
n**x
发帖数: 30 | 14 写得有点恶心，细节没有优化。后半部分感觉可以优化掉，但不知道怎么证明。
#include
#include
inline int IsOdd(int x){
return (x&1)==1;
}
inline int IsEven(int x){
return (x&1)==0;
}
int getmedian(int *s1,int *e1,int *s2,int *e2){
int N1=(e1-s1),N2=(e2-s2);
int N=N1+N2;
int NHalf=(N1+N2)>>1;
float m1,m2;
int remainHead=0,remainTail=0;
while(remainHead
N1=(e1-s1);
N2=(e2-s2);
if(IsOdd(N1)) m1=s1[N1>>1];
else m1=(s1[(N1>>1)-1]+ |
|
K*****k
发帖数: 430 | 15 要求in place, 只要求O(m + n)的方法，不需要log(m + n)那个。我写的代码还是觉得太长，怎么简化才能在白板上写的下？
double GetMedian(int A[], int m, int B[], int n)
{
bool odd_length = ((m + n) % 2 == 0)? false : true;
int m1, m2;
int pos = (m + n + 1) / 2;
int count = 0;
int i = 0;
int j = 0;
while (i < m && j < n)
{
count++;
if (A[i] <= B[j])
{
if (count == pos)
{
m1 = A[i];
if (odd_length)
return m1;... 阅读全帖 |
|
s*******f
发帖数: 1114 | 16 面试了很多，有一个offer，不过没赶上H1B。我懒，一直没总结，多数问题板上都有。
慢慢更新帖子列出来，不列公司名。
1. 正则表达式匹配字符串，包含 *， ?
2. give u a function IsBad(item) and an array: good, good, .., bad, bad, ...
always bad, find out first bad
3. design a data structure, support 2 functions: Insert and GetMedian.
4. give a matrix, sorted as follow, M[i][col - 1] < M[i + 1][0]
1 3 4
5 6 8
10 14 16
write function: bool Find(int k)
5. linkedin经典format文本题，我居然没复习到，真得给h1b进度逼死了
6. write function: search(keywords). you have invert table, return top10
b... 阅读全帖 |
|
g**e
发帖数: 6127 | 17 今天直接被bar raiser批了，谁告诉你我们一定要optimal solution? 背包问题只要能
给brute force就可以了，getMedian只要O(n)就可以了。 |
|
g**e
发帖数: 6127 | 18 希望对找工作的同胞有用。不过我以后的面试题可是会换了，哈。
【 以下文字转载自 Topcoders 俱乐部 】
发信人: gate (态度+做题), 信区: Topcoders
标 题: Re: G Interview Workshop
发信站: BBS 未名空间站 (Sat Sep 29 21:13:43 2012, 美东)
先说amzn的录取比例。我看了一下过去一年的，SDE 1，2，3从简历到最后接受offer的
比例是3-4%。 onsite -> offer比例30%， 最后有大概60%的人接受。SDE1接受offer的
比例明显高。SDE3接受比例最低，估计牛人都去google了。
再说面试，就我们大组(>200人)来看，面试的题目实在是简单。电面一般是2 sum，
find 2 min number in array这种口水题。我偷的zhangbz的数组去重的题电面了十几
个人只有两个人写对。onsite最难的也就是背包，最长回文，getMedian这种，设计就
是restaurant simulation。我这个礼拜问的is_bst没有一个人答对。版上大牛们应该
分分... 阅读全帖 |
|
d**e
发帖数: 6098 | 19 ☆─────────────────────────────────────☆
gate (态度+做题) 于 (Sun Sep 30 23:00:35 2012, 美东) 提到:
希望对找工作的同胞有用。不过我以后的面试题可是会换了，哈。
【 以下文字转载自 Topcoders 俱乐部 】
发信人: gate (态度+做题), 信区: Topcoders
标 题: Re: G Interview Workshop
发信站: BBS 未名空间站 (Sat Sep 29 21:13:43 2012, 美东)
先说amzn的录取比例。我看了一下过去一年的，SDE 1，2，3从简历到最后接受offer的
比例是3-4%。 onsite -> offer比例30%， 最后有大概60%的人接受。SDE1接受offer的
比例明显高。SDE3接受比例最低，估计牛人都去google了。
再说面试，就我们大组(>200人)来看，面试的题目实在是简单。电面一般是2 sum，
find 2 min number in array这种口水题。我偷的zhangbz的数组去重的题电面了十几
个人只有两... 阅读全帖 |
|
S********e
发帖数: 28 | 20 攢人品及回報本版的幫助。
=== PS 1 ===
1. Similar to 'Combination Sum I/II' on Leetcode.
=== PS 2 ===
1. Similar to 'Design/Implement LRU Cache'. Key requirements: efficient look
-up while maintaining insertion order.
2. Figure out potential concurrent issues for a code segment. Key
observations: use 'wait/notify' instead of 'sleep' for coordination between
threads.
=== Onsite ===
1. Given a 2D array of integers, determine if it is possible to go from one
cell to another cell following non-descreasing path.
... 阅读全帖 |
|
