SDE - Intern

Step-by-Step Explanation

Step 1: I initially thought of using a brute-force approach, where I checked every pair of elements using two nested loops to see if their sum equals the target.

Step 2: I realized this solution has a time complexity of O(N²), which is inefficient for large inputs. The interviewer then asked me to optimize it.

Step 3: I used a hash map to store each number and its index while iterating through the array.

Step 4: For each element, I checked whether (target − current element) already existed in the map. If it did, I returned the indices.

Step 5: This optimized the solution to O(N) time complexity with O(N) extra space, which satisfied the interviewer.

Step-by-Step Explanation

Step 1: I initially thought of a brute-force approach, where I would generate all possible subarrays and calculate their sums.

Step 2: This approach involved nested loops and had a time complexity of O(N²) (or O(N³) if sums were recalculated), which is inefficient for large inputs.

Step 3: The interviewer asked me to optimize the solution.

Step 4: I observed that if the current subarray sum becomes negative, it will only reduce the sum of any future subarray. Therefore, it is better to start a new subarray from the next element.

Step 5:
Using this insight, I applied Kadane’s Algorithm, maintaining two variables:

currentSum to store the maximum sum ending at the current index

maxSum to store the overall maximum subarray sum

Step 6: At each step, I updated currentSum = max(A[i], currentSum + A[i]) and updated maxSum accordingly.

Step 7: This optimized the solution to O(N) time complexity with O(1) space, which satisfied the interviewer.

Step-by-Step Explanation

Step 1: I first recalled the key property of a BST:

Inorder traversal gives elements in sorted order (ascending).

Step 2: To find the Kth largest element, I realized I needed the elements in descending order.

Step 3: I used reverse inorder traversal (Right → Root → Left), which visits nodes from largest to smallest.

Step 4: While traversing, I maintained a counter that increments each time a node is visited.

Step 5: When the counter became equal to K, I stored the current node’s value as the answer and stopped further traversal.

Step 6: This approach works in O(N) time in the worst case and uses O(H) space due to recursion, where H is the height of the tree.

Step 7: The interviewer was satisfied because the solution efficiently leveraged BST properties without using extra data structures.

Step-by-Step Explanation

Step 1: I first considered a brute-force approach, where I would remove each node one by one and check whether the graph becomes disconnected using DFS or BFS.

Step 2: This approach was inefficient because for every node removal, a full graph traversal is required, leading to a time complexity of O(V × (V + E)).

Step 3: The interviewer asked me to optimize the solution.

Step 4:
I used Tarjan’s Algorithm based on DFS traversal, maintaining:

disc[] → discovery time of each node

low[] → lowest discovery time reachable from that node

parent[] → parent of the node in the DFS tree

Step 5: During DFS:

A root node is critical if it has more than one DFS child.

A non-root node is critical if low[child] ≥ disc[node].

Step 6: Nodes satisfying these conditions were marked as critical nodes.

Step 7: This optimized the solution to O(V + E) time complexity using a single DFS traversal, which satisfied the interviewer.