181. Employees Earning More Than Their Managers

The Employee table holds all employees including their managers. Every employee has an Id, and there is also a column for the manager Id.
+----+-------+--------+-----------+
| Id | Name  | Salary | ManagerId |
+----+-------+--------+-----------+
| 1  | Joe   | 70000  | 3         |
| 2  | Henry | 80000  | 4         |
| 3  | Sam   | 60000  | NULL      |
| 4  | Max   | 90000  | NULL      |
+----+-------+--------+-----------+

Given the Employee table, write a SQL query that finds out employees who earn more than their managers. For the above table, Joe is the only employee who earns more than his manager.

+----------+
| Employee |
+----------+
| Joe      |
+----------+

Thoughts:

Self  Join, nothing special


# Write your MySQL query statement below
SELECT e1.Name as Employee FROM Employee e1  LEFT JOIN Employee e2 on e2.id =  e1.ManagerId WHERE e2.Salary < e1.Salary;

 

104. Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its depth = 3.


Thought:

Nothing special but..

I’m using Java this time..


 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        return maxDepthHelper(root, 0);
    }
     public int maxDepthHelper(TreeNode node, int depth) {
        if(node != null){
            return Math.max(maxDepthHelper(node.left, depth+1)
                       , maxDepthHelper(node.right, depth+1));
        }
         return depth;
    }
}

 

859. Buddy Strings

Given two strings A and B of lowercase letters, return true if and only if we can swap two letters in A so that the result equals B.

 

Example 1:

Input:

A = "ab", B = "ba"

Output:

true

Example 2:

Input:

A = "ab", B = "ab"

Output:

false

Example 3:

Input:

A = "aa", B = "aa"

Output:

true

Example 4:

Input:

A = "aaaaaaabc", B = "aaaaaaacb"

Output:

true

Example 5:

Input:

A = "", B = "aa"

Output:

false

 

Note:

  1. 0 <= A.length <= 20000
  2. 0 <= B.length <= 20000
  3. A and B consist only of lowercase letters.

Two cases:

  1. Exactly two chars are different, and two strings are same with these chars swapped
  2. Two strings are exactly same, the string has duplicate char, so we can pretend to have a swap.

 

class Solution {

    /**
     * @param String $A
     * @param String $B
     * @return Boolean
     */
    function buddyStrings($A, $B) {
        if(empty($A) || empty($B) || count($A) !== count($B)){
            return false;
        }
        
        if($A == $B){
            if(strlen(count_chars($A, 3)) != strlen($A)){
                // Check is there're duplicate chars
                return true;
            }
        }
        
        $diff_a = [];
        $diff_b = [];
        
        
        for($i = 0; $i < strlen($A); $i ++){
            if($A[$i] !== $B[$i]){
                $diff_a[] = $A[$i];
                $diff_b[] = $B[$i];
            }
        }

        return  count($diff_b) == 2
            && $diff_a[1] == $diff_b[0] 
            && $diff_a[0] == $diff_b[1]; 
    }
}

 

884. Uncommon Words from Two Sentences

We are given two sentences A and B.  (A sentence is a string of space separated words.  Each word consists only of lowercase letters.)

A word is uncommon if it appears exactly once in one of the sentences, and does not appear in the other sentence.

Return a list of all uncommon words.

You may return the list in any order.

 

Example 1:

Input: A = "this apple is sweet", B = "this apple is sour"
Output: ["sweet","sour"]

Example 2:

Input: A = "apple apple", B = "banana"
Output: ["banana"]

 

Note:

  1. 0 <= A.length <= 200
  2. 0 <= B.length <= 200
  3. A and B both contain only spaces and lowercase letters.
Runtime: 8 ms
Memory Usage: 14.9 MB
class Solution {

    /**
     * @param String $A
     * @param String $B
     * @return String[]
     */
    function uncommonFromSentences($A, $B) {
        $x = []; $y = [];
        foreach(explode(' ',$A) as $aa) {
            $this->add($x, $aa);
        }
        foreach(explode(' ',$B) as $bb) {
            $this->add($y, $bb);
        }
        $this->rmCommon($x, $y);
        $x = array_keys($x);
        $y = array_keys($y);
        return array_merge(array_diff($x,$y), array_diff($y, $x));
    }
    
    function add(&$arr, $v){
        if(isset($arr[$v])){
            $arr[$v] ++;
        } else {
            $arr[$v] = 1;
        }
    }
                
    function rmCommon(&$a,&$b){
        foreach($a as $k => $v){
            if ($v > 1){
                unset ($a[$k]);
                unset ($b[$k]);
            }
        }
        foreach($b as $k => $v){
            if ($v > 1){
                unset ($b[$k]);
                unset ($a[$k]);
            }
        }
    }
}

 

 

994. Rotting Oranges

In a given grid, each cell can have one of three values:

the value 0 representing an empty cell;
the value 1 representing a fresh orange;
the value 2 representing a rotten orange.
Every minute, any fresh orange that is adjacent (4-directionally) to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1 instead.

Example 1:

Input: [[2,1,1],[1,1,0],[0,1,1]]
Output: 4
Example 2:

Input: [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.
Example 3:

Input: [[0,2]]
Output: 0
Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.

Note:

1 <= grid.length <= 10
1 <= grid[0].length <= 10
grid[i][j] is only 0, 1, or 2.

24 ms 38.6 MB

class Solution {
    public int orangesRotting(int[][] grid) {
        if(this.nothing(grid)){
            return 0;
        }
        if(this.neverR(grid)){
            return -1;
        }
        
        int count = 0;
        while(!this.isAllR(grid)){
            grid = this.infect(grid);

            count ++;
            if(count > grid.length * grid[0].length){
                return -1;
            }
        }
        return count;
    }
    
    public int[][] infect(int[][] grid){
        int[][] next = new int[grid.length][grid[0].length];
        for(int x  = 0; x < grid.length; x ++){
            for(int y = 0; y < grid[0].length; y++){
                next[x][y] = grid[x][y];
            }
        }
        for(int x  = 0; x < grid.length; x ++){
            for(int y = 0; y < grid[0].length; y++){
                if(grid[x][y] == 2){
                    if(x>0 && next[x-1][y] > 0){
                        next[x-1][y] = 2;
                    }
                    if(y>0 && next[x][y-1] > 0){
                        next[x][y-1] = 2;
                    }
                    if(x< grid.length-1 && next[x+1][y] > 0){
                        next[x+1][y] = 2;
                    }
                    if(y < grid[0].length - 1 && next[x][y+1] > 0){
                        next[x][y+1] = 2;
                    }
                }
            }
        }
        return next;
    }
    
    public boolean isAllR(int[][] grid){
        boolean allR = true;
        for (int[] col : grid){
            for (int c : col){
                if(c == 1){
                    allR = false;
                }
            }
        }
        return allR;
    }
    
    public boolean neverR(int[][] grid){
        boolean allFresh = true;
        for(int x  = 0; x < grid.length; x ++){
            for(int y = 0; y < grid[0].length; y++){

                if(grid[x][y] == 2){
                    allFresh = false;
                }
                
                if(grid[x][y] == 1){
                    
                    boolean alone = true;
                    if(x>0 && grid[x-1][y] != 0){
                        alone = false;
                    }
                    if(y>0 && grid[x][y-1] != 0){
                        alone = false;
                    }
                    if(x< grid.length-1 && grid[x+1][y] != 0){
                        alone = false;
                    }
                    if(y < grid[0].length - 1 && grid[x][y+1] != 0){
                        alone = false;
                    }
                    System.out.println(alone);
                    if(alone){
                        return true;
                    }
                }
            }
        }
        return allFresh;
    }
    
    
    public boolean nothing(int[][] grid){
        boolean nothing = true;
        for(int x  = 0; x < grid.length; x ++){
            for(int y = 0; y < grid[0].length; y++){

                if(grid[x][y] > 0){
                    nothing = false;
                }

            }
        }
        return nothing;
    }
}