Category: Array related Problems
Find Minimum difference pair [ Amazon Interview Question]
Problem: Find the minimum difference between any pair in an unsorted array.
|
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 |
#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 MN=res[1]-res[0]; for(int i=2;i<n;i++) { if(res[i]-res[i-1]<MN) MN=res[i]-res[i-1]; } cout<<MN<<endl; } return 0; } |
Kadane’s Algorithm [ Macrosoft – Amazon – FlipKart ]
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; } |
Maximum Product Sub array [ Microsoft – Amazon ]
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 ]”
Search in rotational sorted array[ Microsoft – Amazon – FlipKart ]
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; } |
Head to Tail ordering
Problem:A head to tail ordering of strings is the one in which the last letter of the previous word is the same as the first letter of the following word. For eg. ‘Angular’can be followed by ‘ rotation’. The task is to write a code to accept a set of finite strings and determine if
Parenthesis Checker [ Snapdel – Amazon ]
Problem: Check the balance of parenthesis sequence, the string contains (),{} and []. 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 |
#include <stdio.h> #include <string.h> int main() { //code char s[105]; char arr[105]; int balance; int t,idx,i; scanf("%d",&t); while(t--) { scanf("%s",s); idx=0; balance=1; for(i=0;i<strlen(s);i++) { if(s[i]=='(' || s[i]=='{' || s[i]=='[') arr[idx++]=s[i]; else if(s[i]==')') { if(arr[idx-1]=='(') { idx--; } else balance=0; } else if(s[i]=='}') { if(arr[idx-1]=='{') { idx--; } else balance=0; } else if(s[i]==']') { if(arr[idx-1]=='[') { idx--; } else balance=0; } if(balance==0) break; } if(balance==0) printf("not balanced\n"); else printf("balanced\n"); } return 0; } |
Find Maximum Distance [ Google-Amazon ]
Problem: An array of integers will be given, find the maximum distance of indexes of [j – i] subjected to the constraint of A[i] <= A[j]. A : [4 6 5 3]; Output : 2; For the pair (4, 5). 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 |
#include <stdio.h> int arr[1005]; int t,n,mx; int main() { //code int i,j; scanf("%d",&t); while(t--) { scanf("%d",&n); for( i=0;i<n;i++) { scanf("%d",&arr[i]); } mx=0; for(i=0;i<n-1;i++) { for(j=n-1;j>=i;j--) { if(arr[i]<arr[j]) { if(j-i>mx) mx=j-i; break; } } } printf("%d\n",mx); } return 0; } |
Removing duplicate chars[Microsoft]
Problem: Given a string, Remove all the duplicate chars, string may include spaces. Solution Hints:solN; ASCII char valaus range from -128 to 127. Link The following solution did not get AC from OJ. My guess is, there may be a problem with that OJ.
|
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 |
#include <iostream> #include <string> #include <stdio.h> using namespace std; int main() { //code int t; int arr[1005]; string str; scanf("%d",&t); //t+=1; getchar(); while(t--) { getline(cin,str); for(int i=0;i<1005;i++) arr[i]=0; for(int i=0;i<str.size();i++) { if(arr[(str[i]-'0')+128]==0) //printf("%c",str[i]); cout<<str[i]; arr[(str[i]-'0')+128]=1; } printf("\n"); } return 0; } |
Find Largest Number formed from an Array [PayTm , Amazon]
Problem:A list of non negative integers will be provided, arrange the numbers in such a way that they form the largest number possible. Example: From a list : 9 30 31 4 10 ; Largest number formed : 94313010. 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 |
#include <stdio.h> #include <algorithm> #include <vector> #include <iostream> #include <string> using namespace std; //vector<string> vb; string vb[105]; int n; bool cmp(string a,string b) { string p=a; p.append(b); string q=b; q.append(a); for(int i=0;i<p.size();i++) { if((p[i]-'0')<(q[i]-'0')) return 1;//if a<b if((p[i]-'0')>(q[i]-'0')) return 0;//if b<a } return 1; } void _sort() { string tmp; for(int i=0;i<n;i++) { for(int j=0;j<n-1;j++) { if(cmp(vb[j],vb[j+1])==0) { tmp=vb[j]; vb[j]=vb[j+1]; vb[j+1]=tmp; } } } } int main() { //code int t,a; string crnt,prev; scanf("%d",&t); while(t--) { scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%d",&a); prev=""; if(a==0) prev.append(1u,'0'); else { prev=""; crnt=""; while(a) { crnt.append(1u,(a%10)+'0'); a/=10; crnt.append(prev); prev=crnt; crnt=""; } } vb[i]=prev; } _sort(); for(int i=n-1;i>=0;i--) cout<<vb[i]; cout<<"\n"; } return 0; } |