Cracking Programming Interviews: 350 Questions with Solutions (Paperback)

This book contains 350 programming questions most frequently asked in technical interviews in top technical companies including Facebook, Microsoft, Google, Apple, Yahoo and others. Detailed solutions are provided for all of these including tips and techniques for solving similar problems.


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
K th 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

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
The Parallel Prefix Problem
Finding Ranks in Linked Lists
Finding the k th Smallest Element

Part II C++

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

這本書包含了在頂尖科技公司的技術面試中最常問到的350個程式設計問題，包括Facebook、Microsoft、Google、Apple、Yahoo等公司。書中提供了這些問題的詳細解答，並提供解決類似問題的技巧和方法。

第一部分 算法和資料結構
1 基礎知識
- 逼近一個數字的平方根
- 高效生成排列
- 獨特的5位元序列
- 選擇第K小的元素
- 非騙子問題
- 是否（幾乎）有序？
- 排序幾乎有序的列表
- 最長上升子序列問題
- C++中固定大小的通用陣列
- 座位問題
- 區間問題
- 指數運算
- 搜索二維有序陣列
- 漢明問題
- 常數時間範圍查詢
- 線性時間排序
- 將一個值表示為平方和
- 名人問題
- 運輸問題
- 找到繩子的長度
- 開關燈泡問題
- 在內還是在外
- 平衡段的問題
- 最孤立的村莊問題

2 陣列
- 高原問題
- 在二維序列中搜索
- 福利騙子問題
- 二維陣列旋轉
- 郵局排隊問題
- 插值搜索
- 機器人行走
- 線性時間排序
- 將正整數表示為連續數字的和
- 螺旋順序打印二維陣列
- 圓形賽道問題
- 稀疏陣列技巧
- Bulterman的重排問題
- 找到眾數
- 多重集合的眾數
- 循環陣列
- 找到兩個已排序陣列的中位數
- 找到缺失的整數
- 找到有排序列的缺失數字
- 重新排列陣列
- 開關和燈泡問題
- 計算子陣列的總和
- 找到一個不是陣列子集和的數字
- 兩個已排序陣列中的第K小元素
- 對子序列進行排序
- 找到缺失的整數
- 原地反轉
- 找到陣列中不重複出現的數字

3 樹
- 最低共同祖先（LCA）問題
- 間諜活動

4 動態規劃
- 字串編輯距離
- 音樂識別
- 最大子陣列問題

5 圖
- 可靠分配
- 獨立集
- 派對問題

6 其他
- 計算下一個更大的數字
- 在可能為空的二維序列中搜索
- 最佳匹配螺帽和螺栓
- 隨機數生成
- 加權中位數
- 計算a的n次方
- 重新計算a的n次方
- 計算a和b的乘積
- 計算商和餘數
- 計算最大公約數
- 計算受限制的最大公約數
- 替代歐幾里得算法
- 重新訪問受限制的最大公約數
- 只使用加法和減法計算平方
- 因式分解
- 重新訪問因式分解
- 十進制表示
- 反向十進制表示
- 解不等式
- 重新訪問解不等式
- 打印十進制表示
- 十進制循環節長度
- 序列週期性問題
- 計算函數
- 模擬除法和取模運算
- 字串陣列排序：線性時間
- LRU資料結構
- 交換前綴和後綴

7 並行算法
- 並行加法
- 找到最大值
- 並行前綴問題
- 在鏈表中找到排名
- 找到第k小的元素

第二部分 C++
8 一般
9 常數表達式
10 型別指定符
11 命名空間
12 其他
13 類別
14 模板
15 標準庫