Question

Uber | OA Coding Questions and Solutions | Set - 10 | 2022

Answer 1

Image of Questions 

Answer 2

Q2 dp

 

    adj=collectiosn.defaultdict(set)
    costs=Counter()
    for u,v,w in edges:
        adj[i]|={j}
        adj[j]|={i}
        costs[v,u]=w
    
    @cache    
    def dfs(cur,prev):
        return sum(dfs(nxt,cur)+costs[cur,nxt] for nxt in adj(cur)-{prev})
        
    return min(dfs(node,-1) for node in adj)

Answer 3

Q3 sliding window

 

    s=list(map(int,s))
    ct=[0,0]
    tot=l=0
    res=float('inf')
    
    for r in range(len(s)):
        ct[s[r]]+=1
        tot+=ct[0]*(1-s[r])
           
        while tot>=k:
            res=min(res,r-l+1)        
            tot-=ct[1]*(1-s[l])     
            ct[s[l]]-=1            
            l+=1               
    return [res,-1][res==foat('inf')]  

Answer 4

Q1:

 

1.  

   we sort pairs by B from high to low.

    

2.  

   given B[i] is the smallest b, we can only choose pairs before B[i] from the sorted arr because only those pairs have B[j]>=B[i]

    

3.  

   if k is odd, we pick the largest k//2 nums and the smallest k//2 nums, depending on the sign of B[i], either largest -smallest or smallest-largest
   if k is even, we either pick k//2-1 largest and k//2 smallest, or k//2 largest and k//2-1 smallest

    

    A=[1,4,-3,4,-6,-4,6,7,8]
    B=[1,2,-4,5,-6,-7,2,1,2]
    
    k=3
    
    low,high=[],[]               # store the largest k//2 A[i] and the smallest k//2 A[i]
    th=tl=0                      # sum of the largest k//2 A[i] and  sum of the smallest k//2 A[i]
    res=float('-inf')
    for b,a in sorted(zip(B,A),reverse=True):          # sort pairs by B from high to low 
        if k%2: 
            res=max([res, (th-tl+a)*b,(tl-th+a)*b])    #  if b is negative, smallest minus the largest;  else, largest-smallest
           
        elif high and low:
            i,j=th-high[0]+a-tl,tl+low[0]+a-th
            res=max([res,i*b,-i*b,j*b,-j*b ])
            
        heapq.heappush(high,a)
        heapq.heappush(low,-a)
        th+=a
        tl-=-a    
        if len(high)>k//2:        
            th-=heapq.heappop(high)
        if len(low)>k//2:
            tl+=heapq.heappop(low) 
     return res