Data Structures

Question 1

Arrays

Answer 1

Collection of elements stored in memory locations through which each element can be accessed by its index

Question 2

Accessing an element in array: time complexity

Answer 2

O(1)

Question 3

Deleting elements in the middle of an array: time complexity

Answer 3

O(n), because it may require shifting elements

Question 4

Linked Lists

Answer 4

Linked lists are a sequence of nodes where each node contains data and a reference to the next node

Question 5

There are two types of linked lists:

Answer 5

• Single linked lists (one-way links)
• Double linked lists (two-way links)

Question 6

For Linked Lists: insertion and deletion can be (enter time complexity) at head or end of tail

Answer 6

O(1)

Question 7

For linked lists: searching takes (enter time complexity) as you need to traverse the list

Answer 7

O(n)

Question 8

Stacks

Answer 8

A stack is a collection of elements that follows the Last-In, First-Out principle (LIFO). You can only insert (push) or remove (pop) elements from the top of the stack

Question 9

Stacks: push and pop operations both run in (insert time complexity)

Answer 9

O(1)

Question 10

Queues

Answer 10

A queue is a collection of elements that follows the First-In, First-Out (FIFO) principal. Elements are inserted at the back (enqueue) and removed from the front (dequeue). Therefore, the first element is pulled out by dequeue.

Question 11

Queues: both enqueue and dequeue run in (insert time complexity) in implementations like linked lists

Answer 11

O(1)

Question 12

Trees

Answer 12

A tree is a hierarchical data structure with nodes connected by edges. The top node is called the root, and each node may have children. It is non-linear compared to arrays and linked lists.

Question 13

Binary Trees

Answer 13

Binary Trees are trees in which each node has at most two children, referred to as the left child and the right child.

Question 14

Binary Search Trees

Answer 14

Binary Search Trees (BST) is a type of binary tree in which the left child of a node contains values less than the node, and the right child contains values greater than the node. This allows for efficient searching, insertion, and deletion.

Question 15

Binary trees have traversal operations with time complexity ____ (inorder, preorder, postorder)

Answer 15

O(n)

Question 16

Binary Search Trees: - In the AVG case, search, insert and delete operations run in ____, but the worst case (unbalanced tree) can lead to O(n)

Answer 16

O(log n)

Question 17

AVL Trees

Answer 17

AVL Tree is a self-balancing binary search tree. It ensures the height difference between the left and right subtrees (balance factor) is at most 1

Question 18

AVL Trees: - Insertions, deletions, and lookups all run in ____, as the tree remains balanced

Answer 18

O(log n)

Question 19

Hash Tables (DataFrames in Pandas)

Answer 19

Hash tables store key-value pairs and use hash functions to map keys to their values. Python’s dict and set use hash tables internally. In Pandas, DataFrames behave like a table where rows and columns are labeled and can hold heterogenous data

Question 20

Hash tables: Insertion, deletion, and lookup operations run in average-case O(1), though collisions can degrade performance to ___ in the worst case.

Answer 20

O(n)

Question 21

Hash tables are ideal for ____

Answer 21

fast lookups by key