Wednesday, June 24, 2015

LeetCode: The Skyline Problem

Problem Description
A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skyline formed by these buildings collectively (Figure B).
Buildings Skyline Contour
The geometric information of each building is represented by a triplet of integers [Li, Ri, Hi], where Li and Ri are the x coordinates of the left and right edge of the ith building, respectively, and Hi is its height. It is guaranteed that 0 ≤ Li, Ri ≤ INT_MAX0 < Hi ≤ INT_MAX, and Ri - Li > 0. You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.
For instance, the dimensions of all buildings in Figure A are recorded as: [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] .
The output is a list of "key points" (red dots in Figure B) in the format of [ [x1,y1], [x2, y2], [x3, y3], ... ] that uniquely defines a skyline. A key point is the left endpoint of a horizontal line segment. Note that the last key point, where the rightmost building ends, is merely used to mark the termination of the skyline, and always has zero height. Also, the ground in between any two adjacent buildings should be considered part of the skyline contour.
For instance, the skyline in Figure B should be represented as:[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ].
Notes:
  • The number of buildings in any input list is guaranteed to be in the range [0, 10000].
  • The input list is already sorted in ascending order by the left x position Li.
  • The output list must be sorted by the x position.
  • There must be no consecutive horizontal lines of equal height in the output skyline. For instance, [...[2 3], [4 5], [7 5], [11 5], [12 7]...] is not acceptable; the three lines of height 5 should be merged into one in the final output as such: [...[2 3], [4 5], [12 7], ...]
Solution:


LeetCode: Insert Interval

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].
This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].
Solution: 
Below is a simple solution in Python:

# Definition for an interval.
# class Interval:
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution:

    def insert(self, intervals, newInterval):
        l = []
        count = 0
        while(count < len(intervals)):
            if(newInterval.start <= intervals[count].end):
                if(newInterval.end >= intervals[count].start):
                    newInterval.start = min(intervals[count].start, newInterval.start)
                break
            l.append(intervals[count])
            count += 1
        l.append(newInterval)
        while(count < len(intervals)):
            if(newInterval.end < intervals[count].start):
                break
            l[-1].end = max(intervals[count].end, l[-1].end)
            count += 1
        while(count < len(intervals)):
            l.append(intervals[count])
            count += 1
        return l

And here is a faster solution using binary search:
class Solution:  
  
    def insert(self, intervals, newInterval):  
        if len(intervals) == 0:  
            return [newInterval]  
              
        v1 = self.search(intervals, newInterval.start,0, len(intervals)-1, 0)  
        v2 = self.search(intervals, newInterval.end,(v1)>>1, len(intervals)-1, 1)  
   
        if (v1 & 1):  
            newInterval.start = intervals[v1>>1].start   
        if (v2 & 1):  
            newInterval.end = intervals[(v2)>>1].end 
                  
        return intervals[:(v1>>1)] + [newInterval] + intervals[(v2+1)>>1:] 
          
    def search(self, intervals, index, start=0, end=0, isStart=0):  
        while(start <= end):  
            middle = (end+start)>>1 
            if intervals[middle].start <= index and intervals[middle].end >= index:  
                return (middle << 1)+1 
            if intervals[middle].start > index:  
                end = middle - 1
            else:
                start = middle + 1       
        return start << 1

Third solution:
class Solution: 
  
    def insert(self, intervals, newInterval):
        s, e = newInterval.start, newInterval.end
        left = [i for i in intervals if i.end < s]
        right = [i for i in intervals if i.start > e]
        if left + right != intervals:
            s = min(s, intervals[len(left)].start)
            e = max(e, intervals[~len(right)].end)
        return left + [Interval(s, e)] + right

If you want to train the code reading skills, here is another approach in Java:
/**
 * Definition for an interval.
 **/
class Interval {
    int start;
    int end;
    Interval() { start = 0; end = 0; }
    Interval(int s, int e) { start = s; end = e; }
}

public class Solution {
    public List<Interval> insert(List<Interval> intervals, Interval newInterval){
        List<Interval> is = new ArrayList<Interval>();
        if(intervals == null || newInterval == null) return is;

        int status = 0;
        Interval open = null;
        for(Interval i: intervals){

            //if not found a interval containing the newInterval
            if(status==0){
                if(i.start > newInterval.end){
                    is.add(newInterval);
                    is.add(i);
                    status = 2;
                }else if(i.end < newInterval.start){
                    is.add(i);
                }else if(i.start<= newInterval.start && i.end < newInterval.end){
                    open = new Interval(i.start, newInterval.end);
                    status = 1;
                }else if(i.start > newInterval.start && i.end < newInterval.end){
                    status = 1;
                    open = new Interval(newInterval.start, newInterval.end);
                }else {
                    is.add(new Interval(Math.min(newInterval.start, i.start), i.end));
                    status = 2;
                }
            }else if(status == 1){
                if(i.start <= newInterval.end && i.end>= newInterval.end){
                    status = 2;
                    open.end = i.end;
                    is.add(open);
                }else if(i.start > newInterval.end){
                    status = 2;
                    open.end = newInterval.end;
                    is.add(open);
                    is.add(i);
                }                
            }else {   //status = 2
                is.add(i);
            }
        }

        if(status == 0) is.add(newInterval);
        if(status == 1){
            open.end = newInterval.end;
            is.add(open);
        }
        return is;
    }
}

Friday, June 19, 2015

Populating Next Right Pointers in Each Node

Problem Description: 
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
Initially, all next pointers are set to NULL . We also need to use constant space.
For example,
Given the following binary tree,
         1
       /  \
      2    3
     / \    \
    4   5    7
After calling your function, the tree should look like:
         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \    \
    4-> 5 -> 7 -> NULL
Solution:
Use level order traversal.


public class Solution {
    public void connect(TreeLinkNode root) {

        while(root != null){
            TreeLinkNode tempChild = new TreeLinkNode(0);
            TreeLinkNode currentChild = tempChild;
            while(root!=null){
                if(root.left != null) { currentChild.next = root.left; currentChild = currentChild.next;}
                if(root.right != null) { currentChild.next = root.right; currentChild = currentChild.next;}
                root = root.next;
            }
            root = tempChild.next;
        }
    }
}

Tuesday, June 16, 2015

Introduction To PowerShell

What is PowerShell:
- Used for task automation and management
- A framework by Microsoft.
- It is supported by .NET Framework. (As you can see below, you can play around with .Net functionality)

PowerShell has:
- Command-line shell, which is similar to cmd in Windows or terminal in Linux.
- Associated scripting language.


How to install:
You can follow the guide at Installing PowerShell Windows.
If you have installed Microsoft Visual Studio, it also have options to install PowerShell.

How to Start with command-line shell after installation:
- You can follow this guide at Starting the 32-bit Version of PowerShell
Normally in Windows, you also can click "Start" and search for PowerShell.

After starting, the screen is as below. You can type: get-command to see all commands.

PowerShell command-line

Getting Started With PowerShell Command-line
You can play around with PowerShell. In the Command-line Shell, 

Below is one way that you can save a password with SecureString to a text file. Although this is not the good way in terms of security, but this is a good start with PowerShell.

Try the following commands !

Command 1:
$key = (3,4,2,3,56,34,254,222,1,1,2,23,42,54,33,233,1,34,2,7,6,5,35,43)

Command 2:
$pw = read-host "Enter Password" –AsSecureString

Command 3:
ConvertFrom-SecureString $pw -key $key | out-file "path\to\password\file\here\textfile.txt"


Now you have a textfile.txt, and its content might look like this:

76492d1116743f0423413b16050a5345MgB8ADMAVQBBAG8AeQAwAC8AdwBaAFgAZgBxAHMAMgBOAHYAUgBhAG8AaQB3AGcAPQA9AHwAMgAwAGIAMQAyADQANwA0ADUAMQBlADAANQA4ADcANwA0AGMAYwA1ADEANwA2AGMAYQAyAGYAMgBhADQAOAA0ADcANAA2ADYAYgBiADAAYwA3AGIAZABlADIAMgAwADgAYQBlADYANAA1ADUAYwBmADMAMwA2ADMAMwA4ADcAMQA=


In order to decrypt the content, try the following command from the command-line Shell:

Command 4:
$password = cat  "path\to\password\file\here\textfile.txt" | convertto-securestring -key $key

Command 5:
$Ptr = [System.Runtime.InteropServices.Marshal]::SecureStringToCoTaskMemUnicode($password)

command 6:
$result = [System.Runtime.InteropServices.Marshal]::PtrToStringUni($Ptr)

Command 7:
[System.Runtime.InteropServices.Marshal]::ZeroFreeCoTaskMemUnicode($Ptr)

Command 8:
$result


Here it is, $result is the "password" you entered in command 1

Just play around with it and you will get more experienced!

UPDATE 1:
Links

It is a little bit off the scope. Below is the C# code to convert the text of a SecureString stored in a text file to an in-memory SecureString.

public static SecureString ConvertToSecureString(string psProtectedString, byte[] key)
        {
            // '|' is indeed the separater
            byte[] asBytes = Convert.FromBase64String(psProtectedString);
            string[] strArray = Encoding.Unicode.GetString(asBytes).Split(new[] { '|' });

            if (strArray.Length != 3) throw new InvalidDataException("input had incorrect format");

            // strArray[0] is a static/magic header or signature (different passwords produce
            //    the same header)  It unused in our case, looks like 16 bytes as hex-string
            // you know strArray[1] is a base64 string by the '=' at the end
            //    the IV is shorter than the body, and you can verify that it is the IV, 
            //    because it is exactly 16bytes=128bits and it decrypts the password correctly
            // you know strArray[2] is a hex-string because it is [0-9a-f]
            byte[] magicHeader = HexStringToByteArray(psProtectedString.Substring(0, 32));
            byte[] rgbIV = Convert.FromBase64String(strArray[1]);
            byte[] cipherBytes = HexStringToByteArray(strArray[2]);

            // setup the decrypter
            SecureString str = new SecureString();
            SymmetricAlgorithm algorithm = SymmetricAlgorithm.Create();
            ICryptoTransform transform = algorithm.CreateDecryptor(key, rgbIV);
            using (var stream = new CryptoStream(new MemoryStream(cipherBytes), transform, CryptoStreamMode.Read))
            {
                // using this silly loop format to loop one char at a time
                // so we never store the entire password naked in memory
                int numRed = 0;
                byte[] buffer = new byte[2]; // two bytes per unicode char
                while ((numRed = stream.Read(buffer, 0, buffer.Length)) > 0)
                {
                    str.AppendChar(Encoding.Unicode.GetString(buffer).ToCharArray()[0]);
                }
            }

            //
            // non-production code
            // recover the SecureString; just to check
            // from http://stackoverflow.com/questions/818704/how-to-convert-securestring-to-system-string
            //
            IntPtr valuePtr = IntPtr.Zero;
            string secureStringValue = "";
            try
            {
                // get the string back
                valuePtr = Marshal.SecureStringToGlobalAllocUnicode(str);
                secureStringValue = Marshal.PtrToStringUni(valuePtr);
            }
            finally
            {
                Marshal.ZeroFreeGlobalAllocUnicode(valuePtr);
            }

            return str;
        }

        // from http://stackoverflow.com/questions/311165/how-do-you-convert-byte-array-to-hexadecimal-string-and-vice-versa
       
public static byte[] HexStringToByteArray(String hex)
        {
            int NumberChars = hex.Length;
            byte[] bytes = new byte[NumberChars / 2];
            for (int i = 0; i < NumberChars; i += 2) bytes[i / 2] = Convert.ToByte(hex.Substring(i, 2), 16);

            return bytes;
        }

       
public static SecureString DecryptPassword(string psPasswordFile, byte[] key)
        {
            if (!File.Exists(psPasswordFile)) throw new ArgumentException("file does not exist: " + psPasswordFile);

            string formattedCipherText = File.ReadAllText(psPasswordFile);

            return ConvertToSecureString(formattedCipherText, key);
        }



Friday, June 5, 2015

Shortest Palindrome and KMP algorithm: A little thought!

In leetcode, Shortest Palindrome is one of the site's interesting algorithmic problems. It states that from a string s find the shortest palindrome by adding some characters to the front of s.

If you have never tried to solve this problem, I suggest that you solve it, and it will help you improve your problem solving skill.

After solving it, I kept looking for better solutions. I stumbled upon another programmer's solution. It is in python, and really neat. It is really interesting, but later I found out it was wrong.
class Solution:
    # @param {string} s
    # @return {string}
    def shortestPalindrome(self, s):
        A=s+s[::-1]
        cont=[0]
        for i in range(1,len(A)):
            index=cont[i-1]
            while(index>0 and A[index]!=A[i]):
                index=cont[index-1]
            cont.append(index+(1 if A[index]==A[i] else 0))
        print cont[-1]
        return s[cont[-1]:][::-1]+s

If you know python, please take some time to digest the Solution. By 2015-06-05, this solution is still accepted by leetcode. (Updated: LeetCode now added test cases to check this issue)

I myself looked at the Solution and saw it's interesting idea. At first, the algorithm concatenates the string and its reversed version. Then the following steps are similar to the steps for building KMP-table (or failure function) using in KMP algorithm. Why does this procedure work?

If you know KMP text searching algorithm, you will know its "lookup table" and steps to build it. Right now, I just show one important use of the table: it can show you the longest prefix of a string that is also suffix of s (but not itself). For example, "abcdabc" has the longest prefix which is also a suffix: "abc" (not "abcdabc" since this is the entire string!!!). To make it fun, we call this prefix is "happy substring" of s. So the happy substring of "aaaaaaaaaa" (10 a's ) is "aaaaaaaaa" (9 a's).

Now we go back and see how finding happy sub string of s can help solve the shortest palindrome problem.

Suppose that q is the shortest string added to the front of s to make the string qs is a palindrome. We can see that obviously length(q) < length(s) since ss is also a palindrome. Since qs is a palindrome, qs must end with q, or s = p+q where p is a sub string of s. Easily we see that p is also a palindrome. Therefore, in order to have shortest qs, q needs to be shortest. In turn, p is the longest palindromic sub string of s.

We call s' and q' are the reversed strings of s and q respectively. We see that s = pq, s' = q'p since p is a palindrome. So ss' = pqq'p . Now we need to find the longest p. Eureka! This also means that p is a happy sub string of the string ss'. That's how the above algorithm works!!!

However, after some thought, the above algorithm has some loophole. p is not a happy sub string of ss'! In fact, p is the longest prefix that is also a suffix of ss', but the prefix and suffix must not overlap each other. So let's make it more fun, we call "extremely happy sub string" of a string s is the longest sub string of s that is a prefix and also a suffix and this prefix and suffix must not overlap. On the other word, the "extremely happy sub string" of s must have length less than or equal half length of s. 

So it turns out the "happy sub string" of ss' is not always "extremely happy sub string" of ss'. We can easily construct an example: s = "aabba". ss'="aabbaabbaa". The happy sub string of "aabbaabbaa" is "aabbaa", while the extremely happy sub string of "aabbaabbaa" is "aa". Bang!

Hence, the correct solution should be as following, based on the observation that length(p) <= length(ss')/2.

class Solution:
    # @param {string} s
    # @return {string}
    def shortestPalindrome(self, s):
        A=s+s[::-1]
        cont=[0]
        for i in range(1,len(A)):
            index=cont[i-1]
            while(index>0):
                if(A[index]==A[i]):
                    if index < len(s):
                        break
                index=cont[index-1]
            cont.append(index+(1 if A[index]==A[i] else 0))
        print cont[-1]
        return s[cont[-1]:][::-1]+s


Hooray!
As you can see, algorithms are interesting! And we programmers are responsible for making correct solutions carefully studying the problems. The only way for us is to keep learning, "Train dragons the hard way"!