Basic Data Structures and Algorithms Flashcards
What are the 5 steps for handling technical questions?
- Ask questions
- Design an algorithm
- Pseudocode
- Code
- Test
What are the 5 approaches to algorithms?
- Examplify
- Pattern Matching
- Simplify and Generalize
- Base Case and Build
- Data Structure Brainstorm
What is a linked list?
a data structure in which objects are arranged in linear order. Unlike an array (where order is determined by array indicies) the order is determined by a pointer in each object.
What is a singly linked list?
a linked list where the prev pointer is omitted in each element
What is a doubly linked list?
a linked list with both a ‘prev’ and next pointer in each element
What is a circular list?
a list where the prev pointer of the head of the list (first item in the list) points to the tail of the list. And the next pointer points to the head of the list.
What is a binary tree?
A binary tree is made of nodes, where each node contains a “left” pointer, a “right” pointer, and a data element. The “root” pointer points to the topmost node in the tree. The left and right pointers recursively point to smaller “subtrees” on either side.
What’s are tries?
A trie is a tree structure, where each edge represents one character, and the root represents the null string.
Thus, each path from the root represents a string, described by the characters labeling the edges traversed. Any finite set of words defines a trie, and two words with common prefixes branch off from each other at the first distinguishing character. Each leaf denotes the end of a string.
When are tries useful?
Tries are useful for testing whether a given query string q is in the set.
We traverse the trie from the root along branches defined by successive characters of q. If a branch does not exist in the trie, then q cannot be in the set of strings
What is a suffix tree?
A trie of all the proper suffixes of S.
The suffix tree enables you to test whether q is a substring of S, because any substring of S is the prefix of some suffix.
The search time is again linear in the length of q.
What are 3 things a suffix tree can be used for?
Find all occurrences of q as a substring of S
Longest substring common to a set of strings
Find the longest palindrome in S
Define Big-O notation.
Big O notation is most commonly used by programmers as an approximate measure of how long a computation (algorithm) will take to complete expressed as a function of the size of the input set.
Big O is useful to compare how well two algorithms will scale up as the number of inputs is increased.
More precisely Big O notation is used to express the asymptotic behavior of a function. That means how the function behaves as it approaches infinity.
What is linear complexity in Big-O notation?
O(n)
ex.) counting the number of items in a linked list
What is quadratic complexity in Big-O notation?
O(n2)
ex.) bubble sort
What is logarithmic complexity in Big-O notation?
O(log n)
ex.) binary search tree
What is constant complexity in Big-O notation?
O(1)
ex.) accessing an array element by index
What is factorial or combinatorial complexity in Big-O notation?
O(n!)
ex.) traveling salesman problem brute-force solution
What is linearithmic complexity in Big-O notation?
O(n log n)
ex.) heap sort and quick sort
What is a stack?
a dynamic set with a LIFO (last in first out) policy.
Think of it as a stack of cafeteria trays, when adding new trays to the stack they go on top, when taking trays off of the stack they come from the top.
What is a queue?
a dynamic set with a FIFO (first in, first out) policy.
What happens when you try to pop an empty stack?
the stack underflows (normally resulting in an error)
What happens if you try adding an element to a stack when it is already holding the maximum amount of elements it can hold?
the stack overflows
what is the insert operation on a stack called?
push
what is the delete operation on a stack called?
pop
what is the insert operation on a queue called?
enqueue
what is the delete operation on a queue called?
dequeue
what is the head and the tail of a queue?
When an element is enqueued (added) to a queue it happens at the tail of the queue. When an element is it dequeued (removed) from a queue it is always the one at the head of the queue.
what happens if you try to dequeue an element from an empty queue?
the queue underflows
what happens if you try to enqueue an element to a full queue?
the queue overflows
what is the difference between a stack and a queue?
a stack is LIFO and a queue is FIFO
what is a hash table?
a Python dictionary
an unordered set of key: value pairs, where the keys are unique and immutable
under reasonable assumptions the average time to search for an element in a hash table is O(1)
only support dictionary operations INSERT, SEARCH, and DELETE
what are “collisions” in a hash table?
when more than one key maps to the same array index
when is a hash table a better alternative to directly addressing an array?
when the number of keys actually stored is small relative to the total number of possible keys
what is the worst-case running time for most search-tree operations?
worst-case running time is proportional to the height of the tree
which sorting algorithm is typically the best practical choice for storting and why?
Quicksort. it is remarkably efficient on the average
how does quicksort work?
It is a divide-and-conquer algorithm.
- Choose any element of the array to be the pivot.
- Divide all other elements (except the pivot) into two partitions.
- Elements less than the pivot must be in the first partition.
- elements greater in the second partition. - Use recursion to sort both partitions.
(Once the pivot is selected, we select successive elements from the beginning of the array that are greater than or equal to the pivot and select elements from the end of the array that are less than or equal to the pivot. Once we find one of each of these, we swap their values and move the selectors toward the opposite ends of the array and repeat until the selectors meet at the pivot. This partitions the array.)
- Join the first sorted partition, the pivot, and the second sorted partition.
The runtime of Quicksort ranges from O(n log n) with the best pivots, to O(n2) with the worst pivots, where n is the number of elements in the array.
what is a set?
A set is a collection (container) of certain values, without any particular order, and no repeated values. It corresponds with a finite set in mathematics. A set can be implemented as an associative array (partial mapping) in which the value of each key-value pair is ignored.
what is a powerset?
Given a set S, the power set (or powerset) of S, written P(S), or 2S, is the set of all subsets of S.
For example, the power set of {1,2,3,4} is {{}, {1}, {2}, {1,2}, {3}, {1,3}, {2,3}, {1,2,3}, {4}, {1,4}, {2,4}, {1,2,4}, {3,4}, {1,3,4}, {2,3,4}, {1,2,3,4}}.
