Category: Practice Problems
Find Minimum difference pair [ Amazon Interview Question]
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]”
Check Mirror Tree [ MakeMyTrip, Amazon ]
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
Tree construction a Binary Tree from Postorder and Inorder traversal [Amazon, Adobe]
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*
Tree construction from Inorder & Preorder [ Microsoft ]
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 ]”
Count number of bits to be flipped to convert A to B [Amazon]
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; }
Count total set bits in all numbers from 1 to n [Amazon ]
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 ]”
Count Number of subsequences of the form a^i b^j c^k [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]”
Matrix Exponentiation algorithm
Related studies: Here Problem Link Problem description: The laboratory of Microbiology department has been attacked by several robbers recently. They robbed and stole many valuable samples of viruses, bacteria, microorganisms. While being in hurry, they broke a tube. The tube contained sample of one of the most dangerous germs called Dangerm. The tube contained exactly
Count of n digit numbers whose sum of digits equals to given sum [ Amazon ]
Problem: Given two integers ‘n’ and ‘sum’, find count of all n digit numbers with sum of digits as ‘sum’. Leading 0’s are not counted as digits. Print your output % 10^9+7. #include <stdio.h> #define MOD 1000000007 unsigned long long dp[101][1001]; unsigned long long Count(int n,int sum) { int i; if(n==0) { if(sum==0) return 1; return
Continue Reading “Count of n digit numbers whose sum of digits equals to given sum [ Amazon ]”