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}")
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