# Google | DSA 문제 대비하는 방법

DSA 문제 풀 때 해야할 것
---
1) 문제를 찬찬히 읽어보고 **정확하게 문제의 의도를 파악**해라. (Interviewer에게 내가 잘 이해했는지를 되물어보자)
2) 일단 **brute force**로 해결하는 방법을 제시하고, 이 방법의 문제점을 설명한다.
3) 그 문제점을 해결하기 위해 어떤 자료구조와 알고리즘을 통해서 **brute force한 방법보다 개선시킬 수 있는 방법**을 제안한다.
4) **toy example** 을 통해서 coding 없이 잘 동작하는지 확인한다. 간단한 테스트를 통해서 잘 동작한다는 것을 보여준다.
5) Edge case (corner case) 등에 문제가 없다고 판단되면 **진짜 code 를 작성한다.** 이 때 작성하는 코드는 pseudo code가 아니기 때문에 언어의 syntax도 고려해야한다.

Leet Code 난이도
---
- Easy 난이도: **brute force + basic tricks**
- acceptance rate으로 내림차순 정렬 후 빠르게 문제 해결
- 적어도 brute force 문제는 hint 없이 풀어보자
- 한번의 submission 으로 accept 되는 것을 목표로 하자
- performance 향상을 위해서 top solution들은 어떻게 해결했는지 확인하자
- Accept되는 것도 중요하지만, 문제를 풀면서 나오는 여러가지 코딩 스킬(basic tricks)을 배우는데 집중하자.
- Medium 난이도: **DSA 측면에서 문제 접근**.
- Easy 했던 것처럼 brute force한 방법으로 접근했다가 TLE (Time Limit Exceed)가 나올 수 있음.
- 문제를 보고 어떤 문제 타입인지 파악하고, 30분 안에 해결할 때까지는 연습할 것
- 어느정도 문제풀이의 방향이 잡혔으면 반쯤 온 것. 적어도 suboptimal 한 문제에 대해서 solution 을 구현해 볼 것.
- top solution 을 보면서 어떤 부분을 최적화할 수 있는지 살펴본다.
- Hard 난이도: **?**
- 45분 정도 시간을 갖고 solution을 떠올릴 수 있어야 한다.
- BUD (Bottleneck, Unnecessary work, Duplicated work) 을 생각하자: https://www.slideshare.net/gayle2/cracking-the-coding-interview-abbreviated-aug-2016/26

Leet Code 문제들에 등장하는 패턴들
---
- Graph, Tree, String 문제의 대부분은 (단순하게 생각하면) DFS 또는 BFS 문제로 풀리는 경우가 허다하다.

#### DFS
- DFS에서 유념할 순서
1) push stack
2) pop top (if not visited)
3) stack 이 빌 때까지 1 ~ 3 반복
- DFS 가 적용되는 문제들
1) 그래프 탐색
2) 모든 솔루션 찾기 (ex. 순열)
3) 솔루션에 다다르기 위한 path 기록하기
4) 그래프에서 사이클 찾기

#### BFS
- BFS 가 적용되는 문제들
1) shortest path 찾는 문제 (단, 간선의 weight 가 없어야 함)
2) 레벨 또는 스텝을 찾는 문제: 방문할 노드에 level도 같이 저장하자.
3) 퍼즐

#### String
- Longest Common Sequence (LCS): string 에서 가장 긴 common substring 을 찾는 문제. Dynamic Programming 으로 품.

#### Kandane's Algorithm
- 부분 배열의 최대합 문제
#### Dynamic Programming
- 다양함...

Tricks
---
- Two pointers
- Bit manipulation: 배열 대신에 메모리 공간을 아끼고, pass by reference 문제점을 해결할 수 있는 솔루션
- CTCI (Cracking... 코딩 인터뷰 완전 분석 이라는 책으로 코딩 인터뷰의 교과서라고 생각하는 것 같음)
- https://cses.fi/book/book.pdf 에서 트릭을 배워보자

Google 인터뷰 질문 분석
---
- https://www.codinginterview.com/google-interview-questions
- https://www.carrus.io/blog/crack-the-google-coding-interview
- https://igotanoffer.com/blogs/tech/google-software-engineer-interview

Leet code 외 문제 제공 사이트
---
- https://www.interviewbit.com/search/?q=Google

참고 자료
---
1. https://medium.com/leetcode-patterns/leetcode-pattern-1-bfs-dfs-25-ofthe-problems-part-1-519450a84353
2. https://medium.com/algorithms-and-leetcode/want-to-crack-leetcode-problems-easily-dc825e27e423
3. https://www.reddit.com/r/cscareerquestions/comments/6luszf/a_leetcode_grinding_guide/
4. https://leetcode.com/discuss/career/449744/google-interview-tips-faqs-answered-resources