Maximum continuous sum subarray problem

 Posted on January 5, 2012  (Last modified on August 7, 2020)  |  6 minutes  |  Kinshuk Chandra

Problem You are given an array of integers (both positive and negative). Find the continuous sequence with the largest sum. Return the sum. EXAMPLE Input: {2, -8, 3, -2, 4, -10} Output: 5 (i.e., {3, -2, 4}) Solution  Method 1 - Brute force The outer loop picks the beginning element, the inner loop finds the maximum possible sum with first element picked by outer loop and compares this maximum with the overall maximum. [Read More]
max  kodeknight  sub-array  Dynamic Programming  DP  Moderate  array  integer-array  CrackingTheCodingInterview 

Huffman Codes

 Posted on January 5, 2012  (Last modified on August 7, 2020)  |  5 minutes  |  Kinshuk Chandra

Background When we encode characters in computers, we assign each an 8-bit code based on an ASCII chart. But in most files, some characters appear more often than others. So wouldn’t it make more sense to assign shorter codes for characters that appear more often and longer codes for characters that appear less often? This is exactly what Claude Shannon and R.M. Fano were thinking when they created the first compression algorithm in the 1950’s. [Read More]
Algorithms  kodeknight  Dynamic Programming  DP  incomplete 

Print pascal's triangle

 Posted on January 5, 2012  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Pascal’s triangle is based on this formula : C(n, r) = C(n-1, r-1) + C(n-1, r) int Pascal(int n, int r) { if (r == 0) return 1; if (n == 0) return 0; return Pascal(n - 1, k - 1) + Pascal(n - 1, r); } In cpp, this recursive routine can use both memoization and recursion: public static long nCr(int n, int r){ static unsigned long table256256256256 = {0}; if(r == 0 || n == r) { return tablennrr = 1; } if(r == 1) { return tablennrr = n; } if(r > n / 2) { return tablennrr = ncr(n, n - r); } return tablennrr = tablen−1n - 1r−1r - 1 + tablen−1n - 1rr; } In java, you can use a class and maintain the array outside the function and just use the function similar to above to update that array and return the value in the end. [Read More]
memoization  kodeknight  Dynamic Programming  DP  recursion 

Convert array of positive numbers to sorted array

 Posted on January 3, 2012  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

You are given an array of positive integers. Convert it to a sorted array with minimum cost. Only valid operation are Decrement -> cost = 1 Delete an element completely from the array -> cost = value of element For example: 4,3,5,6, -> cost 1 (decrement 4) 10,3,11,12 -> cost 3 (delete 3) Trying out DP We can make the DP more efficient You don’t need to scan the whole previous column when calculating costs of decrementing. [Read More]
conversion  kodeknight  Dynamic Programming  DP  array  sorted-array 

Minimum number of coins to get particular amount, given multiple denomination

 Posted on January 2, 2012  (Last modified on August 7, 2020)  |  5 minutes  |  Kinshuk Chandra

Question: You are given some denominations of coins in an array (int denom[])and infinite supply of all of them. Given an amount (int amount OR S), find the minimum number of coins required to get the exact amount. Problem statement “Given a list of N coins, their values (V1, V2, … , VN), and the total sum S. Find the minimum number of coins the sum of which is S (we can use as many coins of one type as we want), or report that it’s not possible to select coins in such a way that they sum up to S. [Read More]
kodeknight  knapsack problem  coin  Dynamic Programming  DP  Amazon  min 

Get maximum sum from coins in a line

 Posted on January 2, 2012  (Last modified on August 7, 2020)  |  5 minutes  |  Kinshuk Chandra

Question: There are n coins in a line. Two players take turns to take a coin from one of the ends of the line until there are no more coins left. The player with the larger amount of money wins. Assume that you go first, describe an algorithm to compute the maximum amount of money you can win. Answer: If we assume that n is even then there is simple strategy to ensure that you win. [Read More]
kodeknight  Dynamic Programming  DP 

Find optimal number of jumps to reach last element

 Posted on January 2, 2012  (Last modified on August 7, 2020)  |  4 minutes  |  Kinshuk Chandra

Question: Given an array, start from the first element and reach the last by jumping. The jump length can be at most the value at the current position in the array. Optimum result is when you reach the goal in minimum number of jumps. Example: Given array A = {2,3,1,1,4} Possible ways to reach the end (index list) 0,2,3,4 (jump 2 to index 2, and then jump 1 to index 3 and then jump 1 to index 4) 0,1,4 (jump 1 to index 1, and then jump 3 to index 4) Since second solution has only 2 jumps it is the optimum result. [Read More]
kodeknight  Dynamic Programming  DP 

Max possible sum of non-consecutive elements

 Posted on January 2, 2012  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Below code works for -ve numbers : public static … vikramdpatil - May 4, 2014Below code works for -ve numbers : public static int findMaxSum(int arr[]) { if (arr.length == 0) return 0; if (arr.length == 1) return arr[0]; int a = arr[0]; int b = Math.max(arr[0], arr[1]); int c = b; for(int i=2; i<arr.length; i++) { c = Math.max(arr[i], Math.max(b, arr[i] + a)); a = b; // a now becomes second last sum [Read More]
kodeknight  Dynamic Programming  DP 

Max possible sum of non-consecutive elements

 Posted on January 2, 2012  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Question: There is an integer array consisting positive numbers only. Find maximum possible sum of elements such that there are no 2 consecutive elements present in the sum. Example: If given array is (6, 4, 2, 8, 1), the answer will be 14 (8+6). This is the maximum sum we can obtain without taking two consecutive elements. Answer: To solve these type of question, first thing is to find a recurring relation. [Read More]
kodeknight  Dynamic Programming  DP 

Maximum size square sub-matrix with all 1s

 Posted on January 2, 2012  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Question: Given a matrix consisting only 0s and 1s, find the maximum size square sub-matrix with all 1s. Example: Consider the below matrix. 0 1 1 0 1 1 1 0 1 0 0 1 1 1 0 1 1 1 1 0 1 1 1 1 1 0 0 0 0 0 The maximum square sub-matrix with all ‘1’ bits is from (2,1) to (4,3) 1 1 1 1 1 1 1 1 1 Answer: [Read More]
kodeknight  Dynamic Programming  DP  square matrix  google  matrix