Resolve “Runtime Error” problem when hackinging in hackerrank

A few days ago, I was trying to resolve the classic maximum subarray conundrum in hackerrankand bumped into an interesting issue. When I submitted the solution, one testcase would fail. But if I ran the testcase individually, the result is right. After discussing in the IRC and Support, it seems the code didn’t pass some memory/time limit constraint in the environment, so I began to optimize my code.

My initial Go code is like this:

package main
import "fmt"
import "math"
import "os"

func MaxNonConArray(s []int) int {
    var max int

    if len(s) < 1 {
        return 0
    }

    for _, v := range s {
        if v > 0 {
            max += v
        }
    }

    if max == 0 {
        max = s[0]
        for _, v := range s[1:] {
            if v > max {
                max = v
            }
        } 
    }
    return max
}

func MaxConArray(s []int) int {
    var max int

    if len(s) > 0 {
        max = s[0]
        currMax := s[0]
        for _, v := range s[1:] {
            currMax = int(math.Max(float64(currMax+v), float64(v)))
            max = int(math.Max(float64(currMax), float64(max)))
        }
    }
    return max
}


func main() {
 //Enter your code here. Read input from STDIN. Print output to STDOUT
    num := 0
    s := [][]int(nil)

    _, err := fmt.Scanf("%d", &num)
    if err != nil {
        os.Exit(1)
    }

    s = make([][]int, num)
    for i := 0; i < len(s); i++ {
        n := 0
        _, err := fmt.Scanf("%d", &n)
        if err != nil {
            os.Exit(1)
        }

        s[i] = make([]int, n)
        for j := 0; j < n; j++ {
            _, err := fmt.Scanf("%d", &s[i][j])
            if err != nil {
                os.Exit(1)
            }
        }
    }

    for i := 0; i < len(s); i++ {
        fmt.Println(MaxConArray(s[i]), MaxNonConArray(s[i]))
    }
}

The main function would allocate a two-dimension slice to accommodate all the input elements. Suddenly I realized a one-dimension slice should be enough, and it could be reused after the wanted value was calculated. So the main code was changed like this:

func main() {
    //Enter your code here. Read input from STDIN. Print output to STDOUT
    var num int

    _, err := fmt.Scanf("%d", &num)
    if err != nil {
        os.Exit(1)
    }

    for i := 0; i < num; i++ {
        var n int
        _, err := fmt.Scanf("%d", &n)
        if err != nil {
            os.Exit(1)
        }

        s := make([]int, n)
        for j := 0; j < n; j++ {
            _, err := fmt.Scanf("%d", &s[j])
            if err != nil {
                os.Exit(1)
            }
        }
        fmt.Println(MaxConArray(s), MaxNonConArray(s))
    }
}

Unfortunately, this time the testcase still can’t pass. So I resorted to C programming language:

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int maxNonConSubArray(int *array, int n) {
    int max = 0;

    if (n > 0) {
        for (int i = 0; i < n; i++) {
            if (array[i] > 0) {
                max += array[i];
            }
        }

        if (max == 0) {
            max = array[0];
            for (int i = 1; i < n; i++) {
                if (array[i] > max) {
                    max = array[i];
                }
            }
        }
    }

    return max;
}

int MaxConSubArray(int *array, int n) {
    int max = 0, currMax = 0;

    if (n > 0) {
        max = currMax = array[0];
        for (int i = 1; i < n; i++) {
            currMax = (currMax + array[i]) > array[i] ? (currMax + array[i]) : array[i];
            max = max > currMax ? max : currMax;
        }
    }
    return max;
}

int main() {
    int num = 0;
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    if (scanf("%d", &num) != 1) {
        return 1;
    }

    for (int i = 0; i < num; i++) {
        int n = 0, *array = NULL;

        if (scanf("%d", &n) != 1) {
            return 1;
        }

        array = calloc(n, sizeof(int));
        if (array == NULL) {
            return 1;
        }
        for (int j = 0; j < n; j++) {
            if (scanf("%d", array + j) != 1) {
                return 1;
            }
        }
        printf("%d %d\n",MaxConSubArray(array, n), maxNonConSubArray(array, n));
        free(array);
    }
    return 0;
}

In the C code, I need to manage memory manually, and this time, the testcase didn’t complain, and the submission was success.

How to maintain a software project?

For a software engineer, at least from my own experience, maintaining an existing software project would take up a considerable amount of time: adding new features, fixing tricky bugs, and so on. In this post, I will share some some tips about how to become a veteran from a novice quickly when facing a new project.

(1) Get familiar with the background knowledge of the project.

Every software has its own purposes and users: a device driver serves the specified hardware, whilst a SMS gateway helps routing the messages all over the world. So before delving into the code, you should get an overview of these background information. You need not to be an expert now, but at least have a sketch in your brain. Then when you meet a problem in your later work, you can know which part of knowledge you should enrich.

(2) Study the architecture of the project.

The correct method of studying a software is knowing its architecture first: Is it one-process or multiple-process? How many modules is it divided into? Does it provide some fundamental components? such as creating threads, allocating memory, etc. This step not only keeps you from losing the forest for the trees, but also gives you more confidence since it avoids you trap into the messy code at the beginning.

(3) Master the module which has the highest priority.

Since you have got the enough knowledge of project, it’s time to dig into the details of the required modules now. You should begin with the highest priority, for example, which one is frequently reported bugs, or which one is suggested to refactor. During this stage, you should try to utilize all the resources which can give a hand: previous maintainer, the QA engineers who test this software, the project manager, etc. As you become more versed in the code, you will also get a better understanding of the related business.

Good luck!

git rollback operations cheatsheet

Operation objects Git operations
Untracked files git clean -f: Remove all untracked files
Tracked but not committed files git reset –hard: Rollback the tracked files to last committed status
committed-ID git reset –hard committed-ID: Rollback the repository to the specified committed-ID status

Append slice puzzle

This puzzle comes from go-traps.appspot.com:

package main

import "fmt"

func main() {
    a := make([]int, 3, 4)
    a[0], a[1], a[2] = 0, 1, 2

    b := append(a, 66)
    b[0] = 6
    c := append(a, 77)
    c[0] = 7
    d := append(a, 88, 99)
    d[0] = 9

    fmt.Println(a)
    fmt.Println(b)
    fmt.Println(c)
    fmt.Println(d)
}

I think this is a good tutorial to explain the nitty-gritty behind the slice in Go, so I will analyze this issue detailedly. But before our journey, let’s get into some preliminaries of slice first:

The internals of a slice is like the following diagram:

1

A slice consists of 3 components:
a) ptr: A pointer which points to the start position of slice in the underlying array;
b) len (also known as length, and its type is int): the number of the valid elements of the slice;
b) cap (also known as capacity, and its type is int): the total number of slots of the slice.

Now that we have known the construction of the slice, we can explain the problem step by step:
(1)

a := make([]int, 3, 4)
a[0], a[1], a[2] = 0, 1, 2

The above statements are very general. Now the a slice is as follows:

2

(2)

b := append(a, 66)

Since the capacity of a is 4, and the length of a is 3, so a has a free slot for storing the new element: 66. Besides this, the operation of “append(a, 66)” assigns to a new variable: b, so the value of a doesn’t change: len is still 3; cap is still 4; ptr still points the original array, but the content of original array is modified: the 4th element is 66 now. Because b is the assignee of “append(a, 66)“, it points to the same underlying array of a, but The len of b is 4:

3

After running “b[0] = 6“, now the memory layout is like this:

4

(3)

c := append(a, 77)
c[0] = 7

Since the len of a is 3 up to this time, the program will consider there is an available slot. The result is the 4th element in the array will be changed to 77 from 66. “c[0] = 7” will modify the 1st element. Now the ptrs of a, b and c all point to the same array:

5

(4)

d := append(a, 88, 99)
d[0] = 9

Since a only has 1 accessible slot, “append(a, 88, 99)” will relocating a new array (the size will be doubled to be be more efficient, that is from 4 to 8 in this case.). So now the ptr of d points to a new array, and the final result should be here:

6

To wrap out this discussion, I want to quote the following statement from go-traps.appspot.com:

A good rule of thumb for non-specialists would be “never call append without assigning back to the same variable”.

So if you really need using append but without assigning back the original value, please be more careful, or else it may bite you and give you a big unpleasant surprise!

Why do I need a debugger?

When I begin to learn a new programming language, I will try and master the debugger for it as early as possible. For example, in 2013, while I touched the Go, there seems only gdb for use. Although gdb itself is not a good choice (From Debugging Go Code with GDB):

As a consequence, although GDB can be useful in some situations, it is not a reliable debugger for Go programs, particularly heavily concurrent ones.

But at that time there was no other choice. So after delve came out, I switched to it without hesitation. Though I am not an expert of delvecode, I still try my best do some contributions to make delve become better: improve documents, report issues, etc. Why am I so keen on debugger? The answer is it is a really irreplaceable and necessary tool for software engineers. The reasons are as follows:

(1) If the print statements are the only debugging method of a programming language, it will make feel upset. I.e., if a bug is fully reproduceable, but from the logs you can’t figure out the reason. If there is a debugger which can help you step into every statement and inspect value of every variable, I think you can get the root cause quickly.

Certainly, the debugger isn’t omnipotent. E.g., the nasty multi-threads bug (If you are interested in this topic, you can read this post which describes an experience I have undergone.). If you can’t find reproduce condition of this issue, and adding logs still fails, you can try to add some assert statements which are triggered when the issue happens again. Then you can get the core dump file which records the scene of crime, and use debugger to analyze it. You can see the debugger plays an important part in this scenario yet.

(2) “Debugger is a perfect unit-test tool”, the words come form my director when I got my first full-time job after leaving school. The reason is when you finish a code segment, you can use debugger to check whether it is correct through step-in mode: check value of every variable, mock the conditions which can’t easily be constructed in black-box test, inspect the stack and registers, etc. By means of this, you can fix many corner bugs.

(3) Debugger is a good tool to help you understand code. When I dive into some big Go projects, I find so many channels, interfaces, goroutines, and they sometimes make me crazy. But by way of using debugger, I can set breakpoints, then once the program is stopped, I can understand the code logic better through watching the calling stack.

Based on the above, debugger is an invaluable tool for everyone who lives on writing code. Try know and master it better. Maybe one day, a colleague can’t find reasons for one bug, then you use a small debugger trick and spot the root cause immediately. Isn’t it a cool stuff? 🙂