Problem:Given a Binary Tree (BT), convert it to a Doubly Linked List(DLL) In-Place. The left and right pointers in nodes are to be used as previous and next pointers respectively in converted DLL.The order of nodes in DLL must be same as Inorder of the given Binary Tree. The first node of Inorder traversal (left
Continue Reading “Binary Tree to Doubly LinkedList Conversion [ Microsoft – Amazon ]”
Problem:Given a positive number x, print all Jumping Numbers smaller than or equal to x. A number is called as a Jumping Number if all adjacent digits in it differ by 1. The difference between ‘9’ and ‘0’ is not considered as 1. All single digit numbers are considered as Jumping Numbers. For example 7, 8987 and
Continue Reading “Jumping Numbers [ Google – Microsoft – Amazon ]”
Problem:Given two strings str1 and str2 and below operations that can performed on str1. Find minimum number of edits (operations) required to convert ‘str1′ into ‘str2′. a.Insert b.Remove c.Replace All of the above operations are of cost=1.Both the strings are of lowercase. Hint: Use DP to solve the problem. This problema also can be solved using
Continue Reading “Edit Distance of Two Given String [ Amazon ]”
Problem:A string is k pallindrome if it can be transformed into a palindrome on removing at most k characters from it. Link
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
/*You are required to complete this function*/ bool is_k_pallin(string s,int k) { //Your code here string rev_s=""; int n = s.size(); for(int i=s.size()-1;i>=0;i--) rev_s.append(1u,s[i]); int dp[n+1][n+1]; for(int i=0;i<=n;i++) { for(int j=0;j<=n;j++) { if(i==0) dp[i][j]=j; else if(j==0) dp[i][j]=i; else if(s[i-1]==rev_s[j-1]) dp[i][j]=dp[i-1][j-1]; else if(s[i-1]!=rev_s[j-1]) dp[i][j] = 1+ (dp[i-1][j]<dp[i][j-1]?dp[i-1][j]:dp[i][j-1]); } } if(dp[n][n]<=2*k) return 1; return 0; } |
Problem: Given an array containing both negative and positive integers. Find the contiguous sub-array with maximum sum. Link
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
#include <stdio.h> int main() { //code int t,n,i,a; int mx_end_here,mx_so_far; scanf("%d",&t); while(t--) { scanf("%d",&n); mx_end_here=0,mx_so_far=-1000; for(i=0;i<n;i++) { scanf("%d",&a); if(a<0) { if(mx_so_far<a) mx_so_far=a; mx_end_here=mx_end_here+a; if(mx_end_here<0) mx_end_here=0; } else if(a>=0) { mx_end_here=mx_end_here+a; if(mx_end_here>mx_so_far) mx_so_far=mx_end_here; } } printf("%d\n",mx_so_far); } return 0; } |
Problem : Given an array that contains both positive and negative integers, find the product of the maximum product subarray. Link Discussion: It is a Similiar problem to maximum sum sub array problem. Notice,maximum product can also be obtained by minimum (negative) product ending with the last element multiplied by this element. we use mn_end_here(can be
Continue Reading “Maximum Product Sub array [ Microsoft – Amazon ]”
Problem: Find a value from a rotational sorted array. Solution Hint: binary search. Link
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 |
#include <stdio.h> int arr[100010]; int bin_search(int lw,int hi,int v) { if(v<arr[lw] || v>arr[hi]) return 0; int mid; while(lw<=hi) { mid=(lw+hi)/2; if(arr[mid]==v) { printf("%d\n",mid); return 1; } else if(arr[mid]<v) lw=mid+1; else if(arr[mid]>v) hi=mid; } return 0; } int main() { //code int t,i,j,n,val,a,idx; int f=0; int lw,mid,hi; scanf("%d",&t); while(t--) { scanf("%d",&n); val=100010; f=0; for( i=0;i<n;i++) { scanf("%d",&arr[i]); if(arr[i]<val) { val=arr[i]; idx=i; } } scanf("%d",&a); lw=idx;hi=(idx+n-1)%n; f=bin_search(0,hi,a); if(f==0) f=bin_search(lw,n-1,a); if(f==0) printf("-1\n"); } return 0; } |
Problem:Traverse 4×4 matrix spirally. Link
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
#include <stdio.h> int main() { //code int t,i,j; int ar[4][4]; scanf("%d",&t); while(t--) { for(i=0;i<4;i++) { for(j=0;j<4;j++) scanf("%d",&ar[i][j]); } for(i=0;i<4;i++) printf("%d ",ar[0][i]); for(i=1;i<4;i++) printf("%d ",ar[i][3]); for(i=2;i>=0;i--) printf("%d ",ar[3][i]); printf("%d %d ",ar[2][0],ar[1][0]); printf("%d %d ",ar[1][1],ar[1][2]); printf("%d %d\n",ar[2][2],ar[2][1]); } return 0; } |
Problem:Merge two Sorted (non-increasing) Array. Link
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 |
#include <stdio.h> void _sort(int ar[],int len1,int br[],int len2) { int i=1,j=1; while(i<=len1 && j<=len2) { if(ar[i]>br[j]) { printf("%d ",ar[i]); i+=1; } else if(ar[i]<br[j]) { printf("%d ",br[j]); j+=1; } else if(ar[i]==br[j]) { printf("%d %d ",ar[i],br[j]); j+=1; i+=1; } } while(i<=len1) printf("%d ",ar[i++]); while(j<=len2) printf("%d ",br[j++]); printf("\n"); } int main() { //code int t,n,X,Y,j,i,len; int arr[50005]; int brr[50005]; scanf("%d",&t); while(t--) { scanf("%d%d",&X,&Y); for( i=1;i<=X;i++) { scanf("%d",&arr[i]); } for( i=1;i<=Y;i++) { scanf("%d",&brr[i]); } if(X<Y) { _sort(arr,X,brr,Y); } else _sort(brr,Y,arr,X); } return 0; } |
Problem:Given a positive integer, return its corresponding column title as appear in an Excel sheet. MS Excel columns has a pattern like A, B, C, … ,Z, AA, AB, AC,…. ,AZ, BA, BB, … ZZ, AAA, AAB ….. etc. In other words, column 1 is named as “A”, column 2 as “B”, column 27 as
Continue Reading “Find Excel Column Name From Column Number [ Microsoft, Amazon, Samsung ]”