Finding substrings

Feature

substring can be thought as a feature, this kind of question is asking for find that feature in a string.

Not order related
https://www.lintcode.com/problem/minimum-window-substring/description
https://www.lintcode.com/submission/17057235/

It asks to find a shorted substring that contains all characters in target string. Here the feature is the counts of characters in target string, since order does not matter.

To solve this kind of problem, you will need two piece of data:
1. the feature, a statistics of characters in target string. it is counting in this problem
counters can be a hashmap or int array if character set is small and known.
2. a number that denotes if all unique characters has been processed. Every time when there is a match on a character's count, increase unique number count. When the total unique character counts are equal, it finds one window.

Algorithm:
1. calculate feature
2.check feature in string.
    2.1. To find feature string in a string, consider to use two pointers, Fix left position the first, run the right pointer to find a substring that covers the feature.
    2.2 when a substring containing the feature was found, change window by advance the left pointer
    2.3 track the shortest substring that has the feature
    2.4 continue 2.1 to find next substring that covers the feature

Some Keywords to use in Resume

achieved acted adapted
addressed adjusted administered
advised altered analyzed
arranged assembled assessed
audited balanced broadened
budgeted built calculated
calibrated catalogued categorized
chaired changed charted
checked classified coached
collated collected combined
communicated compared compiled
completed composed computed
conceived concluded conducted
configured considered consolidated
constructed contracted contrasted
controlled converted coordinated
corrected corresponded counseled
created critiqued cultivated
cut decided decreased
defined delegated delivered
demonstrated described designed
detected determined developed
devised diagnosed differentiated

directed discovered dispensed
displayed dissected distributed
diverted documented doubled
drafted drew edited
eliminated empathized encouraged
enforced enhanced enlarged
ensured established estimated
evaluated examined expanded
expedited explained expressed
extracted facilitated filed
finalized financed fixed
followed forecasted formulated
founded gathered gave
generated guided hired
hosted identified illustrated
implemented improved improvised
incorporated increased informed
initiated inspected installed
instituted instructed integrated
interacted interpreted interviewed
introduced invented investigated
itemized judged launched
learned lectured led
liaised listed located
maintained managed marked
marketed measured mediated
met minimized modeled
moderated modernized modified
monitored motivated narrated
navigated negotiated observed
obtained opened operated
ordered organized oriented
originated oversaw painted
patterned performed persuaded
photographed piloted planned
predicted prepared prescribed
presented printed processed
produced programmed projected
promoted proofread proposed
protected provided publicized
published purchased raised
received recommended reconciled
recorded recruited redesigned
reduced referred refined
rehabilitated related rendered
reorganized repaired reported
represented researched resolved
responded restored restructured
retrieved reviewed revised
revitalized saved scheduled
searched secured selected
separated served serviced
set sewed shaped
shared showed simplified
sized sketched sold
solved sorted specified
spliced split spoke
started streamlined strengthened
studied summarized supervised
supplied talked taught

tended tested traced
trained transcribed transformed
translated traveled treated
trimmed troubleshot tutored
uncovered unified updated
upgraded used utilized
verified weighed welded
widened wired won
wrote

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