Interview Preparation

Check if a number is a power of another number Input: x = 10, y = 1 Output: True x^0 = 1 Input: x = 10, y = 1000 Output: True x^3 = 1 Input: x = 10, y = 1001 Output: False Code: package sap; public class Power {         public static void main(String[] args){                int x = 27, y = 729;                 int val = (int)Math.log(y)/ (int)Math.log(x);                 double res = Math.log(y)/Math.log(x);                 if(val == res){             System.out.println(x+" can be expressed as a power of "+y);         }                 else{             System.out.println(x +" cannot be expressed as a power of "+y);         }             } } Output: 27 can be expressed as a power of 729

Given a String of length N reverse the whole string without reversing the individual words in it. Words are separated by dots. Code: package sap; public class ReverseWords {         public static void main(String[] args){                 String word = "I am done";         StringBuilder result = new StringBuilder("");                 String[] arr = word.split("\\s");                 for(int i=arr.length-1; i>=0; i--){                         result.append(arr[i]);             result.append(" ");                     }                 System.out.println(result.toString());                     } }   Output: done am I  

https://www.geeksforgeeks.org/commonly-asked-c-interview-questions-set-1/ https://www.geeksforgeeks.org/commonly-asked-c-interview-questions-set-2/

Given an array of integers, our task is to write a program that efficiently finds the second largest element present in the array. Example: Input : arr[] = {12, 35, 1, 10, 34, 1} Output : The second largest element is 34. Code: package sap; public class SecondLargest {         public static void main(String[] args){                 int[] a = {89, 24, 75, 11, 23};         int max = Integer.MIN_VALUE, secondMax = Integer.MIN_VALUE;                 for(int i=0; i<a.length; i++){                         if(a[i] > max){                                 secondMax = max;                 max = a[i];                             }             else if(a[i] > secondMax){                 secondMax = a[i];             }                     }                 System.out.println("The second maximum element is "+secondMax);             } } Output: The second maximum element is 75

Code: package sap; public class RemoveSpaces {         public static void main(String[] args){                 String str = "Hi nivetha";         System.out.println("Input String: "+str);         str = str.replaceAll("\\s", "");                 System.out.println("Output String: "+str);        } } Ouput: Input String: Hi nivetha Output String: Hinivetha

refer Code: package sorting_algorithms; import java.util.Arrays; public class QuickSort {     static void quickSort(int[] a, int p, int r){         if(p<r){             int pivot = partition(a, p, r);             quickSort(a, p, pivot -1);             quickSort(a, pivot+1, r);         }     }     static int partition(int[] a,int p,int r){         int pivotelem = a[r];         int i = p-1;         for(int j= p; j<r; j++){             if(a[j] < pivotelem){                 i++;                 int temp = a[i];                 a[i] = a[j];                 a[j] = temp;             }         }         int temp = a[i+1];         a[i+1] = a[r];         a[r] = temp;         return i+1;             }     public static void main(String args[])     {         int arr[] = {12, 11, 13, 5, 6, 7};         System.out.println("Given Array");         System.out.println(Arrays.toString(arr));         quickSort(arr, 0, arr.length-1);         System.out.println("\nSorted array&q

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             System.out.println(binarySearch(a, pivot+1, n, key));     }        static int findPivot(int[] a, int low, int high){         if(high < low)             return -1;         int mid = (low + high) / 2;         if( a[mid] > a[mid+1])             return mid;         if(a[low] > a[mid])             r

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];                 a[low] = a[mid];                 a[mid] = temp;                                 low++;                 mid++;             }                         else if(a[mid] == 2){                                 int temp = a[high];                 a[high] = a[mid];                 a[mid] = temp;                 high--;             }                         else{

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;         }     }     static boolean  hasRootToLeafPath(Node node, int sum){         //if tree is called with null root         if(node == null){             return (sum == 0);         }         if(node.left == null && node.right == null){             return (sum == node.dat

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;         printTree(node.left);         System.out.print(node.data+" ");         printTree(node.right);     }     public static void main(String[] args){         N1804_MirrorTree tree = new N1804_MirrorTree();         tree.root = new Node(1);         tree.root.left = new Node(2);         tree.root.right = new Node(3);         tree.root.left.left = new Node(4);         tree.root.left.right = new Node(5);            

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){             return (root1.data == root2.data)&& isIdentical(root1.left, root2.left) && isIdentical(root1.right,root2.right);         }         return false;     }     public static void main(String[] args){         N1802_IdenticalTrees trees = new N1802_IdenticalTrees();         trees.tree1 = new Node(2);        

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];         }                 int res = total - arraytotal;                 System.out.println("Missing number is "+ res);     }         public static void main(String[] args){                 int[] a= {1, 2, 4, 6, 3, 7, 8};         findMissingNumber(a);             } } Output: Missing n

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.println("The pairs with sum "+ sum+" are: "+ a[l]+" and "+a[r]);                 break;             }             else if( currsum < sum){                 l++;             }             else{                 r--;             }         }                     }                 public static void main(String[] args){                   int a[] = {1, 4, 45, 6, 10, -8};           int n = 16;           findKeyPair(a, n);                     } } Outpu

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;         }     }             static void  printMiddle(Node head){                 Node slow = head;         Node fast = head;                 while(fast != null && fast.next != null){             slow = slow.next;             fast = fast.next.next;         }                 System.out.println("Middle element is: "+ slow.data);                     }         void push(int data){      

Given two binary trees, check if the first tree is subtree of the second one. Code: package trees; public class N2011_subTree {         Node root1, root2;     static class Node{         int data;         Node left, right;         Node(int data){             this.data = data;             left = right = null;         }     }     static boolean isIdentical(Node n1, Node n2){         if(n1 == null && n2 == null){             return true;         }         if(n1 != null && n2 != null){             return (n1.data == n2.data) && isIdentical(n1.left, n2.left) && isIdentical(n1.right, n2.right);         }                 return false;     }         static boolean isSubtree(Node t, Node s){                 if(s == null){             return true;         }                 if( t == null){             return false;         }                 if( isIdentical(t, s)){             return true;         }                 return isSubtree(t.left, s) || isSubtree(t.righ

Input: Inorder traversal in[] = {4, 2, 5, 1, 3, 6} Preorder traversal pre[] = {1, 2, 4, 5, 3, 6} Output: Postorder traversal is {4, 5, 2, 6, 3, 1} Code: package trees; public class N2003_PrintPostOrer {     class Node{         int data;         Node left , right;         Node(int data){             this.data = data;             left = right = null;         }     }     static int findIndex(int element, int[] a, int start, int end){         int i= -1;         for(i =start; i<= end; i++){             if(element == a[i]){                 return i;             }         }         return i;     }     static int preIndex = 0;     static void printPostOrder(int[] in, int[] pre, int start, int end){         if(start > end){             return;         }         int element = pre[preIndex++];         if(start != end){             int index = findIndex(element, in, start, end);             printPostOrder(in, pre, start, index-1);             printPostOrder(in, pre, index+1, end);    

Let us consider the below traversals: Inorder sequence: D B E A F C Preorder sequence: A B D E C F Tree: A / \ / \ B C / \ / / \ / D E F Code: package trees; public class N2002_ConstructTreeInorderPreOrder {             static int preIndex = 0;         static class Node{         char data;         Node left, right;                 Node(char data){                         this.data = data;             left = null;             right = null;                     }     }         static Node buildTree(char[] pre, char[] in, int start, int end){                 if(start > end){             return null;         }                 Node node = new Node(pre[preIndex++]);                 if(start == end){             return node;         }                 int index = findIndex(node.data, in , start, end);                 node.left = buildTree(pre, in, start, index-1);         node.right = buildTree(pre, in, index+1,

Given a Binary Tree, find maximum(or minimum) element in it. For example, maximum in the following Binary Tree is 9. Code: package trees; public class N2017_findMaxOrMin {         Node root;         static class Node{                 int data;         Node left, right;                 Node(int data){                         this.data = data;                         right = null;             left = null;                     }     }         static int findMax(Node node){                 if(node == null){             return Integer.MIN_VALUE;         }                 int max = node.data;         int left = findMax(node.left);         int right = findMax(node.right);                 if(left > max){             max = left;         }                 if(right > max){             max = right;         }                 return max;             }         public static void main(String[] args){                         N2017_findMaxOrMin tree = new N2017_findMaxOrMin();        

Point arbit pointer to greatest value right side node in a linked list Given singly linked list with every node having an additional “arbitrary” pointer that currently points to NULL. We need to make the “arbitrary” pointer to greatest value node in a linked list on its right side. Code: package linkedlist; public class PonitGreatestValue {     Node head = null;     class Node{         int data;         Node arbit;         Node next;         Node(int data){             this.data = data;             arbit = null;             next = null;         }     }     void insert(int data){         Node new_node = new Node(data);         if(head == null){             head = new_node;             return;         }         Node last = head;         while(last.next != null){             last = last.next;         }         last.next = new_node;     }     static void printlist(Node head) {         Node temp = head;         while (temp != null) {             System.out.prin

Rearrange a Linked List in Zig-Zag fashion Given a linked list, rearrange it such that converted list should be of the form a < b > c < d > e < f .. where a, b, c.. are consecutive data node of linked list. Examples : Input: 1->2->3->4 Output: 1->3->2->4 Input: 11->15->20->5->10 Output: 11->20->5->15->10 Code: package linkedlist; import linkedlist.RerverseKnodes.Node; /*  * author: Nivetha G  */ public class RearrageListZigZagFashion {     Node head = null;     class Node{         int data;         Node next;         Node(int data){             this.data = data;             next = null;         }     }     void insert(int data){         Node new_node = new Node(data);         if(head == null){             head = new_node;             return;         }         Node last = head;         while(last.next != null){             last = last.next;         }