Grammar Mistake & Coding Interview tips

1. CoordinatesQueue이런식으로 만들고 나중에 q라고 함

2. vector에다가 push_back안하고 push라고 함 or pq에다가 push함 top해야하는

3

 

Intuition

  C++ is a widely used programming language that is known for its efficiency and power. However, even experienced programmers can make mistakes when writing code in C++. One common area where programmers may struggle is with grammar, as C++ has a complex set of rules and conventions that must be followed.

  These rules cover everything from syntax and punctuation to proper use of keywords and identifiers. In this article, we will explore some of the most common grammar mistakes made in C++ and provide tips on how to avoid them. By improving your understanding of C++ grammar, you can write more efficient and effective code that is easier to read and maintain.

알아두면 유용한거

1. 이차원백터 copy그냥 v = c 이렇게 가능 + private에 선언할때는 초기화 못하고 생성자에서 초기화 혹은 main함수에서 초기화

2. c++ priority_queue에서 안에 넣을때 다음과 같다. const를 꼭 앞뒤로 해줘야한다.

3. struct cmp안의 operator()랑 struct안의 operator<의 차이

Grammer Mistake

1) binary search 할때 left <right 가 아니라 left<=right (상황에 따라 다르긴 함)

2) INT_MAX가 integer 최고값 / string reverse 할때는 아래와 같이

reverse(ans.begin(),ans.end()); // return 값이 있는건 아니라서 이 자체를 return은 안됨

3) string 자르는거 x.substr(0,짜르고싶은idx);

4) priority_queue<구조체> 할때는 아래와 같음

class MinStack {
private:
    struct Point{
        int idx;
        int val;
    };
    stack<Point> st;
    struct cmp{
        bool operator()(Point &a, Point &b){
            return a.val>b.val;
        }
    };
    priority_queue<Point,vector<Point>,cmp> minHeap;
    int idx;
    bool visited[30001];
public:
    MinStack() {
        idx=0;
    }
    
    void push(int val) {
        visited[idx]=true;
        st.push({idx,val});
        minHeap.push({idx++,val});
    }
    
    void pop() {
        Point now = st.top();
        st.pop();
        visited[now.idx]=false;
    }
    
    int top() {
        return st.top().val;
    }
    
    int getMin() {
        while(visited[minHeap.top().idx]==false){
            minHeap.pop();
        }
        return minHeap.top().val;
    }
};

 

 

조심해야될 실수1

실수 1) this -> cnt임

실수 2) bool operator<를 쓸때는 앞은 몰라도 뒤는 반드시 const 붙여줘야함

bool operator<(const Point input) const{
        return this->cnt < input.cnt;
    }

이런 실수 자주함

조심해야될 실수2

 

[외부 페이지 참조]

https://kbj96.tistory.com/15

[C++ STL] Priority_queue 사용법

 

5) String to Int / Int to String

stoi("123"); // string -> int

to_string("123"); // int -> string

6) 8진수 -> 10진수 / 10진수 -> 16진수 함수들 찾아놓기

7) string 에서 제일 뒤에꺼 빼는거는 pop_back()이다.

8) runtime error = misalliend

<내코드>

class Solution {
private:
    struct Point{
        int idx;
        int tem;
    };
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        stack<Point> st;
        vector<int> ans(temperatures.size(),0);
        int idx=0;
        for(auto tem:temperatures){
            if(!st.empty() && st.top().tem<tem){
                Point now = st.top();
                while(now.tem<tem){
                    Point now = st.top();
                    ans[now.idx] = idx - now.idx;
                    st.pop();
                }
            }
            st.push({idx,tem});
            idx++;
        }
        return ans;
    }
};

<문제점>

stack이 다 빌수가있는 경우가 있다. 근데 에러가 mis aligned로 나와서 헷갈리는거 같다.

아래는 맞는 코드다.

class Solution {
private:
    struct Point{
        int idx;
        int tem;
    };
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        stack<Point> st;
        vector<int> ans(temperatures.size(),0);
        int idx=0;
        
        for(auto tem:temperatures){
            if(!st.empty() && st.top().tem<tem){
                while(!st.empty() && st.top().tem<tem){
                    ans[st.top().idx] = idx - st.top().idx;
                    st.pop();
                }
            }
            st.push({idx,tem});
            idx++;
        }
        return ans;
    }
};

case2) 이런 경우가 또 나왔다,,

문제는 아래와 같이 misaligned 다.. 그것도 뜬금없이 tmp배열이 선언된 곳에서 misaligned라고 해서 당황했다.

<문제 현상>

<문제 코드>

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
private:
    int arr[50001];
    int tmp[50001];
public:
    void mergesort(int start, int end){
        if(start>=end) return;
        int mid = (start+end)/2;
        mergesort(start,mid);
        mergesort(mid+1,end);
        int i=start,k=start,j=mid+1;
        while(i<=mid && j<=end){
            if(arr[i]<arr[j]){
                tmp[k++]=arr[i++];
            }else{
                tmp[k++]=arr[j++];
            }
        }
        while(i<=mid) tmp[k++]=arr[i++];
        while(j<=end) tmp[k++]=arr[j++];
        for(int p=start ; p<=end; p++){
            arr[p]=tmp[p];
        }
    }
    ListNode* sortList(ListNode* head) {
        int idx=0;
        while(head){
            arr[idx++]=head->val;
            head = head->next;
        }

        mergesort(0,idx-1);

        //ListNode *ans = new ListNode(); -> 맞는거
        ListNode *ans,*cur; // -> 틀린거
        cur = ans;
        for(int i=idx-1; i>=0;i--){
            printf("%d ",arr[i]);
            //ListNode *tmp = new ListNode(arr[i],cur);
            //cur = tmp;
        }

        return ans;
    }
};

결국엔 new 연산을 해줘서 초기화를 해주라는 말이었음,,

해당 문제는 ans를 new해줘서 초기화를 안해주면 stack 영역을 이상한 곳에 접근한다는 에를 만날수도있음,,

 

 

9) vector 정렬,,! 하다가 문제 

vector 정렬 = sort(v.begin() , v.end())

<문제 코드>

class Solution {
private:
    struct Point{
        int pos;
        int spd;
    };
    //struct cmp{ // priority_queue처럼은 안 되나 도전 해봤었음
        int cmp(Point &a, Point &b){ // bool x
            return a.pos<b.pos;
        }
    //};
public:
    int carFleet(int target, vector<int>& position, vector<int>& speed) {
        vector<Point> v;
        for(int i=0; i<position.size();i++){
            v.push_back({position[i],speed[i]});
        }
        sort(v.begin(),v.end(),cmp);
        return 0;        
    }
};

<문제점>

cmp가 static으로 불려야함 

<맞는 코드>

class Solution {
private:
    struct Point{
        int pos;
        int spd;
    };
    static int cmp(Point &a, Point &b){ // static must be needed + bool도 괜춘
        return a.pos>b.pos;
    }
public:
    
    int carFleet(int target, vector<int>& position, vector<int>& speed) {
        int ans=0;
        vector<Point> v;
        for(int i=0; i<position.size();i++){
            v.push_back({position[i],speed[i]});
        }
        sort(v.begin(),v.end(),cmp);

        stack<float> st; // store destination time to check whether car will colide with previous one or not  => I get wrong answer with "int" stack
        for(int i=0; i<v.size(); i++){
            //printf(">=%d %d :  ",v[i].pos, v[i].spd);
            if(st.empty() || st.top() < (float)((target-v[i].pos)/(float)v[i].spd))
                st.push((float)(target-v[i].pos)/(float)v[i].spd);
            //printf("%d %d\n",st.top(), ((target-v[i].pos)/v[i].spd));
        }
        return st.size();        
    }
};

 

 

10) string에서 뒤에 뺄때 pop_back()가능!

https://leetcode.com/problems/letter-combinations-of-a-phone-number/

에서 

이런식으로 사용가능

 

11) 아직도 원인을 모르는 것 + 2차원 배열 초기화 잘보기

이거 pass

class Solution {
public:
    void dfs(string digits, vector<string>& ans, string& tmp, int depth, char aPhone[10][4]) {
        if (digits.length() == depth && digits.length()!=0) {
            
            ans.push_back(tmp);
            return;
        }        
        
        for (int j=0; j<4; j++) {
            
            if (aPhone[digits[depth]-'0'][j]) {
                tmp += aPhone[digits[depth]-'0'][j];
                dfs(digits, ans, tmp, depth+1, aPhone);
                tmp.pop_back();
            }
        }
        
    }

    vector<string> letterCombinations(string digits) {
        char aPhone[11][4] = {{}, {}, {'a','b','c'}, {'d','e','f'}, {'g','h','i'}, {'j','k','l'}, {'m','n','o'}, {'p','q','r','s'}, {'t','u','v'}, {'w','x','y','z'}};
        vector<string> ans;
        string tmp;

        dfs(digits, ans, tmp, 0, aPhone);

        return ans;
    }
};

이거는 fail (depth만 tmp.length()로!)

class Solution {
public:
    void dfs(string digits, vector<string>& ans, string& tmp, int depth, char aPhone[10][4]) {
        printf("%d %d\n",depth, digits.length());
        if (digits.length() == tmp.length() && digits.length()!=0) {
            
            ans.push_back(tmp);
            return;
        }        
        
        for (int j=0; j<4; j++) {
            
            if (aPhone[digits[depth]-'0'][j]) {
                tmp += aPhone[digits[depth]-'0'][j];
                dfs(digits, ans, tmp, depth+1, aPhone);
                tmp.pop_back();
            }
        }
        
    }

    vector<string> letterCombinations(string digits) {
        char aPhone[11][4] = {{}, {}, {'a','b','c'}, {'d','e','f'}, {'g','h','i'}, {'j','k','l'}, {'m','n','o'}, {'p','q','r','s'}, {'t','u','v'}, {'w','x','y','z'}};
        vector<string> ans;
        string tmp;

        dfs(digits, ans, tmp, 0, aPhone);

        return ans;
    }
};

 

11) unordered_map의 경우 사용하고 나면 first, second로 사용가

 

14) heap buffer 초과했다고 하면 배열 범위를 초과한곳에 접근하지는 않았는지 확인

15) pq.pop()이 empty일때 해도 heap-buffer-overflow 가능하다 (621. Task Scheduler 풀다가 발생)

 

 

Interview tips & 좋은 표현 

1) O(n) = Big O of N

2) two pointer 설명할때, We can simply use the two-pointer technique to compare indexes at either end, moving in towards the middle. One pointer starts at the start and goes up, and the other starts at the end and goes down.

3) 각각 = respectively, separately

4) 고려하지 말자 => remove it from consieration

5) ~보다 크다 작다 => greater than / 

6) ~라 하겠다 => I just say (wanna say) 

7) 내 큐에는 내 구조체 넣겠다. => In my queue, I'm gonna hold my own structure.

8) queue가 빌때까지 pop 한다.(BFS에서) => As long as the queue is not empty, remove the next node from the queue, 동사(ex) swap the child node..)

9) 다른 풀이도 있다고 말할때 => Alternatively, (we can solve the problem iteratively)

영어 n^3 같은 표현들 => https://nanjidostudy.tistory.com/12

10) hypothetically : 가정해서 말하자면,
(4. Median of Two Sorted Arrays의 neetcode 설명 13:13에도 나옴)

 

 

* Time Complexity 말할때

1) 무조건 한 번씩은 방문해야 될때 time complexity 말할때 => We cannot do better than that, since at the very least we have to visit each node (to invert it).

* Space Complexity 말할때

1) 재귀함수 설명할때 Because of recursion, O(h) function calls will be placed on the stack in the worst case, where hhh is the height of the tree.

 

 

Google 기출 분석

(1) Line sweep 문제

https://leetcode.com/discuss/study-guide/2166045/line-sweep-algorithms

1) 1854. Maximum Population Year -1D easy type

걍 단순 더해도 됨, 범위도 작고 양도 작아서

2) 253. Meeting Rooms II - 1D easy type

풀이 3개임. 1) priority_queue 풀이 2) sort 3) line sweep 

3) Meeting Room - 1D type2

 

4) Insert Intervals - 1D type2

 

5) Merge Intervals - 1D type2

6) Amount of New Area Painted Each Day - Hard

7) Employee Free Time - Hard

8) Minimum Interval to Include Each Query - Hard

 

(2) Hash 문제

1) 359. Logger Rate Limiter

Hash 써야하는데 내 Hash 쓰