## Amazon Interview Question for Software Engineer / Developers

• 12

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 = B (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 (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.

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

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.

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

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

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

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

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

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

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

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

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!=Y)):
return False
else:
if(len(X) == 1): return True
Amin = [x for x in X[1:] if x<=X]
Amax = [x for x in X[1:] if x>X]
Bmin = [y for y in Y[1:] if y<=Y]
Bmax = [y for y in Y[1:] if y>Y]

if(Amin):
if(Bmin.count(Amin) == 0): return False
if(len(Bmin)>1 and Amin!= Bmin):
i = Bmin.index(Amin)
Bmin,Bmin[i] = Bmin[i],Bmin
if (not find_if_equal(Amin,Bmin)): return False
if(Amax):
if(Bmax.count(Amax) == 0): return False
if((len(Bmax)>1) and (Amax!=Bmax)):
i = Bmax.index(Amax)
Bmax,Bmax[i] = Bmax[i],Bmax
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))``````

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 != arr2)
return false;

//		int maxSoFar = arr1;
//		int minSofar = arr2;
//
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;
}``````

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

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.

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

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

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.

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

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.

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

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

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

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

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

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.

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

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.

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

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.

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

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

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

does not work for case

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

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

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

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

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

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

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

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

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

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

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

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
- 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 != B)
return false;

int root = A;

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

}

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.

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

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

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

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}

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

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

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

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

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

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

``````#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);
printf("%s\n",isSameBST(a,b,n)?"BSTs are same":"BSTs not same");
return 0;
}``````

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 != B)
return 0;
vector<int> Ainf, Asup, Binf, Bsup;
for (int i = 1; i < A.size(); ++i) {
if (A[i] <= A)
Ainf.push_back(A[i]);
else
Asup.push_back(A[i]);
if (B[i] <= A)
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);
}``````

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.

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

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

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

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.

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.

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

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

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

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.

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

2 bsts would not be identical

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

2 bsts would not be identical

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 != A2))
return false;
int i=0,j=0;

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

return true;
}// end of function``````

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

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.

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

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.

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

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

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

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

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.