C# 시니어 코딩·알고리즘 기술면접

Interlocked 클래스를 활용한 CAS(Compare-And-Swap) 연산으로 Lock-Free 방식을 구현할 수 있습니다. Interlocked.CompareExchange를 사용하여 재고 값을 원자적으로 업데이트하며, 실패 시 재시도하는 스핀락 방식으로 구현합니다. 시간 복잡도는 경합이 적을 때 O(1)이지만, 경합이 심할 경우 재시도로 인해 성능이 저하될 수 있습니다. 대안으로 ConcurrentDictionary와 같은 .NET의 동시성 컬렉션을 활용하거나, 재고를 샤딩하여 경합을 분산시키는 방법도 있습니다. 극단적인 고성능이 필요한 경우 Actor 모델(예: Akka.NET)을 도입하여 재고별로 단일 스레드 처리를 보장하는 아키텍처도 고려할 수 있습니다.

Hash Partitioning과 Min-Heap을 조합한 접근법을 사용합니다. 먼저 파일을 스트리밍으로 읽으면서 IP 주소를 해시 함수로 N개의 파티션 파일로 분할합니다(O(n) 시간). 각 파티션은 메모리에 적재 가능한 크기가 되도록 N을 조정합니다. 각 파티션별로 Dictionary를 사용해 IP별 카운트를 집계하고(O(m) 공간, m은 파티션 내 고유 IP 수), 크기 100인 Min-Heap을 유지하며 상위 100개를 추출합니다(O(m log 100)). 모든 파티션의 상위 100개를 병합하여 최종 상위 100개를 선택합니다(O(N*100 log 100)). 전체 시간 복잡도는 O(n)이며, 공간 복잡도는 O(m + 100)으로 메모리 제약을 만족합니다. 대안으로 Count-Min Sketch 같은 확률적 자료구조를 사용하면 메모리를 더 절약할 수 있지만 정확도가 약간 감소합니다.

Dictionary와 Doubly Linked List를 조합하여 구현합니다. Dictionary는 키를 LinkedListNode의 참조로 매핑하여 O(1) 조회를 제공하고, Doubly Linked List는 접근 순서를 유지하며 O(1) 삽입/삭제를 보장합니다. Get 연산 시 Dictionary에서 노드를 찾아 리스트의 헤드로 이동시키고, Put 연산 시 새 노드를 헤드에 추가하며 용량 초과 시 테일 노드를 제거합니다. 멀티스레드 환경에서는 ReaderWriterLockSlim을 사용하여 읽기는 동시 허용, 쓰기는 배타적으로 제어하거나, ConcurrentDictionary를 사용하되 리스트 조작 시에만 lock을 사용하는 하이브리드 접근도 가능합니다. 대안으로 .NET의 MemoryCache를 활용하거나, 높은 동시성이 필요하면 lock-free 알고리즘 기반의 써드파티 라이브러리를 검토할 수 있습니다.