Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

AlgoExpert > Data Structures > Flashcards

Data Structures Flashcards

1
Q

What are data structures?

A

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?
1
Not at all
2
3
4
5
Perfectly
2
Q

True or False

Data structures can be boiled down to the manipulation of data

A

True

manipulating data involves structuring that data.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is complexity analysis?

A

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?
1
Not at all
2
3
4
5
Perfectly
4
Q

During a coding interview, when asked (about your code) “can you improve it and do better” is usually referring to?

A

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?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is space-time complexity?

A

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?
1
Not at all
2
3
4
5
Perfectly
6
Q

True or False

Memory is a bounded type of storage

A

True

memory is finite (limited)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

bits are?

8 bits is a?

A

binary 0 and 1’s (base 2)

byte

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

True or False

pointers can be allocated in memory as well

A

True

and pointers aren’t memory intensive and don’t have to be in continuous memory.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

True or False

Accessing a memory address is just about instantaneous?

A

True

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

True or False

32bit (fixed-width) is 4 bytes memory

A

True

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

True or False

64bit (fixed-width) is 8 bytes memory

A

True

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

A single byte can represent up to ___ data values

A

256

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Constant time is represent as?

A

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?
1
Not at all
2
3
4
5
Perfectly
14
Q

Logarithmic time is represented as?

A

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?
1
Not at all
2
3
4
5
Perfectly
15
Q

Linear time is represented as?

A

O(n)

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Log-Linear time is represented as?

A

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).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Quadratic time is represented as?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Cubic time is represented as?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Exponential time is represented as?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Factorial time is represented as?

A

O(n!)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

True or False

In terms on Big O Notation, it’s always in the context of the worst case senario?

A

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?
1
Not at all
2
3
4
5
Perfectly
22
Q

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

A

O(1) constant time

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

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

A

O(log n) logarithmic time

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

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

A

O(n3) cubic time

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

Cite the time complexity

O(1)

A

constant time

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

Cite the time complexity

O(log n)

A

logarithmic time

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

Cite the time complexity

O(n)

A

linear time

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

Cite the time complexity

O(n * log n)

A

log linear time

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

Cite the time complexity

O(n2)

A

quadratic time

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

Cite the time complexity

O(n3)

A

cubic

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

Cite the time complexity

O(2n)

A

exponential

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

Cite the time complexity

O(n!)

A

factorial

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

what is log(n) complexity analysis?

logb(x)=y iif by=x

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
34
Q

True or False

In log(n) the base is assumed to be base 2(binary)?

logb(x)=y iif by=x

A

True

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
35
Q

True or False

logb(n)=y iif by=n or log(n)=y iif 2y=n

are one in the same

A

True

This is just log(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
36
Q

True or False

Computer science deals with log base 10?

A

False

Computer science uses log base 2, dealing with binary values.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
37
Q

log(1) = ?

A

0

20 = 1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
38
Q

log(4) = ?

A

2

  • 2? = 4*
  • 2 * 2 = 4*
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
39
Q

log(16) = ?

A

4

2? = 16

2 * 2 * 2 * 2 = 16

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
40
Q

How would you find the log of (n)?

A

2? = (n)

the ? is the log of n

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
41
Q

True or False

2? = n

when you double n you’re increasing ? by 1

A

True

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
42
Q

2? = n

when you increase ? by one, you’re _______ n

A

doubling

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
43
Q

24 = 16

What is ? in 2? = 32

A

? is increased by 1 to 25

25 = 32

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
44
Q

logarithmic time

O(log N)

is particular efficient because?

A

It’s increases by 1 when the input (n) doubles!

  • log(n) = y*
  • y is the ? in n?*
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
45
Q

Array - Cite the time complexity

Accessing a value at a given index?

A

O(1) constant time

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
46
Q

Array - Cite the time complexity

Updating a value at a given index?

A

O(1) constant time

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
47
Q

Array - Cite the time complexity

Inserting a value at the begining?

A

O(n) linear time

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
48
Q

Array - Cite the time complexity

Inserting a value in the middle?

A

O(n) linear time

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
49
Q

Array - Cite the time complexity

Inserting a value at the end (dynamic array)?

A

amoritized O(1) contstant time

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
50
Q

Array - Cite the time complexity

Inserting a value at the end (static array)?

A

O(n) linear time

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
51
Q

Array - Cite the time complexity

Removing a value at the begining?

A

O(n) linear time

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
52
Q

Array - Cite the time complexity

Removing a value in the middle?

A

O(n) linear time

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
53
Q

Array - Cite the time complexity

Removing a value at the end?

A

O(1) constant time

54
Q

Array - Cite the time complexity

Copying an array?

A

O(n) linear time

55
Q

A func that runs at constant time O(1) means what exactly?

A

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

56
Q

What is the time complexity of __init__ of an array object?

A

O(n) linear time

57
Q

What is the time complexity when traversing an array?

A
  • O(n) linear time*
  • O(1)* space
58
Q

What is the time complexity when copying an array?

A
  • O(n) linear time*
  • O(n) space*
59
Q

What is amortized analysis?

A

a method for analyzing a given algorithm’s complexity, or how much of a resource, especially time or memory, it takes to execute.

60
Q

What is the time complexity of using the built-in pop() method to remove and element from the end of an array?

A

constant time O(1)

61
Q

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?

A

linear time O(n)

62
Q

True or False

Like an array, linked lists are stored in continuous memory locations?

A

False

Linked lists use pointers in memory

63
Q

What is this?

[1, 2, 3, 4, 5]

A

an array

64
Q

What is this?

[1->, 2->, 3->, 4->, 5]

A

linked list

65
Q

A listed list has what time complexity?

A

O(i) time

must traverse through i nodes

66
Q

Linked list - time complexity

Accessing the head?

A

O(1) constant time

67
Q

Linked list - time complexity

Accessing the tail?

A

O(n) linear time

68
Q

Linked list - time complexity

Accessing the middle node?

A

O(n) linear time

69
Q

Linked list - time complexity

Inserting / removing the head?

A

O(1) constant time

70
Q

Linked list - time complexity

Inserting / removing the tail?

A

O(n) to access + O(1)

71
Q

Linked list - time complexity

Inserting / removing the middle node?

A

O(n) to access + O(1)

72
Q

Linked list - time complexity

Searching for a value?

A

O(n) linear time

73
Q

Doubly linked list - time complexity

Accessing the head?

A

O(1) constant time

74
Q

Doubly linked list - time complexity

Accessing the tail?

A

O(1) constant time

75
Q

Doubly linked list - time complexity

Accessing a middle node?

A

O(n) linear time

76
Q

Doubly linked list - time complexity

Inserting / removing the head?

A

O(1) constant time

77
Q

Doubly linked list - time complexity

Searching for a value?

A

O(n) linear time complexity

78
Q

Doubly linked list - time complexity

Inserting / removing the tail?

A

O(1) constant time

79
Q

Doubly linked list - time complexity

Inserting / removing a middel node?

A

O(n) to access + O(1)

80
Q

True or False

Like an array a link-list can be indexed

A

False

Linked lists have nodes that don’t function like an arrays idx

81
Q

True or False

The space time for both the __init__ of an array and linked list is O(n) linear time

A

True

82
Q

True or False

In a Python dict (hash table) inserting, deleting, and searching all have a time complexity of O(1) constant time!

A

True on average but

O(n) linear time in worst case senario, collisions and having to rely on a linked-list data structure underneath.

83
Q

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?

A

True

84
Q

Describe how a hash function operates.

A

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

85
Q

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.

A

True

86
Q

What is a collison when describing a hash table?

A

When more than a single key is assigned (hashed to) indentical values.

87
Q

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.

A

True

88
Q

True or False

hashing keys are O(1) constant time operations?

A

True

89
Q

What is an array-like structure that follows the LIFO: Last In First Out rule?

A

a stack

90
Q

Pushing an element on a stack is what time complex?

A

O(1) constant time

91
Q

Popping or removing an element from a stack is what time complexity?

A

O(1) constant time

92
Q

Peeking at the top element of a stack is accomplished in what time complexity?

A

O(1) constant time

93
Q

Searching for an element in a stack has what time complexity?

A

O(n) linear time

94
Q

An array-like data structure that implements the FIFO: First In First Out rule?

A

a Queue

95
Q

Enqueuing a queue has ___ time complexity.

A

O(1) constant time

96
Q

Dequeuing a queue takes ____ time complexity

A

O(1) constant time

97
Q

Peeking a the first element in a queue is perform in ____ time

A

O(1) constant

98
Q

Searching for an queue element is performed in _____ time

A

O(n) linear

99
Q

True or False

A stack is usually implemented with a dynamic-array or a singly-linked list

A

True

100
Q

True or False

A queue is implemented with a doubly linked-list

A

True

101
Q

True or False

strings are stored in memory as arrays of integers

A

True

102
Q

True or False

strings are mutable

A

True

103
Q

What is the time complexity of the string code?

string = 'this is a string object'
newString = ""

for character in string:
newString += character

A

O(n2) because each addition of a char to newString creates an entirely new string and is itself O(n) operation

104
Q

Traversing a str has what time complexity?

A
  • O(n)* time identical to an array
  • O(1)* space
105
Q

The complexity of copying a string?

A

O(n) time and space

106
Q

The complexity of getting a string?

A

O(1) constant time and space

107
Q

True or False

strings are immutable

A

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

108
Q

Define a collection of nodes or values called vertices that may be related; relations between vertices are called edges

A

graph

109
Q

a ______ cycle occurs in a ______ when three of more vertices are connected so as to form a closed loop

A

graph

110
Q

a graph that has no cycles

A

acyclic graph

111
Q

a graph that has at least one cycle

A

cyclic graph

112
Q

a graph whose edges are directed, meaning that they can only traverse in one direction, which is specified.

A

directed graph

113
Q

a graph whose edges are undirected, meaning they can traverse in both directions

A

undirected graph

114
Q

if for every pair of vertices in the graph there’s a path of one or more edges connection the given vertices

A

connected graph

115
Q

Cite two attributes of a direct graph

A

strongly connected - bidirectional

weakly connected - not bidirectional

116
Q

What is a graph in space complexity?

A

O(v+e)

vertices + edges

117
Q

What are the two ways to traverse a graph?

A
  • breath* first search
  • depth* first search
118
Q

What is a graph in time complexity?

A
  • O(v+e)*
  • vertices + edges*
119
Q

A data structure that consists of nodes, each with some value and pointers to child-nodes, which recursively form _____ in the tree

A

subtrees

120
Q

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 ______.

A

root
leaf nodes, leaves

121
Q

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.

A

branches, height

122
Q

A tree is effectively a ______

A

graph

123
Q

A tree is effectively a graph that’s ______, _______, and _______ that has an explicit root node, and whose nodes all have a single _______

A

connected, directed, acyclic, parent

124
Q

There are many types of trees and tree-like structures, including

A

binary trees, heaps, and tries (pronounced trees)

125
Q

A tree whose nodes have up to two child-nodes

A

binary tree

126
Q

A tree whose nodes have up to k child nodes

A

K-ary tree

A binary tree is a k-ary tree where k == 2

127
Q

A binary tree whose interior nodes all have two child-nodes and whose leaf nodes all have the same depth is a?

A

perfect binary tree

128
Q

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.

A

complete binary tree

129
Q

A binary tree whose nodes all have left and right subtress whose heights differ by no more than 1

A

balanced binary tree

130
Q

A binary tree whose nodes all have either two child-nodes or zero child-nodes

A

full binary tree

AlgoExpert (5 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions