CareerCup

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)

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

}
}

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

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
	}

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.

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

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.

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.

tries data structure

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.

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

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

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

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;

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 ?

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

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.

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;

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

}

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


}

}

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

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

}
}

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

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.

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.

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

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

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

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

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.

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

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

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

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.

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)

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.

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

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

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

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

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

if(sizeof(arr1)==sizeof(arr2)){
//yes, they are similar
}

Like this?