Pramp - Merging 2 Packages

문제

주어진 배열값 두개를 더해서 lim값이 되는 인덱스 한쌍을 찾아라. [i, j] 라면 i>j 이어야 한다. 모든 가능성의 조합 중에 가장 마지막 조합을 리턴해야함(문제에는 표기가 안됐음)

input:  arr = [4, 6, 10, 15, 16],  lim = 21
output: [3, 1] # since these are the indices of the
               # weights 6 and 15 whose sum equals to 21

총평

• two sum 문제라 익순한 문제고, 해시테이블로 풀수 있다는것도 알아서 쉽게 풀이로 넘어갔다.
• 코딩시 해시테이블 배열 인덱싱 하는걸 실수함. 혼자하면 손쉽게 할수있는건데, 인터뷰 상황에서는 항상 배열인덱싱이 몹시 햇갈린다. -> 주석으로 작성하면서 할것. 머리로만 인덱싱 하지말기.
• 인도인 인터뷰어의 발음을 알아듣기가 너무 힘들다. 무슨 말인지 잘 못알아듣겠는데, 계속 말하면 답변을 안하게 됨. 그냥 잘 못알아듣겠다고 하고 더 천천히 말해달라고 이야기해야함.
• unordered_map 의 값이 존재하는지 아닌지 찾는 문법이 익숙치 않아서 인터뷰어에게 물어봄. (이런 라이브러리 사용법을 물어보는건 크게 감점요소가 되지 않을거라는 생각)

     hash.find(key) != hash.end()
     // key가 존재할때 조건을 만족.

• 또한가지 발견한 점, 혼자서 어떻게 풀수 있을지 궁리고하고 있는데, 인터뷰어가 자꾸 힌트를 주거나 말을 걸면, 그 흐름이 깨져서 제대로 풀기 힘들다. 따라서 해결책이있다면 혼자서 궁리할때 그 과정을 계속 이야기해야함. 인터뷰어가 최소한으로만 개입하고 딱 필요할때만 힌트만 주는게 좋은 인터뷰어인것같기도.

해결

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

vector<int> getIndicesOfItemWeights( const vector<int>& arr, int limit)
{
  unordered_map<int, int> hash;
  vector<int> ret;
  
  // make hashtabl
  for (int i = 0; i < arr.size(); i++)
    hash[arr[i]] = i;
    
  for (int i = 0; i < arr.size(); i++) {
    if (hash.find(limit - arr[i]) == hash.end())
      continue;

    int newidx = hash[limit - arr[i]];
    if (i != newidx && arr[i] + arr[newidx] == limit) {
      ret.clear();
      if (i > newidx) {
        ret.push_back(i);
        ret.push_back(newidx);
      } else {
        ret.push_back(newidx);
        ret.push_back(i);
      }
    }
  }
  return ret;  
}

int main() {
  return 0;
}