Microsoft Interview Question
Country: United States
make a hash table, walk over elements of array A and insert into HT, now walk over elements of B if not found in HT, return false, if found remove from HT.
Now check if something is left in HT, if yes, return false else return true.
@Ashish, well that's clear. The question was whether we can do it in O(n) and O(1) space
I thought for this question for quite a while.. you probably right that there is no universal solution in O(n) time and O(1) space.
Yet the number of different combinations to try is practically infinite: for example, you can take sums modulo 2^n (to prevent overflow) combined with inverse grey code, popcount, bitreversal, etc. Besides there is a number of cryptographic hash functions like MD5 checksums that can be computed in O(n) time.. this would give a correct answer with high probability.
So my point is proving that O(n) time O(1) space is not possible in general is not easy while the reverse is also true..
O(1) memory does not mean not using memory, it basically means that the memory requirement should be constant irrespective of the input size.
What this implies is,
1. I can allocate an array of size of maximum range of integers ( always constant size) hence O(1) and initialize it to zero.
2. I can use O(n) time to scan the first array and increment the count at corresponding indices i.e. if the element is 25 increment the value at 25th index ( if we consider negative integers, then it would mean adding the max possible negative number to find the index)
3. Scan the second array in O(n) time and this time decrement the values at the corresponding indices.
4. Scan the large array, if all elements are zero, then the two input arrays are permutations.
This solution is based on the basis of O(1) meaning constant space!!
Primus though u r right that O(1) means memory requirement should be constant but still it doesnt mean that u allocate infinite amount of memory initially and that remains constant. The sizes of both arrays can vary and this may be possible that size of one array can reach size of RAM.
We can add 1st 2 prime numbers one=by-one to each element of both the arrays.
Compare the products.
if(a.length != b.length)
return false;
for (int i = 0; i < a.Length; i++)
{
a[i]=a[i]+3;
if (a[i] != 0)
prodA = prodA * a[i];
b[i]=b[i]+3;
if (b[i] != 0)
prodB = prodB * b[i];
}
if (prodA == prodB)
{
//For some extreme cases
for (int i = 0; i < a.Length; i++)
{
a[i]=a[i]+5;
if (a[i] != 0)
prodA = prodA * a[i];
b[i]=b[i]+5;
if (b[i] != 0)
prodB = prodB * b[i];
}
}
else
return false;
if(prodA == prodB)
return true;
else
return false;
you can take any example.
the addition of 1st prime number is more than enough.
But still I am using 2nd prime number just to be sure that there is no extreme cases that fall outside the 1st one.
the correctness of this algo is no more than a random guess.
It is mathematically non-sense and against some most basic algebraic commen sense.
it is like you want to solve a equation group with 100000 variables and only 2 equations. I can prove that, ofc, if the size is 2, your method is correct, coz it is solving a equation group with 2 variables and 2 equations. But it is definitely wrong when size goes beyond 2.
Also, the choice of 3 , 5 makes 0 sense too. when the size is 2, any two different numbers, even two complex numbers can be used there to provide the correct solution. when the size goes beyond two, no particular numbers can help.
Sachin, product can go too big to handle, thus, not suitable for cases where n is say 50, thus, product can be almost equivalent to 50!
if(a.length != b.length)
return false;
for (int i = 0; i < a.Length; i++)
{
a[i]=a[i]+3;
if (a[i] != 0)
prodA = prodA * a[i];
b[i]=b[i]+3;
if (b[i] != 0)
prodB = prodB * b[i];
}
if (prodA == prodB)
{
//For some extreme cases
for (int i = 0; i < a.Length; i++)
{
a[i]=a[i]+5;
if (a[i] != 0)
prodA = prodA * a[i];
b[i]=b[i]+5;
if (b[i] != 0)
prodB = prodB * b[i];
}
}
else
return false;
if(prodA == prodB)
return true;
else
return false;
1. Add 1st two prime numbers one-by-one to both the arrays
2. Compare the products.
Tested for a lot of cases. Please let me know if skipped any.
I checked all the answers but I couldn't see anything like this. Correct me if I am wrong.
Is it possible to make this like below:
1. For example we have two arrays like [3,2,5,6] and [5,6,2,3]
2. First Sum=2^3 + 2^2 + 2^5 + 2^6=108
3. Second Sum= 2^5+2^6+2^2+2^3=108
4. We know these sums are unique. Am I wrong?
If these are equal than we can claim that these arrays are permutations of each other.
lont flag = 0;
#for every number in a ,set the corresponging bit to 1
for ( i = 0; i < n; i ++)
{
flag = flag | (1 << a[i])
}
#for every number in j,check if the bit is set.If it is,clear it and proceed,if it is not set,return False
for(i = 0; i <n ; i++)
{
if( 1 << b[i])
{
flag = flag & ~(1 << b[i])
}
else
{
return false;
}
}
if(flag ==0)
{
return true;
}
A shot in the dark :)
A={x1, x2, x3, .. xn}
B={y1, y2, y3, .. yn}
Sum(A) = x1+x2+x3+...+xn (for all x)
Mul(A) = x1*x2*x3*...*xn (for all x!=0)
Sum(B) = y1+y2+y3+...+yn (for all y)
Mul(B) = y1*y2*y3*...*yn (for all y!=0)
if(Sum(A) == Sum(B) && Mul(A) == Mul(B)
&& zerosCountIn(A) == zerosCountIn(B))
{
return true;
}
else
{
return false;
}
Yes, it can be done in O(n) time and O(1) space complexity.
Consider multiplying all of the numbers of the array
Array1: a1,a2,a3,a4...an
Product of Array1 numbers = a_prod
Array 2: b1,b2,b3....bn
Product of Array2 numbers = b_prod
a_prod will NEVER be equal to b_prod unless the arrays are permutations of each other.
SOLVED. :)
O(nlog n) solution:
1) Sort both the arrays - O(nlog n)
2) Compare both the arrays - O(n)
Sorting arrays is O(N log N) at best, while the requirement is O(N). See my implementation using the bitwise XOR, which is considered to be the most efficient solution for this.
This can be done in O(N) time and with O(1) space using a simple bitwise XOR like below.
bool is_valid_permutation(int a[], int b[], int cnt)
{
int XOR = 0;
int i;
for (i = 0 i < cnt; i++){
XOR = XOR ^ a[i];
XOR = XOR ^ b[i];
}
return (!XOR)
}
ooh man I can give you hundreds of counterexamples where xor is zero but arrays are not permutations:
a: [1 6 0 0 4 ] -- b: [1 0 6 1 5 ]
a: [1 6 0 0 5 ] -- b: [1 0 6 1 4 ]
a: [1 6 0 0 0 ] -- b: [1 0 6 2 2 ]
a: [1 6 0 0 1 ] -- b: [1 0 6 2 3 ]
a: [1 6 0 0 3 ] -- b: [1 0 6 2 1 ]
a: [1 6 0 0 4 ] -- b: [1 0 6 2 6 ]
a: [1 6 0 0 6 ] -- b: [1 0 6 2 4 ]
a: [1 6 0 0 0 ] -- b: [1 0 6 3 3 ]
a: [1 6 0 0 1 ] -- b: [1 0 6 3 2 ]
a: [1 6 0 0 2 ] -- b: [1 0 6 3 1 ]
a: [1 6 0 0 5 ] -- b: [1 0 6 3 6 ]
a: [1 6 0 0 6 ] -- b: [1 0 6 3 5 ]
a: [1 6 0 0 0 ] -- b: [1 0 6 4 4 ]
a: [1 6 0 0 1 ] -- b: [1 0 6 4 5 ]
a: [1 6 0 0 2 ] -- b: [1 0 6 4 6 ]
a: [1 6 0 0 5 ] -- b: [1 0 6 4 1 ]
a: [1 6 0 0 6 ] -- b: [1 0 6 4 2 ]
a: [1 6 0 0 0 ] -- b: [1 0 6 5 5 ]
a: [1 6 0 0 1 ] -- b: [1 0 6 5 4 ]
a: [1 6 0 0 3 ] -- b: [1 0 6 5 6 ]
a: [1 6 0 0 4 ] -- b: [1 0 6 5 1 ]
a: [1 6 0 0 6 ] -- b: [1 0 6 5 3 ]
a: [1 6 0 0 0 ] -- b: [1 0 6 6 6 ]
a: [1 6 0 0 2 ] -- b: [1 0 6 6 4 ]
a: [1 6 0 0 3 ] -- b: [1 0 6 6 5 ]
a: [1 6 0 0 4 ] -- b: [1 0 6 6 2 ]
a: [1 6 0 0 5 ] -- b: [1 0 6 6 3 ]
a: [1 6 0 1 1 ] -- b: [1 0 6 0 0 ]
a: [1 6 0 1 2 ] -- b: [1 0 6 0 3 ]
a: [1 6 0 1 3 ] -- b: [1 0 6 0 2 ]
a: [1 6 0 1 4 ] -- b: [1 0 6 0 5 ]
a: [1 6 0 1 5 ] -- b: [1 0 6 0 4 ]
a: [1 6 0 1 0 ] -- b: [1 0 6 2 3 ]
a: [1 6 0 1 1 ] -- b: [1 0 6 2 2 ]
a: [1 6 0 1 3 ] -- b: [1 0 6 2 0 ]
a: [1 6 0 1 5 ] -- b: [1 0 6 2 6 ]
a: [1 6 0 1 6 ] -- b: [1 0 6 2 5 ]
a: [1 6 0 1 0 ] -- b: [1 0 6 3 2 ]
a: [1 6 0 1 1 ] -- b: [1 0 6 3 3 ]
a: [1 6 0 1 2 ] -- b: [1 0 6 3 0 ]
a: [1 6 0 1 4 ] -- b: [1 0 6 3 6 ]
a: [1 6 0 1 6 ] -- b: [1 0 6 3 4 ]
a: [1 6 0 1 0 ] -- b: [1 0 6 4 5 ]
a: [1 6 0 1 1 ] -- b: [1 0 6 4 4 ]
a: [1 6 0 1 3 ] -- b: [1 0 6 4 6 ]
a: [1 6 0 1 5 ] -- b: [1 0 6 4 0 ]
here is the counterexample where xors are the same
and sums are the same:
a: [1 3 3 4 5 ] -- b: [5 3 1 2 5 ]
a: [1 3 3 4 5 ] -- b: [5 3 1 5 2 ]
a: [1 3 3 5 4 ] -- b: [5 3 1 1 6 ]
a: [1 3 3 5 4 ] -- b: [5 3 1 2 5 ]
a: [1 3 3 5 4 ] -- b: [5 3 1 5 2 ]
a: [1 3 4 0 5 ] -- b: [5 3 0 0 5 ]
a: [1 3 4 0 5 ] -- b: [5 3 0 5 0 ]
a: [1 3 4 5 0 ] -- b: [5 3 0 0 5 ]
a: [1 3 4 5 0 ] -- b: [5 3 0 5 0 ]
a: [1 3 4 1 5 ] -- b: [5 3 1 5 0 ]
a: [1 3 4 3 5 ] -- b: [5 3 1 1 6 ]
a: [1 3 4 3 5 ] -- b: [5 3 1 2 5 ]
a: [1 3 4 3 5 ] -- b: [5 3 1 5 2 ]
a: [1 3 4 5 3 ] -- b: [5 3 1 1 6 ]
a: [1 3 4 5 3 ] -- b: [5 3 1 2 5 ]
a: [1 3 4 5 1 ] -- b: [5 3 1 5 0 ]
a: [1 3 4 5 3 ] -- b: [5 3 1 5 2 ]
a: [1 3 5 0 2 ] -- b: [5 3 0 0 3 ]
a: [1 3 5 0 4 ] -- b: [5 3 0 0 5 ]
a: [1 3 5 0 2 ] -- b: [5 3 0 3 0 ]
a: [1 3 5 0 4 ] -- b: [5 3 0 5 0 ]
a: [1 3 5 2 0 ] -- b: [5 3 0 0 3 ]
a: [1 3 5 2 0 ] -- b: [5 3 0 3 0 ]
a: [1 3 5 4 0 ] -- b: [5 3 0 0 5 ]
O(n) time and O(n) space (using HashMap) seems to be the most feasible solution. Can't think of any algo and datastructure combination yielding O(n) time and O(1) space.
int arr1[]={2,4,6,7,3};
int arr2[]={6,3,7,4,2};
HashMap<Integer,Integer> hm2=new HashMap<Integer,Integer>();
//1) length 1 = length 2
//2) Every integer shud be there in the table twice
// Handle cases where both of them can have two two values
if(arr1.length == arr2.length)
{
for(int p=0;p<arr1.length;p++)
{
if(hm2.containsKey(arr1[p]))
{
Integer temp = (Integer)hm2.get(arr1[p]);
hm2.remove(arr1[p]);
hm2.put(arr1[p], temp+1);
}
else
hm2.put(arr1[p], 1);
}
for(int p=0;p<arr1.length;p++)
{
if(hm2.containsKey(arr2[p]))
{
Integer temp = (Integer)hm2.get(arr2[p]);
hm2.remove(arr2[p]);
hm2.put(arr2[p], temp-1);
}
else
hm2.put(arr2[p], 1);
}
System.out.println(hm2.values());
int count=0;
for(int l : hm2.values())
{
if(l == 0)
{
count += 1;
}
}
if(count == arr1.length)
System.out.println("They are permutations");
else
System.out.println("They are not permutations");
}
//I am doing it in 3n steps, Can some one do it better
We know that we can get many possible examples where multiplication or addition of n-numbers can be same as that of n other no.'s.
Why don't we use both multiplication and addition. I think I'm really tired b'coz it's really consuming my energy to think of such two different sets of n-no,s having same addition and multiplication (both). May be somebody can think them for me.
Not bothered abt special cases of 0 and 1.
here it is:
a: [1 2 5 6 7 8 9 ] -- b: [1 10 9 4 3 7 4 ]
]; sum_a: 38; sum_b: 38; mul_a: 30240; mul_b: 30240; xor_a: 6; xor_b: 6
a: [1 2 5 6 7 8 9 ] -- b: [1 10 9 4 4 3 7 ]
]; sum_a: 38; sum_b: 38; mul_a: 30240; mul_b: 30240; xor_a: 6; xor_b: 6
a: [1 2 5 6 7 8 9 ] -- b: [1 10 9 4 4 7 3 ]
]; sum_a: 38; sum_b: 38; mul_a: 30240; mul_b: 30240; xor_a: 6; xor_b: 6
a: [1 2 5 6 7 8 9 ] -- b: [1 10 9 4 7 3 4 ]
]; sum_a: 38; sum_b: 38; mul_a: 30240; mul_b: 30240; xor_a: 6; xor_b: 6
a: [1 2 5 6 7 8 9 ] -- b: [1 10 9 4 7 4 3 ]
]; sum_a: 38; sum_b: 38; mul_a: 30240; mul_b: 30240; xor_a: 6; xor_b: 6
a: [1 2 5 6 8 9 10 ] -- b: [1 10 9 4 3 4 10 ]
]; sum_a: 41; sum_b: 41; mul_a: 43200; mul_b: 43200; xor_a: 11; xor_b: 11
a: [1 2 5 6 8 9 10 ] -- b: [1 10 9 4 3 10 4 ]
]; sum_a: 41; sum_b: 41; mul_a: 43200; mul_b: 43200; xor_a: 11; xor_b: 11
a: [1 2 5 6 8 9 10 ] -- b: [1 10 9 4 4 3 10 ]
]; sum_a: 41; sum_b: 41; mul_a: 43200; mul_b: 43200; xor_a: 11; xor_b: 11
a: [1 2 5 6 8 9 10 ] -- b: [1 10 9 4 4 10 3 ]
]; sum_a: 41; sum_b: 41; mul_a: 43200; mul_b: 43200; xor_a: 11; xor_b: 11
"The idea is that, if the arrays were sorted, the difference between every element Ai and Bi would be zero. Using this property, we can deduce that, the sum of all the numbers in the imaginary array C, which contains the difference of numbers Ai and Bi respectively, will be zero.
So if there is a number that is in array A and not in array B, the sum of numbers in the imaginary array C, will be non-zero. Thus we can find if array B is a permutation of array A."
linearspacetime.blogspot.com/#!/2012/05/check-if-array-is-permutation-of.html
Sorry, my solution worked only for some cases. I have added an additional condition: I now check that the product of numbers in both arrays too. If the difference=0 and prodA==prodB, then it is a permutation.
for (int i = 0; i < a.Length; i++)
{
// Get the difference
if (a[i] != 0)
prodA = prodA * a[i];
if (b[i] != 0)
prodB = prodB * b[i];
// Get the difference
difference += a[i] - b[i];
}
// Return the result
if (difference == 0 && prodA == prodB)
return true;
else
return false;
I have not tested it for different test cases though. Will test it and reply back to this thread. Thanks for the feedback :)
bool is_valid_permutation(int a[], int b[], int cnt)
{
int sum1 = 0;
int sum2 = 0;
int i;
for (i = 0; i < cnt; i++){
sum1 += 10 ^ a[i];
sum2 += 10 ^ b[i];
}
return (sum1 == sum2)
}
This is a great solution, however if array's size and elements are large, it will use lots of space. Instead of using 10^ you can just use 2^, but still there is space concern.
@cp, are you serious man ?
what's the difference btw "10 xor b[i]" and "2 xor b[i]" ?
actually I have no idea why he needs xor at all because he simply compares the sums of two arrays which is not a satisfying criterion for permutation
the problem that prevents us doing the stuff through XORing is non-uniqueness of the elements , if there is no repeated element then only the O(n) and o(1) is achievable.
that's not true either. Consider:
a: [1 2 3 9 14 16 19 ] -- b: [1 2 3 19 17 12 10 ]
from the above examples where xors, sums, square sums
and min/max are the same
void main()
{
int a[5]={1,6,0,0,4};
int b[5]={1,0,6,4,0};
int i,sum=0;
for(i=0;i<5;i++)
sum=sum+(a[i]-b[i]);
if(sum==0)
printf("Is permutation");
else
printf("Not Permutation");
}
How about instead of doing the sum or XOR, we do the product BUT each letter get a prime number associated with it. Sorry if I am not clear enough, an example if worth a thousand instructions:
Array A: [a,b,c,d]
Array B: [c,a,d,b]
and lets use the following value for each letter (I am starting at 3)
a-> 3
b-> 5
c-> 7
d-> 11
so array A would give 3*5*7*11 and array B would be 7*3*11*5 and would give the same result. It will not have any collision.
If we assume that we have a list of prime numbers or something similar, the complexity would be O(n) and the required space would be an integer ( without the prime number list)
Any feedback?
For any integer k, just use the Kth prime.
This is a solution only when you have unlimited computation power.
It works for an alien computer or a computer in the far future.
But it does satisfy the requirement. O(n) time and O(1) space.
I think we can do it in o(n) time and o(1) space. Make an array of size = 2 * 32767(size of the integer) and do hashing for both the arrays.If the both hash to the same entries then its true else false. Also I know many people will say my answer is wrong as the size of the array used for hashing is 32767 but guys its still be o(1) space as its constant space....:)
is the idea is to compare sum of pow(10,a[i]) and sum of pow(10,b[i])?? i guess it works
hw abt just first add 1 to both the arrays,multiply them and check if they are equal and do the same again after adding 2. It will remove the problem of common factors.
how about
1. find sum of a and b
2. find sum of square every a[i] and b[i]
3. find sum of cube of every a[i] and b[i].
if(sum(a) == sum(b) &&( sum_of_square(a[i]) == sum_of_square(b)) && (sum_of_cube(a[i] == sum_of_cube(b[i]))))
print("a and b r permutation")
Time: O(n)
Space: 3*O(1) i.e. O(1) unless it doesn't overflow
boolean isDuplicate(int *a, int *b, int n) {
int xorss = 0;
for (i =0; i<n; i++) {
xorss = xorss ^ a[i];
xorss = xorss ^ b[i];
}
if (xorss == 0) return true;
return false;
}
I'm going to prove the solution with O(n) time and O(1) space dosn't exist.
Let's make following assumptions that simplify the problem:
1) the array 'a' is sorted,
2) both arrays contain only unique elements.
To check that 'b' is permutation of 'a' we'll have to pick every element of 'b' and check whether it is in 'a'.
It is done with binary search in O(ln(n)) time.
It could not be done any faster even if we utilized information from the previous steps (removing elements already found in 'a', for example.)
So even in this, simplified case, the problem requires O(n*ln(n)) time to get solved.
Did I miss something?
//given 2 unsorted integer arrays a and b of equal size. Determine if b is a permutation of a.
//Can this be done in O(n) time and O(1) space ?
#include<iostream>
#define size 7
using namespace std;
int main()
{
int a[size];
int b[size];
int i;
cout<<"Enter "<<size<<" elements into first array :"<<endl;
for(i=0;i<size;i++)
{
cin>>a[i];
}
cout<<"Enter "<<size<<" elements into second array :"<<endl;
for(i=0;i<size;i++)
{
cin>>b[i];
}
int max1=a[0];
int max2=b[0];
int flag=1;
int*count;
//find max of first array
for(i=0;i<size;i++)
{
if(a[i]>max1)
max1=a[i];
}
//find max of second array
for(i=0;i<size;i++)
{
if(b[i]>max2)
max2=b[i];
}
if(max1!=max2)
flag=0;
else
{
count=new int[max1+1];
for(i=0;i<max1+1;i++)
count[i]=0;
for(i=0;i<size;i++)
{
count[a[i]]++;
}
for(i=0;i<size;i++)
{
count[b[i]]++;
}
for(i=0;i<max1+1;i++)
{
if(count[i]==1)
flag=0;
}
}
if(flag)
cout<<"Permutations"<<endl;
else
cout<<"Not permutations"<<endl;
delete[] count;
return 0;
}
What i'm doing is :
1. I'm finding the max element of both arrays. Call them max1 and max2
2. if max1!=max2, then not permutations.
3. Else, i'm creating an array "count" of size=max1/max2+1 and initialising it to zero.
4. Scan the first array and increment count of each element in the count array.Similarly for the second array.
5. Now scan the "count" array to see if there is any entry containing 1. If there is then the two arrays are not permutations. If they are, then the "Count" array will have entries either 0 or 2.
If you remember the merge procedure in merge sort,
Run merge procedure on both arrays.
1. If the current heads of both arrays are equal, then delete both of them from the arrays
2. If the next element to be inserted in the merged array is same as its tail then remove that element
from its array as well as the tail of the merged array.
I think it's indeed not doable in O(n) time. Here is a couple of extreme counterexamples where
- Anonymous May 16, 2012sums are the same, square sums are the same, xors are the same,
min/max are the same and the # of odd elements is the same:
a: [1 2 3 9 14 16 19 ] -- b: [1 2 3 19 17 10 12 ]
]; sum_a: 64; sum_b: 64; sq_sum_a: 908; sq_sum_b: 908; xor_a: 4; xor_b: 4
a: [1 2 3 9 14 16 19 ] -- b: [1 2 3 19 17 12 10 ]
]; sum_a: 64; sum_b: 64; sq_sum_a: 908; sq_sum_b: 908; xor_a: 4; xor_b: 4
a: [1 2 3 9 12 18 20 ] -- b: [1 2 3 20 17 8 14 ]
]; sum_a: 65; sum_b: 65; sq_sum_a: 963; sq_sum_b: 963; xor_a: 3; xor_b: 3
a: [1 2 3 9 12 18 20 ] -- b: [1 2 3 20 17 14 8 ]
]; sum_a: 65; sum_b: 65; sq_sum_a: 963; sq_sum_b: 963; xor_a: 3; xor_b: 3