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] #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
Continue Reading “Super Ugly Number – Extension of Ugly Number Problem”
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 #include <stdio.h> #include <iostream> using
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
#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++;
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]”