Cracking Programming Interviews 500 Questions with Solutions

Part I Algorithms and Data Structures

1 Fundamentals

Approximating the square root of a number
Generating Permutation Efficiently
Unique 5-bit Sequences
Select Kth Smallest Element
The Non-Crooks Problem
Is this (almost) sorted?
Sorting an almost sorted list
The Longest Upsequence Problem
Fixed size generic array in C++
Seating Problem
Segment Problems
Exponentiation
Searching two-dimensional sorted array
Hamming Problem
Constant Time Range Query
Linear Time Sorting
Writing a Value as the Sum of Squares
The Celebrity Problem
Transport Problem
Find Length of the rope
Switch Bulb Problem
In, On or Out
The problem of the balanced seg
The problem of the most isolated villages

2 Arrays

The Plateau Problem
Searching in Two Dimensional Sequence
The Welfare Crook Problem
2D Array Rotation
A Queuing Problem in A Post Office
Interpolation Search
Robot Walk
Linear Time Sorting
Write as sum of consecutive positive numbers
Print 2D Array in Spiral Order
The Problem of the Circular Racecourse
Sparse Array Trick
Bulterman’s Reshuffling Problem
Finding the majority
Mode of a Multiset
Circular Array
Find Median of two sorted arrays
Finding the missing integer
Finding the missing number with sorted columns
Re-arranging an array
Switch and Bulb Problem
Compute sum of sub-array
Find a number not sum of subsets of array
Kth Smallest Element in Two Sorted Arrays
Sort a sequence of sub-sequences
Find missing integer
Inplace Reversing
Find the number not occurring twice in an array

3 Trees

Lowest Common Ancestor(LCA) Problem
Spying Campaign


4 Dynamic Programming

Stage Coach Problem
Matrix Multiplication
TSP Problem
A Simple Path Problem
String Edit Distance
Music recognition
Max Sub-Array Problem

5 Graphs

Reliable distribution
Independent Set
Party Problem

6 Miscellaneous

Compute Next Higher Number
Searching in Possibly Empty Two Dimensional Sequence
Matching Nuts and Bolts Optimally
Random-number generation
Weighted Median
Compute a^n
Compute a^n revisited
Compute the product a × b
Compute the quotient and remainder
Compute GCD
Computed Constrained GCD
Alternative Euclid’ Algorithm
Revisit Constrained GCD
Compute Square using only addition and subtraction
Factorization
Factorization Revisited
Decimal Representation
Reverse Decimal Representation
Solve Inequality
Solve Inequality Revisited
Print Decimal Representation
Decimal Period Length
Sequence Periodicity Problem
Compute Function
Emulate Division and Modulus Operations
Sorting Array of Strings : Linear Time
LRU data structure
Exchange Prefix and Suffix

7 Parallel Algorithms

Parallel Addition
Find Maximum
Parallel Prefix Problem
Finding Ranks in Linked Lists
Finding the k th Smallest Element

8 Low Level Algorithms

Manipulating Rightmost Bits
Counting 1-Bits
Counting the 1-bits in an Array
Computing Parity of a word
Counting Leading/Trailing 0’s
Bit Reversal
Bit Shuffling
Integer Square Root
Newton’s Method
Integer Exponentiation
LRU Algorithm
Shortest String of 1-Bits
Fibonacci words
Computation of Power of 2
Round to a known power of 2
Round to Next Power of 2
Efficient Multiplication by Constants
Bit-wise Rotation
Gray Code Conversion
Average of Integers without Overflow
Least/Most Significant 1 Bit
Next bit Permutation
Modulus Division

Part II C++

8 General
9 Constant Expression
10 Type Specifier
11 Namespaces
12 Misc
13 Classes
14 Templates
15 Standard Library