코딩 테스트에서 아래 문제가 발생했으며 28/30 개의 테스트를 통과했고 2 번은 실패했습니다. 시간 제한.

문제
프로그래밍 언어를 작성했으며 이제 hashmap 지원을 추가하기로 결정했습니다. 일반적인 프로그래밍 언어에서는 모든 hashmap 키 / 값에 숫자를 추가하는 것이 불가능합니다. 따라서 다음 작업을 통해 새 언어로 자신 만의 hashmap를 구현하기로 결정했습니다.

  • insert x y–x 키와 y
  • get x 값으로 삽입 및 개체 div>-키 x
  • addToKey x-지도의 모든 키에
  • addToValue y-지도의 모든 값에 y 추가

당신의 임무는이 hashmap를 구현하고, 주어진 쿼리를 적용하고, 를 찾는 것입니다. get 작업에 대한 모든 결과의 합계

예 :

  • queryType=["insert","insert","addToValue","addToKey","get"] 및 query=[[1,2],[2,3],[2],[1],[3]], 출력은 .

설명

  1. insert 1 2-해시 맵은 {1:2}
  2. insert 2 3-해시 맵은 {1:2,2:3}
  3. addToValue 2-해시 맵은
  4. addToKey 1-해시 맵은 {2:4,3:5}

  5. -값은 5입니다.

입력 / 출력

  • [실행 시간 제한] 3 초 (Java)
  • [input] array.string queryType
    쿼리 유형. 각 queryType[i] 위에서 언급 한 작업 중 하나
    1 < = queryType.length < = 10 ^ 5
  • [input] array.array.integer 쿼리
    각 쿼리는 삽입을위한 2 개의 숫자와 다른 1 개의 숫자로 언급되는 쿼리의 배열입니다. 키 값은 [-10 ^ 9,10 ^ 9] 범위 내에 있습니다.

다음은 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; }

hashmap 대신 사용할 수있는 다른 데이터 구조가 있습니까? 아니면 개선 할 수 있습니까? 내 코드가 더 선형 적일까요?

댓글

  • 코드 검토에 오신 것을 환영합니다. ‘ insert를 만들 때마다 새 Map를 만드는 이유를 이해하지 못합니다. get 질문입니다. 감사하는 이유를 설명해 주시면 감사하겠습니다.
  • @dariosicily, 내가하지 않기 때문입니다. ‘ 키 또는 맵을 업데이트하는 동안 기존 값을 덮어 쓰고 싶습니다. 예 : {2 : 3,3 : 1}의 경우 키 1과 값 1을 추가하려면 첫 번째 반복에서 {3 : 4}가됩니다. 여기서는 다음 키 값 쌍인 실제 3 : 1을 잃게됩니다. 간단히 말해서 키 값 쌍의 덮어 쓰기 / 충돌을 방지하기 위해.
  • 감사합니다. 이제 확인했습니다.

답변

정수간에 매핑하고 키 및 값의 오프셋을 처리 할 수있는 고유 한 OffsetIntegerMap를 만드는 것이 좋습니다.

당신은 HashMap를 처음부터 구현할 필요는 없습니다. 자신 만의 제한된 인터페이스를 정의하고 구성을 통해 기존 Map<Integer, Integer>로 구현합니다.

오프셋을 키 및 값과 별도로 처리함으로써 오프셋 작업의 복잡성은 재 계산을 수행 할 때 O (n) 대신 O (1)이되고 Map<> put 및 get 작업은 원래 O (1)로 유지됩니다.

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

오프셋 로직을 캡슐화함으로써 처리 루프도 많은 부분을 리팩토링하지 않고도 훨씬 간단 해집니다. 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; }

댓글

  • 감사합니다. 더 나은 구현처럼 보입니다. 이 논리를 확인하겠습니다.
  • 이 답이 맨 위에 있습니다. 모든 사례를 테스트하는 것과는 별도로 클래스를 사용합니다.keyWithoutOffset 및 valueWithoutOffset (원래 코드에서 버그가 발견 된 것 같습니다.) 명확한 이름 (오프셋). 메서드 이름은 요구 사항이 아닌지도 중심입니다.
  • 질문의 예를 사용할 수 있습니다. []를 {}로 바꾸면됩니다. queryType는 String[]이고 query는 int[][].
  • 아, 간과했습니다. 그리고 ‘ ” 실행 “을 제공하는 챌린지 사이트를 코딩하는 것에 너무 망쳤습니다. 버튼 :-). 이 솔루션을 지금 내 대답으로 수정했습니다.
  • 해시 맵의 모든 키에 대해 오프셋이 동일하지는 않습니다! -키 세트 (1,2,3)로 시작-모든 키에 10을 추가합니다. 이제 키 세트는 (10,11,12)입니다.-새 키를 삽입합니다 (5), 이제 키 세트는 (10,11,12,5)입니다.-추가 모든 키에 10 개, 이제 키 세트는 (20,21,22,15)입니다. 따라서 처음 3 개의 키에는 사실상 오프셋 20이 추가되었지만 마지막 키에는 오프셋이 10 개뿐입니다 (즉,이 키 (5)가 삽입되기 전에 수행 된 키 추가는 무시됩니다).

답변

제안 사항이 있습니다.

메소드에 대한 논리를 추출합니다.

코드에서 쿼리가 insert 및 get 인 경우 유사한 두 개의 큰 코드 블록이 있습니다. 메서드로 추출하여 두 섹션 모두에서 메서드를 재사용 할 수 있습니다.

if 조건에 따라 부울을 반환하는 메서드를 제안합니다. currValue 및 currKey 변수를 0으로 설정할 수 있습니다. 

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

또한 현재 쿼리 currQuery를 확인하기 위해 메서드에서 각각을 추출 할 수 있습니다. 

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

가능한 경우 항상 기본 형식 사용

숫자로 null 값을 얻는 것이 불가능하다는 것을 알고 프리미티브를 사용하십시오. 이들은 메모리를 덜 차지하고 래퍼 클래스보다 빠릅니다.

이전 

 Integer currKey = 0; Integer currValue = 0;

이후 

 int currKey = 0; int currValue = 0;

switch 블록에 적은 코드를 넣으십시오.

제 생각에는 스위치 블록에 3 줄 이상의 코드가있을 때 코드의 가독성이 떨어집니다. is-else-if로 변환하는 것이 좋습니다. 이 변환으로 코드가 더 짧고 읽기 쉬워집니다.

Before 

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

리팩토링 된 코드 

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

답변

가장 비용이 많이 드는 작업은지도의 모든 키에 x를 추가하는 addToKey x입니다. 실질적으로 hashmap 이전 입력 키 값을 삭제합니다. 맵에서 반복하는 동안 이전 항목을 캐싱 할 필요가 없도록 두 가지 경우를 구분할 수 있습니다.

x > 0, keyset 내림차순으로 정렬되어 이전 항목을 캐싱 할 필요가 없습니다.

x < 0, 동일한 접근 방식이지만 keyset는 오름차순으로 정렬됩니다.

hashmap를 사용하고 있기 때문에 키 순서가 보장되지 않으므로 데이터가 필요합니다. 다음과 같은 키를 반복하기 전에 주문할 키를 저장하는 구조 : 

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

0 map는 그대로 유지되기 때문입니다. 다른 작업에는 키 순서가 필요하지 않으며 이미 제안했듯이 모든 작업을 비공개 방법으로 분리하는 것이 좋습니다.

댓글

  • 답변에 대해 @dariosicily에게 감사드립니다. ‘ addToKey 작업을 수행하는 동안 매번 정렬하는 것도 비용이 많이 듭니까?. 또는 사용할 수 있습니까? SortedMap는 게재 신청서를 내림차순으로 유지합니다. 예 : SortedMap<Integer, Integer>values = new TreeMap<Integer, Integer>(Collections.reverseOrder());
  • @Praveen 환영합니다. 예, 그렇습니다. 매번 정렬하지만 정렬 후 ArrayList를 사용하면 선형 방식으로 진행됩니다.HashMap 만 사용할 수 있다는 유죄 판결을 받았습니다. HashMap 대신 TreeMap를 사용할 수 있다면 반복기와 역방향 반복기를 사용하고 .

답변

Johnbot의 답변 추가 클래스가 없는 . 많은 코드를 검색해야하므로 추가 클래스가 과도하고 알고리즘에서 산만하다고 생각합니다. (대부분의 상용구) 무슨 일이 일어나고 있는지 확인합니다. 처리 루프를 훨씬 간단하게 만드는 것은 추가 클래스가 아닙니다. 바로 알고리즘입니다.

추가 변경 사항 :

  • keyOffset는 오프셋이 어느 방향인지 명확하지 않아서 이름을 addedToKey (값도 마찬가지 임)로 변경했습니다.
  • 작업 순서를 지정했습니다. 이름은 문제 사양에서와 같이 사양에 가깝게 유지하고 그 순서가 나에게 더 의미가 있기 때문입니다.
  • 코드 반복을 줄이기 위해 args를 도입했습니다.
  • 합계뿐만 아니라 모든 것에 long / Long를 사용했습니다. 결국 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; }

댓글

  • 왜 addedToKey를 value ‘의 키가 작동하지 않지만 insert 및 get 작업에서 키를 빼면 작동합니다. 작동합니까?

Answer

키와 값에 대한 오프셋 값을 저장하고 주위에 래퍼 메서드를 구축하는 것은 어떻습니까? hashmaps get / put 메서드는이 오프셋을 설명합니다.

답글 남기기

이메일 주소를 발행하지 않을 것입니다. 필수 항목은 *(으)로 표시합니다