24 = 16 What is ? in 2? = 32

? is increased by 1 to 25 25 = 32

Data Structures Flashcards by Kelvin Waters

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.

How well did you know this?

Not at all

Perfectly

True or False

Data structures can be boiled down to the manipulation of data

True

manipulating data involves structuring that data.

How well did you know this?

Not at all

Perfectly

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)

How well did you know this?

Not at all

Perfectly

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?

How well did you know this?

Not at all

Perfectly

What is space-time complexity?

time: how fast algorithm runs
space: how much memory an algorithm is utilizing

all depends on the use-case

How well did you know this?

Not at all

Perfectly

True or False

Memory is a bounded type of storage

True

memory is finite (limited)

How well did you know this?

Not at all

Perfectly

bits are?

8 bits is a?

binary 0 and 1’s (base 2)

byte

How well did you know this?

Not at all

Perfectly

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.

How well did you know this?

Not at all

Perfectly

True or False

Accessing a memory address is just about instantaneous?

True

How well did you know this?

Not at all

Perfectly

True or False

32bit (fixed-width) is 4 bytes memory

True

How well did you know this?

Not at all

Perfectly

True or False

64bit (fixed-width) is 8 bytes memory

True

How well did you know this?

Not at all

Perfectly

A single byte can represent up to ___ data values

256

How well did you know this?

Not at all

Perfectly

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.

How well did you know this?

Not at all

Perfectly

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.

How well did you know this?

Not at all

Perfectly

Linear time is represented as?

O(n)

the running time increases at most linearly with the size of the input.

How well did you know this?

Not at all

Perfectly

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(n²) but not as well as O(n).

How well did you know this?

Not at all

Perfectly

Quadratic time is represented as?

O(n²)

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.

How well did you know this?

Not at all

Perfectly

Cubic time is represented as?

O(n³)

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.

How well did you know this?

Not at all

Perfectly

Exponential time is represented as?

O(2ⁿ)

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.

How well did you know this?

Not at all

Perfectly

Factorial time is represented as?

O(n!)

How well did you know this?

Not at all

Perfectly

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!

How well did you know this?

Not at all

Perfectly

In Big O Notation, which has a better time complexity? O(n) or O(1)

O(1) constant time

How well did you know this?

Not at all

Perfectly

In Big O Notation, which has a better time complexity? O(n) or O(log n)

O(log n) logarithmic time

How well did you know this?

Not at all

Perfectly

In Big O Notation, which has a better time complexity? O(n³) or O(n!)

O(n³) cubic time

How well did you know this?

Not at all

Perfectly

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(n²)

quadratic time

Cite the time complexity O(n³)

cubic

Cite the time complexity O(2ⁿ)

exponential

Cite the time complexity O(n!)

factorial

what is log(n) complexity analysis? ## Footnote *log_b(x)=y iif b^y=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)? *log_b(x)=y iif b^y=x*

True

True or False *log_b(n)=y iif b^y=n* **or** *log(n)=y iif 2^y=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 ## Footnote *2⁰ = 1*

*log(4) = ?*

2 ## Footnote * 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

*2⁴ = 16* What is ? in *2^? = 32*

? is increased by 1 to 2⁵ ## Footnote *2⁵= 32*

logarithmic time *O(log N)* is particular efficient because?

It's increases by 1 when the input *(n)* doubles! ## Footnote * 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? ## Footnote ``` string = 'this is a string object' newString = "" ``` for character in string: newString += character

*O(n²)* 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(n²) 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