상위 30개 데이터 구조 및 알고리즘 인터뷰 질문 및 답변 [초보자 및 경험자용]

데이터 구조와 알고리즘은 컴퓨터 과학 및 공학 세계에서 가장 중요한 과목 중 하나입니다. 소프트웨어 엔지니어링 인터뷰에 참석하는 경우 데이터 구조 및 알고리즘에 대해 특별히 전담하는 일련의 질문에 직면하게 될 것입니다. 이것이 얼마나 중요한지 알 수 있습니다!

알고리즘은 컴퓨터 과학 및 데이터 과학에서 일어나는 모든 일의 핵심입니다. 기계 학습에서 AI, 블록체인에 이르기까지 모든 기술은 알고리즘에서 실행됩니다. 그리고 알고리즘이 작동하려면 데이터 구조가 필요합니다. 따라서 데이터 구조 및 알고리즘에 대한 결합된 지식은 인터뷰 중에 군중에서 눈에 띄는 데 도움이 될 수 있습니다.

그러나 문제는 DSA가 광범위한 영역이라는 것입니다. 여기에서 학습은 멈추지 않으며 항상 이해해야 하는 몇 가지 새로운 발전 사항이 있습니다. 데이터 구조 및 알고리즘을 다룰 때는 지속적인 기술 향상이 필수이지만 오늘은 기술 면접에 도움이 되는 몇 가지 DSA 기본 사항을 살펴보겠습니다.

상위 데이터 구조 및 알고리즘 인터뷰 Q&A

1. '데이터 구조'에 대해 무엇을 이해합니까?

데이터 구조는 데이터를 체계적으로 정의, 저장 및 액세스하는 데 사용되는 기술로 정의할 수 있습니다. 그것들은 모든 알고리즘의 가장 중요한 구성 요소를 형성합니다. 데이터 구조의 유형에 따라 다른 종류의 데이터를 저장하고 다양한 방식으로 액세스할 수 있습니다. 알고리즘이 결과를 반환하려면 최종 결과에 도달하기 위해 조직적이고 효율적인 방식으로 일련의 데이터 구조를 조작하고 조작해야 합니다.

2. 파일 구조와 데이터 구조를 어떻게 구별할 수 있습니까?

파일 구조에서 데이터는 표준 파일 저장 정책에 따라 디스크에 저장되며 외부 타사 응용 프로그램과 호환되지 않습니다. 반면 데이터 구조에서는 데이터가 디스크와 RAM 모두에 맞춤형 스토리지 정책에 따라 저장되며 외부 앱과의 호환성이 매우 높습니다.

3. 광범위한 유형의 데이터 구조는 무엇입니까?

데이터 구조는 크게 두 가지 범주로 나눌 수 있습니다.

• 선형: 모든 요소가 순차적으로 저장되고 검색이 선형으로 발생합니다. 배열은 비계층적이며 각 요소에는 하나의 후속 작업과 하나의 선행 작업이 있습니다. 예 – 배열, 연결 목록, 스택, 대기열 등
• 비선형: 여기서 스토리지는 선형 시퀀스로 발생하지 않습니다. 즉, 모든 요소에 반드시 하나의 후속 작업과 선행 작업만 있는 것은 아닙니다. 대신, 비선형 데이터 구조의 요소는 비선형 방식으로 둘 이상의 항목에 연결됩니다. 예 – 트리, 그래프, 힙.

4. 데이터 구조의 주요 사용 영역은 무엇입니까?

데이터 구조는 생각할 수 있는 모든 컴퓨팅 분야, 특히 알고리즘 및 알고리즘 최적화에서 거의 필요합니다. 다음은 데이터 구조가 광범위하게 사용되는 몇 가지 다른 영역입니다.

• 운영 체제 설계
• 수치해석
• 머신 러닝과 AI
• 컴파일러 설계 및 개발
• 데이터베이스 관리
• 어휘 분석
• 그래픽 프로그래밍
• 검색 및 정렬 알고리즘 등

5. 스택 데이터 구조를 설명하고 사용 영역을 언급하십시오.

스택은 '상단'이라고 하는 한쪽 끝에서만 삽입 및 삭제를 허용하는 정렬된 목록입니다. 스택의 최상위 요소에 대해 알려주는 '상위' 요소에 대한 포인터가 있는 재귀적 데이터 구조입니다. 요소 검색 전략에 따라 스택은 후입선출(Last-In-First-Out)이라고도 합니다. 스택에 푸시된 마지막 요소가 맨 위에 있고 가장 먼저 튀어나오기 때문입니다. 다음은 스택 데이터 구조의 몇 가지 용도입니다.

• 역추적
• 메모리 관리
• 함수 반환 및 호출
• 표현 평가

6. 스택에서 수행할 수 있는 작업은 무엇입니까?

스택 데이터 구조는 다음 세 가지 작업을 지원합니다.

• push() — 스택의 맨 위 위치에 요소를 삽입합니다.
• pop() — 스택의 맨 위에서 하나의 요소를 가져옵니다.
• peek() — 스택에서 꺼내지 않고 스택 상단에 있는 요소를 확인합니다.

7. Postfix 표현식에 대해 무엇을 이해합니까?

후위 표현식은 연산자가 피연산자 뒤에 오는 표현식입니다. 이는 하위 표현식을 괄호로 묶을 필요가 없고 연산자 우선 순위를 고려할 필요가 없기 때문에 계산 용어에서 매우 유용합니다. a+b라는 표현은 단순히 접미사에서 ab+로 표시됩니다.

8. 2D 배열 요소는 메모리에 어떻게 저장됩니까?

2차원 배열의 요소는 다음 두 가지 방법 중 하나로 메모리에 저장할 수 있습니다.

• Row-Major: 이 방법에서는 먼저 배열의 모든 행이 메모리에 연속적으로 저장됩니다. 먼저 첫 번째 행이 완전히 저장되고 두 번째 행이 마지막 행까지 계속 저장됩니다.
• Column-Major: 배열의 모든 열이 지속적으로 메모리에 저장됩니다. 먼저 첫 번째 열이 완전히 저장된 다음 두 번째 열이 저장되는 방식입니다.

9. 연결 목록 데이터 구조를 정의합니다.

연결 목록은 무작위로 저장된 개체인 노드의 모음입니다. 각 노드에는 데이터 필드와 링크 필드의 두 가지 내부 요소가 있습니다. 데이터 필드에는 특정 노드가 가진 값이 있고 링크 필드에는 이 노드가 연결된 다음 노드에 대한 포인터가 있습니다. 상황에 따라 연결 목록은 선형 및 비선형 데이터 구조로 모두 간주될 수 있습니다.

10. 연결 목록이 배열보다 나은 점은 무엇입니까?

연결 목록은 다음과 같은 면에서 배열보다 낫습니다.

• 배열 크기는 런타임에 고정되어 나중에 수정할 수 없지만 연결 목록은 요구 사항에 따라 실시간으로 확장할 수 있습니다.
• 연결 목록은 메모리에 연속적으로 저장되지 않으므로 결과적으로 정적으로 저장된 배열보다 메모리 효율성이 훨씬 높습니다.
• Linked List에 저장할 수 있는 요소의 수는 사용 가능한 메모리 공간으로만 제한되는 반면 요소의 수는 배열의 크기에 따라 제한됩니다.

11. C 프로그래밍 언어에서 이기종 연결 리스트를 구현하기 위해 어떤 포인터를 사용하시겠습니까?

이기종 연결 목록은 이름에서 알 수 있듯이 서로 다른 데이터 유형을 보유합니다. 결과적으로 여기서는 일반 포인터를 사용할 수 없습니다. 따라서 Void 포인터는 모든 유형의 값을 가리킬 수 있으므로 일반적으로 이러한 시나리오에서 사용됩니다.

12. 이중 연결 목록이란 무엇입니까?

이름에서 알 수 있듯이 이중 연결 목록은 다음 노드와 이전 노드 모두에 연결된 노드가 있는 연결 목록입니다. 결과적으로 이중 연결 목록의 노드에는 2개가 아닌 3개의 필드가 있습니다.

• 데이터 필드
• 다음 포인터(다음 노드를 가리키기 위해)
• 이전 포인터(이전 노드를 가리킬 때)

13. 일부 응용 프로그램과 함께 대기열 데이터 구조를 설명하십시오.

큐는 REAR 및 FRONT라고 하는 한쪽 끝이 아닌 두 끝에서 요소를 삽입 및 삭제할 수 있도록 하는 정렬된 목록입니다. 삽입은 FRONT 끝에서 발생하고 삭제는 REAR 끝에서 발생합니다. 이 때문에 대기열을 FIFO(선입선출)라고 합니다. 다음은 데이터 구조로서의 큐의 광범위한 응용 프로그램입니다.

• CPU, 프린터, 디스크 등과 같은 단일 공유 리소스에 대한 대기 목록의 경우
• 데이터의 비동기 전송의 경우, 예를 들어 파일 IO, 소켓, 파이프.
• 대부분의 미디어 플레이어 응용 프로그램에서 버퍼로 사용됩니다.
• 중단 처리를 위해 운영 체제에서.

14. 배열을 사용하여 큐를 구현할 때의 몇 가지 단점을 나열할 수 있습니까?

배열을 사용하여 대기열을 구현할 때 주로 두 가지 단점이 발생합니다.

• 배열이 정적 데이터 구조이기 때문에 메모리를 잘못 관리하면 배열을 사용하여 대기열을 구현하면 대기열의 많은 기능이 제거됩니다.
• 배열 정의 중에 배열 크기가 정의되기 때문에 크기에 문제가 있습니다. 따라서 배열 크기보다 더 많은 요소를 대기열에 추가하려는 경우 불가능합니다.

15. 요소가 순환 대기열에 삽입되기 위해서는 어떤 조건이 충족되어야 합니까?

다음은 순환 대기열에 삽입하는 것과 관련된 몇 가지 조건입니다.

• (후면 + 1)%maxsize == 전면 -> 큐가 가득 찼음을 의미하는 경우 -> 더 이상 삽입할 수 없습니다.
• 후면 != 최대 – 1이면 후면 값이 최대 크기로 증가하고 후면 끝에 새 값이 삽입됩니다.
• front != 0이고 rear == max -1 ->이면 대기열이 가득 차지 않았음을 의미합니다. 따라서 rear의 값은 0으로 설정되고 순환 큐의 뒤쪽 끝에 새 요소가 삽입됩니다.

16. 대기열이 무엇입니까?

Double-Ended Queue 또는 deque는 앞뒤 양쪽 끝에서 삽입 및 삭제를 용이하게 하는 정렬된 요소 집합입니다. 결과적으로 이것은 대기열 데이터 구조보다 훨씬 더 유연합니다.

17. 트리 데이터 구조를 정의하고 몇 가지 유형의 트리를 나열합니다.

트리는 다양한 노드를 포함하는 비선형 재귀 데이터 구조입니다. 하나의 특정 노드는 다른 모든 노드가 나오는 트리의 루트로 지정됩니다. 루트를 제외하고 다른 모든 노드를 자식 노드라고 합니다. 트리 데이터 구조에는 다음과 같은 유형이 있습니다.

• 일반 나무
• 이진 트리
• 이진 검색 트리
• 숲
• 표현식 트리
• 토너먼트 트리

18. 버블 정렬은 어떻게 작동합니까?

버블 정렬은 가장 많이 사용되는 정렬 알고리즘 중 하나이며 인접한 요소를 비교하고 값에 따라 위치를 교환하여 배열과 함께 사용됩니다. 작동 방식에 대한 시각화는 물 위에서 떠다니는 거품과 가라앉는 더 큰 개체와 같기 때문에 버블 정렬이라고 합니다.

읽기: C의 데이터 구조 및 사용 방법

19. 사용 가능한 가장 빠른 정렬 알고리즘은 무엇입니까?

병합 정렬, 빠른 정렬, 버블 정렬 등과 ​​같은 다양한 정렬 알고리즘을 사용할 수 있습니다. 이 중에서 객관적으로 가장 빠른 특정 알고리즘은 입력 데이터, 알고리즘이 데이터를 처리한 후의 반응 및 저장 방법에 따라 성능이 크게 다르기 때문에 하나를 선택할 수 없습니다.

20. 이진 트리란 무엇입니까?

이진 트리는 각 노드가 최대 두 개의 자식을 가질 수 있는 특수한 유형의 트리입니다. 일을 쉽게 하기 위해 이진 트리는 일반적으로 루트 노드, 오른쪽 하위 트리 및 왼쪽 하위 트리의 세 가지 분리된 집합으로 나뉩니다.

21. AVL 트리는 BST와 비교하여 다양한 작업에서 어떻게 사용될 수 있습니까?

AVL 나무는 높이 균형이 잡힌 나무이므로 나무가 어느 한 쪽에서 기울어지는 것을 허용하지 않습니다. 높이 h의 BST에서 수행된 모든 연산에 걸리는 시간은 O(h)입니다. 그러나 이것은 BST가 왜곡되는 최악의 시나리오에서 O(n)이 될 수 있습니다. AVL은 트리의 높이를 제한하여 이러한 제한을 제거하는 데 도움이 됩니다. 그렇게 함으로써, n = 노드의 수인 O(log n)의 최대값이 되도록 모든 작업에 대한 상한을 부과합니다.

22. B-트리의 속성은 무엇입니까?

차수가 m인 B-트리는 다음 속성을 포함합니다.

• M-way 트리의 모든 속성.
• B_tree의 모든 노드에는 최대 m개의 자식이 있습니다.
• 루트와 리프를 제외한 모든 노드에는 최소 m / 2개의 자식이 있습니다.
• 루트 노드에는 최소 2개의 하위 노드가 있어야 합니다.
• 모든 리프 노드는 동일한 수평 레벨에 있어야 합니다.

23. 그래프 데이터 구조에 대해 무엇을 이해하고 계십니까?

그래프(G) 데이터 구조는 정렬된 집합 G(V,E)로 정의할 수 있습니다. 여기서 V는 정점 집합을 나타내고 E는 연결을 형성하는 모서리입니다. 기본적으로 그래프는 노드가 부모-자식 관계뿐만 아니라 노드 간의 복잡한 관계를 유지할 수 있는 순환 트리로 생각할 수 있습니다.

24. 그래프 데이터 구조를 참조하여 주기, 경로 및 회로를 구분합니다.

주기, 경로 및 회로의 차이점은 다음과 같습니다.

• 패치는 아무런 제약 없이 가장자리로 연결된 인접 정점의 순서입니다.
• 사이클은 초기 정점이 끝 정점과 동일한 닫힌 경로입니다. 주기에서 특정 정점은 두 번 방문할 수 없습니다.
• 순환과 같은 회로는 초기 정점이 끝 정점과 동일한 닫힌 경로입니다. 그러나 회로의 특정 정점은 두 번 이상 방문할 수 있습니다.

25. Kruskal의 알고리즘은 어떻게 작동합니까?

Kruskal의 알고리즘은 그래프를 포리스트로 간주하고 각 노드를 개별 트리로 간주합니다. 트리는 모든 옵션 중에서 가장 비용이 적게 들고 MST(Minimum Spanning Tree)의 속성을 위반하지 않는 경우에만 다른 트리에 연결된다고 합니다.

관련 항목: 데이터 구조의 이진 트리

26. Prim의 알고리즘은 어떻게 스패닝 트리를 찾는가?

Prim의 알고리즘은 노드를 단일 트리로 간주하여 작동합니다. 그런 다음, 필요한 스패닝 트리로 변환되어야 하는 주어진 그래프에서 스패닝 트리에 새 노드를 계속 추가합니다.

27. MST(최소 스패닝 트리)란 무엇입니까?

가중 그래프에서 MST는 최소 가중치를 갖는 트리이지만 모든 정점에 걸쳐 있습니다.

28. 재귀 함수란?

정의에 따르면 재귀 함수는 자신을 다시 호출하거나 이를 호출하는 함수를 직접 호출합니다. 모든 재귀 함수에는 몇 가지 기본 기준이 있으며, 이에 따라 함수가 자체 호출을 중지합니다.

29. 보간 검색 기술이란 무엇입니까?

보간 검색 기술은 이진 검색 방법을 수정한 것입니다. 보간 검색 알고리즘은 원하는 값의 프로빙 위치에서 작동합니다.

30. 해싱이란 무엇입니까?

해싱은 키-값 쌍의 범위를 배열의 인덱스로 변환하는 데 사용되는 매우 유용한 기술입니다. 해시 테이블은 키-값 쌍을 제공하는 것만으로 데이터 인덱스를 쉽게 찾을 수 있는 연관 데이터 저장소를 생성할 때 편리합니다!

결론적으로

데이터 구조는 진정으로 컴퓨터 과학에서 일어나는 모든 것의 기초입니다. 데이터 과학, 기계 학습, 인공 지능, IoT와 같은 컴퓨터 과학의 더 복잡한 응용 프로그램도 모두 데이터 구조 및 알고리즘을 기반으로 구축됩니다.

따라서 뉴에이지 분야에서 경력을 쌓고자 하는 초보자라면 먼저 데이터 구조와 알고리즘을 마스터하는 것이 좋습니다. 또는 초보자를 위해 설계된 데이터 과학의 Executive PG 프로그램 과정을 확인할 수도 있습니다 . 처음부터 배우고 데이터 과학 전문가가 되십시오. 오늘 등록하세요!