SDE - 1

A straightforward approach that I tried was compute pow(x, n) involves multiplying x by itself n times. This can be achieved efficiently using a basic for loop. But it would fail time constraints. 

Employing the Divide and Conquer strategy:
To address the problem, adhere to the following approach:

The problem can be recursively defined as follows:

power(x, n) = power(x, n / 2) * power(x, n / 2); // if n is even
power(x, n) = x * power(x, n / 2) * power(x, n / 2); // if n is odd
And we compute power(x, n / 2) only once. This was the optimised solution O(logN) which passed the tests.

Brute force - Traverse through all oranges in successive rounds. During each round, move the oranges to adjacent positions of those that became rotten in the previous round. But this would fail the time complexity.

Optimised - The concept employs Breadth First Search (BFS) to track the rotting oranges. Oranges become rotten upon contact with other rotten oranges. This resembles a BFS strategy where the graph is organized into layers or cycles, and the search progresses from lower to higher layers.

In the earlier method, although BFS was utilized in concept, the execution was suboptimal and inefficient. Identifying the elements necessitated traversing the entire matrix. By adopting this more efficient BFS approach, time can be significantly minimized.

Brute force - A straightforward approach involves examining each pair and monitoring the pair with the smallest absolute difference between their sum and x. Subsequently, the closest pair is printed. The time complexity of this method amounts to O(n^2).

Binary Search Approach:- A more efficient solution compared to the previous approach involves utilizing Binary Search, leveraging the fact that the given array is sorted.

Brute force -Iterate through the given array, examining each window of size K, and tally the distinct elements within each window. Time complexity was O(N * K2) and interviewer told me to further optimise it.

Optimised using hashing - Count distinct numbers in all windows of size K using hashing. 
I was able to solve the problem in O(N) time and O(N) space and interviewer was satisfied.

I gave the very brute force solution first using Insertion Sort. It's time complexity was O(n2), space O(1).

The interview asked me to further optimise it.

So I gave him the solution using 2 heaps , a min heap and a max heap. The interviewer was satisfied with the solution and asked me to write code for the same. Time complexity O(n*logn) , space - O(n)

I started with a brute force solution by traversing over every contiguous subarray, finding the product of each of these subarrays and returning the maximum product from these results. Time was O(N^2) and interviewer asked me to optimise it.

Then I gave an optmised solution using Kadane’s algorithm and maintain 3 variables max_so_far, max_ending_here & min_ending_here. Iterate the indices 0 to N-1 and update the variables such that:

max_ending_here = maximum(arr[i], max_ending_here * arr[i], min_ending_here[i]*arr[i])
min_ending_here = minimum(arr[i], max_ending_here * arr[i], min_ending_here[i]*arr[i])
update the max_so_far with the maximum value for each index.
return max_so_far as the result.

The TC for this was reduced to O(N).
The interviewer was happy with this solution and asked me to write neat code for it.

I used Hashmaps & DLL(Doubly Linked List) to solve this.

Intuition:

While inserting the {key,val} pair into the DDL make sure that we are inserting it from the back tail to head.

The cache will tell us when the {key, value} pair is used/inserted.

Tip 1: Just be honest.
Tip 2: Read about Aamzon's leadership principles.
Tip 3: Don't try to fake anything. The Interviewer is more intelligent than you :)