241017 TIL

2024년 10월 17일 작성

• SOLID 오랜만에 복습
  • It’s not easy to explain the concept
• Finish Sorting with implementation
  • In java, we can splice the array by using Array.copyOfRange()
  • Copilot is very useful when we make edge cases of the question.

Leetcode

Tree

• https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/

  helpful picture → https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/description/comments/1947878

  class Solution {
      public TreeNode sortedArrayToBST(int[] nums) {
          if (nums.length == 0) {
              return null;
          }
          if (nums.length == 1) {
              return new TreeNode(nums[0]);
          }
          int mid = nums.length / 2;
          TreeNode head = new TreeNode(nums[mid]);
          head.left = sortedArrayToBST(Arrays.copyOfRange(nums, 0, mid));
          head.right = sortedArrayToBST(Arrays.copyOfRange(nums, **mid + 1**, nums.length));
          return head;
      }
  }

  • Trial and error: I miss-pass the argument for building right tree, I accidentally passed mid. We have to exclude mid-th element in child tree.

• https://leetcode.com/problems/balanced-binary-tree/

  • If a child tree is not balanced, then the root tree of the child tree is not balanced as well. like below ⬇️

    

    Although the height of the left tree and the height of the right tree are same, each tree itself is not height-balanced. So the original tree is also not height-balanced.

• https://leetcode.com/problems/minimum-depth-of-binary-tree/

  • I approached this question by using recursion, but the time complexity was not good. So I saw the other solutions to get another idea and find it → “Why dfs? Here is my bfs solution.” Right. I don’t need to search depth first, because I just want to count minimum depth of the tree. If we search the node breadth first and find the node that hasn’t any child node then we can simply return the node’s depth and exit the method.

Recursion

• https://leetcode.com/problems/kth-largest-element-in-an-array/description/
  • Approach
    1. Sort the array and search $k^{th}$ element → $O(nlogn)$
    2. Using min heap size of $k$ → $O(nlogk)$
       • detail
         1. Inserting into the heap takes O(log k) time for each element.
         2. Processing n elements results in a total time complexity of O(n log k).
    3. Using quick select → best: $O(n)$ , worst: $O(n^2)$
  • I already solved this problem, but my solution was using priority queue.
  • In the lecture, I can get new solution that uses recursion(quick select?). I’ve never heard Hoare’s QuickSelect before. Thank you teacher..
  • And this is my implementation of quick sort
    • https://www.notion.so/oieuoa/Recursion-Kth-Largest-Element-1225220bc5758081a40ae3ab642fb262?pvs=4
  • Insights from quick sort → Quick sort is also recursive mechanism (divide & conquer → very important to explain this algorithmic paradigm)
  • Quick Select, which side of our partition do we want to continue searching through.

    • We don’t have to sort both sides of the array divided by pivot

      • we are only interested in the side which has a range of indices, including k

    • implementation

      // Only this part is different from quicksort
      if (left == k) {
          return array[left];
      }
      // if the left is smaller than k, we have to find the kth element on the right side
      if (left < k) {
          return quickSelect(array, left + 1, end, k);
      }
      // if the left is bigger than k, we have to find the kth element on the left side
      return quickSelect(array, start, left - 1, k);

쉬운 문제 뒤에 숨은 속 마음

• 위 글은 faang 기업들에서 인터뷰를 많이 진행해본 분이 본인이 좋아하는 질문과 함께 문제를 푸는 다양한 방법과 그 과정에서 물어보는 것들 그리고 지원자들이 어떤 부분에서 갈리는지를 풀어놓은 글이다!

• 진짜 재밌고 글을 잘 쓰신다. 내 기준 영어로 잘 쓴 글은 영어를 못하는 사람(나)도 술술 읽을 수 있는 글이다.

• 처음부터 심금을 울리는 말이 있었는데..

  I tend to favor easier questions that lead to a high quality conversation where I can learn about the way somebody thinks

  나는 우리가 깍두기라서 쉬운 문제를 내나 싶었는데, 그것보다는 이런 면접 문화가 회사 전체적으로 합의돼있는 것 같다는 생각이 들었다.

  연습할 시간이 부족한게 너무 아쉽다. 한국도 이렇게 채용하는 곳이 있으면 좋겠다. 앞으로 이런 기업에 또 지원할 기회가 있을까..? 그러려면 얼마나 영어해야하지..

  https://www.amazon.jobs/en/jobs/2769612/2025-graduate-software-dev-engineer?cmpid=SPLICX0248M&ss=paid

• 전체적으로 우리가 직관적으로 수행하는 최적화를 짚어가며 평가한다는 느낌이다. 그래서 우리도 직관으로 당연하게 생각하던 것들을 설명하고 그냥 넘어가지 않는 연습을 계속 해야하나보다.. 직관으로만 풀다보면 정확한 근거를 마련하지 않은 채로 답만 얻게 되는데, 이런 경우 최적화, 변경된 요구사항 만족을 위해 답변하기 어려워진다. Downside/Tradeoff 를 항상 설명하고 적고 가자

• Exercise: Imposter Syndrome 라는 제목으로 강의가 있어서 무슨 문제지? 했는데, 내가 아는 imposter syndrome 이야기였다.

  임포스터 증후군을 겪고 있다면 이는 당신은 가치있는 일을 하고 있다는 의미입니다. 그러니 이걸 나쁘게 생각마세요. 당신이 잘하고 있고, 배우고 있고, 한계를 늘려감에 대한 격려로 받아들이세요. 라나 뭐라나,,