그럴듯한 면접 문제

시스템을 구현하다가, 어제 두 시간 동안 나를 고민하게 만들었던 문제 ㅎㅎ 내 생각엔 면접 문제로도 괜찮을 거 같다. 나중에 내가 면접관이 되면 이 문제를 써야지.

Q) 다음 함수를 구현하시오.

Rules addRule(Rules previousRules, int min, int max);

1) 각 룰은 min, max로 이루어지는 size cluster 단위로 정렬되고, 각 cluster는 겹치지 않아야 한다.

e.g.) 1-5, 8-13, 19-25, 28-33 요런 식으로..

2) 새로운 룰(min, max)이 추가되었을 때, 기존의 룰과 비교하여 필요한 경우, merge를 해야 한다.

e.g.) 위 규칙 셋에서 10-20 이 추가될 경우, 다음과 같은 룰 셋이 생성 되어야 함

1-5, 8-25, 28-33

3) merge 조건은 연속되는 숫자이다.

e.g.)  1-5, 6-9 이 두 조건은 1-9 한 룰로 merge 되어야 한다.

 

간단한 문제 같지만, 은근 생각할 거리가 많음 ㅎㅎ 일단 구현을 시키고, 시간 안에 구현할 수 있다면, Rules는 어떤 data structure를 쓸 것인지, time complexity는 얼마인지 물을 예정. 그리고 time complexity를 단축할 수 있다면 보너스~~!!