Python >> Python opplæring >  >> Python Tag >> Array

[Intervjuspørsmål] Hvordan søke i innsettingsposisjonen til målet i en sortert matrise?

Bedriftsmerker:Adobe, Uber, Airbnb, Bloomberg

Er du ute etter å klare ditt kodeintervju? Hvis ja! Da er dette spørsmålet noe du må gjøre, ettersom det angivelig har blitt stilt i en rekke intervjuer av noen av de gigantiske organisasjonene som Adobe. Kan du løse dette problemet optimalt?

Problemerklæring

Gitt en sortert matrise av distinkte heltall og en målverdi, returner indeksen hvis målet er funnet. Hvis ikke, returner indeksen der den ville vært hvis den ble satt inn i rekkefølge.

Utfordring: Kan du foreslå en algoritme medO(log n) runtime kompleksitet?

⚠️Begrensninger:

  1. 1 <= nums.length <= 104
  2. -104 <= nums[i] <= 104
  3. nums inneholder distinkte verdier sortert i «stigende rekkefølge» .
  4. -104 <= target <= 104

Eksempler

La oss se på noen eksempler for å forbedre forståelsen av problemet:

Eksempel 1:
Inndata:
tall =[1, 3, 5, 6]
mål =5
Utgang:2
Forklaring:Mål 5 er indeksert ved posisjon 2 i matrisen.

Eksempel 2:
Inndata:
tall =[1, 3, 5, 6]
mål =2
Utgang:1
Forklaring:Mål 2 vil bli satt inn i posisjon 1 i matrisen.

Eksempel 3:
Inndata:
tall =[1, 3, 5, 6]
mål =7
Utgang:4
Forklaring:Mål 7 vil bli satt inn i posisjon 4 i matrisen.

Eksempel 4:
Inndata:
tall =[1, 3, 5, 6]
mål =0
Utgang:0
Forklaring:Mål 0 vil bli satt inn i posisjon 0 i matrisen.

Eksempel 5:
Inndata:
tall =[1]
mål =0
Utgang:0
Forklaring:Mål 0 vil bli satt inn i posisjon 0 i matrisen.

Nå som du har en klar forståelse av problemet, la oss dykke ned i ulike metoder for å løse problemet:

Metode 1:Lineært søk

Tilnærming: Den enkleste måten å løse problemet på er å iterere gjennom hvert tall i matrisen. Returner indeksen hvis målet blir funnet. Ellers, sjekk hvor målverdien kan settes inn og returner den indeksverdien.

Algorithme:

  1. Sjekk om matrisen er tom. Hvis ja, returner 0 .
  2. Hvis målverdien er større enn det siste elementet i matrisen, blir målverdien satt inn på slutten av matrisen. Returner derfor lengden på matrisen.
  3. Hvis målverdien er mindre enn det første elementet i matrisen, vil målet settes inn i begynnelsen av matrisen. Returner derfor 0 .
  4. Videre gjennom matrisen. Hvis gjeldende tall er større enn eller lik målverdien, returner gjeldende indeks.

Løsning:

def search_insert(nums, target):
    if not nums:
        return 0
    if target > nums[-1]:
        return len(nums)
    if target < nums[0]:
        return 0
    for i in range(len(nums)):
        if nums[i] >= target:
            return i

Testtilfelleanalyse:

La oss kjøre denne løsningen på våre eksempler:

# Eksempel 1
tall =[1, 3, 5, 6]
mål =5
print(search_insert(nums, target))
#2

# Eksempel 2
tall =[1, 3, 5, 6]
mål =2
print(search_insert(nums, target))
# 1

# Eksempel 3
tall =[1, 3, 5, 6]
mål =7
print(search_insert(nums, target))
#4

# Eksempel 4
tall =[1, 3, 5, 6]
mål =0
print(search_insert(nums, target))
#0

# Eksempel 5
tall =[1]
mål =0
print(search_insert(nums, target))
# 0

Ja! Den besto alle testsakene.

Kompleksitetsanalyse:

  • Tidskompleksitet :I verste fall må du besøke hvert tall i matrisen. Derfor er tidskompleksiteten til denne metoden O(n) .
  • Romkompleksitet: Ingen ekstra plass brukes. Romkompleksiteten til denne metoden er derfor O(1) .

Diskusjon: Selv om denne algoritmen henter oss den nødvendige utgangen, sikrer den imidlertid ikke at kjøretidskompleksiteten er log(n), noe som også er en utfordring som presenteres for oss. I neste tilnærming vil vi finne ut hvordan du bruker binært søk og når den optimale løsningen.

Metode 2:Binært søk

Tilnærming: En bedre tilnærming ville være å bruke binært søk da du vil søke etter et bestemt element i matrisen. Du må initialisere to-pekere og beregne verdien av mid . Sammenlign mellomverdien med målverdien og returner indeksen hvis den blir funnet.

Algorithme:

  1. Sjekk om matrisen er tom. Hvis ja, returner 0 .
  2. Initialiser variablene lav og høy med 0 og len(nums) , henholdsvis.
  3. Mens «low "-indeksen er mindre enn "high ”, beregne mellomverdien.
  4. Sammenlign mellomverdien med målverdien.
  5. Hvis målverdien er større enn middelverdien, vil målverdien være til høyre. Oppdater low til mid + 1 .
  6. Hvis målverdien er mindre enn eller lik midtverdien, oppdaterer du high til mid .
  7. Når du går ut av loopen, posisjonen til low pekeren er enten på posisjonen lik målverdien eller på posisjonen der du må sette inn målverdien. Returner derfor verdien pekt av low .

Vurder følgende illustrasjon for å forstå tilnærmingen bedre:

Løsning:

def search_insert(nums, target):
    if not nums:
        return 0
    low, high = 0, len(nums)
    while low < high:
        mid = (low + high) // 2
        if target > nums[mid]:
            low = mid + 1
        else:
            high = mid
    return low

Testtilfelleanalyse:

La oss kjøre denne løsningen på våre eksempler:

# Eksempel 1
tall =[1, 3, 5, 6]
mål =5
print(search_insert(nums, target))
#2

# Eksempel 2
tall =[1, 3, 5, 6]
mål =2
print(search_insert(nums, target))
# 1

# Eksempel 3
tall =[1, 3, 5, 6]
mål =7
print(search_insert(nums, target))
#4

# Eksempel 4
tall =[1, 3, 5, 6]
mål =0
print(search_insert(nums, target))
#0

# Eksempel 5
tall =[1]
mål =0
print(search_insert(nums, target))
# 0

Ja! Den besto alle testsakene.

Kompleksitetsanalyse:

  • Tidskompleksitet: Siden denne metoden bruker binært søk, må du bare krysse halve matrisen. Derfor er tidskompleksiteten til denne metoden O(log(n)) .
  • Romkompleksitet: Ingen ekstra plass brukes. Romkompleksiteten til denne metoden er derfor O(1) .

Ønsker du å utvikle ferdighetene til en godkjent Python-profesjonell – mens du får betalt i prosessen? Bli en Python-frilanser og bestill boken din Leaving the Rat Race with Python på Amazon (Kindle/Print )!

Bonusmetode:Bruk av Bisect-modulen

Tilnærming: Du kan bruke Bisect-modulen direkte for å finne posisjonen til målelementet. bisect_left metoden til halveringsmodulen brukes til å finne indeksen til målelementet i den sorterte matrisen. Hvis elementet allerede er tilstede i matrisen, returneres posisjonen lengst til venstre der elementet kan settes inn i listen.

Bisect Module Recap:
➥ Formålet med Bisect  algoritmer er å finne indeksen/posisjonen av et nødvendig element i en gitt liste der elementet må settes inn i listen. Derfor hjelper det å holde listen sortert etter at innsettingen er fullført.
bisect_left metoden til bisekt modulen brukes til å finne indeksen til målelementet i den sorterte listen. Hvis elementet allerede er til stede i listen, returneres posisjonen lengst til venstre der elementet kan settes inn i listen.

Løsning:

from bisect import bisect_left


def search_insert(nums, target):
    return bisect_left(nums, target)

Testtilfelleanalyse:

La oss kjøre denne løsningen på våre eksempler:


# Eksempel 1
tall =[1, 3, 5, 6]
mål =5
print(search_insert(nums, target))
#2

# Eksempel 2
tall =[1, 3, 5, 6]
mål =2
print(search_insert(nums, target))
# 1

# Eksempel 3
tall =[1, 3, 5, 6]
mål =7
print(search_insert(nums, target))
#4

# Eksempel 4
tall =[1, 3, 5, 6]
mål =0
print(search_insert(nums, target))
#0

# Eksempel 5
tall =[1]
mål =0
print(search_insert(nums, target))
# 0

Ja! Den besto alle testsakene.

Kompleksitetsanalyse:

  • Tidskompleksitet: Siden denne metoden ligner på binært søk, er tidskompleksiteten til denne metoden O(log(n)).
  • Romkompleksitet: Ingen ekstra plass brukes. Romkompleksiteten til denne metoden er derfor O(1).

Konklusjon

Jeg håper du likte dette kodeintervjuet spørsmål. Vennligst følg med og abonner for mer interessante kodeproblemer.

Legg inn kreditt: Shubham Sayon og Rashi Agarwal


Anbefalt: Finxter Computer Science Academy

  • En av de mest ettertraktede ferdighetene på Fiverr og Upwork er nettskraping . Gjør ingen feil:trekk ut data programmatisk fra nettsteder er en kritisk livsferdighet i dagens verden som er formet av nettet og eksternt arbeid.
  • Så, vil du mestre kunsten å skrape nett ved å bruke Pythons BeautifulSoup?
  • Hvis svaret er ja – dette kurset tar deg fra nybegynner til ekspert på nettskraping.