ARTS-Week3

Algorithm

Problem

Leetcode #11: Container With Most Water

Given n non-negative integers a1, a2, …, an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Thought

At the first glance, I thought this problem has relation to longest non-repeating substring, and maybe we could solve it using the same method. If it’s true, the time complexity will be O(n) which is much better than the brute-force method.

Then, I tried to change this problem to iterate all the lines and find the container whoes right border is the new line and contains the most water.

However, I found that left border of the new container and previous container had no obvious relationship. It may be at any position, left or right to the previous left border, and it’s hard to judge with O(1) complexity.

So I finally quit.

Method

The hints of this problem woke me a lot. Area formed between the lines will always be limited by the height of the shorter line, and what’s more, the farther the lines, the more will be the area obtained.

We use two position index to indicate the left and right border of the container. The initial state is one at the beginning and the other end of the array. We try to find the container of most area through decreasing the width of the container step by step. After we have calculated the area of one container, the next possible one can be formed through moving the border with smaller value.

The following graph showes that if we move the border with larger value, the formed area will definitely decrease. So our strategy is to move the shorter line.

If you have already captured the theory in it, the code will be very simple.

class Solution {
public:
    int maxArea(vector<int>& height) {
        int max_area = 0, area = 0;
        int i = 0, j = height.size() - 1;
        while(i != j)
        {
            area = (j - i) * std::min(height[i], height[j]);
            max_area = std::max(max_area, area);
            
            if(height[i] < height[j])
            {
                i++;
            }
            else
            {
                j--;
            }
        }
        
        return max_area;
    }
};

Review

This review part is not about some techinal post, but an useful tool that I could not wait to recommend to you until the next time.

It’s really really useful, and you can find it here.

Extract the description of q here:

q allows performing SQL-like statements on tabular text data. Its purpose is to bring SQL expressive power to the Linux command line and to provide easy access to text as actual data.

So far, it only supports Python2, so please set default Python env to Python2, or replace the shebang line #!/usr/bin/env python with #!/usr/bin/env python2 till Python 3 compatibility is achieved. Reference to issue #172.

Let us see a simple example. Suppose that I have an IMU records file named imu.txt, and the record is saved in sequence form of timestamp [3-Axis gyro] [3-Axis accelerator]. Then I want to filter some of them with conditions, e.g., timestamp before 278.5s and gravity is lesser than -10.

Do you have any idea about how to do this? Yeah, you can use Excel or Numbers, and I believe you can. How about make it through q?

Look the sql code example:

q "SELECT * from imu.txt where c1 < 278.5 and c6 < -10" > imu_sql.txt

Then you get the filtered records as follows:

278.379 -0.006391999777 0.002130999928 -0.006391999777 -0.3038569987 -10.00097656 -0.07895500213
278.383 -0.006391999777 0.001597999944 -0.006391999777 -0.3014650047 -10.00097656 -0.09091799706
278.387 -0.006391999777 0.002130999928 -0.006391999777 -0.3038569987 -10.00097656 -0.09091799706
278.446 -0.006391999777 0.002130999928 -0.005859000143 -0.306250006 -10.00097656 -0.08134800196
278.462 -0.006391999777 0.002130999928 -0.005326000042 -0.3134280145 -10.00097656 -0.08134800196

Quite convenient is it. Even more, if there is column header row in the file, then you can write condition using column header, and the SQL code will be more readable.

Tip

Whenever you wanna explain something hard to others, you can add a case comics to describe it.

And I have made a simple demonstration about what is ARTS, and I think it’s quite fun.

Hope you will like it, and come on to make one yourself.

Make comix yourself.

Share

You may want to switch to management role after years of coding, and may definitely meet many troubles that never occur before. So this share will be an good introduction for you.

Engineering Management : Lessons learned in first year

The author listed many tips he learned during his first year of management, and many of them are reasonable.

I extract some here:

• This role is not about the tech. It is also about the tech. It is primarily about the people.
• Only 2 things matter : Results & Retention
• Always Be Learning, Trying, Reflecting

Wish you could fullfil your expectation in engineering management.