I'm aiming to revise/ learn all the common questions asked in coding interviews. I've compiled a basic list of the concepts I need to cover, which I will then work through.

Computer Science Foundations

Algorithm Complexity

• Big O Notation (time and space)

Trees

• Binary Search Tree (BST)
• Trie
• Balanced (Red Black / AVL)
• Heap
• Traversal (BFS, DFS, in/pre/postorder)

Graphs

• Graph Representations
• Graph traversal (BFS, DFS)
• Graph colouring
• Dijkstra's Algorithm
• A*

Hashmaps

• Using Java HashMap
• Uses for hashmaps

Sorting

• Merge Sort
• Quick Sort

NP-Complete Problems

• Travelling salesman

Dynamic Programming

• Rod cutting problem
• Knapsack problem

Greedy Algorithms

• Huffman Coding
• Kruskal's Algorithm

Math

• Combinatorics
• Probability

Practice Problems

1. Interpreter for stack based language
2. LRU (Least Recently Used) cache with a max capacity, with LRU element replaced when capacity reached
3. Given an array of integers, determine if there are 3 elements that sum to 0. Generalise to k elements summing to i.
4. Given an integer, replace its bits starting from the bit at position a to the bit at position b, inclusive, with the bits of integer k. Count from the least significant bit to the most significant bit, starting from 0. For n=24, a=1, b=6, k=17, the output should be 1058. n=100 0000 0000, k=1 0001, 1058=100 0010 0010
5. Implement a simple, persistent, thread-safe cache, which should ideally be able to store up to 1 million product names
6. Sort the letters in one word by the order they appear in another in linear time
7. Given an array of values, design an algorithm that returns whether there are two duplicated within k indices of each other. Do all in O(n) running time and O(k) space
8. Implement a multi-map in Java without using any collections
9. (EASY) Find the first recurring character in a string