Implement rand7() using rand5()

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

Problem Write a method to generate a random number between 1 and 7, given a method that generates a random number between 1 and 5. (i.e., implement rand7() using rand5()). Solution This appear to be one of those probabilistic analysis questions. You should be familiar with the concept of expected value, as it could be extremely helpful in probabilistic analysis. This solution is based upon Rejection Sampling. The main idea is when you generate a number in the desired range, output that number immediately. [Read More]
kodeknight  Moderate  CrackingTheCodingInterview  understand 

Encode XML

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

Problem Since XML is very verbose, you are given a way of encoding it where each tag gets mapped to a pre-defined integer value The language/grammar is as follows: Element –> Element Attr* END Element END [aka, encode the element tag, then its attributes, then tack on an END character, then encode its children, then another end tag] Attr –> Tag Value [assume all values are strings] END –> 01 [Read More]
kodeknight  Moderate  CrackingTheCodingInterview 

Find the frequency of a word in a book

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

Problem Design a method to find the frequency of occurrences of any given word in a book. Solution Just scan the word, trim it and put in hashtable. Now, when searching lower case it and search it. Hashtable<String, Integer> setupDictionary(String book) { Hashtable<String, Integer> table = new Hashtable<String, Integer>(); for (String word : book) { word = word.toLowerCase(); if (word.trim() != "") { if (!table.containsKey(word)) table.put(word, 0); table.put(word, table. [Read More]
kodeknight  Moderate  CrackingTheCodingInterview 

Generate english phrase that describes a integer

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

Problem Given an integer between 0 and 999,999, print an English phrase that describes the integer (e.g., “One Thousand, Two Hundred and Thirty Four”). Solution private static final Map<Integer, String> digitsToStrings; static { Map<Integer, String> aMap = new HashMap<Integer, String>(); aMap.put(1, "One"); aMap.put(2, "Two"); aMap.put(3, "Three"); aMap.put(4, "Four"); aMap.put(5, "Five"); aMap.put(6, "Six"); aMap.put(7, "Seven"); aMap.put(8, "Eight"); aMap.put(9, "Nine"); aMap.put(10, "Ten"); aMap.put(11, "Eleven"); aMap.put(12, "Twelve"); aMap.put(13, "Thirteen"); aMap.put(14, "Fourteen"); aMap. [Read More]
kodeknight  Moderate  CrackingTheCodingInterview 

Game of Master Mind

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

Problem The Game of Master Mind is played as follows: The computer has four slots containing balls that are red (R), yellow (Y), green (G) or blue (B). For example, the computer might have RGGB (e.g., Slot #1 is red, Slots #2 and #3 are green, Slot #4 is blue). You, the user, are trying to guess the solution You might, for example, guess YRGB. When you guess the correct color for the correct slot, you get a “hit” If you guess a color that exists but is in the wrong slot, you get a “pseudo-hit”. [Read More]
kodeknight  Moderate  incomplete  CrackingTheCodingInterview 

Find the maximum (or minimum) of two numbers (or morenumbers) without use of comparison operators or if-else

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

Problem Write a method which finds the maximum of two numbers You should not use if-else or any other comparison operator EXAMPLE Input: 5, 10 Output: 10 Solution Method 1 - Using arithematic operator Let a is greater than b, and M is the mid point, then: then max = (a + b) / 2 + |a - b| / 2 Method 2 - Using most significant bit [Read More]
kodeknight  Moderate  CrackingTheCodingInterview  bits 

Number of trailing zeros in a factorial

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

Problem Write an algorithm which computes the number of trailing zeros in n factorial. Solution The trailing zeros are constructed by multiplying pairs of 2 and 5. So to count the number of trailing zeros, we need to count the number of pairs of 2 and 5. For a factorial, there are way more number of factor 2 than 5 so we just need to count the number of factor 5 in the factorial. [Read More]
kodeknight  CrackingTheCodingInterview 

Check if someone has won tic-tac-toe

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

Problem Design an algorithm to figure out if someone has won in a game of tic-tac-toe. Solution I’ve written a game of tic-tac-toe in Java, and my current method of determining the end of the game accounts for the following possible scenarios for the game being over: The board is full, and no winner has yet been declared: Game is a draw. Cross has won. Circle has won. [Read More]
kodeknight  incomplete  CrackingTheCodingInterview 

Cracking the coding interview questions

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

The book - cracking the coding interview has list of questions. The list of questions and solutions is not comprehensive, but I guess that is the point. Coding interviews are about judging your approach to problems rather than specific solutions. I found that some of the problems were quite simple compared to the difficulty level currently in force at various companies. In particular would like to see more dynamic programming problems, but I think the author covers all the main questions, which sharpens our mind to focus on the problem solving, and is a very good starting point, which covers almost 80-90% problem solving exercises. [Read More]
kodeknight  Page  CrackingTheCodingInterview 

Solve Towers of Hanoi using stack

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

Problem In the classic problem of the Towers of Hanoi, you have 3 rods and N disks of different sizes which can slide onto any tower. The puzzle starts with disks sorted in ascending order of size from top to bottom (e.g., each disk sits on top of an even larger one). You have the following constraints: (A) Only one disk can be moved at a time. (B) A disk is slid off the top of one rod onto the next rod. [Read More]
kodeknight  CrackingTheCodingInterview  stack