Tweets per second

This challenge is from Talent Buddy:


Tweets per second


Japan Castle in the Sky airing broke a Twitter
record on August 3, 2013. At one point during the classic anime movie
showing, people submitted 143,199 tweets per second. This particular
spike was about 25 times greater than Twitter’s steady state.


Given an array of integers representing the number of tweets recorded
every second and an integer value K, your task is to write a function
that prints to the standard output (stdout) the highest number of
tweets recorded between each second in the array and the past K
seconds before it


Note that your function will receive the following
arguments: tps, which is an array of integers representing the number
of tweets recorded every second, and k, which is the integer number
mentioned above.


Data constraints: the length of the array above will
not exceed 500,000 numbers


Efficiency constraints: your function is
expected to print the requested result and return in less than 2
seconds


Example Input



tps: 6, 9, 4, 7, 4, 1


k: 3



Output



6 9 9 9 7 7



Please Note: The above program should run in below 2 seconds

My Program

start=1
for i,j in enumerate(tps):
    if start<=k:
        print max(tps[:start])
        start+=1
    else:
        print max(tps[i-(start)+2:i+1])

This function takes more than 2 seconds for the test case.

How can we do same thing less in than 2 seconds? How can this be optimized to make it faster?

The problem with your implementation is you will slice the list each iteration, thus the \$O(n*k)\$ complexity Josay talked about. To (somewhat) fix this, you can change your code so that it will only slice your list at most once every k indices.

In order to do this, we can need to store the current maximum value as well as its 'life' (i.e. the number of iterations the value can be still in a window). A basic algorithm is explained on this site provided in the comments by Jaime.

Here is my first implementation:

def tweets_per_second(tps, k):
    life = k
    maximum = -1
    for index, val in enumerate(tps):
        # Is the current value a new maximum?
        # If so, set it and give it a maximum lifespan.
        if val >= maximum:
            maximum = val
            life = k

        print maximum

        # The current maximum has one less window it can reside in.
        # Once we reach zero, we need to find the maximum from 
        # the (k-1 length) window starting IMMEDIATELY after the 
        # previous maximum and the current value. 
        life -= 1
        if not life:
            window = tps[index-k+2:index+1]
            maximum = max(window)

            # Reassign the lifespan based on how far back in the window
            # the maximum value is.
            life = k - window[::-1].index(maximum) - 1

Notice there are a few improvements that we can make, most namely, getting rid of the slicing which takes \$O(k)\$ time. So instead lets use a deque from the collections module. It has an \$O(1)\$ time when appending. Thus, instead of generating the window each time we need find a new maximum, we simply keep the active window in memory.

This change does force use to move some things around, but they are not too major:

from collections import deque

def tweets_per_second(tps, k):
    life = k
    maximum = -1
    window = deque(maxlen=k)
    for index, val in enumerate(tps):
        # Because we specified `maxlen` when creating our window,
        # it will only keep `k` elements.
        window.append(val)

        if not life:
            maximum = -1

            # windex.....get it?
            for windex, win_val in enumerate(window): 
                if win_val >= maximum:
                    maximum = win_val
                    max_index = windex

            life = max_index + 1

        # Is the current value a new maximum?
        # If so, set it and give it a maximum lifespan.
        if val >= maximum:
            maximum = val
            life = k

        print maximum
        life -= 1

The above algorithm runs in under 2 seconds for all of their test cases, and passes all but one. This fail, I believe, is on their end as the output they generate is inconsistent from test to test.

StackExchange Code Review Q#54625, answer score: 5