/* Kleinste gemeenschappelijke voorouder in een boom in O(1) geheugen Beschrijving Gegeven een binaire boom (geen zoekboom): struct Node { Node* parent; Node* left; Node* right; } Je moet een functie schrijven die voor twee gegeven knooppunten hun kleinste (dichtstbijzijnde) gemeenschappelijke voorouder teruggeeft: Node* Lca (Node* a, Node* b); */
Wat is de complexiteit van het algoritme in tijd en geheugen?
/* We moeten gegevens van een bron naar een ontvanger overbrengen. De bron levert de gegevens in kleine pakketten (~tientallen records), terwijl de ontvanger efficiënter werkt met grotere batches. Een echt voorbeeld is het overzetten van gegevens van Kafka-achtige wachtrijen naar de Clickhouse-database. Bron: - Bijna oneindig. - De bron geeft nooit meer dan MaxItems records terug in één Next-aanroep. - Tijdens één "sessie" (één aanroep van de Pipe-functie) geeft de bron bij elke Next nieuwe gegevens. - Na een herstart begint de bron weer vanaf de vorige "bevestigde" positie, aangegeven door cookie. Daarom moet elke waarde van cookie die Next teruggeeft, na het opslaan van de gegevens in de ontvanger, worden bevestigd met een Commit-aanroep, in dezelfde volgorde als waarin ze door Next werden teruggegeven. Ontvanger: - Kan niet meer dan MaxItems tegelijk verwerken. Basisniveau: Het is nodig om de functie func Pipe(p Producer, c Consumer) error te implementeren, die gegevens uit de bron leest, ze groepeert in een buffer van niet meer dan MaxItems en opslaat in de ontvanger, en vervolgens de voortgang in de bron bevestigt. */ const MaxItems = 9999 type Producer interface { // Next geeft terug: // - een batch van items om te verwerken // - een cookie om te bevestigen wanneer de verwerking is voltooid // - een fout Next() (items []any, cookie int, err error) // Commit wordt gebruikt om de gegevensbatch als verwerkt te markeren Commit(cookie int) error } type Consumer interface { Process(items []any) error } func Pipe(p Producer, c Consumer) error { var buf []any var cookies []int for { items, cookie, err := p.Next() if err != nil { return err } buf = append(buf, items...) cookies = append(cookies, cookie) if len(buf) >= MaxItems { if err := c.Process(buf); err != nil { return err } for _, c := range cookies { if err := p.Commit(c); err != nil { return err } } buf = buf[:0] cookies = nil } } if len(buf) > 0 { if err := c.Process(buf); err != nil { return err } for _, c := range cookies { if err := p.Commit(c); err != nil { return err } } } return nil }
Welke prestatie-indicatoren hebt u gebruikt om uw werk in het laatste project te beoordelen?
func countSubs(s string) int { result := 0 left := 0 hm := make(map[rune]int) n := len(s) for right := 0; right < n; right++ { hm[s[right]]++ for hm[s[right]] > 1 { hm[s[left]]-- if hm[s[left]] == 0 { delete(hm, s[left]) } left++ } result += (right - left + 1) } return result }
Wat is het verschil tussen een L4- en een L7-loadbalancer?
""" De plaatsen in de bioscoop zijn in één rij gerangschikt. Een net aangekomen kijker kiest een plek, om zo ver mogelijk van de andere kijkers in de rij te zitten. Dat wil zeggen, de afstand van die plek, waar de kijker zal zitten, tot de dichtstbijzijnde kijker, moet maximaal zijn. Er wordt gegarandeerd dat er altijd vrije plaatsen in de rij zijn en dat er al minstens één kijker zit. Schrijf een functie die, gegeven een rij van plaatsen (een array van nullen en enen), de afstand (het aantal tussenruimtes tussen de stoelen) teruggeeft van de gekozen plek tot de dichtstbijzijnde kijker. [1, 0, 0, 0, 1] -> 2 [1, 0, 1, 0, 0, 1, 0, 0, 1] -> 2 [1, 0, 1, 0] -> 1 [0, 0, 0, 1] [1, 0, 0, 0] place = ((right - left) / 2) """ func maxPlaces(arr []int) int { }
""" De plekken in de bioscoop zijn in één rij gerangschikt. Een net gearriveerde bezoeker kiest een plek, om zo ver mogelijk van de andere bezoekers in de rij te zitten. Dat wil zeggen, de afstand van die plek tot de dichtstbijzijnde bezoeker moet maximaal zijn. Er wordt gegarandeerd dat er altijd vrije plekken zijn en dat er al minstens één bezoeker zit. Schrijf een functie die, gegeven een rij van plekken (een array van nullen en enen), de afstand (het aantal tussenruimtes tussen de stoelen) vanaf de gekozen plek tot de dichtstbijzijnde bezoeker retourneert. [1, 0, 0, 0, 1] -> 2 [1, 0, 1, 0, 0, 1, 0, 0, 1] -> 2 [1, 0, 1, 0] -> 1 """
/* * Gegeven een array van gehele getallen en een getal X, * moet het langste niet-lege subarray worden gevonden waarvan de minimum X is. * Geef de lengte van dat subarray of -1 als er geen is. */
Welk project kiezen voor een technisch interview en hoe het te beschrijven?
Hoe wordt de uitvoeringstijd van de bewerking om een element met een sleutel toe te voegen aan de Map-gegevensstructuur bepaald?
Hoe bepaal je visueel of algoritmisch dat een element uniek is in de Map-gegevensstructuur?
Welke requests per seconde werden bereikt tijdens het schrijven van gegevens?
Waarom zijn er twee if-controles nodig (op regel 79 en op de regel met len(buf)==MaxItems), in plaats van één?
// Voor twee arrays van gehele getallen van lengte N, // voor alle K van 1 tot N, tel het aantal gemeenschappelijke getallen in de prefixen van lengte K. // De getallen in de array kunnen zich herhalen, de intersectie wordt zonder rekening te houden met de multiplicaties geteld. // Een prefix van lengte K van de array A is de eerste K elementen van de array A // A [1, 1] => [1], [1, 1] // B [1, 1] => [1], [1, 1] // R [1, 1] // [1, 2, 5] => [1], [1, 2], [1, 2, 5] // [1, 5, 4] => [1], [1, 5], [1, 5, 4] // [1, 1, 2]
// Er zijn twee gesorteerde reeksen gehele getallen in niet-afnemende volgorde. // Het is nodig om alle elementen uit de eerste reeks te retourneren die niet in de tweede voorkomen. // 0 <= N <= 10^6 // -10^9 <= a[i] <= 10^9 // [1] // [2, 3, 4, 5, 6] // [1] // [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ...] // [1] // [2, 3, 4, 5, 6, 7, 8] func filter(first []int, second []int) []int { res := make([]int, 0, len(first)) i, j := 0, 0 for i < len(first) && j < len(second) { if first[i] < second[j] { result = append(result, first[i]) i++ } else if first[i] > second[j] { j++ } else { i++ j++ } } for i < len(first) { result = append(result, first[i]) i++ } return result }
Vertel ons over de moeilijkste en meest interessante taak die je hebt opgelost, vooral met betrekking tot architecturale ervaring.
Hoe verplaats je het venster in het sliding window-algoritme?
[naam] gaf aan: op regel 20 bevat uniq niet het aantal unieke tekens, maar iets anders. Wat precies?
Woon je momenteel in Moskou? Welke stad overweeg je? Overweeg je een hybride werkmodel? In welke fase van de zoektocht ben je?
