LIKE CODING: Zenefits

Showing posts with label Zenefits. Show all posts

Tuesday, March 22, 2016

MJ [56] Longest String Chain

Given a set of strings, find the longest string chain. Two strings are chained if
1. both strings belong to the given set
2. the second string is generated by remove one letter in the first string
For example:
Given vector<string> w = {a,ba,bca,bda,bdca}, the longest string chain is bdca->bda->ba->a.

Solution:
Represent the string chain by a Trie like structure. Record the depth while building Trie.

bdca
| |
bda bca
| |
ba ba
|
a

=============
===============

Ref
[1] http://www.1point3acres.com/bbs/thread-131978-1-1.html

MJ [55] Best Merging Point

problem: robot merge point
input:
robot: 1
obstacle: X
[
0 0 0 M 1
0 1 X 0 0
0 X 0 0 0
0 0 0 1 0
0 0 0 0 0
]
output:
best merge point: M
3 + 1 + 3 = 7

======
For every robot, compute its shortest distance to every point. The best merge point is the point with the smallest distance sum over all the robots.

Thursday, February 4, 2016

MJ [53] Tree S Expression

Question:

You are given a binary tree as a sequence of parent-child pairs. For example, the tree represented by the node pairs below:

(A,B) (A,C) (B,G) (C,H) (E,F) (B,D) (C,E)

may be illustrated in many ways, with two possible representations below:

A / \ B C / \ / \G D E H \ F A / \ B C / \ / \D G H E / F

Below is the recursive definition for the S-expression of a tree:

S-exp(node) = ( node->val (S-exp(node->first_child))(S-exp(node->second_child))), if node != NULL
= "", node == NULL
where, first_child->val < second_child->val (lexicographically smaller)

This tree can be represented in a S-expression in multiple ways. The lexicographically smallest way of expressing this is as follows:

(A(B(D)(G))(C(E(F))(H)))

We need to translate the node-pair representation into an S-expression (lexicographically smallest one), and report any errors that do not conform to the definition of a binary tree.

The list of errors with their codes is as follows:

Error Code    Type of error
E1                More than 2 children
E2                Duplicate Edges
E3                Cycle present
E4                Multiple roots
E5                Any other error

Input Format:
Input must be read from standard input.
Input will consist of on line of parent-child pairs. Each pair consists of two node names separated by a single comma and enclosed in parentheses. A single space separates the pairs.

Output:
The function must write to standard output.
Output the given tree in the S-expression representation described above.

There should be no spaces in the output.

Constraints:

There is no specific sequence in which the input (parent,child) pairs are represented.
The name space is composed of upper case single letter (A-Z) so the maximum size is 26 nodes.
Error cases are to be tagged in the order they appear on the list. For example, if one input pair raises both error cases 1 and 2, the output must be E1.

Sample Input #00

(B,D) (D,E) (A,B) (C,F) (E,G) (A,C)

Sample Output #00

(A(B(D(E(G))))(C(F)))

Sample Input #01

(A,B) (A,C) (B,D) (D,C)

Sample Output #01

Explanation

Node D is both a child of B and a parent of C, but C and B are both child nodes of A. Since D tries to attach itself as parent to a node already above it in the tree, this forms a cycle.

===============
Ref
[1] http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=165923&extra=page%3D2%26filter%3Dsortid%26sortid%3D311%26sortid%3D311

MJ [52] subsquence combinations

Question:
String s1 = "waeginsapnaabangpisebbasepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc"
String s2 = "a+b+c-";

s2的形式是一个字母加上一个符号，正号代表有两个前面的字符，负号代表有四个，也就是说s2其实是"aabbcccc"，不考虑invalid。
在s1中，找出连续或者不连续的s2，也就是说从s1中找出"aa....bb.....cccc"，abc顺序不能变，但是之间可以有零个或多个字符，返回共有多少个。在上面这个例子中，有四个。

Wednesday, February 3, 2016

MJ [51] Pair in BST

Question:
http://www.geeksforgeeks.org/find-a-pair-with-given-sum-in-bst/

Monday, December 14, 2015

LeetCode [317] Shortest Distance from All Buildings

317. Shortest Distance from All Buildings

Hard

You want to build a house on an empty land which reaches all buildings in the shortest amount of distance. You can only move up, down, left and right. You are given a 2D grid of values 0, 1 or 2, where:

Each 0 marks an empty land which you can pass by freely.
Each 1 marks a building which you cannot pass through.
Each 2 marks an obstacle which you cannot pass through.

Example:

Input: [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]

1 - 0 - 2 - 0 - 1
|   |   |   |   |
0 - 0 - 0 - 0 - 0
|   |   |   |   |
0 - 0 - 1 - 0 - 0

Output: 7 

Explanation: Given three buildings at (0,0), (0,4), (2,2), and an obstacle at (0,2),
             the point (1,2) is an ideal empty land to build a house, as the total 
             travel distance of 3+3+1=7 is minimal. So return 7.

Note:
There will be at least one building. If it is not possible to build such house according to the above rules, return -1.

#define N 100
class Solution {
public:
    int shortestDistance(vector<vector<int>>& grid) {
        int m = grid.size();
        if(m==0) return 0;
        int n = grid[0].size();
        if(n==0) return 0;

        int nb = 0;//count the number of buildings
        for(int i=0; i<m; ++i){
            for(int j=0; j<n; ++j){
                if(grid[i][j]==1){
                    nb++;
                }
            }
        }

        int ret = INT_MAX;
        bool found = false;//is true of there exists a valid place which can reach all buildings

        //check every cell if it is not an obstacle, grid[i][j]==0 or 1
        //if grid[i][j]==0, this is an potential valid place 
        //if grid[i][j]==1, check if we can reach all other buildings from [i][j]. If not, ie., there exists another buildings [i', j'] 
        //such that grid[i'][j']==1 and [i, j] cannot reach [i', j'], thus, there mush not exist an valid place which can reach all buildings. 
        for(int i=0; i<m; ++i){
            for(int j=0; j<n; ++j){
                if(grid[i][j]==2) continue;//cannot pass through an obstacle
                bool visited[N][N] = {false};
                queue<vector<int>> que;
                int cnt = 0, dist = 0;
                vector<int> cor={i, j, 0};//row id, column id, current steps
                que.push(cor);
                visited[i][j] = true;
                while(!que.empty()){
                    int x = que.front()[0];
                    int y = que.front()[1];
                    int step = que.front()[2];
                    que.pop();
                    if(grid[x][y]==1){//found an buildings which can be reached from [i, j] in "step" steps
                        cnt++;
                        dist += step;
                    }

                    //continue bfs if 1) current place is empty; 2) current place is the original place
                    if(grid[x][y]==0||(i==x && j==y)){
                        if(x-1>=0 && grid[x-1][y]<2 && !visited[x-1][y]){vector<int> v = {x-1, y, step+1}; que.push(v); visited[x-1][y] = true;};
                        if(x+1<m  && grid[x+1][y]<2 && !visited[x+1][y]){vector<int> v = {x+1, y, step+1}; que.push(v); visited[x+1][y] = true;};
                        if(y-1>=0 && grid[x][y-1]<2 && !visited[x][y-1]){vector<int> v = {x, y-1, step+1}; que.push(v); visited[x][y-1] = true;};
                        if(y+1<n  && grid[x][y+1]<2 && !visited[x][y+1]){vector<int> v = {x, y+1, step+1}; que.push(v); visited[x][y+1] = true;};
                    }
                }

                //[i, j] is a buildings and it cannot reach all other buildings. Return -1.
                if(grid[i][j]==1 && cnt<nb) return -1;

                //[i, j] is an empty place and it can reach all buildings.
                if(cnt==nb && grid[i][j]==0){
                    found = true;
                    ret = min(ret, dist);
                }
            }
        }

        return found?ret:-1;
    }
};

public class Solution {
    public int shortestDistance(int[][] grid) {
        if (grid == null || grid[0].length == 0) return 0;
        final int[] shift = new int[] {0, 1, 0, -1, 0};
        
        int row  = grid.length, col = grid[0].length;
        int[][] distance = new int[row][col];
        int[][] reach = new int[row][col];
        int buildingNum = 0;
        
        for (int i = 0; i < row; i++) {
            for (int j =0; j < col; j++) {
                if (grid[i][j] == 1) {
                    buildingNum++;
                    Queue<int[]> myQueue = new LinkedList<int[]>();
                    myQueue.offer(new int[] {i,j});

                    boolean[][] isVisited = new boolean[row][col];
                    int level = 1;
                    
                    while (!myQueue.isEmpty()) {
                        int qSize = myQueue.size();
                        for (int q = 0; q < qSize; q++) {
                            int[] curr = myQueue.poll();
                            
                            for (int k = 0; k < 4; k++) {
                                int nextRow = curr[0] + shift[k];
                                int nextCol = curr[1] + shift[k + 1];
                                
                                if (nextRow >= 0 && nextRow < row && nextCol >= 0 && nextCol < col
                                    && grid[nextRow][nextCol] == 0 && !isVisited[nextRow][nextCol]) {
                                        //The shortest distance from [nextRow][nextCol] to thic building
                                        // is 'level'.
                                        distance[nextRow][nextCol] += level;
                                        reach[nextRow][nextCol]++;
                                        
                                        isVisited[nextRow][nextCol] = true;
                                        myQueue.offer(new int[] {nextRow, nextCol});
                                    }
                            }
                        }
                        level++;
                    }
                }
            }
        }
        
        int shortest = Integer.MAX_VALUE;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == 0 && reach[i][j] == buildingNum) {
                    shortest = Math.min(shortest, distance[i][j]);
                }
            }
        }
        
        return shortest == Integer.MAX_VALUE ? -1 : shortest;
        
        
    }
}

Wednesday, August 12, 2015

MJ [7] Sell Ticket

=======================

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

Friday, August 7, 2015

MJ [2]

Questions: Similar to LeetCode Permutation Sequence [1] except the numbers in nums are not unique. In Test, there are 4 numbers whose permutations are in increasing order, find the sequence number (1-based) of one of its permutation in the sequence. Eg., if nums=[2 1 2 3] it should return 4; if nums=[3 1 2 2] it should return 10.

Test:
1 2 2 3---1
1 2 3 2---2
1 3 2 2---3
2 1 2 3---4
2 1 3 2---5
2 2 1 3---6
2 2 3 1---7
2 3 1 2---8
2 3 2 1---9
3 1 2 2---10
3 2 1 2---11
3 2 2 1---12

============ =====================

Ref
[1] https://leetcode.com/problems/permutation-sequence/
[2] http://www.mitbbs.com/article_t/JobHunting/33021689.html
[3] http://www.mitbbs.com/article_t1/JobHunting/32952623_0_1.html
Zenefits MJ, replace numbers with chars.

Tuesday, July 7, 2015

LeetCode [229] Majority Element II

229. Majority Element II

Medium

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

Follow-up: Could you solve the problem in linear time and in O(1) space?

Example 1:

Input: nums = [3,2,3]
Output: [3]

Example 2:

Input: nums = [1]
Output: [1]

Example 3:

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

Constraints:

1 <= nums.length <= 5 * 104
-109 <= nums[i] <= 109

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        vector<int> ret;
        int n1, c1 = 0, n2, c2 = 0;
        for(auto n:nums){
            if(c1>0 && n==n1){
                c1++;
            }else if(c2>0 && n==n2){
                c2++;
            }else if(c1==0){
                c1++; n1 = n;
            }else if(c2==0){
                c2++; n2 = n;
            }else{
                c1--; c2--;
            }
        }

        int t1 = 0, t2 = 0, n = nums.size();
        for(auto n:nums){
            if(c1>0 && n==n1) t1++;
            if(c2>0 && n==n2) t2++;
        }
        if(t1>n/3) ret.push_back(n1);
        if(t2>n/3) ret.push_back(n2);
        return ret;
    }
};

Thursday, February 19, 2015

LeetCode [168] Excel Sheet Column Title

168. Excel Sheet Column Title

Easy

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 
    ...

Example 1:

Input: 1
Output: "A"

Example 2:

Input: 28
Output: "AB"

Example 3:

Input: 701
Output: "ZY"

===

//there's no "0", so we -1 every iteration
class Solution {
    public String convertToTitle(int n) {
        String s = "";
        n--;
        while(n>=0){
            int t = (n)%26;
            char c = (char)('A'+t);
            s = c+s;
            n = (n)/26-1;
        }
        return s;
    }
}