Author |
Topic: Google Interview Question (Read 4079 times) |
|
sulfur
Newbie
Posts: 18
|
|
Google Interview Question
« on: Mar 10th, 2010, 4:31am » |
Quote Modify
|
Given a set of integers S, rearrange them so that the same number does not occur in a window of n numbers. when n= 2 and S = [1,1,1,2,2,3] one possible solution is [1,2,1,2,1,3] The interviewer was more interested in looking a correct solution than time complexity.
|
|
IP Logged |
|
|
|
mmgc
Newbie
Gender:
Posts: 47
|
|
Re: Google Interview Question
« Reply #1 on: Mar 10th, 2010, 5:45am » |
Quote Modify
|
Start traversing S For each element - check the availability in existing lists(i.e whether all elements of window exist) - whereever it does not exist, put it - if it exist every where - initiate another list with the current element as first -- if element is outside window attach it in first list itself In the end join the lists
|
|
IP Logged |
|
|
|
mmgc
Newbie
Gender:
Posts: 47
|
|
Re: Google Interview Question
« Reply #2 on: Mar 10th, 2010, 6:35am » |
Quote Modify
|
Alternative & better way: Sort S. Now, we can easily find the number of groups to be formed with window n.Initiate that many lists. Now traverse sorted S and keep adding same elements ( with in window ) to different lists.Elements out of window can be added to first list. In the end join the lists ( end to end )
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Google Interview Question
« Reply #3 on: Mar 10th, 2010, 7:20am » |
Quote Modify
|
For window size 2: Calculate how many times each value appears (and the total size n of S). If a value appears more than n/2+1 times, the problem has no solution. Otherwise you can sort the values and split the list into two rows in the "almost middle". Then traverse the "rectangle vertically". (1,1,2,2,2,2,3) would be split to Code: In each vertical pair there must be different numbers. Problem is that in resulting list you could obtain the majority values nearby (1,2,1,2,2,3,2). So the method should be improved ... you have to sort the elements by their count's (descending). Code: leading to (2,1,2,1,2,3,2). Actually partial sort would be sufficient and you could work with "packed lists" using sublist lengths. This method could be easily adopted for bigger windows.
|
« Last Edit: Mar 10th, 2010, 7:20am by Hippo » |
IP Logged |
|
|
|
blackJack
Junior Member
2b \/ ~2b
Gender:
Posts: 55
|
|
Re: Google Interview Question
« Reply #4 on: Mar 10th, 2010, 9:15am » |
Quote Modify
|
How about this solution. 1. Sort the elements on the basis of their frequencies, with the highest frequency one first. 2. Keep a empty window of given length. 3. Untill window gets filled up, Now pick unique elements from the array (decrement their freq by 1) starting from the highest frequency one untill window gets filled up. 4. Print and Empty the window and repeat 1. 6. If all elements finish, done else no solution. For example:consider 1,1,1,1,2,2,2,3,4,4,4,4 :window=2 Sort with frequency : 1,1,1,1,4,4,4,4,2,2,2,3 ....Window........array 1> 1,4 1,1,1,4,4,4,2,2,2,3 2> 1,4 1,1,4,4,2,2,2,3 -> 2,2,2,1,1,4,4,3 3> 2,1 2,2,1,4,4,3 -> 2,2,4,4,1,3 4> 2,4 2,4,1,3 5> 2,4 1,3 6> 1,3 It is something like given degrees and to tell wether a graph is possible or not and solvable using Havel hakimi theorom.
|
|
IP Logged |
|
|
|
newCoder
Newbie
Gender:
Posts: 3
|
|
Re: Google Interview Question
« Reply #5 on: Mar 10th, 2010, 10:21am » |
Quote Modify
|
We can further simplify the sort by storing the number in a map<number,frequency> and sort this based on frequency. Use initial array to store the O/P. Iterate over array to populateMap. SortMap based on frequency(High to low) Take first N elements from Map (decrement frequency by 1) and store these number in array.
|
|
IP Logged |
|
|
|
sulfur
Newbie
Posts: 18
|
|
Re: Google Interview Question
« Reply #6 on: Mar 11th, 2010, 1:27am » |
Quote Modify
|
Aaah !!! I was able to do the question without sorting and in linear time complexity.
|
|
IP Logged |
|
|
|
blackJack
Junior Member
2b \/ ~2b
Gender:
Posts: 55
|
|
Re: Google Interview Question
« Reply #7 on: Mar 11th, 2010, 1:36am » |
Quote Modify
|
@ sulfur can you share with us how is it possible without sorting?
|
|
IP Logged |
|
|
|
peninha
Newbie
Posts: 7
|
|
Re: Google Interview Question
« Reply #8 on: Mar 11th, 2010, 3:22am » |
Quote Modify
|
on Mar 10th, 2010, 7:20am, Hippo wrote:For window size 2: Calculate how many times each value appears (and the total size n of S). If a value appears more than n/2+1 times, the problem has no solution. |
| Even if no element appears more than n/w+1 (where w is the window size), there is no guarantee that there will be a solution. Take for instance a window of size 3, and the following array: [1,1,1,2,2,2,3]. No element appears more than 3 times, and yet no solution is possible.
|
|
IP Logged |
|
|
|
mmgc
Newbie
Gender:
Posts: 47
|
|
Re: Google Interview Question
« Reply #9 on: Mar 11th, 2010, 5:53am » |
Quote Modify
|
on Mar 11th, 2010, 1:27am, sulfur wrote:Aaah !!! I was able to do the question without sorting and in linear time complexity. |
| 1. Traverse S For each duplicate element in window swap it with next element 2. Reverse Traverse S For each duplicate element in window swap it with previous element Do 1, 2 till whole array is rearranged as asked 1,1,1,2,2,3 1,1,2,1,2,3 1,2,1,2,1,3 I think the time complexity is O ( n * K ) where k depends on the maximum number same window elements in S
|
|
IP Logged |
|
|
|
blackJack
Junior Member
2b \/ ~2b
Gender:
Posts: 55
|
|
Re: Google Interview Question
« Reply #10 on: Mar 11th, 2010, 7:24am » |
Quote Modify
|
on Mar 11th, 2010, 5:53am, mmgc wrote: 1. Traverse S For each duplicate element in window swap it with next element 2. Reverse Traverse S 1,1,1,2,2,3 1,1,2,1,2,3 1,2,1,2,1,3 |
| what do you mean by reverse traverse S, you mean traverse it from last ? why is reverse traverse needed? Can you please elaborate the example you mentioned. how 1,1,2,1,2,3 arrived from 1,1,1,2,2,3 ? Acc. to step 1, 2nd '1' mentioned in array should be swapped with '2' ??
|
|
IP Logged |
|
|
|
mmgc
Newbie
Gender:
Posts: 47
|
|
Re: Google Interview Question
« Reply #11 on: Mar 11th, 2010, 6:31pm » |
Quote Modify
|
on Mar 11th, 2010, 7:24am, blackJack wrote: what do you mean by reverse traverse S, you mean traverse it from last ? why is reverse traverse needed? Can you please elaborate the example you mentioned. how 1,1,2,1,2,3 arrived from 1,1,1,2,2,3 ? Acc. to step 1, 2nd '1' mentioned in array should be swapped with '2' ?? |
| Yes, reverse traverse means traversing it from last...For some inputs(where same window elements are in the end of S),we may end up doing Step 1 infinitely..So, Step 2 is required Step 1 i = 0 1, 1, 1, 2, 2, 3 i = 1 1, 1, 1, 2, 2, 3 i = 2 1, 1, 2, 1, 2, 3 --- we swap with the last element in the same element sequence i = 3 & i = 4... 1, 1, 2, 1, 2, 3 Step 2 will not make any change in S When Step 1 is executed again : i = 0 -- 1, 1, 2, 1, 2, 3 i = 1 -- 1, 2, 1, 1, 2, 3 i = 2 -- 1, 2, 1, 1, 2, 3 i = 3 -- 1, 2, 1, 2, 1, 3 I am still figuring out the proof --that this will work for every case
|
|
IP Logged |
|
|
|
singhar
Newbie
Posts: 22
|
|
Re: Google Interview Question
« Reply #12 on: Mar 20th, 2010, 2:33am » |
Quote Modify
|
Two observations: 1. If the window size is larger than the number of unique elements then it is not possible to do the re-arranging. Because there will be definitely one repetition no matter what. 2. If window size is equal to the number of unique elements, then re-arrangement is possible only if we have equal number of each element. 3. If window size if less than the number of unique elements then let k = m / n where m is the total number of elements and n is window size. So k here is the numbers of windows that we have to have. So the maximum frequency that can allow us a valid re-arrangement is k. So if we have an element with frequency greater than k then we can't re-arrange.. Can someone verify if these observations are correct. I believe we must take these into account to build correct solution.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Google Interview Question
« Reply #13 on: Mar 20th, 2010, 11:35am » |
Quote Modify
|
on Mar 20th, 2010, 2:33am, singhar wrote:Can someone verify if these observations are correct. |
| Yes they are, and 1) and 2) follow from 3). But if you have a procedure that gives a solution given that a solution is possible, you can always check in the end that it satisfies the constraints.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
jack_alyz
Newbie
Posts: 8
|
|
Re: Google Interview Question
« Reply #14 on: Aug 31st, 2010, 9:46am » |
Quote Modify
|
Sol: WindowSize: N Set: S SizeOfSet: M LargestElementIn S : R To store latest index for each distinct element, let's take array L[R]. i=0; while( i < M ) { if(i - L[S[i]] < N ) { swap(i, M); } else { L[S[i]] = i; i++; } } swap(i, T) { while( S[i] == S[T] ) { T = (T+1) % sizeof(S); } S[i] <=> S[T] } After completion of the loop, if there exists two elements at distance < N, than solution is not possible.
|
« Last Edit: Aug 31st, 2010, 10:07am by jack_alyz » |
IP Logged |
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Google Interview Question
« Reply #15 on: Dec 17th, 2010, 10:12pm » |
Quote Modify
|
Assuming k is the size of the set and n is the window size, do the following. 1) Sort elements according to decreasing frequency. 2) Divide elements into groups make (k%n) groups of size (k/n+1), the rest of elements in groups of size k/n. 3) A total of n groups will be formed. 4) 1st element of each group will form 1st window, 2 element will form 2nd group...like that, form as many groups as possible.
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Google Interview Question
« Reply #16 on: Dec 18th, 2010, 1:40am » |
Quote Modify
|
on Mar 11th, 2010, 3:22am, peninha wrote: Even if no element appears more than n/w+1 (where w is the window size), there is no guarantee that there will be a solution. Take for instance a window of size 3, and the following array: [1,1,1,2,2,2,3]. No element appears more than 3 times, and yet no solution is possible. |
| yes, you are right the condition cannot be so easily extended for higher window sizes. But the method write fill the "rectangle" and read by columns does what required. 1,1,1 2,2 2,3 ... failed as the first three windows contain value 2 twice. having 1,1,1,2,2,2,3,3 would lead to 1,1,1 2,2,2 3,3 with correct solution. Actually the sorting by count is not required, just make sure the elements with highest count went first. ... that required just O(n). 1,1,1,1,1 2,2,2,2,2 3,3,4,4,4 4,5,5,5,5 6,7,7,7
|
« Last Edit: Dec 18th, 2010, 1:45am by Hippo » |
IP Logged |
|
|
|
|