[Computer Science / Python Algorithm Question]

Python Algorithm/Stack If you need more information, pleas let me know. Thanks!

• Problem:
  • Please find whether two lists of integers, list1 and list2, are equal
  • here list2 only has nonnegative integers whereas list1 may also have negative integers
  • particularly
    • the negative number, say -n, in list1 means that this negative number and the n nonnegative numbers prior to it should be (hypothetically) removed from list1 during the comparison
    • for example, if list1 = [2, 3, -1] and list2 = [2], the function should return True because based on the discussion above, in essence list1 = [2] (since 3 and -1 should be hypothetically removed from list1)
    • another example, if list1 = [2, 3, 4, -1, 5, -2] and list2 = [2], the function still should return True, because in essence list1 = [2] (since 5 and 4 should be hypothetically removed due to -2, and 3 should be hypothetically removed due to -1)
    • it is worth noting that, the function should return False if for a negative number, say -n, there are fewer than n nonnegative numbers prior to it in list1
    • for example, if list1 = [-1], the function should return False no matter what list2 is
    • see the test cases for more examples
  • find a solution with the complexity below

• Complexity:
  • O(n) time
  • O(n) space

==========================================================================

#Implementation

def exr_1(list1, list2): """ Find whether two lists of integers, list1 and list2, are equal Parameters ---------- list1 : one list of integers list2 : another list of integers Returns ---------- True, if the two lists are equal False, otherwise """

========================================================================

Output should look like this,

# Test print(exr_1([], [])) print(exr_1([2, 3, -1], [2])) print(exr_1([2, 3, 4, -1, 5, -2], [2])) print(exr_1([-1], [])) print(exr_1([1, 2, 3, 4, -2, 5, 6, -1], [2, 5])) print(exr_1([1, -1, 1], [1])) print(exr_1([2, 3, -100], [2]))

True True True False False True False