Written by Poogle
on 

자료구조 면접 질문 모음

참고

Books

Cracking the Coding Interview

Articles

Backend-Interview-Question

Ready-For-Tech-Interview

bigocheatsheet

f-lab - 자바 백엔드 기술 면접 대비하기 - 1편

Posts

[실무 면접 준비 - 5] 자료구조 & Java (Data Structure & Java)

[자료구조] 우선순위 큐와 힙 (Priority Queue & Heap)

[Java] ArrayList는 어떻게 동적으로 사이즈가 늘어나는가? add() flow(동작 방식)


📌 자료구조

선형 자료구조와 비선형 자료구조의 차이는 무엇인가요?


📌 시간복잡도, 공간복잡도

🕰️ 시간복잡도

🫧 공간복잡도


📌 Big-O 표기법

각 자료구조 연산 별 시간복잡도

출처: bigocheatsheet

image

image



📌 Collection Framework in Java

image



📌 Array, LinkedList, ArrayList

IMG_A44B54629259-1

Array


LinkedList

❓ 왜 LinkedList를 사용할까요? (배열과 비교해서)

장점

단점


ArrayList (Dynamic Array)

❓ ArrayList는 내부적으로 어떻게 구현되어 있을까요?


비교



📌 List, Queue, Set 인터페이스



📌 Hash

Hash Table

Hash Function

Hash Collision Resolve 방식에는 어떠한 방법이 존재하나요?

Open Address 방식 (개방 주소법)

Separate Chaining 방식 (분리 연결법)

HashMap



📌 Stack, Queue

Stack

Queue



📌 Tree, Binary Tree, BST, Red Black Tree, AVL Tree, 최대/최소 신장 트리, B Tree, B+ Tree

Tree

image


Tree vs. Binary Tree(이진 트리)

image

Complete Binary Tree; 완전 이진 트리

image

Full Binary Tree; 전 이진 트리

image

Perfect Binary Tree; 포화 이진 트리

image


Binary Tree(이진 트리) vs. Binary Search Tree(이진 탐색 트리)

image

BST의 최악의 경우의 예와 시간복잡도

image


Red-Black Tree란 무엇인가요?

Red-Black Tree의 정의

Red-Black Tree 노드 삽입

Red-Black Tree 노드 삭제


AVL Tree


B Tree & B+ Tree

B Tree

B+ Tree


트라이(Trie)


Minimum Spanning Tree

Minimum Spanning Tree를 구하는 알고리즘에는 어떤 방법이 존재하나요?



📌 Heap, Priority Queue

Heap

❓ Heap과 BST의 차이

Priority Queue 우선순위 큐

우선순위 큐는 일반적으로 힙(Heap)을 이용하여 구현합니다.



📌 피보나치 수열을 코드로 구현하는 방법 (코드로 구현할 수 있는지, 재귀로 구현할 때의 문제점, DP로 구현하는 이유 등)

재귀로 구현

반복문으로 구현

DP로 구현

image


📌 그래프 - DFS, BFS

그래프

Graph 탐색에는 어떠한 방법이 존재하나요?

인접 행렬을 이용한 구현

void dfs(int x) {
    check[x] = true; //방문함
    for (int i = 1; i <= n; i++) {
        if (a[x][i] == 1 && check[i] == false) { //1) x와 i 사이에 간선이 있는지 2) i를 방문한 적이 없는지 확인
            dfs(i);
        }
    }
}

인접 리스트를 이용한 구현

void dfs(int x) {
    check[x] = true; //방문함
    for (int i = 1; i < a[x].size; i++) { //a[x]= x와 연결된 모든 정점(간선)
        int y = a[x][i];
        if(check[y] == false) {
            dfs(y); //O(V + E) = (V < E -> O(E))
        }
    }
}


BFS 조건

풀이

  1. 시작하는 칸을 큐에 넣고 방문했다는 표시를 남깁니다.
  2. 큐에서 원소를 꺼내어 그 칸에 상하좌우로 인접한 칸에 대해 (아래)3번을 진행합니다.
  3. 해당 칸을 이전에 방문했다면 아무 것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 큐에 삽입합니다.
  4. 큐가 빌 때까지 (위)2번을 반복합니다.
    • 모든 칸이 큐에 한 번씩 들어가므로 -> 칸이 N개 일 때 O(N)
    • 참고 - 구현 시 문제가 되는 경우들
      • 시작점에 방문했다는 표시를 남기지 않았을 때
      • 큐에 넣을 때 방문했다는 표시를 하는 대신 큐에서 빼낼 대 방문했다는 표시를 남길 때
      • 이웃한 원소가 범위를 벗어났는지에 대한 체크를 잘못했을 때

인접 행렬을 이용한 구현

check[1] = true; queue.push(1);
while (!queue.empty()) {
    int x = queue.front(); queue.pop();
    for (int i = 1; i <= n; i++) {
        if (a[x][i] == 1 && check[i] == false) {
            check[i] = true;
            queue.push(i);
        }
    }
}

인접 리스트를 이용한 구현

check[1] = true; queue.push(1);
while (!queue.empty()) {
    int x = queue.front(); queue.pop();
    for (int i = 0; i < a[x] .size(); i++) {
        int y = a[x][i];
        if (check[y] == false) {
            check[y] = true;
            queue.push(y);
        }
    }
}



📌 정렬, 탐색

Bubble Sort(버블 정렬)

bubble-sort-001


Insertion Sort(삽입 정렬)

insertion-sort-001

Selection Sort(선택 정렬)

selection-sort-001

Quick Sort(퀵 정렬)

quick-sort-001