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 

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 

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 

DFS (Depth First Search) on tree or graph

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

Consider this tree (which is a graph without a cycle) : Now DFS means traversing to the depth…and then going up, so here DFS traversal will result in 5 2 -4 3 21 19 25. We can use non recursive as well recursive approach to solve this problem. A depth first search (DFS) through a tree starts at the root and goes straight down a single branch until a leaf is reached. [Read More]
backtracking  Graph  search  tree  kodeknight  sorting  DFS  incomplete  traversal  binary-search-tree  BST  graph-search 

All permutations of a string

 Posted on September 7, 2011  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

small trick ,but a very nice solution for duplicat…

nikhil - Feb 4, 2014

small trick ,but a very nice solution for duplicates!!!!

Thanks Nikhil. :)

can u please write the main function for duplicate program. I ran the duplicate program and it is not giving me the desired output

backtracking  Permutation and Combination  kodeknight  String  Permutation  Interview Question  recursion  CrackingTheCodingInterview  java 

All permutations of a string

 Posted on September 7, 2011  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Problem Write a method to compute all permutations of a string. Example For a string of length n, there are n! permutations. INPUT: “abc” OUTPUT: “abc” “acb” “bac” “bca” “cab” “cba” So, we have 3! = 6 items for string abc. Solution There are several ways to do this. Common methods use recursion, memoization, or dynamic programming. The basic idea is that you produce a list of all strings of length 1, then in each iteration, for all strings produced in the last iteration, add that string concatenated with each character in the string individually. [Read More]
backtracking  Permutation and Combination  kodeknight  String  Permutation  Interview Question  recursion  CrackingTheCodingInterview  java 

Solve the Rat In A Maze problem using backtracking.

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

This is one of the classical problems of computer science. There is a rat trapped in a maze. There are multiple paths in the maze from the starting point to the ending point. There is some cheese at the exit. The rat starts from the entrance of the maze and wants to get to the cheese. This problem can be attacked as follows. Have a m*m matrix which represents the maze. [Read More]
backtracking  Algorithms  kodeknight  interview  programming Questions 

Representing the Solution Space

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

This section presents an interface for the nodes of a solution space. By using an interface, we hide the details of the specific problem to be solved from the backtracking algorithm. In so doing, it is possible to implement completely generic backtracking problem solvers. Although a backtracking algorithm behaves as if it is traversing a solution tree, it is important to realize that it is not necessary to have the entire solution tree constructed at once. [Read More]
backtracking  Algorithms  kodeknight 

Balancing Scales

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

Consider the set of scales shown in Figure . Suppose we are given a collection of n weights, , and we are required to place all of the weights onto the scales so that they are balanced.  Figure: A set of scales. The problem can be expressed mathematically as follows: Let represent the pan in which weight is placed such that The scales are balanced when the sum of the weights in the left pan equals the sum of the weights in the right pan, [Read More]
backtracking  Algorithms  kodeknight