미국 개발자 산만한 일기 미국 개발자 산만한 일기

마이크로소프트에 입사한지 벌써 1달이 조금 넘었다. 잊기 전에 기록해두고, 혹시나 나 같은 다른 사람들에게 도움이 되었으면 해서 블로그에 남긴다. 인터뷰 보기 전 스펙 나는 미국학위가 전혀 없다. 한국 CS 학사 졸업이고 당연하지만(?) 미국 사람들은 한국에 있는 학교들을 모르기 때문에 내가 어느정도의 대학을 나왔는지 알지 못한다. 대학 졸업 후, 미국 인턴쉽에 지원해 J1 비자로 한인 회사를 1년 다녔다. 그 뒤 결혼으로 영주권을 받고 개발직으로 작은회사 8개월, 미국 법인 삼성을 3년 8개월 다녔다. 인터뷰 준비 인터뷰 준비 단계는 크게 이력서 / 알고리즘 / 영어 대화 스킬 / 시스템 디자인 4가지로 나누어서 준비했다. 이력서(Resume) 나의 경우에는 이력서를 통해 한번 컨텍이 되고 나면 그 다..

리트코드 - leetcode.com/problems/serialize-and-deserialize-binary-tree/ 구글 인터뷰 문제 TOP10 중 2 위인 BFS 알고리즘 BFS 는 트리 구조의 Data를 너비 먼저 탐색하는 (Breath First Search) 알고리즘이다. 꼭 binary tree 가 아니여도 된다. BFS DFS ▪ 깊이가 얕고 노드가 적을 때 유리 ▪ DFS 보다 메모리를 더 많이 쓸 수 있다. 탐색할 모든 노드를 큐에 저장 ▪ 큐 (Queue) ▪ 답이 되는 경로가 최단경로 보장 ▪ 깊이가 깊고 노드가 많을 때 유리 ▪ BFS 보다 메모리를 더 적게 쓴다. 백트래킹을 해야하는 노드만 저장 ▪ 스택 (Stack), 재귀 (Recursive) ▪ 끝까지 찾아봐야 최단경로를 ..

leetcode.com/problems/two-sum/ Two Sum - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 리트 코드 알고리즘, 1번 문제. 쉬운 문제이고 다양한 방법으로 풀 수 있지만 Hash Table의 원리를 이용하면 시간복잡도가 더 최적화된 방법으로 풀 수 있다. Approach Hash Table이 적용된 HashMap 을 이용한다. HashMap의 search (get이나 containsKey method) 는 key 기준이므로 value..

leetcode.com/problems/design-hashmap/ Design HashMap - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com Hash Table은 검색에 O(1) 의 시간복잡도를 가져서 다른 Search 문제에도 많이 쓰이는 Data Structure 이다. Hash Table을 이용한 Hash Set, Hash Map의 Big O 참고 Hash Table이 Solution 으로 쓰인 문제 예시 더보기 leetcode.com/problems/..

leetcode.com/problems/sudoku-solver/ Sudoku Solver - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 백트래킹이란, 맞는 답을 먼저 찾는 대신 일단 후보를 입력하고 답인것 처럼 진행하다가 조건이 안맞는 경우가 생기면 다시 되돌아와서 다른 후보값을 입력하는 방식으로 답을 찾는 알고리즘이다. 가지치기 (pruning) 처럼 답이 아닌 것들을 후보에서 제거하여 경우의 수를 줄여나가 답을 찾는 접근 recursive 를 사용하는 ..

leetcode.com/problems/valid-sudoku/ Valid Sudoku - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 스도쿠 문제가 유효한지 아닌지 검사하는 코드에 대한 문제 스도쿠 문제의 힌트 값들이 들어있는 2차원 배열이 주어지고 행,열,3x3 박스안에서 중복되는 값이 있는지 체크하는 문제이다. Approach 1 행,렬,3x3 박스 각각 3번의 다른 범위에 대한 중복 체크가 필요하다. 중복을 허용하지 않고 검색이 쉬운 HashSet 을 ..

관련 문제 링크 : leetcode.com/problems/maximum-subarray/ leetcode.com/problems/gas-station/ 다른 다이나믹 프로그래밍 문제 : 더보기 leetcode.com/problems/best-time-to-buy-and-sell-stock/ 이문제의 핵심은 각각의 부분합을 구할 때 현재 위치 이전까지의 결과가 반영된다는 것을 이해하는 것이다. 예를들어 -3이 있는 index 2까지의 부분합을 구할 때 우리는 이전 index 들인 -2 와 1 의 합에 현재 index 2의 값 -3을 더함으로써 쉽게 index 2 까지의 부분합을 구할 수 있다. 그리고 그다음 index인 4까지의 부분합을 구할 때 또 -3까지의 부분합에 4를 더하여 쉽게 구할 수 있다. ..

1. DFS (깊이 우선 탐색) 더보기 ▪트리 leetcode.com/problems/binary-tree-paths/ leetcode.com/problems/merge-two-binary-trees/ leetcode.com/problems/balanced-binary-tree leetcode.com/problems/maximum-depth-of-binary-tree/ leetcode.com/problems/minimum-depth-of-binary-tree/ leetcode.com/problems/maximum-depth-of-n-ary-tree/ ▪백트래킹 leetcode.com/problems/word-search/ leetcode.com/problems/sudoku-solver/ ▶문제 해결 포스..