Brainscape's Knowledge GenomeTM


Top Flashcards (Certified)
All Flashcards

Youtube review > Improved DSA Review > Flashcards

Improved DSA Review Flashcards

(95 cards)

Start Studying
1
Q

What is a data structure?

A

A way of organizing data so that it can be used effectively. A concrete implementation of an ADT using actual code and memory layout

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 concept or model that defines how data can be used and what operations are allowed. 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

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

Static arrays are used when the size of the data is fixed and fast access by index is needed. Common use cases include:
* Storing and accessing sequential data efficiently
* Temporary object storage
* Buffers in I/O routines
* Lookup and inverse lookup tables
* Returning multiple values from a function
* Dynamic programming tables for memoization

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?
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?
Linked lists are used in many situations where dynamic memory and flexible structure are important, including: * Implementing List, Queue, and Stack data structures * Creating circular lists for cyclic processes * Modeling real-world sequences, like trains or playlists * Separate chaining in hash tables to handle collisions * Adjacency lists in graphs to efficiently store neighbors
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?
Stacks are used in many computing scenarios where Last-In, First-Out (LIFO) behavior is needed, including: * Undo functionality in text editors (last action undone first) * Syntax checking in compilers (e.g., matching parentheses or braces) * Supporting recursion by storing function call frames * Depth-First Search (DFS) traversal in graphs * Modeling real-world stacks like plates, books, or browser history
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?
Queues model situations where First-In, First-Out (FIFO) order is important, such as: * Waiting lines like a movie theater queue or customer service line * Managing web server requests to ensure fair, first-come-first-served processing * Keeping track of the most recent x elements efficiently * Performing Breadth-First Search (BFS) in graphs
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
66
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.
67
When and where is a priority queue (PQ) used?
Priority queues are used when elements must be processed based on priority, such as: * Dijkstra’s shortest path algorithm for efficient edge selection * Dynamically retrieving the next best or worst element in scheduling or resource management * Huffman coding for lossless data compression * Best-First Search algorithms in AI and pathfinding * Minimum Spanning Tree algorithms like Prim’s and Kruskal’s
68
What is the time complexity of constructing a binary heap?
O(n)
69
What is the time complexity of removing from a binary heap?
O(log n)
70
What is the time complexity of checking the value at the top of a binary heap?
O(1)
71
What is the time complexity of adding to a binary heap?
O(log n)
72
What is union find (AKA disjoint set)?
A data structure that keeps track of a collection of disjoint (non-overlapping) sets. Its two primary operations are find and union.
73
When and where is a Union Find used?
Union Find is used in problems involving grouping and connectivity, including: * Kruskal’s Minimum Spanning Tree algorithm to detect cycles and connect components * Grid percolation and connectivity analysis in simulations * Network connectivity to quickly check if nodes are in the same network * Finding Least Common Ancestors in trees (in some algorithms) * Applications in image processing like segmentation
74
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
75
What is hashing?
Hashing is the process of converting data into a fixed-size numerical value (hash) using a hash function. It is used to quickly index and retrieve data in structures like hash tables.
76
What is a hash table?
A data structure that stores key-value pairs and uses a hash function to compute the index into an array of buckets from which the desired value can be found.
77
What are common hash table collision resolution strategies?
Chaining (linked lists in buckets), open addressing (linear probing, quadratic probing, double hashing)
78
What is the average time complexity of insertion, deletion, and search in a hash table?
O(1) average case, O(n) worst case (due to collisions)
79
What is a binary search tree (BST)?
A binary tree in which for every node, all elements in the left subtree are less than the node, and all elements in the right subtree are greater.
80
What is the time complexity of search, insert, and delete in a BST?
O(log n) average case, O(n) worst case (unbalanced tree)
81
What is a balanced binary search tree?
A BST where the height difference between the left and right subtree is small. The height is kept to O(log n). Examples: AVL Tree, Red-Black Tree.
82
What are the main tree traversal methods?
In-order (LNR), Pre-order (NLR), Post-order (LRN), Level-order (BFS)
83
What is the time complexity of traversing a binary tree with n nodes?
O(n)
84
What is a graph?
A collection of nodes (vertices) and edges that connect pairs of nodes. Graphs may be directed or undirected, weighted or unweighted.
85
What are two common ways to represent graphs?
Adjacency list and adjacency matrix
86
What is Depth First Search (DFS)?
A graph traversal algorithm that explores as far as possible along each branch before backtracking. Can be implemented using a stack or recursion.
87
What is Breadth First Search (BFS)?
A graph traversal algorithm that explores all neighbors of a node before moving to the next level. Implemented using a queue.
88
What is the time complexity of BFS and DFS?
O(V + E), where V is the number of vertices and E is the number of edges.
89
What is recursion?
When a function calls itself to solve smaller instances of the same problem.
90
What are the components of a recursive function?
Base case(s) and recursive case(s)
91
What is dynamic programming?
A method for solving problems by breaking them into overlapping subproblems, solving each only once, and storing the result.
92
What are two main approaches to dynamic programming?
Top-down (memoization) and bottom-up (tabulation)
93
What is the sliding window technique?
A technique for problems involving contiguous sequences in arrays/lists where a window is moved over the data to reduce nested iteration.
94
What is the two pointer technique?
A pattern where two pointers are used to iterate through a structure in a coordinated way, often used for sorted arrays or linked lists.
95
What are key system design concepts every entry-level engineer should know?
Scalability, load balancing, caching, latency vs throughput, database sharding, CAP theorem

Youtube review (3 decks)

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