Grokking Amazon Coding Interview

0% completed

​
Hidden Document
Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content

.....

.....

.....

Like the course? Get enrolled and start learning!
L

Lee

· 2 years ago

Heapq.heapify(some array) is O(n) in python. So the total time complexity is O[n + k * log(n) + n]. I'm not sure what the analysis of largest component here is, so I would just call this O(n + k*log(n)).

For space complexity, because they python heapq library operates on the provided gifts list in place, there is no additional space allocated for a new heap array. Thus the space complexity should be O(1).

Show 2 replies
J

Jimmy

· 2 years ago

Why is the time complexity for the final summation portion O(N)? Shouldn't it be O(N log N) since you are popping all gifts off of the heap to calculate the sum? This seems like an unnecessary step since you don't need a particular ordering of the gifts when calculating the sum - you just need to know how many gifts are remaining.

A more optimized solution would be to get the total number of gifts at the start and deduct the number of gifts taken after each second.

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <numeric>

class Solution {
public:
    int remainingGifts(std::vector<int>& gifts, int k) {
        // ToDo: Write Your Code Here.
        int result = std::accumulate(gifts.begin(), gifts.end(), 0);
        std::priority_queue pq(gifts.be
Show 1 reply
Mykola Zhadanov

Mykola Zhadanov

· 2 years ago

  • Pop an item from the heap, which is O(log(n)).
  • this is incorrect as we always poll Min (or Max), so it's always O(1) operation.
Show 1 reply
csnotebook553

csnotebook553

· 4 months ago

Please update the python version here. Python 3.14+ supports max heap library now, can't use it here