wu :: forums
« wu :: forums - Google Interview Question »

Welcome, Guest. Please Login or Register.
Oct 31st, 2024, 4:54pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   cs
(Moderators: Icarus, Grimbal, SMQ, william wu, towr, ThudnBlunder, Eigenray)
   Google Interview Question
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Google Interview Question  (Read 4079 times)
sulfur
Newbie
*





   


Posts: 18
Google Interview Question  
« on: Mar 10th, 2010, 4:31am »
Quote Quote Modify 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: male
Posts: 47
Re: Google Interview Question  
« Reply #1 on: Mar 10th, 2010, 5:45am »
Quote Quote Modify 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: male
Posts: 47
Re: Google Interview Question  
« Reply #2 on: Mar 10th, 2010, 6:35am »
Quote Quote Modify 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: male
Posts: 919
Re: Google Interview Question  
« Reply #3 on: Mar 10th, 2010, 7:20am »
Quote Quote Modify 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:

1,1,2,2
2,2,3

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:

2,2,2,2
1,1,3

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: male
Posts: 55
Re: Google Interview Question  
« Reply #4 on: Mar 10th, 2010, 9:15am »
Quote Quote Modify 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: male
Posts: 3
Re: Google Interview Question  
« Reply #5 on: Mar 10th, 2010, 10:21am »
Quote Quote Modify 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 Quote Modify Modify

Aaah !!!
 
I was able to do the question without sorting and in linear time complexity.  Tongue
IP Logged
blackJack
Junior Member
**




2b \/ ~2b

   


Gender: male
Posts: 55
Re: Google Interview Question  
« Reply #7 on: Mar 11th, 2010, 1:36am »
Quote Quote Modify 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 Quote Modify 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: male
Posts: 47
Re: Google Interview Question  
« Reply #9 on: Mar 11th, 2010, 5:53am »
Quote Quote Modify Modify

on Mar 11th, 2010, 1:27am, sulfur wrote:
Aaah !!!
 
I was able to do the question without sorting and in linear time complexity.  Tongue

 
 
  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: male
Posts: 55
Re: Google Interview Question  
« Reply #10 on: Mar 11th, 2010, 7:24am »
Quote Quote Modify 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: male
Posts: 47
Re: Google Interview Question  
« Reply #11 on: Mar 11th, 2010, 6:31pm »
Quote Quote Modify 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 Quote Modify 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: male
Posts: 13730
Re: Google Interview Question  
« Reply #13 on: Mar 20th, 2010, 11:35am »
Quote Quote Modify 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 Quote Modify 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: male
Posts: 250
Re: Google Interview Question  
« Reply #15 on: Dec 17th, 2010, 10:12pm »
Quote Quote Modify 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: male
Posts: 919
Re: Google Interview Question  
« Reply #16 on: Dec 18th, 2010, 1:40am »
Quote Quote Modify 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
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board