Things About Leetcode Before That Coding Interview

Introduction

At the bare minimum, it’s good to have a solid understanding of 2 Pointers, sliding window, BFS/DFS, Trees, Graphs, Stacks, Queus, Hash Maps.

Leetcode IDE Tips

No Global Variables

To evaluate our code samples, Leetcode simply import the file containing our implementation. Then, it will run test cases on it. If we have a global variable, the global variable will be used consistently. E.g.,

1
2
3
4
5
int MyGlobalVar2;    // bad

class Solution{
    int MyGlobalVar;    // good
};

Shortcuts & Debugging Tips

• ctrl - ' is to run.
• Leetcode does support std::cout in a separate window stdout.
• no need for std::

Questions

Two Pointers

Question Description

Two pointers is a local gradient descent technique: we use 2 points starting from the head and tail of the vector. Calculate the area, then move the pointer if its side is shorter than the other.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
    int maxArea(vector<int>& height) {
        int i_s = 0, i_e = height.size()-1;
        int max = 0;
        while (i_s != i_e){
            int area = std::min(height.at(i_s), height.at(i_e)) * (i_e - i_s); 
            max = std::max(area, max);
            if (height.at(i_s) > height.at(i_e)){
                i_e --;
            }
            else{
                i_s ++;
            }
        }
        // Why does this work? gradient descent? 
        return 0;
    }

In this case, it can actually guarantee to find the global maximum. Why? Because as we move the pointers along, we are actually evaluating:

1. what’s the max when size = L
2. what’s the max when size = L-1 (apparently if we move the pointer the way we do)
3. What’s the max when size = L-2 (still, we can find the max there)

So we find all these local maximums, which covers all combination of sides. So, two pointers is an interesting algorithm!

Queue

Sliding Window Max

This question is an interesting one. We can quickly come up with a brute force solution, but wait a second, that is $o(nk)$. There’s gotta be a better way. Can we do this in just one pass?

The trick is a maintaining a queue to store indices of monotonically decreasing elements. For example: Input: nums = [1,3,-1,-3,5,3,6,7], k = 3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
std::vector<int> maxSlidingWindow(std::vector<int>& nums, int k) {
    std::deque<int> dq;  // Stores indices, not values
    std::vector<int> result;
    for (int i = 0; i < nums.size(); ++i) {
        // Remove elements that are out of the window
        if (!dq.empty() && dq.front() < i - k + 1) {
            dq.pop_front();
        }
        // Maintain decreasing order: Remove elements smaller than nums[i]
        while (!dq.empty() && nums[dq.back()] <= nums[i]) {
            dq.pop_back();
        }
        // Add current element's index
        dq.push_back(i);
        // Store the max value once we have processed at least k elements
        if (i >= k - 1) {
            result.push_back(nums[dq.front()]);  // The max is always at the front
        }
    }
    return result;
}

Common Leetcode Commands (C++)

std::string

• Raw C strings (char arrays) should always terminate with a null character, ‘\0’. Fun fact about char arrays: nullptr is inserted at the back of the array. This is a convention for argv

1
2
3
4
5
6
7
8
char str[] = "a string";
printf("%s", str);  // searches for "\0" to terminate

char *strs[] = {"str1", "str2", nullptr};
for (size_t i = 0; strs[i] != nullptr; ++i){
    // uses nullptr to terminate string array.  
    printf("%s", strs[i]);
}

Substring

• std::string substr(size_t pos = 0, size_t len = std::string::npos) const;
  • std::string::npos is optional. If not provided, it will be the full string size. ```cpp

std::string str = “Hello, World!”; std::string sub1 = str.substr(0, 5); std::string sub3 = str.substr(7);

1
2
3
4
5
6
7
### Best way for concactenate variables of different types - use `stringstream`

```cpp
std::ostringstream oss;
oss << "index are not matching! " << idx << "|" << match.idx_in_this_cloud;
throw std::runtime_error(oss.str());

Find Next Element

• Universal search method: std::search(start_it, end_it, sub_element_end, sub_element_end)

1
2
3
4
5
6
7
std::vector<int> vec = {1, 2, 3, 4, 5, 6, 7, 8, 9};
std::vector<int> sub = {4, 5, 6};
auto it = std::search(vec.begin(), vec.end(), sub.begin(), sub.end());

std::list<int> lst = {10, 20, 30, 40, 50, 60};
std::list<int> sub = {30, 40};
auto it = std::search(lst.begin(), lst.end(), sub.begin(), sub.end());

• Vector, list:

1
2
auto it = std::find(vec.begin(), vec.end(), 3);
auto it = std::find(lst.begin(), lst.end(), 30);

• String str.find(sub_str). Returns std::string::npos if nothing is found

1
2
3
std::string str = "Hello, World!";
std::string sub = "World";
size_t pos = str.find(sub);

1
2
3
4
5
6
7
8
9
- For string, if the search is for **tokenization**, `std::stringstream` could be more efficient for tokenization:

```cpp
#include <sstream>
stringstream ss(str);
while (std::getline(ss, token, '/')) {
    // No '/', we get token directly
}
```

std::find_if(a, b, pred)

std::binary_search(vec.begin(), vec.end(), val) (For sorted data)

Equate

std::equal(sub.begin(), sub.end(), it)

std::search() for subsequence matching.

std::stack

std::stack is simply an adapter for std::deque and std::vector

1
2
3
4
5
stack<int> sta;
sta.top();
sta.pop();
sta.empty();
sta.push();

• stack can be iterated over as well. So iterating over a stack will guarantee insertion order using std::stack().size()

• Previous
  Robotics - [2D SLAM 1] Hands-On Mapping
• Next
  Virtual Network Computing (VNC)