Software Developer

The most basic approach is to merge both the sorted arrays using an auxiliary array. The median would be the middle element in the case of an odd-length array or the mean of both middle elements in the case of even length array.
The merging of two sorted arrays can be done in a way similar to merge sort. The time complexity of this approach would be O(n+m). 
A better solution is to use binary search. 

Steps :
 

1. Find the length of the smaller arrays of the two. Perform binary search on the smaller array.
 

2. Initialize two pointers - start = 0 and end = m (assuming m is the smaller length).
 

3. Run a while loop : while (start <= end) { ... }.
 

4. Calculate the partition index (partitionA) for a which is the mid-point of start and end i.e., (start + end) / 2.
 

5. Calculate the partition index (partitionB) for b which is (m + n + 1) / 2 - partitionA.
 

6. Find the maximum element in the left of a and b and minimum element in the right of a and b.
Now, we can have three cases -
(i) If (maxLeftA <= minRightB && maxLeftB <= minRightA), then return the median based on (m + n) is even or odd.
(ii) Else If (maxLeftA > minRightB), it means, we need to go on the left, so, set end = partitionA - 1.
(iii) Else, we need to go to the right, so, set start = partitionA + 1.

This was a pretty standard Binary Search Question and I had solved this question before on platforms like LeetCode and CodeStudio . I was asked this question to test my implementation skills and how well do I handle Edge Cases .

Approach :

1) The idea is to find the pivot point, divide the array in two sub-arrays and perform binary search.

2) The main idea for finding pivot is – for a sorted (in increasing order) and pivoted array, pivot element is the only element for which next element to it is smaller than it.
 

3) Using the above statement and binary search pivot can be found.
 

4) After the pivot is found out divide the array in two sub-arrays.
 

5) Now the individual sub – arrays are sorted so the element can be searched using Binary Search.

TC : O(Log(N))
SC : O(1)

This can be solved both : recursively and iteratively.
The recursive approach is more intuitive. First reverse all the nodes after head. Then we need to set head to be the final node in the reversed list. We simply set its next node in the original list (head -> next) to point to it and sets its next to NULL. The recursive approach has a O(N) time complexity and auxiliary space complexity.
For solving the question is constant auxiliary space, iterative approach can be used. We maintain 3 pointers, current, next and previous, abbreviated as cur, n and prev respectively. All the events occur in a chain.

1. Assign prev=NULL, cur=head .
 

2. Next, repeat the below steps until no node is left to reverse:
2.1. Initialize n to be the node after cur. i.e. (n=cur->next)
2.2. Then make cur->next point to prev (next node pointer).
2.3. Then make prev now point to the cur node.
2.4. At last move cur also one node ahead to n.
 

The prev pointer will be the last non null node and hence the answer.

To solve the question using a max heap, make a max heap of all the elements of the list. Run a loop for k-1 times and remove the top element of the heap. After running the loop, the element at top will be the kth largest element, return that. Time Complexity : O(n + klogn)
The question can also be solved using a min heap. 

Approach :
1. Create a min heap class with a capacity of k.

2. When the heap reaches capacity eject the minimum number. 
 

3. Loop over the array and add each number to the heap. 
 

4. At the end, the largest k number of elements will be left in the heap, the smallest of them being at the top of the heap, which is the kth largest number.

The time complexity for this solution is O(N*log(K)).