ashu
BAN USER- 0of 0 votes
AnswersYou are given an unsorted array with both positive and negative elements. You have to find the smallest positive number missing from the array in O(n) time using constant extra space.
- ashu in India
Eg:
Input = {2, 3, 7, 6, 8, -1, -10, 15}
Output = 1
Input = { 2, 3, -7, 6, 8, 1, -10, 15 }
Output = 4| Report Duplicate | Flag | PURGE
InMobi Algorithm - 0of 0 votes
AnswersYou are given n variable length sets with each set like set1: [s1.....e1], set2:[s2.....e2] with the condition that the sets overlap (i.e. if you represent them on number line, they intersect). Now you have to remove the minimum number of sets from here so that the remaining sets are disjoint.
- ashu in India
For example you have set S1, S2, S3 with S1 and S3 disjoint and S2 overlapping both S1 and S3 then we remove S2 to get the answer.| Report Duplicate | Flag | PURGE
InMobi Algorithm
given: xy = a + b*lcm + c*gcd
elementry maths: xy = lcm*gcd, on substitution, we get: lcm*gcd = a + b*lcm + c*gcd
on rearranging, we get (gcd - b)(lcm - c) = a + bc.
This is a program of finding all pairs of numbers p,q such that pq = k.
=> lcm - c = x1, gcd - b = x2
=> lcm = x1 + c, gcd = x2 + b
Now xy = lcm*gcd => x*y = (x1+c)(x2+b) Which is again a case of pq = k. Call the same function again and count the number of values found, which is our output.
Take a look at this problem this way:
For instance take a look at 3rd case: ababab [4, 2]
The possible outcomes are 111100, 111001.......(just replace 1 at ith position with char[i]), we get abab, abaa.......
If you see all we need to do is find all the anagrams of 111100 (and the word here has repeated characters).
An example solving of such anagram can be [consider aabc] and we already have anagrams of abc (i.e. abc, acb, bac, cab, bca, cba) and we need to now merge a into these 6 guys (to get anagrams of aabc)
This can be done as: _a_bc, _a_cb, _b_ac, _ba_c...........
When doing this, if we check if last character of 1st substring or first character of last substring is same as character to be merged then we get a duplicate case. For all other cases, merge the character as normal.
The same principle can be applied to the problem above
Instead of using the hash table, you can shift the wrong values towards the end of the array and decrease end.
eg: int[] a = {12, 2, 1, -5, 6, 18}
Keep a pointer at the start and another at the end of the array.
a[0] = 12 and 12 > a.length() so swap 12 with a[end] and do end--
so my a[] becomes {18, 2, 1, -5, 6}
similarly, 18 is also out of bounds so I repeat and a[] = {6, 2, 1, -5} and then {-5, 2, 1} and then {2, 1}
Now, in this step we see a[start] <= end so what I do is swap a[start] with a[a[start]]
Thus, a[] = {1, 2}
lastly, I have to loop only till whenever a[start] = a[a[start]], in this case till 3 (which is our answer).
Repmarthavmoody, Consultant at Dell
Spent 2002-2010 investing in toy elephants in Pensacola, FL. Earned praised for my work testing the market for squirt guns ...
- ashu February 19, 2012