Hill Billy
BAN USER- 1 Answer Hi, I have a general question....
Hi, I have a general question. Does the median of medians algo really work for finding median of an unsorted big array? E.g. take 1 2 5, 3 4 6, 7 8 9: medians are 2, 4, 8. Median of medians is 4 but overall median is 5.
- Hill Billy May 13, 2012
Another example,
we have 45 distinct numbers divided to 9 group with 5 elements.
48 43 38 33 28 23 18 13 8
49 44 39 34 29 24 19 14 9
50 45 40 35 30 25 20 15 10
51 46 41 36 31 26 21 16 53
52 47 42 37 32 27 22 17 54
The first step is sorting every group (in this case they are already sorted)
Second step recursively, find the "true" median of the medians (50 45 40 35 30 25 20 15 10) i.e. the set will be divided into 2 groups:
50 25
45 20
40 15
35 10
30
sorting this 2 groups
30 10
35 15
40 20
45 25
50
the medians is 40 and 15 (in case the numbers are even we took left median) so the returned value is 15 however "true" median of medians (50 45 40 35 30 25 20 15 10) is 30.
Please explain what am I missing? I have read at many places that median of medians algo doesnt work. If it does can you explain above and also give a good reference to read for the algo?| Flag | PURGE
Greedy approach will not work.
Run your code on {3,3',2,2',1,100,1}; (' for discrimination)
It prints 4 (3->3'->2'->100->1)
while the answer should be 3 (3->2'->100->1)
you can cross verify that this should indeed have been the answer if you replace 3' with something < 2' : (3,1,2,2',1,100,1) : prints 3
How is this O(N) ?
If each array value =N
for (int x = 1; x <= array[index]; x++) will run N time for each recursion and hence total run time = O(n*n)
@EOF : Your greedy approach is wrong.
Consider this case:
3,3',2,2',1,100,Destination (' is just to differentiate)
If you take greedy approach , you will take path :
3,3',2',100,Destination = 5 jumps (at 2nd jump : Max of 3',2,2' = 3')
While the answer would be 3,2',100,Destination = 4 jumps
This is going to be a theoretical answer exploring all the posibilities comparing the time and space complexities which you should discuss with the interviewer to make a tradeoff
Naive : pick every elem from list1 and find in list 2. Update max_found along the way O(n*m)
Best : Using O(min(n,m)) space feed smaller list into hash. Check list 2 elems 1 by 1 and find if in hash. time : O(n+m)
In between :
when you say in between only thing that comes to mind is AlogB kind time complexity. Cases :
1) So lets say I sort 1 list. Now I can search the second list item using binary search in sorted list , but wait! since its a list, binary search is not possible (unless you have a skip list). So searching can be list 2 elemenst one buy one {space = O(1), time = O(nlogn)+O(m*n))}
2) Or sort 1 list and make a 'Balanced' BST of it, so that you can binary search on hit.
{space = O(n), 'worst' time = O(nlogn)+O(mlogn)}
3) Sort both the lists in descending order. Use two pointes and traverse linearly both of them increasing the pointer which points to larger number.
{space = O(1), time = O(2*nlogn)+O(n+m))}
So the best approach will be to use hash or 3)
vgeek as varun pointed out, even if you are not assuming that the binary tree is complete, you would still be using O(n) extra space just to compute the lca. lca for a binary tree can be computed using recursion (o(logn) stack space). I would not write the code here, as you might already know this. My question is, how interesting would this problem be if you can just iterate over the tree once.
- Hill Billy September 08, 2013This is exactly what I thought. +1 !
- Hill Billy September 08, 2013Given the map is 6*5 , given any character , you can find out which row/col it resides in, in O(1)
void getrowcol(char ch, int rc[2]) // returns back row and col in r[2].
int prevr=0;prevc=0; //start point
for(i=0;i<strlen(str);i++)
{
getrowcol(str[i],r);
if(r[0]<prevr)
print("r") , (r[0]-prevr) TIMES;
else
print("l") , (prevr-r[0]) TIMES;
if(r[1]<prevc)
print("d") , (r[1]-prevc) TIMES;
else
print("u") , (prevc-r[1]) TIMES;
print("!");
prevr=r[0];
prevc=r[1];
}
Consider line[] array where people have to be placed.
Assumption : all people have distinct height from 0 to N-1. so sort A and hence B array (along with A) in increasing order.
Now A=[0,1,2,3,4...].
So, now we can ignore A[] and only consider B[] ans array where B[i] is = number of people with greater height in front that person of height i.
Now, in line[], 0th person will be at index B[0] since there are exactly B[0] person > than 0th person. For second largest person if B[1] < B[0] 1 ahead of 0th person in line[]. else after 0th person. Eg
if B=[3,2,....] line = [--10-------] - is space to be taken by others. 0th person took 4th free seat. 1st took 3rd free
if B=[3,3,....] line = [---01------] => 0th person took 4th free seat. 1st took 4th free seat, after 0 took its seat. so 1 basically took 5th seat
notice how 1 after 0 in line.
So basically you have a set of free seats and each person comes and takes whatever is left.
So Algo : put 0th person at index B[0] in line[]. remove B[0] index from line[] from free seat list. next for ith person, traverse whatever free spaces are left in line[] from index 0 and place them there.
pseudo code :
for(i=0;i<N;i++)
{
c=0;
for(j=0;j<N;j++)
{
if(line[j]==free)
c++;
if(c==B[i])
break; //after skipping B[i] "free" seats in line, make ith height person settle down.
}
line[j]=B[i]; //settle down
}
Above is O(N*N)
can be reduced to O(N) is we can find out in O(1) which seat index a person will get currently if he has to skip x seats
O(nlogn) : Consider line as a skip linked list. node has value 0 to N-1. for each person , given x seats to skip - find xth node using bin search on skip list. delete that node. update skip list.
O(nlogn) : See line as a balanced BST. nodes have value of index 0 to N-1. each node also has the value 'number of nodes in this tree' in tree rooted at it.
construct N node such balanced BST in O(N) (yes, find out how this can be constructed in O(N) yourself) (or to simplify , make in O(logn))
Sort A hence B in inc order. Take B[i] for ith smallest person. Delete B[i]th "number" (not value) of node from the tree. this nodes value = persons index in line. Also update 'number of nodes in this tree' for all nodes effected by delete - O(logn) per person. total nlogn.
Since we have the liberty of making the data structure , I will go like this
struct {
node *par1;
node *par2;
int magicnumber;
} node;
par1,par2 are obvious. While filling in the data , who is child of whom etc, you leave magicnumber as 0;
No lets say you get n queries for siblings or not.
for(i=0;i<n;i++)
{
input(node1,node2);
findsiblingsornot(node1,node2,i);
}
in findsiblingsornot() i serves as the query number or the magic number. Do a BFS/DFS using node1 as you like and fill magicnumber=querynumber in nodes you meet;
Next try to do BFS/DFS with node2 and if you get any node with magicnumer=i , you are done :)
Space here is just the space required to create DS. (if you still are considering extra space then its O(n). Time is O(N) too.
You dont need to worry about clearing up after your calls to the function.
Next time you call, you call with bigger magic number.
Since we have the liberty of making the data structure , I will go like this
struct {
node *par1;
node *par2;
int magicnumber;
} node;
par1,par2 are obvious. While filling in the data , who is child of whom etc, you leave magicnumber as 0;
No lets say you get n queries for siblings or not.
for(i=0;i<n;i++)
{
input(node1,node2);
findsiblingsornot(node1,node2,i);
}
in findsiblingsornot() i serves as the query number or the magic number. Do a BFS/DFS using node1 as you like and fill magicnumber=querynumber in nodes you meet;
Next try to do BFS/DFS with node2 and if you get any node with magicnumer=i , you are done :)
Space here is just the space required to create DS. (if you still are considering extra space then its O(n). Time is O(N) too.
You dont need to worry about clearing up after your calls to the function.
Next time you call, you call with bigger magic number.
Now the only question that remains, is how would you solve maps with circles created by people like jamie and cersie ;) Just kiding :D it wouldnt be a circle as the graph is directional :D
As far as I understand the question, the question is about how would you identify if the ad being clicked is by a genuine user or a script / virus.
Now for "this" question , I do not understand some of the solutions mentioned here.
1) The check for IP address is incorrect solution as for both the cases user/script the ip address would remain the same
2) People suggesting here to use some kind of captcha, click on this part of the ad, hold left mouse key for x seconds, press various key combinations : guys, the question is about how to "differentiate" between users and script from the click requests that have already come in, and not to "avoid" scripts.
Now I did like this solution : Look at which part of the ad is being clicked continuously by this IP. humans tend to click at different places.
But, to me the questions seems unanswerable as , if the script writer is intelligent enough, he would obviously know that his script should place clicks NOT at constant intervals but at random times and at random places of the ad.
So, this questions highly depends on what the interviews wants to ask you, assume script writer is not much intelligent and differentiate between clicks that have come already.
OR avoid scripts.
1) Use a trie and insert in it all the N length strings like BCABDADAB,CABDADABB etc. Find the left most path in this trie.
O(N*N) , O(N*N)
2) Find out all the rounded strings of length N (the strings used in 1)) that start with the smallest char i.e ABDADABBC,ADABBCABD,ABBCABDAD (all start with A, ans would be one of these) Find lexicographical min in O(N).
3) Or instead of copying into temp strings (3 O(N) strings)) use 3 pointers with start address of 3 A's. Max O(N) space for index pointers.
for(l=0;l<N;l++)
{
for(k=0;k<ptListLen,k++) //len =3
find the min of Str[(ptList[k]+l)%N] (when l=1, you will be comparing B,D,B 1st index in the three strings.
if(multiple equal mins (like B) discard other pointer indices other that min and continue searching till you get only only 1 min.
}
T : O(N*N), S=O(N) : time can be reduced is getting the count of mins can be reduced somehow
Code:
input = a[N];
min=a[0];
min2=-100000;
for(M=1;M<=N-1;M++)
{
if(min2!==-100000) / /this means some i,j pair is already found , lets see if a[M] can be k
{
if(a[M]>min2) //a[i]<a[j]<a[k]
return (min,min2,a[M]);
else if(a[M] > min) //a[i]<a[k]<a[j]
min2=a[M];
else //we have found the smallest element yet. next time we have to first find j/min2 : a[k]<a[i]<a[j]
{
min=a[M];
min2=-10000;
}
}
else
{
if(a[M] > min)
min2 = a[M];
else
min=a[M];
}
}
I hope nobody thinks I suck at coding. Lets not worry about the inequalities either :)
- Hill Billy May 11, 2013Your algorithm sounds interesting , however I think you need to take care of these
1) Why do you have <x,x> as a pair? The question is to have a,b,c,d distinct right? (Its not challenging enough if a,b,c,d are not distinct) (Discuss this with the interviewer may be?)
2) Assuming that a,b,c,d have to be distinct , you need to take care of cases
Bucket1 : <a,b>
Bucket2 : <b,c>
Bucket 1 + Bucket 2 = 4 such that your set becomes <a,b,b,c> which should be excluded from answer.
So how about this.
1) Generate all sort of <a,b> pairs on a sum array. O(N*N)
2) Sort it. O(N* N*log(N*N)) = N*N*log(N)
3) take pointer a from left, b from right and close in on the solution like you would for (given sorted array find a+b= sum) O(N*N) : size of sum array
4) When you get a,b check if a=(a1+a2) and b=(b1+b2) gives you 4 distinct values.
For 4) you can use a hash map or something?
Instead of blabbing around with the code. Why dont you give us the algorithm and let us figure out whether its correct or not?
- Hill Billy April 15, 2013I am not sure why this question would be asked(as you have to traverse the whole dictionary of million words). The better question to ask would be how would you design the dictionary so that you can print the words efficiently.
The answer to that would be :
Have your dictionary stored in key , value pair : key : count[26]array, value list of all strings that match (basically all anagrams will be in this string)
Now given word with count array G[]
There are the following three cases :
1) anagram of Given(G) + An extra alphabet
2) anagram - 1 alpha
3) change one alphabet in G
Now solution for above 3 cases :
1) for i = 0 to 25 : {G[i]++ ; printlist(hash(G)); G[i]--; }
2) Take old G, not from 1) . for i = 0 to 25 : {if(G[i]) {G[i]-- ; printlist(hash(G)); G[i]++; }
3) for i=0 to 25
{
G[]= given;
if(G[i])
{
G[i]--;
for j=0 to 25 -> skip j=i;
{
G[j]++;
printlist(hash(G))
G[j]--;
}
G[i]++;
}
Correction to the buffalo's last comment(j should start from 0).
Overall explanation : Lets have a as given, b as sorted a.
Now for the sake of explanation lets say a has elements 1 to n and a is like:
<garb>,1,2,3,<garb>4,5,<garb>,6<garb>,7,8<garb>
for example 15,13,1,2,3,12,14,4,5,11,6,9,7,8,10
Basically I am trying to identify from min onwards how much of answer can be got by removing <garbs>.
Now removing of the garbage will be in the order : 9 to 15.
so swap(9),swap(10)...swap(15) will give us sorted array
So code :
i=0;
for(j=0;j<n,j++)
{
if(a[j]==b[i])
i++;
}
return len(a)-i;
So after removing garb, a[0] to a[i-1] will be already sorted = total i elements sorted. So return len(a)-i
If j started with 1 will fail for 1,13,15,2,3,12,14,4,5,11,6,9,7,8,10 which has same property.
How about this for the DP recursion:
DP[i,z]=DP[i-1,z-dist(Di,Di-1)]+DP[i+1,z-dist(Di,Di+1)]
i = 0 for start,1 for D1, n for Dn,n+1 for end
Basically when you are at ith stone and you have to walk z distance more, you can either goto i-1th or i+1th having walked dist(i to i-1) or dist(i to i+1)
Use memoization to store arr[i][z] = DP[i,z] etc.
Breaking conditions:
DP[n+1(end),0] = 1
DP[i,z] = 1 if( dist(i,end_or_n+1) == z) meaning from i you go to end via i+1,i+2 ...
DP[i,z] = 0 if( dist(i,end_or_n+1) > z)
DP[i,z] = 0 if i <0 or i> n+1
MAIN call : DP[0,Z]
You forgot the case where you can go into parents siblings as well , path : node->parent->parent's parent->parent's siblings....
- Hill Billy January 17, 2013question if not how you can give the output, its about your process. so no, what you are saying wont be valid. you 'need' to swap adjacent values only you get the desired output
- Hill Billy May 25, 2012You are saying "5. For the ith person, go through all elements Array[0] to Array[i-1]" . How is the order nlogn then? shouldnt it be O(n*n) ?
- Hill Billy November 10, 2011* 3)Now we can surely say that( V1_L1_tree )and L2 will be on left of V2
- Hill Billy November 05, 2011Lets say the two trees are
V1 V2
/ \ / \
L1 R1 L2 R2
where V1,V2 are the values of roots and L1,L2,R1,R2 are the left and right sub trees.
1)Check which of V1,V2 is bigger and make that the root of our final answer(lets say V2>V1)
2)Then we make it root of the final merged tree.
3)Now we can surely say that( V1 )and L2 will be on left of V2
( / )
( L1 )
4)therefore let X=Merge(V1_L1_tree , L2)
5)Now nodes in R1, can lie either to the left or right of V2
6)therefore let Y=Merge(V2_R2_tree , R1)
7)After this, we can safely merge the left subtree of Y with X and make the head of this result as the left child of root of Y.
8)Not we need to specifically see the fact that we said 3) with respect to V2 but when we were making Y, it might have happened that V2 was replaced from the head of Y(and may be 3) would not hold then) but that will happen only in case R1->value > V2->value (as the bigger value is made root as in 1) ) and still 3) will hold
The solution is from 1-7. 8 is just proof
Please mention if anybody finds any mistake.
I like the way you have visioned the states. But there are a few more things to consider :
- Hill Billy January 03, 20151) Use case : Alarms can be set to recur daily/weekly/ or on specific days of each week. So the AlarmSetState need not be a called manually always. Your clock class can take care of it. As soon as a AlarmEndState is captured from the user, the recurring states can be checked to automatically call the AlarmSetState with the next recurring instance. (you can argue here that an alarm can be snoozed till the next recurring instance is crossed (in which case alarm end state will not be caught and recurring instance alarm will not be set). Either you can add all the recurring instance till 1 year as separate alarms, or in the beginning of each day (assuming lowest recurring interval is 1 day) add the recurring instances from each alarm for that day.
2) The future java task needs to be owned and handled by the clock class as it will sort all the java tasks set by multiple alarms and know which one to execute first. maybe you can use a heap here to know which one needs to go first. Or use a simpler DS is number of alarms you think will be less.
3) You failed to mention that AlarmBuzzState will NOT be a manual action and will be taken by the java task.(or the clock). So the clock picks up the top of heap and when the time comes triggers AlarmBuzzState.