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