Amazon Interview Question for Software Engineer / Developers


Country: India




Comment hidden because of low score. Click to expand.
10
of 12 vote

Assumption: All numbers are distinct (otherwise, you need to tell us about the BST insertion algorithm).

One solution (but essentially same as the tree compare solution in spirit): you can do something like quicksort:

Given Arrays A and B, check if A[0] = B[0] (if not, return false).

Now construct A_more, A_less and B_more, B_less where A_more contains elements of A which are > A[0] (and appear in the same order as they appear in A). This is basically the partition step in quicksort. Note that you need the partition to be stable. It is possible to do that in-place, but is very complex.

Now, recursively compare A_more, B_more and compare A_less and B_less. You can add optimizations to compare lengths of arrays to bail out quicker.

- Loler June 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

quick sort works .. but there is a catch ..
For the first time, we take first element as pivot from both arrays and divided the arrays..
For the 2nd iteration onwards, we have to take the same element as pivot in both arrays .. this needs O(n) time or we have to do some kind of pre-processing ...

Second approach is not accepted as it was stated in the question itself that we should give answer without constructing BSTs.

- bharat June 03, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

@Bharath: The catch is that you need a stable partition: The relative ordering of elements must not change. Once you do that, you can do recursively, by comparing the first elements of the two partitions you get. You don't have to do any other preprocessing.

If you actually look to take the same element as pivot (as you seem to suggest), then you will get wrong answers, counterexample:

1 2 3
1 3 2

- Loler June 03, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

How about using O(n) extra space to do partition in-place? Let quicksort's partition algorithm decide the correct position of an element only (Create a backup of original array before passing it to partition algorithm, then use it to partition stably).
Time complexity would be O(nlogn) which is same as original algorithm and space complexity would be O(n).

- Epic_coder June 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Epic_coder: Then by definition it is not in-place. The point of an in-place algorithm is to save space...

- Loler June 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Very nice idea with partitioning, I was thinking about recursive check for left and right children, but qsort partitioning will do the work

- Tim1 June 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice logic! Here is the working python code using quicksort:

A = [2,3,1,4,5,6,7,8]
B = [2,1,3,8,7,6,5,4]

def find_if_equal(X,Y):
    if ((len(X) != len(Y)) or (X[0]!=Y[0])):
        return False
    else:
        if(len(X) == 1): return True
        Amin = [x for x in X[1:] if x<=X[0]]
        Amax = [x for x in X[1:] if x>X[0]]
        Bmin = [y for y in Y[1:] if y<=Y[0]]
        Bmax = [y for y in Y[1:] if y>Y[0]]
        
        if(Amin):
            if(Bmin.count(Amin[0]) == 0): return False
            if(len(Bmin)>1 and Amin[0]!= Bmin[0]):
                i = Bmin.index(Amin[0]) 
		Bmin[0],Bmin[i] = Bmin[i],Bmin[0]
            if (not find_if_equal(Amin,Bmin)): return False
        if(Amax):
            if(Bmax.count(Amax[0]) == 0): return False
            if((len(Bmax)>1) and (Amax[0]!=Bmax[0])):
                i = Bmax.index(Amax[0])
                Bmax[0],Bmax[i] = Bmax[i],Bmax[0] 
            if (not find_if_equal(Amax,Bmax)): return False

        return True

if (find_if_equal(A,B)):
    print("Two arrays A:{} and B:{} will make identical Binary Search Trees".format(A,B))
else:
    print("Two arrays A:{} and B:{} will not make identical BST's".format(A,B))

- bluepulse5577 September 21, 2015 | Flag
Comment hidden because of low score. Click to expand.
3
of 5 vote

I *think* this should work. When we're inserting any given key, it is always 'perfectly' inserted, that is it is inserted right after the maximum key that is still less than this key.
Given that, we can go through the array and for each value from each array see if we've already inserted it in the other array, and if so if the insertion point is still the same. If not, we know that we would produce two different trees. If so, then we keep looking.

Right now I'm not checking to make sure that both trees contain the same elements, but that should be easy to add.

Also right now the findInsertAfter method does a brute-force search which makes the algorithm n^2, but if you replace that with a sorted data structure and binary search for the optimal element it should be n*log(n).

static boolean willMakeSame(int [] arr1, int [] arr2)
	{
		if(arr1.length != arr2.length || arr1[0] != arr2[0])
			return false;
		
//		int maxSoFar = arr1[0];
//		int minSofar = arr2[0];
//		
		Map <Integer, Integer> insertedAt = new HashMap<>();
		
		for(int at = 0; at < arr1.length; at++)
		{
			if(!insertedAt.containsKey(arr1[at]))
			{
				int insertAfter = findInsertAfter(insertedAt.keySet(), arr1[at]);
				insertedAt.put(arr1[at], insertAfter);
			}
			else
			{
				int insertAfter = findInsertAfter(insertedAt.keySet(), arr1[at]);
				if(insertAfter != insertedAt.get(arr1[at]))
				{
					if(PRINT)
						System.out.println("For arr1 " + at + ", " + arr2[at] + " NOT correctly inserted after " + insertAfter);
					return false;
				}
				else if (PRINT)
					System.out.println("For arr1 " + at + ", " + arr2[at] + " correctly inserted after " + insertAfter);
			}
			if(!insertedAt.containsKey(arr2[at]))
			{
				int insertAfter = findInsertAfter(insertedAt.keySet(), arr2[at]);
				insertedAt.put(arr2[at], insertAfter);
			}
			else
			{
				int insertAfter = findInsertAfter(insertedAt.keySet(), arr2[at]);
				if(insertAfter != insertedAt.get(arr2[at]))
				{
					if(PRINT)
						System.out.println("For arr2 " + at + ", " + arr2[at] + " NOT correctly inserted after " + insertAfter);
					return false;				
				}
				else if(PRINT)
					System.out.println("For arr2 " + at + ", " + arr2[at] + " correctly inserted after " + insertAfter);
			}
		}
		return true;
	}

	private static  int findInsertAfter(Set<Integer> keySet, int i) {
		int maxThatIsSmaller = -1;
		for(int item : keySet)
		{
			if(item > maxThatIsSmaller && item < i)
			{
				maxThatIsSmaller = item;
			}
		}
		return maxThatIsSmaller;
	}

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

Could you please explain what you are trying to do, in English?

I think an O(nlog n) algorithm will exist, but I haven't thought about it fully. Perhaps you have one.

- Loler June 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

The basic idea is that when we're adding to a BST, a node is always added after the next-largest key. So if a given BST contains the values 1,2,3, then the value 4 will be added to the right of 3 no matter what the tree's shape.

So we can verify whether two trees are the same by checking for every value that its next-smallest value is the same as in the other tree.

There was a bug in my code, the corrected version is below:
"""
static boolean willMakeSame(int [] arr1, int [] arr2)
{
if(arr1.length != arr2.length || arr1[0] != arr2[0])
return false;

Map <Integer, Integer> insertedAt = new HashMap<>();
Set <Integer> insertedSetA = new HashSet <>();
Set <Integer> insertedSetB = new HashSet <>();

for(int at = 0; at < arr1.length; at++)
{
if(!insertedAt.containsKey(arr1[at]))
{
int insertAfter = findInsertAfter(insertedSetA, arr1[at]);
insertedAt.put(arr1[at], insertAfter);
}
else
{
int insertAfter = findInsertAfter(insertedSetA, arr1[at]);
if(insertAfter != insertedAt.get(arr1[at]))
{
return false;
}
}
if(!insertedAt.containsKey(arr2[at]))
{
int insertAfter = findInsertAfter(insertedSetB, arr2[at]);
insertedAt.put(arr2[at], insertAfter);
}
else
{
int insertAfter = findInsertAfter(insertedSetB, arr2[at]);
if(insertAfter != insertedAt.get(arr2[at]))
{
return false;
}
}
insertedSetA.add(arr1[at]);
insertedSetB.add(arr2[at]);
}
return true;
}

private static int findInsertAfter(Set<Integer> keySet, int i) {
int maxThatIsSmaller = -1;
for(int item : keySet)
{
if(item > maxThatIsSmaller && item < i)
{
maxThatIsSmaller = item;
}
}
return maxThatIsSmaller;
}
"""

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

Actually, the assumption that next highest will be the right child is valid only for the root.

For instance consider

2 1 3

2 3 1

both these give the same tree, but I believe your algorithm will say no.

- Loler June 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Actually it works, since for 1 the next-smallest in both cases is none and for 3 the next-smallest in both cases is 2.

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

It works, since 2 follows 1 in both cases and 3 follows 2. Code including some test cases is up here: shrib.com/5ULdxAua

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

I had to modify your code to run it (probably java version assumptions). I gave it a test input where I thought it might fail, but it didnt!

So, now I am not sure what your algorithm is.

What exactly is next-smallest? Can you please define it and give a couple of examples?

Thanks.

EDIT: This is a failing test case

// Comment to prevent formatting problems.
			int [] arr1 = {8, 7, 9};
			int [] arr2 = {8, 10, 7};		
			System.out.println(willMakeSame(arr1, arr2));

prints true, instead of false.

- Loler June 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hello loler, as I mentioned in my original post right now it doesn't check that both have the same elements, but a simple set comparison will take care of that (I've already got both items in sets, so just check whether they completely overlap).

The next-smallest is the largest item currently in the array that is still smaller than the item we're trying to insert. So when inserting 5 into 1,2,4, the next-smallest is 4.
If we were inserting 3, the next-smallest would be 2. For 0, the next-smallest is none.
When you insert into a BST, the element always gets inserted after the next-smallest unless that space is already filled. However, if that space is already filled, then the algorithm will detect the error for the node that filled the space in one tree and not in the other.

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

For the record, this should fix the test case you mentioned:

if(!insertedSetA.equals(insertedSetB))
	return false;

Just stick it right before the return true.

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

Ok, I had misunderstood you earlier. This works, and guaranteed O(nlog n). Good job!

I believe I have a proof, brief attempt below:

Given a permutation P of 1,2,3...,n, Call the signature S_P of P, the function f which maps {1,2,...,n} to {0,1,2..., n-1} such that f(k) = next-smallest according to your definition (replacing None by 0).

The claim is that two permutations P1 (a1,a2, ..,an) and P2 (b1,b2, ...,bn) give rise to the same binary tree if and only if S_P1 is identical to S_P2.

Assume S_P1 = S_P2

First we show that the first element of P1 and P2 must be same. Suppose b1 = aj for some j > 1. Then since S_P2(aj) = 0, we must have that a1 > a_j. So we must have that S_P1(a1) = 0 but S_P2(a1) >= aj as a1 appears after aj in P2.

Now we can parittion and show for the subtrees.

DIdn't try proving the other way.

- Loler June 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
3
of 5 vote

coders-stop.blogspot.in/2012/03/compare-bsts.html

- Anonymus June 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

does not work for case

8 14 11 9 13 20 16 22
8 14 20 22 16 11 13 9

- blackfever September 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@blackfever:
the bsts formed with the sequences u gave are not same, try to represent them in the form of tree based on order.

- KC March 01, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 4 vote

What does "making bst from array" mean? More details!

- Anonymous June 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Take first element as root and insert from then onwards in BST...
Ex:
A1[]={2,1,3}
2
1 3

A2[]={2,3,1}
2
1 3

- bharat June 03, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

@Bharat: Then don't 1,2,3 and 1,3,2 give different trees?

- Loler June 03, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Bharath: Why don't you edit the question to also add what make BST from array means?

- Loler June 03, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Simple solution (few assumptions made, obviously as question is quite vague):

Input: 2 int arrays
Output: boolean - whether BST constructed from either array will be same

Idea:
- first element has to be equal
- loop till the end of array
- if there is 1 more element left in both arrays, they have to be equal
- advance 1 place
- if there are 2 more elements in the array, they have to be equal when sorted
- if swapped around, each must be on either side of the first element (i.e root of the BST)

public boolean equalBST(int [] A, int [] B) {
    if(A.length != B.length)
        return false;
    if(A[0] != B[0])
        return false;
    
    int root = A[0];
    
    for(int i = 1; i < A.length; i++) {
        if(A[i] == B[i])
            continue;
        else if(i < A.length - 1) {
            if(A[i] == B[i + 1] && A[i + 1] == B[i] && checkSides(A[i], B[i], root)) {
                i++;
                continue;
            }
        }
        return false; 
    }
    return true;
}

private boolean checkSides(int a, int b, int k) {
    if(a < k && b > k)
        return true;
    else if(b < k && a > k)
        return true;
    else
        return false;

}

- Rooney June 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{#include<stdio.h>
#include<stdlib.h>
#define size 20
int check(int a1[],int a2[],int l,int r)
{
if(r==-1) return 1;
if(a1[l]!=a2[l]) return 0;
if(l==r) return 1;
int b1[r-l+1],b2[r-l+1],b3[r-l+1],b4[r-l+1],k1=-1,k2=-1,k3=-1,k4=-1,i,pivot;
pivot=a1[l];
for(i=l+1;i<=r;i++)
{
if(pivot<a1[i])
b1[++k1]=a1[i];
else
b2[++k2]=a1[i];
if(pivot<a2[i])
b3[++k3]=a2[i];
else
b4[++k4]=a2[i];
}
if(k1==k3 && k2==k4 && check(b1,b3,0,k1) && check(b2,b4,0,k2))
return 1;
else return 0;
}
void main()
{
int a1[]={3,1,0,2,5,4,6};
int a2[]={3,5,6,1,2,4,-1};
int n=sizeof(a1)/sizeof(int);
printf("%d\n",check(a1,a2,0,n-1));
}}
Can we do like this? Here I used extra space. Everytime I am selecting a pivot and putting the elements less than pivot in first array and the elements greater than the pivot in the second array, and recursively checking these arrays.

- Anonymous June 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

and for in-place sorting this would work
#include<stdio.h>
void in_place(int a[],int n)
{
int save,i,j,k,pivot;
pivot=a[0];
for(i=1;i<n;i++)
{
if(a[i]<pivot)
{
save=a[i];
for(j=i;a[j]!=pivot;j--);
for(k=i-1;k>=j;k--)
a[k+1]=a[k];
a[j]=save;
}
}
}
void main()
{
int a[]={3,7,8,2,5,4,9,1,6,0};
int n=sizeof(a)/sizeof(int);
in_place(a,n);
int i;
for(i=0;i<n;i++)
printf("%d ",a[i]);
printf("\n");
}

- Anonymous June 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Idea is based on qsort-partitioning where order of elements is preserved and done *in place*.
As input function takes 2 arrays, applies partitioning on them and recursively processes each of 2 sub arrays.

public class CompareArraysAsBST {

    public static boolean areBSTEqual(final int[] a, final int[] b) {

        if (a == null || b == null) {
            return false;
        }

        return areBSTEqual(a, 0, a.length - 1, b, 0, b.length - 1);
    }

    /**
     * Returns true if 2 arrays are BST equal from index start to index end inclusive.
     */
    private static boolean areBSTEqual(final int[] firstArr, final int firstStart, final int firstEnd,
            final int[] secondArr, final int secondStart, final int secondEnd) {

        // indexes have to be always the same for both arrays
        if (firstStart != secondStart || firstEnd != secondEnd) {
            return false;
        }

        // if we are outside of the array then ok
        if (firstStart >= firstArr.length && secondStart >= secondArr.length) {
            return true;
        }

//if first indexes are bigger than end ones return true
         if (firstStart > firstEnd || secondStart > secondEnd) {
            return true;
        }


        // if first elements of the array are not the same then arrays are not BST same
        if (firstArr[firstStart] != secondArr[secondStart]) {
            return false;
        }

        int firstBorder = partition(firstArr, firstStart, firstEnd);
        int secondBorder = partition(secondArr, secondStart, secondEnd);

        // recursive invocation on 2 pieces of an array exclusive the first one (we checked it already)
        boolean areEqualLeft = areBSTEqual(firstArr, firstStart + 1, firstBorder - 1, secondArr, secondStart + 1,
                secondBorder - 1);
        boolean areEqualRight = areBSTEqual(firstArr, firstBorder, firstEnd, secondArr, secondBorder, secondEnd);

        return areEqualLeft && areEqualRight;
    }

    /**
     * Sorts an array in qsort way but elements' order is presumed.
     * Returns an index of the first element that is *bigger* than a[begin]
     */
    private static int partition(final int[] a, final int start, final int end) {

        // loop invariant: res is always pointing to the first element *bigger* than a[begin]
        int res = start + 1;
        for (int i = start + 1; i <= end; i++) {

            // if found an element that is less than a[begin] then circularly shift the sub array of elements
            // example: 4 1 3 5 8 2 7, res = 3 (a[res] = 5), i = 5 (a[i] = 2) -> shift the sub array {5 8 2} -> {2 5 8}
            // so that array becomes 4 1 3 2 5 8 7 and res = 6 (a[res] = 5)
            if (a[i] <= a[start]) {
                swapWithShift(a, res, i);
                ++res;
            }
        }

        return res;
    }

    private static void swapWithShift(final int[] a, final int start, final int end) {
        int tmp = a[end];
        for (int i = start; i <= end; i++) {
            int tmp2 = a[i];
            a[i] = tmp;
            tmp = tmp2;
        }
    }

    public static void main(final String[] args) {
        assertThat("", areBSTEqual(new int[] {2, 1, 3}, new int[] {2, 3, 1}), is(true));
        assertThat("", areBSTEqual(new int[] {5, 1, 3, 4, 8, 7, 6}, new int[] {5, 8, 1, 3, 7, 6, 4}), is(true));
        assertThat("", areBSTEqual(new int[] {3, 2, 3}, new int[] {2, 3, 1}), is(false));
        assertThat("", areBSTEqual(new int[] {2, 1, 3, 5}, new int[] {2, 3, 1}), is(false));
        assertThat("", areBSTEqual(new int[] {4, 2, 3, 1, 7}, new int[] {4, 2, 1, 3, 7}), is(true));
        assertThat("", areBSTEqual(new int[] {}, new int[] {}), is(true));
        assertThat("", areBSTEqual(null, null), is(false));
    }
}

- Tim1 June 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

For following test case, it is showing as false... but it should be true.
{8,2,0,4,1,3,6,5,7,14,11,9,13,20,16,22}
{8,14,20,22,16,11,13,9,2,4,6,7,5,3,0,1}

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

Thanks for pointing that out, I forgot to check the case when first indexes are bigger than last indexes, of course it should lead to TRUE

- Tim1 June 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

the algo i thought...i will call a fn with 2 arrays A and B with same length n say with min=INT_MIN and max=INT_MAX,index1=0,index2=0
1. now starting from index1 in A and index2 in B,find 1st element in both arrays greater than min and less than max.If no such element in both the arrays,return true...If such element is only in 1 array return false.let index of such element in array A is i1 and array B is i2. If both elements are not same return false
2. call the same fn twice
return
isSameBST(A,B,A[i1],max,i1+1,i2+1) &&
isSameBST(A,B,min,A[i1],i1+1,i2+1).

- Amit June 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

only recursion stack used and time complexity is o(n*height of BST)

- Amit June 20, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

#include<stdio.h>
#include<limits.h>
int myfn(int a[],int b[],int n,int i1,int i2,int min,int max)
{
    int j,k;
    for(j=i1;j<n;j++)
    if(a[j]>min && a[j]<max)
    break;
    for(k=i2;k<n;k++)
    if(b[k]>min && b[k]<max)
    break;
    if(j==n && k==n)
    return 1;
    if(((j==n)^(k==n)) || a[j]!=b[k])
    return 0;
    return myfn(a,b,n,j+1,k+1,a[j],max) && myfn(a,b,n,j+1,k+1,min,a[j]);
}
int isSameBST(int a[],int b[],int n)
{
    return myfn(a,b,n,0,0,INT_MIN,INT_MAX);
}
int main()
{
    //int a[]={8,3,6,1,4,7,10,14,13},b[]={8,10,14,6,3,4,1,7,13};
    int a[]={1},b[]={2};
    int n=sizeof(a)/sizeof(a[0]);
    printf("%s\n",isSameBST(a,b,n)?"BSTs are same":"BSTs not same");
    return 0;
}

- Amit June 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

My solutions in C++:

#include <iostream>
#include <vector>

using namespace std;

/* Recursive version */
int sameBST(vector<int> A, vector<int> B) {
    if (A.size() != B.size())
        return 0;
    if (A.size() == 0)
        return 1;
    if (A[0] != B[0])
        return 0;
    vector<int> Ainf, Asup, Binf, Bsup;
    for (int i = 1; i < A.size(); ++i) {
        if (A[i] <= A[0])
            Ainf.push_back(A[i]);
        else
            Asup.push_back(A[i]);
        if (B[i] <= A[0])
            Binf.push_back(B[i]);
        else
            Bsup.push_back(B[i]);
    }
    return sameBST(Ainf, Binf) && sameBST(Asup, Bsup);
}

void swap(vector<int>& L, int i, int j) {
    int tmp = L[i];
    L[i] = L[j];
    L[j] = tmp;
}

/* Partitioning version */
int sameBST(vector<int>& A, vector<int>& B, int Astart = 0, int Bstart = 0, int Aend = -1, int Bend = -1) {
    if (Aend == -1)
        Aend = A.size() - 1;
    if (Bend == -1)
        Bend = B.size() - 1;
    if (Bend - Bstart != Aend - Astart)
        return 0;
    int length = Aend - Astart + 1;
    if (length == 0)
        return 1;
    if (A[Astart] != B[Bstart])
        return 0;
    int cntAinf = 0, cntBinf = 0;
    for (int i = 1; i < length; ++i) {
        if (A[Astart + i] <= A[Astart]) {
            swap(A, Astart + i, Astart + cntAinf + 1);
            ++cntAinf;
        }
        if (B[Bstart + i] <= A[Astart]) {
            swap(B, Bstart + i, Bstart + cntBinf + 1);
            ++cntBinf;
        }
    }
    return sameBST(A, B, Astart + 1, Bstart + 1,
                   Astart + cntAinf, Bstart + cntBinf)
            &&
           sameBST(A, B, Astart + cntAinf + 1, Bstart + cntBinf + 1,
                   Aend, Bend);
}

- Thomas February 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

"A1[]={2,1,3}
2
1 3

A2[]={2,3,1}
2
1 3"

How are these really the same? Depending on the rules, the second number could always be the left parent and the third number could be the right parent. According to my rules, it would be

2
1 3

2
3 1

Totally different.

- Johnb February 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It's a binary search tree. The left child is always smaller, and the right child is always larger.

- Kalel June 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public boolean isIdenticalBST(int[] A, int[]B) {
	    return checkIdenticalBST(A, 0, B, 0, Integer.MIN_VALUE, Integer.MAX_VALUE);
	}

	// helper function to check if elements of array A from aPos index and elements of array B from bPos index 
	// which are in the range between min and max can create identical BST 
	private boolean checkIdenticalBST(int[] A, int aPos, int[] B, int bPos, int min, int max) {
		if (aPos == -1 && bPos == -1) {
			return true;
		}
		if (aPos == -1 || bPos == -1) {
			return false;
		}
		// check value of the first element
		if (A[aPos] != B[bPos]) {
	        return false;
	    }
		// then check the subset of smaller elements then greater elements
		return checkIdenticalBST(A, findFirstInRange(A, aPos + 1, min, A[aPos]), 
							   B, findFirstInRange(B, bPos + 1, min, A[aPos]), 
							   min, A[aPos]) 
			   && 
			   checkIdenticalBST(A, findFirstInRange(A, aPos + 1, A[aPos], max), 
							   B, findFirstInRange(B, bPos + 1, A[aPos], max), 
							   A[aPos], max);
	}

	// find first index of element that between min and max, if not found return -1
	private int findFirstInRange(int[] arr, int pos, int min, int max) {
		while (pos < arr.length) {
			if (arr[pos] > min && arr[pos] < max) {
				return pos;
			}
			pos++;
		}
		return -1;	
	}

- Pat September 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Please share feedback on this approach
1. Check length of both the arrays.
1. if both are of equal length, sort them (we can do it in lg n) and then compare each element. If we find a mismatch, then both BSTs are not identical.

- lokesh.motwani.cse November 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Please share feedback on this approach
1. Check length of both the arrays.
1. if both are of equal length, sort them (we can do it in lg n) and then compare each element. If we find a mismatch, then both BSTs are not identical.

- lokesh.motwani.cse November 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

a O(n) time and O(n) space algorithm

typedef std::pair<int, int> PosPair;
typedef std::queue<PosPair> PosPairQueue;

bool check(int a[], int b[], int size) {
  if (size == 0) {
    return true;
  }
  PosPairQueue q;
  q.enqueue(0,0);
  while (!q.empty()) {
    PosPair pp = q.dequeue();
    if ((pp.first == -1 && pp.second != -1) ||
        a[pp.first] != b[pp.second]) {
      return false;
    }

    if (pp.first == -1 && pp.second == -1) {
       continue;
    }
  
    int posGreaterThanA = -1;
    int posLessThanA = -1;
    for (int i = pp.first + 1; 
          i<size && (posGreaterThanA == -1 || posLessThanA == -1); 
          ++i) {
      if (posGreaterThanA == -1 && a[i] > a[pp.first]) {
        posGreaterThanA = i;
      }
      if (posLessThanA == -1 && a[i] < a[pp.first]) {
        posLessThanA = i;
      }
    }

    int posGreaterThanB = -1;
    int posLessThanB = -1;
    for (int i = pp.second + 1; 
          i<size && (posGreaterThanB == -1 || posLessThanB == -1); 
          ++i) {
      if (posGreaterThanB == -1 && a[i] > a[pp.second]) {
        posGreaterThanB = i;
      }
      if (posLessThanB == -1 && a[i] < a[pp.second]) {
        posLessThanB = i;
      }
    }

    q.enqueue({posGreaterThanA, posGreaterThanB});
    q.enqueue({posLessThanA, posLessThanB});
  }
}

- zjzzjz November 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This doesn't use any additional data structure and uses recursion.

public class EqualBST {

	/**
	 * @param args
	 */
	static int[] a={7,9,10,5,2,7};
	static int[] b={7,5,9,10,7,2};
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		boolean isBST=compareBST(0,0);
		if (isBST)
			System.out.println("It is a BST");
		else
			System.out.println("Not a BST");
	}
	public static boolean compareBST(int i, int j){
		if(i >= a.length && j>=b.length){
			return true;
		}
		int k,l,left1 = 0,left2=0,right1=0,right2=0;
		for(k =i+1;k<a.length;k++){
			if(a[k]<a[i])
				left1=a[k];
		}
		for(l=j+1;l<b.length;l++){
			if(b[l]<b[j])
				left2=b[l];
		}
		if(left1 != left2) return false;
		if(compareBST(k,l)){
			for(k =i+1;k<a.length;k++){
				if(a[k]>a[i])
					right1=a[k];
			}
			for(l=j+1;l<b.length;l++){
				if(b[l]>b[j])
					right2=b[l];
			}
		}
		if(right1 != right2) return false;
		return(compareBST(k,l));
	}
}

- Mr.BST September 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

You could visualize subarrays of each array as a level in the tree. subarray[0] will be root. subarray[1, 2] will be first level subarray[3, 4, 5, 6] will be second level etc.

All you need to verify is that for a given subarray of the first array the corresponding subarray of the second is a valid rotation. Below is a python code.

def form_same_bst(arr1, arr2):
    if len(arr1) != len(arr2):
        return False
    n = len(arr1)
    i = 1
    while i < n:
        start = i-1
        end = 2*i - 1
        if not are_rotations(arr1[start:end], arr2[start:end]):
            return False
        i *= 2
    return True


def are_rotations(arr1, arr2):
    arr = arr1 * 2
    n = len(arr1)
    i = 0
    result = False
    while i < n and not result:
        result = True
        for j in range(n):
            if arr[i + j] != arr2[j]:
                result = False
                break
        i += 1
    return result

print(form_same_bst([2, 4, 3, 1, 5, 6, 7], [2, 3, 4, 5, 6, 7, 1]))

- lalat.nayak March 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This question can not be answered without knowledge of the BST construction algorithm. Since none is given I would devise my own: Sort the array, then construct the BST.
In that case, the problem is trivial. Two arrays have the same BST if they contain the same elements. This can be answered in O(n) time by using two hashmaps and intersecting them.

- Woot June 13, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

2 bsts would not be identical

- chandra June 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

2 bsts would not be identical

- chandra June 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

First Element and size of both array should be same.
All the element smaller than first element should be in same Order in both array.
Slly: all the element greater than first element should be in same Order in both array.

(Assuming : all different element in array
n1:- size of A1
n2:- size of A2
)

Boolean function(){
if((n1 != n2) && (A1[0] != A2[0]))
  return false;
int i=0,j=0;

while(i<n1 || j<n1){
  while(i<n1){
     if(A1[i]>A1[0])
        i++;
  }
  while(j<n1){
     if(A2[j]>A2[0])
        j++;
  }
  if(A1[i++] != A2[j++])
      return false;
}// end of while


i=0;j=0;

while(i<n1 || j<n1){
  while(i<n1){
     if(A1[i]<A1[0])
        i++;
  }
  while(j>n1){
     if(A2[j]>A2[0])
        j++;
  }
  if(A1[i++] != A2[j++])
      return false;
}// end of while

return true;
}// end of function

- niraj.nijju June 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

This will fail for

4 2 3 1 7

and

4 2 1 3 7

- Anonymous June 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 3 vote

1) check whether the size of both the arrays are equal.
2)if equal, then simply sort both arrays.
3)compare both the element in linear order.see a flag to track all the elements are equal are not.

- Jerry June 09, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Step may be useful between 1 and 2
1.1) find sum of both of the array... in case not same return FALSE else proceed with step 2.

- PKT June 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

dont think this will give correct answer. Once you sort both arrays, you have lost original order. Without the original order BST shape would be impossible to find and compare...

- shrikar June 14, 2013 | Flag
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

This approach gives false positives ..
Ex:
123, 132 --> don't form same BSTs but , sorted order is same....

- bharat June 04, 2013 | 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