Message on Whatsapp 8879355057 for DSA(OA + Interview) + Fullstack Dev Training + 1-1 Personalized Mentoring to get 10+LPA Job
0 like 0 dislike
890 views
in Online Assessments by Expert (111,530 points) | 890 views

4 Answers

0 like 0 dislike
Best answer

image
image
image

Image of Questions 

by Expert (111,530 points)
0 like 0 dislike

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)
by Expert (111,530 points)
0 like 0 dislike

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')]  
by Expert (111,530 points)
0 like 0 dislike

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
by Expert (111,530 points)