Category: Algorithm
Find Longest valid Parentheses Length [ Google ]
Problem: Given a string consisting of opening and closing parenthesis, find length of the longest valid parenthesis sub string.[Courtesy: geeksforgeeks] Problem Link Solution: The problem can be solved with DP approach . And also as counting the left and right parenthesis from left to right.If the left parenthesis count is less than the right parenthesis
Continue Reading “Find Longest valid Parentheses Length [ Google ]”
Super Ugly Number – Extension of Ugly Number Problem
Problem: The problem is an extension of Ugly number problem. Problem Link : Here [Courtesy geeksforgeeks]
|
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 <iostream> using namespace std; int _min(int arr[],int k) { int m= arr[0]; for(int i=1;i<k;i++) { if(m>arr[i]) m=arr[i]; } return m; } int SuperUgly(int n,int k,int primes[]) { int min_val; int superUgly[n]; int tmp[k]; int prime_iterator_count[k]; for(int i=0;i<k;i++) prime_iterator_count[i]=0; superUgly[0]=1; for(int i=1;i<n;i++) { for(int j=0;j<k;j++) { tmp[j] = superUgly[ prime_iterator_count[j] ] * primes[j]; } min_val = _min(tmp,k); superUgly[i]=min_val; for(int j=0;j<k;j++) { if(min_val==tmp[j]) prime_iterator_count[j]++; } } return superUgly[n-1]; } int main() { int primes[100]; int t,n,k; cin>>t; while(t--) { cin>>n>>k; for(int i=0;i<k;i++) scanf("%d",&primes[i]); cout<<SuperUgly(n,k,primes)<<endl; } } |
Maximum Boolean Parenthesization String [ Microsoft, Amazon]
Problem: Count the maximum number of ways we can parenthesize of a given boolean expression so that the value of expression evaluates to true or false as asked. Boolean expression will be given with following symbols. Symbols ‘T’ —> true ‘F’ —> false And the Operators & —> boolean AND | —>
Continue Reading “Maximum Boolean Parenthesization String [ Microsoft, Amazon]”
Ugly Number Problem
Problem: The problem of ugly number is a common DP problem. Description: Ugly numbers are positive numbers whose prime factors only include 2,3,5,7. For example, 6,8 are ugly while 14 is not ugly since it includes another prime factor 7.Note that 1 is typically treated as an ugly number. courtesy: leetcode.com
|
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> #include <iostream> using namespace std; int _min(int a,int b,int c) { if(a<=b && a<=c) { return a; } if(b<=a && b<=c) { return b; } if(c<=b && c<=a) { return c; } } int main() { int two_used=0,three_used=0,five_used=0; int next_ugly_number; int a,b,c; int ugly[155]; ugly[0]=1; for(int i=1;i<155;i++) { a = ugly[two_used]*2; b = ugly[three_used]*3; c = ugly[five_used]*5; next_ugly_number = _min(a,b,c); ugly[i]=next_ugly_number; if(next_ugly_number==a) two_used++; if(next_ugly_number==b) three_used++; if(next_ugly_number==c) five_used++; } //cout<<_min(5,2,3)<<endl; int t,n; scanf("%d",&t); while(t--) { scanf("%d",&n); cout<<ugly[n-1]<<endl; } return 0; } |
Number that are not divisible [Paytm]
Problem: Find the number of non-divisible numbers in a range starting from 1 to N, for a given set. Problem Link [Courtesy: geeksforgeeks.org] Appeared as interview question in Paytm. Solution: The given set is {2,3,4,5,6,7,8,9,10}. The set can be minimized to {2,3,5,7} as these are the prime numbers and rest of the numbers of the
Find the longest palindrome of a String [Amazon,Microsoft]
Problem: Find the length and/or string of the longest palindrome of a string. The problem appeared as an Interview question in Amazon, Microsoft. Solution: One important property of a palindrome is if we remove the first and last characters of it , it would be another palindrome. So A string S[a..b] will be a palindrome
Continue Reading “Find the longest palindrome of a String [Amazon,Microsoft]”
Find the Inversion Count of an Array [ Microsoft, Flipkart]
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]”
Merge Sort
|
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 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 |
#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++; } } while(i<(mid-lw+1)) { arr[k++]=L[i++]; } while(j<(hi-mid)) { arr[k++]=R[j++]; } } void mergesort(int lw,int hi) { if(hi>lw) { int mid=lw+(hi-lw)/2; mergesort(lw,mid); mergesort(mid+1,hi); merge(lw,mid,hi); } } int main() { int t,n; scanf("%d",&t); while(t--) { scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",&arr[i]); mergesort(0,n-1); for(int i=0;i<n;i++) cout<<arr[i]<<" "; } return 0; } |
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; } |