amzn-OA-challenge.py

#OA Q1 - flight movie duration scheduling

#First decided to save movie index and duration together in a dict for easy fetching of resutls
#Then we sorted the movie by lengths 
# then using a two ponter approach(l = 0 r - len(nums)-1 while l < r), we check the cmbination of the left and right movies
# if they satisfy the criteria m1 + m2 <= fl - 30, 
    # if the sum is m1+m2 == k we return the saved indexes of m1 and m2.
    # if it's < k we check the sum to see if it is closer than the best before this
    # we save best as global-mins and the pair as pairs[]
# if the sum was < k, we increment left
# if it was > K we decrement r
# at the end of the loop if we stored a movie pair, return else [-1,-1]

def flightDetails(arr, k):
    # store the movies in a new list m
    # each entry in m is a tuple of (movie_duration, original_index) 
    m = []
    for i in range(len(arr)):
        m.append((arr[i], i))

    # sort by durations
    m.sort(key=lambda x: x[0])

    k -= 30
    left = 0
    right = len(arr) - 1
    pairs = None
    global_minutes = 0

    while left < right:
        local_minutes = m[left][0] + m[right][0]
        if local_minutes <= k:
            if local_minutes == k :
                return [m[left][1], m[right][1]]
            elif local_minutes > global_minutes:
                global_minutes = local_minutes
                pairs = [m[left][1], m[right][1]]
            left += 1
        else:
            right -= 1
    return pairs

#OA 1 O(n) time
def FindPairs(arr, k):
    k=k-30
    flag=0
    finall1=[]
    fsl1=[]
    for i in range(0, len(arr)):
        l1=[]
        sl1=[]
        if k - arr[i] in arr:
            l1.append(i)
            try:
               arr.index(k-arr[i],1)
               index2=arr.index(k-arr[i],1)
               print(index2)
               l1.append(arr.index(k-arr[i],1))
               sl1.append(arr[i])
               sl1.append(arr[index2])
            except:
              index2=arr.index(k-arr[i])
              l1.append(arr.index(k-arr[i]))
              sl1.append(arr[i])
              sl1.append(arr[index2])
            if i==0:
              finall1=l1
              fsl1=sl1
              if len(finall1)>0:
                flag=1
            if len(finall1)==0:
                  finall1=l1
                  fsl1=sl1
                  if len(finall1)>0:
                    flag=1
            elif len(finall1)>0 and i!=0:
                max1=max(fsl1)
                max2=max(sl1)
                #print(max2,max1)
                if max2>=max1:
                  maxl2=max(finall1)
                  maxl1=max(l1)
                  if maxl1<maxl2:
                    finall1=l1
                    fsl1=sl1
                    flag=1
    if flag==1:
        if finall1[0]>finall1[1]:
          temp=finall1[1]
          finall1[1]=finall1[0]
          finall1[0]=temp
        return  finall1
    else:
      return [-1,-1]


#OA Q2 - DP Audible Book sharing between users, return number of groups of 1s in a 2D matrix
#The solution uses DFS to search the given input matrix as its search space.
#I first convert the input from an array of strings into a 2D matrix of integers, to make it easier to index into to check relationships between users. The convert to Array function has a wordst case of O(n^2)
#I then run the DFS function over every row of the matrix, checking at every step of the loop whether a user(row) has shared a book with another user(column). 
#if the matrix cell has a value of 1, the user has shared the book and we can consider the two as the starting of a group. 
#We then check firther whether there are other users as part of that one group and set all the relationship cells we enounter to 0 so that we do not count them again in another group.
#The adjacency matrix representation of the relationships provides my dfs function with a worst case of O(n^2) where n is the rows in the given matrix.

def countGroups(related):
    # Write your code here
    count = 0
    length = len(related)
    related = convertToArray(related)
    
    for indx in range(length):
        if related[indx][indx] == 1:
            count +=1
            dfs(indx, length, related)
    return count

def dfs(idx, length,matrix):
    if matrix[idx][idx] == 0:
        return 
    for i in range(length):
        if matrix[idx][i]==1:
            matrix[idx][i]=0
            dfs(i,length,matrix)
            
            
def convertToArray(s):
    result = []
    for char in s:
        result.append([int(x) for x in char])
    return result