Data Structures Flashcards
What are data structures?
the elementary particles of algorithms, data structures are woven into the fabric of computer science and are essential building blocks of many coding solutions.
True or False
Data structures can be boiled down to the manipulation of data
True
manipulating data involves structuring that data.
What is complexity analysis?
A single coding problem may have multiple solutions using different data structures, they are not all equal (ie time vs space)
During a coding interview, when asked (about your code) “can you improve it and do better” is usually referring to?
complexity analysis
Did you choose the most efficient data structure (nested for loop over a hash table) or did the question place more emphasis on space vs execution time?
What is space-time complexity?
time: how fast algorithm runs
space: how much memory an algorithm is utilizing
all depends on the use-case
True or False
Memory is a bounded type of storage
True
memory is finite (limited)
bits are?
8 bits is a?
binary 0 and 1’s (base 2)
byte
True or False
pointers can be allocated in memory as well
True
and pointers aren’t memory intensive and don’t have to be in continuous memory.
True or False
Accessing a memory address is just about instantaneous?
True
True or False
32bit (fixed-width) is 4 bytes memory
True
True or False
64bit (fixed-width) is 8 bytes memory
True
A single byte can represent up to ___ data values
256
Constant time is represent as?
O(1)
if the value of T(n) is bounded by a value that does not depend on the size of the input. ie, accessing any single element in an array takes constant time as only one operation has to be performed to locate it.
Logarithmic time is represented as?
O(log(n))
Algorithms taking logarithmic time are commonly found in operations on binary trees or when using binary search.
An O(log n) algorithm is considered highly efficient, as the ratio of the number of operations to the size of the input decreases and tends to zero when n increases.
Linear time is represented as?
O(n)
the running time increases at most linearly with the size of the input.
Log-Linear time is represented as?
O(nlog(n))
gives us a means of notating the rate of growth of an algorithm that performs better than O(n2) but not as well as O(n).
Quadratic time is represented as?
O(n2)
represents an algorithm whose performance is directly proportional to the squared size of the input data set (think of Linear, but squared). … In doing so, we are passing over the same array twice with each search.
Cubic time is represented as?
O(n3)
An algorithm is said to run in cubic time if the running time of the three loops is proportional to the cube of N. When N triples, the running time increases by N * N * N. Time Complexity of a loop is said as O(log N) if the loop variables is divided / multiplied by a constant amount.
Exponential time is represented as?
O(2n)
denotes an algorithm whose growth doubles with each additon to the input data set. If you know of other exponential growth patterns, this works in much the same way. The time complexity starts off very shallow, rising at an ever-increasing rate until the end.
Factorial time is represented as?
O(n!)
True or False
In terms on Big O Notation, it’s always in the context of the worst case senario?
True
Big O defines addresses when a function performs it’s worst in time complexity, when sh!t goes sideways!
In Big O Notation, which has a better time complexity? O(n) or O(1)
O(1) constant time
In Big O Notation, which has a better time complexity? O(n) or O(log n)
O(log n) logarithmic time
In Big O Notation, which has a better time complexity? O(n3) or O(n!)
O(n3) cubic time
Cite the time complexity
O(1)
constant time
Cite the time complexity
O(log n)
logarithmic time
Cite the time complexity
O(n)
linear time
Cite the time complexity
O(n * log n)
log linear time
Cite the time complexity
O(n2)
quadratic time
Cite the time complexity
O(n3)
cubic
Cite the time complexity
O(2n)
exponential
Cite the time complexity
O(n!)
factorial
what is log(n) complexity analysis?
logb(x)=y iif by=x
log of the num x, given a base b, is equal to y, if and only if, base to the power of y is equal to x
True or False
In log(n) the base is assumed to be base 2(binary)?
logb(x)=y iif by=x
True
True or False
logb(n)=y iif by=n or log(n)=y iif 2y=n
are one in the same
True
This is just log(n)
True or False
Computer science deals with log base 10?
False
Computer science uses log base 2, dealing with binary values.
log(1) = ?
0
20 = 1
log(4) = ?
2
- 2? = 4*
- 2 * 2 = 4*
log(16) = ?
4
2? = 16
2 * 2 * 2 * 2 = 16
How would you find the log of (n)?
2? = (n)
the ? is the log of n
True or False
2? = n
when you double n you’re increasing ? by 1
True
2? = n
when you increase ? by one, you’re _______ n
doubling
24 = 16
What is ? in 2? = 32
? is increased by 1 to 25
25 = 32
logarithmic time
O(log N)
is particular efficient because?
It’s increases by 1 when the input (n) doubles!
- log(n) = y*
- y is the ? in n?*
Array - Cite the time complexity
Accessing a value at a given index?
O(1) constant time
Array - Cite the time complexity
Updating a value at a given index?
O(1) constant time
Array - Cite the time complexity
Inserting a value at the begining?
O(n) linear time
Array - Cite the time complexity
Inserting a value in the middle?
O(n) linear time
Array - Cite the time complexity
Inserting a value at the end (dynamic array)?
amoritized O(1) contstant time
Array - Cite the time complexity
Inserting a value at the end (static array)?
O(n) linear time
Array - Cite the time complexity
Removing a value at the begining?
O(n) linear time
Array - Cite the time complexity
Removing a value in the middle?
O(n) linear time
Array - Cite the time complexity
Removing a value at the end?
O(1) constant time
Array - Cite the time complexity
Copying an array?
O(n) linear time
A func that runs at constant time O(1) means what exactly?
That the time does NOT change based on the len of the input or (n) usually a basic operation like looking up an array/list value via it’s index
What is the time complexity of __init__ of an array object?
O(n) linear time
What is the time complexity when traversing an array?
- O(n) linear time*
- O(1)* space
What is the time complexity when copying an array?
- O(n) linear time*
- O(n) space*
What is amortized analysis?
a method for analyzing a given algorithm’s complexity, or how much of a resource, especially time or memory, it takes to execute.
What is the time complexity of using the built-in pop() method to remove and element from the end of an array?
constant time O(1)
What is the time complexity of using the built-in pop(34) method to remove and element from the all but the end of an array?
linear time O(n)
True or False
Like an array, linked lists are stored in continuous memory locations?
False
Linked lists use pointers in memory
What is this?
[1, 2, 3, 4, 5]
an array
What is this?
[1->, 2->, 3->, 4->, 5]
linked list
A listed list has what time complexity?
O(i) time
must traverse through i nodes
Linked list - time complexity
Accessing the head?
O(1) constant time
Linked list - time complexity
Accessing the tail?
O(n) linear time
Linked list - time complexity
Accessing the middle node?
O(n) linear time
Linked list - time complexity
Inserting / removing the head?
O(1) constant time
Linked list - time complexity
Inserting / removing the tail?
O(n) to access + O(1)
Linked list - time complexity
Inserting / removing the middle node?
O(n) to access + O(1)
Linked list - time complexity
Searching for a value?
O(n) linear time
Doubly linked list - time complexity
Accessing the head?
O(1) constant time
Doubly linked list - time complexity
Accessing the tail?
O(1) constant time
Doubly linked list - time complexity
Accessing a middle node?
O(n) linear time
Doubly linked list - time complexity
Inserting / removing the head?
O(1) constant time
Doubly linked list - time complexity
Searching for a value?
O(n) linear time complexity
Doubly linked list - time complexity
Inserting / removing the tail?
O(1) constant time
Doubly linked list - time complexity
Inserting / removing a middel node?
O(n) to access + O(1)
True or False
Like an array a link-list can be indexed
False
Linked lists have nodes that don’t function like an arrays idx
True or False
The space time for both the __init__ of an array and linked list is O(n) linear time
True
True or False
In a Python dict (hash table) inserting, deleting, and searching all have a time complexity of O(1) constant time!
True on average but
O(n) linear time in worst case senario, collisions and having to rely on a linked-list data structure underneath.
True or False
Hash tables can have different data types as keys, these keys are subjected to a hash function underneath that allows for O(1) time interactions, this hash value is equilivent to an array’s index?
True
Describe how a hash function operates.
For a key of a str data type
‘foo’
Is transposed to its askey numerical value
102 ascii
these key values are summed and the modulus operator based on the length of the hash table (underlying array) is used to calculate the index to store the key-value pair
True or False
A hash table in which two keys equal the same index or hash value is then subjected to a linked-list data structure.
True
What is a collison when describing a hash table?
When more than a single key is assigned (hashed to) indentical values.
True or False
In a hash table keys can be described as the heap when collisions are involved and a linked list data structure is being implemented on a hash table.
True
True or False
hashing keys are O(1) constant time operations?
True
What is an array-like structure that follows the LIFO: Last In First Out rule?
a stack
Pushing an element on a stack is what time complex?
O(1) constant time
Popping or removing an element from a stack is what time complexity?
O(1) constant time
Peeking at the top element of a stack is accomplished in what time complexity?
O(1) constant time
Searching for an element in a stack has what time complexity?
O(n) linear time
An array-like data structure that implements the FIFO: First In First Out rule?
a Queue
Enqueuing a queue has ___ time complexity.
O(1) constant time
Dequeuing a queue takes ____ time complexity
O(1) constant time
Peeking a the first element in a queue is perform in ____ time
O(1) constant
Searching for an queue element is performed in _____ time
O(n) linear
True or False
A stack is usually implemented with a dynamic-array or a singly-linked list
True
True or False
A queue is implemented with a doubly linked-list
True
True or False
strings are stored in memory as arrays of integers
True
True or False
strings are mutable
True
What is the time complexity of the string code?
string = 'this is a string object' newString = ""
for character in string:
newString += character
O(n2) because each addition of a char to newString creates an entirely new string and is itself O(n) operation
Traversing a str has what time complexity?
- O(n)* time identical to an array
- O(1)* space
The complexity of copying a string?
O(n) time and space
The complexity of getting a string?
O(1) constant time and space
True or False
strings are immutable
True
The go around is to create a new string objec and thus a O(n2) time and space complexity
or split the string into a appendable list
Define a collection of nodes or values called vertices that may be related; relations between vertices are called edges
graph
a ______ cycle occurs in a ______ when three of more vertices are connected so as to form a closed loop
graph
a graph that has no cycles
acyclic graph
a graph that has at least one cycle
cyclic graph
a graph whose edges are directed, meaning that they can only traverse in one direction, which is specified.
directed graph
a graph whose edges are undirected, meaning they can traverse in both directions
undirected graph
if for every pair of vertices in the graph there’s a path of one or more edges connection the given vertices
connected graph
Cite two attributes of a direct graph
strongly connected - bidirectional
weakly connected - not bidirectional
What is a graph in space complexity?
O(v+e)
vertices + edges
What are the two ways to traverse a graph?
- breath* first search
- depth* first search
What is a graph in time complexity?
- O(v+e)*
- vertices + edges*
A data structure that consists of nodes, each with some value and pointers to child-nodes, which recursively form _____ in the tree
subtrees
The first node in a tree is referred to as the _____ while the nodes at the bottom of a tree (nodes with no child-nodes) are referred to as ____ ____ or simply ______.
root
leaf nodes, leaves
The paths between the root of a tree and its leaves are called _______ and the _____ of a tree is the length of its longest branch.
branches, height
A tree is effectively a ______
graph
A tree is effectively a graph that’s ______, _______, and _______ that has an explicit root node, and whose nodes all have a single _______
connected, directed, acyclic, parent
There are many types of trees and tree-like structures, including
binary trees, heaps, and tries (pronounced trees)
A tree whose nodes have up to two child-nodes
binary tree
A tree whose nodes have up to k child nodes
K-ary tree
A binary tree is a k-ary tree where k == 2
A binary tree whose interior nodes all have two child-nodes and whose leaf nodes all have the same depth is a?
perfect binary tree
A binary tree that’s almost perfect; itls interior nodes all have two child-nodes, but its leaf nodes don’t necessarily all have the same depth. Futhermore, the nodes in the last level of a _________ are as far left as possible.
complete binary tree
A binary tree whose nodes all have left and right subtress whose heights differ by no more than 1
balanced binary tree
A binary tree whose nodes all have either two child-nodes or zero child-nodes
full binary tree
