We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Loading...
  1. Practice
  2. Algorithms
  3. Warmup
  4. Birthday Cake Candles
  5. Discussions

Birthday Cake Candles

  • aida71 + 1 comment

    This is wrong if you do an interview. They most likely want to see a solution which is O(n) and yours is O(n^2).

    This is mine, which is O(n):

    def birthdayCakeCandles(ar):
    max_h = ar[0]
    max_n = 1
    for c in ar[1:]:
        if c > max_h:
            max_h = c
            max_n = 1
        elif c == max_h:
            max_n += 1
    print(max_n)
    • georgechristied1 + 1 comment

      cheers for pointing this out, but is the solution provided by breakbadsp actually O(2^n)?

      • k_mouratidis + 0 comments

        No, it's not. Also, if this were an interview I would get extra points. It is actually 2*n (compared to n), so both are O(n). But you must keep in mind that this is Python, not C++. It IS actually faster to use its functions rather than looping through everything. In fact, it is almost 2x faster. Code for benchmarks:

        from timeit import timeit
from random import randint
from funtools import partial

f = [randint(0,5) for _ in range(10000)]

def breakbadsp(ar): 
    return ar.count(max(ar))
		
def aida71(ar):
    max_h = ar[0]
    max_n = 1
    for c in ar[1:]:
        if c > max_h:
            max_h = c
            max_n = 1
        elif c == max_h:
            max_n += 1
    return max_n
		
		
# 1.72946... seconds
timeit(partial(breakbadsp, f), number=10000)

# 3.10752... seconds
timeit(partial(aida71, f), number=10000)

        Also, this is Python. Even if the second was faster, you should pick the first for 90% of the cases. You need less time to figure what it's doing, and is less error-prone.