Algorithms

I create this repository as part of my preparation to Coding Interviews in FAANG and other big companies.

The idea is to learn/practice skills of implementing well-known data structures and algorithms from scratch.

Note: We are not focusing much on supporting multiple data types in algorithms. This is not important part for Coding interviews and we are not building reusable library here.

Code in this repository represents a collection of Data Structures and algorithms from different sources:

• Gayle L. McDowell "Cracking Coding Interview"
• Robert Sedgewick, Kevin Wayne "Introduction to Algorithms, 3rd Edition" (CLRS for short)
• Thomas Cormen and others "Introduction to Algorithms, 3rd Edition"
• Leetcode
• DailyCodingTask
• other sources

For contribution and other questions feel free to contact me by email [email protected]

Table of content

• Other documents
• Data Structures
• Sort
• Sort in linear time
• Select
• Graph Algorithms
• Bitwise

Other documents

• Solutions for Cracking The Coding Interview
• Initialize Google Test library

Data Structures

• Vector
• Queue
• Stack
• Priority Queue
• 3 stacks as one vector
• Queue as stack

Sort

• Bubble sort O(n²)
• Insert sort O(n²)
• Heap sort O(n log(n))
• Merge sort O(n log(n))
• Quick sort Average: O(n log(n)). Worst: O(n²)
  • Quick sort
  • Randomized quick sort
  • Quick sort with Hoare partitioning

Sort in linear time

• Counting sort O(n + k)

Select

• Linear Select
• MinMax
• Quick Select

Graph Algorithms

• Union Find

Bitwise

Lots of information is available on this resource Bit Twiddling Hacks.

• Sum of two numbers without using "+/-" operations

RUN TESTS

When cloning Algorithms repository run . init_submodules to get all dependencies.

Can be useful

• Commands for compiling shared library

g++ -std=c++17 -fPIC -c -Wall -o math/factorial.o math/factorial.cc

g++ -std=c++17 -fPIC -c -Wall -o math/factorial.so math/factorial.cc

clang -std=c++17 -shared -undefined dynamic_lookup -o math/factorial.so math/factorial.cc