Join Us
Loading Similar Posts
Entering edit mode
Solution to Problem 2
Analysis
Lets first analyze the procedure to calculate the score for an array:
- We traverse the array and keep adding the max element in the array to the current element.
- An observation here is that since the array elements are positive, as soon as we add the maximum element of the array to the current element. The current element becomes the new maximum element of the array.
- This process continues and the maximum element of the array keeps changing at each step. Lets do a dry run for better understanding :
Notice that the final value at some index i is actually the sum of two values, More formally if a'[i] represents the final array after the procedure. Then a'[i] = max(a) + pre[i] where pre is the prefix sum array. Using this we can find the score of the array a in constant time if we have the prefix sum and the prefix max values precalculated.
Now, back to our original problem, we want to find the score for every prefix of the given array. We can use the above analysis and precalculate the prefix sum (and prefix max) values to find the score for each prefix in a constant time leading to a total time complexity of O(N) (as there are n prefixes) and a space complexity of O(N) (for calculating the prefix sum(and prefix max) array).
Implementation
- We first calculate the prefix sum and the prefix max array of the given array.
- Now as per our analysis the final value at some index
iwill be calculated asa'[i] = max(a) + pre[i]. The score of a prefix is defined as the sum of the final values in that prefix. Now, the score of prefix of lengthxcan be calculated simply asx*prefix_max[x] + sum of first x elements of the prefix sum array. We can thus calculate the scores for all prefixes in one go as using the precomputed values.
PseudoCode
solve(arr,n):
prefix_sum = prefix_max = [0]*n //precomputing the prefix sum and prefix max values
for i from 1 to n:
prefix_sum[i] = prefix_sum[i-1] + arr[i]
prefix_max[i] = max(prefix_max[i-1],arr[i])
score = [0]*n
sum = 0 //sum stores the sum of elements of the prefix sum array so far
for i from 1 to n:
sum += prefix_sum[i]
score[i] = i*prefix_max[i] + sum //calculating the score through the expression derived
return score
Entering edit mode
Solution to Problem 1
Analysis
The given problem is a fairly simple implementation and simulation problem. We can use a Self Balancing BST (Binary Search Tree) to solve it optimally. Lets create a BST that would contain the pairs (value at index i, index i) for i from 0 to n-1. Now at each step we remove the smallest pair from the BST (as per the problem, we can use a suitable comparator, refer to the PseudoCode for more details) and the pairs corresponding to the adjacent elements and add the value of the minimum element to the answer. In this way, we can simulate the process specified in the problem in a total time complexity of O(NlogN) and space complexity of O(N).
Implementation
- Create a self balancing BST of pairs with a comparator as specified in the problem and populate it for the entire array.
- Keep removing the minimum element from the BST as well as its adjacent elements(if they exist) while there are some elements in the BST. Also keep adding the minimum element value to a running answer variable.
- As soon as the BST is empty, we have the required answer.
PseudoCode
//comparator for the BST
//if the value of two pairs is same we place the one with smaller index first, as specified in the problem
//otherwise we place the one with smaller value first
compare(left, right):
return (left.value == right.value) ? left.index < right.index : left.value < right.value
solve(products):
//creating and adding elements to the BST
tree = new BST(pair(int,int),compare)
for i from 0 to n-1:
tree.insert((products[i],i))
ans = 0
while(!tree.empty()):
//we remove the smallest pair
value,ind = BST.pop()
//we also remove the adjacent elements as specified.
if(ind-1 >= 0) BST.erase((products[ind-1],ind-1))
if(ind+1 < n) BST.erase((products[ind+1],ind+1))
//and add the value to the ans
ans += value
return ans
Remarks
As per the constraints on the length of products specified in the problem, a simple brute force solution would also pass. At each step, we can find the minimum element by iterating through the array which will solve the problem in O(N^2). However the method explained in the post is a more optimal solution for an interview setup.
Entering edit mode
Solution to Problem 3
Analysis
Notice that the value of rank remains constant at each level, so the given problem reduces to a very standard problem about finding the k-th smallest (or largest) element in a running stream of data. To solve the problem, we will maintain a min heap of size rank and maintain the invariant that it contains the rank biggest elements discovered so far.
Now we can use and maintain the invariant of the heap using the following procedure:
- To find the
rank-th strongest player we simply use the top element of the heap. - Now as we get a new player, we compare it with the
rank-th element and replace it with the new player if the new player is strictly larger than it.
PseudoCode
solve(initial_players, new_players, rank)
pq = new minHeap()
for player in initial_players: //adding the initial players to the heap
if(pq.size() < rank):
pq.push(player)
else if(pq.top() < player): //since the heap is a min heap, we replace the minimum element in the heap
pq.pop() //with the current player if the current player is strictly larger than it
pq.push(player)
ans = pq.top()
for player in new_players:
if(pq.top() < player):
pq.pop()
pq.push(player)
ans += pq.top()
return ans
