Problem: Given an input string and a dictionary of words, find out if the input string can be segmented into a space-separated sequence of dictionary words. See following examples for more details. Consider the following dictionary { i, like, sam, sung, samsung, mobile, ice,cream, icecream, man, go, mango} Input: ilike Output: Yes The string can be
Author: Asif Naeem
Almost Prime number
Problem:A no is said to be k-Almost Prime Number if it has exactly k prime factors (not necessary distinct). Your task is to complete the functionprintKAlmostPrimes which takes two argument k and N and prints the first N numbers that are k prime. Problem Link /*You are required to complete this function*/ bool isPrime(int n) { bool arr[20]; int i; arr[2]=1;arr[3]=1;arr[5]=1;arr[7]=1; arr[11]=1;arr[13]=1;arr[17]=1;arr[19]=1;
Binary Tree to Doubly LinkedList Conversion [ Microsoft – Amazon ]
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 ]”
Jumping Numbers [ Google – 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 ]”
Edit Distance of Two Given String [ 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 ]”
Find K-Palindrome of a 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 /*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)
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 #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;
Continue Reading “Kadane’s Algorithm [ Macrosoft – Amazon – FlipKart ]”
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 #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;
Continue Reading “Search in rotational sorted array[ Microsoft – Amazon – FlipKart ]”
Traverse 4×4 matrix spirally.[ Microsoft – BrowserStack ]
Problem:Traverse 4×4 matrix spirally. Link #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; }