Systems Design
Issues to Consider / Be Aware Of
- Avoid competing / multiple sources of truth
Tips
- Don't jump in; take time to understand the problem and ask clarifying questions.
- Will there be an API? Consider endpoints, request/response formats, etc. 'domain/resource/{params}'. Maybe delve into an endpoint as a case study and to show understanding.
- Discuss frontend - are we working with designers / existing designs? Consider what the user will need to be able to do.
- Is it a web app, mobile app, desktop app, or all of the above? Something else?
- Projected usage levels? How many users? How many requests per second?
- What will the authentication layer look like?
- Microservices or not?
Resources
Coding Test
There can be a wide variety of coding tests to assess coding abilities; FizzBuzz being a historically popular one.
Tips
- Read the question carefully; take a moment to understand and digest the prompt as given.
- Don't jump in; ask questions to figure out requirements, edge cases, need for input validation, etc.
Misc. Examples
- Amazon SDE Coding Test Example Vid
- Run Length Encoding
- Longest Substring With no Duplicate Characters Within a String
Data Structures
Stack
A stack follows the Last-In-First-Out (LIFO) principle - think stack of plates; can only add or remove from the top. Common uses: call stack, undo/redo functionality, browser history (back button), etc. Push/pop/peek O(1) time complexity.
Queue
First-In-First-Out (FIFO) principle; think line of people where first person joins is first to go/leave. Common uses: breadth-first search, printer queue, request handling, etc. Enqueue/dequeue/peek O(1) time complexity.
Linked List
A collection of nodes where each node contains a value and a reference to the next node in the sequence. Common uses: music playlist, undo/redo functionality, etc. prepend O(1), append/insertAt/delete/search O(n) time complexity.
Hash Table / Hash Map
A data structure that maps keys to values; uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found. Common uses
Binary Search Tree
Graph
Breadth-First Search (BFS)
If you can eliminate a node as a solution, you can eliminate all of its children (think divide-and-conquer and how effective that strategy is).
Resources
Algorithms
Sorting
Bubble Sort
Selection Sort
Insertion Sort
In-place, can be stable, O(n^2) time complexity. Basically, iterate through the array, moving elements to the left until they are in the correct position.
Merge Sort
Divide-and-conquer, recursive, stable, O(n log n) time complexity, O(n) space complexity.
Basically, divide the array into two halves, sort each half, and then merge the two halves back together.
Quick Sort
Basic idea: pick a pivot, partition the array into two sub-arrays, elements less than the pivot and elements greater than the pivot. Recursively sort the sub-arrays.
In-place, divide-and-conquer, recursive, unstable, O(n log n) time complexity.