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 ]”
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 ]”
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 ]”
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)
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 ]”
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 ]”
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 ]”
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; }
Problem:Merge two Sorted (non-increasing) Array. Link #include <stdio.h> void _sort(int ar[],int len1,int br[],int len2) { int i=1,j=1; while(i<=len1 && j<=len2) { if(ar[i]>br[j]) { printf("%d ",ar[i]); i+=1; } else if(ar[i]<br[j]) { printf("%d ",br[j]); j+=1; } else if(ar[i]==br[j]) { printf("%d %d ",ar[i],br[j]); j+=1; i+=1; } } while(i<=len1) printf("%d ",ar[i++]); while(j<=len2) printf("%d ",br[j++]); printf("\n"); } int main() {
Problem:Given a positive integer, return its corresponding column title as appear in an Excel sheet. MS Excel columns has a pattern like A, B, C, … ,Z, AA, AB, AC,…. ,AZ, BA, BB, … ZZ, AAA, AAB ….. etc. In other words, column 1 is named as “A”, column 2 as “B”, column 27 as
Continue Reading “Find Excel Column Name From Column Number [ Microsoft, Amazon, Samsung ]”