Software Developer

I had previously solved a similar problem, so I had an idea of how to approach the solution. First, I asked the interviewer for test cases and then explained my thought process, outlining how the problem could be solved using the Sliding Window technique.
Approach:
Step1 : Declare two pointers i and j representing the window [i.....j].
Step2 : Use a variable count to store the number of 0s in the current window.
Step3 : If the window is valid (count <= k), expand it and update the answer; otherwise, shrink it from the left.
Time Complexity: O(N), Space Complexity: O(1).

Explanation: It took me some time to dry-run the problem, and then I explained that this can be solved using a simple DFS function.
Steps: 

Perform a DFS traversal to find the maximum path value if the current node is the root. 

Identify the two child nodes with the highest path sums and combine them.
The time complexity is O(N), and the space complexity is O(N).

Least Recently Used (LRU)
LRU discards the least recently used item when the cache reaches its capacity.
It is effective in scenarios where recently accessed elements are more likely to be used again.
Implemented using a doubly linked list and a hash map, where the most recently accessed item is moved to the front, and the least recently accessed is at the back.

Least Frequently Used (LFU)
LFU discards the least frequently used item when the cache is full.
It is useful when some elements are accessed far more often than others.
Implemented using a frequency map, where each frequency bucket contains keys used that many times.

Hybrid Approach (LRU + LFU)
The cache should be adaptive, meaning:
If multiple items have the same frequency, use LRU to decide eviction.
If an item is accessed more frequently, it should remain in the cache even if it was accessed a long time ago.
The cache should maintain both recency and frequency to make efficient eviction decisions.

You can find the odd ball in just 2 operations using the following approach:
1. Divide the 9 balls into 3 groups, each containing 3 balls.
2. Perform the first weighing:
-> Compare two groups on the weighing machine.
-> If both groups are equal in weight, the odd ball is in the third group.
-> If the weights differ, the lighter group contains the odd ball.
3. Perform the second weighing:
-> From the identified group of 3 balls, pick any two balls and compare their weights.
-> If they are equal, the third ball is the odd one.
-> If they are unequal, the lighter ball is the answer.