leetcode 영어 인터뷰 준비

1. 언어적 준비

1) post-order 필요한거 설명할때

We can see that we need to process the children before we process a node. This indicates that we need to perform a post-order traversal.
To implement post-order traversal, we implement a recursive function. This function takes the root of the subtree as the input.

2) max_sum = max(max_sum, a) 이런 상황일때

compare max_sum with ""the sum of the following"(좋은 표현)", and update it if it is smaller.

3) path in the binary tree 설명할때 
A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.

= A path is a continuous sequence of nodes connected to each other.

4) Tree traverse

 

5) BFS 할때

 

6) 처음에 문제 직관적으로 풀어보겠다고 할때,

The solution is very intuitive(starightforward).

7) reverse하겠다고 할때 + 설명 so that으로 하기 (reverse, flip)

Another method is to flip the second half of the linked list so that the last element points to the second last element,

https://leetcode.com/problems/maximum-twin-sum-of-a-linked-list/

 

2. 개념적 준비

모든 Recursive 문제는 3개를 생각해야한다. 1) end-condition 2) loop statement 3) return value

 

3. 실전 문제로 준비

(1) add two string

https://leetcode.com/problems/add-strings/

=>1) reverse(ans)가 아니라 reverse(ans.begin(), ans.end())로 해야한다. (reverse cmd 사용법에 대해서 배움)

2) string이 첫번째 index가 처음이 아니라 마지막 부터 시작함 (i = 0 으로 초기화 되면 안되고 뒤에서 부터 가야함)

3) while (num1[i] && num2[i]) 이러면 안 됨 while (i < num1.size() && i < num2.size()) 이나 while (i >=0 && j>=0)이런식으로 해야함

4) carry는 num에다가 더하면된다. 마지막에 ans에다가 더할려고 하지말고

( ans += num + '0' + carry 은 잘못된거 )

* 표현

 

(2) Remove Linked list Elements

https://leetcode.com/problems/remove-linked-list-elements/

 while (ptr) {
  if (ptr->val == val) {
    if (prev) {
      prev->next = ptr->next;
    } else 
      head = ptr->next;
  }
  else // 이거를 안 해서 틀렸음
    prev = ptr;
  ptr = ptr->next;
  }
}

1) ptr를 항상 만들어야하고, prev를 잘 활용해야

2) prev를 잘해야함

* 표현

 

(3) Missing Number

https://leetcode.com/problems/missing-number

* 풀이 3개 

1) [Sorting]  Time : nLogn/O(nLogn), Sapce : O(N) - stack

2) [Hash] Time : O(N), Space : O(N)

3) [Bit manupulation] Time : O(N), Space : O(1)

표현

(4) Count Good Nodes in Binary Tree

https://leetcode.com/problems/count-good-nodes-in-binary-tree

1) Void recursive

2) Int recursive

3) Queue

> 무조건 기존함수에서 변형시킬때 저런식으로 말하고 시작하기! (왠만하며 기존의 제약에서 벗어나기)

 

(5) Largest Subarray Length K

https://leetcode.com/problems/largest-subarray-length-k

그냥 제일 큰거 구하면 되는거였음!

 

(6) Add Two Numbers

https://leetcode.com/problems/add-two-numbers/description/

carry똑같이 생각해줘야하고, 제일 마지막 carry 생각해야하는거 중요!

+) 문법 new 공부할수있다

 

(7) Find Subsequence of Length K With the Largest Sum

https://leetcode.com/problems/find-subsequence-of-length-k-with-the-largest-sum/description/

+문법) heap + pair 사용 + sort랑 cmp 같이 사용!

우선 heap을 사용해서 largest sum을 구한다음에 sort로 index기준으로 정렬

 

neetcode Twopointers

1. Valid Palindrome

2. Two Sum II Input Array Is Sorted -> binary search느낌이 아니라 그냥 two pointers로 값 다를때 움직여주기만 하는거

 

neetcode sliding window

424. Longest Repeating Character Replacement

풀이 3개 인데 그 중 2개 공부

1) binary search로 길이 선택 + valid 확인 (sliding window)

2) valid 확인(sliding window)

가장 중요한건 길이를 구하는 과정에서 나는 다른거를 diff라는 variable을 선언해서 밀고가려고했는데 그거 말고, hash를 사용해서 maxFrequency를 구하고, maxFrequency + k < substring_length 일때만 pleft를 움직이면 되는거였다.

그리고 string에서 substring은 항상 분리되지 않고, 연속적이기 때문에 그걸 마음에 두고있으면 될거같다.

 

neetcode stack

20. Valid Parentheses

매번 마지막에 남은 size 확인하기

 

Binaray Search

875. koko eating bananas

주의 1) binarysearch에서 if 문이 mid 보다 크거나 작은것이 아니라, mid를 통과하는지 함수를 사용해야하고,

 2) 그럴때에 따라 right = mid +1, 이런식으로 설정해야함 (left = mid -1 아님주의)

3) long long으로 해야함 + left + (right - left)임 left - 나 right - 가 아니라

 

Linked List

143. Reorder List

ptr->next를 rev가 아니라 rev->next로 했다.

void reorderList(ListNode* head) {
        ListNode *middle = findMiddle(head);
        ListNode *rev = reverse(middle);
        ListNode *ptr = head;
        while (rev && rev->next) {
            ListNode *tmp = ptr->next;
            ListNode *tmp2 = rev->next;
            ptr->next = rev;
            rev->next = tmp;
            ptr = tmp;
            rev = tmp2;
        }
    }

287. Find the Duplicate Number

1) Tortoise and Hare 로 linkedlist로 생각하는 풀이

2) base_cnt랑 nums_cnt로 bit mask로 푸는 풀이 

Copy List With Random Pointer

Random Pointer까지 copy해야해서 복잡한데 hash를 사용하면 간단히 해결할 수 있다는걸 알기

 

Tree

226. Invert Binary Tree 가 left랑 right를 먼저 post order로 구하고 바꾼다는 개념에서 근본,

104. Maximum Depth of Binary Tree 랑 543. Diameter of Binary Tree, 110. Balanced Binary Tree 가 약간 한 유형

근데 543. Diameter of Binary Tree 랑 124. Binary Tree Maximum Path Sum 를 묶어서 이해할 수도 있음

100. Same Tree랑 572. Subtree of Another Tree가 약간 한 유형이다.

110. Balanced Binary Tree의 경우 left, right는 postorder인것마냥 구하는데, &로 recursion가는게 좀 다르다.

 

 

543. Diameter of Binary Tree

이거도 pathsum처럼 풀수가있음

// path sum 이용한 풀이
class Solution {
public:
    int height(TreeNode* root, int& ans)
    {
        if (!root) return 0;
        int l = height(root->left, ans);
        int r = height(root->right, ans);
        ans = max(ans, l + r);
        return max(l, r) + 1;
    }
    int diameterOfBinaryTree(TreeNode* root) {
        int ans = 0;
        height(root, ans);
        return ans;
    }
};

// height 이용한 풀이
class Solution {
public:
    int heightofTree(TreeNode* root) {
        if (!root)
            return 0;
        return max(heightofTree(root->left), heightofTree(root->right)) + 1;
    }
    void maxDiameter(TreeNode* root, int &maxLength) {
        if (root->left)
            maxDiameter(root->left, maxLength);
        if (root->right)
            maxDiameter(root->right, maxLength);
        int left = heightofTree(root->left);
        int right = heightofTree(root->right);
        maxLength = max(maxLength, left + right);
    }
    int diameterOfBinaryTree(TreeNode* root) {
        int maxLength = 0;
        maxDiameter(root, maxLength);
        return maxLength;
    }
};

 

124. Binary Tree Maximum Path Sum

"In this problem, we are given the root of a binary tree. We want to find the maximum path sum of this tree."

"We must traverse the entire tree to find the maximum path sum. (At the top of my head, we can talk about brute force solution. So, I can consider ~~)
One way to find the maximum path sum would be to look at all possible paths, calculate their path sums, and then find the maximum path sum. However, this would be a "brute force" approach. If there are n nodes in the tree, creating all the paths and computing their path sums would take O(n ^ 2) time. We can do better than this."

"We can consider a scenario where the path with the highest sum passes through the tree's root.
There could be four possibilities."
Concept : Post Order by DFS
 *Possibilities
    "1) The path starts at the root goes down through the root's left child."
    "2)  .    .    .     .  .  .     .    .     .      .   .     right child."
    "3) The path involves both the left and the right child with the root."
    "4) The path involves only root (X any child)"
  => "path always contains the root!"
  "Therefore, in the beginning, we can assume that the path sum is the root node's value.
  : The path goes down the left or the right subtree only if we see a gain in the path sum.To find the maximum path sum, we determine if there is a viable path leading down through the left or the right subtree. 
    -> This means we must first determine the gain in the path sum contributed by the left and the right subtree.  => We can see that we need to process the children before we process a node. This indicates that we need to perform a post-order traversal"

"Let me work you through how my post-order DFS algorithm works."
Datastructure("The datastructrues I'm gonna use are quite simple.")
"1) I need to use TreeNode structure to store the value of node and move to left and right pointer"
"2) And I'm gonna declare one integer as a global variable to find maximum pathSum comparing with the the sum of the following and the sum of the each nodes"

Algorithm ("To explain Algorithms, I wanna seperate in two functions.")
* Main function ("First Main function which means that I am given in the question,")
"In here"
1) "First of all, Initialize a global variable max_sum to MIN_INT"
2) "Next, Call the function 'gain_from_subtree' on the tree's root."
3) "Lastly, Return the value of max_sum"

"Now, let's make our recursive function named as gain_from_subtree which acts as a post order DFS.
This function is, in addition to returning the path sum gain contributed by the subtree, the recursive function also keeps track of the maximum path sum. "
* Gain_from_subtree -> param : root of the subtree
"Every recursive function needs base case. In here, base case is this. If a node doesn't have a left or right child, then the path sum contributed by the respective subtree is 0"
[Base case] 
1) if the root is null
    return 0
2) "Next, call the function recursively on the left and right child of the root.
Store the results in gain_from_left and gain_from_right, respectively."
3) "If either is negative, set it to 0."
=> "This is because we don't want to include a path sum contributed by a subtree if it is negative."
4) "Just before we finished this function with return value. Lastly, Update the maximum path sum (max_sum) seen so far."
"To do so, compare max_sum with ""the sum of the following"(좋은 표현)", and update it if it is smaller."
5) "So finally, return the path sum gain contributed by the subtree."
"This is the maximum of the following two values : The valud of root plus + max(left, right)"

"Let me explain Complexity analysis.
Time complexity would be O(n) : Each node in the tree is visited only once. During a visit, we perform constant time operations, including two recursive calls and calculating the max path sum for the current node. So the time complexity is O(n)
Space complexity would be O(n) : We don't use any auxiliary data structure, but the recursive call stack can go as deep as the tree's height. In the worst case, the tree is a linked list, so the height is n(like skew tree). Therefore, the space complexity O(n)"

 

 

여기서 또 중요했던게 

1) post order로 도는거

2) 함수 return값이랑

dfadsfㅇ

 

Linked List

2095. Delete the Middle Node of a Linked List

Middle을 구하기만 하려고 하면, slow = head, fast = head로 하고 돌리면 되는데,
여기서는  Middle을 제거하려고 하는거니까 fast=head->next->next로 놓고 middle전의 slow를 구해서 없애버리기

struct ListNode* deleteMiddle(struct ListNode* head) {
    struct ListNode* ans = head;
    struct ListNode* slow = head;
    struct ListNode* fast;

    if (head == NULL || head->next == NULL)
        return NULL;
    fast = head->next->next; // 원래 middle구할때는 그냥 head하고 시작해도 되는데 여긴 안됨
    while (slow && fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    slow->next = slow->next->next;
    return ans;
}

206. Reverse Linked List

iterative하게 하는 거는 쉬운데(prev while 밖에서 만들고, tmp 안에서 만들고 4줄로 돌리기)
recursive하게 하는 거는 은근 생각해야할게 있다.
모든 Recursive 문제는 3개를 생각해야한다. 1) end-condition 2) loop statement 3) return value

여기서는
1) end-condition을 리스트의 마지막을 보고 생각하고

if (head == NULL || head->next == NULL)

return head;

2) loop statement는 리스트의 앞을 보고 생각하고

head->next->next = head;

head->next = NULL;

3) return value는 함수로 다음거 던져주고 리턴한다.

struct ListNode *p = reverseList(head->next);

return p;

struct ListNode* reverseList(struct ListNode* head) {
    if (head == NULL || head->next == NULL)
        return head;

    struct ListNode *p = reverseList(head->next);
    head->next->next = head;
    head->next = NULL;
    return p;
}
    /*
struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* prev = NULL;
    while (head) {
        struct ListNode* tmp = head->next;
        head->next = prev;
        prev = head;
        head = tmp;
    }
    return prev;
}*/

328. Odd Even Linked List

틀린부분1) 마지막에 odd의 next를 even의 head에 안 이어주었다.

틀린부분2) while의 조건문을 (odd & even)했는데 even이 항상 앞에 있으므로 even을 while문에 넣어주었어야했다.

struct ListNode* oddEvenList(struct ListNode* head) {
    if (head == NULL || head->next == NULL)
        return head;
    struct ListNode* odd = head;
    struct ListNode* even = head->next;
    struct ListNode* evenhead = even;
    struct ListNode *ans = head;
    while (even && even->next) { // (odd && even)하면 틀림
        struct ListNode* tmp = odd->next->next; // odd->next하면 틀림
        struct ListNode* tmp2 = even->next->next;
        if (odd->next) odd->next = odd->next->next;
        if (even->next) even->next = even->next->next;
        odd = tmp;
        even = tmp2;
    }
    if (odd)
        odd->next = evenhead;
    return ans;
}