GeeksSpot

Given a array, find the n increasing number whose summation will be maximum. Thanks to my friend pallav for asking this. Certainly its DP, I will post once i am through.

Find the two numbers whose difference is minimum among the set of numbers. For example the sequence is 5, 13, 7, 0, 10, 20, 1, 15, 4, 19 The algorithm should return min diff = 20-19 = 1. Make an efficient algorithm, yeah best could be O(n). Not sure if i could use DP here, will post a solution tommorow. Let me know if you find a answer. Algorithm:MiniMumDiffN Get the size of array , say n. Get the range of array, range. Bucket Sort the above array. Search the above sorted array for minimum difference. This will be the minimum difference numbers. Now question comes where the range of above given array is very big. Algorithm:DivideArray Take an random element. Search for its position in array. Return the index of element. Algorithm:MiniMumDiff if array_range > MAXRANGE int mid = divideArray (arr,start,end); d1,max1 = MiniMumDiff( arr,start,mid-1); d2,max2 = MiniMumDIff(arr,mid+1,end); d3 = difference max1 and arr[mid] d4 = difference max2 and arr[mid] return minimum( d1,d2...

you are given a M x N matrix with 0's and 1's find the matrix- 1. find the largest square matrix with all elements 1's 2. Find the largest rectangular matrix with all elements 1's Its simple DP problem guys ..just think of extending the solution to sub-problem. Will post answer soon..till then give it a try. Okie so recursive expression is SQ(i,j) = MIN(SQ(i-1,j),SQ(i-1,j-1),SQ(i,j-1))*ARR(i,j)+ARR(i,j); Idea is that SQ(i,j) will be a 1+ min of its precedents square size. I am multiplying and adding to avoid if else condition if ( ARR[i][j] == 1 ) SQ(i,j) = MIN(SQ(i-1,j),SQ(i-1,j-1),SQ(i,j-1))+1; else SQ(i,j) = 0; is same as this SQ(i,j) = MIN(SQ(i-1,j),SQ(i-1,j-1),SQ(i,j-1))*ARR(i,j)+ARR(i,j); Will post code soon.

Given an array which have samples of stock price at different timestamps. You have to find best timings when we can buy and sell and make maximum benifit by it. No need to say u can sell only after you buy. Its simple DP problem, just need to form a equation MaxGain(i) = Max(MaxGain(i-1), DIff(i,min)) Min is the index of element having min value till now. Diff will return the value(i)-value(min). Hope its clear.

39. Find first non repeating character in a string. a) Bruteforce: TC: o(n2) SC: o(1) b) use another array or use hashtable 40. Find whether two arrays of same size have same values. Go through first array, hash every element and increment the count if repeated. Go through second and decrement count for every element and at the lost every index should be having zero. 41. Given a minheap find the max element. Sol) max element will always be at leaf, take the last element in heap and find its parent which will be always the last non leaf node. Find the max element after the last non leaf node and last node. 42. Convert an array to heap. a) Sort the array and sorted array is always min heap. b) Add the first element in heap and then second. Now particulate for heap property. Keep adding element and managing heap property. c) Bottom up heap building ( I really did not understand this concept. Please google). 43. Kth element in a Min heap. a) Bruteforce: Call delete min () k times. TC (nl...