Get Sentence from raw text

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

Problem Given a raw sentence without spaces and dictionary of words, break the raw sentence to sentence of words. String getSentence(String text, Setdictionary); // text is a string without spaces, you need to insert spaces into text, so each word seperated by the space in the resulting string exists in the dictionary, return the resulting string This problem is also known as wordbreaker problem. Example // getSentence(“iamastudentfromwaterloo”, {“from, “waterloo”, “hi”, “am”, “yes”, “i”, “a”, “student”}) -> “i am a student from waterloo” [Read More]
backtracking  kodeknight  String  java-code  Dynamic Programming  DP  recursion  parse  understand 

Suggest the selling time and buying time of a share based on stock price prediction

 Posted on April 14, 2014  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Problem You have an API to predict stock values of a particular share, The API is StockPrediction predict(int stockid); where class StockPrediction{ Date time: float value; } using this API develop another API which will suggest the best selling time and buying time of a share (you have to call the predict API N number of times and from the StockPredictions provide the best buy time and sell time for the stock) [Read More]
kodeknight  inmobi  stock  Dynamic Programming  DP 

Maximum product sub-array

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

Problem Given an integer array with negative numbers and zero find the subarray with maximum product, i.e. find the contiguous array elements that produce maximum product. Also find the sub array. Example For 7 -3 -1 2 -40 0 3 6, the max subarray product = -1 * 2 * -40 = 80 For -3 7 2 0 -5 7 -2 -2 2, the maximum subarraproduct = -5 * 7 * -2 = 70 [Read More]
kodeknight  contiguous  Dynamic Programming  DP  product 

Circus tower sorting problem

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

Problem A circus is designing a tower routine consisting of people standing atop one another’s shoulders. For practical and aesthetic reasons, each person must be both shorter and lighter than the person below him or her. Given the heights and weights of each person in the circus, write a method to compute the largest possible number of people in such a tower. EXAMPLE: Input (ht, wt): (65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110) [Read More]
kodeknight  Dynamic Programming  DP  CrackingTheCodingInterview  sorting-and-searching 

Print all combinations of n balanced parentheses

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

Problem Implement an algorithm to print all valid (i.e., properly opened and closed) combinations of n-pairs of parentheses. Example Input 3 (i.e., 3 pairs of parentheses) Output ()()(), ()(()), (())(), ((())) Solution This is a classic combinatorial problem that manifests itself in many different ways. Such kind of strings are called Dyck strings (see more here), which contain n X’s and n Y’s such that no initial segment of the string has more Y’s than X’s. [Read More]
backtracking  kodeknight  Dynamic Programming  DP  recursion  CrackingTheCodingInterview  parentheses 

Two egg puzzle

 Posted on March 26, 2014  (Last modified on August 7, 2020)  |  8 minutes  |  Kinshuk Chandra

Problem: There is a building of 100 floors. If an egg drops from the Nth floor or above it will break. If it’s dropped from any floor below, it will not break. You’re given 2 eggs. Find N, while minimizing the number of drops for the worst case. Solution This is similar as binary search. If we have unlimited number of eggs, we only need 7 (log 100 to base 2) to find N i. [Read More]
kodeknight  brainteaser  Dynamic Programming  DP  recursion  CrackingTheCodingInterview 

Avid TV watcher

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

Problem There is a TV avid person, who wants to spend his maximum time on TV. There are N channels that telecast programs of different length at different timings. WAP to find the program and channel number so that the person can spend his max time on TV. Condition: If he watches a program, he watches it completely. Example: Channel1: prg1: 8:00 am - 9:00am prg2: 9:30 am - 12:00 am [Read More]
kodeknight  Dynamic Programming  DP 

Maximum weight independent set (WIS) graph problem using DP

 Posted on November 5, 2013  (Last modified on August 7, 2020)  |  7 minutes  |  Kinshuk Chandra

Input - A path graph G = (V,E) with non - negative weights on vertices eg.Consider the graph with vertex weights - 1,4,5,4 Desired output - subset of non-adjacent vertices - an independent set of maximum total weights. Solutions Brute force polynomial time, so lets do better. greedy approach Greedy algos are easy to implement but are sometimes not correct. To apply greedy approach here we have to iteratively choose the max-weight vertex not adjacent to any previously chosen vertex. [Read More]
Graph  kodeknight  Dynamic Programming  DP