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)

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

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

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

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

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

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)

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

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)

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)

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

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

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

}
}

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

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

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

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

Add another condition, Multiply is the same.

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

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

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

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

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

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.

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

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

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

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

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

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

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.

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

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.

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

{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

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

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

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

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

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.

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

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

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

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.

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

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

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

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

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

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

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?

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

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

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.

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

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

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.

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

Salle tu hai kaun?

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

tries data structure

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.

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

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

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

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

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.

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

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>

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;

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

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.

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

how is this not hashing?

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 ?

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

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.

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

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

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

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

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

it is still O(n^2)

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;

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

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

}

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

}

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

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

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

}

}

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

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

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

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

}
}

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

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

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

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.

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

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.

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.

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

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

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

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
}

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

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

solution is o(n)
sry for bad english

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

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

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

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

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.

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

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

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

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.

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

In what way would a stack possibly help you?

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)

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

Binary search requires a sorted array.

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

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

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

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?

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

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

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.

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

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

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

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

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

bakhsala

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

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

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

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

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

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.