Author |
Topic: The hardest interview question I met so far (Read 37668 times) |
|
sumitmal
Newbie
Posts: 2
|
 |
Re: The hardest interview question I met so far
« Reply #50 on: Mar 18th, 2008, 9:23am » |
 Quote  Modify
|
i think i got this one .... the way it can be done is
take two pointers starting from A[0] and B[0]. now compare A[0] + B[1] & A[1] + B[0]. For the greater one run the iterator as follows.
assume A[1] + B[0] exceeds the other . check A[i] + B[j] where j increments till, it is more than B[1] and A[0]. once it happens store j for next iteration...and change j = 0 and i = 1 and iterate i, till it is more than A[0] + B[nextiterator] or no. of pairs reaches n.
for the next iteration, mark j and i as the ones where above loops ended. Number of comparisons will be of O(n)
|
|
 IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender: 
Posts: 919
|
|
Re: The hardest interview question I met so far
« Reply #51 on: Mar 19th, 2008, 2:10am » |
Quote Modify
|
It's always pleasure to read James Fingas posts.
I have read the thread just now ... of course You cannot give the n numbers sorted. It should cost n log n.
So the pivot approach is required if trying to make O(n) solution.
The sqrt compression method is very nice trick!
I should think about choosing correct pivot from medians of diferent sized samples but the solution looks well.
I would start by choosing pivots on the diagonal by binary search until two neighbouring pivots are found such that n-th pair is among their values.
Now we are trying to find n-th pair from all, which is  -th after the last smaller pivot choosen, we ignore all pairs out of the interval between last smaller and last larger pivot. If the number of remaining pairs N  o(n) we can find the n-th value in the o(n) remaining time by standard k-th from N algorithm. In our case the number of remaining pairs can be  (n n).
[edit]Oops only 2n(1+1/2+1/3+1/4+...1/n)-n=n(1+1/2+1/3+...+1/n) 2n ln n[/edit]
OK, if you resign on finding the pivot in O(n) time and O(n log n) is sufficient (actually this is good choice as the pivot test costs (n log n), you can easily sort all sample medians and traverse them from smallest to highest. After that you can count in O(1) amortized per original sample median how many pairs are garanted to be smaller and how many larger than the sample median. I would choose the sample median such that the number of garanted smaller is less than such that number of garanted larger is as close to number of garanted smaller as possible. Actually if N (n) the choosen pivot would be largest which guarantees less than smaller values. If the choosen pivot would be higher than n-th pair, we speeded up the search highly and the remaining N' would be /2 +O(N/2) and each subinterval longer than is halved. If the choosen pivot would be less than n-th pair, we can choose as the next pivot its higher neighbour in the list which is surely bigger than n-th pair. In that case we shortened the interval using sample medians as much as possible and it became O(N/2) and all the subintervals are halved.
So at least after log N steps the interval of remaining pairs is O(n) long. I should analyse it better ...
[edit]And I did here and here[/edit]
|
| « Last Edit: Jun 13th, 2009, 3:37pm by Hippo » |
IP Logged |
|
|
|
scm007
Newbie
Posts: 11
|
|
Re: The hardest interview question I met so far
« Reply #52 on: Dec 25th, 2008, 2:35pm » |
Quote Modify
|
Isn't this solution as simple as keeping track of wherever we branch in terms of searching for the solution, then reverting back to that branch if it is greater than the current?
I have attached C++ code, no comments if you can't figure it out just ask. I coded this up in about 5 minutes so it is ugly and slow.
#include <vector>
#include <string>
#include <iostream>
using namespace std;
int sum(pair<int, int> p, vector<int> A, vector<int> B) {
return A[p.first] + B[p.second];
}
vector< pair<int, int> > maxPairs(vector<int> A, vector<int> B, int n) {
vector< pair<int, int> > pairs;
pair<int, int> sec, cur, temp;
cur = make_pair(0, 0);
pairs.push_back(cur);
if ( sum(make_pair(cur.first, cur.second + 1), A, B) >
sum (make_pair(cur.first + 1, cur.second), A, B) )
{
cur = make_pair(0, 1);
sec = make_pair(1, 0);
}
else {
cur = make_pair(1,0);
sec = make_pair(0, 1);
}
pairs.push_back(cur);
for (int i = 2; i < n; i++) {
temp = cur;
if ( sum(make_pair(cur.first, cur.second + 1), A, B) >
sum (make_pair(cur.first + 1, cur.second), A, B) )
{
cur.second++;
}
else {
cur.first++;
}
if (sum(sec, A, B) > sum(cur, A, B)) {
temp = cur;
cur = sec;
sec = temp;
}
pairs.push_back(cur);
}
return pairs;
}
int main() {
vector< pair<int, int> > ret;
vector<int> A, B;
for (int i = 0; i < 10; i++) {
A.push_back(5*(i+1));
B.push_back(3*(i+2));
}
sort(A.begin(), A.end());
sort(B.begin(), B.end());
reverse(A.begin(), A.end());
reverse(B.begin(), B.end());
ret = maxPairs(A, B, 10);
for (int i = 0; i < ret.size(); i++) {
cout << '(' << ret[i].first << ',' << ret[i].second << ')' << ' ';
}
cout << endl;
for (int i = 0; i < ret.size(); i++) {
cout << sum(ret[i], A, B) << ' ';
}
cout << endl;
for (int i = 0; i < A.size(); i++) {
cout << A[i] << ' ';
}
cout << endl;
for (int i = 0; i < B.size(); i++) {
cout << B[i] << ' ';
}
cout << endl;
return 0;
}
|
| « Last Edit: Dec 25th, 2008, 2:54pm by scm007 » |
IP Logged |
|
|
|
scm007
Newbie
Posts: 11
|
|
Re: The hardest interview question I met so far
« Reply #53 on: Jan 20th, 2009, 9:13pm » |
Quote Modify
|
Can someone verify that my solution is correct? Logically I think it is, and it passes all of the test cases supplied thus far.
|
|
IP Logged |
|
|
|
computer
Newbie
Posts: 5
|
|
Re: The hardest interview question I met so far
« Reply #54 on: Jan 21st, 2009, 8:29am » |
Quote Modify
|
Can somebody elaborate a bit more about the O(n log n) solution ? What is meant by 4-connected here and which balanced tree is Towr referring to ?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: The hardest interview question I met so far
« Reply #55 on: Jan 21st, 2009, 8:55am » |
Quote Modify
|
on Jan 21st, 2009, 8:29am, computer wrote:| Can somebody elaborate a bit more about the O(n log n) solution ? What is meant by 4-connected here |
|
Look at number pad of you keyboard and consider the 5. Its 4-connected neighbours are 2,4,6 and 8. Its 8-connected neighbours are 1,2,3,4,6,7,8 and 9.
Quote:| and which balanced tree is Towr referring to ? |
|
Just any type that happens to exist in your favorite standard template library, like red-black trees.
on Jan 20th, 2009, 9:13pm, scm007 wrote:| Can someone verify that my solution is correct? Logically I think it is, and it passes all of the test cases supplied thus far. |
|
I'm not really proficient at reading code, especially if there's no layout or annotation. Just so you don't get the idea I'm willfully ignoring it or something. I just haven't had the time.
Is it supposed to be O(n), or merely solve the problem? The use of recursion makes me suspect runtime complexity may not be that good.
|
| « Last Edit: Jan 21st, 2009, 8:56am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
scm007
Newbie
Posts: 11
|
|
Re: The hardest interview question I met so far
« Reply #56 on: Jan 21st, 2009, 6:50pm » |
Quote Modify
|
It's O(n) and has no recursion, I think you guys have made this problem way too hard for yourselves. I'm pretty sure it's correct, I tried to explain what I was doing but didn't comment very well, compile it and run it I suppose. I mean it was an interview question, it seemed to me to be pretty easy, but I have been wrong before 
Stephen
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: The hardest interview question I met so far
« Reply #57 on: Jan 22nd, 2009, 5:51am » |
Quote Modify
|
on Jan 21st, 2009, 6:50pm, scm007 wrote:| I think you guys have made this problem way too hard for yourselves. |
|
I always love to see that -- it's even occasionally true. 
In this case, though, I don't think so. Don't get me wrong -- it's a good effort -- but I believe it's flawed: when you make the first choice (before the loop) you remember the other option in sec, but you don't do this for subsequent choices (the corresponding if block within the loop). Because you don't remember all not-taken choices, you lose track of some possible paths. I don't have a failure case off the top of my head, but I'm confident I can come up with one:
Edit -- a failure case:
A = B = {6, 5, 4, 3, 2, 1}
Your program picks: (0,0) (1,0) (0,1) (1,1) (2,0) (3,0) = 12, 11, 11, 10, 10, 9
One correct answer: (0,0) (1,0) (0,1) (1,1) (2,0) (0,2) = 12, 11, 11, 10, 10, 10
Another failure case -- revisiting an element already chosen:
A = B = {6, 5, 3, 2, 1}
Your program picks: (0,0) (1,0) (0,1) (1,1) (1,1) = 12 11 11 10 10
One correct answer: (0,0) (1,0) (0,1) (1,1) (2,0) = 12 11 11 10 9
--SMQ
|
| « Last Edit: Jan 22nd, 2009, 6:55am by SMQ » |
IP Logged |
--SMQ
|
|
|
eklavya
Newbie
Posts: 18
|
|
Re: The hardest interview question I met so far
« Reply #58 on: Jun 11th, 2009, 3:14am » |
Quote Modify
|
on Nov 17th, 2005, 3:14am, towr wrote:I can see how to get an O(n log n) algorithm, but a step to O(n) still refuses to show itself.
O(n log n):
| hidden: | The largest value will be (A[0],B[0]).
Given the M largest values, the M+1st largest value will be a (4-connected) neighbour of one of the larger values. So use a balanced binary tree initialized with just (A[0], B[0]), then repeatedly extract the pair with the largest value, and insert the two neighbours (except when duplicate).
There will always be at most two new neighbours, so the size of the BBT is at most 2n (and in fact generally much less) |
There are probably more efficient ways though. |
|
Correct me if I am wrong,but wont the highest n sums definitely contain a[0] or b[0] as one component.
If so then the problem becomes-
for(m,n from 1 to n)
nexthighest[k]=max(A[0]+B[m],B[0]+A[n])
if(1st was larger m++ else n++).
Whats ur take on this?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: The hardest interview question I met so far
« Reply #59 on: Jun 11th, 2009, 3:44am » |
Quote Modify
|
on Jun 11th, 2009, 3:14am, eklavya wrote:| Correct me if I am wrong,but wont the highest n sums definitely contain a[0] or b[0] as one component. |
|
No, typically you'd have a upper-left triangle in the AxB matrix that contains the highest sums, and only at the edges does it contain A[0] or B[0]
For example, take [10, 9, 5, 4, 3, 2] and [12, 11, 9, 6, 1, 0]
10 9 5 4 3 2
12 22 21 17 .. .. ..
11 21 20 16 ..
9 19 18 14 ..
6 16 15 ..
1 .. ..
0 ..
Here two sums don't contain 10 or 12, and four do. But as the two arrays get larger, so does the upper-left triangle, which means fewer elements are at its top and left edge. (But I don't really want to draw larger matrices)
|
| « Last Edit: Jun 11th, 2009, 3:46am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
singhar
Newbie
Posts: 22
|
|
Re: The hardest interview question I met so far
« Reply #60 on: Apr 6th, 2010, 11:00am » |
Quote Modify
|
Did anyone find the O(n) solution for this question? I dont understand James Fingas and Hippo's solution at all. Could anyone explain in a bit more detail or give some pseudo code.
Towr, the scanning of anti-diagonal elements (in bottom-left to top-right direction) would lead to a O(nlogn) solution, since for the pair with kth largest sum we are checking at most k pairs. Am I right?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: The hardest interview question I met so far
« Reply #61 on: Apr 6th, 2010, 12:25pm » |
Quote Modify
|
on Apr 6th, 2010, 11:00am, singhar wrote:| Towr, the scanning of anti-diagonal elements (in bottom-left to top-right direction) would lead to a O(nlogn) solution, since for the pair with kth largest sum we are checking at most k pairs. Am I right? |
|
It's been about a year since I last thought about this problem, but yeah, something like that should work, I think.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print