Interview Preparation

An element in a sorted array can be found in O(log n) time via binary search . But suppose we rotate an ascending order sorted array at some pivot unknown to you beforehand. So for instance, 1 2 3 4 5 might become 3 4 5 1 2. Devise a way to find an element in the rotated array in O(log n) time. Code: package microsoftInterviewPrep; public class SearchSortedRotatedArray {     static void pivotedBinarySearch(int[] a, int key){         int n = a.length -1;         int pivot = findPivot(a, 0, n);         if(a[pivot] == key)             System.out.println(pivot);         else if(key > a[0])             System.out.println(binarySearch(a, 0, pivot-1, key));         else             Syste...

Given an array A[] consisting 0s, 1s and 2s, write a function that sorts A[]. The functions should put all 0s first, then all 1s and all 2s in last. Examples: Input : {0, 1, 2, 0, 1, 2} Output : {0, 0, 1, 1, 2, 2} Input : {0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1} Output : {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2} Code: package microsoftInterviewPrep; import java.util.Arrays; public class SortArrayOf0_1_2 {         static void sortArray(int[] a){                 int low = 0, high = a.length-1, mid = 0;                 while( mid <= high){                         if(a[mid] == 0){                 int temp = a[low];               ...

Given a binary tree and a number, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals the given number. Return false if no such path can be found. For example, in the above tree root to leaf paths exist with following sums. 21 –> 10 – 8 – 3 23 –> 10 – 8 – 5 14 –> 10 – 2 – 2 So the returned value should be true only for numbers 21, 23 and 14. For any other number, returned value should be false. Code: package trees; public class N1906_SumRootToLeafPath {     Node root = null;     static class Node{         int data;         Node left, right;         Node(int data){             this.data = data;             left = right = null;         }     }  ...

Mirror of a Tree: Mirror of a Binary Tree T is another Binary Tree M(T) with left and right children of all non-leaf nodes interchanged. Code: package trees; public class N1804_MirrorTree {     Node root = null;     static void convertToMirror(Node node){         if(node == null){             return;         }         Node temp = node.left;         node.left = node.right;         node.right = temp;         convertToMirror(node.left);         convertToMirror(node.right);     }     static void printTree(Node node){         if(node == null)             return;        ...

Two trees are identical when they have same data and arrangement of data is also same. To identify if two trees are identical, we need to traverse both trees simultaneously, and while traversing we need to compare data and children of the trees. Code: package trees; class Node{     int data;     Node left, right;     Node(int data){         this.data = data;         right = left = null;     } } public class N1802_IdenticalTrees {     Node tree1 = null, tree2 = null;     boolean isIdentical(Node root1, Node root2){         if(root1 == null && root2 == null){             return true;         }         if(root1!= null && root2!= null){          ...

You are given a list of n-1 integers and these integers are in the range of 1 to n. There are no duplicates in list. One of the integers is missing in the list. Write an efficient code to find the missing integer. Solution 1: using the formula n(n+1) / 2 Code: package microsoftInterviewPrep; public class MissingNumber {         static void findMissingNumber(int[] a){         //we add one to the length since we are missing one element in the array         // we should include that also to get our results correct         int n = a.length + 1;         int total = n* (n+1) /2;                 int arraytotal = 0;         for(int i=0; i<a.length; i++){             arraytotal += a[i];   ...

given an array A[] of n numbers and another number x, determines whether or not there exist two elements in S whose sum is exactly x. Code: package microsoftInterviewPrep; import java.util.Arrays; public class KeyPair {         static void findKeyPair(int[] a, int sum){                 Arrays.sort(a);                 int l = 0;         int r = a.length -1;                 while(l < r){                         int currsum = a[l]+ a[r];                         if(currsum == sum){                 System.out.pr...

Given a singly linked list, find middle of the linked list.  For example, if given linked list is 1->2->3->4->5 then output should be 3. If there are even nodes, then there would be two middle nodes, we need to print second middle element. For example, if given linked list is 1->2->3->4->5->6 then output should be 4. Code: package microsoftInterviewPrep; public class MiddleOfList {         Node head;         class Node{                 int data;         Node next;                 Node(int data){             this.data = data;             next = null;         }     }        ...

In binary representation of a number, if difference between even set bit and odd set bit is a multiple of 3. For example: 12 = 0000 1100 difference = 0 since 0 is a multiple of any integer, 12 is  multiple of 3.. Code: import java.util.*; public class Solution {          static int ismultipleof3(int num){         int evencount = 0;         int oddcount = 0;                  if(num < 0)             num = -num;         if(num == 0) return 0;         if(num == 1) return 1;                           while(num != 0){             if((num & 1) != 0){                 oddcount++;             }     ...

Given an array find the contiguous subarray with maximum sum: I) If the array consists of both positive and negative elements:  We will have the sum initialize the sum to zero. If we find the sum greater then zero then we will update the sum. In successive steps we will update the maximum sum only when it is greater than previous sum. Code: import java.util.*; public class Solution {          public static void main(String[] args) {                  int[] a = {-2, -3, 4, -1, -2, 1, 5, -3};         int n = a.length;         int sum = 0;         int newsum = 0;         for(int i=0; i<n; i++){             newsum += a[i];             if(newsum<0){                 newsum = 0;           ...

A  majority element  in an array A[] of size n is an element that appears more than n/2 times (and hence there is at most one such element). Write a function which takes an array and prints the majority element (if it exists), otherwise prints “No Majority Element”. Naive solution using HashMap : Space complexity = O(n) Time complexity = O(n) HashMap stores key value pairs. The keys must be unique. We iterate through all the elements in the array. If the element is already present in the hashmap then we get its count, increment it by 1. If the count is greater than n/2 then we print the majority element. Else We put the updated count into the hashmap.      If the element is not already present in the hashmap then we put the element into the hashmap with its count set to zero. Code: import java.util.*; public class Solution {     static void findMajorityElement(int[] a) {         int n = a.length; ...