인터뷰 : 시스템/API 디자인

Question

이 질문은 소프트웨어 회사에서 질문했습니다. 나는 간단한 해결책을 생각해 냈고 나는 다른 사람들이 그 해결책에 대해 어떻게 느끼는지 알고 싶다.

님의 시스템에 대한 API와 백엔드를 설계 해야하는 그 도시에 살고있는 사람들에게 충당 전화 번호 수 있습니다. 전화 번호는 이고 111-111-1111부터 시작하여 999-999-9999로 끝납니다. API는 다음을 수행 클라이언트 (도시에있는 사람)를 활성화해야합니다

1. 전화 번호에 대한 클라이언트 요청, 그것은 그들에게 가능한 번호 중 하나를 할당하게.
2. 일부 클라이언트는 멋진 번호를 원할 수 있으므로 특별히 할당 된 번호를 요청할 수 있습니다. 요청한 번호가 인 경우 시스템에서 할당합니다. 그렇지 않으면 시스템에서 사용 가능한 번호를 할당합니다.

시스템은 어떤 번호가 클라이언트에 할당되는지 알 필요가 없습니다. 동일한 클라이언트가 연속 요청을하고 전화 번호를 여러 개 가져올 수 있지만 시스템에 문제가 발생하지는 않습니다. 어떤 시점에서, 시스템은 어떤 전화 번호가 으로 할당되어 있고 어떤 전화 번호가 무료인지만을 알고 있습니다.

111-111-1111부터 999-999-9999까지의 숫자는 대략 80 억 개의 숫자에 해당합니다. 메모리가 제약이 아니라고 가정하면 다음 두 가지 접근 방식을 생각할 수 있습니다 (거의 비슷합니다).

1. 길이 80 억의 거대한 부울 배열을 유지하고 (next는 0으로 초기화된다) 배열 인덱스를 가리키는 next 포인터를 가지고있다. next이 가리키는 값이 비어 있지 않으면 무료 숫자가 발견 될 때까지 next을 전달하십시오. 공상적인 숫자가 요구 될 때, 해당 색인 위치가 자유로운지를 확인하고 그 숫자를 반환하십시오. 이 방법의 단점은 일반적인 방식으로 숫자를 할당 할 때 중간에 거대한 덩어리 (예를 들어 10 억 개)가 할당되어 공상적인 할당으로 할당 된 경우 next 포인터를 10 억 번 이동해야한다는 것입니다.

2. previos 디자인에서 언급 한 어려움을 극복하기 위해 일종의 연결된 해시 맵을 사용할 수 있습니다. 우리는 이중 연결리스트 (이전 디자인의 배열을 대체 함)와 배열의 각 요소가리스트의 해당 요소를 가리키는 목록과 동일한 길이의 또 다른 배열을 유지합니다. 그래서 일반적인 방법으로 숫자를 할당 할 때, 우리는 링크 된리스트의 포인터를 전진시키고 우리가 할당 할 때 노드를 표시합니다 (이전 방법과 동일). 화려한 번호를 할당 할 때 우리는 배열에서 먼저 색인을 생성하고 포인터를 따라 요구 한 특수 번호에 해당하는 노드를 목록에서 직접 찾을 수 있습니다. 노드가 식별되면 일반 노드와 다음 노드를 단락시켜 일반 할당을 수행 할 때 사용 된 번호를 하나씩 건너 뛸 필요가 없습니다 (이전 접근법의 문제점 이었음).

제가 올바른 길을 가고 있는지 알려주세요. 제가 빠뜨린 중요한 세부 사항을 알려주십시오.

Answer 1

먼저 API를 프로토 타입하지 않았습니다. 예를 들어, 이러한 API를 설계해야한다면 2 개의 API를 게시 할 것입니다.

string acquireNextAvailableNumber(); 
string acquireRequestedNumber(string special); 

둘째로, 구현 방법을 결정해야합니다. 코드 기반 또는 데이터 기반?

이러한 모든 숫자에 대해 해시를 유지하면 (메모리를 소비 함) 신속하게 번호 가용성을 쿼리 할 수 ​​있습니다. 또는

분산 된 숫자 (적은 메모리) 만 저장하도록 단일 목록을 유지 관리 할 수 ​​있습니다. 요청이 올 때마다 목록에서 1부터 n까지 숫자를 검색하기 시작합니다 (시간 복잡성 증가). 첫 번째 (또는 요청 된) 번호가 없으면 클라이언트에 할당하고 목록에 해당 항목을 추가합니다.

10 억 개의 숫자가 있으므로 공간과 시간의 절충을 고려해야합니다.

또한 데이터베이스를 활용할 수도 있습니다.

Answer 2

이 질문에 대한 anser에서 훨씬 더 잘할 수 있습니다.

먼저 API를 디자인해야합니다. Icarus3 추천 한 완벽하게 좋다 :

string acquireNextAvailableNumber(); 
boolean acquireRequestedNumber(string special); 

두 번째는 true를 돌려줍니다 (그 수를 보유) 가능한 경우, 그렇지 않은 경우는 false를 돌려줍니다.

질문에 전화 번호를 할당하는 방법이 명시되어 있지 않으므로 직접 할당하십시오. 첫 번째 '다음 이용 가능'요청은 "111-111-1111", 다음은 "111-111-1112"등으로 반환하십시오. 이는 마지막으로 할당 된 번호를 기억함으로써 '다음'을 통해 할당 된 모든 번호를 기록 할 수 있음을 의미합니다. ('111-111-1119'뒤에 "111-111-1120"또는 111-111-1121 "이 올지 여부를 묻는 것이 필요 하겠지만, 어쨌든 물어 봐야 할 것입니다. 중요한 것은 마지막으로 할당 된 번호를 아는 다음 번호가 무엇인지 알아낼 수 있다는 것입니다.)

개별적으로 저장해야하는 특별 요청입니다. 해시 테이블은 작동하지만 BST 또는 단순히 정렬 된 목록도 마찬가지입니다. 그것은 공간과 속도 사이에서 당신이 원하는 절충점과 얼마나 자주 특수 번호가 요구 될지에 달려 있습니다. 나머지 부분에서는 BST (번호순으로 주문)를 사용하겠습니다. 이유는 다음과 같습니다.

이렇게 코드를 작성하는 방법은 무엇입니까? 다음으로 할당 된 번호 :

1. 마지막으로 할당 된 번호를보고 다음 순서대로 찾으십시오.
2. 해당 번호가 특수 번호로 할당되지 않았는지 확인하십시오. BST가 있으면 BST에서 가장 낮은 항목이되기 때문에 BST로이 작업을 매우 빠르게 수행 할 수 있습니다.
3. 숫자가 '특별 숫자'데이터베이스에있는 경우 해당 번호를 포함하도록 '할당 된 숫자'값을 증가시키고 특수 숫자에서 항목을 제거하십시오. 그런 다음 특수 번호가 아닌 번호를 얻을 때까지이 과정을 반복하십시오.

이 프로세스는 '다음'에 의해 할당 된 마지막 '특수 번호'보다 낮은 모든 '특수 번호'가 특수 번호 데이터베이스에 나타나지 않도록합니다. '마지막으로 정상적인 번호가 할당 됨'이 증가함에 따라 할당 된 특수 번호가 흡수되어 표에서 제거됩니다. 이것은 순서대로 다음 번호가 특수 번호 데이터베이스에 있는지 여부를 묻는 경우 가장 낮은 항목 만 살펴 봐야합니다.

특수 번호를 확인하는 것은 쉽습니다.할당 된 마지막 '정상'번호보다 낮 으면 사용할 수 없습니다. 그렇지 않으면 BST에 있는지 확인하십시오. 그렇지 않으면 BST에 추가하십시오.

BST에 단일 번호뿐만 아니라 숫자 범위를 저장하여이 프로세스를 최적화 할 수 있습니다. 할당 된 특수 숫자가 밀집되어 있으면 트리의 공간과 액세스 할 수있는 수를 줄일 수 있습니다. 테스트 중에 '다음'숫자가 크기 n의 비율을 발견하면 루프 n 번 반복하지 않고 즉시 가장 높은 정상 숫자를 n만큼 증가시킬 수 있습니다.