Compare two trees to see if they are structurally identical

Q. Compare two binary trees to see if they are structurally identical

Solution:-

boolean identicalTree(Node a, Node b) {
if (a==null && b==null) return(true);
else if (a!=null && b!=null) {
return(
a.data == b.data &&
sameTree(a.left, b.left) &&
sameTree(a.right, b.right)
);
}
else return(false);
}

This is done in O(n) time complexity.

Merging two sorted arrays

Q.Write a method that will take two sorted arrays as input and merge them and give a new sorted array as output.

Soln:- Take the two arrays straight go to the ends (I assume you consider checks for boundary conditions) cause in this approach you also handle the case that you are not allowed to use extra space with the condition that one of the array has extra space left to accommodate the other.
Start from the tail picking and comparing each element and putting the largest among them to the tail of new array. Decrement the index of the array of which a value is put in the new array. Repeat until all elements are traversed.

Code:

int[] MergeSortedArrays(int[] array1, int[] array2)
{
int indexArray1 = array1.length - 1;
int indexarray2 = array2.length - 1;


if(array1 == null || array1.length == 0)
return array2;
else if(array2 == null || array2.length == 0)
return array1;

int[] mergedArray = new int[array1.length + array2.length];


for(int indexDestination = indexArray1 + indexarray2 + 1;indexDestination>=0;indexDestination--)
{
if(array1[idexArray1] > array2[indexarray2])
{
mergedArray[indexDestination] =array1[indexArray1];
idexArray1--;
}
else
{
mergedArray[indexDestination] = array2[indexarray2];
indexarray2--;
}
}

return mergedArray;
}

Time complexity of this algorithm would be O(n) where n is the sum total of number of elements in both the arrays, with extra space complexity of O(n) which actually is the requirement

Number with odd number of occurrence - Amazon

Q. Given an array containing positive integers, all the integers occur even number of times except one. Find this integer occurring odd number of times.

Solution: Sort the array and run a linear search with a counter incrementing on each iteration. On encountering a new number see if the counter value is odd or even. If odd the previous number is the result. Other wise reset the counter. repeat until result is achieved.

To sort O(lg(n)) * search for all --> O(n(lg(n)).

Solution 2:
An XOR operation on a number with itself will nullify it. So as all the numbers except one occurs even number of times. Everything will be 0 except for the number itself. So XOR operation in a loop will get you the answer.

The time complexity will be O(n) here.