## Microsoft Interview Question

Country: United States

Comment hidden because of low score. Click to expand.
2
of 2 vote

I think it's indeed not doable in O(n) time. Here is a couple of extreme counterexamples where
sums 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

Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
0

@Ashish, well that's clear. The question was whether we can do it in O(n) and O(1) space

Comment hidden because of low score. Click to expand.
0

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..

Comment hidden because of low score. Click to expand.
2
of 4 vote

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!!

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
1
of 1 vote

We have 2^32 integers, and in order to keep the frequencies, we need to have an int array. Therefore, memory requirement of your solution is:
32 * (2^32) bits = 2^37 bits = 16 GB

True, this is O(1), but I'm not quite sure the interviewer is looking for something this big.

Comment hidden because of low score. Click to expand.
1
of 3 vote

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;

Comment hidden because of low score. Click to expand.
0

Could you prove the correctness of your program?

Comment hidden because of low score. Click to expand.
0

Could you prove the correctness of your algo/program?

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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!

Comment hidden because of low score. Click to expand.
0

I can see otherwise, it is doing fine. Great logic though!!!

Comment hidden because of low score. Click to expand.
0

is there a name for this computation? seems like a encryption skill or something... anyone knows?

Comment hidden because of low score. Click to expand.
0
of 2 vote

``````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;``````

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

Could you prove the correctness of your algo/program?

Comment hidden because of low score. Click to expand.
0
of 0 vote

stackoverflow.com/questions/10639661/check-if-array-b-is-a-permutation-of-a

Comment hidden because of low score. Click to expand.
0
of 0 vote

@counterexample how u have generated these many test cases

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

counter example: a[1,3,3] b[0,0,4] ;

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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. :)

Comment hidden because of low score. Click to expand.
-1
of 1 vote

O(nlog n) solution:
1) Sort both the arrays - O(nlog n)
2) Compare both the arrays - O(n)

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
-1
of 3 vote

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)
}``````

Comment hidden because of low score. Click to expand.
0

+1

Comment hidden because of low score. Click to expand.
0

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 ]

Comment hidden because of low score. Click to expand.
0

and also sum of both arrays are same then only both are permutations

Comment hidden because of low score. Click to expand.
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 ]

Comment hidden because of low score. Click to expand.
0

a[0] = 111000111 a[1] = 111100000
b[0] = 000111000 b[1] = 000011111
a[0]^b[0]^a[1]^b[1] = 0 However, they are not permutation to each

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
0

+1

Comment hidden because of low score. Click to expand.
0

+1

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

Came to the same conclusion. The sum seems to catch cases that the product fails at and vice versa, but not sure if it's correct in all cases or how to prove it.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

I doubt O(n) O(1) requirement is come from interviewer unless this is not a WAP question which can be solved by hard coding instruction into the CPU. that is the only way that I can see, to get this done in O(n) time without using any data structure.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

"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

Comment hidden because of low score. Click to expand.
0

A: 2 2 2
B: 3 2 1
-----------
C: -1 0 1
Sum: 0
Conclusion: is permutation?

Comment hidden because of low score. Click to expand.
0

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 :)

Comment hidden because of low score. Click to expand.
0

look man, you should read previous posts before:
your soln is nothing but requiring the sums and products of two arrays being equal - it's already being shown above that it's not working

Comment hidden because of low score. Click to expand.
-1
of 1 vote

The solution posted above is O(n) time and O(1) space

Comment hidden because of low score. Click to expand.
0

is the idea is to compare sum of pow(10,a[i]) and sum of pow(10,b[i])?? i guess it works

Comment hidden because of low score. Click to expand.
-1
of 1 vote

The latest solution won't work too. For example, if A=12, 21, 0 and B=14, 18, 1, then the difference will be 0 and the products will be equal too.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

This prob rather cannot be solved in O(n) time and O(1) space! The question is whether this can be done or not and not to implement the same.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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)
}

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

@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

Comment hidden because of low score. Click to expand.
0

Nice one .. with 10 u need to check if both array sizes are same or not

With 2 ...

1 3 1

2 2 2 this will fail .. so its better to take a prime number

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
-1
of 3 vote

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");
}

Comment hidden because of low score. Click to expand.
0

dude, care about reading other comments before posting yours, it's been shown several times that two arrays having the same sum is not satisfiable condition for being permutation of each other

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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?

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

for n integers, we need n prime numbers...........this is not O(1)

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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....:)

Comment hidden because of low score. Click to expand.
0

why 32767 is size of the integer ??

Comment hidden because of low score. Click to expand.
-1
of 1 vote

What if i keep a bitmap of 2^32 bits. Thats 1GB of memory. We can keep a array of int size 2^27.
Whatever the size of input array, this requirement doesnt grown in size. So this is constant memory.

Multiple occurances of same number are a problem.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

is the idea is to compare sum of pow(10,a[i]) and sum of pow(10,b[i])?? i guess it works

Comment hidden because of low score. Click to expand.
0

At least,the number of the same element in the array can't be divided by 10.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Found this

stackoverflow.com/questions/2872959/how-to-tell-if-an-array-is-a-permutation-in-on

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Found this
stackoverflow.com /questions / 2872959 / how-to-tell-if-an-array-is-a-permutation-in-on

remove spaces

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
0

A:{0,1,4}
B:{0,2,3}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Find Sum and product if both arrays
If both are equal , B is permutation of A

Comment hidden because of low score. Click to expand.
-1
of 1 vote

create in-place heap for each array it is O(N) operation,
started from the top of both heap, compare top of the heaps, O(1)
remove tops if they are equal and restore heaps O(log N)
walk through both arrays O(N)

so, come for O(N) time O(1) space

Comment hidden because of low score. Click to expand.
-1
of 1 vote

create in-place heap for each array it is O(N) operation,
started from the top of both heap, compare top of the heaps, O(1)
remove tops if they are equal and restore heaps O(log N)
walk through both arrays O(N)

so, come for O(N) time O(1) space

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

Comment hidden because of low score. Click to expand.
-1
of 3 vote

boolean isDuplicate(int *a, int *b, int n) {
for (i =0; i<n; i++) {
}

if (xorss == 0) return true;

return false;
}

Comment hidden because of low score. Click to expand.
0

It will not work.

Counter Examples:

[1,3] [5,7]

[2,2] [4,4]

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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?

Comment hidden because of low score. Click to expand.
0

wake up man there are other ways to solve in O(n) even if it is not sorted

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````//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;
}``````

Comment hidden because of low score. Click to expand.
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.

Comment hidden because of low score. Click to expand.
0

i guess it is O(n) and O(1). Am I right?

Comment hidden because of low score. Click to expand.
0

This is not O(1) as the array of size max1/max2 will be dependent on the arrays

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

How about finding the product of all elments in each array keeping thecount of 0 in a and b and then performing an ^ on the results.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.