Question

Write a function

intersect(L, M)

that consumes two sorted lists of distinct integers L and M, and returns a sorted list that contains only elements common to both lists.

You must obey the following restrictions:

• No recursion or abstract list functions,
• intersect must run in O(n) where n is the combined length of the two parameters.

Example:

 intersect([3, 7, 9, 12, 14], [1, 2, 5, 7, 10, 11, 12]) => [7, 12]

Hint: As the title hints at, you are mostly doing the same thing as the merge function from merge sort. Mostly.

DO NOT USE dictionaries, commands continue or break, zip, anything with set or enumerator, etc.).

Do not mutate passed parameters unless otherwise told to.

Answer 1

note:

The programming language is not specified.

It is mentioned thet use of dictionaries is not allowed. So I recognize the language as python.

If you need the code in other programming language please comment.

Code in python:

//Function that returns an sorted intersected list
def intersect(L, M): 
    i,j = 0,0
    m=len(L)
    n=len(M)
    Intersect=[]
    while i < m and j < n: 
        if L[i] < M[j]: 
            i += 1
        elif M[j] < L[i]: 
            j+= 1
        else: 
            Intersect.append(M[j]) 
            j += 1
            i += 1
    return Intersect
            

Example output of above example in python shell: