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 ]”
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; } } |
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]”
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; } |
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
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]”