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

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

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

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

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

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

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

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

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

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

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