Linkedin | SRE | Coding OA and Solutions | Set-7 | 2022

Question

For proper oa or interview experiences list of all top tech companies visit :

https://oa.desiqna.in

https://interview.desiqna.in

 

 

Answer 1

LinkedIn Online Assessment Test

 

If you have a subsequence,
you can find the longest contiguous subarray with its sum<=limit

 

Example:
arr=[2,3,1,1,5], limit=7
(solution=4) because longest subarray=[2, 3, 1, 1]

 

arr=[1,2, 3, 6, 4, 3], limit=10
(solution=3) because longest subarray = [1, 2, 3]

 

I was also able to print the solution subaarray

 

I used a recursive call. For example 1:
[2]->[2,3]->[2,3,1]->[2,3,1,1]->[2,3,1,1,5]
[3]->[3,1]->[3,1,1]->[3,1,1,5]
[1]->[1,1]->[1,1,5]
[1]->[1,5]
[5]

 

arr=[1,2, 3, 6, 4, 3]
limit=10
n=len(arr)
maxi=0
elem=[]


def findk(start, end):
    if end==n+1:
      return 
    
    lis=arr[start:end]
    x=sum(lis)
    
    global maxi,elem,limit
    
    if x<=limit:
        maxi=max(maxi,len(lis))
        if len(lis)==maxi:
            elem=lis
            
    findk(start,end+1)

for i in range(0,len(arr)):
    findk(i,i+1)


print(maxi)
print(elem)

 

Complexity is O(n*((n+1)/2))

Answer 2

Its not a dynamic programming, nor recursion is needed, its a simple sliding window

 

cur_sum = 0
max_len = 0
l=0
for x in range(0 , len(arr)):
    cur_sum+=arr[x]
    
    if cur_sum<=limit:
        max_len = max(max_len , x-l+1)
    else:
        while cur_sum>limit:
            cur_sum-=arr[l]
            l+=1

return(max_len)

Answer 3

You should be able to do this in linear time complexity. The key condition is that the answer needs to be contiguous. So you can use a sliding window.

 

• Use two pointers to denote the start and end of the subarray
• Initialize both to zero
• Go on incrementing end and adding the value at that index until sum becomes larger than limit
• Update max subarray length using (start, end - 1)
• Go on incrementing start subtracting the value at the start index until sum becomes <= limit
• Continue

 

Something like this:

 

def solve(arr, limit):
    i, j, tot = 0, 0, 0
    length, start, end = 0, None, None
    
    while j < len(arr):
        tot += arr[j]
        if tot > limit:
            if j - i + 1 > length:
                length = j - i + 1
                start, end = i, j
            while tot > limit:
                tot -= arr[i]
                i += 1
        j += 1
    
    return arr[i:j] if j - i + 1 > length else arr[start:end]