Crack Meta Software Engineering Հարցազրույցներ. լավագույն 5 անհամապատասխան հարցեր Python լուծումների հետ

Երբ դուք հրազենում եք Meta-ում ծրագրային ապահովման ինժեներական դերի համար (նախկինում հայտնի էր որպես Facebook), դուք կհանդիպեք տվյալների բազմաթիվ կառուցվածքների, և հետաքրքիրներից մեկը տարանջատված հավաքածուն է, որը նաև հայտնի է որպես union-find: Տվյալների այս հզոր կառուցվածքը կատարյալ է կապի, ցանցի կառուցման և բաժանման խմբերի հետ կապված խնդիրների լուծման համար: Այս հոդվածում մենք կանդրադառնանք 5 լավագույն հարցերին, որոնք կապված են տարանջատված խմբերի հետ, որոնք կարող եք ակնկալել Meta-ի ծրագրային ապահովման ինժեներական հարցազրույցներում, ինչպես նաև Python լուծումներ յուրաքանչյուրի համար:

Հաշվի առեք ByteByteGo-ի հանրաճանաչ Համակարգի դիզայնի հարցազրույցի դասընթացըձեր հաջորդ հարցազրույցի համար:

1. Ընկերների շրջանակներ

Հարց:

Հաշվի առնելով N x N մատրիցը՝ M, որը ներկայացնում է ընկերների ցանկը, որտեղ M[i][j]-ը 1-ն է, եթե i-ը և j-ը ընկերներ են, գտե՛ք ընկերների շրջանակների թիվը:

def find_circle_num(M):
    def find(i, parent):
        if parent[i] == -1:
            return i
        return find(parent[i], parent)
    
    def union(x, y, parent):
        x_set = find(x, parent)
        y_set = find(y, parent)
        if x_set != y_set:
            parent[x_set] = y_set
    
    n = len(M)
    parent = [-1] * n
    
    for i in range(n):
        for j in range(i, n):
            if M[i][j] == 1:
                union(i, j, parent)
                
    return len(set(find(i, parent) for i in range(n)))

Մի՛ մոռացեք ստանալ Designing Data Intensive Applications-ի ձեր օրինակը, որն ամենակարևոր գիրքն է, որը պետք է կարդալ համակարգի դիզայնի հարցազրույցի նախապատրաստման համար:

2. Կղզիների թիվը II

Հարց:

Հաշվի առնելով m x n չափի ցանցը, կատարեք k գործողությունների ցանկ, որոնք ավելացնում են նոր կղզի (x, y) վայրում: Յուրաքանչյուր ավելացումից հետո վերադարձրեք կղզիների թիվը:

def num_islands2(m, n, positions):
    parent = {}
    
    def find(i, parent):
        if parent.setdefault(i, i) == i:
            return i
        parent[i] = find(parent[i], parent)
        return parent[i]
    
    def union(x, y, parent):
        parent[find(x, parent)] = find(y, parent)
        
    islands = 0
    res = []
    
    for x, y in positions:
        cur = x * n + y
        parent[cur] = cur
        islands += 1
        
        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nb = (x + dx) * n + (y + dy)
            if nb in parent and find(nb, parent) != find(cur, parent):
                union(cur, nb, parent)
                islands -= 1
                
        res.append(islands)
        
    return res

Ձեռք բերեք ձեր մրցակցությունը Grokking the Advanced System Design Interview դասընթացըև ձեռք բերեք այդ երազանքի աշխատանքը: Ժամեր մի վատնեք Leetcode-ի վրա։ Սովորեք օրինաչափություններ Կոդավորման հարցազրույցի ձևավորում. կոդավորման հարցերի օրինաչափություններ դասընթացի միջոցով:

3. Ավելորդ միացում

Հարց:

Հաշվի առնելով edges կապերի ցանկը, որոնք ներկայացնում են չուղղորդված գրաֆիկ, գտեք մի եզր, որը կարելի է հեռացնել այնպես, որ գրաֆիկը ցիկլ չպարունակի:

def find_redundant_connection(edges):
    parent = {}
    
    def find(u, parent):
        if parent.setdefault(u, u) == u:
            return u
        parent[u] = find(parent[u], parent)
        return parent[u]
    
    for u, v in edges:
        if find(u, parent) == find(v, parent):
            return [u, v]
        parent[find(u, parent)] = find(v, parent)

4. Հաշիվների միաձուլում

Հարց:

Հաշվի առնելով հաշիվների ցանկը, որտեղ յուրաքանչյուր հաշիվ ունի անուն և էլ. նամակների ցուցակ, միավորեք նույն անձին պատկանող հաշիվները:

from collections import defaultdict

def accounts_merge(accounts):
    parent = {}
    
    def find(u):
        if parent.setdefault(u, u) == u:
            return u
        parent[u] = find(parent[u])
        return parent[u]
    
    email_to_name = {}
    for name, *emails in accounts:
        for email in emails:
            email_to_name[email] = name
            
    for name, *emails in accounts:
        for email in emails[1:]:
            parent[find(emails[0])] = find(email)
            
    merged = defaultdict(list)
    for email in email_to_name.keys():
        merged[find(email)].append(email)
        
    return [[email_to_name[k]] + sorted(v) for k, v in merged.items()]

5. Միացված բաղադրիչների քանակը չուղղորդված գրաֆիկում

Հարց:

Հաշվի առնելով n հանգույցները, որոնք նշված են 0-ից մինչև n-1 և չուղղորդված եզրերի ցանկը, գտե՛ք միացված բաղադրիչների քանակը:

def count_components(n, edges):
    parent = list(range(n))
    
    def find(v):
        if parent[v] == v:
            return v
        parent[v] = find(parent[v])
        return parent[v]
    
    for u, v in edges:
        parent[find(u)] = find(v)
        
    return len(set(find(v) for v in range(n)))

Վարպետացնելով Python-ում տարանջատված հավաքածուների օգտագործումը՝ դուք ձեզ համալրում եք հզոր գործիքով, որը կարող է լինել Meta-ում ձեր երազանքի աշխատանքը բացելու բանալին: Շարունակեք կիրառել այս հարցերը, և դուք լավ կլինեք ձեր հաջորդ հարցազրույցը կատարելու ձեր ճանապարհին:

Ավելի բարձր աշխատավարձ ստացեք Grokking Comp Negotiation in Tech-ի հետ։