Longest sequence count and sequence to be returned

Question

We need to print the longest sequence of nos. Input = [2,3,4,5,8,0] Output= 3,[2,3,4,5]

Input=[2,3,4,5,8,0,10,9,8,7,6,5] Output= 5,[10,9,8,9,6,5]

Below is the code that I have written, can someone please help me with optimising the code

I have used 2 flags, flag1 refers to the forward seq, and flag2 for the reverse seq, kepping in mind the below mentioned test case

In = [2,3,4,3,2,1] Out = 3, [4,3,2,1]

I got this question in one of the interview, and I took a lot of time to solve this almost 50% of my interview time, any tips on attempting such questions at a faster pace if faced during an interview.

Here is my solution, please help me optimize it.

            l=[2,3,4,3,2,1]
            
            flag1=0
            flag2=0
            index=0
            seq=0
            seq_dict={}
            n=len(l)
            for i in range(n-1):
                
                if (l[i]+1==l[i+1]):
                    if (flag2==1):
                        index=i
                        seq_dict.update({seq:[index,flag1,flag2]})
                        seq=0
                        flag2=0 
                    elif(flag1==0 and i==n-2):
                        index=i+1
                        flag1=1
                        seq+=1
                        seq_dict.update({seq:[index,flag1,flag2]})   
                    flag1=1 
                    seq+=1
                
                elif (l[i]-1==l[i+1]):
                    if (flag1==1):
                        index=i-1
                        seq_dict.update({seq:[index,flag1,flag2]})
                        seq=0
                        flag1=0
                    elif(flag2==1 and i==n-2):
                        index=i+1
                        flag2=1
                        seq+=1
                        seq_dict.update({seq:[index,flag1,flag2]})  
                    flag2=1
                    seq+=1
            
                else:
                    if(seq!=0 and (flag1==1 or flag2==1)):
                        index=i
                        seq_dict.update({seq:[index,flag1,flag2]})  
                    seq=0
                    flag1=0
                    flag2=0
                    index=0   
            
            final=[]
            
            m=max(seq_dict)
            print(m)
            end=seq_dict[m][0]
            while(m>=0):
                final.append(l[end-m])
                m-=1
            print(final)

Andrej Kesely · Accepted Answer · 2024-05-19 15:49:34Z

I suggest to look at itertools, there's lots of utility function that you can use to solve various tasks, for example the one you posted (using itertools.groupby):

from itertools import groupby


def find_longest_sequence(lst):
    m1 = max(
        (list(g) for _, g in groupby(enumerate(lst), lambda k: k[0] - k[1])), key=len
    )
    m2 = max(
        (list(g) for _, g in groupby(enumerate(reversed(lst)), lambda k: k[0] - k[1])),
        key=len,
    )
    if len(m1) > len(m2):
        return m1[-1][1] - m1[0][1], [v for _, v in m1]
    return m2[-1][1] - m2[0][1], [v for _, v in m2][::-1]


testcases = [
    [2, 3, 4, 5, 8, 0],
    [2, 3, 4, 5, 8, 0, 10, 9, 8, 7, 6, 5],
    [2, 3, 4, 3, 2, 1],
]

for t in testcases:
    print(t)
    print(find_longest_sequence(t))
    print()

Prints:

[2, 3, 4, 5, 8, 0]
(3, [2, 3, 4, 5])

[2, 3, 4, 5, 8, 0, 10, 9, 8, 7, 6, 5]
(5, [10, 9, 8, 7, 6, 5])

[2, 3, 4, 3, 2, 1]
(3, [4, 3, 2, 1])

no comment · Accepted Answer · 2024-05-19 17:50:23Z

Shorter version of Andrej's and another way:

def find_longest_sequence(lst):
    m = max((
        g
        for key in [sum, lambda k: k[0] - k[1]]
        for _, [*g] in groupby(enumerate(lst), key)
    ), key=len)
    m = [v for _, v in m]
    return len(m) - 1, m


def find_longest_sequence(lst):
    best = ()
    for diff in -1, 1:
        prev = None
        for curr in lst:
            if curr - diff == prev:
                length += 1
            else:
                first, length = curr, 0
            best = max(best, (length, first, diff))
            prev = curr
    length, first, diff = best
    return length, list(range(first, first + (length+1) * diff, diff))

Attempt This Online!

Collectives™ on Stack Overflow

Longest sequence count and sequence to be returned

2 Answers 2

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Related