LIKE CODING: August 2015

Monday, August 31, 2015

MJ [35] Print Tree Vertically

Ref
[1] http://www.geeksforgeeks.org/print-binary-tree-vertical-order/
Question
[2] http://www.mitbbs.com/article_t1/JobHunting/32925369_0_1.html

Sunday, August 30, 2015

LeetCode [273] Integer to English Words

Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 231 - 1.

Example 1:

Input: 123
Output: "One Hundred Twenty Three"

Example 2:

Input: 12345
Output: "Twelve Thousand Three Hundred Forty Five"

Example 3:

Input: 1234567
Output: "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

Example 4:

Input: 1234567891
Output: "One Billion Two Hundred Thirty Four Million Five Hundred Sixty Seven Thousand Eight Hundred Ninety One"

class Solution {
    vector<string> lessThan20, tens, thousands;
public:
    string numberToWords(int num) {
        if(num==0) return "Zero";
        lessThan20 = vector<string>{"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
        tens = vector<string>{"", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
        string ret = helper(num);
        string s;
        for(int i=0; i<ret.size(); ++i)
        {
            if((i>0 && ret[i]==' ' && ret[i-1]==' ') || (i==ret.size()-1 && ret[i]==' ')) continue;
            else s += ret[i];
        }
        return s;
    }

    string helper(int num)
    {
        if(num < 20) return lessThan20[num];
        else if(num<100){
            return tens[num/10] + " " + helper(num%10);
        }else if(num<1000)
        {
            return lessThan20[num/100] + " " + "Hundred" + " " + helper(num%100);
        }else if(num<1000000)
        {
            return helper(num/1000) + " " + "Thousand" + " " + helper(num%1000);
        }else if(num<1000000000)
        {
            return helper(num/1000000) + " " + "Million" + " " + helper(num%1000000);
        }else
        {
            return helper(num/1000000000) + " " + "Billion" + " " + helper(num%1000000000);
        }
    }
};

class Solution {
    Map<Integer, String> map = new HashMap<>();
    public String numberToWords(int num) {
        map.put(0, "Zero");
        map.put(1, "One");
        map.put(2, "Two");
        map.put(3, "Three");
        map.put(4, "Four");
        map.put(5, "Five");
        map.put(6, "Six");
        map.put(7, "Seven");
        map.put(8, "Eight");
        map.put(9, "Nine");
        map.put(10, "Ten");
        map.put(11, "Eleven");
        map.put(12, "Twelve");
        map.put(13, "Thirteen");
        map.put(14, "Fourteen");
        map.put(15, "Fifteen");
        map.put(16, "Sixteen");
        map.put(17, "Seventeen");
        map.put(18, "Eighteen");
        map.put(19, "Nineteen");
        map.put(20, "Twenty");
        map.put(30, "Thirty");
        map.put(40, "Forty");
        map.put(50, "Fifty");
        map.put(60, "Sixty");
        map.put(70, "Seventy");
        map.put(80, "Eighty");
        map.put(90, "Ninety");
        map.put(100, "Hundred");
        map.put(1000, "Thousand");
        map.put(1000000, "Million");
        map.put(1000000000, "Billion");

        return helper(num);
    }

    String toString(int gra, int num){
        int cnt = num/gra;
        String s = helper(cnt) + " " + map.get(gra) ;
        int r = num%gra;
        if(r>0) s += " " + helper(r);
        return s;
    }

    String helper(int num){
        String s = "";
        if(num<=20) return map.get(num);
        else if(num<100){//(20, 100)
            int r = num%10;
            s = map.get(num-r);
            if(r>0) s += " " + helper(r);
            return s;
        }else if(num<1000){//[10 , 1000)
            s = toString(100, num);
        }else if(num<1000000){//[1000, 1000000)
            s = toString(1000, num);
        }else if(num<1000000000){//[1000000, 1000000000)
            s = toString(1000000, num);
        }else{//[1000000000, 
            s = toString(1000000000, num);
        }
        return s;
    }
}

Implement HashMap

class LinkedHashEntry{
public:
    int key;
    int value;
    LinkedHashEntry *next;
    LinkedHashEntry(int k, int v):key(k), value(v), next(NULL){}
};

class HashMap{
public:
    int sz;
    LinkedHashEntry ** table;
    HashMap(int s):sz(s){
        table = new LinkedHashEntry *[sz];
        for(int i=0; i<sz; ++i){
            table[i] = NULL;
        }
    }

    void set(int key, int value){
        int index = key%sz;
        LinkedHashEntry *entry = table[index];
        if(entry == NULL){
            table[index] = new LinkedHashEntry(key, value);
        }else{
            LinkedHashEntry *prev;
            while(entry && entry->key != key){
                prev = entry;
                entry = entry->next;
            }
            if(!entry){
                prev->next = new LinkedHashEntry(key, value);
            }else{
                entry->value = value;
            }
        }
    }

    int get(int key){
        int index = key%sz;
        LinkedHashEntry *entry = table[index];
        if(entry == NULL){
            cout<<"not exist\n";
        }else{
            while(entry && entry->key != key){
                entry = entry->next;
            }
            if(entry){
                return entry->value;
            }else{
                cout<<"not exist\n";
            }
        }
        return -1;
    }

    void resize(){
        int old_sz = sz;
        sz = sz*2;
        LinkedHashEntry ** old_table = table;
        table = new LinkedHashEntry *[sz];
        for(int i=0; i<sz; ++i) table[i] = NULL;
        for(int i=0; i<old_sz; ++i){
            LinkedHashEntry *entry = old_table[i];
            while(entry){
                set(entry->key, entry->value);
                LinkedHashEntry * old_entry = entry;
                entry = entry->next;
                delete old_entry;
            }
        }
    }
};

Output:
64
256
not exist
-1
new size is 256
64
256
not exist
-1

Ref
[1] http://www.algolist.net/Data_structures/Hash_table/Chaining
[2] http://www.algolist.net/Data_structures/Hash_table/Dynamic_resizing

LeetCode [272] Closest Binary Search Tree Value II

Ref
[1] https://leetcode.com/problems/closest-binary-search-tree-value-ii/
[2] https://leetcode.com/discuss/55240/ac-clean-java-solution-using-two-stacks

MJ [32] Iterate a nested array (Deep Iterator)

Question:
Write an iterator to iterate a nested array. For example, for given array:

[1,2,[3,[4,5],[6,7],8],9,10]

call iterator.next() 10 times should return 1,2,3,4,5,6,7,8,9,10.

Dark nodes are of TYPE_NESTED. Numbered nodes are of TYPE_ITEM.

Ref

[1] http://www.mitbbs.com/article_t/JobHunting/33037695.html

Saturday, August 29, 2015

Question:
Given a grid with 'o' and 'x'. Find minimum steps from top-left to bottom-right without touching 'x'.
a) You can only move right or move down. (BFS or DP) (m+n-2)?
b) You can move in all 4 directions. (BFS)

Ref
[1] http://www.mitbbs.com/article_t/JobHunting/33037695.html

MJ [30] Longest Words in a Dictionary

Question:
Find the longest words in a dictionary of legal words that can be constructed from a given list of letters. The dictionary is give by ospd.txt.
$ ./test ospd.txt i g h l p r a
ret :argil glair grail graph hilar laigh phial pilar ralph
ret_trie:argil glair grail graph hilar laigh phial pilar ralph

Ref

[1] https://www.reddit.com/r/Python/comments/n3arf/python_quiz_of_the_week_1/
[2] http://codereview.stackexchange.com/questions/6634/longest-words-in-dictionary-that-can-be-constructed-from-a-list-of-letters

Friday, August 28, 2015

LeetCode [271] Encode and Decode Strings

271. Encode and Decode Strings

Medium

Design an algorithm to encode a list of strings to a string. The encoded string is then sent over the network and is decoded back to the original list of strings.

Machine 1 (sender) has the function:

string encode(vector<string> strs) {
  // ... your code
  return encoded_string;
}

Machine 2 (receiver) has the function:

vector<string> decode(string s) {
  //... your code
  return strs;
}

So Machine 1 does:

string encoded_string = encode(strs);

and Machine 2 does:

vector<string> strs2 = decode(encoded_string);

strs2 in Machine 2 should be the same as strs in Machine 1.

Implement the encode and decode methods.

Note:

The string may contain any possible characters out of 256 valid ascii characters. Your algorithm should be generalized enough to work on any possible characters.
Do not use class member/global/static variables to store states. Your encode and decode algorithms should be stateless.
Do not rely on any library method such as eval or serialize methods. You should implement your own encode/decode algorithm.

//C++: 92ms
typedef unsigned char uchar;

class Codec {
public:

    // Encodes a list of strings to a single string.
    string encode(vector<string>& strs) {
        string ret;
        for(auto s:strs){
            int i = 0, len = s.size(), cnt;
            while(i<len){
                cnt = 1;
                uchar c = s[i++];
                while(i<len && (uchar)s[i]==c && cnt<254){
                    i++; cnt++;
                }
                ret += (uchar)cnt;
                ret += c;
            }
            ret += (uchar)255;
        }
        return ret;
    }

    // Decodes a single string to a list of strings.
    vector<string> decode(string s) {
        vector<string> ret;
        string cur;
        int i=0, len = s.size();
        while(i<len){
            uchar c = s[i++];
            if(c==(uchar)255){
                ret.push_back(cur);
                cur.clear();
            }else{
                int cnt = c;
                c = s[i++];
                for(int i=0; i<cnt; ++i) cur += c;
            }
        }
        return ret;
    }
};

public class Codec {
	// Encodes a list of strings to a single string.
    public String encode(List<String> strs) {
        StringBuilder sb = new StringBuilder();
        for(String s : strs) {
            sb.append(s.length()).append('/').append(s);
        }
        return sb.toString();
    }

    // Decodes a single string to a list of strings.
    public List<String> decode(String s) {
        List<String> ret = new ArrayList<String>();
        int i = 0;
        while(i < s.length()) {
            int slash = s.indexOf('/', i);
            int size = Integer.valueOf(s.substring(i, slash));
            i = slash + size + 1;
            ret.add(s.substring(slash + 1, i));
        }
        return ret;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.decode(codec.encode(strs));

Thursday, August 27, 2015

MJ [28] Largest Rectangle with Budget K

Question:
Given an N x N parcels in city, matrix M contains the cost of each parcel; Write code to find largest rectangular area in the city you can afford with budget K. Note that all the costs are non-negative.

Ref
[1] http://www.mitbbs.com/article_t/JobHunting/33032299.html
[2] http://likemyblogger.blogspot.com/2015/08/mj-26-maximum-sum-rectangle-in-2d-matrix.html

Wednesday, August 26, 2015

MJ [27] Find Alibaba

Question:
A thief steals from n houses denoted from 0 to n-1. To avoid to be caught, the thief cannot stay in the same house in two successive days and can only move to the left or right house on the next day. For example, if the thief steals house 5 on day 8, he must move to house 4 or 6 one day 9.

The police is trying to catch the thief with a strategy. strategy[i] (i=0,...,k-1) indicates the house to be searched on day i. The police catches the thief if they are in the same house on the same day. Write a program to determine whether the police can catch the thief by the strategy.

Ref
[1] http://www.mitbbs.com/article_t1/JobHunting/32978937_0_1.html

LeetCode [270] Closest Binary Search Tree Value

270. Closest Binary Search Tree Value

Easy

Given the root of a binary search tree and a target value, return the value in the BST that is closest to the target.

Example 1:

Input: root = [4,2,5,1,3], target = 3.714286
Output: 4

Example 2:

Input: root = [1], target = 4.428571
Output: 1

Constraints:

The number of nodes in the tree is in the range [1, 104].
0 <= Node.val <= 109
-109 <= target <= 109

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int value = -1;
    public int closestValue(TreeNode root, double target) {
        helper(root, target);
        return value;
    }
    
    void helper(TreeNode node, double target){
        if(node==null) return;
        if(value == -1 || Math.abs(value-target)>Math.abs(node.val-target)){
            value = node.val;
        }
        if(target<node.val) helper(node.left, target);
        if(target>node.val) helper(node.right, target);
    }
}