Jeg hadde problemet nedenfor i en kodetest, og jeg fikk 28/30 tester og 2 mislyktes på grunn til en time-out.

Problem
Du har opprettet et programmeringsspråk, og nå har du bestemt deg for å legge til hashmap støtte til det. Det ble funnet at det i vanlige programmeringsspråk er umulig å legge til et tall til alle hashmap nøkler / verdier. Så du har bestemt deg for å implementere din egen hashmap på det nye språket ditt med følgende operasjoner.

  • insert x y – sett inn og objekt med nøkkel x og verdi y
  • get x – returner verdien til et objekt med nøkkel x
  • addToKey x – legg til x til alle nøkler i kart
  • addToValue y – legg til y til alle verdiene i kartet

Din oppgave er å implementere denne hashmap, bruke de gitte spørsmålene og finne sum av alle resultatene for get operasjoner

For eksempel

  • For queryType=["insert","insert","addToValue","addToKey","get"] og query=[[1,2],[2,3],[2],[1],[3]], skal utgangen være .

Forklaring

  1. insert 1 2 – hashmap vil være {1:2}
  2. insert 2 3 – hashmap vil være {1:2,2:3}
  3. addToValue 2 – hashmap vil være {1:4,2:5}
  4. addToKey 1 – hashmap vil være {2:4,3:5}
  5. get 3 – verdien er 5

Input / Utgang

  • [tidsgrense for utførelse] 3 sekunder (Java)
  • [input] array.string queryType
    Array of søketyper. det er garantert at hver queryType[i] en av de ovennevnte operasjonene
    1 < = queryType.length < = 10 ^ 5
  • [input] array.array.integer query
    Array of queries, der hvert søk er nevnt av 2 tall for innsetting og ett nummer for andre Nøkkelverdier er i området [-10 ^ 9,10 ^ 9]

Nedenfor er løsningen min i Java 

long hashMap(String[] queryType, int[][] query) { long sum = 0; Integer currKey = 0; Integer currValue = 0; Map<Integer, Integer> values = new HashMap<>(); for (int i = 0; i < queryType.length; i++) { String currQuery = queryType[i]; switch (currQuery) { case "insert": HashMap<Integer, Integer> copiedValues = new HashMap<>(); if (currKey != 0 || currValue != 0) { Set<Integer> keys = values.keySet(); for (Integer key : keys) { copiedValues.put(key + currKey, values.get(key) + currValue); } values.clear(); values.putAll(copiedValues); currValue = 0; currKey = 0; } values.put(query[i][0], query[i][1]); break; case "addToValue": currValue += values.isEmpty() ? 0 : query[i][0]; break; case "addToKey": currKey += values.isEmpty() ? 0 : query[i][0]; break; case "get": copiedValues = new HashMap<>(); if (currKey != 0 || currValue != 0) { Set<Integer> keys = values.keySet(); for (Integer key : keys) { copiedValues.put(key + currKey, values.get(key) + currValue); } values.clear(); values.putAll(copiedValues); currValue = 0; currKey = 0; } sum += values.get(query[i][0]); } } return sum; }

Er det noen annen datastruktur jeg kan bruke i stedet for hashmap eller kan jeg forbedre koden min for å være mer lineær?

Kommentarer

  • Velkommen til Code Review. Jeg forstår ikke ‘ hvorfor du oppretter en ny Map hver gang du lager insert eller get spørsmål, hvis du kan forklare meg hvorfor jeg setter pris på det.
  • @dariosicily, det er fordi jeg ikke ‘ t vil overskrive den eksisterende verdien mens du oppdaterer en nøkkel eller et kart. Eksempel: For {2: 3,3: 1}, hvis du vil legge til nøkkel 1 og verdi 1. I den første iterasjonen blir den {3: 4}. Her vil jeg miste den faktiske 3: 1 som er neste nøkkelverdipar. Kort sagt, for å unngå overskriving / kollisjon av nøkkelverdipar.
  • Takk, nå fikk jeg det.

Svar

Jeg vil foreslå at du oppretter din egen OffsetIntegerMap som kan kartlegge mellom heltall og håndtere en forskyvning på tastene og verdiene.

Du trenger ikke nødvendigvis å implementere HashMap fra grunnen av, definere ditt eget begrensede grensesnitt og implementere det med en eksisterende Map<Integer, Integer> gjennom komposisjon.

Ved å håndtere forskyvningene atskilt fra tastene og verdiene, vil kompleksiteten til forskyvningsoperasjonene ende opp O (1) i stedet for O (n) når du foretar omberegninger, og > sett og få operasjoner, hold deg på sin opprinnelige O (1).

Et eksempel på » OffsetIntegerMap «: 

import java.util.HashMap; import java.util.Map; public class OffsetIntegerMap { private final Map<Integer, Integer> actualMap; private int keyOffset = 0; private int valueOffset = 0; public OffsetIntegerMap() { actualMap = new HashMap<>(); } public int size() { return actualMap.size(); } public boolean isEmpty() { return actualMap.isEmpty(); } public boolean containsKey(int key) { var keyWithoutOffset = key - keyOffset; return actualMap.containsKey(keyWithoutOffset); } public boolean containsValue(int value) { var valueWithoutOffset = value - valueOffset; return actualMap.containsValue(valueWithoutOffset); } public Integer get(int key) { var keyWithoutOffset = key - keyOffset; var value = actualMap.get(keyWithoutOffset); if (value == null) return null; return value + valueOffset; } public Integer put(int key, int value) { var keyWithoutOffset = key - keyOffset; var valueWithoutOffset = value - valueOffset; var oldValue = actualMap.put(keyWithoutOffset, valueWithoutOffset); if (oldValue == null) return null; return oldValue + valueOffset; } public Integer remove(int key) { var keyWithoutOffset = key - keyOffset; var oldValue = actualMap.remove(keyWithoutOffset); if (oldValue == null) return null; return oldValue + valueOffset; } public void clear() { actualMap.clear(); keyOffset = 0; valueOffset = 0; } public int getKeyOffset() { return keyOffset; } public void setKeyOffset(int keyOffset) { this.keyOffset = keyOffset; } public int getValueOffset() { return valueOffset; } public void setValueOffset(int valueOffset) { this.valueOffset = valueOffset; } public void addToValues(int toAdd) { this.valueOffset += toAdd; } public void addToKeys(int toAdd) { this.keyOffset += toAdd; } }

Ved å kapsle inn forskyvningslogikken blir prosesseringsløyfen også mye enklere uten å omformulere mye av noe ing: 

static long hashMap(String[] queryType, int[][] query) { long sum = 0; var map = new OffsetIntegerMap(); for (int i = 0; i < queryType.length; i++) { String currQuery = queryType[i]; switch (currQuery) { case "insert": map.put(query[i][0], query[i][1]); break; case "addToValue": map.addToValues(query[i][0]); break; case "addToKey": map.addToKeys(query[i][0]); break; case "get": sum += map.get(query[i][0]); } } return sum; }

Kommentarer

  • Takk. Ser ut som en bedre implementering. Jeg vil sjekke denne logikken.
  • Jeg finner dette svaret øverst. Bruke en klasse skilt fra å teste alle saker.keyWithoutOffset og valueWithoutOffset (jeg tror jeg så en feil i den opprinnelige koden w.r..t. til det). De klare navnene (forskjøvet). Bare metodenavnene er kart-sentriske i stedet for de i kravene
  • Du kan bruke eksemplet fra spørsmålet. Bare bytt ut [] med {}. queryType er String[] og query er int[][].
  • Ah, oversett det. Og jeg ‘ er også bortskjemt med koding av utfordringssider som bare gir meg en » Kjør » knapp :-). Modifiserte denne løsningen i mitt eget svar nå.
  • Offset vil ikke være den samme for hver tast i hashmap! – start med nøkkelset (1,2,3) – legg til 10 til alle nøklene, nå er nøkkelsettet (10,11,12) – sett inn ny nøkkel (5), nå er nøkkelsettet (10,11,12,5) – legg til 10 til alle nøkler, nå er nøkkelsettet (20,21,22,15). Så de første 3 tastene hadde offset 20 lagt til dem, men den siste nøkkelen hadde bare forskjøvet 10 (dvs. at nøkkeltillegg gjort før denne nøkkelen (5) ble satt inn vil bli ignorert).

Svar

Jeg har noen forslag til deg.

Trekk ut noe av logikken til metoder.

I din kode, når spørringen er insert og get, har du to store kodeblokker som er like; du kan trekke ut til en metode og bruke metoden i begge seksjoner.

Jeg foreslår en metode som returnerer en boolsk basert på if -tilstanden, så du blir i stand til å sette variablene currValue og currKey. 

  long hashMap(String[] queryType, int[][] query) { //[...] switch (currQuery) { //[...] case "insert": if (didWeCopiedValuesToMap(currKey, currValue, values)) { currValue = 0; currKey = 0; } values.put(query[i][0], query[i][1]); break; //[...] } //[...] } private boolean didWeCopiedValuesToMap(Integer currKey, Integer currValue, Map<Integer, Integer> values, HashMap<Integer, Integer> copiedValues) { if (currKey != 0 || currValue != 0) { Set<Integer> keys = values.keySet(); for (Integer key : keys) { copiedValues.put(key + currKey, values.get(key) + currValue); } values.clear(); values.putAll(copiedValues); return true; } return false; }

Hvis du vil sjekke gjeldende spørring currQuery, kan du trekke ut hver av dem i en metode. 

 private boolean isGet(String currQuery) { return "get".equals(currQuery); } private boolean isAddToKey(String currQuery) { return "addToKey".equals(currQuery); } private boolean isAddToValue(String currQuery) { return "addToValue".equals(currQuery); } private boolean isInsert(String currQuery) { return "insert".equals(currQuery); }

Bruk alltid primitivene når det er mulig

Når du vet at det er umulig å få en nullverdi med tallet, prøv å bruke primitivene. De tar mindre minne og er raskere enn wrapper-klassen.

Før 

 Integer currKey = 0; Integer currValue = 0;

Etter 

 int currKey = 0; int currValue = 0;

Prøv å sette mindre kode i switch blokker

Etter min mening blir koden mindre lesbar når det er mer enn 3 linjer med koder i en bryterblokk; Jeg foreslår at du konverterer den til en is-else-if. Denne konverteringen vil gjøre koden kortere og mer lesbar.

Før

switch (currQuery) { case "insert": if (didWeCopiedValuesToMap(currKey, currValue, values)) { currValue = 0; currKey = 0; } values.put(query[i][0], query[i][1]); break; case "addToValue": currValue += values.isEmpty() ? 0 : query[i][0]; break; case "addToKey": currKey += values.isEmpty() ? 0 : query[i][0]; break; case "get": if (didWeCopiedValuesToMap(currKey, currValue, values)) { currValue = 0; currKey = 0; } sum += values.get(query[i][0]); }

Etter 

 if ("insert".equals(currQuery)) { if (didWeCopiedValuesToMap(currKey, currValue, values)) { currValue = 0; currKey = 0; } values.put(query[i][0], query[i][1]); } else if ("addToValue".equals(currQuery)) { currValue += values.isEmpty() ? 0 : query[i][0]; } else if ("addToKey".equals(currQuery)) { currKey += values.isEmpty() ? 0 : query[i][0]; } else if ("get".equals(currQuery)) { if (didWeCopiedValuesToMap(currKey, currValue, values)) { currValue = 0; currKey = 0; } sum += values.get(query[i][0]); }

Refactored code 

  long hashMap(String[] queryType, int[][] query) { long sum = 0; int currKey = 0; int currValue = 0; Map<Integer, Integer> values = new HashMap<>(); for (int i = 0; i < queryType.length; i++) { String currQuery = queryType[i]; if (isInsert(currQuery)) { if (didWeCopiedValuesToMap(currKey, currValue, values)) { currValue = 0; currKey = 0; } values.put(query[i][0], query[i][1]); } else if (isAddToValue(currQuery)) { currValue += values.isEmpty() ? 0 : query[i][0]; } else if (isAddToKey(currQuery)) { currKey += values.isEmpty() ? 0 : query[i][0]; } else if (isGet(currQuery)) { if (didWeCopiedValuesToMap(currKey, currValue, values)) { currValue = 0; currKey = 0; } sum += values.get(query[i][0]); } } return sum; } private boolean isGet(String currQuery) { return "get".equals(currQuery); } private boolean isAddToKey(String currQuery) { return "addToKey".equals(currQuery); } private boolean isAddToValue(String currQuery) { return "addToValue".equals(currQuery); } private boolean isInsert(String currQuery) { return "insert".equals(currQuery); } private boolean didWeCopiedValuesToMap(int currKey, int currValue, Map<Integer, Integer> values) { HashMap<Integer, Integer> copiedValues = new HashMap<>(); if (currKey != 0 || currValue != 0) { Set<Integer> keys = values.keySet(); for (Integer key : keys) { copiedValues.put(key + currKey, values.get(key) + currValue); } values.clear(); values.putAll(copiedValues); return true; } return false; }

Svar

Det mest kostbar operasjon er addToKey x som legger til x til alle nøkler i kartet, fordi du i det vesentlige må opprette en ny inngangsnøkkel, verdi + x i hashmap og slett den gamle inngangsnøkkelen, verdien. For å unngå behovet for å cache den gamle oppføringen mens den gjentas over kartet, kan du skille mellom to tilfeller:

x > 0, så hvis du har iterering over en keyset ordnet synkende, det er ikke behov for å cache de gamle oppføringene

x < 0, samme tilnærming men keyset bestilles stigende

Fordi du bruker hashmap, er det ingen nøkkelordre garantert, så du trenger data struktur for å lagre nøkler som skal bestilles, før den gjentas over nøkler som nedenfor: 

private static void addtoKey(Map<Integer, Integer> map, int i) { if (i != 0) { List<Integer> list = new ArrayList<>(map.keySet()); if (i > 0) { Collections.sort(list, Collections.reverseOrder()); } else { Collections.sort(list); } for(int key : list) { map.put(key + i, map.get(key)); map.remove(key); } } }

Jeg ekskluderte saken 0 fordi map forblir uberørt. Andre operasjoner trenger ikke rekkefølge på nøklene, og som allerede antydet, kan det være bedre å prøve å isolere hver operasjon i en privat metode.

Kommentarer

  • Takk @dariosicily for svaret. Er ikke ‘ t sortering hver gang mens du gjør addToKey operasjonen er også kostbar ?. Eller kan jeg bruke a SortedMap for å holde innsettingsrekkefølgen synkende. Som, SortedMap<Integer, Integer>values = new TreeMap<Integer, Integer>(Collections.reverseOrder());
  • @Praveen Du er velkommen. Ja det er sortering hver gang, men med ArrayList etter sortering fortsetter du på en lineær måte.Jeg ble dømt for at du bare kunne bruke HashMap; hvis du kan bruke TreeMap i stedet for HashMap kan du bruke en iterator og en omvendt iterator og iterere over TreeMap på en rett måte.

Svar

Endret versjon av Johnbot s svar uten en ekstra klasse. Jeg tror den ekstra klassen er overkill og heller distraherer fra algoritmen, da jeg må søke gjennom mye kode (mye av det kjele) for å se hva som skjer. Det er ikke den ekstra klassen som gjør prosesseringsløyfen mye enklere. Det er algoritmen.

Ytterligere endringer:

  • keyOffset er ikke tydelig for meg i hvilken retning den er forskjøvet, så jeg omdøpte det til addedToKey (også for verdi).
  • Bestilte operasjonen navn som i problemspesifikasjonen, både for å holde seg nær spesifikasjonen og fordi den rekkefølgen gir mer mening for meg.
  • Introdusert args for å lagre litt kodegjenta.
  • Brukt long / Long til alt, ikke bare for summen. Tross alt kan det å legge til nøklene / verdiene få dem til å renne over hvis vi bare bruker int / Integer. 
static long hashMap(String[] queryType, int[][] query) { Map<Long, Long> map = new HashMap<>(); long sum = 0, addedToKey = 0, addedToValue = 0; for (int i = 0; i < query.length; i++) { int[] args = query[i]; switch (queryType[i]) { case "insert": map.put(args[0] - addedToKey, args[1] - addedToValue); break; case "get": sum += map.get(args[0] - addedToKey) + addedToValue; break; case "addToKey": addedToKey += args[0]; break; case "addToValue": addedToValue += args[0]; } } return sum; }

Kommentarer

  • Hvorfor legger addedToKey jevnt til verdi ‘ s nøkkel fungerer ikke, men trekker den fra for insert og get handlinger arbeid?

Svar

Hva med bare å lagre en forskjøvet verdi for nøkler og verdier og bygge omslagsmetoder rundt hashmaps få / put-metoder for å gjøre rede for denne forskyvningen.

Legg igjen en kommentar

Din e-postadresse vil ikke bli publisert. Obligatoriske felt er merket med *