2020-05-29

Rain

The rain is raining all around,
It falls on field and tree,
It rains on the umbrellas here,
And on the ships at sea.

2020-05-23

Gauss's algorithm and Chinese remainder theorem

$
\begin{align*}
\begin{cases}
x \equiv 2 \hspace{2mm} (mod \hspace{1mm} 3) \hspace{8mm} 2,5,8,11,14,17,20,\textbf{23},\cdots \\
x \equiv 3 \hspace{2mm} (mod \hspace{1mm} 5) \hspace{8mm} 3,8,13,18,\textbf{23},28,\cdots \\
x \equiv 2 \hspace{2mm} (mod \hspace{1mm} 7) \hspace{8mm} 2,9,16,\textbf{23},30,\cdots
\end{cases}
\end{align*}
$

$ n_1=3, n_2=5, n_3=7 $
$ N = n_1 \times n_2 \times n_3 = 3 \times 5 \times 7 = 105 $
$ a_1=2, a_2=3, a_3=2. $

Now $ N_1 = \frac{N}{n_1} = 35 $ and so $d_1 \equiv 35^{-1} \hspace{2mm} (mod \hspace{1mm} 3) = 2 $,
$ N_2 = \frac{N}{n_2} = 21 $ and so $d_2 \equiv 21^{-1} \hspace{2mm} (mod \hspace{1mm} 5) = 1 $, and
$ N_3 = \frac{N}{n_3} = 15 $ and so $d_3 \equiv 15^{-1} \hspace{2mm} (mod \hspace{1mm} 7) = 1 $. Hence

$ x \equiv (2 \times 35 \times 2) + (3 \times 21 \times 1) + (2 \times 15 \times 1) = 233 ≡ 23 \hspace{2mm} (mod \hspace{1mm} 105) $

The Chinese Remainder Theorem

If the $n_i$ are pairwise coprime, and if $a_1, …, a_k$ are any integers

$
\begin{align}
x \equiv a_1 \hspace{2mm} (mod \hspace{1mm} n_1) \\
x \equiv a_2 \hspace{2mm} (mod \hspace{1mm} n_2) \\
x \equiv a_3 \hspace{2mm} (mod \hspace{1mm} n_3) \\
\vdots \\
x \equiv a_k \hspace{2mm} (mod \hspace{1mm} n_k)
\end{align}
$

has a simultaneous solution which is unique modulo $n_1n_2⋯n_k$.

Gauss’s algorithm

Let $N = \prod_{i=1}^k n_i $ then
$x ≡ \sum_{i=1}^k a_iN_id_i \hspace{2mm} (mod \hspace{1mm} N)$

where $N_i = N/n_i$ and $d_i ≡ N_i^{-1} \hspace{2mm} (mod \hspace{1mm} n_i).$

The latter modular inverse $d_i$ is easily calculated by the extended Euclidean algorithm.

Resources

The Chinese Remainder Theorem

2020-05-22

HackerRank - Regex - Repetitions

Matching {x} Repetitions

The tool {x} will match exactly x repetitions of character/character class/groups.

For Example

w{3} : It will match the character w exactly 3 times.
[xyz]{5} : It will match the string of length 5 consisting of characters {x, y, z}. For example it will match xxxxx, xxxyy and xyxyz.
\d{4} : It will match any digit exactly 4 times.

Task

2222222222aaaaaaaaaa2222222222aaaaaaaaaa13 57

1	^[a-zA-Z02468]{40}[13579\s]{5}$

Matching {x, y} Repetitions

The {x,y} tool will match between x and y (both inclusive) repetitions of character/character class/group.

For Example

w{3,5} : It will match the character w 3, 4 or 5 times.
[xyz]{5,} : It will match the character x, y or z 5 or more times.
\d{1, 4} : It will match any digits 1, 2, 3, or 4 times.

Task

3threeormorealphabets.

1	^\d{1,2}[a-zA-Z]{3,}\.{0,3}$

Matching Zero Or More Repetitions

The * tool will match zero or more repetitions of character/character class/group.

For Example

w* : It will match the character w 0 or more times.
[xyz]* : It will match the characters x, y or z 0 or more times.
\d* : It will match any digit 0 or more times.

Task

14

1	^\d{2,}[a-z][A-Z]$

Matching One Or More Repetitions

The + tool will match one or more repetitions of character/character class/group.

For Example

w+ : It will match the character w 1 or more times.
[xyz]+ : It will match the character x, y or z 1 or more times.
\d+ : It will match any digit 1 or more times.

Task

1Qa

1	^\d+[A-Z]+[a-z]+$

Matching Ending Items

The $ boundary matcher matches an occurrence of a character/character class/group at the end of a line.

Task

Kites

1	^[a-zA-Z]*s$

Resources

Regex - Subdomains - Repetitions

2020-05-17

LeetCode - Algorithms - 34. Find First and Last Position of Element in Sorted Array

Problem

34. Find First and Last Position of Element in Sorted Array

Java

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int lo = 0;
        int hi = nums.length - 1;
        while (lo<=hi) {
            int mid = lo + (hi - lo) / 2;
            if (target < nums[mid])
                hi = mid-1;
            else if (target > nums[mid])
                lo = mid+1;
            else {
                int startPos = mid;
                int endPos = mid;
                while(startPos>=0 && nums[startPos]==nums[mid]) startPos--;
                while(endPos<=nums.length - 1 && nums[endPos]==nums[mid]) endPos++;
                int[] r = new int[2];
                r[0] = startPos+1;
                r[1] = endPos-1;
                return r;
            }
        }

        int[] r = {-1, -1};
        return r;       
    }
}

Submission Detail

88 / 88 test cases passed.
Runtime: 0 ms, faster than 100.00% of Java online submissions for Find First and Last Position of Element in Sorted Array.
Memory Usage: 44.5 MB, less than 6.38% of Java online submissions for Find First and Last Position of Element in Sorted Array.

JavaScript

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function(nums, target) {
    var lo = 0, hi = nums.length-1;
    while (lo<=hi) {
        var mid = lo + Math.floor((hi-lo)/2);
        if (target < nums[mid])
            hi = mid-1;
        else if (target > nums[mid])
            lo = mid+1;
        else {
            var startPos = mid, endPos = mid;
            while(startPos>=0 && nums[startPos]==nums[mid]) startPos--;
            while(endPos<=nums.length - 1 && nums[endPos]==nums[mid]) endPos++;
            return [startPos+1, endPos-1];
        }
    }

    return [-1, -1];    
};

Submission Detail

88 / 88 test cases passed.
Runtime: 92 ms, faster than 7.49% of JavaScript online submissions for Find First and Last Position of Element in Sorted Array.
Memory Usage: 34.9 MB, less than 100.00% of JavaScript online submissions for Find First and Last Position of Element in Sorted Array.

2020-05-16

LeetCode - Algorithms - 205. Isomorphic Strings

Problem

205. Isomorphic Strings

Java

class Solution {
    public boolean isIsomorphic(String s, String t) {
        boolean r = true;
        Map<Character,Character> map = new HashMap<Character, Character>();
        Map<Character,Character> map2 = new HashMap<Character, Character>();
        for(int i=0; i<s.length(); i++) {
            char k = s.charAt(i);
            char x = t.charAt(i);
            if (map.containsKey(k)) {
                char v = map.get(k);
                if (x!=v) {
                    return false;
                }
            }
            else {
                map.put(k,x);
            }
            if (map2.containsKey(x)) {
                char v = map2.get(x);
                if (k!=v) {
                    return false;
                }
            }
            else {
                map2.put(x, k);
            }
        }
        return r;        
    }
}

Submission Detail

32 / 32 test cases passed.
Runtime: 12 ms, faster than 26.96% of Java online submissions for Isomorphic Strings.
Memory Usage: 39.6 MB, less than 6.14% of Java online submissions for Isomorphic Strings.

2020-05-15

How to Read Code

How to read other people’s code? You will need good code-browsing skills to make sense of the code.

Start by gathering information about which problems the program should solve and which code style to adapt.

Don’t spend all your time figuring out how everything works at the beginning. Narrow things down to something you can actually process.

Step through behavior that concerns you with a debugger. The stack trace have a lot of information about how events are propogated in the application.

In Action

getting it into a “smart” IDE that can make sense of it

try to build and run it (preferably in a debugger)

Find Main, Reading “main”

Learn to Dig

git blame

You can use git blame on a file to get an author name, last modified date, and commit hash for every single line.

git log

Use git log to look at the commit history of the overall repo.

git log can also show you the history of a single file with the -p flag: git log -p index.js.

breakpoint

One method the community strongly suggests is to set out breakpoint on methods that triggers behaviours that concerns you. If changing a line of code causes unexpected changes on other places, put a breakpoint on that line, and see what happens. You have a lot of information on the runtime state once the breakpoint hits. Breakpoints stops the execution of the code on a certain line, and from there, you can see from the stacktrace how the code got there. Use the step into and step out functions to see what the different methods does and how events are propogated in the application. This will teach you something about the structure of the codebase.

Grepping

the search function in your IDE

Search for Key Words

Use your editor’s Find feature (or grep) to search the entire source tree for occurrences of words associated with what you want to know. For example, if you want to figure out how/where the program opens files, search for “open” or “file”. You may get zillions of hits, but that’s not a bad thing–a focused reading of the code will result.
Often-useful words for C/C++ programs are “main”, “abort”, “exit”, “catch”, “throw”, “fopen”, “creat”, “signal”, “alarm”, “socket”, “fork”, “select”. Other words are useful in other languages.

Code Review

Software development is a very collaborative work. No one can build a large or a significant software alone. Every software is built in a team. In a team, everyone contributes to shaping a project. End of the day, everyone’s contribution get merged and become a good piece of work which has a real value to the customers.

Besides doing the actual coding, there is another practice that every team these days does, which is, review each other’s code making observations, suggestions and learning from one other. This is a powerful tool for building knowledge of a code base, creating strong bonds in a team and improving code quality that leads to fewer bugs in the system, and happy customers.

Doing code review, you are forced to read someone else’s code in your team which ends up improving your code reading skill.

Things to Remember

Go Back in Time

Read the Specs

Think of Comments as Hints

Commenting your code is incredibly important, for yourself and for your peers reviewing your code.

Notice Style

Expect to Find Garbage

Don’t Get Lost

Where is this button?
What do the tests do?
The graphical layout
Runtime Investigation

Find one thing you know the code does, and trace those actions backward, starting at the end.

Let’s call those connected pieces of code a “chain of actions.”

Following input events

Rinse and repeat.

a body of code is designed to tackle one (or more) complex problems.

the more you can gain an understanding of how different parts of the code are connected, the more you’ll develop an understanding of the entire codebase, as a whole.

the more (good) code you see, the easier it becomes to read and understand all code, and the faster you can do so.

“high quality examples of expertise” = good code

exposure to high quantity, high quality examples of expertise is one of the two main factors that dictate how quickly and effectively people learn new skills. – Badass: Making Users Awesome, Kathy Sierra

The more you watch (or listen) to expert examples, the better you can become. The less exposure you have to experts or results of expert work, the less likely you are to develop expert skills.

the longer you’re programming — and thus the more code samples you see, of all different kinds — the easier it gets to understand other people’s code. And the faster you’re able to do it.

Reading a class

Before reading the implementation of a class, however, I recommend you study its interface.

The public functions will most likely be the command interface for your class.

Retelling or Rubber Ducking

Use/know tools

There are plenty of tools out there for reading and exploring source code that can help to visualize code. For example – IntelliJIdea has really a great capability of navigating source code where you can search by words, part of a word or even abbreviation. You should learn the keyboard shortcuts as well. Navigating source code with the mouse can be pretty boring and slow where working with the keyboard shortcuts can be faster. You can jump from one part of the source code to another quickly.

There is another great software to read code, called Sourcegraph, which was created by two Stanford grads, Quinn Slack and Beyang Liu, who, after spending hours hunting through the poorly documented code, decided to build a tool to help them better reading and understanding the code.

Know the language/conventions

Read the best practices/design patterns

Temporary Refactoring

heuristics

Code is not like a novel

if you insist on understanding each and every thing before you understand the next, you will be lost for sure.

Let the machine help

Take the time to learn and use the stepper, trace, inspecting and browsing tools.

Many important relations in a program are non-sequential, and there are tools that will help you find what to look at next.

Start with an example

Don’t try to understand what all the code does at once. Instead, start with a specific example, representative of what a new user might try in his or her first session with the program, or an example from the manual primer.
Set yourself the task of learning just how that particular example works. Ignore everything else that doesn’t pertain to that example.

Go just as deep as you have to do to understand it, no deeper. Treat everything else as a black box. Learn about how it works later.

Become familiar with the user interface from a user’s perspective. For each user-visible action or object, ask: “Where is that implemented”?

Have a specific goal in mind when you work. Experiment with small changes and extensions to the code to test your understanding.

If it ain’t broke, fix it

The best attitude to take is to pretend you are debugging the code, even if there is nothing wrong with it. The same tools that are used for debugging the code will be helpful in getting you to understand it in the first place. Even if you aren’t looking for bugs now, if you plan on using, extending or modifying the code, you soon will be.

Tools

Jump to function definition
Step the code
Guess function names
Trace functions
Inspect the application’s data structures

RTFM

When all else fails, read the documentation.

Navigating a Web Page’s Source Code

another invaluable tool is stored inside your browser: the Developer tools. Knowing how to use the developer tools correctly and effectively can help you quickly locate the source of problems with styling these sections.

localized JavaScript console, where you can test out code separately from your programs.

Start with what you do know

find one thing you know the code does, and trace those actions backward, starting at the end.

Believe that you know what you’re looking at

For ultimately effective searching, you’ll want to use something like “language_name function_name” in your Google search, rather than just the function name, as they can be repetitive across multiple coding languages.

In the long run, expose yourself to high-quality code

By exposing yourself to well-written code made by experienced programmers, you are subconsciously taking in the methodology they follow, as well as their best practices.

If you read poorly-written, non-semantic code, you will likely emulate the same when writing your own. And yes, although we all start writing garbage code, our ultimate goal is to move on from that point as quickly as possible!

Try watching live-streamed programming (or pair programming with a peer)

it’s one of the best ways to watch the coding process from start to finish in real time, and ask questions as you encounter them. Watching other people program in real time also gives you insight into other people’s coding processes, and helps you develop good habits, regardless of whether or not they are a master themselves.

For an excellent resource on the front end (HTML, CSS, JavaScript), try perusing Codepen. Free, and very user-friendly, many front-end developers use this site as a sandbox.

On the back end, I recommend you sign up for GitHub and start digging into some of the most popular repositories. You can view a file from right within your browser, and if you wish to improve on the code, you can edit it in your own forked version and create a “pull request”. If the author likes your improvements, they may choose to implement them into their programs!

Find the high-level logic

Starting with the program’s entry point (e.g. main() in C/C++/Java), find out how the program initializes itself, does its thing, and then terminates.

Basically, skimmed through the whole project and gain a primary idea and then ask a question to yourself where do you want to focus, which part you want to read first.

Draw Some Flowcharts

Yes, we all know flowcharts are a horrible design tool, but they can be useful when analyzing program flow. You can’t keep all that information in your head, so draw some flowcharts or state diagrams while you are reading. Make sure you account for both sides of a two-way branch, and all branches of multi-way branches.

Examine Library Calls

Leverage the Power of Code Comprehension Tools

Some techniques available with a good text search tool, or better yet a tool that can analyze the source and find references and generate diagrams, allow the following questions to be answered, for object-oriented code:

Who calls this method?
Who implements this interface or subclasses this class?
What are this class’ superclasses?
Where are instances of this class created, held, and passed as arguments or returned?
What superclass methods does this class override?
Where might methods of this class be called polymorphically, i.e. through a base class or interface?

Print the code

developing a “big picture” view of the code

reading and writing tests

Although testing is rare, it acts as a wonderful documentation tool, and is a good introduction to a new codebase.

Comment the Code

One of the best ways of reverse-engineering code you’re so unfamiliar with that you cannot even guess to comment is to derive HoareTriples for the code under scrutiny, and to compute a procedure’s WeakestPrecondition. Knowing the invariants of a procedure often gives valuable clues as to its intended purpose, thus letting you derive understanding from the code in a way that merely guessing from reading a number of poorly named procedure names simply cannot. Using this technique, you might even find bugs in the code, despite your lack of understanding thereof (I know this from experience!).

Clean Up the Code

Use Aspect Browser

Aspect Browser is a tool for viewing cross-cutting code aspects in large amounts of code. I find it indispensable for navigating unfamiliar code, as a kind of super-grep.

AspectBrowser for Eclipse

Resources

2020-05-08

HackerRank - Regex - Character Class

Matching Specific Characters

The character class [ ] matches only one out of several characters placed inside the square brackets.

Task

1203x.

1	^[123][120][xs0][30Aa][xsu][\.\,]$

Excluding Specific Characters

The negated character class [^] matches any character that is not in the square brackets.

Task

think?

1	^[^\d][^aeiou][^bcDF][^\s][^AEIOU][^\.\,]$

Matching Character Ranges

In the context of a regular expression (RegEx), a character class is a set of characters enclosed within square brackets that allows you to match one character in the set.

A hyphen (-) inside a character class specifies a range of characters where the left and right operands are the respective lower and upper bounds of the range. For example:

[a-z] is the same as [abcdefghijklmnopqrstuvwxyz]
[A-Z] is the same as [ABCDEFGHIJKLMNOPQRSTUVWXYZ]
[0-9] is the same as [0123456789]

In addition, if you use a caret (^) as the first character inside a character class, it will match anything that is not in that range. For example, [^0-9] matches any character that is not a digit in the inclusive range from 0 to 9.

It’s important to note that, when used outside of (immediately preceding) a character or character class, the caret matches the first character in the string against that character or set of characters.

Task

h4CkR

1	^[a-z][1-9][^a-z][^A-Z][A-Z]*

Resources

Regex - Subdomains - Character Class

2020-05-07

If—

by Rudyard Kipling

If you can keep your head when all about you
Are losing theirs and blaming it on you;
If you can trust yourself when all men doubt you,
But make allowance for their doubting too;
If you can wait and not be tired by waiting,
Or, being lied about, don’t deal in lies,
Or being hated, don’t give way to hating,
And yet don’t look too good, nor talk too wise;

If you can dream—and not make dreams your master;
If you can think—and not make thoughts your aim;
If you can meet with Triumph and Disaster
And treat those two impostors just the same;
If you can bear to hear the truth you’ve spoken
Twisted by knaves to make a trap for fools,
Or watch the things you gave your life to, broken,
And stoop and build ’em up with worn-out tools;

If you can make one heap of all your winnings
And risk it on one turn of pitch-and-toss,
And lose, and start again at your beginnings
And never breathe a word about your loss;
If you can force your heart and nerve and sinew
To serve your turn long after they are gone,
And so hold on when there is nothing in you
Except the Will which says to them: “Hold on!”

If you can talk with crowds and keep your virtue,
Or walk with kings—nor lose the common touch,
If neither foes nor loving friends can hurt you,
If all men count with you, but none too much;
If you can fill the unforgiving minute
With sixty seconds’ worth of distance run,
Yours is the Earth and everything that’s in it,
And—which is more—you’ll be a Man, my son!

In a poll conducted in 1995 by the BBC Radio 4 Bookworm programme to determine the nation’s favourite poems, If— came first.
The poem If of Kipling is written as if a father is talking to his son, giving him advices on the way to behave to obtain the reputation of being a mature and an outstanding citizen of the community and the world. It has been written in 1895 and published in his collection Rewards and Fairies in 1909. Throughout the poem, Kipling illustrates ideal behaviour and virtue through the use of paradox: righteousness without smugness; detachment while practicing determination; and noble life blended with commonality. The employment of these contradictory extremes throughout the poem serves to illustrate a central theme of striving for an idealized “golden mean” in all facets of life.

Resources

2020-05-07

HackerRank - Regex - Introduction

Matching Anything But a Newline

The dot (.) matches anything (except for a newline).

Task

123.456.abc.def

1	^(.{3}\.){3}.{3}$

Matching Digits & Non-Digit Characters

\d

The expression \d matches any digit [0-9].

\D

The expression \D matches any character that is not a digit.

Task

06-11-2015

1	(\d){2}(\D){1}(\d){2}(\D){1}(\d){4}

Matching Whitespace & Non-Whitespace Character

\s

\s matches any whitespace character [ \r\n\t\f ].

\S

\S matches any non-white space character.

For Example

match blank line

\r\n

Task

12 11 15

1	(\S){2}(\s){1}(\S){2}(\s){1}(\S){2}

Matching Word & Non-Word Character

\w

The expression \w will match any word character.
Word characters include alphanumeric characters (a-z, A-Z and 0-9) and underscores (_).

\W

\W matches any non-word character.
Non-word characters include characters other than alphanumeric characters (a-z, A-Z and 0-9) and underscore (_).

Task

www.hackerrank.com

1	(\w){3}(\W){1}(\w){10}(\W){1}(\w){3}

Matching Start & End

^

The ^ symbol matches the position at the start of a string.

$

The $ symbol matches the position at the end of a string.

Task

0qwer.

1	^(\d){1}(\w){4}(\.){1}$

Resources

Regex - Subdomains - Introduction

2020-05-05

LeetCode - Algorithms - 128. Longest Consecutive Sequence

Hard problem. Exercise for union-find. Almost done by myself, with help of union-find by Robert Sedgewick and Kevin Wayne.

Problem

128. Longest Consecutive Sequence

Java

union–find

class Solution {
    public int longestConsecutive(int[] nums) {
        int[] arr = removeDuplicates(nums);
        int N = arr.length;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i=0; i<N; i++) {
            if (!map.containsKey(arr[i]-1)) map.put(arr[i]-1, i);
            if (!map.containsKey(arr[i]+1)) map.put(arr[i]+1, i);
        }
        int len = 0;
        UF uf = new UF(N);
        for(int i=0; i<N; i++) {
            if (map.containsKey(arr[i])) {
                uf.union(i, map.get(arr[i]));
            }
        }
        int[] parent = uf.parent();
        Map<Integer,Integer> tmpMap = new HashMap<Integer, Integer>();
        int k;
        for(int i=0; i<parent.length; i++) {
            k = parent[i];
            if (tmpMap.containsKey(parent[i]))
                tmpMap.put(k, tmpMap.get(k)+1);
            else
                tmpMap.put(k, 1);
        }
        for(Integer n : tmpMap.values()) {
            if (n>len)
                len = n;
        }

        return len;        
    }
    
    private int[] removeDuplicates(int[] input) {
        if (input == null || input.length <= 0) {
            return input;
        }
        Set<Integer> aSet = new HashSet<>(input.length);
        for (int i : input) {
            aSet.add(i);
        }
        int[] a = new int[aSet.size()];
        int i=0;
        for(Integer x : aSet)
            a[i++] = x;
        return a;
    }
}

/**
 * Weighted quick-union by rank with path compression by halving.
 * @author Robert Sedgewick
 * @author Kevin Wayne
 * Algorithms, 4th edition textbook code and libraries
 * https://github.com/kevin-wayne/algs4
 */
class UF {
    private int[] parent;
    private byte[] rank;
    private int count;

    public UF(int n) {
        if (n < 0) throw new IllegalArgumentException();
        count = n;
        parent = new int[n];
        rank = new byte[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }

    public int find(int p) {
        validate(p);
        while (p != parent[p]) {
            parent[p] = parent[parent[p]];
            p = parent[p];
        }
        return p;
    }

    public int count() {
        return count;
    }

    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ) return;

        if      (rank[rootP] < rank[rootQ]) parent[rootP] = rootQ;
        else if (rank[rootP] > rank[rootQ]) parent[rootQ] = rootP;
        else {
            parent[rootQ] = rootP;
            rank[rootP]++;
        }
        count--;
    }

    private void validate(int p) {
        int n = parent.length;
        if (p < 0 || p >= n) {
            throw new IllegalArgumentException("index " + p + " is not between 0 and " + (n-1));
        }
    }

    public int[] parent() {return parent;}
}

Submission Detail

68 / 68 test cases passed.
Runtime: 8 ms, faster than 23.72% of Java online submissions for Longest Consecutive Sequence.
Memory Usage: 40.8 MB, less than 8.62% of Java online submissions for Longest Consecutive Sequence.