Brainscape's Knowledge GenomeTM


Top Flashcards (Certified)
All Flashcards

Youtube review > DSA Youtube Playlist > Flashcards

DSA Youtube Playlist Flashcards

(75 cards)

Start Studying
1
Q

What is a data structure?

A

A way of organizing data so that it can be used effectively

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

What is an abstract data type?

A

A theoretical model that defines a data structure by its behavior (operations) and properties, independent of its implementation. It specifies what operations can be performed but not how they are implemented

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

What are implementations (data structures) that can be used for a list abstraction (abstract data type)?

A

Dynamic array, linked list

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

What are implementations (data structures) that can be used for a queue abstraction (abstract data type)?

A

Linked list based queue, array based queue, stack based queue (not a good implementation)

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

What are implementations (data structures) that can be used for a map abstraction (abstract data type)?

A

Tree map, hash map/hash table

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

What is Big-O notation?

A

It gives an upper bound of the complexity in the worst case, helping to quantify performance as the input size becomes arbitrarily large

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

What is the Big-O complexity for constant time?

A

O(1)

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

What is the Big-O complexity for logarithmic time?

A

O(log n)

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

What is the Big-O complexity for linear time?

A

O(n)

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

What is the Big-O complexity for linearithmic time?

A

O(n log n)

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

What is the Big-O complexity for quadratic time?

A

O(n^2)

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

What is the Big-O complexity for cubic time?

A

O(n^3)

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

What is the Big-O complexity for exponential time?

A

O(b^n), b > 1

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

What is the Big-O complexity for factorial time?

A

O(n!)

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

What is the Big-O of finding all subsets of a set?

A

O(2^n), exponential time

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

What is the Big-O of finding all permutations of a string?

A

O(n!), factorial time

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

What is the Big-O of sorting using mergesort?

A

O(n log n), linearithmic time

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

What is the Big-O of iterating over all the cells in a matrix of size n by m?

A

O(n * m)

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

What is a static array?

A

[Change] A fixed length container containing n elements indexable from the range [0, n-1]. Arrays: A collection of elements stored in contiguous memory locations, accessible by index.

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

When and where is a static array used?

A
  • Storing and accessing sequential data
  • Temporarily storing objects
  • Used by IO routines as buffers
  • Lookup tables and inverse lookup tables
  • Can be used to return multiple values from a function
  • Used in dynamic programming to cache answers to subproblems
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

What is the time complexity of accessing an element in a static array?

A

O(1)

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

What is the time complexity of accessing an element in a dynamic array?

A

O(1)

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

What is the time complexity of searching for an element in a static array?

A

O(n)

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

What is the time complexity of searching for an element in a dynamic array?

A

O(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
What is the time complexity of inserting/deleting an element in a static array?
Not applicable, static array is fixed size
26
What is the time complexity of inserting/deleting an element in a dynamic array?
O(n)
27
What is the time complexity of appending an element in a static array?
Not applicable, static array is fixed size
28
What is the time complexity of appending an element in a dynamic array?
O(1)
29
What is a dynamic array?
[Change] Can grow and shrink in size. Arrays: A collection of elements stored in contiguous memory locations, accessible by index.
30
What is a linked list?
A sequential list of nodes that hold data which point to other nodes also containing data
31
Where are linked lists used?
- In many List, Queue, and Stack implementations - For creating circular lists - Can easily model real world objects such as trains - In separate chaining, which is present in certain Hash table implementations to deal with hashing collisions - In the implementation of adjacency lists for graphs
32
What are singly linked lists?
Linked lists where each node only hold a reference to the next node
33
What are doubly linked lists?
Linked lists where each node holds a reference to the next and previous node
34
What are pros and cons of singly linked list?
Pros: Uses less memory, simpler implementation Cons: Cannot easily access previous elements
35
What are pros and cons of doubly linked list?
Pros: Can be traversed backward Cons: Takes 2x memory
36
What is the time complexity of searching a singly linked list?
O(n)
37
What is the time complexity of searching a doubly linked list?
O(n)
38
What is the time complexity of inserting a node at the head of a singly linked list?
O(1)
39
What is the time complexity of inserting a node at the head of a doubly linked list?
O(1)
40
What is the time complexity of inserting a node at the tail of a singly linked list?
O(1)
41
What is the time complexity of inserting a node at the tail of a doubly linked list?
O(1)
42
What is the time complexity of removing a node at the head of a singly linked list?
O(1)
43
What is the time complexity of removing a node at the head of a doubly linked list?
O(1)
44
What is the time complexity of removing a node at the tail of a singly linked list?
O(n)
45
What is the time complexity of removing a node at the tail of a doubly linked list?
O(1)
46
What is the time complexity of removing a node in the middle of a singly linked list?
O(n)
47
What is the time complexity of removing a node in the middle of a doubly linked list?
O(n)
48
What is a stack?
A LIFO (Last In, First Out) data structure where elements are added and removed from the top
49
What are the two main operations of a stack?
Push (add an element) and Pop (remove the top element)
50
When and where is a stack used?
- By undo mechanisms in text editors - In compiler syntax checking for matching brackets and braces - To model a pile of books or plates - Behind the scenes to support recursion by keeping track of previous function calls - To do a Depth First Search (DFS) on a graph
51
What is the time complexity of pushing on a stack?
O(1)
52
What is the time complexity of popping on a stack?
O(1)
53
What is the time complexity of peeking on a stack?
O(1)
54
What is the time complexity of searching a stack?
O(n)
55
What is the time complexity of getting the size of a stack?
O(1)
56
What is a queue?
A FIFO (First In, First Out) data structure where elements are added at the rear and removed from the front
57
What are the two main operations of a queue?
Enqueue (add an element) and Dequeue (remove an element)
58
When and where is a queue used?
- Any waiting line models a queue, e.g. a lineup at a movie theater - To efficiently keep track of the x most recently added elements - Web server request management where you want first come first serve - Breadth First Search (BFS) graph traversal
59
What is the time complexity of enqueue in a queue?
O(1)
60
What is the time complexity of dequeue in a queue?
O(1)
61
What is the time complexity of peeking in a queue?
O(1)
62
What is the time complexity of a contains operation in a queue?
O(n)
63
What is the time complexity of removing an element in a queue?
O(n)
64
What is the time complexity checking if a queue is empty?
O(1)
65
What is a heap?
A tree based data structure (DS) that satisfies the heap invariant (AKA heap property): If A is a parent node of B then A is ordered with respect to B for all nodes A, B in the heap
65
What is a priority queue?
An abstract data type (ADT) that operates similar to a normal queue except that each element has a certain priority. The priority of the elements in the priority queue determine the order in which the elements are removed from the PQ.
66
When and where is a priority queue (PQ) used?
- Certain implementations of Dijkstra's Shortest Path algorithm - Anytime you need to dynamically fetch the 'next best' or 'next worst' element - In Huffman coding (often used for lossless data compression) - Best First Search algorithms - Minimum Spanning Tree algorithms
67
What is the time complexity of constructing a binary heap?
O(n)
68
What is the time complexity of removing from a binary heap?
O(log n)
69
What is the time complexity of checking that value at the top of a binary heap?
O(1)
70
What is the time complexity of adding to a binary heap?
O(log n)
71
What is union find (AKA disjoint set)?
A data structure that keeps track of elements which are split into one or more disjoint sets. Its two primary operations are find and union.
72
When and where is a Union Find used?
- Kruskal's minimum spanning tree algorithm - Grid percolation - Network connectivity - Least common ancestor in trees - Image processing
73
What is Kruskal's Minimum Spanning Tree?
Given a graph G = (V, E) we want to find a Minimum Spanning Tree in the graph, i.e., a subset of the edges which connect all vertices in the graph with the minimal total edge cost
74

Youtube review (2 decks)

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