Minulla oli alla oleva ongelma koodaustestissä ja sain 28/30 testiä ja 2 epäonnistui johtuen aikakatkaisuun.

Ongelma
Olet luonut ohjelmointikielen ja nyt olet päättänyt lisätä siihen hashmap -tuen. Todettiin, että yleisissä ohjelmointikielissä on mahdotonta lisätä numeroa kaikkiin hashmap -avaimiin / arvoihin. Joten olet päättänyt toteuttaa oman hashmap uudella kielelläsi seuraavilla toiminnoilla.

  • insert x y – lisää ja esine avaimella x ja arvolla y
  • get x – palauta objektin arvo avaimella x
  • addToKey x – lisää x kaikkiin kartan avaimiin
  • addToValue y – lisää y kaikkiin kartan arvoihin

Sinun tehtäväsi on toteuttaa tämä hashmap, soveltaa annettuja kyselyitä ja löytää summa kaikista tuloksista get -operaatioista

Esimerkki

  • Mille queryType=["insert","insert","addToValue","addToKey","get"] ja query=[[1,2],[2,3],[2],[1],[3]], lähdön tulisi olla .

Selitys

  1. insert 1 2 – hashmap on {1:2}
  2. insert 2 3 – hashmap on {1:2,2:3}
  3. addToValue 2 – hashmap on {1:4,2:5}
  4. addToKey 1 – hashmap on {2:4,3:5}
  5. get 3 – arvo on 5

Tulo / Lähtö

  • [suorituksen aikaraja] 3 sekuntia (Java)
  • [input] array.string queryType
    Taulukko kyselytyypit. sen taataan, että kukin queryType[i] jokin yllä mainituista toiminnoista
    1 < = queryType.length < = 10 ^ 5
  • [input] array.array.integer kysely
    Kyselyryhmä, jossa kukin kysely mainitaan 2 numerolla lisättäväksi ja yksi numero muille Avainarvot ovat alueella [-10 ^ 9,10 ^ 9]

Alla on ratkaisuni 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; }

Onko mitään muuta tietorakennetta, jota voin käyttää hashmap -kohdan sijaan vai voinko parantaa koodini lineaarisemmaksi?

Kommentit

  • Tervetuloa Code Review -ohjelmaan. En ymmärrä ’, miksi luot uuden Map joka kerta, kun teet insert tai get -kyselyjä, jos pystyt selittämään, miksi arvostan sitä.
  • @dariosicily, Itse siksi, etten minä Et halua korvata olemassa olevaa arvoa samalla kun päivität avainta tai karttaa. Esimerkki: Kohdalle {2: 3,3: 1}, jos haluat lisätä avaimen 1 ja arvon 1. Ensimmäisessä iteraatiossa siitä tulee {3: 4}. Täällä menetän todellisen 3: 1, joka on seuraava avainarvopari. Lyhyesti sanottuna välttääksesi avainarvoparien korvaamisen / törmäämisen.
  • Kiitos, nyt sain sen.

Vastaa

Ehdotan, että luot oman OffsetIntegerMap, joka voi kartoittaa kokonaislukuja ja käsitellä avainten ja arvojen siirtymää.

Sinä Ei välttämättä tarvitse toteuttaa HashMap -kuvaketta alusta alkaen, määritellä oma rajoitettu käyttöliittymä ja toteuttaa se olemassa olevalla Map<Integer, Integer> -sovelluksella.

Käsittelemällä siirtymiä erillään näppäimistä ja arvoista, siirtotoimintojen monimutkaisuus johtaa O (1): een O (n): n sijasta, kun suoritetaan uudelleenlaskelmia, ja Map<> put and get -toiminnot pysyvät alkuperäisessä O: ssa (1).

Esimerkki ” 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; } }

Kapseloimalla offset-logiikkaa käsittelysilmukka yksinkertaistuu myös huomattavasti yksinkertaisemmaksi korjaamatta paljoa mitään : 

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; }

Kommentit

  • Kiitos. Näyttää paremmalta toteutukselta. Tarkistan tämän logiikan.
  • Minusta tämä vastaus on paras. Käyttämällä luokkaa erillään kaikkien tapausten testaamisesta.keyWithoutOffset ja valueWithoutOffset (mielestäni näin virheen alkuperäisessä koodissa w.r..t. siihen). Selkeät nimet (offset). Vain menetelmien nimet ovat karttakeskeisiä vaatimusten sijasta.
  • Voit käyttää kysymyksen esimerkkiä. Korvaa vain [] sanoilla {}. queryType on String[] ja query on int[][].
  • Ah, unohti sen. Ja olen ’ liian pilaantunut koodaamalla haastesivustoja vain antamalla minulle ” Suorita ” -painike :-). Muunnin tämän ratkaisun omaksi vastaukseksi nyt.
  • Siirtymä ei ole sama kaikille hashmap-näppäimille! – aloita näppäimistöllä (1,2,3) – lisää 10 kaikkiin näppäimiin, nyt näppäimistö on (10,11,12) – lisää uusi avain (5), nyt näppäimistö on (10,11,12,5) – lisää 10 kaikkiin näppäimiin, nyt näppäimistö on (20,21,22,15). Joten ensimmäiset 3 avainta olivat tosiasiallisesti lisänneet niihin 20, mutta viimeinen avain vain 10 (eli ennen tämän avaimen (5) lisäämistä tehdyt avainlisäykset jätetään huomioimatta).

Vastaa

Minulla on sinulle ehdotuksia.

Pura osa logiikasta menetelmiin.

koodi, kun kysely on insert ja get, sinulla on kaksi samanlaista koodilohkoa; voit purkaa menetelmään ja käyttää menetelmää uudelleen molemmissa osissa.

Ehdotan menetelmää, joka palauttaa loogisen arvon, joka perustuu ehtoon if, joten saat pystyy asettamaan currValue – ja currKey -muuttujat nollaksi. 

  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; }

Jos haluat tarkistaa nykyisen kyselyn currQuery, voit purkaa ne kaikki menetelmään. 

 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); }

Käytä aina primitiiviä, kun mahdollista

Kun tiedä, että nolla-arvon saaminen numerolla on mahdotonta, yritä käyttää primitiivejä; ne vievät vähemmän muistia ja ovat nopeammat kuin käärintäluokka.

Ennen 

 Integer currKey = 0; Integer currValue = 0;  

 int currKey = 0; int currValue = 0;

Yritä laittaa vähemmän koodia switch -lohkoihin

Mielestäni koodi muuttuu vähemmän luettavaksi, kun kytkinlohkossa on enemmän kuin 3 koodiriviä; Ehdotan, että muunnat sen muotoon is-else-if. Tämä muunnos tekee koodista lyhyemmän ja luettavamman.

Ennen 

 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]); }  

 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]); }

Refraktoitu koodi 

  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; }

vastaus

Eniten kallis toiminta on addToKey x, joka lisää x kaikkiin kartan avaimiin, koska olennaisesti sinun on luotava uusi syöttöavain, arvo + x hashmap ja poista vanha syöttöavain, arvo. Voit välttää vanhan merkinnän välimuistiin tallentamisen kartalla, voit erottaa kaksi tapausta:

x > 0, sitten jos sinulla on iterointi keyset järjestetty laskevasti, vanhoja merkintöjä ei tarvitse tallentaa välimuistiin.

x < 0, sama lähestymistapa, mutta keyset on järjestetty nousevaksi

Koska käytät hashmap, avainten järjestystä ei ole taattu, joten tarvitset tietoja rakenne tilattavien avainten tallentamiseksi, ennen kuin iteroidaan seuraavien avainten yli: 

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); } } }

Poistin tapauksen 0 koska map pysyy koskemattomana. Muut toiminnot eivät tarvitse avainten järjestystä, ja kuten jo ehdotettiin, voi olla parempi yrittää eristää kaikki toiminnot yksityisellä menetelmällä.

Kommentit

  • Kiitos @dariosicily vastauksesta. Eikö ’ t ole lajittelua joka kerta samalla kun addToKey -toiminto on kallista? Tai voinko käyttää a SortedMap pitämään lisäysjärjestys laskevana. Kuten, SortedMap<Integer, Integer>values = new TreeMap<Integer, Integer>(Collections.reverseOrder());
  • @Praveen Olet tervetullut. Kyllä, se on lajittelu joka kerta, mutta ArrayList -toiminnolla lajittelun jälkeen jatkat lineaarisesti.Minut tuomittiin, että voit käyttää vain HashMap; Jos voit käyttää TreeMap HashMap -tilan sijaan, voit käyttää iteraattoria ja käänteistä iteraattoria ja toistaa TreeMap suoralla tavalla.

Vastaa

Muokattu versio versiosta Johnbotin vastaus ilman ylimääräistä luokkaa. Luulen, että ylimääräinen luokka on ylivoimainen ja häiritsee pikemminkin algoritmia, koska minun on haettava paljon koodia (paljon siitä kattilalevyä) nähdäksesi mitä tapahtuu. Se ei ole se ylimääräinen luokka, joka tekee käsittelysilmukasta paljon yksinkertaisemman. Se on algoritmi.

Muut muutokset:

  • keyOffset ei ole minulle selvä, mihin suuntaan se siirtyy, joten nimein sen uudeksi nimeksi addedToKey (vastaavasti arvoksi).
  • Tilasi operaation nimet, kuten ongelman määrittelyssä, sekä pysyäkseen lähellä määritystä että siksi, että järjestyksellä on mielestäni järkevämpi.
  • Esitettiin args koodin toistojen tallentamiseksi.
  • Käytetty long / Long kaikkeen, ei vain summaan. Loppujen lopuksi avaimiin / arvoihin lisääminen voi tehdä niistä ylivuodon, jos käytämme vain 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; }

Kommentit

  • Miksi addedToKey lisätään tasaisesti arvo ’ s-avain ei toimi, mutta vähennetään se insert – ja get -toiminnoille toimiiko?

vastaus

Entä pelkästään offset-arvon tallentaminen avaimille ja arvoille ja käärintämenetelmien rakentaminen hashmaps get / put -menetelmät tämän siirtymän huomioon ottamiseksi.

Vastaa

Sähköpostiosoitettasi ei julkaista. Pakolliset kentät on merkitty *