LIKE CODING: Facebook

Showing posts with label Facebook. Show all posts

Saturday, March 12, 2016

LeetCode [336] Palindrome Pairs

Tuesday, December 8, 2015

LeetCode [314] Binary Tree Vertical Order Traversal

Given a binary tree, return the vertical order traversal of its nodes' values. (ie, from top to bottom, column by column).

If two nodes are in the same row and column, the order should be from left to right.

Examples 1:

Input: [3,9,20,null,null,15,7]

   3
  /\
 /  \
 9  20
    /\
   /  \
  15   7 

Output:

[
  [9],
  [3,15],
  [20],
  [7]
]

Examples 2:

Input: [3,9,8,4,0,1,7]

     3
    /\
   /  \
   9   8
  /\  /\
 /  \/  \
 4  01   7 

Output:

[
  [4],
  [9],
  [3,0,1],
  [8],
  [7]
]

Examples 3:

Input: [3,9,8,4,0,1,7,null,null,null,2,5] (0's right child is 2 and 1's left child is 5)

     3
    /\
   /  \
   9   8
  /\  /\
 /  \/  \
 4  01   7
    /\
   /  \
   5   2

Output:

[
  [4],
  [9,5],
  [3,0,1],
  [8,2],
  [7]
]

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> verticalOrder(TreeNode* root) {
        int l = 0, r = 0;
        vector<vector<int>> ret;
        if(!root) return ret;
        
        ret.resize(1);
        queue<pair<TreeNode*, int>> que;//node. column index
        que.push(make_pair(root, 0));
        while(!que.empty())
        {
            TreeNode *node = que.front().first;
            int index = que.front().second;
            que.pop();
            if(index<l)
            {
                l--;
                ret.insert(ret.begin(), vector<int>());
            }
            else if(index>r)
            {
                r++;
                ret.insert(ret.end(), vector<int>());
            }
            ret[index-l].push_back(node->val);
            if(node->left) que.push(make_pair(node->left, index-1));
            if(node->right) que.push(make_pair(node->right, index+1));
        }
        return ret;
    }
};

Thursday, November 5, 2015

LeetCode [301] Remove Invalid Parentheses

301. Remove Invalid Parentheses

Hard

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note: The input string may contain letters other than the parentheses ( and ).

Example 1:

Input: "()())()"
Output: ["()()()", "(())()"]

Example 2:

Input: "(a)())()"
Output: ["(a)()()", "(a())()"]

Example 3:

Input: ")("
Output: [""]

class Solution {
    bool isvalid(string s){
        int cnt = 0;
        for(auto c:s){
            cnt += c=='(';
            cnt -= c==')';
            if(cnt<0) return false;
        }
        return cnt==0;
    }
public:
    vector<string> removeInvalidParentheses(string s) {
        int l = 0, r = 0;
        for(auto c:s){
            if(c=='(') l++;
            else{
                if(l==0) r += (c==')');
                else l -= (c==')');                
            }
        }      
        vector<string> ret;
        dfs(s, ret, 0, l, r);
        return ret;
    }
    
    void dfs(string s, vector<string>&ret, int pos, int l, int r){
        if(l==0 && r==0 && isvalid(s)){
            ret.push_back(s);
            return;
        }
        
        for(int i=pos; i<s.size(); ++i){
            if(i>pos && s[i]==s[i-1]) continue;
            if(!(s[i]=='(' && l>0 || s[i]==')' && r>0)) continue;
            string s1 = s;
            
            s1.erase(i, 1);
            if(s[i]=='(' && l>0) dfs(s1, ret, i, l-1, r);
            else if(s[i]==')' && r>0) dfs(s1, ret, i, l, r-1);
        }
    }
};

http://zxi.mytechroad.com/blog/string/leetcode-301-remove-invalid-parentheses/

Monday, October 26, 2015

LeetCode [297] Serialize and Deserialize Binary Tree

297. Serialize and Deserialize Binary Tree

Hard

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Clarification: The input/output format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Example 1:

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

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [1]
Output: [1]

Example 4:

Input: root = [1,2]
Output: [1,2]

Constraints:

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

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
    void serialize(TreeNode* node, stringstream &ss){
        if(!node)
        {
            ss<<"# ";
        }
        else
        {
            ss<<node->val<<" ";
            serialize(node->left, ss);
            serialize(node->right, ss);
        }
    }
    
    TreeNode* deserialize(stringstream &ss)
    {
        string s;
        ss>>s;
        if(s=="#"){
            return NULL;
        }else{
            TreeNode* node = new TreeNode(stoi(s));
            node->left = deserialize(ss);
            node->right = deserialize(ss);
            return node;
        }
    }
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        stringstream ss;
        serialize(root, ss);
        return ss.str();
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        stringstream ss;
        ss<<data;
        return deserialize(ss);
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {
    String str;
    String[] strs;
    int index = 0;
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        str = "";
        sh(root);
        return str;
    }
    
    void sh(TreeNode node){
        if(str.length()>0) str += ",";
        if(node==null){
            str += "#";
        }else{
            str += node.val;
            sh(node.left);
            sh(node.right);
        }
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        strs = data.split(",");
        index = 0;
        return dh();
    }
    
    TreeNode dh(){
        TreeNode node;
        String s = strs[index++];
        if(s.equals("#")){
            node = null;
        }else{
            node = new TreeNode(Integer.parseInt(s));
            node.left = dh();
            node.right = dh();
        }
        return node;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));

Thursday, September 24, 2015

MJ [40] Count squares

Question:
Given a set of points, find all squares composed by four points of the set.

Ref
[1] http://www.mitbbs.com/article_t1/JobHunting/32968629_0_1.html
[2] https://www.codechef.com/problems/D6
[3] https://www.quora.com/Given-two-diagonally-opposite-points-of-a-square-how-can-I-find-out-the-other-two-points-in-terms-of-the-coordinates-of-the-known-points

Saturday, September 19, 2015

MJ [39] Valid Parentheses

Question:
Given a string with parentheses, return a string with balanced parentheses by removing the fewest characters possible. You cannot add anything to the string.
Examples:
balance("()") -> "()"
balance(")(") -> "".
balance("(((((") -> ""
balance("(()()(") -> "()()"
balance(")(())(") -> "(())"
Note：balance(")(())(") != "()()"

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

Friday, September 18, 2015

MJ [38] Target Sum

Question:
Given an array A, determine if there is a subarray with sum equal to a given target.
Eg., if A = {4, 7, -5, 6, -2, 1} and target = 8. It should return true because sum{7, -5, 6} = 8. If target = 3, it should return false.

Ref
[1] http://www.mitbbs.com/article_t/JobHunting/32957899.html
[2] http://www.geeksforgeeks.org/find-if-there-is-a-subarray-with-0-sum/

LeetCode [283] Move Zeroes

283. Move Zeroes

Easy

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Example:

Input: [0,1,0,3,12]
Output: [1,3,12,0,0]

Note:

You must do this in-place without making a copy of the array.
Minimize the total number of operations.

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n = nums.size(), i = 0, j = 0;
        while(j<n){
            while(j<n && nums[j]==0) j++;
            if(j<n) nums[i++] = nums[j++];
        }
        while(i<n){
            nums[i++] = 0;
        }
    }
};

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n = nums.size();
        int i = 0, j = 0;
        
        while(j<n){
            while(j<n && nums[j]==0){ 
                j++;
            }
            while(j<n && nums[j]!=0){
                nums[i++] = nums[j++];
            }
        }
        fill(nums.begin()+i, nums.end(), 0);
    }
};

class Solution {
    public void moveZeroes(int[] nums) {
        int n = nums.length;
        int i = 0, j = 0;
        while(i<n){
            if(nums[i]==0){
                i++;
            }else{
                nums[j] = nums[i];
                i++;
                j++;
            }
        }
        
        while(j<n){
            nums[j] = 0;
            j++;
        }
    }
}

Tuesday, September 1, 2015

MJ [36] Arrange Keys

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

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

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

Saturday, August 15, 2015

MJ [10] CanView Design

Question:
Design a system to meet the following requirements:
boolean CanView(Viewer, Object, Owner);
Return true if viewer can read object of owner; otherwise return false.

object has one property which can be public or friends. If it is public, viewer can read object; if it is friends, only friend of owner can read object.

Ref
[1] http://www.mitbbs.com/article_t/JobHunting/33022171.html
[2] http://stackoverflow.com/questions/8663072/database-design-for-social-network-friends-list-friends-circle-post-sharing

Friday, August 7, 2015

LeetCode [253] Meeting Rooms II

253. Meeting Rooms II

Medium

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.

Example 1:

Input: [[0, 30],[5, 10],[15, 20]]
Output: 2

Example 2:

Input: [[7,10],[2,4]]
Output: 1

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

//C++: 584ms
bool myComp(const Interval &a, const Interval &b){
    return (a.start<b.start);
}
class Solution {
public:
    int minMeetingRooms(vector<interval>& intervals) {
        int rooms = 0;
        priority_queue<int> pq;//prioritize earlier ending time
        sort(intervals.begin(), intervals.end(), myComp);
        for(int i=0; i<intervals.size(); ++i){
            while(!pq.empty() && -pq.top()<intervals[i].end) pq.pop();
            pq.push(-intervals[i].end);
            rooms = max(rooms, (int)pq.size());
        }
        return rooms;
    }
};

//C++
//C++: 616ms
/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    int minMeetingRooms(vector<Interval>& intervals) {
        map<int, int> changes;//sorted by keys.
        for(auto i:intervals){
            changes[i.start]++;
            changes[i.end]--;
        }
        int rooms = 0, min_rooms = 0;
        for(auto c:changes){
            rooms += c.second;
            min_rooms = max(min_rooms, rooms);
        }
        return min_rooms;
    }
};

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for(int i=0; i<intervals.length; ++i){
            map.put(intervals[i][0], map.getOrDefault(intervals[i][0], 0)+1);
            map.put(intervals[i][1], map.getOrDefault(intervals[i][1], 0)-1);
        }
        int rooms = 0, minRooms = 0;
        for(Map.Entry<Integer,Integer> e : map.entrySet()){
            rooms += e.getValue();
            minRooms = Math.max(minRooms, rooms);
        }
        return minRooms;
    }
}

YMSF

第二轮，白人manager，刷题网尔无伞的变形，要求自定义输入的数据，并且返回一个schedule（自定义输出格式）。我这轮执着于原题解法，总是想用priority queue，写的磕磕巴巴，面完回去想了想用dict记录每个房间和能放在这个房间的所有会议起始时间就行。。最后问了问怎么测试，测试数据从哪来。。等等，就到时间了，这轮应该是给了个比较差的feedback。