Maximize the number of magical gems by passing through array of house

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

Problem There was a thief, he has to pass through colored house - which can be red or blue, and contain 0 or more gems. The property of these gems is they multiply the previous gems by the current gems in the house. The houses are in array and thief can only visit once to steal the gems, with the goal of maximizing the gems. Find the range of house where he can maximize the gems in such a way that number of red houses are even. [Read More]
kadane  Dynamic Programming  DP  directi  product 

Number of steps required to convert string 1 to string2 when only bring character to first index operation is giving

 Posted on May 3, 2015  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Problem Given 2 strings - s1 and s2, when only 1 operation is allowed - Moving character at a time but only to the first position. Example Example 1 Input s1 = abcd s2 = bacd Output Ans = 1 Reason, just move b forward and we get it. Example 2 Input A = (a)b(cd)e(f)g(hij) B = ahdjcifbeg Output Ans =7 Explanation A = (a)b(cd)e(f)g(hij) B = ahdjcifbeg Characters b,e,g are in the order, rest characters have to brought first. [Read More]
conversion  Dynamic Programming  DP  incomplete  directi 

Implement a function similar to diff command in linux

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

Problem Give logic for implementing “diff” command in Linux. Consider various test cases and explain what will happen in each. The two files are source code and are huge.. For e.g. File 1: 1-2-3-4 File 2: 1-3-4-2 Solution The operation of diff is based on solving the longest common sub-sequence problem. In this problem, you have two sequences of items: a b c d f g h j q z [Read More]
vmware  Dynamic Programming  DP 

Maximum single sell profit from stock

 Posted on April 30, 2015  (Last modified on August 7, 2020)  |  7 minutes  |  Kinshuk Chandra

Problem Suppose we are given an array of n integers representing stock prices on a single day. We want to find a pair (buyDay, sellDay), with buyDay ≤ sellDay, such that if we bought the stock on buyDay and sold it on sellDay, we would maximize our profit. OR Given an array arr[] of integers, find out the difference between any two elements such that larger element appears after the smaller number in arr[]. [Read More]
max  maxima  stock  divide and conquer  Dynamic Programming  DP  minima  array 

Find the largest subarray with sum of 0 in the given array

 Posted on April 17, 2015  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Problem An array contains both positive and negative elements, find the largest subarray whose sum equals 0. Example int[] input = {4, 6, 3, -9, -5, 1, 3, 0, 2} int output = {4, 6, 3, -9, -5, 1} of length 6 Solution Method 1 - Brute force This is simple. Will write later (incomplete) Method 2 - Storing the sum upto ith element in temp array Given an int[] input array, you can create an int[] tmp array where [Read More]
sub-array  Dynamic Programming  DP  incomplete  array  sum 

Maximum subset of Cuboid boxes that can fit into one another

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

Problem  Given a lot of cuboid boxes with different length, breadth and height. We need to find the maximum subset which can fit into each other. Example For example: If Box 1 has LBH as 7 8 9 If Box 2 has LBH as 5 6 8 If Box 3 has LBH as 5 8 7 If Box 4 has LBH as 4 4 4 then answer is 1,2,4 [Read More]
kodeknight  Dynamic Programming  DP  incomplete 

Given a set of numbers [1-N]. Subsets such that the sum of numbers in the subset is a prime number.

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

Problem Given a set of numbers [1-N] . Find the number of subsets such that the sum of numbers in the subset is a prime number. Solution  Method 1 - Using DP Maximum sum can be = N*(N+1) / 2 for any subset considered, as numbers are from 1 to N. Hence put S = (N*(N+1) / 2) in subset sum problem. For each number in the Sum S, check if there is subset of numbers from 1 to N that sum up to S - Yes that you can do with Subset Sum problem. [Read More]
kodeknight  Dynamic Programming  DP  subset  understand 

Petrol Bunk in a Circle.

 Posted on May 5, 2014  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Problem You have a circular track containing fuel pits at irregular intervals. The total amount of fuel available from all the pits together is just sufficient to travel round the track and finish where you started. Given the the circuit perimeter, list of each fuel pit location and the amount of fuel they contain, find the optimal start point on the track such that you never run out of fuel and complete circuit. [Read More]
kodeknight  Dynamic Programming  DP  google 

Get Sentence from raw text

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

DP Code Given Above Has Some Issue I Fixed It: st… PaNThErA - Dec 0, 2015DP Code Given Above Has Some Issue I Fixed It: static boolean wordBreak(String str, Set tokenMap) { int size = str.length(); if (size == 0) return true; // Create the DP table to store results of subroblems. The value wb[i] // will be true if str[0..i-1] can be segmented into dictionary words, // otherwise false. [Read More]
backtracking  kodeknight  String  java-code  Dynamic Programming  DP  recursion  parse  understand