ARTS-Week1

Algorithm

Problem

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8 Explanation: 342 + 465 = 807.

Thought

At the first glance, I thought that I could use divide and conquer method to solve it, but I got stucked in it.

Later on, I tried to use a simple method quite similar to our way to add two numbers, and it works well.

After I have submit my first version using above method, I analysed it with divide and conquer, and I finnally reach a point that this problem cannot be optimized through it because we cannot divide it to sub problems which can be merged with less complexity.

Method

Result link is pasted here

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int digit = 0, carry = 0;
        ListNode* result, *pre, *po;
        while(l1 != NULL || l2 != NULL)
        {
            int d1 = 0, d2 = 0;
            if(l1)
            {
                d1 = l1->val;
            }
            
            if(l2)
            {
                d2 = l2->val;
            }
            
            int out_d = (d1 + d2 + carry);
            carry = out_d / 10;
            out_d %= 10;
            
            if(digit == 0)
            {
                result = new ListNode(out_d);
                pre = result;
            }
            else
            {
                po = new ListNode(out_d);
                pre->next = po;
                pre = po;
            }
            
            if(l1)
            {
                l1 = l1->next;
            }
            if(l2)
            {
                l2 = l2->next;
            }
            
            digit++;
        }
        
        if(carry)
        {
            po = new ListNode(carry);
            pre->next = po;
        }
        
        return result;
    }
};

Review

Semantic Versioning 2.0.0 is a official guideline on how to manage software versions through project management. It is authored by Tom Preston-Werner, inventor of Gravatars and cofounder of GitHub.

The guide starts with introducing a concept called “dependency hell” which may cause many pain to your daily R&D work. And then it bring in a system thought named as “Semantic Versioning” which will guide you through version update.

I will extract some useful tips below:

1. It uses three level version method: MAJOR.MINOR.PATCH
2. Software using Semantic Versioning MUST declare a public API, and it is your responsibility as a professional developer to properly document software that is intended for use by others.
3. Major version zero (0.y.z) is for initial development
4. Patch version Z (x.y.Z, x > 0) MUST be incremented if only backwards compatible bug fixes are introduced.
5. Minor version Y (x.Y.z, x > 0) MUST be incremented if new, backwards compatible functionality is introduced to the public API
6. Major version X (X.y.z, X > 0) MUST be incremented if any backwards incompatible changes are introduced to the public API.

Tip

If you always operate with terminal, you may find it full of pain when switching between many directories because you have to input the directory’s full path through multi tab complete.

Today I will recommend z to you which can help you cut the pain.

z, is a light-weight command-line tool to manage your local direcotries according to access frequency.

After a short learning phase, z will take you to the most ‘frecent’ directory that matches ALL of the regexes given on the command line, in order.

For example, z foo bar would match /foo/bar but not /bar/foo.

I have made a demo record here, for your reference:

Share

10 Common Software Architectural Patterns in a nutshell

No matter you are a software programmer or architect, it’s important to have some basic knowledge on common software architectures.

This article shows a top-down view about 10 common architecutural patterns, and it may help.

Good luck!