DS Entretien 2 Flashcards
Bias and Variance
Bias = underfitting (too simple)
Variance = overfitting (too complex)
Time Complexity:
looping over N elements
for i in range(n)
O(N), linear
Time Complexity:
Nested Loops
for i in range(n): for j in range(n):
O(N^2), quadratic
Time Complexity:
Sorting
- order by column (SQL)
- quick sort, merge sort
O(N log N)
Time Complexity:
Using an index
- where id = x (SQL)
O (log N), logarathmic
Space Complexity:
Single variable
O(1), linear
Space Complexity:
Array of size N
O(N), linear
Space Complexity:
2D matrix of size NxN
O(N^2), quadratic
Complexity:
Select avg(sales) over (order by month rows between 2 preceding and current row) from sales_data
- O(N log N) time complexity
- Space O(1)
Complexity:
select customer
from orders
group by customer
having count(order_id)>2;
- Group by causes extra space of O(N)
- Time complexity is O(N log N) as counting order_id is O(N) and group by is O(N log N)
Complexity:
Select rank() over (partition by department order by salary desc) as rank_salary
From employees
Where rank_salary <= 3;
- O(N log N) time, because database needs to sort the data into departments (partition by department)
- O(N) space for the storage required when partitioning
Complexity:
select tweet_id
from Tweets
where length(content)>15;
- Time complexity: O(N) full table scan
- O(1) space complexity, no extra storage beyond the query execution
Complexity:
def count_salary_categories(accounts: pd.DataFrame) -> pd.DataFrame:
low = len(accounts[accounts.income<20000])
high = len(accounts[accounts.income>50000])
avg = len(accounts) - low - high
return pd.DataFrame(
{‘category’: [‘Low Salary’,’Average Salary’,’High Salary’], ‘accounts_count’:[low,avg,high]})
- Time complexity O(N)
- Len lines scan table, filtering data O(N), although Len operation itself is O(1)
- Pd.dataframe creates 3 rows so its constant O(1)- Space complexity O(1)
- Len lines are integers (constant space) O(1)
- Dataframe is constant size too
- Space complexity O(1)
What’s a holdout set?
A holdout set is a portion of data that is separated from the training set and used to evaluate the performance of a machine learning model after it has been trained.
When to use grid search or random search for hyper parameter tuning.
Grid search tries every possible parameter combination (comp expensive). Random only tries a subset but works pretty well.
Use Grid Search when you have <100 combinations and want precision.
Use Random Search when you have hundreds or thousands of possible combinations and need efficiency
Why are insertions and deletions more efficient in linked lists than arrays?
Arrays require shifting elements when inserting/deleting from the beginning or middle, making these operations O(n). Linked lists use pointers, allowing O(1) insertion/deletion at the head since no shifting is needed. However, inserting or deleting in the middle or end still requires traversal (O(n)).
What is the time complexity of inserting an element at the head of a linked list?
O(1). The new node is created, pointed to the current head, and the head pointer is updated. No shifting is required.
What is the time complexity of inserting an element in the middle of a linked list?
O(n). The list must be traversed to find the insertion point before updating pointers.
What is the time complexity of deleting an element at the head of a linked list?
O(1). The head pointer is updated to the next node, and the old head is freed.
What is the time complexity of deleting an element in the middle of a linked list?
O(n). The list must be traversed to locate the node before updating pointers.
How does inserting in an array compare to inserting in a linked list?
Inserting at the head of an array is O(n) due to shifting, while it is O(1) in a linked list. Inserting in the middle or end of both structures is O(n) unless a tail pointer is used in a linked list, which makes end insertions O(1).
How does deleting in an array compare to deleting in a linked list?
Deleting at the head of an array is O(n) due to shifting, while it is O(1) in a linked list. Deleting in the middle or end is O(n) in both structures unless a tail pointer exists in a doubly linked list, making end deletions O(1).
How does Merge Sort work, and what is its time complexity?
Merge Sort is a divide-and-conquer algorithm that:
1. Recursively splits the array into two halves until each half has one element.
2. Merges the sorted halves back together in a sorted order.
Time Complexity:
- Best, Worst, and Average Case: O(n log n)
- Space Complexity: O(n) (due to extra space for merging)
- Stable? Yes (maintains relative order of equal elements)
None
What is Quick Sort, and why is it efficient in practice?
Quick Sort is a divide-and-conquer algorithm that:
1. Selects a pivot element.
2. Partitions the array into elements smaller and larger than the pivot.
3. Recursively sorts the subarrays.
Time Complexity:
- Best and Average Case: O(n log n)
- Worst Case: O(n²) (if the pivot is always the smallest or largest element)
- Space Complexity: O(log n) (for recursion)
- Stable? No (swaps can change the relative order of equal elements)
- Why is it fast in practice? Has good cache locality and usually outperforms Merge Sort for large datasets.
None
How does Binary Search work, and what are its advantages?
Binary Search is an efficient search algorithm that:
1. Checks the middle element of a sorted array.
2. If the target is smaller, it searches the left half; if larger, it searches the right half.
3. Repeats until the element is found or the search space is empty.
Time Complexity: O(log n)
Space Complexity: O(1) (iterative), O(log n) (recursive)
Limitations: Only works on sorted arrays.
None
When is Linear Search better than Binary Search?
Linear Search checks each element one by one.
- Best for: Unsorted or small datasets.
- Time Complexity: O(n) (worst case)
- When to use it? When data is unsorted, or when you expect the target to be near the beginning.
None
What is Gradient Descent, and what are its types?
Gradient Descent is an optimization algorithm used in ML to minimize loss functions by updating model parameters.
Types:
- Batch Gradient Descent: Uses all data points; slow but stable.
- Stochastic Gradient Descent (SGD): Updates after each data point; noisy but faster.
- Mini-Batch Gradient Descent: Uses small batches; balances speed and stability.
None
What is the EM Algorithm, and where is it used?
The EM Algorithm finds maximum likelihood estimates for models with latent variables (e.g., Gaussian Mixture Models).
1. Expectation Step (E-step): Estimates missing data based on current parameters.
2. Maximization Step (M-step): Updates parameters to maximize likelihood.
3. Repeats until convergence.
Used in clustering (GMMs), HMMs, and topic modeling.
None
What is BFS, and when is it used?
BFS explores a graph level by level using a queue.
- Time Complexity: O(V + E) (V = vertices, E = edges)
- Used for: Finding shortest paths (unweighted graphs), web crawling, network broadcasting.
None
How does DFS work, and what are its applications?
DFS explores as deep as possible before backtracking.
- Time Complexity: O(V + E)
- Used for: Cycle detection, topological sorting, solving mazes.
None
What is Dijkstra’s Algorithm, and when does it fail?
Finds the shortest path in a weighted graph using a priority queue.
- Time Complexity: O((V + E) log V) with a priority queue
- Fails when: Graph has negative weights (use Bellman-Ford instead).
None
What is K-Means, and what are its limitations?
K-Means partitions data into K clusters by minimizing variance.
- Limitations: Sensitive to initialization, assumes spherical clusters, struggles with non-convex shapes.
None
How does DBSCAN handle noise better than K-Means?
DBSCAN groups dense regions and labels outliers separately.
- Advantages: Detects arbitrary-shaped clusters, handles noise well.
- Limitations: Struggles with varying density clusters.
None
What does PCA do, and how does it work?
PCA reduces dimensionality by transforming data into uncorrelated principal components.
- Steps:
1. Standardize the data.
2. Compute the covariance matrix.
3. Find eigenvalues/eigenvectors.
4. Select top k eigenvectors.
- Used in: Feature reduction, noise filtering, data visualization.
None
Why is t-SNE better for visualization than PCA?
t-SNE preserves local structures in high-dimensional data, making clusters more visible, while PCA preserves global structure.
- Limitation: Computationally expensive, non-deterministic.
None
How is LDA different from PCA?
LDA:
- Supervised: Maximizes class separability.
- Used for: Feature reduction in classification tasks.
PCA:
- Unsupervised: Maximizes variance.
None
What is Dynamic Programming, and when is it useful?
DP solves problems by breaking them into overlapping subproblems and storing results to avoid redundant calculations.
- Used in: Time series forecasting, reinforcement learning, optimization problems (e.g., Knapsack, Fibonacci).
None
What is the time complexity of Merge Sort?
O(n log n)
Merge Sort is a divide-and-conquer algorithm that splits the array into halves, sorts each half, and merges them back together.
What is the space complexity of Merge Sort?
O(n)
What is the description of Quick Sort?
A divide-and-conquer algorithm that selects a pivot and partitions the array around the pivot, sorting recursively.
What is the time complexity of Quick Sort in the worst case?
O(n²)
What is the space complexity of Quick Sort?
O(log n)
What does Binary Search do?
Finds the position of a target value within a sorted array by repeatedly dividing the search interval in half.
What is the time complexity of Binary Search?
O(log n)
What is the space complexity of Binary Search?
O(1)
What is Ternary Search?
A variation of binary search that divides the array into three parts and eliminates two-thirds of the search space each time.
What is the time complexity of Ternary Search?
O(log₃ n)
What is the space complexity of Ternary Search?
O(1)
What is Counting Sort?
A non-comparative sorting algorithm that counts the occurrences of each element and uses this information to place elements in the correct position.
What is the time complexity of Counting Sort?
O(n + k)
What is the space complexity of Counting Sort?
O(k)
What is Radix Sort?
A non-comparative sorting algorithm that sorts numbers digit by digit starting from the least significant digit.
What is the time complexity of Radix Sort?
O(nk)
What is the space complexity of Radix Sort?
O(n + k)
What does BFS stand for?
Breadth-First Search
What is the time complexity of BFS?
O(V + E)
What is the space complexity of BFS?
O(V)
What is the description of DFS?
A graph traversal algorithm that explores as far as possible along each branch before backtracking.
What is the time complexity of DFS?
O(V + E)
What is the space complexity of DFS?
O(V)
What is Dijkstra’s Algorithm used for?
Finds the shortest paths from a source node to all other nodes in a weighted graph.
What is the time complexity of Dijkstra’s Algorithm using priority queue?
O(E + V log V)
What is the space complexity of Dijkstra’s Algorithm?
O(V)
What does the Bellman-Ford Algorithm handle?
Negative edge weights and detects negative weight cycles.
What is the time complexity of Bellman-Ford Algorithm?
O(V * E)
What is the space complexity of Bellman-Ford Algorithm?
O(V)
What is the A* Algorithm?
A pathfinding algorithm that uses heuristics to find the shortest path while optimizing search time.
What is the time complexity of the A* Algorithm?
O(E)
What is the space complexity of the A* Algorithm?
O(V)
What does the Floyd-Warshall Algorithm do?
Finds all pairs shortest paths in a graph.
What is the time complexity of the Floyd-Warshall Algorithm?
O(V³)
What is the space complexity of the Floyd-Warshall Algorithm?
O(V²)
What is Kruskal’s Algorithm used for?
Finding the minimum spanning tree of a graph by adding edges in increasing weight order.
What is the time complexity of Kruskal’s Algorithm?
O(E log E)
What is the space complexity of Kruskal’s Algorithm?
O(E)
What does Prim’s Algorithm do?
Finds the minimum spanning tree by growing the tree one vertex at a time.
What is the time complexity of Prim’s Algorithm?
O(E log V)
What is the space complexity of Prim’s Algorithm?
O(V + E)
What is Tarjan’s Algorithm used for?
Finding strongly connected components (SCC) in a directed graph.
What is the time complexity of Tarjan’s Algorithm?
O(V + E)
What is the space complexity of Tarjan’s Algorithm?
O(V)
What does Hopcroft-Karp Algorithm find?
The maximum matching in a bipartite graph.
What is the time complexity of Hopcroft-Karp Algorithm?
O(√V * E)
What is the space complexity of Hopcroft-Karp Algorithm?
O(V + E)
What is Topological Sort?
A linear ordering of vertices in a Directed Acyclic Graph (DAG).
What is the time complexity of Topological Sort?
O(V + E)
What is the space complexity of Topological Sort?
O(V)
What does Kadane’s Algorithm find?
The maximum sum subarray in an array of integers.
What is the time complexity of Kadane’s Algorithm?
O(n)
What is the space complexity of Kadane’s Algorithm?
O(1)
What is Floyd’s Cycle Detection (Tortoise and Hare)?
A fast and slow pointer algorithm used to detect cycles in a linked list.
What is the time complexity of Floyd’s Cycle Detection?
O(n)
What is the space complexity of Floyd’s Cycle Detection?
O(1)
What does the Knapsack Algorithm solve?
The 0/1 knapsack problem by finding the optimal selection of items.
What is the time complexity of the Knapsack Algorithm?
O(n * W)
What is the space complexity of the Knapsack Algorithm?
O(n * W)
What is the Longest Common Subsequence (LCS)?
A dynamic programming algorithm to find the longest subsequence common to two sequences.
What is the time complexity of Longest Common Subsequence?
O(m * n)
What is the space complexity of Longest Common Subsequence?
O(m * n)
What does the Bellman-Ford Algorithm (DP version) do?
Finds the shortest paths from a source to all vertices in a graph with negative weights.
What is the time complexity of Bellman-Ford Algorithm (DP version)?
O(V * E)
What is the space complexity of Bellman-Ford Algorithm (DP version)?
O(V)
What does Longest Increasing Subsequence (LIS) find?
The longest subsequence in a sequence where the elements are in strictly increasing order.
What is the time complexity of Longest Increasing Subsequence?
O(n²)
What is the space complexity of Longest Increasing Subsequence?
O(n)
What does the Coin Change Problem solve?
Finds the minimum number of coins required to make a given amount using a set of denominations.
What is the time complexity of the Coin Change Problem?
O(n * m)
What is the space complexity of the Coin Change Problem?
O(n)
What is Union-Find (Disjoint Set Union)?
A data structure to manage a partition of a set into disjoint subsets.
What is the time complexity of Union-Find per operation?
O(α(n))
What is the space complexity of Union-Find?
O(n)
What is a Segment Tree?
A tree-based data structure that supports range queries and updates efficiently.
What is the time complexity of Segment Tree for queries and updates?
O(log n)
What is the space complexity of Segment Tree?
O(n)
What is a Trie (Prefix Tree)?
A tree-based data structure used for efficient string storage and retrieval.
What is the time complexity of Trie for search/insert?
O(m)
What is the space complexity of Trie?
O(m * n)
What does KMP Algorithm stand for?
Knuth-Morris-Pratt
What is the time complexity of KMP Algorithm?
O(m + n)
What is the space complexity of KMP Algorithm?
O(m)
What is Reservoir Sampling?
An algorithm for selecting k random samples from a stream of data where the total number of elements is unknown.
What is the time complexity of Reservoir Sampling?
O(n)
What is the space complexity of Reservoir Sampling?
O(1)
What is Fenwick Tree (Binary Indexed Tree)?
A data structure that provides efficient methods for querying and updating prefix sums in a dynamic array.
What is the time complexity of Fenwick Tree for updates and queries?
O(log n)
What is the space complexity of Fenwick Tree?
O(n)
