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
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.