- Stores data elements based on an sequential, most commonly 0 based, index.
- Based on tuples (a finite ordered list of elements) from set theory.
- They are one of the oldest, most commonly used data structures.
- Optimal for indexing; bad at searching, inserting, and deleting (except at the end).
- Linear arrays, or one dimensional arrays, are the most basic.
- Are static in size, meaning that they are declared with a fixed size.
- Dynamic arrays are like one dimensional arrays, but have reserved space for additional elements.
- If a dynamic array is full, it copies it's contents to a larger array.
- Two dimensional arrays have x and y indexes like a grid or nested arrays.
| Action | Linear array | Dynamic array |
|---|---|---|
| Indexing | O(1) | O(1) |
| Search | O(n) | O(n) |
| Optimized Search | O(log n) | O(log n) |
| Insertion | n/a | O(n) |
- Stores data with nodes that point to other nodes.
- Nodes, at its most basic it has one datum and one reference (another node).
- A linked list chains nodes together by pointing one node's reference towards another node.
- Designed to optimize insertion and deletion, slow at indexing and searching.
- Doubly linked list has nodes that reference the previous node.
- Circularly linked list is simple linked list whose tail (the last node) references the head (the first node).
- Stack, commonly implemented with linked lists but can be made from arrays too.
- Stacks are last in, first out (LIFO) data structures.
- Made with a linked list by having the head be the only place for insertion and removal.
- Queues, too can be implemented with a linked list or an array.
- Queues are a first in, first out (FIFO) data structure.
- Made with a doubly linked list that only removes from head and adds to tail.
| Action | Linked Lists |
|---|---|
| Indexing | O(n) |
| Search | O(n) |
| Optimized Search | O(n) |
| Insertion | O(1) |
- Stores data with key value pairs.
- Hash functions accept a key and return an output unique only to that specific key.
- This is known as hashing, which is the concept that an input and an output have a one-to-one correspondence to map information.
- Hash functions return a unique address in memory for that data.
- Designed to optimize searching, insertion, and deletion.
- Hash collisions are when a hash function returns the same output for two distinct inputs.
- All hash functions have this problem.
- This is often accommodated for by having the hash tables be very large.
- Hashes are important for associative arrays and database indexing.
| Action | Hash Tables |
|---|---|
| Indexing | O(1) |
| Search | O(1) |
| Insertion | O(1) |
- Is a tree like data structure where every node has at most two children.
- There is one left and one right child node.
- Designed to optimize searching and sorting.
- A degenerate tree is an unbalanced tree, which if entirely one-sided is a essentially a linked list.
- They are comparably simple to implement than other data structures.
- Used to make binary search trees.
- A binary tree that uses comparable keys to assign which direction a child is.
- Left child has a key smaller than it's parent node.
- Right child has a key greater than it's parent node.
- There can be no duplicate node.
- Because of the above it is more likely to be used as a data structure than a binary tree.
| Action | Binary Search Tree |
|---|---|
| Indexing | O(log n) |
| Search | O(log n) |
| Insertion | O(log n) |
- An algorithm that searches a tree (or graph) by searching levels of the tree first, starting at the root.
- It finds every node on the same level, most often moving left to right.
- While doing this it tracks the children nodes of the nodes on the current level.
- When finished examining a level it moves to the left most node on the next level.
- The bottom-right most node is evaluated last (the node that is deepest and is farthest right of it's level).
- Optimal for searching a tree that is wider than it is deep.
- Uses a queue to store information about the tree while it traverses a tree.
- Because it uses a queue it is more memory intensive than depth first search.
- The queue uses more memory because it needs to stores pointers
- Search: Breadth First Search: O(|E| + |V|)
- E is number of edges
- V is number of vertices
Breadth-First-Search(Graph, root):
for each node n in Graph:
n.distance = INFINITY
n.parent = NIL
create empty queue Q
root.distance = 0
Q.enqueue(root)
while Q is not empty:
current = Q.dequeue()
for each node n that is adjacent to current:
if n.distance == INFINITY:
n.distance = current.distance + 1
n.parent = current
Q.enqueue(n)
- An algorithm that searches a tree (or graph) by searching depth of the tree first, starting at the root.
- It traverses left down a tree until it cannot go further.
- Once it reaches the end of a branch it traverses back up trying the right child of nodes on that branch, and if possible left from the right children.
- When finished examining a branch it moves to the node right of the root then tries to go left on all it's children until it reaches the bottom.
- The right most node is evaluated last (the node that is right of all it's ancestors).
- Optimal for searching a tree that is deeper than it is wide.
- Uses a stack to push nodes onto.
- Because a stack is LIFO it does not need to keep track of the nodes pointers and is therefore less memory intensive than breadth first search.
- Once it cannot go further left it begins evaluating the stack.
- Search: Depth First Search: O(|E| + |V|)
- E is number of edges
- V is number of vertices
preorder(node)
if (node = null)
return
visit(node)
preorder(node.left)
preorder(node.right)
inorder(node)
if (node = null)
return
inorder(node.left)
visit(node)
inorder(node.right)
postorder(node)
if (node = null)
return
postorder(node.left)
postorder(node.right)
visit(node)
- The simple answer to this question is that it depends on the size and shape of the tree.
- For wide, shallow trees use Breadth First Search
- For deep, narrow trees use Depth First Search
- Because BFS uses queues to store information about the nodes and its children, it could use more memory than is available on your computer. (But you probably won't have to worry about this.)
- If using a DFS on a tree that is very deep you might go unnecessarily deep in the search. See xkcd for more information.
- Breadth First Search tends to be a looping algorithm.
- Depth First Search tends to be a recursive algorithm.
- A comparison based sorting algorithm
- Divides entire dataset into groups of at most two.
- Compares each number one at a time, moving the smallest number to left of the pair.
- Once all pairs sorted it then compares left most elements of the two left most pairs creating a sorted group of four with the smallest numbers on the left and the largest ones on the right.
- This process is repeated until there is only one set.
- This is one of the most basic sorting algorithms.
- Know that it divides all the data into as small possible sets then compares them.
| Sort | Merge Sort |
|---|---|
| Best Case | O(n) |
| Average Case | O(n log n) |
| Worst Case Sort | O(n log n) |
- A comparison based sorting algorithm
- Divides entire dataset in half by selecting the average element and putting all smaller elements to the left of the average.
- It repeats this process on the left side until it is comparing only two elements at which point the left side is sorted.
- When the left side is finished sorting it performs the same operation on the right side.
- Computer architecture favors the quicksort process.
- While it has the same Big O as (or worse in some cases) many other sorting algorithms it is often faster in practice than many other sorting algorithms, such as merge sort.
- Know that it halves the data set by the average continuously until all the information is sorted.
| Sort | Quicksort |
|---|---|
| Best Case | O(n) |
| Average Case | O(n log n) |
| Worst Case Sort | O(n^2) |
- A comparison based sorting algorithm
- It iterates left to right comparing every couplet, moving the smaller element to the left.
- It repeats this process until it no longer moves and element to the left.
- While it is very simple to implement, it is the least efficient of these three sorting methods.
- Know that it moves one space to the right comparing two elements at a time and moving the smaller on to left.
| Sort | Bubble Sort |
|---|---|
| Best Case | O(n) |
| Average Case | O(n^2) |
| Worst Case Sort | O(n^2) |
- Quicksort is likely faster in practice.
- Merge Sort divides the set into the smallest possible groups immediately then reconstructs the incrementally as it sorts the groupings.
- Quicksort continually divides the set by the average, until the set is recursively sorted.
- An algorithm that calls itself in its definition.
- Recursive case a conditional statement that is used to trigger the recursion.
- Base case a conditional statement that is used to break the recursion.
- Stack level too deep and stack overflow.
- If you've seen either of these from a recursive algorithm, you messed up.
- It means that your base case was never triggered because it was faulty or the problem was so massive you ran out of RAM before reaching it.
- Knowing whether or not you will reach a base case is integral to correctly using recursion.
- Often used in Depth First Search
- An algorithm that is called repeatedly but for a finite number of times, each time being a single iteration.
- Often used to move incrementally through a data set.
- Generally you will see iteration as loops, for, while, and until statements.
- Think of iteration as moving one at a time through a set.
- Often used to move through an array.
- The differences between recursion and iteration can be confusing to distinguish since both can be used to implement the other. But know that,
- Recursion is, usually, more expressive and easier to implement.
- Iteration uses less memory.
- Functional languages (that treats computation as the evaluation of mathematical functions and avoids changing-state and mutable data) tend to use recursion. (i.e. Perl, Python, Haskell)
- Imperative languages (uses statements that change a program's state) tend to use iteration. (i.e. Java, Python, Ruby)
- Check out this Stack Overflow post for more info.
Recursion | Iteration
----------------------------------|----------------------------------
recursive method (array, n) | iterative method (array)
if array[n] is not nil | for n from 0 to size of array
print array[n] | print(array[n])
recursive method(array, n+1) |
else |
exit loop |
- An algorithm that, while executing, selects only the information that meets a certain criteria.
- The general five components, taken from Wikipedia:
- A candidate set, from which a solution is created.
- A selection function, which chooses the best candidate to be added to the solution.
- A feasibility function, that is used to determine if a candidate can be used to contribute to a solution.
- An objective function, which assigns a value to a solution, or a partial solution.
- A solution function, which will indicate when we have discovered a complete solution.
- Used to find the optimal solution for a given problem.
- Generally used on sets of data where only a small proportion of the information evaluated meets the desired result.
- Often a greedy algorithm can help reduce the Big O of an algorithm.
greedy algorithm (array)
var largest difference = 0
var new difference = find next difference (array[n], array[n+1])
largest difference = new difference if new difference is > largest difference
repeat above two steps until all differences have been found
return largest difference
This algorithm never needed to compare all the differences to one another, saving it an entire iteration.
See Wikipedia
Creational patterns are ones that create objects for you, rather than having you instantiate objects directly. This gives your program more flexibility in deciding which objects need to be created for a given case.
- Abstract factory pattern groups object factories that have a common theme.
- Builder pattern constructs complex objects by separating construction and representation.
- Factory method pattern creates objects without specifying the exact class to create.
- Prototype pattern creates objects by cloning an existing object.
- Singleton pattern restricts object creation for a class to only one instance.
These concern class and object composition. They use inheritance to compose interfaces and define ways to compose objects to obtain new functionality.
- Adapter allows classes with incompatible interfaces to work together by wrapping its own interface around that of an already existing class.
- Bridge decouples an abstraction from its implementation so that the two can vary independently.
- Composite composes zero-or-more similar objects so that they can be manipulated as one object.
- Decorator dynamically adds/overrides behaviour in an existing method of an object.
- Facade provides a simplified interface to a large body of code.
- Flyweight reduces the cost of creating and manipulating a large number of similar objects.
- Proxy provides a placeholder for another object to control access, reduce cost, and reduce complexity.
Most of these design patterns are specifically concerned with communication between objects.
- Chain of responsibility delegates commands to a chain of processing objects.
- Command creates objects which encapsulate actions and parameters.
- Interpreter implements a specialized language.
- Iterator accesses the elements of an object sequentially without exposing its underlying representation.
- Mediator allows loose coupling between classes by being the only class that has detailed knowledge of their methods.
- Memento provides the ability to restore an object to its previous state (undo).
- Observer is a publish/subscribe pattern which allows a number of observer objects to see an event.
- State allows an object to alter its behavior when its internal state changes.
- Strategy allows one of a family of algorithms to be selected on-the-fly at runtime.
- Template method defines the skeleton of an algorithm as an abstract class, allowing its subclasses to provide concrete behavior.
- Visitor separates an algorithm from an object structure by moving the hierarchy of methods into one object.
top 10 algorithms for coding interview
Scalability can be achieved following multiple principles: parallelization, fault tolerance, stateless, idempotent, partitioning, asynchronous.
Load data on demand into a cache from a data store. This pattern can improve performance and also helps to maintain consistency between data held in the cache and the data in the underlying data store.
Enable multiple concurrent consumers to process messages received on the same messaging channel. This pattern enables a system to process multiple messages concurrently to optimize throughput, to improve scalability and availability, and to balance the workload.
Segregate operations that read data from operations that update data by using separate interfaces. This pattern can maximize performance, scalability, and security; support evolution of the system over time through higher flexibility; and prevent update commands from causing merge conflicts at the domain level.
Use an append-only store to record the full series of events that describe actions taken on data in a domain, rather than storing just the current state, so that the store can be used to materialize the domain objects. This pattern can simplify tasks in complex domains by avoiding the requirement to synchronize the data model and the business domain; improve performance, scalability, and responsiveness; provide consistency for transactional data; and maintain full audit trails and history that may enable compensating actions.
Create indexes over the fields in data stores that are frequently referenced by query criteria. This pattern can improve query performance by allowing applications to more quickly retrieve data from a data store.
Generate pre-populated views over the data in one or more data stores when the data is formatted in a way that does not favor the required query operations. This pattern can help to support efficient querying and data extraction, and improve application performance.
Prioritize requests sent to services so that requests with a higher priority are received and processed more quickly than those of a lower priority. This pattern is useful in applications that offer different service level guarantees to individual types of client.
Use a queue that acts as a buffer between a task and a service that it invokes in order to smooth intermittent heavy loads that may otherwise cause the service to fail or the task to timeout. This pattern can help to minimize the impact of peaks in demand on availability and responsiveness for both the task and the service.
Divide a data store into a set of horizontal partitions shards. This pattern can improve scalability when storing and accessing large volumes of data.
Deploy static content to a cloud-based storage service that can deliver these directly to the client. This pattern can reduce the requirement for potentially expensive compute instances.
Control the consumption of resources used by an instance of an application, an individual tenant, or an entire service. This pattern can allow the system to continue to function and meet service level agreements, even when an increase in demand places an extreme load on resources.
a dispatcher determines which worker instance will handle a request based on different policies.
a dispatcher multicasts requests to all workers in a pool. Each worker will compute a local result and send it back to the dispatcher, who will consolidate them into a single response and then send back to the client.
a dispatcher will first lookup if the request has been made before and try to find the previous result to return, in order to save the actual execution.
all workers monitors information from the shared space and contributes partial knowledge back to the blackboard. The information is continuously enriched until a solution is reached.
all workers connected by pipes across which data flows.
targets batch jobs where disk I/O is the major bottleneck. It use a distributed file system so that disk I/O can be done in parallel.
a lock-step execution across all workers, coordinated by a master.
an intelligent scheduler / orchestrator schedules ready-to-run tasks (based on a dependency graph) across a clusters of dumb workers.
Constantly monitoring performance and scaling a system to adapt to fluctuating workloads to meet capacity targets and optimize operational cost can be a labor-intensive process. It may not be feasible to perform these tasks manually. This is where autoscaling is useful.
Caching is a common technique that aims to improve the performance and scalability of a system by temporarily copying frequently accessed data to fast storage located close to the application. Caching is most effective when an application instance repeatedly reads the same data, especially if the original data store is slow relative to the speed of the cache, it is subject to a high level of contention, or it is far away resulting in network latency.
Cloud applications typically use data that is dispersed across data stores. Managing and maintaining data consistency in this environment can become a critical aspect of the system, particularly in terms of the concurrency and availability issues that can arise. You frequently need to trade strong consistency for performance. This means that you may need to design some aspects of your solutions around the notion of eventual consistency and accept that the data that your applications use might not be completely consistent all of the time.
In many large-scale solutions, data is divided into separate partitions that can be managed and accessed separately. The partitioning strategy must be chosen carefully to maximize the benefits while minimizing adverse effects. Partitioning can help to improve scalability, reduce contention, and optimize performance.