Print all sequences of given length

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

Problem Given two integers k and n, write a function that prints all the sequences of length k composed of numbers 1,2..n. You need to print these sequences in sorted order. Examples Example 1 Input: k = 2, n = 3 Output: 1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3 Example 2 Input: k = 3, n = 4 Output: 1 1 1 1 1 2 1 1 3 1 1 4 1 2 1 . [Read More]
kodeknight  recursion  sequence  maths 

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 

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 

The Celebrity Problem

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

Problem In a party of N people, only one person is known to everyone. Such a person may be present in the party, if yes, (s)he doesn’t know anyone in the party. We can only ask questions like “does A know B? “. Find the stranger (celebrity) in minimum number of questions. Solution We can describe the problem input as an array of numbers/characters representing persons in the party. [Read More]
Graph  kodeknight  recursion  celebrity  stack 

Eight Queen Puzzle (likewise N Queen)

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

Problem Write an algorithm to print all ways of arranging eight queens on a chess board so that none of them share the same row, column or diagonal. (image courtesy) Solution This is a classic problem to implement using backtracking. It has 92 distinct solutions. If solutions that differ only by symmetry operations (rotations and reflections) of the board are counted as one, the puzzle has 12 fundamental solutions. [Read More]
backtracking  kodeknight  queen  chess  incomplete  recursion  CrackingTheCodingInterview 

Number of ways of representing n cents using quarters, dimes, nickels and pennies

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

Problem Given an infinite number of quarters (25 cents), dimes (10 cents), nickels (5 cents) and pennies (1 cent), write code to calculate the number of ways of representing n cents. Solution Method 1 - Recursion This is a recursive problem, so let’s figure out how to do makeChange(n) using prior solutions (i.e., sub-problems). Let’s say n = 100, so we want to compute the number of ways of making change of 100 cents. [Read More]
kodeknight  coin  recursion  CrackingTheCodingInterview 

Implement the “paint fill” function

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

Problem Implement the “paint fill” function that one might see on many image editing programs. That is, given a screen (represented by a 2-dimensional array of Colors), a point, and a new color, fill in the surrounding area until you hit a border of that color. Solution Again, the solution falls in the bucket of recursion, backtracking. Method 1 - Recursion First, let’s visualize how this method works. [Read More]
kodeknight  recursion  CrackingTheCodingInterview 

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 

All possible paths for a robot moving along a NxN grid

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

Problem Imagine a robot sitting on the upper left hand corner of an NxN grid. The robot can only move in two directions: right and down. How many possible paths are there for the robot? FOLLOW UP Imagine certain squares are “off limits”, such that the robot can not step on them. Design an algorithm to get all possible paths for the robot.  Solution We solved the similar question here, where we had to find the count of number of paths. [Read More]
kodeknight  recursion  CrackingTheCodingInterview 

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