python - Where does my code fail? Longest sequence of alternating 0's and 1's - Stack Overflow

In an online exam for a programming job, I was asked to code, in python, a function that would receive an input list containing a sequence of 0's and 1's. The list always has at least one element, and it's guaranteed that the elements are all 0's and '1s. The function needs to find the longest subsequence of alternating 0's and 1's

Example:

In: [0] Out: 1

In: [0, 1, 0, 1, 0] Out: 5

My code worked for all my custom tests, but was right only for 43% of the hidden tests of their grading software. Is there something I am missing here? I can't think of any edge cases if the input is guaranteed to not be messed up. Code:

def sequence(inputLst):
  if len(inputLst) == 1:
    return 1
  
  biggest   = 0
  count     = 1

  print(inputLst)
  for i in range(1, len(inputLst)):
    if inputLst[i] != inputLst[i-1]:
      count += 1
    else:
      biggest = max(biggest, count)
      count = 1
    #print(f"loop {i} max:{biggest} count:{count} current:{inputLst[i]}")
  biggest = max(biggest, count)
  
  return biggest

tests = [
    ([0, 1, 0, 1, 0], 5),
    ([1, 1, 0, 1, 0, 0], 4),
    ([0, 0, 0, 0], 1),
    ([1, 0, 1, 0, 1, 1, 0, 1, 0, 1], 5),
    ([1, 1, 1, 0, 1, 0, 1, 0, 1], 7),
    ([0, 1, 0, 1, 0, 1, 0, 1], 8),
    ([0], 1),
    ([0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1], 5),
    ([1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0], 7)
]

for i, (Sin, truth) in enumerate(tests):
    Sout = sequence(Sin)
    print(f"Test {i + 1}: {'OK' if Sout == truth else 'Fail'} | Expected: {truth}, Output: {Sout}")

In an online exam for a programming job, I was asked to code, in python, a function that would receive an input list containing a sequence of 0's and 1's. The list always has at least one element, and it's guaranteed that the elements are all 0's and '1s. The function needs to find the longest subsequence of alternating 0's and 1's

Example:

In: [0] Out: 1

In: [0, 1, 0, 1, 0] Out: 5

My code worked for all my custom tests, but was right only for 43% of the hidden tests of their grading software. Is there something I am missing here? I can't think of any edge cases if the input is guaranteed to not be messed up. Code:

def sequence(inputLst):
  if len(inputLst) == 1:
    return 1
  
  biggest   = 0
  count     = 1

  print(inputLst)
  for i in range(1, len(inputLst)):
    if inputLst[i] != inputLst[i-1]:
      count += 1
    else:
      biggest = max(biggest, count)
      count = 1
    #print(f"loop {i} max:{biggest} count:{count} current:{inputLst[i]}")
  biggest = max(biggest, count)
  
  return biggest

tests = [
    ([0, 1, 0, 1, 0], 5),
    ([1, 1, 0, 1, 0, 0], 4),
    ([0, 0, 0, 0], 1),
    ([1, 0, 1, 0, 1, 1, 0, 1, 0, 1], 5),
    ([1, 1, 1, 0, 1, 0, 1, 0, 1], 7),
    ([0, 1, 0, 1, 0, 1, 0, 1], 8),
    ([0], 1),
    ([0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1], 5),
    ([1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0], 7)
]

for i, (Sin, truth) in enumerate(tests):
    Sout = sequence(Sin)
    print(f"Test {i + 1}: {'OK' if Sout == truth else 'Fail'} | Expected: {truth}, Output: {Sout}")

• python
• counting

Share Improve this question Follow asked Jan 15 at 3:16 Luigi CarvalhoLuigi Carvalho 1311 silver badge44 bronze badges 3

• 1 Seems correct. Was it asking for longest subsequence or length of longest subsequence? – Adeva1 Commented Jan 15 at 4:40
• Agree with above. Your code seems correct given your understanding and restitution of the problem. So I'd say either you didn't read / understand the exact question properly, or their tests might be wrong. In either case we can't really help without a minimal reproducible example – Julien Commented Jan 15 at 4:58
• It asked for the length of the longest subsequence, the 2 examples I posted were from the question itself – Luigi Carvalho Commented Jan 15 at 16:21

Add a comment  | 

1 Answer 1

Sorted by: Reset to default 1

The question asks for (apparently the length of) the longest subsequence of alternating 0s and 1s, but your code returns the length of the longest subarray of alternating 0s and 1s.

Unlike a subarray, a subsequence does not need to be a contiguous sequence of the given array, but needs only to maintain the order, so in this case the length of the longest subsequence of alternating 0s and 1s is really the number of groups of consecutive 0s and 1s from which each element in the subsequence can be picked:

def sequence(input_list):
    count = 1
    last, *rest = input_list
    for item in rest:
        if item != last:
            count += 1
        last = item
    return count