CrackingTheCodingInterview

One shot or at least two shots in three games?

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

Problem: You have a basketball hoop and someone says that you can play 1 of 2 games. Game #1: You get one shot to make the hoop. Game #2: You get three shots and you have to make 2 of 3 shots. If p is the probability of making a particular shot, for which values of p should you pick one game or the other? Solution: For game #1, you have probability p of winning. [Read More]

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

Searching in a sorted array of strings with empty strings

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

Problem Given a sorted array of strings which is interspersed with empty strings, write a method to find the location of a given string. Example: find “ball” in [“at”, “”, “”, “”, “ball”, “”, “”, “car”, “”, “”, “dad”, “”, “"] will return 4 Example: find “ballcar” in [“at”, “”, “”, “”, “”, “ball”, “car”, “”, “”, “dad”, “”, “"] will return -1 Solution The worst we can do is O(n) where we just do a linear search. [Read More]

kodeknight binary search CrackingTheCodingInterview sorting-and-searching

Sorting a 2GB file with one string per line

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

Problem If you have a 2GB file with one string per line, which sorting algorithm would you use to sort the file and why? Solution When an interviewer gives a size limit of 2GB, it should tell you something – in this case, it suggests that they don’t want you to bring all the data into memory. So what do we do? We only bring part of the data into memory. [Read More]

kodeknight sorting CrackingTheCodingInterview sorting-and-searching limited memory

Sort an array of strings so that anagrams are next to each other

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

Problem Write a method to sort an array of strings so that all the anagrams are next to each other. Example INPUT : "xyz", "ca", "ab", "ac", "ba", "zyx" OUTPUT: "ab", "ba", "ac", "ca", "xyz", "zyx" Lets see the solutions now. Solution Method 1 - Using bubble sort Check if two pairs of strings are anagrams or not, if yes, swap. Java code private static boolean areAnagrams(String s1, String s2) { if (s1. [Read More]

kodeknight sorting anagrams compare CrackingTheCodingInterview sorting-and-searching

Merge two sorted arrays - One having big enough buffer to hold another

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

Problem You are given two sorted arrays, A and B, and A has a large enough buffer at the end to hold B. Write a method to merge B into A in sorted order. Another way to ask same question Given a sorted array of size n with n elements (array1) and a sorted array of size 2n with n elements (array2), merge them to get a sorted array of size 2n. [Read More]

kodeknight merge sorting two-arrays two-sorted-arrays CrackingTheCodingInterview sorted-array sorting-and-searching

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