Problem: Inversion Count for an array indicates – how far (or close) the array is from being sorted. If array is already sorted then inversion count is 0. If array is sorted in reverse order that inversion count is the maximum. Formally speaking, two elements a[i] and a[j] form an inversion if a[i] > a[j] and
Continue Reading “Find the Inversion Count of an Array [ Microsoft, Flipkart]”
#include <stdio.h> #include <iostream> using namespace std; int arr[100000]; void merge(int lw,int mid,int hi) { int L[mid-lw+1]; int R[hi-mid+1]; int tmp; for(int i=0;i<mid-lw+1;i++) L[i]=arr[lw+i]; for(int i=0;i<hi-(mid+1)-1;i++) R[i]=arr[mid+i+1]; int i = 0; int j = 0; int k = lw; while(i<(mid-lw+1) && j<(hi-mid)) { if(L[i]<=R[j]) { arr[k]=L[i]; i++; k++; } else if(L[i]>R[j]) { arr[k]=R[j]; k++; j++;
Problem: Find the minimum difference between any pair in an unsorted array. #include <stdio.h> #include <algorithm> #include <iostream> using namespace std; int arr[105]; int res[100005]; int main() { int t,n,k,a; scanf("%d",&t); while(t–) { scanf("%d",&n); for(int i=0;i<105;i++) arr[i]=0; for(int i=0;i<n;i++) { scanf("%d",&a); arr[a]++; } //sort(arr,arr+n); k=0; for(int i=0;i<105;i++) { if(arr[i]==0) continue; for(int j=1;j<=arr[i];j++) res[k++]=i; } int
Continue Reading “Find Minimum difference pair [ Amazon Interview Question]”
Problem: Check if two n-ary tree are mirror to each other. Two trees are mirror if : the key/data value of the root are same of the two trees left sub tree is same as right sub tree of another tree right sub tree is same as left sub tree of another tree The problem
Problem: Provided Inorder and PostOrder of a tree. Construct the tree and print it in PreOrder traversal. #include <stdio.h> #include <iostream> #include <string.h> #include<stdlib.h> #include <string> using namespace std; struct Node{ int data; Node *left; Node *right; }; int search(int in[],int in_stIndex,int in_endIndex,int data) { for(int i=in_stIndex;i<=in_endIndex;i++) { if(in[i]==data) return i; } } void pintPreOrder(Node*
Problem: Provided Inorder and PreOrder of a tree. Construct the tree and print it in PostOrder traversal. #include <stdio.h> #include <iostream> #include <string.h> #include<stdlib.h> #include <string> using namespace std; int preOrderIdx=0; struct Node{ int data; Node *left; Node *rit; }; int search(int in[],int in_stIndex,int in_endIndex,int data) { for(int i=in_stIndex;i<=in_endIndex;i++) { if(in[i]==data) return i; } }
Continue Reading “Tree construction from Inorder & Preorder [ Microsoft ]”
Problem: Find multiplication result of two large numbers in less than O(n^2) time complexity. #include <iostream> #include <string> /* 123456 34343 add=157799 sub=0@J113 */ using namespace std; void makeEqualString(string &a,string &b) { if(a.size()==b.size()) return; else { if(a.size()>b.size()) { for(int i=1;i<=a.size()-b.size();i++) b='0'+b; } else { for(int i=1;i<=b.size()-a.size();i++) a='0'+a; } } } string addString(string a,string b) {
Continue Reading “Karatsuba’s Fast Multiplication Algorithm”
Problem: Count number of bits needed to be flipped to convert from integer A to B. #include <stdio.h> int main() { //code int t,a,b,c; int count=0; scanf("%d",&t); while(t–) { scanf("%d%d",&a,&b); c = a^b; count=0; while(c) { if(c&1) count+=1; c>>=1; } printf("%d\n",count); } return 0; }
Problem: Find the sum of all bits from numbers 1 to N. #include <stdio.h> int main() { //code int t,n,i,ans; int powerOfTwo,dividend,m; int arr[30]; arr[0]=1; arr[1]=2; arr[2]=5; arr[3]=13; int gapOfNumber=8; for(i=4;i<30;i++) { arr[i]=(arr[i-1])*2+(gapOfNumber-1); gapOfNumber=gapOfNumber*2; } scanf("%d",&t); while(t–) { scanf("%d",&n); ans=0; while(n) { m=n; dividend=1; powerOfTwo=0; while(m) { if(m/2) { powerOfTwo+=1; dividend*=2; m=m/2; } else break;
Continue Reading “Count total set bits in all numbers from 1 to n [Amazon ]”
Problem: Find the number of subsequences of the form aibjck, i.e., it consists of i number of ’a’ characters, followed by j i number of ’b’ characters, followed by k i number of ’c’ characters where i >= 1, j >=1 and k >= 1 from a given string S. #include <stdio.h> #include <string.h> int
Continue Reading “Count Number of subsequences of the form a^i b^j c^k [Amazon]”