1. Understand the differences between the data structures and trade-offs (array vs linked list, hash tables, trees, etc.) Don’t worry about implementation just understand how they’re built and what they’re good for.
Linked-Lists
About Linked List Data Structures
Linked list’s read, create, and delete methods were all much slower than array’s same methods.
Arrays utilize Spacial Locality. Linked Lists allow utilization of additional memory.
Hashes
Open addressing
makes sure underlying array is not resized during insertion unless the underlying array is indeed full.
Separate chaining
utilizes linked-lists to “chain” off underlying array’s indexes. An Insertion first checks if index returned from hashing function is occupied. If so, the last node is found on any potential existing linked-list, (of which the @next attribute is NIL) and the new item insertion is complete.
Trees
Binary Search Trees
- Maintains one root node off which all others branch off. Each node has at most, 2 adjoined nodes. Each node’s left and right attributes are written according to that nodes’ value.
Min/Max Binary Heap
Has all the properties of a Binary Search Tree but also organizes row by value with either the maximum value node as the root (max binary heap) or the minimum value node is the root (min binary heap)
2. Understand what Object Relational Mapping is (Conceptually, nothing code related. You should have learned this with Ruby.)
Object Relational Mapping, or ORM
provides a way for Rails developers to manipulate a database using Ruby, rather than writing SQL. Rails employs an ORM library named ActiveRecord to provide this translation service.
Rails Console
Provides command line access to a Rails application and Ruby.
SQL
SQL is a language for communicating with a relational database.
Object Relational Mapping
Object-Relational Mapping (ORM) is a design pattern that connects the objects of an application to tables in a database. Using ORM, the properties and relationships of objects in an application can be connected to a database without the need to write SQL statements.
ActiveRecord
ActiveRecord is Rails’ ORM library.
3. Understand all the O time complexities and what they mean/signify.
O(1)
Read as “constant time” or “Big-O of constant time”. No matter the size of n, the algorithm always takes the same amount of time to execute. This is the fastest an algorithm can operate.
O(logn)
Read as “logarithmic time” or “Big-O of logarithmic time”. As the size of n grows, the time it takes the algorithm to execute and complete grows faster than constant time. Logarithmic time algorithms are slower than constant time algorithms.
O(n)
Read as “linear time” or “Big-O of linear time”. As the size of n grows, the time it takes the algorithm to execute and complete grows at the same rate. Linear time algorithms are slower than constant time algorithms.
O(nlogn)
Read as “loglinear time” or “Big-O of loglinear time”. As the size of n grows, the time it takes the algorithm to execute and complete grows faster than constant time. Loglinear time algorithms are slower than linear time algorithms.
O(n2)
Read as “quadratic time” or “Big-O of quadratic time”. As n grows, the time it takes the algorithm to execute grows faster than loglinear time. This is considered a slow efficiency classification. Quadratic time algorithms are slower than loglinear time algorithms and overall considered relatively slow, but still usable.
O(2n)
Read as “exponential time” or “Big-O of exponential time”. As n grows, the time it takes the algorithm to execute grows much faster than quadratic time. Algorithms with this complexity are very slow, and in most cases unusable.
4. Be able to identify all of the sorts you encountered. Once again no need for implementing them, but you should be able to identify them given some code. You should know the time complexities of them as well.
Insertion Sort
Moves items from an unsorted collection to a new, sorted collection by inserting items in their proper place one at a time. This algorithm has poor performance compared to other sorting algorithms. Big 0(n2)
Selection Sort
Selects the item which should be sorted “next” and moves it to the front (or back) of the collection. Selection sort has poor performance compared to other sorting algorithms. Big 0(n2)
Bubble Sort
Passes through a collection multiple times. In each pass, it compares adjacent items and swaps them according to the desired sorting order. The algorithm finishes when there are no swaps done for a complete pass. Bubble sort has poor performance when compared to other sorting algorithms. Big 0(n2)
Merge Sort
Breaks the collection into sub-collections and sorts each sub-collection. Sorted sub-collections are merged together (using recursion) to form larger sorted collections until the entire collection is sorted. Merge sort has good performance compared to other sorting algorithms. Big O(nlogn)
Quick Sort
Picks a pivot point and compares each item to the pivot point. It moves each item according to the pivot point. When there are no more items to move in the first iteration, these steps are repeated for the “left” and “right” sides of the collection. Quick sort has good performance compared to other sorting algorithms. Big O(nlogn)
5. Study LEFT, RIGHT, and INNER join.
SELECT department.name, professor.name
FROM department
LEFT OUTER JOIN professor
ON professor.department*id = department.id;
6. Be able to write a linear search and binary search and know the associated runtimes.
Binary Search
The best case scenario for binary search is if the collection being searched through has only one item, such that the algorithm has 0(1). If the collection only has one item, then in the binary search high, low, and mid are all equal at which point the method returns “not found”/nil or the item at the sole index.
The worst case scenario for binary search is if the input collection approaches an infinite size. In this case, the collection will have to be cut in half more times but that’s not so bad because on first iteration you’re still throwing away half of an infinite collection of items. Because of this, binary search in it’s worst case has O(log n).
What is the Big-O of binary search?
O(log n). Worst case of binary search is log n
What is the Big-Ω of binary search?
Ω(1). Best case for binary search is constant
What is the Big-Ө of binary search?
Ө(logn). Average case for binary search is log n.
7. Be able to design a database and write CREATE TABLE statements.
Example:
CREATE TABLE boat (
id integer PRIMARY KEY NOT NULL,
type text NOT NULL,
license\*plate varchar(7) NOT NULL,
owner\*id integer REFERENCES owner(id)
);
8. Be able to utilize JOINS and subqueries in a query.
9. Understand the purpose of normalization and denormalization
Benefits of data normalization:
Data integrity:
- not only does normalization reduce data duplication, since there is no redundant, neglected data, normalization prevents update anomalies (mistakes) and data inconsistencies.
Optimized queries:
normalized tables group data more logically, and produce rapid, efficient joins.
Faster index creation and sorting (since the tables have fewer columns)
Faster update performance (since there are fewer indexes per table)
Improved concurrency resolution (since table locks will affect less data)
Data Denormalization
- If data normalization aims to reduce redundancy, data denormalization is a process performed on a previously-normalized database to increase read performance.
Methods of denormalization
Common techniques for denormalization in database design include:
Adding redundant groups
Adding derived columns
Combining tables
Repeating groups
Creating extract tables
Partitioning relations