Awesome
Nailing-the-Coding-Interview
Author: github.com/agavrel
Learn how to pass C++ assessment tests with the most optimized algorithms
0x00 - Purpose of this repository
This repository is aimed at a broad range of people:
- Computer Science and Mathematics students
- Professionals looking to sharpen their skills for interviews
- People who prefer to have fun on week-ends solving interesting problems
- Kids who need to build and enhance their problem-solving logic
- Elders who want to keep their brain active
0x01 - Algorithm Definition (quoting wikipedia)
In mathematics and computer science, an algorithm is an unambiguous specification of how to solve a class of problems. Algorithms can perform calculation, data processing and automated reasoning tasks.
Algorithms have become an important way of optimizing programs in Computer Science. It is rather easy to code a solution to a specific problem. What is more difficult is to have the most efficient algorithm, meaning the algorithm with the lowest time complexity.
0x02 - Algorithm General Categories
While they are all interesting, they serve different purposes. Depending on which kind of career you are looking for, you might want to focus more specifically in one area or another
| Category | Purpose |
|---|---|
| Well-Known Algorithms | Starting Point for Interviews |
| Bitwise | Best for those looking for careers in Embedded Systems |
| Mathematics and Logical Sequences | Mathematics is ideal for those interested in working on Graphic Motors |
| Linked List | To understand better Recursion, structure and pointers |
| Prime Numbers | Excellent for Cryptography as Prime Numbers allow to compute unique Hashes |
| Greedy | Interesting for those who contemplate AI |
| Parsing | Best for those interested into Hacking, segfaulting the parser is often the best way to exploit a program |
| Binary Search Algorithms | Logarithmic search of a special number in a sorted array, good to understand map/dictionary implementations |
0x03 - Bitwise Category
| Name | How Interesting | Notes |
|---|---|---|
| Is Power of Two | :star::star::star::star::star: | Understanding Binary Representation |
| Find the Single Integer | :star: | Understanding Binary Representation |
| Is Nth Bit Set | :star::star: | Binary Representation |
| Spy Hawk | :star::star::star::star::star: | Bitset |
| Reverse 32 bits | :star::star::star::star::star: | Lookup Table, Shifts and Masks, Use of Carry Flag (assembly) |
| Reverse 8 bits | :star::star::star::star::star: | Lookup Table, Shifts and Masks, Use of Carry Flag (assembly) |
| INT to HEX | :star::star::star: | printf %x or print_base_16 implementation, easier in C++ thanks to std::string |
| Number of Common Letters | :star::star::star: | Bitwise Approach |
| Least Operators to Express a Number | :star::star::star: | Binary Representation and Mathematics |
| Match Maker | :star::star::star::star: | Algorithm that I coined myself, no solution published |
| Binary Gap | :star::star::star::star: | Shifts and Masks |
| Align Number on Power of Two | :star::star::star::star::star: | Shifts and Masks |
| Longest Palindrome | :star: | Shifts and Masks |
| Number Complement | :two_hearts: | Excellent in-depth Algorithm |
| Bitwise AND of Number Range | :two_hearts: | Excellent in-depth Algorithm to apply Mathematics to bitwise |
| Repeated DNA Sequences | :star::star::star::star: | Bitwise Approach |
0x04 - Mathematics and Logical Sequences
| Name | How Interesting | Notes |
|---|---|---|
| The Dancer | :star::star::star::star: | Do you see a Pattern ? |
| Fibonacci Series | :star: | Top 10 interview questions in Finance |
| Binary Search | :star: | Also Top 10 interview questions in Finance |
| Is Power of Three | :star::star: | Return result in O(1) |
0x05 - Linked List
| Name | How Interesting | Notes |
|---|---|---|
| Merge Two Sorted Lists | :star::star::star: | Sort Algorithms |
| Merge k Sorted Lists | :star::star::star::star::star: | Sort Algorithms |
0x06 - Hashmap
| Name | How Interesting | Notes |
|---|---|---|
| Group Anagram | :star::star::star: | How about implementing the Hash function yourself ? |
| Target Sum | :star::star::star::star: | Beware of Integer overflow |
0x07 - Greedy
| Name | How Interesting | Notes |
|---|---|---|
| Change Problem | :star: | If you ever have to code the program of an ATM |
0x08 - Parsing
| Name | How Interesting | Notes |
|---|---|---|
| Reverse Integer Digits | :star: | Not the most exciting one |
| https://github.com/agavrel/Nailing-the-Coding-Interview/tree/master/parsing/string_to_lowercase | :star::star::star: | Best Way to get Flamed on StackOverflow |
0xFE - Credit
My past interview assessments with different financial companies (BNP Paribas, Societe Generale, Murex etc.) were what got me started into algorithms and competitive programming.
I want to thank my Friends of 42 School in Paris, especially Iwan Burel (iburel) and Steven Toupin (stoupin), for their precious insights and outstanding problem solving skills.
The various internet sites like Codingame, Leetcode, Hackerrank and Codility were helpful to read about new algorithm problems.
Last, I want to thank the numerous quidam on github and stackoverflow who raised my knowledge of algorithm resolution using assembly language
0xFF - Purpose of this repository
All rights reserved by Antonin GAVREL. Contact me if you want to redistribute the code. No commercial use.