Interview Preparation

Problem Link When we do XOR we will get 1 in all places where two bits are different. Then we can find the position of rightmost set bit. Code: package bitManipulation; public class RightMostDifferentBit {     public static void main(String[] args){         int m = 11, n = 9;                 int diffValue = m ^ n;                 int result = (int)(Math.log10( diffValue & -diffValue) / Math.log10(2)) +1;                 System.out.print(result);             } } Output: 2  

Problem Link 2's complement flips every bit except right most 1. Hence AND operation with n and its two's complement will give 2 power position of rightmost 1. We can get position by taking log. Code: package bitManipulation; public class RightMostSetBit {         public static void main(String[] args){                 int n = 12;         int rightmostbit;                 rightmostbit = (int) (Math.log10((n & -n)) / Math.log10(2)) +1;                 System.out.print(rightmostbit);                     } } Output: 3

Problem Link (n-1) flips all bits till it sees a rightmost bit as 1 . It flips also the rightmost 1. Hence, n-1 flips set bits one by one, when placed in a loop. Code: package bitManipulation; public class CountSetBits {         public static void main(String[] args){         int n = 6, count = 0;                 while (n != 0){             count +=1;             n = n & (n-1);         }                 System.out.println(count);         } } Output: 2

Problem link Code: package bitManipulation; public class RotateBits {     static final int INT_BITS = 32;         static void rotateRight(int n, int k){         n = (n>>k) | (n<<(INT_BITS-k));         System.out.println("Right rotaed: "+n);     }         static void rotateLeft(int n, int k){         n = (n<<k) | (n>>(INT_BITS-k));         System.out.println("Left rotaed: "+n);     }         public static void main(String[] args){                 int n = 16, k = 2;         rotateRight(n,k);         rotateLeft(n,k);     } } Output: Right rotaed: 4 Left rotaed: 64

Input : n = 10, k = 2 Output : 14 (10) 10 = (1010) 2 Now, set the 2nd bit from right. (14) 10 = (1 1 10) 2 2nd bit has been set. Input : n = 15, k = 3 Output : 15 3rd bit of 15 is already set. Code: import java.util.*; public class Solution {       public static void main(String[] args){                 int n = 10, k=2;                 //n = n | ( 1 << k );         n |= ( 1 << k );                 System.out.print(n);                         } } Output: 14

Input: n=15, k=1 Output: 14 Explanation: 15 -> 1111 & ~(0001) -> 1111 & 1110 -> 14 Code: import java.util.*; public class Solution {       public static void main(String[] args){                 int n = 15, k=2;                 n = n & ( ~( 1 << (k-1) ) );                 System.out.print(n);                         } } Output: 13

Input: n = 5, k = 1 Output: SET Input: n = 6, k = 2 Ouput: NOT SET Explanation: To get kth bit left shift 1 by k-1, do AND operation with n to get the kth bit. We have k-1 because, the bit positions are like, 1,2,3,4.... To get the first bit we have to shift by zero, to get second bet we have to shift 1 by one....Hence k-1. If k has values starting from 0 then we can shift by k instead of k-1. Code: import java.util.*; public class Solution {     public static void main(String[] args){               int n = 5, k=3;               if( ( n & ( 1 << ( k-1) ) ) != 0)             System.out.print("SET");         else             System.out.print("NOT SET");               } } Output: SET Examples: 5 -> 101 k=1:     left shift 1 by k-...

Problem link Recursion Steps: If the node is null return Integers min value Maximum is the max of node data, left subtree and right subtree. Code: package may; public class MaximumInTree {         Node root;         int findMax(Node node){         if(node == null)             return Integer.MIN_VALUE;                 return Math.max(Math.max(node.data, findMax(node.left)), findMax(node.right));     }         public static void main(String args[])     {         MaximumInTree tree = new MaximumInTree();         tree.root = new Node(2);         tree.root.left = new Node(7);         tree.root.right...

Types of binary trees Problem link Code: public class FullBinaryTree {         Node root;         boolean isFullTree(Node node){                 if(node == null)             return true;                 if(node.left == null && node.right == null)             return true;                 if(node.left != null && node.right != null)             return isFullTree(node.left) && isFullTree(node.right);                 return false;                 }      ...

Problem link Code: public class Ancestors {         Node root;         boolean isAncestor(Node node, int data){         if(node == null)             return false;         if(node.data == data)             return true;         if(isAncestor(node.left, data) || isAncestor(node.right, data)){             System.out.print(node.data+" ");             return true;         }                 return false;     }         public static void main(String[] args){         Ancestors tree = n...

Problem link Recursion Steps: If node is null return zero If left and right nodes are null return 1 Return count of leaves for left and right subtrees Code: public class CountLeaves {     Node root;         int countLeaves(Node node){                 if(node == null)             return 0;                 if(node.left == null && node.right == null)             return 1;                 return countLeaves(node.left)+countLeaves(node.right);     }         public static void main(String[] args){         CountLeaves tree = new CountLeaves();      ...

Source: problem link Code: public class DeleteTree {     Node root;         void deleteTree(Node node){         if(node == null)             return;         deleteTree(node.left);         deleteTree(node.right);         System.out.println("node to delete "+node.data);         node = null;     }         void deleteTreeRef(Node root)     {         deleteTree(root);         root=null;     }         public static void main(String[] args){         DeleteTree tree = new DeleteTree();               ...

problem link Code: class Node{ int data; Node left, right; Node(int data){     this.data = data; } } public class MirrorTree {         Node root;         void converToMirror(Node node){                 if(node == null){             return;         }                 Node temp = node.right;         node.right = node.left;         node.left = temp;         converToMirror(node.left);         converToMirror(node.right);     }         void printTree(Node node){                 if(node == null)  ...

Recursion Steps:   Size of a tree= 1+size of left subtree + size of right subtree   Base case : return zero if  a node is null Code:     Time:O(n) class Node{     int data;     Node left, right;     Node(int data){         this.data = data;     } } public class SizeOfBinaryTree {       static int calculateSize(Node node){           if(node == null){               return 0;           }                     return (1+calculateSize(node.left)+calculateSize(node.right));       }             public static void main(String[] args){      ...

Steps: If two nodes are null we reached the end for that subtree and we will return true If two nodes are not null we check for data and check recursively their left and right sub trees If one node is null and other is not null then we return false which is the last statement in the function.     Code: class Node{     int data;     Node left, right;         Node(int data){         this.data = data;     } } public class IdenticalTrees {      Node tree1, tree2;           boolean isIdentical(Node n1, Node n2){          if(n1 == null && n2 == null){              return true;          }          if(n1!= null && n2!=null){   ...

Input: {5,4,1,2,3} Output: yes Explanation: Max element is 5 and min element id 1, Array contains all elements from 1 to 5 Input: {2,1,0,-3,-2,-1} Output: yes Explanation: Array contains elements from -3 to 2. Concept used: If the array elements are consecutive and distinct then the array is in AP. So we compare array sum with AP sum. ap_sum = n/2 * [2a +(n-1)*d] where d = 1, since elements are consecutive. Code: import java.util.*; public class Solution {          public static void main(String[] args) {                 int[] a = {5, 4, 2, 1, 3};         int n = a.length;         int sum = 0;         boolean result = false;                  int first = a[0];         for(int i=1; i<n; i++){             if(a[i]<first) ...

Input = {12, 34, 45, 9, 8, 90, 3} Output = {12, 34, 8, 90, 45, 9, 3} Method1: O(n) time Keep incrementing left till we have even number. Keep incrementing right till we have odd number. Swap left and right if left less than right. Code: import java.util.*; public class Solution {          public static void main(String[] args) {                 int[] a = {12, 34, 45, 9, 8, 90, 3};         int n = a.length;         int left = 0, right = n-1;                  while(left<right){             while(a[left]%2 == 0 && left< right){                 left++;             }             while(a[right]%2 !=0 && left< right){               ...

Input: arr[] = {1, 4, 20, 3, 10, 5}, sum = 33 Ouptut: Sum found between indexes 2 and 4 Input: arr[] = {10, 2, -2, -20, 10}, sum = -10 Ouptut: Sum found between indexes 0 to 3 Input: arr[] = {-10, 0, 2, -2, -20, 10}, sum = 20 Ouptut: No subarray with given sum exists Naive Solution:    We pick elements one by one in outer loop and find its sum with other elements to its right till we get the given sum. Code: import java.util.*; public class Solution {          public static void main(String[] args) {                 int[] a = {10, 2, -2, -20, 10};         int n = a.length;         int sum = -10, currsum = 0;         int index1 = -1, index2 = -1;                  for(int i=0; i<n; i++){             currsum = a[i];           ...

Input: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Output: 1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10 Concept: When we look at array indices, i) At top we have row as constant and column varying from left to right. ii) At right we have column as constant and row varying from top to bottom. iii) At bottom we have row as constant and column varying from right to left. iv) At left we have column as constant and row varying from bottom to top. Code: import java.util.*; public class Solution {          public static void main(String[] args) {         int[][] a ={{1,2,3,4,5,6},{7,8,9,10,11,12},{13,14,15,16,17,18}};         int m = a.length;         int n = a[0].length;                  int top = 0, bottom = m-1, left = 0, right = n-1;                ...

Input: arr[] = {1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1} m = 2 Output: 5 7 We are allowed to flip maximum 2 zeroes. If we flip arr[5] and arr[7], we get 8 consecutive 1's which is maximum possible under given constraints Input: arr[] = {1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1} m = 1 Output: 7 We are allowed to flip maximum 1 zero. If we flip arr[7], we get 5 consecutive 1's which is maximum possible under given constraints. Input: arr[] = {0, 0, 0, 1} m = 4 Output: 0 1 2 Since m is more than number of zeroes, we can flip all zeroes. Steps: It is based on sliding window method. The window at any time should consists of only m zeroes. If the zerocount is below m wr is incremented. If the zerocount is more wl is incremented. Code: import java.util.*; public class Solution {       public static void main(String[] args) {         int[] a = {1,1,0,1,1,0,0,1,1,1};         int m = 2;   ...

An element is leader if it is greater than all the elements to its right. The last array element is a leader by default. Example: Input:  {16, 17, 4, 3, 5, 2} Output: 2, 5, 17 Concept: Scan form right. Keep track of maximum element. If the maximum changes print the element and update the maximum. Time complexity O(n). Code: import java.util.*; public class Solution {          public static void main(String[] args) {         int[] a = {1,10,4,5,3,2};         int n = a.length;         int max = a[n-1];                  System.out.print(max+" ");         for(int i=n-2; i>=0; i--){             if(a[i] > max){                 System.out.print(a[i]+" ");                 max = a[i];     ...

Given a number find the smallest number that is greater than n, and has same number of digits as n. Input: n = "218765" Output: "251678" Input: n = "1234" Output: "1243" Input: n = "4321" Output: "Not Possible" Input: n = "534976" Output: "536479" Steps: Consider  3,2,8,4,1 1. Start from right and find the digit that is smaller than its next digit.     3, 2 < 8 >4 >1 2. Swap that digit with its next higher number in the right.     3, 2 , 8, 4 ,   1    (next higher digit of 2 is 4)     3, 4 ,8, 2 ,1 3. Reverse the digits to the right of that digit (4).    3,4,1,2,8 Code: import java.util.*; public class Solution {          static void findNextGreater(int[] a){         int n = a.length;         int position = -1;                  for(int i=n-1; i>0; i--){     ...

Given an array where only two elements where swapped , sort the array with O(n) time complexity and one swap Input: arr[] = {10, 20, 60, 40, 50, 30} // 30 and 60 are swapped Output: arr[] = {10, 20, 30, 40, 50, 60} Input: arr[] = {10, 20, 40, 30, 50, 60} // 30 and 40 are swapped Output: arr[] = {10, 20, 30, 40, 50, 60} Input: arr[] = {1, 5, 3} // 3 and 5 are swapped Output: arr[] = {1, 3, 5} Concept behind:   If you swap two elements in a sorted(ascending) array, the first out of order element will be greater than its next element and the next out of order element will be less than its previous element. Consider:  {10, 20, 40, 30, 50, 60}  Here the first out of order element is 40( 40 > 30) -> a[i] > a[i+1] The next out of order element is  30 (30 < 40) -> a[i] < a[i-1] Hence we will first find the first out of order element and from the next element we check for the other out of order element using the above condition...