Does hacker rank evaluate code for speed?

  Kiến thức lập trình

I am practicing on hacker rank on the following question:

Jesse loves cookies and wants the sweetness of some cookies to be
greater than value . To do this, two cookies with the least sweetness
are repeatedly mixed. This creates a special combined cookie with:

sweetness Least sweet cookie 2nd least sweet cookie).

This occurs until all the cookies have a sweetness .

Given the sweetness of a number of cookies, determine the minimum
number of operations required. If it is not possible, return .

Example

The smallest values are . Remove them then return to the array. Now .
Remove and return to the array. Now . Remove , return and .
Finally, remove and return to . Now . All values are so the process
stops after iterations. Return .

Function Description Complete the cookies function in the editor
below.

cookies has the following parameters:

int k: the threshold value int A[n]: an array of sweetness values
Returns

int: the number of iterations required or -1

I wrote this very simple solution in Python:

def cookies(k, A):
    i = 0
    while True:
        A.sort()
        print(A)
        if A[0] >= k:
            break
        elif len(A)< 2:
            i = -1
            break
        n1 = A.pop(0)
        n2 = A.pop(0)
        new_cookie = (n1 + 2*n2)
        A.insert(0, new_cookie)
        i += 1
    return i

It fails several test cases. Despite banging my head against the wall and consulting ChatGPT, I don’t see any errors on edge cases. Are there other things (like speed) being evaluated by hacker rank? Is this ‘technically correct’ but not performant/ optimal? Are their crazy edge cases they include like where my sort is causing an overflow?

4

You can use heapq to solve this problem. Your current approach is inefficient and it fails as commented.

import heapq

def cookies(k, A):
    heapq.heapify(A)
    i = 0

    while len(A) > 1 and A[0] < k:
        n1 = heapq.heappop(A)
        n2 = heapq.heappop(A)
        new_cookie = n1 + 2 * n2
        heapq.heappush(A, new_cookie)
        i += 1

    if A[0] < k:
        return -1
    return i

print(cookies(7, [1, 2, 3, 9, 10, 12]))

Prints

2


Note

  • pop(0) from a list has an O(N) time complexity.
  • insert(0, value) into a list is also O(N) time complexity.

LEAVE A COMMENT