This is just studying for coding interviews. It loosely follows "Cracking the Coding Interview" by Gayle Laakmann McDowell. The code is structured by keeping the implementations in the lib directory and the study questions in the tests directory. The build system, meson, supports pulling down other projects and integrating them. CPPUTEST is pulled down with a wrap file.

Initialization

Toolchain

I use devbox to handle the toolchain dependencies. If you have not installed it, I have found it best to first install Nix via the Determinate Systems installer and then use the Jetify Devbox installer:

  curl --proto '=https' --tlsv1.2 -sSf -L https://install.determinate.systems/nix | sh -s -- install
  curl -fsSL https://get.jetify.com/devbox | bash

After that just run the following in a shell from this directory:

  devbox shell

On the first run it will take a few minutes to install the required packages and their dependencies. On subsequent runs it should be pretty fast.

The Build System (Meson)

Initialize build directory and pull down the sub projects via the meson "wrap" feature:

  meson setup build

Testing

To run the tests:

  meson test -C build

Plan

Arrays `[3/6]`

Is Unique (CTCI: 1.1)
Check permutation (CTCI: 1.2)
String Compression (CTCI: 1.6)
Rotate Matrix (CTCI: 1.7)
Zero Matrix (CTCI: 1.8)
Sliding Window (GfG: Sliding Window Technique)

Linked Lists `[1/6]`

Remove Duplicates (CTCI: 2.1)
Return Kth to Last (CTCI: 2.2)
Delete middle node (CTCI: 2.3)
Partition (CTCI: 2.4)
Loop Detection (CTCI: 2.8)

Stacks and Queues `[0/2]`

Stack Min (CTCI: 3.1)
Sort Stack (CTCI: 3.5)

Trees and Graphs `[7/9]`

Implement binary tree object
- Insert breadth first
Recursive Pre-order traversal
Recursive In-order traversal
Recursive Post-order traversal
Non-Recursive Pre-order traversal
Non-Recursive In-order traversal
Non-Recursive Post-order traversal
Min Heap
Binary Search

C/C++ `[2/5]`

Code as static library
Templates
Inheritance, base/parent classes
Smart pointers
Threads and locks

CTCI Advanced

LRU Cache (CTCI: 16.25)
- Design and build a "least recently used" cache, which evicts the least recently used item. The cache should map from keys to values (allowing you to insert and retrieve a value associated with a particular key) and be initialized with a max size. When it is full, it should evict the least recently used item.

CTCI Hard

Baby Names (CTCI: 17.7)
- Each year, the government releases a list of the 10000 most common baby names and their frequencies (the number of babies with that name). The only problem with this is that some names have multiple spellings. For example,"John" and ''.Jon" are essentially the same name but would be listed separately in the list. Given two lists, one of names/frequencies and the other of pairs of equivalent names, write an algorithm to print a new list of the true frequency of each name. Note that if John and Jon are synonyms, and Jon and Johnny are synonyms, then John and Johnny are synonyms. (It is both transitive and symmetric.) In the final list, any name can be used as the "real" name.
- EXAMPLE
  - Input:
    - Names: John(15),Jon(12), Chris(13),Kris(4),Christopher(19)
    - Synonyms:(Jon,John),(John,Johnny),(Chris,Kris),(Chris, Christopher)
    - Output: John(27), Kris(36)
Continuous Median (CTCI: 17.20)
- Numbers are randomly generated and passed to a method. Write a program to find and maintain the median value as new values are generated.
Volume of Histogram (CTCI: 17.21)
- Imagine a histogram (bar graph). Design an algorithm to compute the volume of water it could hold if someone poured water across the top. You can assume that each histogram bar has width 1.
- EXAMPLE
  - (Black bars are the histogram. Gray is water.)
  - Input:{0, 0, 4, 0, 0, 6, 0, 0, 3, 0, 5, 0, 1, 0, 0, 0}
    - Book has an image here
  - Output:26

Readme.org

Data Structures And Algorithms Studying in C++

Overview