기술 면접 - 손코딩

1. 스택 구현

---

코드 링크

2. 큐 구현

---

코드 링크

3. 연결리스트 구현

---

코드 링크

4. 해시테이블 구현

---

코드 링크

5. 싱글턴 패턴 구현

---

• 스레드 세이프 싱글턴 패턴

class Singleton {
    private Singleton() {}

    public static Singleton getInstance() {
        return LazyHolder.INSTANCE;
    }

    private static class LazyHolder {
        private static final Singleton INSTANCE = new Singleton();
    }
}

6. 피보나치

---

public class Fibonacci {
    static int[] cache = new int[11];
    public static void main(String[] args) {
        System.out.println(loopFibonacci(8));
        System.out.println(recurFibonacci(8));
        System.out.println(dpFibonacci(8));
    }

    public static int loopFibonacci(int n) {
        int a = 0, b = 1, c = 0;
        if(n == 0) return 0;
        else if(n == 1) return 1;
        else {
            for (int i = 2; i <= n; i++) {
                c = a + b;
                a = b;
                b = c;
            }
        }
        return c;
    }


    public static int recurFibonacci(int n) {
        if(n == 0) return 0;
        if(n == 1) return 1;
        return recurFibonacci(n - 1) + recurFibonacci(n - 2);
    }


    public static int dpFibonacci(int n) {
        if(n == 0) return 0;
        if(n == 1) return 1;
        int ret = cache[n];
        if(ret != 0) return ret;
        return cache[n] = dpFibonacci(n - 1) + dpFibonacci(n - 2);
    }
}

7. 팩토리얼

---

public class Factorial {
    static int[] cache = new int[10];
    public static void main(String[] args) {
        System.out.println(loopFactorial(5));
        System.out.println(recurFactorial(5));
        System.out.println(dpFactorial(5));
    }

      // 반복문으로 풀이
    public static int loopFactorial(int n) {
        int ret = 1;
        for(int i = 1; i <= n; i++) {
            ret *= i;
        }

        return ret;
    }

      // 재귀함수로 풀이
    public static int recurFactorial(int n) {
        if(n == 1)
            return 1;

        return n * recurFactorial(n - 1);
    }


      // 재귀함수 + 메모이제이션 풀이
    public static int dpFactorial(int n) {
        if(n == 1)
            return 1;

        int ret = cache[n];
        if(ret != 0)
            return ret;

        return cache[n] = n * dpFactorial(n - 1);
    }
}

8. 랜덤 한 자리 숫자 10개 출력

---

• Random 클래스 사용

public class RandomClass {
    public static void main(String[] args) {
        Random random = new Random();

        for(int i = 0; i < 10; i++) {
            System.out.println(random.nextInt(9) + 1);
        }
    }
}

9. 아나그램 판별

---

• 정렬해서 같은지 판별

import java.util.Arrays;

public class Anagram {
    public static void main(String[] args) {
        char[] a = "acdbe".toCharArray();
        char[] b = "ecabd".toCharArray();
        Arrays.sort(a);
        Arrays.sort(b);

        if(Arrays.equals(a, b))
            System.out.println(true);
        else
            System.out.println(false);
    }
}

10. 문자열 안에 문자들이 고유한 문자인지 확인

---

• 유니코드라도 돌아가는 코드
• 아스키 코드일 때 최적화하려면 128칸 불린 배열을 사용할 수도 있음

static HashSet<Integer> hs = new HashSet<>();
public static boolean isUnique(String str) {
    char[] arr = str.toCharArray();

    for(int c : arr) {
        if(hs.contains(c)) return false;
        hs.add(c);
    }
    return true;
}

11. 최소 공배수, 최대 공약수

---

// 유클리드 호제법
// 최소공배수 = (n1 * n2) / (n1과 n2의 최대공약수)

public class GCD_LCM {
    public static void main(String[] args) {
        System.out.println(gcd(8, 12));

        int LCM = (8 * 12) / gcd(8, 12);
        System.out.println(LCM);
    }


    public static int gcd(int a, int b) {
        if(b == 0) return a;
        return gcd(b, a % b);
    }
}

13. 이진 트리 순회

---

public class TreeTraversal {
    class Node {
        int data;
        Node left, right;

        public Node(int data) {
            this.data = data;
        }
    }

    class Tree {
        public Node root;

        public void setRoot(Node node) {
            root = node;
        }

        public Node getRoot() {
            return root;
        }

        public Node createNode(int data, Node left, Node right) {
            Node node = new Node(data);
            node.left = left;
            node.right = right;
            return node;
        }
                //중위 순회
        public void inOrder(Node node) {
            if(node == null) return;

            inOrder(node.left);
            System.out.println(node.data);
            inOrder(node.right);
        }
                //전위 순회
        public void preOrder(Node node) {
            if(node == null) return;

            System.out.println(node.data);
            preOrder(node.left);
            preOrder(node.right);
        }
                //후위 순회
        public void postOrder(Node node) {
            if(node == null) return;

            postOrder(node.left);
            postOrder(node.right);
            System.out.println(node.data);
        }
    }
}

14. 진수 변환

---

public class Radix {
    public static void main(String[] args) {
        changeRadix(2556, 16);
    }


    public static void changeRadix(int n, int radix) {
        int[] num = new int[100];

        int idx = 0;
        while(n > 0) {
            num[idx] = n % radix;
            n /= radix;
            idx++;
        }
        idx--;

        for(;idx >= 0; idx--) {
            if(num[idx] < 10)
                System.out.printf("%c", num[idx] + 48);
            else
                System.out.printf("%c", num[idx] + 55);
        }
    }
}

15. 1000보다 작은 숫자 중 3과 5의 배수의 총합

---

public static void main(String[] args) {
    int sum = 0;
    for(int n = 1; n < 1000; n++) {
        if(n % 3 == 0 || n % 5 == 0)
            sum += n;
    }
    System.out.println(sum);
}

16. 문자열 역순 변환

---

public static void main(String[] args) {
    String str = "abcdefg";
    StringBuilder sb = new StringBuilder(str);
    sb.reverse();
    System.out.println(sb);
}

17. 문자열에서 모음만 거꾸로

---

public static void main(String[] args) {
    String str = "bacedufivo";
    StringBuilder sb = new StringBuilder(str);
    HashSet<Character> vowel = new HashSet<>();
    vowel.add('a');
    vowel.add('e');
    vowel.add('i');
    vowel.add('o');
    vowel.add('u');

    int left = 0, right = str.length() - 1;

    while(left < right) {
        while(!vowel.contains(str.charAt(left)))
            left++;
        while(!vowel.contains(str.charAt(right)))
            right--;

        sb.setCharAt(left, str.charAt(right));
        sb.setCharAt(right, str.charAt(left));

        left++;
        right--;
    }

    System.out.println(sb);
}

18. 문자열에 있는 단어 순서 바꾸기

---

public static void main(String[] args) {
    String str = "Hello I am a developer";
    String[] arr = str.split(" ");

    for(int i = arr.length - 1; i >= 0; i--)
        System.out.print(arr[i] + " ");
}

19. 비트 1 개수 카운트

---

public static void main(String[] args) {
    int n = 1024;

    int cnt = 0;
    while(n > 0) {
        n &= n - 1;
        cnt++;
    }

    System.out.println(cnt);
}

20. N크기의 정수 배열에서 K번째로 큰 수

---

• Quick Selection 사용
• 보통 정렬을 사용하면 O(NlgN), 이 방법은 O(N)

static int K = 4;
static int ret = -1;

public static void main(String[] args) {
    int[] arr = {3, 5, 2, 4, 1};

    QuickSelection(arr, 0, arr.length - 1);
    System.out.println(ret);
}


public static void QuickSelection(int[] arr, int left, int right) {
    int pivot = partition(arr, left, right);

    if(pivot == K - 1) {
       ret = arr[pivot];
    }
    else if(pivot > K - 1) {
        QuickSelection(arr, left, pivot - 1);
    } else {
        QuickSelection(arr, pivot + 1, right);
    }
}

public static int partition(int[] arr, int left, int right) {
    int mid = (left + right) / 2;
    swap(arr, left, mid);

    int i = left, j = right;
    int pivot = arr[left];

    while (i < j) {
        while(arr[j] >= pivot)
            j--;
        while(i < j && arr[i] <= pivot)
            i++;

        swap(arr, i, j);
    }

    arr[left] = arr[i];
    arr[i] = pivot;

    return i;
}

public static void swap(int[] arr, int a, int b) {
    int tmp = arr[a];
    arr[a] = arr[b];
    arr[b] = tmp;
}