Find pairs of integers in an array that sum to a value

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

Problem Design an algorithm to find all pairs of integers within an array which sum to a specified value. Solution  We have found a pair of elements in an array which sum upto a given number already, this is a known problem called 2-sum problem. We know we can solve this problem in O(n) time. Let T be the sum. Method 1 - Using Hash table solution [Read More]
kodeknight  Moderate  CrackingTheCodingInterview 

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 

Maximum continuous sum subarray problem

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

Problem You are given an array of integers (both positive and negative). Find the continuous sequence with the largest sum. Return the sum. EXAMPLE Input: {2, -8, 3, -2, 4, -10} Output: 5 (i.e., {3, -2, 4}) Solution  Method 1 - Brute force The outer loop picks the beginning element, the inner loop finds the maximum possible sum with first element picked by outer loop and compares this maximum with the overall maximum. [Read More]
max  kodeknight  sub-array  Dynamic Programming  DP  Moderate  array  integer-array  CrackingTheCodingInterview 

Swap two number in place without temporary variables.

 Posted on November 27, 2009  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Problem Write a function to swap two number in place without temporary variables. Solution Method1 - The XOR or Exclusive trick In C this should work: a ^= b ^= a ^= b; to simplify : a=a^b; b=a^b; a=a^b; OR a^=b; b^=a; a^=b; Following are operations in XOR 0^0=0 0^1=1 1^0=1 1^1=0 Hence, we have: a=a^b: ‘a’ will save all the bits that a differs from b: if the bit that ‘a’ and ‘b’ differ, it gets 1, otherwise 0. [Read More]
kodeknight  programming  Moderate  swap  CrackingTheCodingInterview  bits