Solution for The Cutting Complexity Challenge

Since the contest is over(seems I have a chance to get an ASML T-Shirt), the solution can be posted now.

Scarily, it takes me time to understand my own code when reviewing it.

https://app.codility.com/cert/view/certC5DTD8-E4TCUGZC2GSJYSWT/
https://app.codility.com/cert/view/certC5DTD8-E4TCUGZC2GSJYSWT/details/

Solution For Codility Cobaltum 2018

IncreasingSequences

Given two sequences of integers, count the minimum number of swaps (A[k], B[k]) needed to make both sequences increasing.

You have two sequences A and B consisting of integers, both of length N, and you would like them to be (strictly) increasing, i.e. for each K (0 ≤ K < N − 1), A[K] < A[K + 1] and B[K] < B[K + 1]. Thus, you need to modify the sequences, but the only manipulation you can perform is to swap an arbitrary element in sequence A with the corresponding element in sequence B. That is, both elements to be exchanged must occupy the same index position within each sequence.

For example, given A = [5, 3, 7, 7, 10] and B = [1, 6, 6, 9, 9], you can swap elements at positions 1 and 3, obtaining A = [5, 6, 7, 9, 10], B = [1, 3, 6, 7, 9].

Your goal is make both sequences increasing, using the smallest number of moves.

Write a function:

class Solution { public int solution(int[] A, int[] B); }

that, given two arrays A, B of length N, containing integers, returns the minimum number of swapping operations required to make the given arrays increasing. If it is impossible to achieve the goal, return −1.

For example, given:

A[0] = 5 B[0] = 1 A[1] = 3 B[1] = 6 A[2] = 7 B[2] = 6 A[3] = 7 B[3] = 9 A[4] = 10 B[4] = 9

your function should return 2, as explained above.

Given:

A[0] = 5 B[0] = 2 A[1] = -3 B[1] = 6 A[2] = 6 B[2] = -5 A[3] = 4 B[3] = 1 A[4] = 8 B[4] = 0

your function should return −1, since you cannot perform operations that would make the sequences become increasing.

Given:

A[0] = 1 B[0] = -2 A[1] = 5 B[1] = 0 A[2] = 6 B[2] = 2

your function should return 0, since the sequences are already increasing.

Assume that:

• N is an integer within the range [2..100,000];
• each element of arrays A, B is an integer within the range [−1,000,000,000..1,000,000,000];
• A and B have equal lengths.

Complexity:

• expected worst-case time complexity is O(N);
• expected worst-case space complexity is O(N) (not counting the storage required for input arguments).

Solution

This is actually same as LeetCode 801. Minimum Swaps To Make Sequences Increasing. Frankly, the medium difficulty challenge is a hard one to me. I treat the ones who did this in half hour genius if they never saw it before.

The only difference this one added is to return -1 if the two lists can not be made increasing.

public class Solution {
    public int minSwapPossibleFailure(int[] A, int[] B) {
        int swapRecord = 1, noswapRecord = 0;
        for (int i = 1; i < A.length; i++) {
            //A[i] and B[i] are out of order and they can not swap            if(A[i]<=A[i-1]&&A[i]<=B[i-1]||B[i]<=B[i-1]&&B[i]<=A[i-1]){
                return -1;
            }
            else if (A[i - 1] >= B[i] || B[i - 1] >= A[i]) {
                // In this case, the ith manipulation should be same as the i-1th manipulation                // fixRecord = fixRecord;                swapRecord++;
            } else if (A[i - 1] >= A[i] || B[i - 1] >= B[i]) {
                // In this case, the ith manipulation should be the opposite of the i-1th manipulation                int temp = swapRecord;
                swapRecord = noswapRecord + 1;
                noswapRecord = temp;
            } else {
                // Either swap or fix is OK. Let's keep the minimum one                int min = Math.min(swapRecord, noswapRecord);
                swapRecord = min + 1;
                noswapRecord = min;
            }
        }
        return Math.min(swapRecord, noswapRecord);
    }
}

Two Codility Golden Awards In A Row

The current one is hard. I will not include link to certificate since the challenge is not completed yet and solution can be viewed from link in the certificate.

The previous one is easier. Challenge and solution can be viewed by link in certificate.
https://app.codility.com/cert/view/certQ65CZN-VDK7QY36D8EJ7R7B/

Delete Healthy Recovery Partition on Windows 10

I wanted to expand a disk partition, but the free space was blocked by a small Healthy recovery partition, which could not be deleted by graphical Disk Management utility. A few search reveals diskpart Windows utility is a rescuer.

This is a link to original post. Below is a reference for my future use.

1. Open a command prompt as administrator.

2. Run Diskpart application by typing diskpart in the command prompt.

3. In the “diskpart” prompt, enter rescan command and press Enter key to re-scan all partitions, volumes and drives available.

4. Then type in list disk and press Enter key to show all hard disk drive available.

5. Select the disk that contains the partition you want to remove. Normally, with just 1 hard disk, it will be disk 0. So the command will be:

Select disk 0

Finish by Enter key.

6. Type list partition and press Enter key to show all available and created partition in the disk selected.

7. Select the partition that wanted to be deleted by using the following command, followed by Enter key:

Select partition x

Where x is the number of the recovery partition to be removed and unlocked its space. Be careful with the number of this partition, as wrong number may get data wipes off.

8. Finally, type in delete partition override and press Enter key.

Shell: Check if symbolic link

This function checks if given path has symbolic link within it.

checkSymbolicLink()
{
    if [ ! -d $1 ]; then
        return 1
    fi
    pushd $1 1>/dev/null
    cdir=$(pwd)
    while [ $cdir != '/' ]
    do
        if [ -h $cdir ]
        then
            return 0
        fi
        cd .. 1>/dev/null
        cdir=$(pwd)
    done
    popd 1>/dev/null
    return 1
}

To get real path, whether the path is real of symbolic, use realpath command.

A Note on .ssh folder

When I made a not wise decision to change /root and its content as fully accessible to other users while still logging in as root user, the other users were refused to log in as root through ssh. They could log in back after I revoked the write permission on /root folder.

Checking the /var/log/secure, it said
xx sshd[xxx]: Authentication refused: bad ownership or modes for directory /root

Based on this, further google search reveals .ssh folder does not like to be writable by group users.

Here is a suggestion to .ssh folder to make sure the access to it is mostly limited to owner itself:

chmod 700 ~/.ssh
chmod 600 ~/.ssh/authorized_keys

Amazon's solutions to What I've being doing

Green grass is what Predix.io has been doing, edge to cloud, digital twin etc.
http://www.allthingsdistributed.com/2017/06/unlocking-value-device-data-aws-greengrass.html

Glue is my work of data management workbench in Bitstew.
http://docs.aws.amazon.com/glue/latest/dg/what-is-glue.html

It's a little scary when I first learned this. They are so similar and Amazon is so influential and I worried they will surpass us. 

At the end of day, I convinced myself that at least what I have been doing is cutting edge technologies and I want to do harder to make it better than Amazon's.