Consider an array 'A' of 1st n natural numbers randomly permuted. Consider an array B formed from array A as given below
B(k) = number of elements from A(1) to A(k-1) which are smaller than A(k)
Obviously B(1) = 0;
i) Given A can you find B in O(n)
ii) Given B can you find A in O(n)
Disclaimer: The question was asked to me during GSachs interview and of course I was unable to answer. I am still unable to figure out the solution
B(k) = number of elements from A(1) to A(k-1) which are smaller than A(k)
Obviously B(1) = 0;
i) Given A can you find B in O(n)
ii) Given B can you find A in O(n)
Disclaimer: The question was asked to me during GSachs interview and of course I was unable to answer. I am still unable to figure out the solution
I have figured out a method of how we will get back the original matrix A from B given, but I have a doubt that it's not O(n)....
ReplyDeletelet A = [3 1 5 2 6 7 4]
and B = [0 0 2 1 4 5 3]
(i) make a new matrix C by comparing elements of B from right onwards i.e. compare B(k) with B(n), k ranging from n to 1, and put C(k)=1 if B(k)<=B(n) and we don't reach the 1st '0' (keep a signal red/green),ow C(k)=0,
so C = [0 1 0 1 0 0 1]
(ii) make another matrix D by counting, from left onwards, how many 1's are there in the left of any element'0' of C i.e. keep track of a signal t=0 starting and make D(k)=t and then t=t+1 once C(k)=1,
so D = [0 * 1 * 2 2 *], * are insignificant nos...
(iii) 1st step to reconstruct the original matrix R is put R(k)=B(k)+C(k) whenever C(k)=1, ow if C(k)=0 then R(k)=0,
so R = [0 1 0 2 0 0 4]
(iv) make a list 1-2-3-4-5-6-7 and eliminate the nonzero elements of R, i.e. eliminate 1,2,4; so the new list is 3-5-6-7
(v) take the significant elements of D (neglect the stars, so specially mark them) from rightwards(n to 1) and take the 1st significant one from right D(6) and subtract it from B(6) (or you can make a new matrix E from B - D),
then E = [0 * 1 * 2 3 *],
E(6)= 3, so retain the 1st 3 elements of the list and remove the next i.e. 7 and put it in R(6), the new list is 3-5-7 and R = [0 1 0 2 0 7 4]
then take E(5)=2 and retain 1st 2 elements of the new list and remove next i.e. 6 and put it in R(5), so new list is 3-5 and R = [0 1 0 2 6 7 4]
thus continuing this we get R = [0 1 5 2 6 7 4] and then R = [3 1 5 2 6 7 4] = A
the problem is although (i) & (ii) are of O(n), but i doubt the removing operation from list(in (iii) & )iv)) is not of O(n).... so please check it...
i think from A to B can not be done in O(n).......
sorry, there i a mistake in (i)... corrected version is : put C(k)=1 if B(k)form a decreasing seq starting from B(n)(not necessarily consecutive seq)i.e. B(k)<B(k'), (where k' is the previous k' th element which forms the decreasing seq) and we don't reach the 1st '0' i.e. end of the seq (keep a signal red/green),ow C(k)=0
ReplyDeleteanother example that will clarify the method...
ReplyDeleteA = [3 2 5 1 7 6 4]
B = [0 0 2 0 4 4 3]
C = [0 0 0 1 0 0 1]
D = [0 0 0 * 1 1 *]
E = [0 0 2 * 3 3 *]
R = [0 0 0 1 0 0 4]
L1: 1-2-3-4-5-6-7
L2: 2-3-5-6-7
L3: 2-3-5-7 R = [0 0 0 1 0 6 4]
L4: 2-3-5 R = [0 0 0 1 7 6 4]
L5: 2-3 R = [0 0 5 1 7 6 4]
L6: 3 R = [0 2 5 1 7 6 4]
final R = [3 2 5 1 7 6 4] = A
The motivation behind finding out the above algo is as follow:
ReplyDeleteI first noticed that the last element A(n) is always B(n)+1 .... then I saw it happens for all B(k)'s that form a decreasing sequence starting from B(n) and for those k's, A(k) = B(k)+1 ... as e.g. if A = [1 2 4 3 5] and B = [0 1 2 2 4], then B(5)-B(4)-B(2)[4-2-1] forms the decreasing seq. and B(3)=2 is not a part of the seq as B(3)=2=B(4) and we already encountered B(4)and 2 already became a part of the seq. , so it's necessary that B(k)<B(k'), where k' is in the seq.....
Then I find out that the no which we got from adding 1 with elements from dec. seq. has no role in finding the other no.s, so i removed them from the list of no's from 1-2-3-...-n .... the gaps will be filled by the remaining no.s
Next I realized that the no.s in those gaps are effected by the no. of elemnts of the dec. seq. sittinf left to them... so I counted the matrix D and then I realized that if I deduce D from B, then the new matrix E will give a hints to calulate the gaps from the remaining list... but we have to reduce the list every time...
just see the algo now.. it will be much clear now...
btw, as we know exactly what element(node) has to be deleted at every stage from the linked list and elimination from a fixed list takes O(1) time, for at most n elements, at the worst, it will take O(n) time... so at all the algo is of ordeer O(n)....