Is there a better way than a while loop to perform this function?

Question

I was attempting some python exercises and I hit the 5s timeout on one of the tests. The function is pre-populated with the parameters and I am tasked with writing code that is fast enough to run within the max timeframe of 5s.

There are N dishes in a row on a kaiten belt, with the ith dish being of type Di​. Some dishes may be of the same type as one another. The N dishes will arrive in front of you, one after another in order, and for each one you'll eat it as long as it isn't the same type as any of the previous K dishes you've eaten. You eat very fast, so you can consume a dish before the next one gets to you. Any dishes you choose not to eat as they pass will be eaten by others. Determine how many dishes you'll end up eating.

Issue

The code "works" but is not fast enough.

Code

The idea here is to add the D[i] entry if it is not in the pastDishes list (which can be of size K).

from typing import List
# Write any import statements here

def getMaximumEatenDishCount(N: int, D: List[int], K: int) -> int:
  # Write your code here
  numDishes=0
  pastDishes=[]
  i=0
  while (i<N):
    if(D[i] not in pastDishes):
      numDishes+=1
      pastDishes.append(D[i])
      if len(pastDishes)>K:
        pastDishes.pop(0)
    i+=1
  return numDishes  

Is there a more effective way?

Answer 1

After much trial and error, I have finally found a solution that is fast enough to pass the final case in the puzzle you are working on. My previous code was very neat and quick, however, I have finally found a module with a tool that makes this much faster. Its from collections just as deque is, however it is called Counter.

This was my original code:

def getMaximumEatenDishCount(N: int, D: list, K: int) -> int:
    numDishes=lastMod=0
    pastDishes=[0]*K
    for Dval in D:
        if Dval in pastDishes:continue
        pastDishes[lastMod] = Dval
        numDishes,lastMod = numDishes+1,(lastMod+1)%K
    return numDishes   

I then implemented Counter like so:

from typing import List

# Write any import statements here
from collections import Counter

def getMaximumEatenDishCount(N: int, D: 'list[int]', K: int) -> int:
    eatCount=lastMod = 0
    pastDishes=[0]*K

    eatenCounts = Counter({0:K})
    for Dval in D:
        if Dval in eatenCounts:continue
        eatCount +=1
        eatenCounts[Dval] +=1

        val = pastDishes[lastMod]
        if eatenCounts[val] <= 1:   eatenCounts.pop(val)
        else:                       eatenCounts[val] -= 1
        
        pastDishes[lastMod]=Dval
        lastMod = (lastMod+1)%K
    return eatCount

Which ended up working quite well. I'm sure you can make it less clunky, but this should work fine on its own.

Some Explanation of what i am doing:

Typically while loops are actually marginally faster than a for loop, however since I need to access the value at an index multiple times if i used it, using a for loop I believe is actually better in this situation. You can see i also initialised the list to the max size it needs to be and am writing over the values instead of popping+appending which saves alot of time. Additionally, as pointed out by @outis, another small improvement was made in my code by using the modulo operator in conjunction with the variable which removes the need for an additional if statement. The Counter is essentially a special dict object that holds a hashable as the key and an int as the value. I use the fact that lastMod is an index to what would normally be accesed through list.pop(0) to access the object needed to either remove or decrement in the counter

Note that it is not considered 'pythonic' to assign multiple variable on one line, however I believe it adds a slight performance boost which is why I have done it. This can be argued though, see this post.

If anyone else is interested the problem that we were trying to solve, it can be found here: https://www.facebookrecruiting.com/portal/coding_puzzles/?puzzle=958513514962507

Answer 2

Can we use an appropriate data structure? If so:

Data structures

Seems like an ordered set which you have to shrink to a capacity restriction of K.

To meet that, if exceeds (len(ordered_set) > K) we have to remove the first n items where n = len(ordered_set) - K. Ideally the removal will perform in O(1).

However since removal on a set is in unordered fashion. We first transform it to a list. A list containing unique elements in the order of appearance in their original sequence.

From that ordered list we can then remove the first n elements.

For example: the function lru returns the least-recently-used items for a sequence seq limited by capacity-limit k.

To obtain the length we can simply call len() on that LRU return value:

maximumEatenDishCount = len(lru(seq, k))

See also:

• Does Python have an ordered set?
• Fastest way to get sorted unique list in python?

Using set for uniqueness (up to Python 3.6)

def lru(seq, k):
    return list(set(seq))[:k]

Using dict for uniqueness (since Python 3.6)

Same mechanics as above, but using the preserved insertion order of dicts since 3.7:

• using OrderedDict explicitly

from collections import OrderedDict

def lru(seq, k):
    return list(OrderedDict.fromkeys(seq).keys())[:k]

• using dict factory-method:

def lru(seq, k):
    return list(dict.fromkeys(seq).keys())[:k]

• using dict-comprehension:

def lru(seq, k):
    return list({i:0 for i in seq}.keys())[:k]

See also:

• The order of keys in dictionaries
• Using ordered dictionary as ordered set
• How do you remove duplicates from a list whilst preserving order?
• Real Python: OrderedDict vs dict in Python: The Right Tool for the Job

Answer 3

As the problem is an exercise, exact solutions are not included. Instead, strategies are described.

There are at least a couple potential approaches:

• Use a data structure that supports fast containment testing (a set in use, if not in name) limited to the K most recently eaten dishes. Fortunately, since dict preserves insertion order in newer Python versions and testing key containment is fast, it will fit the bill. dict requires that keys be hashable, but since the problem uses ints to represent dish types, that requirement is met.

  With this approach, the algorithm in the question remains unchanged.

• Rather than checking whether the next dish type is any of the last K dishes, check whether the last time the next dish was eaten is within K of the current plate count. If it is, skip the dish. If not, eat the dish (update both the record of when the next dish was last eaten and the current dish count). In terms of data structures, the program will need to keep a record of when any given dish type was last eaten (initialized to -K-1 to ensure that the first time a dish type is encountered it will be eaten; defaultdict can be very useful for this).

  With this approach, the algorithm is slightly different. The code ends up being slightly shorter, as there's no shortening of the data structure storing information about the dishes as there is in the original algorithm.

There are two takeaways from the latter approach that might be applied when solving other problems:

1. More broadly, reframing a problem (such as from "the dish is in the last K dishes eaten" to "the dish was last eaten within K dishes of now") can result in a simpler approach.
2. Less broadly, sometimes it's more efficient to work with a flipped data structure, swapping keys/indices and values.

Approach & takeaway 2 both remind me of a substring search algorithm (the name escapes me) that uses a table of positions in the needle (the string to search for) of where each character first appears (for characters not in the string, the table has the length of the string); when a mismatch occurs, the algorithm uses the table to align the substring with the mismatching character, then starts checking at the start of the substring. It's not the most efficient string search algorithm, but it's simple and more efficient than the naive algorithm. It's similar to but simpler and less efficient than the skip search algorithm, which uses the positions of every occurrence of each character in the needle.

Answer 4

from typing import List
# Write any import statements here
from collections import deque, Counter

def getMaximumEatenDishCount(N: int, D: List[int], K: int) -> int:
  # Write your code here
  q = deque()
  cnt = 0
  dish_counter = Counter()
  for d in D:
    if dish_counter[d] == 0:
      cnt += 1
      q.append(d)
      dish_counter[d] += 1
      if len(q) == K + 1:
        remove = q.popleft()
        dish_counter[remove] -= 1

  return cnt