Thinking out loud

Just attended GlobalHack 5. The only thing I am thinking right now is that I fucked up the whole team.

Things has been happening to me recently. I have been too confident about public speaking. I thought I was ceremony host several years ago so I don’t need to prepare it too hard to get everything running. It turned out to be, I am deadly wrong.

Here I am, in a weird state. I have been trying too hard to get in English thinkings, therefore my Chinese speaking skills dropped dramatically. I can not find the right words at the right time if it is formal. And here I am, not in English thinkings long enough, so that I also cannot find right words at the right time while speaking English either. The thing, to sum up, is that I am having trouble communicating in disregard of what language I am using. The irony really is all the crappy grammar I am using while typing this article right now.

However I was still confident enough to take the presentation work, without knowing I really should have practiced more.

I am sorry. To my teammates and all the efforts we have put into this project in the past 48 hours.

I don’t know, I think I should just leave….

Advertisements

Compare Version Numbers – Python

Compare two version numbers version1 and version2.
If version1 > version2 return 1, if version1 < version2 return -1, otherwise return 0.

You may assume that the version strings are non-empty and contain only digits and the . character.
The . character does not represent a decimal point and is used to separate number sequences.
For instance, 2.5 is not "two and a half" or "half way to version three", it is the fifth second-level revision of the second first-level revision.

Here is an example of version numbers ordering:
0.1 < 1.1 < 1.2 < 13.37

Idea: make two versions same length. Not literally, but in runtime


class Solution:
    # @param {string} version1
    # @param {string} version2
    # @return {integer}
    
    ## Idea: make two versions same length. Not literally, but in runtime
    def compareVersion(self, version1, version2):
        v1 = version1.split(".")
        v2 = version2.split(".")
        len1 = len(v1);
        len2 = len(v2);
        
        for i in range(0, max(len(v1), len(v2))):
            if i >= len1:
                if int(v2[i]) > 0:
                    return -1
                continue
            if i >= len2:
                if int(v1[i]) > 0:
                    return 1
                continue
            if int(v1[i]) > int(v2[i]):
                return 1
            if int(v1[i]) < int(v2[i]):
                return -1
        return 0

Urinal protocol vulnerability

Additional

xkcd

When a guy goes into the bathroom, which urinal does he pick?  Most guys are familiar with the International Choice of Urinal Protocol.  It’s discussed at length elsewhere, but the basic premise is that the first guy picks an end urinal, and every subsequent guy chooses the urinal which puts him furthest from anyone else peeing.  At least one buffer urinal is required between any two guys or Awkwardness ensues.

Let’s take a look at the efficiency of this protocol at slotting everyone into acceptable urinals.  For some numbers of urinals, this protocol leads to efficient placement.  If there are five urinals, they fill up like this:

The first two guys take the end and the third guy takes the middle one.  At this point, the urinals are jammed — no further guys can pee without Awkwardness.  But it’s pretty efficient; over 50% of the urinals are used.

On the…

View original post 490 more words

Length of Last Word

Problem: Given a string s consists of upper/lower-case alphabets and empty space characters ‘ ‘, return the length of last word in the string.

If the last word does not exist, return 0.

Note: A word is defined as a character sequence consists of non-space characters only.

For example,
Given s = “Hello World”,
return 5.

Analysis:

There are two ways to solve the problem. First one is using the Java built in String method split. Quite a cheating way to do it.


public class Solution {
    public int lengthOfLastWord(String s) {
        String[] S = s.split(" ");
        if (S.length == 0) return 0;
        else return S[S.length-1].length();
    }
}

Second way is to use a counter like a ‘normal person’.


public class Solution {
    public int lengthOfLastWord(String s) {
        if (s == null || s.length() == 0 || (s.length() == 1 && s.charAt(0) == ' ')) return 0;
        
        int right = s.length() - 1;
        int len = 0;
        
        while (right >= 0 && s.charAt(right) == ' ') {
            right --;
        }
        
        while (right >= 0 && s.charAt(right) != ' ') {
            len++;
            right--;
        }
        
        return len;
    }
}

Container With Most Water

Problem:
Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container.

Analysis:

This question was confusing, be sure to make sure what kind of container, I thought only neighbor lines can be part of the container so I ‘solved’ it with just one line.

It is easily to come up with a O(n^2) solution, however there are a lot of cases we counted twice.


public class Solution {
    public int maxArea(int[] height) {
        int left = 0; 
        int right = height.length-1;
        
        int result = 0;
        
        while (left < right) {
            result = Math.max(((right-left)*Math.min(height[left], height[right])), result);
            if (height[left] < height[right]) left++;
            else right--;
        }
        
        return result;
    }
}

Unique Paths

Problem:

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

How many possible unique paths are there?

Thinking:

This problem is actually an example when we are having the Algorithm course, when introducing DP (Well of course the not the first example because the first example is always Fibonacci Numbers.)

 

 


public class Solution {
    public int uniquePaths(int m, int n) {
        int[][] table= new int[m+1][n+1];
        for (int i = 1; i <= m; i++) {
            table[i][1] = 1;
        }
        
        for (int i = 1; i <= n; i++) {
            table[1][i] = 1;
        }
        
        for (int i = 2; i <= m; i++) {
            for (int j = 2; j <= n; j++) {
                table[i][j] = table[i-1][j] + table[i][j-1];
            }
        }
        
        return table[m][n];
    }
}

Maximum Subarray *****

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

More practice:If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

Thinking: Using DP, there is a pattern that for subarray 0-i, the maximum subarray is the maximum in this subarray. Therefore we need to keep one max that keeps track on what is the first maximum subarray so far.


public class Solution {
    public int maxSubArray(int[] A) {
        if (A.length == 0) return 0;
        
        int max = A[0];
        int sum = 0;
        
        for (int i = 0; i < A.length; i++) {
            sum += A[i];
            max = Math.max(max, sum);
            sum = Math.max(0, sum);
        }
        
        return max;
    }
}

Linked List Cycle

Problem:
Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?

Thinking: Using fast & slow runner method. If one leap forward two steps per time, and one leap forward one step per time. If there is a cycle, then the fast runner will catch the slow one at some point.


/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) return false;
        
        ListNode fast = head.next;
        ListNode slow = head;
        
        while (fast != null && fast.next != null) {
            if (fast == slow) return true;
            fast = fast.next.next;
            slow = slow.next;
        }
        
        return false;
    }
}

Merge Two Sorted Lists

Problem: Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.


/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        
        ListNode dummy = new ListNode(0);
        ListNode pointer = dummy;
        
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                pointer.next = l1;
                l1 = l1.next;
                pointer = pointer.next;
            } else {
                pointer.next = l2;
                l2 = l2.next;
                pointer = pointer.next;
            }
        }
        
        if (l1 == null && l2 != null) {
            while (l2 != null) {
                pointer.next = l2;
                l2 = l2.next;
                pointer = pointer.next;
            }
        }
        
        if (l2 == null && l1 != null) {
            while (l1 != null) {
                pointer.next = l1;
                l1 = l1.next;
                pointer = pointer.next;
            }
        }
        
        return dummy.next;
    }
}

Plus One

Problem: Given a non-negative number represented as an array of digits, plus one to the number.

The digits are stored such that the most significant digit is at the head of the list.


public class Solution {
    public int[] plusOne(int[] digits) {
        if (digits.length == 0) return digits;
        
        int toAdd = 1;
        
        for (int i = digits.length-1; i >= 0; i--) {
            if (digits[i] + toAdd > 9) {
                toAdd = 1;
                digits[i] = 0;
            }else{
                digits[i] += toAdd;
                toAdd = 0;
                break;
            }
        }
        
        if (digits[0] == 0) {
            int[] temp = new int[digits.length + 1];
            temp[0] = 1;
            for (int i = 0; i < digits.length; i++) {
                temp[i+1] = digits[i];
            }
            digits = temp;
        }
        
        return digits;
    }
}