Leetcode: Happy Number

Write an algorithm to determine if a number is "happy".

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Example: 19 is a happy number

• 12 + 92 = 82
• 82 + 22 = 68
• 62 + 82 = 100
• 12 + 02 + 02 = 1

Understand the problem:
The hint of the problem is if the input number is a happy number, it will end with 1. 
Else, it will loop endlessly in a cycle. Therefore, we could use a hash set to keep track of each number we have visited. If we saw a visited number, that means the loop has been formed and it will return a false. 

Code (Java):

public class Solution {
    public boolean isHappy(int n) {
        if (n <= 0) {
            return false;
        }
        
        Set<Integer> set = new HashSet<Integer>();
        
        while (true) {
            int square = getSumOfSquare(n);
            
            if (square == 1) {
                return true;
            } else if (set.contains(square)) {
                return false;
            }
            
            set.add(square);
            n = square;
        }
    }
    
    private int getSumOfSquare(int n) {
        int result = 0;
        
        while (n > 0) {
            int digit = n % 10;
            n = n / 10;
            result += digit * digit;
        }
        
        return result;
    }
}

An O(1) space solution:

int digitSquareSum(int n) {
    int sum = 0, tmp;
    while (n) {
        tmp = n % 10;
        sum += tmp * tmp;
        n /= 10;
    }
    return sum;
}

bool isHappy(int n) {
    int slow, fast;
    slow = fast = n;
    do {
        slow = digitSquareSum(slow);
        fast = digitSquareSum(fast);
        fast = digitSquareSum(fast);
    } while(slow != fast);
    if (slow == 1) return 1;
    else return 0;
}

Questions: Why unhappy number must end with a loop?
There is a proof from wiki:
https://en.wikipedia.org/wiki/Happy_number

Numbers that are happy, follow a sequence that ends in 1. All non-happy numbers follow sequences that reach the cycle:

4, 16, 37, 58, 89, 145, 42, 20, 4, ...

To see this fact, first note that if n has m digits, then the sum of the squares of its digits is at most ${\displaystyle 9^{2}m}$, or ${\displaystyle 81m}$.

For ${\displaystyle m=4}$ and above,

${\displaystyle n\geq 10^{m-1}>81m}$

so any number over 1000 gets smaller under this process and in particular becomes a number with strictly fewer digits. Once we are under 1000, the number for which the sum of squares of digits is largest is 999, and the result is 3 times 81, that is, 243.

• In the range 100 to 243, the number 199 produces the largest next value, of 163.
• In the range 100 to 163, the number 159 produces the largest next value, of 107.
• In the range 100 to 107, the number 107 produces the largest next value, of 50.

Considering more precisely the intervals [244,999], [164,243], [108,163] and [100,107], we see that every number above 99 gets strictly smaller under this process. Thus, no matter what number we start with, we eventually drop below 100. An exhaustive search then shows that every number in the interval [1,99] either is happy or goes to the above cycle.

The above work produces the interesting result that no positive integer other than 1 is the sum of the squares of its own digits, since any such number would be a fixed point of the described process.

Leetcode: Binary Tree Right Side View

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

For example:
Given the following binary tree,

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

You should return [1, 3, 4].

Idea:
Obviously, the question asks for a BFS. The major difference from the traditional BFS is it only prints the right-most nodes for each level. Consequently, the basic idea is to add right child before adding the left child. For each level, only print out the first node, which must be the right-most node. 

Code (Java):

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        if (root == null) {
            return result;
        }
        
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode curr = queue.poll();
                if (i == 0) {
                    result.add(curr.val);
                }
                if (curr.right != null) {
                    queue.offer(curr.right);
                }
                
                if (curr.left != null) {
                    queue.offer(curr.left);
                }
            }
        }
        
        return result;
    }
}

A DFS solution: 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        
        if (root == null) {
            return result;
        }
        
        rightSideViewHelper(root, 0, result);
        
        return result;
    }
    
    private void rightSideViewHelper(TreeNode root, int level, List<Integer> result) {
        if (root == null) {
            return;
        }
        
        if (level == result.size()) {
            result.add(root.val);
        }
        
        rightSideViewHelper(root.right, level + 1, result);
        rightSideViewHelper(root.left, level + 1, result);
    }
}

Leetcode: Bitwise AND of Numbers Range

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

For example, given the range [5, 7], you should return 4.

Credits:
Special thanks to @amrsaqr for adding this problem and creating all test cases.

Understand the problem:
We could take several examples, e.g. 5 6 7
101
110
111
-------
100

We could find out that the trick of the problem is when compare bit-by-bit for each number, once they are the same, e.g. bit 1 for the most significant bit, they start to be the same. 

9 10 11 12
1001
1010
1011
1100
---------
1000

So the solution is shift both m and n to the right until they are the equal, count the number of steps it shifted. Then shift m left to the number of steps. 

Code (Java):

public class Solution {
    public int rangeBitwiseAnd(int m, int n) {
        int shift = 0;
        
        while (m != n) {
            shift++;
            m = m >> 1;
            n = n >> 1;
        }
        
        return m << shift;
    }
}

Leetcode: Number of 1 Bits

Write a function that takes an unsigned integer and returns the number of ’1' bits it has (also known as the Hamming weight).

For example, the 32-bit integer ’11' has binary representation 00000000000000000000000000001011, so the function should return 3.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

Understand the problem:
The questions is quite easy to address. Each time we get the least significant bit and check if it is 1. Then shift the number to the right by 1 until 32 times. 

Code (Java):

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int result = 0;
        for (int i = 0; i < 32; i++) {
            result += n & 1;
            n = n >> 1;
        }
        
        return result;
    }
}

Leetcode: Reverse Bits

Reverse bits of a given 32 bits unsigned integer.

For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as00111001011110000010100101000000).

Follow up:
If this function is called many times, how would you optimize it?

Related problem: Reverse Integer

Understand the problem:
We could get the least significant bit each time and append to the new result. 
e.g. 11100, we get 0 0 1 1 1, and append to the new result from right to left as well.

Code (Java):

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        
        int result = 0;
        for (int i = 0; i < 32; i++) {
            result = (result << 1) | (n & 1);
            n = (n >> 1);
        }
        
        return result;
    }
}

Leetcode: Rotate Array

Rotate an array of n elements to the right by k steps.

For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

Note:
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.

Code (Java):

public class Solution {
    public void rotate(int[] nums, int k) {
        if (nums == null || nums.length <= 1 || k <= 0) {
            return;
        }
        
        // Step 1: swap each element of the array
        int i = 0;
        int j = nums.length - 1;
        while (i < j) {
            swap(nums, i, j);
            i++;
            j--;
        }
        
        k %= nums.length; 
        
        // Step 2: swap the first k elements
        i = 0;
        j = k - 1;
        while (i < j) {
            swap(nums, i, j);
            i++;
            j--;
        }
        
        // Step 3: swap the rest of k elements
        i = k;
        j = nums.length - 1;
        while (i < j) {
            swap(nums, i, j);
            i++;
            j--;
        }
    }
    
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

Leetcode: Reverse Words in a String II

Given an input string, reverse the string word by word. A word is defined as a sequence of non-space characters.

The input string does not contain leading or trailing spaces and the words are always separated by a single space.

For example,
Given s = "the sky is blue",
return "blue is sky the".

Could you do it in-place without allocating extra space?

Code (Java):

public class Solution {
    public void reverseWords(char[] s) {
        if (s == null || s.length <= 1) {
            return;
        }
        
        int i = 0;
        int j = s.length - 1;
        while (i < j) {
            swap(s, i, j);
            i++;
            j--;
        }
        
        // Step 2: swap again within a token
        i = 0;
        j = 0;
        while (j < s.length) {
            while (j < s.length && s[j] != ' ') {
                j++;
            }
            
            int m = i;
            int n = j - 1;
            while (m < n) {
                swap(s, m, n);
                m++;
                n--;
            }
            
            i = j + 1;
            j = i;
        }
    }
    
    private void swap(char[] s, int i, int j) {
        char tmp = s[i];
        s[i] = s[j];
        s[j] = tmp;
    }
}

Leetcode: Largest Number

Given a list of non negative integers, arrange them such that they form the largest number.

For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.

Note: The result may be very large, so you need to return a string instead of an integer.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

Understand the problem:
The problem suggests to sort the array first according to the lexco order. The sorting rule is if two strings a and b, we compares ab and ba, and sort it in descending order.

The only thing needs to take care is the leading zeros in the final results. If there are leading zeros, it must be the case like 0, 0, 0, 0 ... i.e all array elements must be 0. In this case, return "0".

Code (Java):

public class Solution {
    public String largestNumber(int[] nums) {
        if (nums == null || nums.length == 0) {
            return "";
        }
        String[] strs = new String[nums.length];
        for (int i = 0; i < strs.length; i++) {
            strs[i] = String.valueOf(nums[i]);
        }
        
        Arrays.sort(strs, new StringComparator());
        
        StringBuffer sb = new StringBuffer();
        
        for (String str : strs) {
            sb.append(str);
        }
        
        if (sb.charAt(0) == '0') {
            return "0";
        }
        
        return sb.toString();
    }
    
    public class StringComparator implements Comparator<String> {
        @Override
        public int compare (String str1, String str2) {
            String ab = str1 + str2;
            String ba = str2 + str1;
            return ba.compareTo(ab);
        }
    }
}

Leetcode: Factorial Trailing Zeroes

Given an integer n, return the number of trailing zeroes in n!.

Note: Your solution should be in logarithmic time complexity.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

Understand the problem:
The naive solution would be first calculate the n!, can then count how many number of zeros. Here the question requires the log time complexity. 

Let's take several examples then we may find some patterns. 
5 ! = 1 * 2 * 3 * 4 * 5 = 120,  -> 1 zero
6 ! = 1 * 2 * 3 * ... * 6 = 720, -> 1 zero
10 ! = 1 * 2 * ... * 5 * ... 10 = 362800  -> 2 zeros. 

Therefore, the number of trailing zeros are determined by the number of pair of (2 ,5) for the number. Since number of 2 are always greater than number of 5. We only need to count how many 5s in the number. 

Code (Java):

public class Solution {
    public int trailingZeroes(int n) {
        if (n <= 0) {
            return 0;
        }
        
        int count = 0;
        
        while (n > 1) {
            count += n / 5;
            n /= 5;
            
        }
        
        return count;
    }
}

Update on 10/14/15:

public class Solution {
    public int trailingZeroes(int n) {
        if (n < 5) {
            return 0;
        }
        
        int count = 0;
        for (long i = 5; n / i > 0; i *= 5) {
            count += n / i;
        }
        
        return count;
    }
}

Leetcode: Excel Sheet Column Number

Related to question Excel Sheet Column Title

Given a column title as appear in an Excel sheet, return its corresponding column number.

For example:

    A -> 1
    B -> 2
    C -> 3
    ...
    Z -> 26
    AA -> 27
    AB -> 28 

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

Understand the problem:
This question is an reverse question of the previous one. Let's still an transforming 26-base number to a 10-base number. Before we solve this question, let's consider how to convert a string to a number. For e.g. "123" -> 123, we start from the most significant digit,
1 + result * 10 = 1
2 + rssult * 10 = 12
3 + result * 10 = 123

So the solution here is the same, except for replacing the 10 by 26. Also noted that we need to add number by 1 each time since this question is index-1 started. 

Code (Java):

public class Solution {
    public int titleToNumber(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        
        int result  = 0;
        
        for (int i = 0; i < s.length(); i++) {
            result = result * 26 + s.charAt(i) - 'A' + 1;
        }
        
        return result;
    }
}

Leetcode: Excel Sheet Column Title

Given a positive integer, return its corresponding column title as appear in an Excel sheet.

For example:

    1 -> A
    2 -> B
    3 -> C
    ...
    26 -> Z
    27 -> AA
    28 -> AB 

Credits:
Special thanks to @ifanchu for adding this problem and creating all test cases.

Understand the problem:
A classic 10-based math to 26-based math. Remember for a 10-based integer, e.g. 123, how can we extract each digit?  The idea is from the least significant digit and use %10 and /10 respectively. e.g. 
123 % 10 = 3, 123 / 10 = 12
12 % 10 = 2, 12 / 10 = 1
1 % 10 = 1, 1 / 10 - 0.

Therefore, for this question, we only need to replace 10 to 26. Note that for this question, the map is from 1 to 26. Therefore, we need to minus 1 for each number before the computation.  

Code (Java):

public class Solution {
    public String convertToTitle(int n) {
        if (n <= 0) {
            return "";
        }
        
        StringBuffer sb = new StringBuffer();
        convertToTitleHelper(n, sb);
        
        sb.reverse();
        
        return sb.toString();
    }
    
    private void convertToTitleHelper(int n, StringBuffer sb) {
        if (n <= 0) {
            return;
        }
        n--;
        int val = n % 26;
        val = val < 0 ? val + 26 : val;
        char title = (char) (val + 'A');
        
        sb.append(title);
        
        convertToTitleHelper(n / 26, sb);
    }
}

Update on 10/14/15:

public class Solution {
    public String convertToTitle(int n) {
        if (n <= 0) {
            return "";
        }
        
        StringBuffer sb = new StringBuffer();
        
        while (n > 0) {
            n--;
            
            int val = n % 26;
            char title = (char) (val + 'A');
            sb.insert(0, title);
            
            n /= 26;
        }
        
        return sb.toString();
    }
}

Leetcode: Two Sum II - Input array is sorted

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

Code(Java):

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        if (numbers == null || numbers.length < 2) {
            return new int[2];
        }
        
        int lo = 0;
        int hi = numbers.length - 1;
        
        int[] result = new int[2];
        
        while (lo < hi) {
            if (numbers[lo] + numbers[hi] == target) {
                result[0] = lo + 1;
                result[1] = hi + 1;
                return result;
            } else if (numbers[lo] + numbers[hi] > target) {
                hi--;
            } else {
                lo++;
            }
        }
        
        return result;
    }
}

Leetcode: Maximum Gap

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Try to solve it in linear time/space.

Return 0 if the array contains less than 2 elements.

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

Understand the problem:
We problem is not clearly defined. We can use an example to show.  e.g. 
A[] = {1, 7, 3, 4}
In the sorted form, it is 1 3 4 7, and the maximum gap is between 4 and 7, which is 3. 

Since the problem asks for O(n) time and space solution, we need to think of using a bucket sorting. 

 -- Step 1: Calculate the ave. interval. We calculate the min and max of the array A[], and the maximum gap should be in the upper bound of (max - min) / (N - 1). For example, for the example shown above, if the number is uniformly distributed, the gap is (7 - 1) / 3 = 2, i.e, the array should be 1 3 5 7. 
Since now the number may not be uniformly distributed, the maximum gap might be greater than 2. 
 -- Step 2: Determine the number of buckets, which should be (max - min) / interval + 1. The number of buckets should be equal to the range of numbers / range per bucket. 
  -- Step 3: Determine which number is in which bucket, which equals to (A[i] - min) / interval. e.g. (7 - 1) / 2 = 3, in bucket[3]. 
  -- Step 4: We only need to maintain the min and max value for each bucket. The maximum gap must between two adj. buckets instead of within a bucket. That is because the maximum gap inside of a bucket is interval - 1. However, in the step 1 we have already known that the the maximal gap must be greater than interval. 
  -- Step 5. After we calculated the min and max value in each bucket, we then iterate through the buckets and get the maximal gap between buckets. Be very careful that buckets might be empty. 

Code (Java):

public class Solution {
    public int maximumGap(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return 0;
        }
        
        // Step 1: find max and min element
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int num : nums) {
            if (num > max) {
                max = num;
            }
            
            if (num < min) {
                min = num;
            }
        }
        
        int len = nums.length;
        
        // Step 2: calculate the intervals and number of buckets. 
        int interval = (int) Math.ceil((double) (max - min) / (len - 1));

        if (interval == 0) {
            interval = 1;
        }
        int numBuckets = (max - min) / interval + 1;
        Bucket[] buckets = new Bucket[numBuckets];
        for (int i = 0; i < numBuckets; i++) {
            buckets[i] = new Bucket();
        }
        
        // Step 3: iterate through the nums and assign the number into the buckets. 
        for (int num : nums) {
            int bucketNum = (num - min) / interval;
            if (num > buckets[bucketNum].max) {
                buckets[bucketNum].max = num;
            }
            
            if (num < buckets[bucketNum].min) {
                buckets[bucketNum].min = num;
            }
        }
        
        // Step 4: iterate through the buckets and get the maximal gap
        int prev = buckets[0].max;
        int maxGap = 0;
        for (int i = 1; i < numBuckets; i++) {
            if (prev != Integer.MIN_VALUE && buckets[i].min != Integer.MAX_VALUE) {
                maxGap = Math.max(maxGap, buckets[i].min - prev);
                prev = buckets[i].max;
            }
        }
        
        return maxGap;
    }
    
    private class Bucket {
        public int min;
        public int max;
        
        public Bucket() {
            min = Integer.MAX_VALUE;
            max = Integer.MIN_VALUE;
        }
    }
}

Update on 5/20/19:

public class Solution {
    /**
     * @param nums: an array of integers
     * @return: the maximun difference
     */
    public int maximumGap(int[] nums) {
        // write your code here
        if (nums == null || nums.length < 2) {
            return 0;
        }
        
        int[] minMax = findMinMax(nums);
        int min = minMax[0];
        int max = minMax[1];
        int numBuckets = nums.length;
        
        Bucket[] buckets = new Bucket[numBuckets];
        for (int i = 0; i < numBuckets; i++) {
            buckets[i] = new Bucket();
        }
        int capacity = (int)Math.ceil(((double)max - min + 1) / numBuckets);
        
        for (int num : nums) {
            int bucketIdx = (num - min) / capacity;
            
            if (buckets[bucketIdx].min == -1 || buckets[bucketIdx].min > num) {
                buckets[bucketIdx].min = num;
            }
            
            if (buckets[bucketIdx].max == -1 || buckets[bucketIdx].max < num) {
                buckets[bucketIdx].max = num;
            }
        }
        
        int maxGap = 0;
        Bucket prevBucket = buckets[0];
        for (int i = 1; i < numBuckets; i++) {
            if (buckets[i].min == - 1 || buckets[i].max == -1) {
                continue;
            }
            
            maxGap = Math.max(maxGap, buckets[i].max - buckets[i].min);
            if (prevBucket.min != -1 && prevBucket.max != -1) {
                maxGap = Math.max(maxGap, buckets[i].min - prevBucket.max);
            }
            
            prevBucket = buckets[i];
            
        }
        
        return maxGap;
    }
    
    private int[] findMinMax(int[] nums) {
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        
        for (int num : nums) {
            max = Math.max(max, num);
            min = Math.min(min, num);
        }
        
        int[] ans = new int[2];
        ans[0] = min;
        ans[1] = max;
        
        return ans;
    }
}

class Bucket {
    int min;
    int max;
    public Bucket() {
        min = -1;
        max = -1;
    }
}

Leetcode: Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Naive Solution:
Use a hash map to contain the number of each element. Then iterate the map. 

Code (Java):

public class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        
        for (int num : nums) {
            if (map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
            } else {
                map.put(num, 1);
            }
        }
        
        int len = nums.length;
        
        Iterator it = map.entrySet().iterator();
        while (it.hasNext()) {
            Map.Entry pair = (Map.Entry) it.next();
            int key = (int) pair.getKey();
            int value = (int) pair.getValue();
            
            if (value > len / 2) {
                return key;
            }
        }
        
        return 0;
    }
}

A constant-space solution:
Since the major element must occur more than n/2 times. We could compare each pair numbers, if not the same, we eliminate it. The left number must be the majority number. 

Code (Java):

public class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        int result = 0;
        
        for (int i = 0; i < nums.length; i++) {
            if (count == 0) {
                result = nums[i];
                count = 1;
            } else if (nums[i] == result) {
                count++;
            } else {
                count--;
            }
        }
        
        return result;
    }
}

Leetcode: Read N Characters Given Read4 – Call multiple times

Question:
Similar to Question [15. Read N Characters Given Read4], but the read function may be
called multiple times.

Solution:
This makes the problem a lot more complicated, because it can be called multiple times
and involves storing states.

Therefore, we design the following class member variables to store the states:
i. buffer – An array of size 4 use to store data returned by read4 temporarily. If
the characters were read into the buffer and were not used partially, they will
be used in the next call.

ii. offset – Use to keep track of the offset index where the data begins in the next
read call. The buffer could be read partially (due to constraints of reading up
to n bytes) and therefore leaving some data behind.

iii. bufsize – The real buffer size that stores the actual data. If bufsize > 0, that
means there is partial data left in buffer from the last read call and we should
consume it before calling read4 again. On the other hand, if bufsize == 0, it
means there is no data left in buffer.

This problem is a very good coding exercise. Coding it correctly is extremely tricky due

to the amount of edge cases to consider.

Code (Java):

/* The read4 API is defined in the parent class Reader4.
int read4(char[] buf); */
public class Solution extends Reader4 {
    private char[] buffer = new char[4];
    int offset = 0, bufsize = 0;
/**
* @param buf Destination buffer
* @param n   Maximum number of characters to read
* @return    The number of characters read
*/
    public int read(char[] buf, int n) {
        int readBytes = 0;
        boolean eof = false;
        while (!eof && readBytes < n) {
            int sz = (bufsize > 0) ? bufsize : read4(buffer);
            if (bufsize == 0 && sz < 4) eof = true;
            int bytes = Math.min(n - readBytes, sz);
            System.arraycopy(buffer /* src */, offset /* srcPos */, buf /* dest */, 
                readBytes /* destPos */, bytes /* length */);
            offset = (offset + bytes) % 4;
            bufsize = sz - bytes;
            readBytes += bytes;
        }
        return readBytes;
    }
}

Summary:
This problem is not very hard, but requires thinking of every corner cases. To sum up, the key of the problem is to put the char buf4[4] into global, and maintains two more global variables: 
 -- offset : the starting position in the buf4 that a read() should start from. 
 -- bytesLeftInBuf4 : how many elements left in the buf4. 

One corner case to consider is when is the eof should be true? In the previous question, it is true only if bytesFromRead4 < 4. However, in this question, since we might have some bytes left the buf4, even if it is not end of the file, we may mistakely consider the eof as true. So the condition to set eof is true is bytesFromRead4 < 4 && bytesLeftInBuf4 == 0 

Another corner case we need to consider is: if the bytesFromRead4 + bytesRead > n, the actual bytes to copy is n - bytesRead. 
For example, the file is "abcde", and read(2), in this case, the bytesFromRead4 = 4, but we should only copy 2 bytes from the buf4. So be very careful about this case. 

At the end, we need to update the global offset and bytesLeftInBuf4, as well as the local bytesRead. 

Do execrise more about this question, this is really classical. 


Update on 11/19/18:

/* The read4 API is defined in the parent class Reader4.
      int read4(char[] buf); */

public class Solution extends Reader4 {
    /**
     * @param buf Destination buffer
     * @param n   Maximum number of characters to read
     * @return    The number of characters read
     */
    boolean m_fEof = false;
    char[] m_buf4 = new char[4];
    int m_lastPos = 0;
    int m_cBytesLastRead = 0;
    
    public int read(char[] buf, int n) {        
        int curPos = 0;
        while (curPos < n) {
            if (m_lastPos == m_cBytesLastRead) {
                m_cBytesLastRead = read4(m_buf4);
                if (m_cBytesLastRead < 4) {
                    m_fEof = true;
                }
                m_lastPos = 0;
            }
            
            int cBytesToRead = Math.min(n - curPos, m_cBytesLastRead - m_lastPos);
            System.arraycopy(m_buf4, m_lastPos, buf, curPos, cBytesToRead);
            
            curPos += cBytesToRead;
            m_lastPos += cBytesToRead;
            
            if (m_fEof) {
                break;
            }
        }
        
        return curPos;
    }
}

Leetcode: Read N Characters Given Read4

The API: int read4(char *buf) reads 4 characters at a time from a file.

The return value is the actual number of characters read. For example, it returns 3 if there is only 3 characters left in the file.

By using the read4 API, implement the function int read(char *buf, int n) that reads n characters from the file.

Note:
The read function will only be called once for each test case.

Understand the problem:
This seemingly easy coding question has some tricky edge cases. When read4 returns
less than 4, we know it must reached the end of file. However, take note that read4
returning 4 could mean the last 4 bytes of the file.

To make sure that the buffer is not copied more than n bytes, copy the remaining bytes
(n – readBytes) or the number of bytes read, whichever is smaller.

Code (Java):

/** The read4 API is defined in the parent class Reader4. int read4(char[] buf); */

public class Solution extends Reader4 {
/**
* @param buf 　Destination buffer
* @param n　　　Maximum number of characters to read
* @return　    The number of characters read
*/
    public int read(char[] buf, int n) {
        char[] buffer = new char[4];
        int readBytes = 0;
        boolean eof = false;
        while (!eof && readBytes < n) {
            int sz = read4(buffer);
            if (sz < 4) eof = true;
            int bytes = Math.min(n - readBytes, sz);
            System.arraycopy(buffer /* src */, 0 /* srcPos */,　buf /* dest */, readBytes /* destPos */, bytes /* length */);
            readBytes += bytes;
        }
        return readBytes;
    }
}

Update on 9/29/15:

/* The read4 API is defined in the parent class Reader4.
      int read4(char[] buf); */

public class Solution extends Reader4 {
    /**
     * @param buf Destination buffer
     * @param n   Maximum number of characters to read
     * @return    The number of characters read
     */
    public int read(char[] buf, int n) {
        boolean eof = false;
        int charsRead = 0;
        char[] buf4 = new char[4];
        
        while (!eof && charsRead < n) {
            int size = read4(buf4);
            if (size < 4) {
                eof = true;
            }
            
            if (charsRead + size > n) {
                size = n - charsRead;
            }
            
            System.arraycopy(buf4, 0, buf, charsRead, size);
            charsRead += size;
        }
        
        return charsRead;
    }
}

Leetcode: Compare Version Numbers

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

Understand the problem:
The tricky part of the problem is to understand that 1.0 and 1 are the same version. 

Code (Java):

public class Solution {
    public int compareVersion(String version1, String version2) {
        if ((version1 == null || version1.length() == 0) && 
            (version2 == null || version2.length() == 0)) {
            return 0;
        }
        
        if (version1 == null || version1.length() == 0) {
            return -1;
        }
        
        if (version2 == null || version2.length() == 0) {
            return 1;
        }
        
        String delim = "[.]";
        String[] v1 = version1.split(delim);
        String[] v2 = version2.split(delim);
        
        int i;
        int j;
        for (i = 0, j = 0; i < v1.length || j < v2.length; i++, j++) {
            String s1 = "";
            String s2 = "";
            if (i < v1.length) {
                s1 = v1[i];
            }
            
            if (j < v2.length) {
                s2 = v2[j];
            }
            
            s1 = removeLeadingZeros(s1);
            s2 = removeLeadingZeros(s2);
            
            if (s1.isEmpty() && s2.isEmpty()) {
                continue;
            }
            
            if (s2 == null || s2.length() == 0) {
                return 1;
            }
            
            if (s1 == null || s1.length() == 0) {
                return -1;
            }
            
            if (s1.length() > s2.length()) {
                return 1;
            } else if (s1.length() < s2.length()) {
                return -1;
            } else {
                for (int k = 0; k < s1.length(); k++) {
                    if (Character.getNumericValue(s1.charAt(k)) > 
                        Character.getNumericValue(s2.charAt(k))) {
                        return 1;
                    } else if (Character.getNumericValue(s1.charAt(k)) < 
                        Character.getNumericValue(s2.charAt(k))) {
                        return -1;
                    }
                }
            }
        }
        
        return 0;
    }
    
    private String removeLeadingZeros(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        
        int start = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) != '0') {
                break;
            } else {
                start++;
            }
        }
        
        return s.substring(start);
    }
}

A neater code:
If in each sub-version, we assume that the length is not greater than the upper bound of an integer number, we don't need to parse it character-by-character. 

Code (Java):

public int compareVersion(String version1, String version2) {
    String[] arr1 = version1.split("\\.");
    String[] arr2 = version2.split("\\.");
 
    int i=0;
    while(i<arr1.length || i<arr2.length){
        if(i<arr1.length && i<arr2.length){
            if(Integer.parseInt(arr1[i]) < Integer.parseInt(arr2[i])){
                return -1;
            }else if(Integer.parseInt(arr1[i]) > Integer.parseInt(arr2[i])){
                return 1;
            }
        } else if(i<arr1.length){
            if(Integer.parseInt(arr1[i]) != 0){
                return 1;
            }
        } else if(i<arr2.length){
           if(Integer.parseInt(arr2[i]) != 0){
                return -1;
            }
        }
 
        i++;
    }
 
    return 0;
}

Update on 10/14/15:
The very tricky part is the corner cases need to consider:
1. v1 = 1.0.0, v2 = 1, => so they should be the same version

Therefore, when we went through one of the arrays, we need to also iterate the rest of the array until it's to the end. 

Code (Java):

public class Solution {
    public int compareVersion(String version1, String version2) {
        String delim = "[.]";
        String[] v1 = version1.split(delim);
        String[] v2 = version2.split(delim);
        
        int i = 0; 
        int j = 0;
        
        while (i < v1.length && j < v2.length) {
            int seg1 = Integer.parseInt(v1[i]);
            int seg2 = Integer.parseInt(v2[j]);
            
            if (seg1 > seg2) {
                return 1;
            } else if (seg1 < seg2) {
                return -1;
            } else {
                i++;
                j++;
            }
        }
        
        while (i < v1.length) {
            int seg1 = Integer.parseInt(v1[i]);
            if (seg1 != 0) {
                return 1;
            } else {
                i++;
            }
        }
        
        while (j < v2.length) {
            int seg2 = Integer.parseInt(v2[j]);
            if (seg2 != 0) {
                return -1;
            } else {
                j++;
            }
        }
        
        return 0;
    }
}

Update on 11/20/18:

class Solution {
    public int compareVersion(String version1, String version2) {
        String delim = "[.]";
        String[] s1 = version1.split(delim);
        String[] s2 = version2.split(delim);
        
        int i = 0;
        int j = 0;
        
        while (i < s1.length || j < s2.length) {
            int i1 = 0;
            int i2 = 0;
            if (i < s1.length) {
                i1 = Integer.parseInt(s1[i]);
            }
            
            if (j < s2.length) {
                i2 = Integer.parseInt(s2[j]);
            }
            
            if (i1 == i2) {
                i++;
                j++;
            } else {
                return i1 - i2 < 0 ? -1 : 1;
            }
        }
        
        return 0;
    }
}

Leetcode: Intersection of Two Linked Lists

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

begin to intersect at node c1.

Notes:

• If the two linked lists have no intersection at all, return null.
• The linked lists must retain their original structure after the function returns.
• You may assume there are no cycles anywhere in the entire linked structure.
• Your code should preferably run in O(n) time and use only O(1) memory.

Understand the problem:
The key to understand the problem is when two linked lists have intersections, they will start "merging". 

The solution is first to calculate the length of the list. Move the head of the longer list by (lenA - lenB) steps. Then compare each node of the two lists. If equal, the intersection point was found. If reached to the end, means null.

Code (Java):

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        
        int lenA = getListLength(headA);
        int lenB = getListLength(headB);
        
        ListNode pA = headA;
        ListNode pB = headB;
        
        if (lenA > lenB) {
            for (int i = 0; i < lenA - lenB; i++) {
                pA = pA.next;
            }
        } else if (lenA < lenB) {
            for (int i = 0; i < lenB - lenA; i++) {
                pB = pB.next;
            }
        }
        
        while (pA != null && pB != null) {
            if (pA == pB) {
                return pA;
            } 
            pA = pA.next;
            pB = pB.next;
        }
        
        return null;
    }
    
    private int getListLength(ListNode head) {
        int len = 0;
        ListNode p = head;
        
        while (p != null) {
            len++;
            p = p.next;
        }
        
        return len;
    }
}

Leetcode: Group Shifted Strings

Given a string, we can "shift" each of its letter to its successive letter, for example: "abc" -> "bcd". We can keep "shifting" which forms the sequence:

"abc" -> "bcd" -> ... -> "xyz"

Given a list of strings which contains only lowercase alphabets, group all strings that belong to the same shifting sequence.

For example, given: ["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"],
Return:

[
  ["abc","bcd","xyz"],
  ["az","ba"],
  ["acef"],
  ["a","z"]
]

Note: For the return value, each inner list's elements must follow the lexicographic order.

Understand the problem:
The problem looks quite like the grouping anagrams. So the idea is the same: for each string, find out its "original" format, and check if the hash map contains this original string. If yes, put into the map. 

Code (Java):

public class Solution {
    public List<List<String>> groupStrings(String[] strings) {
        List<List<String>> result = new ArrayList<List<String>>();
        if (strings == null || strings.length == 0) {
            return result;
        }
        
        Arrays.sort(strings, new LexComparator());
        
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        
        for (String s : strings) {
            StringBuffer sb = new StringBuffer();
            int distance = Character.getNumericValue(s.charAt(0)) - 'a';
            for (int i = 0; i < s.length(); i++) {
                int val = Character.getNumericValue(s.charAt(i)) - distance;
                val = val < 'a' ? val + 26 : val;
                char ori = (char) val;
                sb.append(ori);
            }
            String original = sb.toString();
            if (map.containsKey(original)) {
                List<String> list = map.get(original);
                list.add(s);
                map.put(original, list);
            } else {
                List<String> list = new ArrayList<String>();
                list.add(s);
                map.put(original, list);
            }
        }
        
        // Iterate the map
        Iterator it = map.entrySet().iterator();
        while (it.hasNext()) {
            Map.Entry pair = (Map.Entry) it.next();
            result.add((List<String>) pair.getValue());
        }
        
        return result;
    }
    
    private class LexComparator implements Comparator<String> {
        @Override
        public int compare(String a, String b) {
            if (a.length() != b.length()) {
                return a.length() - b.length();
            }
            
            for (int i = 0; i < a.length(); i++) {
                if (a.charAt(i) != b.charAt(i)) {
                    return a.charAt(i) - b.charAt(i);
                }
            }
            return 0;
        }
    }
}

Update on 12/5/18:

class Solution {
    public List<List<String>> groupStrings(String[] strings) {
        List<List<String>> ans = new ArrayList<>();
        if (strings == null || strings.length == 0) {
            return ans;
        }
        
        Map<String, List<String>> map = new HashMap<>();
        
        for (String str : strings) {
            String key = findKey(str);
            if (map.containsKey(key)) {
                map.get(key).add(str);
            } else {
                List<String> list = new ArrayList<>();
                list.add(str);
                map.put(key, list);
            }
        }
        
        // iterate the map
        //
        for (List<String> value : map.values()) {
            ans.add(value);
        }
        
        return ans;
    }
    
    private String findKey(String str) {
        StringBuilder sb = new StringBuilder();
        
        int distance = str.charAt(0) - 'a';
        
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            char o = (char) (c - distance);
            if (o < 'a') {
                o = (char) (o + 26);
            }
            sb.append(o);
        }
        
        return sb.toString();
    }
}

Leetcode: One Edit Distance

http://buttercola.blogspot.com/2014/11/facebook-one-edit-distance.html

Given two strings S and T, determine if they are both one edit distance apart.
Understand the problem:
Note that the problem asks for EXACTLY one edit distance. There are several cases to consider:
  -- If the len1 - len2 > 1, return false; 
  -- We compare each character of the two strings. if not equal. 
   -- If len1 > len2, we move i++, which means delete one character from string1, e.g. abc, ac
   -- If len1 < len2, we move j++, which add one character for string1 (or delete one from string 2).
  --  If len1 == len2, i++, j++

Code (Java):

public class Solution {
    public boolean isOneEditDistance(String s, String t) {
        if ((s == null || s.length() == 0) && (t == null || t.length() == 0)) {
            return false;
        }
        
        if (s == null || s.length() == 0) {
            return t.length() == 1;
        }
        
        if (t == null || t.length() == 0) {
            return s.length() == 1;
        }
        
        if (Math.abs(s.length() - t.length()) > 1) {
            return false;
        }
        
        
        int count = 0;
        int i = 0;
        int j = 0;
        
        while (i < s.length() && j < t.length()) {
            if (s.charAt(i) != t.charAt(j)) {
                count++;
                if (count > 1) {
                    return false;
                }
                
                if (s.length() > t.length()) {
                    i++;
                } else if (s.length() < t.length()) {
                    j++;
                } else {
                    i++;
                    j++;
                }
            } else {
                i++;
                j++;
            }
        }
        
        if (i < s.length() || j < t.length()) {
            count++;
        }
        
        return count == 1;
    }
}

Summary:
The problem itself is not hard, but very tricky to get the OJ passed. Some tricks need to be very very careful:
1. If the length of the two words diff more than 1, directly return false;
2. At the end, we need to check if i < s.length() OR j < t.length(). That is because the problem asks for EXACTLY ONE edit distance. e.g. s = abc, t = ab, in this case. the count = 0. So we need to accumulate the count by 1 in that case. If the problem asks for edit distance which is LESS or EQUAL to 1, then we don't need to check that step.