# Cracking the coding interview exercises and notes

If you can't afford to buy the book, you can find a free pdf [here](https://github.com/alxerg/Books-1/blob/master/Cracking%20the%20Coding%20Interview%2C%206th%20Edition%20189%20Programming%20Questions%20and%20Solutions.pdf) (last updated on 2020.10.09).

## Introduction

1. Big O
2. Technical questions

## Chapter 1 Arrays and strings

* check unique characters
* check if permutation
* replace character by substring
* Levenshtein distance
* String compression
* Matrix rotation
* String rotation
* Hash tables (chapter 7)
* Magic index (chapter 8)
* Search in sorted matrix (chapter 10)

## Chapter 2 Linked lists

* Remove duplicates
* Return kth to last
* Delete middle node
* Partition list
* Sum lists
* Check if palindrome
* Insert node at beginning
* Insert node at end
* Reverse list, single and double linked
* List intersection
* Loop detection

## Chapter 3 Stacks and queues

* 3 stacks in array
* Min function in stack
* List of stacks
* Queue via stack
* Sort stack
* Animal shelter (enqueue and dequeue with ordering)

## Chapter 4 Trees and graphs

* Find route between nodes in graph
* Create minimal binary search tree from array
* Create a linked list for each depth in the tree

## Chapter 5 Bit manipulation

* Insert bit
* Binary to string
* Flip bit to create longest sequence of 1s
* (( n & (n-1)) == 0). n=?
* How many different bits do two numbers have. 11001 vs. 11010 = 2. Levenstein distance

## Chapter 6 Math and logic puzzles

* Prime numbers

## Chapter 7 Object-oriented design

* Call center
* Parking lot
* Chat server
* Hash tables

## Chapter 8 Recursion

* Triple step
* Robot in grid
* Magic index (index such that A\[i\] = 1)
* Power set
* Permutations of string with unique characters
* Permutations of string with duplicate characters

## Chapter 9 System design and scalability

* Stock data
* Social network
* Web crawler
* Duplicate URLs
* Cache
* Sales rank
* Personal finance manager

## Chapter 10 Sorting and searching

* Sorted merge
* Anagrams
* Search in rotated array
* Sorted search, no size
* Sorted matrix search
* Sparse search
* Sort big file
* Missing int
* Find duplicates
* Sorted matrix search
* Rank for stream

## Chapter 11 Testing

* Mistake
* Random crashes
* Chess test
* Test a pen
* Test an ATM

## Chapter 16 Moderate problems

* Write an integer in english
* Contiguous sequence or Maximum subarray
* Least Recently Used cache

## Chapter 18 Advanced topics

* Hash table collision resolution
* Rabin-Karp substring search
