Goldman Sachs Interview Question for Software Engineer / Developers


Country: India
Interview Type: In-Person




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

I think counting the occurrence of each element would be sufficient as the range of variation of numbers in the example is very small. So, counting separately for both the arrays and then matching the counts will be sufficient.

Total time O(n+h)

where h - range of variation of numbers in array.

expecting that h <<< O(n^2)

- prashant December 06, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I guess you basically propose to use hashing or counting sort ?
note that hashing and sorting are not allowed otherwise that would be too easy

- Anonymous December 06, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hey, counting is just half the procedure of counting sort and you do not require hash table compulsorily to store the number of counts.

- prashant December 06, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

then how the complexity comes to be O(n+h) it would be O(n*h), because you gonna calculate frequency of a number and then calculate frequency in another array, if they are equal, then you increment element then again do the same for this element also.
as you said that you are not storing the frequencies(as it is restricted), so your complexity goes to O(n*h) not O(n+h)

- sonesh November 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why not build a (balanced) BST such that its nodes are augmented by 2 fields? One field will maintain the count of the element from the first array and the other one will maintain the count of the element from the other array.

While building the tree, if a node is not present, insert it into the tree, otherwise update it's count fields depending on whether we are traversing the first array or the second one.

Once the tree is built, do an inorder traversal and check if the counts are equal. At any stage if the counts are unequal return false. Otherwise return true in the end. Time complexity to build the BST = O(nlgn). Inorder traversal requires O(n), hence overall complexity = O(nlgn)

- Murali Mohan June 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
3
of 3 vote

import java.util.ArrayList;


public class SameArray {
public static void main(String args[]){

int[] a= {1,2,3,5,5,4,7};
int[] b= {7,5,5,4,3,2,1};
ArrayList<Integer> t1=new ArrayList<Integer>();
if(a.length!=b.length)
{
System.out.println("Not same");
return;
}
for(int v : a)
t1.add(Integer.valueOf(v));

for(int v : b)
t1.remove(Integer.valueOf(v));

if(t1.isEmpty())
System.out.println( "same Array");

else
System.out.println("Not same");

}
}

- Anonymous May 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 4 vote

Are the 3 conditions below sufficient to affirm that the 2 arrays contain same number of elements equally ?
1. arr1.Length == arr2.Lentgh
2. XOR or all elements from both tables should be 0 (for each element in array1 there is a corresponding element in array2
3. SUM of all elements from array1 must be equal to the SUM of all elements from array2

- amustea November 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

No. [0, 1, 2, 3] vs. [1, 1, 2, 2].

- Anonymous November 22, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Add another condition, Multiply is the same.

- Anonymous November 23, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

[0,0,3,3] vs [1,1,2,2]

- Anonymous November 23, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think that is wrong condn.

[0,0,0,3,3] vs [0,1,1,2,2]

both multiple, sum and xor is equal..... but they are not similar...

- Wayne November 24, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

ok, folks, all your counterexamples contain zero element.
Do get rid of it, we can first count the # of zeros in each array,
if they are not equal, we are done.

If yes, we proceed with xor/add/mul tests as above where zero elements are not taken into account.

- pavel.em November 28, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think it's not even needed to get rid of zero elements.
To check if two arrays are permutations of one another, we do the following steps:

1. find & compare min/max for arrays (if not equal we are done)
2. compare the sums: a[1]+...+a[n] and b[1]+...+b[n]
3. compare the sums of squares: a[1]^2+...+a[n]^2 and b[1]^2+...+b[n]^2

if all three conditions are fulfilled, the arrays are permutations
I'd appreciate if someone could find a counterexample

- 111 November 28, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It's not enough. check [-1, 0, 3, 3, 5] and [-1, 1, 1, 4, 5] please.
1. min/max is -1/5 and -1/5, ok
2. sum is 10 and 10, ok
3. sum of squares is 44 and 44, ok
but they are not similar.

essentially, if there are N elements in a array, we should check the sums of power( i, N) for i in array

- jingtianjiang November 29, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

thanks @jingtianjiang, good point
well, computing \sum a[i]^n would certainly be an overkill. Yet perhaps this is a right direction to the solution.. Additionally, if you combine the above idea with xor test, it'd be quite hard to break

- pavel.em November 29, 2011 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

I think the solution you're probably looking for that's in this spirit is to map each number N to the N-th prime number and multiply them all together.

so {2, 5, 1} would become second prime * fifth prime * first prime = 3 * 11 * 2 = 66

This would equal what you'd get with {1, 5, 2} for obvious reasons. Because of the fundamental theorem of arithmetic (every number has a unique factorization into primes), the product you get is actually a signature unique to the array you inspected.

Of course, you'd have to use something like BigInteger because a regular int or long would overflow very, very quickly for this solution. And this solution would sure get slow. You'd need something like FFT to even get N*(logN)^2.

It's possible to come up with very simple and fast randomized algorithms for this problem, too, that can get the answer right with very, very high probability in something like O(N logN) time.

- eugene.yarovoi December 12, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

For each element i in the array, calculate 2^i and then do the sum. If total is same for both arrays, two arrays are same.

- It March 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

{0,0,3} and {1,2,2} is counter example.

However, these condition may provide solution :-
1) length of array is same
2) sum of both array is same
3) sum of 2^i for both array is same

- Harshit May 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The sum of 2^i is a very large number...it would take an awful lot of space to represent that. If you're going to do that, you might as well use a bitset...

- Anonymous May 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

static boolean isSimilar(int[] arr1, int[] arr2) {
Map<Integer, Integer> m = new HashMap<Integer, Integer>(); // O(1) lookups

if (arr1.length != arr2.length)
return false;

// O(n)
int max = arr1.length;
for (int i : arr1) {
// O(1)
if (m.containsKey(i)) {
Integer j = m.get(i);
j++;
m.put(i, j);
} else {
m.put(new Integer(i), 1);
}
}

// O(n)
for (int i : arr2) {
// O(1)
if (m.containsKey(i)) {
Integer j = m.get(i);
j--;
m.put(i, j);
} else {
m.put(new Integer(i), 1);
}
}

// break if any counts are not zero
for (Integer i : m.values())
if (i.intValue() != 0)
return false;

return true;
}

- Gravometer September 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

foreach i:int in arr1
 foreach j:int in arr2
  {
    if(i == j)
     j = -1;
  }

take each element from arr1 compare it with elements from arr2. if the element is found mark that element with a -1. if at the end all elements in arr2 are -1 and we have exhausted arr1, then they are similar.
O(n^2) because of no sorting and hashings.

- Anonymous November 23, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Make a copy of two arrays, ArrayA, ArrayB

1. Compare array length, if not equal return -1.

2. for (i=1; i<len(ArrayA); i++) {
for (j=1; j<len(ArrayB): j++)
if(Array B[j].equals("YES")
continue;
else if ArrayA[i]==ArrayB[j]
{ ArrayA[i]="YES";
ArrayB[j]="YES";}
else return -1;
}

- XM December 02, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I would consider these solutions to be probably invalid because the reason the constraint to avoid sorting is probably being given is because O(N) extra space is too much.

- eugene.yarovoi December 12, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

that would be N^2 right ? which is the trivial solution

- orhancanceylan June 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

If we are allowed to use extra memory in that case we can create BST from both arrays and can check whether both BSTs are same or not..For this purpose we need O(n) extra memory n complexity will be O(nlogn).

- Anshul November 26, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

not sure if this works: there are many ways to construct a BST from an array. Then, it is unclear how to check if two BSTs essentially represent the same permuted arrays.
if you do in-order traversals of both trees, then I guess it'd be the same as sorting..

- Anonymous November 28, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

What if we insert all elements of first array into a binary search tree, then delete the elements of the second array from the binary search tree. If we don't find an element of second array to delete, then the first is not permutation of other otherwise both are same.

Will this work?

- Nani November 29, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

one more thing we could do, add an extra field in a node which will contain frequency , then first create bst with 1'st array and increase the frequency of elements by one .Now scan the 2'nd array and
search in bst one by one if element is found then increase the frequency.Now at last check that the frequency of each element of bst is same or not..

- Aalok June 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

if hashing is not allowed, how about hashmap like solution?

I assume:
changing array is allowed
and there are no duplicate elements allowed in input. (if allowed, algorithm is little tricky)

say, the given array's are
{p1, p2, p3, p4}
{p3, p2, p4, p1}

We need to confirm whether one array is permutation of another array.

1. take one element from 1st array and hash it to generate a value in the range 1-4 (array size)
2. say for p1 we got 3.
3. goto array index 3, put p1 in 3 and take p3 as current element now.
repeat until all elements are processed.

Say, after this process we got 1st array as
{p2, p3, p1, p4}

Now process second array as follows
1. take one element from 2nd array (say p3) and compute hash. as the same hash function is used p3 maps to index 1.
we goto index 1 in 1st array and see if the value is same or not if yes, we have a match. and continue with the next element. if not then the arrays is not same and we can quit.

NOTE: if the arrays have same elements then matching is tricky because we might have to put the element in next position and the worst case is if all the elements are same.

- Krishna November 27, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

small correction: p3 will map to 2. p2 will map to 1 and so on.

- Somisetty November 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

There is an extremely inefficient way using prime numbers.

Let P(i) be the ith prime.
Then calculate PA = Prod(P(i) for i in A), and PB = Prod(P(i) for i in B).
Now arrays A and B are similar if and only if PA == PB.

- dev.cpu November 27, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Salle tu hai kaun?

- Balwant October 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

tries data structure

- skn November 29, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I guess what interviewer was hinting at is that looking at those two array we can see that they lie in range 0 - 5. SO, use a counting sort.

- Anonymous November 29, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

Make a copy of two arrays, ArrayA, ArrayB

1. Compare array length, if not equal return -1.

2. for (i=1; i<len(ArrayA); i++) {
for (j=1; j<len(ArrayB): j++)
if(Array B[j].equals("YES")
continue;
else if ArrayA[i]==ArrayB[j]
{ ArrayA[i]="YES";
ArrayB[j]="YES";}
else return -1;
}

- xz2210 December 02, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

oh gosh, you think we are so stupid and could not come up with such a solution ?

The point is make it running in O(n) time since sorting is not allowed

- Anonymous December 04, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

However, it not required to be O(n). And have you come up with a good O(n) solution now? I will be pleased to see.

- xz2210 December 04, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think If I take the cross product of the vector they should be equal to zero .. isnt it ? for two same n dimension vector

- Anonymous December 03, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

<pre lang="" line="1" title="CodeMonkey94996" class="run-this">package com.test;
class N{
public static void main(String rt[]){
int[] arr1={3,5,2,2,5};
int[] arr2={5,2,5,2,3};
if(arr1.length==arr2.length){
for(int p=0;p<arr1.length;p++){
if(getFlag(arr1,arr1[p])!=getFlag(arr2,arr1[p])){
System.out.println("not equal");
break;
}else{
if(p==arr1.length-1){
System.out.println(" equal");
}
}
}
}else{
System.out.println("not equal");
}
}
public static int getFlag(int[] arr, int comparVal){
int flag=0;
for(int a:arr){
flag=(comparVal==a)?flag:flag+1;
}
return flag;
}
}</pre><pre title="CodeMonkey94996" input="yes">
</pre>

- Anonymous December 05, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

because size of the elements is not large then we can solve it using O(n) space and O(n) time complexity.

initialize A[max] to -1;

for i=0 to n
A[arr1[ i ] ] = 1;


// now search for -1 using index as arr2[i]
for(i=0 to n)
{
if(A[arr2[ i ] ] == -1)
{
printf("\narray not same.\n");
}
}

we can optimize additional array like A[ (arr[i] - min) ] =1;

- atul.87friend January 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think this is not a full-proof solution. You solution will infer 'Same array' in following case.
arr1: 2, 5, 2, 3, 5
arr2: 2, 2, 2, 5, 3

You need to add one more check.

- Manish February 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

how is this not hashing?

- piccu May 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about creating BST for both the array's. Thus, doing an inorder iteration will give you elements in sorted order. Is that allowed or is that considered sorting ?

- Gautam January 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1.]We need to use two boolean arrays need to set them true if elements we compare in arry1 and arry2 is equal and go thru each boolean array if single false is ther then given arry1 and arry2 are not equal.

2.]works for duplicate numbers
3.]performance O(n^2)

public static boolean arrayEqual(int[] arry1,int[] arry2)
	{
		//First Condition compare array lengths
		if(arry1.length!=arry2.length)
		{
			return false;
		}
			else
		{
				//We require two boolean arrays to trace similar elements
				boolean[] temp1 = new boolean[arry1.length];
				boolean[] temp2 = new boolean[arry2.length];
		
				//Normal Comparision  
			for(int i=0;i<=arry1.length-1;i++)
			{
				
				for(int j=0;j<=arry2.length-1;j++)
				{
					//no need to compare with element already found ;
					//required if arry1 has 2,2 and arry2 as 2 we will get false
					if(temp2[j])
					{
						continue;
					}
					else if(arry1[i]==arry2[j])
					{
						//elements position which are similar
						temp1[i]=true;
						temp2[j]=true;
						break;
					}
				}
			}
			//go thru each boolean array if found false arry1 and arry2 are not equal
			System.out.println("position of arry1 elements not common");
			for(boolean a:temp1)
			{
				System.out.println(a);
				if(!a)
					return false;
			}
			System.out.println("position of arry2 elements not common");
			for(boolean a:temp2)
			{
				System.out.println(a);
				if(!a)
					return false;
			}
		}
		System.out.println("final verdict arrays are equal ? ");
		return true;
		}

- spd January 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

Best Solution:-

For each unique element in the array set unique prime numbers into them.
Like if arr[1] = 10,20,20,50,60 and arr[2] = 50,20,60,10,20...
Then arr[1] = 2,3,3,5,7 and arr[2] = 5,3,7,2,3.
Then multiply the two arrays. If the product is same, then the arrays are similar...

This method is Anagram Finding method.
This will work and in amazingly less complexity.

- Sagnik Majumder January 31, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This method doesn't seem different from hashing where you hash each array value to prime number otherwise how would you keep track of unique prime numbers and same prime number for same array numbers

- virat February 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The complexity of this is really not very low...

- Anonymous June 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

it is still O(n^2)

- Anonymous July 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

l=strlen(arr1);
count=0;
for(i=0; i<l ; i++)
  for(j=0; j<l; j++)
    if(arr1[i]==arr2[j])
      {
      count++;
      arr2[j]=-1;  // don't re-count
      }
return count==l;

- MiKL~ February 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about this solution? Please comment,

import java.util.ArrayList;
import java.util.List;

public class ArrayCheck {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] a1 = { 3, 5, 2, 5, 2 };
		int[] a2 = { 2, 3, 5, 5, 2 };

		//int[] a1 = { 2 };
		//int[] a2 = { 2 };

		
		boolean equal = true;
		List<Element<Integer>> list = new ArrayList<Element<Integer>>();
		if (a1.length == a2.length) {
			for (int c = 0; c < a1.length; c++) {
				check(list, a1[c]);
				check(list, a2[c]);
			}

			for (Element<Integer> e : list) {
				if (e.getCount() % 2 != 0) {
					equal = false;
					break;
				}

			}
		}
		System.out.println(equal);
	}

	private static void check(List<Element<Integer>> list, int element) {
		Element<Integer> e = new Element<Integer>(element);
		int index = list.indexOf(e);
		if (index >= 0) {
			list.get(index).incr();
		} else {
			list.add(e);
		}
	}

}

class Element<T extends Number> {
	final T a;
	int count = 0;

	Element(T a) {
		this.a = a;
		incr();
	}

	public void incr() {
		++count;
	}

	public int getCount() {
		return count;
	}

	public T getNumber() {
		return a;
	}

	@SuppressWarnings("unchecked")
	@Override
	public boolean equals(Object obj) {

		if (obj != null
				&& !(obj.getClass().getName()
						.equals(getClass().getName()))) {
			return false;
		}
		Element<T> e = (Element<T>)obj;
		return( this.a == e.getNumber());
	}

	@Override
	public int hashCode() {
		return this.a.hashCode();
	}

}

- javalover February 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You'd get a lot more comments if you explained your solution rather than just writing code.

- Anonymous June 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class SecondArray {

public static void main(String[] args) {

int[] arr1 = { 3, 5, 2, 2, 5 };
int[] arr2 = { 5, 2, 5, 2, 3 };

int l = arr1.length;
int count = 0;
for (int i = 0; i < l; i++)
for (int j = 0; j < l; j++)
if (arr1[i] == arr2[j]) {
count++;
arr2[j] = -1; // don't re-count
}
if (count == l && l==arr2.length) {
System.out.println("Array's are same");
}else{
System.out.println("Array's are not same");
}


}

}

- Anil February 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//take sum of square of each element in both arrays and see if sum is equal or not

int[] a = {2, 3, 5, 3, 5};
        int[] b = {3, 2, 5, 5, 3};
        int sumA = 0, sumB = 0;

        for (int i = 0; i < a.length; i++) {
            sumA = sumA + a[i] * a[i];
            sumB = sumB + b[i] * b[i];
        }
        if (sumA == sumB) {
            System.out.println("`Arrays are equal");
        } else {
            System.out.println("Not Equal");
        }

- sumit February 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

From the pisagor thm; A:{3,4,10} and B:{6,8,5}

- orhancanceylan June 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hi I think following will work:
int A[Max]={0};
for(i=1; 1<n; i++)
{
A[arr1[i]]+=1; //add one for each entry
}
for (i=0; i<n; i++)
{
A[arr2[i]] -= 1; // decrease 1 for each entry
}
//if both the array contains same integer similar no of time the the net sum after addition and deletion will be zero in the array A[]
for(i=0;i<n;i++)
{
if(A[arr1[i]]!=0 || Arr2[i]!= 0)
{
print array no equal
return;
}
print arry equal

}
}

- Mukesh Kumar March 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

multiply 2 array first O(2n). The divide that result with square of each element from one array.
Now if both array are anagram of each other...then final result will come 1. Otherwise not,

....Please correct me if I am wrong

- soumyajuit March 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

u r wrong..
consider [1 1 6] and [1 2 3]

- jindal July 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

For each element i in the array, calculate 2^i and then do the sum. If total is same for both arrays, two arrays are same.

- Kt007 March 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

A = [2, 2, 2, 2, 1]
B = [-1, -1, -1, -1, 4]

The sum in the first = 18 = the sum of the second array. Therefore, doesn't work.

- stz October 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

For each element i in the array, calculate 2^i and then do the sum. If total is same for both arrays, two arrays are same.

- Kt March 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

should be:
DifSum += array1[i] - array2[i];
DifSqSum += array1[i] * array1[i] - array2[i]* array2[i];

- Jeff April 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool IsEqual(array1,array2){
int n = strlen(array1);
if (n ~= strlen(array2)) return false;
double DifSum, DifSqSum;
int i;
for(DifSum = 0, DifSqSum = 0, i = 0; i < n; ++i){
DifSum = array1[i] - array2[i];
DifSqSum = array1[i] * array1[i] - array2[i]* array2[i];
}

return DifSum == = & DifSqSum == 0;
}

- Jeff April 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public boolean isSimilarArrays(int aArr[], int bArr[]){
		int lenA = aArr.length;
		int lenB = bArr.length;
		if( lenA != lenB )
			return false;
		int result = 0,zeroA = 0,zeroB = 0;
		while( --lenA >= 0 ){						//	O(n) Solution
			if( aArr[lenA] == 0 ){					//	Count Zero's in A
				zeroA++;
				continue;
			}
			if( bArr[lenA] == 0 ){					//	Count Zero's in B
				zeroB++;
				continue;
			}
			result ^= aArr[lenA] ^ bArr[lenA];		//	XOR numbers so that replica can be confirmed
		}
		if( zeroA != zeroB )						//	if zeros match we are fine else boom wrong!!!
			return false;
		else
			return result == 0 ? true : false;		//	finally if XOR works 0 is the result else not similar
	}

- Prateek April 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

There are two arrays.

int arr1[5] = { 3, 5, 2, 5, 2}
int arr2[5] = { 2, 3, 5, 5, 2}

The arrays will be called similar if they contain same number of elements equally.

THE ITS SIMPLE  CALUCALTE THE SOME OF ELEMENTS OF arr1 let say sum1 and for arr2 it is sum2 
if(sum1==sum2)
       printf("equal");
else
       printf("not equal");

- Chandan Singh October 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

solution is o(n)
sry for bad english

- mrmastikhorchandan October 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

-1: The sum of two arrays could be the same without the arrays having the same elements. Consider {3, 5} and {4, 4}

- eugene.yarovoi October 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void compareArraysUsingSquares(int[]a,int[]b)
{
int length = a.length-1;
int reps = length/2;

System.out.println("REPS: "+reps);

if((length%2) != 0)
{
reps +=1;
}
int sum=0;

for(int i=0,j=(int)length;i<=reps;i++,j--)
{
int x1 = (a[i]*a[i]);
int x2 = (b[i]*b[i]);
int x3 = (a[j]*a[j]);
int x4 = (b[j]*b[j]);

int s1 = x1 - x2;
int s2 = x3 - x4;

System.out.println("a[i]->["+i+"]"+s1);
System.out.println("a[j]->"+j+"]"+s2);
sum += s1+s2;
System.out.println("sum is "+sum);
System.out.println("******************************");

}

System.out.println("sum is "+sum);
if(sum==0)
System.out.println("Arrays are similar");
else
System.out.println("arrays are not similar");
}

- Rahul October 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

check this link :
mycppexperiments.blogspot.in/2013/01/check-integer-array-permutations.html

- srinu.5019 March 13, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Table look-up, if space is not an issue. If space is an issue then even bit vector implementation won't work because it says you can have repeating elements.

- aalimian April 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

There is a problem called "finding anagrams" .. one ca use similar technique and O(N) solution with O(N) storage

- shashi kant August 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Arrays;
public class SimilarArrays {
    static int[] arr1 = { 3, 5, 2, 5, 2, 15}, arr2 = { 2, 3, 5, 5, 2, 15};
    public static void main(String[] args) {
        System.out.println(new Stats(arr1).equals(new Stats(arr2)));
    }
    //NB - assumes very bounded natural numbers
    static class Stats{
        int [] counter = new int[10];
        Stats(int [] arr){
            for(int i : arr){
                if (counter.length<=i){
                    counter = Arrays.copyOf(counter, i+1);
                }
                counter[i]++;
            }
        }
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            Stats stats = (Stats) o;
            if (!Arrays.equals(counter, stats.counter)) return false;
            return true;
        }
        @Override
        public int hashCode() {
            return counter != null ? Arrays.hashCode(counter) : 0;
        }
    }
}

- petko.ivanov September 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hi,

The following code should be sufficient to test the condition

#include <iostream>
using namespace std;

bool isPalindrome (int aArr[], int bArr[], int lenA, int lenB)
{
	int sumA=0, sumB=0, result=0;
	if(lenA == lenB)
	{
		while(--lenA >= 0)
		{
			sumA += aArr[lenA];
			sumB += bArr[lenA];
			result ^= aArr[lenA] ^ bArr[lenA];
		}
		if(sumA != sumB)
		return false;
	}
	else
		return false;
	cout<<sumA<<sumB<<endl;
	cout<<result<<endl;
	return result == 0 ? true:false;
}
int main() {
	int A[] = {10,20,20,50,60}, B[] = {50,20,60,20,10};
	int lenA = sizeof(A)/sizeof(int);
	int lenB = sizeof(B)/sizeof(int);
	// your code goes here
	isPalindrome(A,B,lenA,lenB)?cout<<"YES":cout<<"NO";
	return 0;
}

- AgentAlpha December 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Why not a stack, it works in O(NlogN)? I found it pretty easy using stack, for instance, for each element in a stack, binary search (O(logN)) it , if in the end the stack is non-empty then not similar, otherwise similar.

- pidig89 June 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

In what way would a stack possibly help you?

- Anonymous June 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

For each of the element in the first array do a binary search in the second. When you find an element in the second replace it with 0 or Int.Min value. If you dont find an element of the first array in the second return false. The complexity will be n Log(n)

- Srivathsan June 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Binary search requires a sorted array.

- Anonymous June 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Not necessary. recursively divide the arrays in half, then search in the left half if you dont find it search in the right half...

- Srivathsan June 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

That would be a bizarre, inefficient recursive implementation of a linear search, which is O(N). Isn't it clear that you need approx. N steps to search for an element in an unsorted array?

- Anonymous June 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Oh yeah.. you are right... sorry i cooked a bad soup......:(

- Srivathsan June 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Foreach element in a do a binary search in b. When you find an element in b replace it with 0 or Int.Minimum value. The binary search should always look in the left half first and then in the right half.

- Srivathsan June 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

For input:
int arr1[5] = { 3, 5, 2, 5, 2}
int arr2[5] = { 2, 3, 5, 5, 2}

They are the same if:
1) XOR all numbers in arr1 and arr2 is 0
2) Sum of all differences between arr1 and arr2 are 0. For example, 1+2+(-3)+0+0=0

- jiangok2006 August 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

what about using the XOr operator

a[]={2,4,2,3,5}
b[]={5,4,2,4,2}
//compare them to be of same length
int j=0;
if (a.length == b.length){
for (int i= 0;i<a.length; i++){
j=a[i]^b[i]^j;

}
}

//if the arrays are similar, j will be 0

- akshaya September 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Sum of ( difference of squares of each element ) == 0 => the arrays are same !

A[5] = [2 0 5 3]
B[5] = [5 2 3 0]

(4-25) + (0-4) +(25-9) + (9-0) = 0

- Anonymous October 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

There are two arrays.

int arr1[5] = { 3, 5, 2, 5, 2}
int arr2[5] = { 2, 3, 5, 5, 2}

The arrays will be called similar if they contain same number of elements equally.

THE ITS SIMPLE  CALUCALTE THE SOME OF ELEMENTS OF arr1 let say sum1 and for arr2 it is sum2 
if(sum1==sum2)
       printf("equal");
else
       printf("not equal");

- Chandan Singh October 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

bakhsala

- bhaksala January 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

Subtract or take difference of each element in the same index of the two arrays and finally sum up the subtacted values. For eg A1={1,2,3}, A2={3,1,2} the Diff={-2,1,1} now sum-up the Diff = 0 that means they have same set of integers. This approach requires an O(n) with no extra memory

- Anonymous December 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

That's just not valid. Consider {4, 1} and {2, 3}. The difference would be {2, -2}, the sum of which is 0. Clearly {4, 1} are not the same elements as {2, 3}.

- eugene.yarovoi December 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

public static int equibriumPoint(int a[]){
int i=0,j=a.length-1;
int sSum = 0, eSum = 0;
while(i<=j){
if(i==j && eSum==sSum) return i;
if(sSum > eSum){ eSum+=a[j]; j--;}
else if(sSum < eSum){ sSum+=a[i];i++; }
else {
eSum+=a[j];j--;
sSum+=a[i];i++;
}
}
return -1;
}

- Ravi September 06, 2012 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More