Google Interview Question Software Engineer / Developers
Country: -
Interview Type: In-Person
In fact, it seems this solution is very general. Instead of working for just a list containing 1...N, it can work on a list containing any integers whatsoever.
To elaborate a little on the general proof of this: suppose you have a partition such that you know all numbers there are k mod X. So initially, your partition is the entire list, and you know all numbers there are 0 mod 1 (whole number constraint).
Now, partition your partition as follows
N | N = X+K (mod 2X) and
N | N = K (mod 2X).
These are the only possibilities for values mod 2X if we know N = K (mod X). The sum of a value that is X+K mod 2X and another value that is K mod 2X is necessarily X + 2K mod 2X, and so the average would be K + X / 2 mod X. X is a power of 2 (because we started at 1 and always scaled in 2s) so the division works out.
Now, we said the average of any two numbers from two different sub-partitions of our partition is K + X / 2 mod X, but the constraint on the partition as a whole (and therefore applicable to every number there) is that each number is K mod X. So for the average to be anywhere in the partition (and a number must be in the partition to be positioned between two numbers that are both in the partition), it would have to be that K = K + X/2 (mod X). This implies that X/2 = 0 (mod X), which is impossible for X != 0.
Another thought that just occurred to me is that this is a radix sort sorting by least significant digit first.
The solution that I came up with was to partition the array into two halves where one half contains the even indexed numbers and the other half contains the odd indexed numbers. The only assumption is that I keep each partition sorted. The conquer step is simply concatenating the array.
The most difficult part was that I had to figure out the hint myself by asking questions to the interviewer. I initially had the impression that if the average was non-integer then we would round that.
@eugene ..
If I cunderstood your approach correctly .. then u are dividing odd numbers into 2 groups, where avg of one grp lies in other grp (in case where avg(odd, odd) = odd)
... If you notice ... this approach fails after a certain no of off nos ..
group1 | group2
1 | 3
5 | 7
9 | 11
13 | 15
.. etc ..
group1 -> 1 modulo 4
group2-> 3 modulo 4
in grp1 avg(1,9) = 5, which is present in the same group, due to which this approach fails for total no of odd numbers > 4
let me knw if u were trying to propose something else ..
@lyra_vega
I didn't get your approach .. Could you please explain with an example ..
even is the partitions are sorted, how are you ensuring for the above property .. ?
@pallavi.bansal20:
Yes, initially the odd numbers would be partitioned into, say, 1 5 9 13 | 3 7 11 15, but then each of those sections in turn would be partitioned again, giving something like 1 9 | 5 13 || 3 11 | 7 15. When there's only 2 numbers per partition, we're done. I invite you to verify that
1 9 5 13 3 11 7 15 satisfies the constraint.
@lyra_vega: So, would your algorithm have produced something like 1 3 5 7 2 4 6 8? You can see how that's incorrect... Splitting by odd and even numbers is the right initial thought, though.
How are you again distributing the set ? Taking every sesond element and putting in one grp, and then reiterating, untill the total size is 2 .. ?
How will u code this eeficiently ?
Let's say you started with 1 2 3 4 5 6 7 8 9 10 11 12.
1 2 3 4 5 6 7 8 9 10 11 12 -> 2 4 6 8 10 12 (0 mod 2) | 1 3 5 7 9 11 (1 mod 2) -> 4 8 12 (0 mod 4) | 2 6 10 (2 mod 4) || 1 5 9 (1 mod 4) | 3 7 11 (3 mod 4) -> 8 (0 mod 8) | 4 12 (4 mod 8) || 2 10 (2 mod 8) | 6 (6 mod 8) ||| 1 9 (1 mod 8) | 5 (5 mod 8) || 3 11 (3 mod 8) | 7 (7 mod 8).
Now all the partitions are size 2 or smaller, so we're done. The final result is 8 4 12 2 10 6 1 9 5 3 11 7.
I invite you to verify that all constraints are satisfied.
Yes, thiss seems correct. Thinking on the implementation part,
We will required to perform mod ops by nos 2,4,8,16, .. etc .. (powers of 2, sinc ewe always dived the sets into 2) .
If we can identify in the first go, which mod it will max require. We can do this in one shot. for N between 8 and 16, mod 8 will be required.
For a general N, we need to find the smallest n, such that, N <= 2^n
So, we can direct start placing them, in the array like,
0 mod n --
1 mod n ..
... till n-1 mod n ..
This is done in O(N) time and constant space.
Let me know if thr is somthing wrong here ..
Nice approach btw :)
You couldn't place them like 0 mod n, 1 mod n, ...
They need to be placed 0 mod 8, 8/2 mod 8, 8/4 mod 8, 3*8/4 mod 8, 8/8 mod 8, 5*8/8 mod 8...the pattern is much more complex.
My current approach is essentially a radix sort judging least significant digit first. It's as if you reversed the digits of all the numbers, radix sorted them, and then reversed the numbers back to what they were. So it's O(NK), where N is how many numbers you have, and K is the number of digits in each number.
@eugene.yaravoi
My approach would be to partition the array as long as there are two elements. So the result would be:
1,2,3,4,5,6,7,8,9,10,11,12 --- initial
1,3,5,7,9,11 2,4,6,8,10,12 --- 1st divide
1,5,9 3,7,11 2,6,10 4,8,12 --- 2nd divide
1,9 5 3,11 7 2,10 6 4,12 8 --- 3rd divide
1,9,5 3,11,7 2,10,6 4,12,8 --- 1st merge
1,9,5,3,11,7 2,10,6,4,12,8 --- 2nd merge
1,9,5,3,11,7,2,10,6,4,12,8 --- 3rd merge (final result)
At every divide, I break the existing partition into two partitions where even position elements go to one partition and odd position elements go to the other partition. So at each level <i> I group numbers that are k mod pow(2, i). For every partition, I would have two values of k and hence two sub-partitions. The logic is probably similar to yours.
basically for number form 1 to 10 we should have
1,5,9,7,3, 2,6,10,8,4
as you can see even and uneven numbers are partitioned. and biggest numbers are in the center of every partition.
You can do it in O(n) time and no extra space, by using function that for x between 1 and n, will return you need index of the array.
After dividing the groups into odd and even numbers why not sort them zig zag way, like
Step 1: 1 2 3 4 5 6 7 8 9 10 11 12 //given elements
Step 2: 1 3 5 7 9 11 | 2 4 6 8 10 12 // breaking into odd and even groups
Step3 : 1 11 3 9 5 7 | 2 12 4 10 6 8 // merge them in a zig zag manner... should give the answer...
I believe that this sequence sure has many answers, so why not this one?
input: 1 3 5 7 2 4 6 8
output: 1 7 3 5 2 8 4 6
Using another example...can someone please let me know what am I missing here :O
Are there more splits after splitting mod 4? If not this fails for N=10
After the 0 mod 4 and 2 mod 4 split, we have 2,6,10 all in one bucket since they are all 2 mod 4. 6 is the average of 2+10 so the solution is incorrect.
Edit: nvm
Time: O(nlgn)
Space: O(n)
public void arrange(int[] a, int[] b, int i, int j)
{
if(j == i) return;
for(int k = i; k <= j; k++) b[k] = a[k]; // copy the elements to the temporary array
int r = i + (j - i) / 2 + 1; // the pivot where the even half starts
int p = i; // the starting index of the odd half
int q = r; // the starting index of the even half
for(int k = i; k <= j; k++) {
if((k - i) % 2 == 0) a[p++] = b[k];
else a[q++] = b[k];
}
arrange(a, b, i, r - 1);
arrange(a, b, r, j);
}
The naive solution is inspired from bubble sort. If we find "bad" happens, i.e. a[k]=b, i<=k<=j, we swap a[k] and a[j]. For each element in the array, we run such test. The process ends when all the elements are tested. I guess the time complexity is O(n^2)
I'm not convinced this is correct. Is this the sequence of ops you had in mind (stars denote next swap to be contemplated)?
1* 2* 3 4 5 -> 1* 2 3* 4 5 -> 1* 3 2 4* 5 -> 1* 3 2 4 5* - 1 5* 2* 4 3 -> 1 5* 2 4* 3 -> 1 5* 2 4 3* -> 1 5 2* 3* 4 -> 1 5 2* 3 4* -> 1 5 2 4* 3*
But 1 and 3 average to 2.
I got to say, it feels right. I am still working on the details and hopes to code it right
good algo @eugene ))
I think what you are doing is just sorting the array by bit-reversal: indeed because first you partition mod 2
than mod 4 and so on. This can be done in a single pass, if the numbers are small, or using a conventional sort as follows:
struct cmp {
bool operator()(int a, int b) {
return (bitrev(a) < bitrev(b));
}
int bitrev(int x) {
int m = 0x55555555;
x = ((x & m) << 1) | ((x & ~m) >> 1);
m = 0x33333333;
x = ((x & m) << 2) | ((x & ~m) >> 2);
m = 0x0f0f0f0f;
x = ((x & m) << 4) | ((x & ~m) >> 4);
m = 0x00ff00ff;
x = ((x & m) << 8) | ((x & ~m) >> 8);
m = 0x0000ffff;
x = ((x & m) << 16) | ((x & ~m) >> 16);
return x;
}
};
int main()
{
int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
int n = sizeof(a) / sizeof(int);
// get a random shuffle first
std::random_shuffle(a, a + n);
for(int i = 0; i < n; i++) {
std::cout << a[i] << " ";
}
std::cout << "\n";
// now sort the array according to bit rev index
std::sort(a, a + n, cmp());
for(int i = 0; i < n; i++) {
std::cout << a[i] << " ";
}
std::cout << "\n";
return 0;
}
output: 1 9 5 3 11 7 8 4 12 2 10 6
Based on eugene's idea on radix sort "Another thought that just occurred to me is that this is a radix sort sorting by least significant digit first.", I come up with the following code and it is tested.
class radix_test{
int bit;
public:
radix_test(int offset):bit(offset){}
bool operator()(int value){
if(bit==31)
return value<0;
else
return !(value&(1<<bit));
}
};
void Array::Arrange_Array(int* first, int* last,int lsd){
if(first==last) return;
if(lsd==32) return;
int* mid=std::stable_partition(first,last,Pearl::radix_test(lsd));
lsd++;
Arrange_Array(first,mid,lsd);
Arrange_Array(mid,last,lsd);
}
test case int a[]={3,1,4,5,2,1,2}; output: 4,2,2,1,1,5,3
The problem states to re-arrange number from 1 to N, so the second test case is int a[]={1,2,3,4,5,6,7}, output is 4,2,6,1,5,3,7
Could you please explain what you are doing in the code .. ? why 31 and 32 ?? wht bit manipulations are you doing ?
Sure, The radix_test class wraps an operation () which performs the test in std::stable_partition. stable_partition performs partition according to the test function which is implemented by radix_test. lsd stands for least significant digit. The algorithm works like this: first we partition the array such that the first half contains elements whose lsd is 0 and second half contains elements whose lsd is 1. By this, we implement eugene idea of separating odd number and even number. We recursively doing this in each half by partitioning by the next lsd.
the stop condition 1) first==last is trivial 2) lsd=32 because the type is int, it only contains 32 bit. Therefore, we stop there. Hope it helps
@geliang2008,
I tried your code but failed to work.
1. What does Pearl ( in Pearl::radix_test(lsd)) mean?
2. what is the input? I ran the following sample, and ASSERT will be shown "invalid iterator range"
int a13[12] = {1,2,3,4,5,6,7,8,9,10,11,12};
int a14[12] = {0,0,0,0,0,0,0,0,0,0,0,0};
Arrange_Array(a13, a14, 1);
Sure, The radix_test class wraps an operation () which performs the test in std::stable_partition. stable_partition performs partition according to the test function which is implemented by radix_test. lsd stands for least significant digit. The algorithm works like this: first we partition the array such that the first half contains elements whose lsd is 0 and second half contains elements whose lsd is 1. By this, we implement eugene idea of separating odd number and even number. We recursively doing this in each half by partitioning by the next lsd.
the stop condition 1) first==last is trivial 2) lsd=32 because the type is int, it only contains 32 bit. Therefore, we stop there. Hope it helps
You code can't work. could you please take a look at it?
I always got an exception "invalid iterator range"
Hi All,
I think we can just swap the binary sequence of every number. But this works only if the N is a power of 2.
Please tell me whether this is correct or not
unsigned reverse_bits(unsigned int n, int bits)
{
unsigned int result = 0;
int write_bit = 0;
int read_bit = bits;
while (read_bit)
{
result |= (((n >> read_bit) & 1) << write_bit);
}
return result;
}
int * fun(unsigned int n)
{
unsigned int k = 1;
int bits = 1;
for (; k < n; k <<= 1, ++bits);
for (unsigned int r = 1; r < k; ++r)
{
unsigned proposed = reverse_bits(r, bits);
if (proposed <= n)
{
cout << proposed << ' ';
}
}
count << endl;
}
One solution for this question. O(logN) space complexity and O(nlogn) time complex
//findOwner(n, m) : Given n, and a position idx m
//Return which number should own this position.
//eg. n = 9; m = 3; it returns 9. Meaning, at the third position of the
//resultant sequence, the number should be 9
//O(logN) time and space for findOwner().
#include <iostream>
#include <stack>
#include "stdlib.h"
using namespace std;
typedef stack<int> Stack;
int findOwner (int n, int m)
{
Stack tags;
while(n > 1)
{
int half = (double)n/2 + 0.5;
int tag = (m - 1) / half;
n = half - (tag & n%2);
m = (m - 1)%half + 1;
tags.push(1 ^ tag);
}
while (!tags.empty())
{
m = 2 * m - tags.top();
tags.pop();
}
return m;
}
void solve(int n)
{
for (int i = 1; i <= n; ++i)
cout<<findOwner(n, i)<<' ';
}
int main(int argc, char * argv[])
{
int n = atoi(argv[1]);
cout<<n<<endl;
solve(n);
cout<<endl;
}
A different approach. Code is Perl:
my $N = shift || 10;
my @list = (1);
my $max = 1;
while ($max <= $N) {
for (my $i = 0; $i < @list; ++$i) {
if ( $list[$i] + $max <= $N ) {
splice @list, $i, 0, $list[$i]+$max;
++$i;
}
}
$max += $max;
}
print join(",", @list), "\n";
Here's why this works. The explanation is simpler if we assume that N is a power of 2.
Note that if a list has the property that the average of any two items in the list does not appear in the list between them, then so does any list derived from that list by adding or subtracting a constant from all items in the list. In the following, I'll be working with lists that have had 1 subtracted from each element.
The algorithm starts with the solution for N=1, which is (0). It then iteratively generates the solution for 2N from the solution for N by the following procedure: replace each item x in the list for N with a pair of items, N+x and x.
So, to go from N=1 to N=2, the 0 in (0) is replaced with 1, 0, giving (1, 0).
To go from N=2 to N=4, the 1 in (1,0) is replaced with 3, 1, and the 0 is replaced with 2, 0, giving (3, 1, 2, 0).
This gives us the sequence of lists for various N:
N=1 (0)
N=2 (1, 0)
N=4 (3, 1, 2, 0)
N=8 (7, 3, 5, 1, 6, 2, 4, 0)
...
This can be viewed as a binary tree, with the root being the 0 from (0). It's children are the 1 and 0 in (1, 0). The children of the 1 in (1, 0) are the 3 and 1 in (3, 1, 2, 0), and so on.
Observation: if two items, x and y, in a given row have a common ancestor z in an earlier row, then all items between x and y also have z as an ancestor. By "between" I mean between them in the list order, not numerically between. E.g., 1 is between 3 and 2 in the N=4 list.
Observation: if two items, x and y, in a given row have a common ancestor z in row N=k, then x and y are congruent to z mod k.
Now let's consider any two items, x and y, in the final row, and let z be their closest common ancestor and let z be in row N=k. If k=1, then one of x is even and one of x is odd, and so their average is not an integer and so is not in the final row.
If k != 1, then x and y are congruent to z mod k. Since z is the closest ancestor of x and y, one of them is part of the left subtree of z, and one is part of the right subtree of z. That means that one of them is congruent to z mod 2k, and one is congruent to k+z mod 2k.
Hence, the average of x and y is congruent to z+k/2 mod 2k, which means that it is also congruent to z+k/2 mod k. This shows that the average of x and y is not between x and y, because as we noted earlier, if it were between x and y, then it would have to have z in row N=k as an ancestor, and so would have to be congruent to z mod k.
Implementation note: if N is not a power of 2, you can just proceed as if it is a power of 2, and simply omit actually putting any numbers bigger than N in your list on each iteration, so you don't end up wasting space storing numbers that you aren't going to need. I do this in the Perl code above.
More concisely, but not quite as space efficient:
my $N = shift || 10;
my @list = (1);
my $max = 1;
while ($max < $N) {
@list = map {$_, $_+$max} @list;
$max += $max;
}
print join(",", grep {$_ <= $N} @list), "\n";
For every pair of number a[i],a[j] such that i<j or j<i, find their average, if its present in the array at position a[k] and i<k<j or j<k<i, then swap a[k] with left (a[i]) or right (a[j]). Repeat this for every pair.
Consider the following divide-and-conquer algorithm:
- eugene.yarovoi November 09, 2011Step 1. The left part of the list will have only even integers, the right side of the list only odd integers. Assertion: since (an even number + an odd number) / 2 does not average to a whole number, there can be no issues with numbers from different halves. We only have to worry about two numbers from the same halves causing problems.
Step 2. Take the even half and partition it into numbers that are 0 modulo 4 and numbers that are 2 modulo 4. The sum of these two numbers will be 2 mod 4, the average will be 1 mod 2, and so the average will be odd. But this is a list of even numbers, so there is no potential problem between these two partitions, and we only have to worry, once again, about the numbers from the same partition causing problems.
What about the odd half? Partition into numbers that are 1 mod 4 and 3 mod 4. Now, two numbers from different partitions would sum to 0 mod 4, average to 0 mod 2, but we already said there were no numbers 0 mod 2 in the odd half!
By continuing this logic (mod 8, mod 16, and so on), we can keep splitting the array into more and more pieces that cannot cause problems with each other, until each piece is of size 1.