Mock Interview: Facebook #3

Simplify Path

class Solution {
    public String simplifyPath(String path) {
        String[] dir = path.split("/");
        
        String result = "";
        ArrayDeque<String> q = new ArrayDeque<String>();
        
        for (int i = 0; i < dir.length; i++) {
            if (dir[i].equals(".."))  {
                if (!q.isEmpty()) {
                    q.removeLast();
                }
            } else if (dir[i].equals(".")) {
                continue;
            } else if (dir[i].equals("")) {
                continue; 
            } else {
                q.addLast(dir[i]);
            }
        }
        
        System.out.println(q);
        
        if (q.isEmpty()) {
            return "/";
        }
        
        while (! q.isEmpty()) {
            result = result + "/" + q.removeFirst();
        }
        
        return result; 
    }
}

Runtime: 10 ms, faster than 13.10% of Java online submissions for Simplify Path.
Memory Usage: 39.2 MB, less than 41.99% of Java online submissions for Simplify Path.

런타임 진심 핵구리다는점...^^

"/"로 split 하고 if statement 냅다 넣어
ArrayDeque가 생각나서 이걸 썼는데.. 스택 써서 POP도 가능하긴 합니다^^..하지만 그럼 끝에 reverse를 해야 한다는 점~~

Stringbuilder로 만드니깐

Runtime: 6 ms, faster than 43.58% of Java online submissions for Simplify Path.
Memory Usage: 39 MB, less than 55.12% of Java online submissions for Simplify Path.

훅 빨라지네요~~

거기에 stack까지 쓰면

Runtime: 3 ms, faster than 95.64% of Java online submissions for Simplify Path.
Memory Usage: 39.2 MB, less than 41.99% of Java online submissions for Simplify Path.

진짜 빨라진다는점
==> 루션이 보니깐 거꾸로 다 pop 한 후에 다시 거꾸로 붙이는게 아니라 그냥 for loop을 쓰면 앞에서 뒤로 가네요.. 완전 신기루

Closest Binary Search Tree Value

/**
 * 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 {
    public int closestValue(TreeNode root, double target) {
        int curMax = root.val;
        TreeNode cur = root;
        
        while (cur != null) {
            curMax = (Math.abs(target - (double) curMax) < Math.abs(target - (double) cur.val)) ? curMax : cur.val;
            
            if (cur.val < target) {
                cur = cur.right;
            } else {
                cur = cur.left; 
            }
        }
        
        return curMax; 
    }
}

Runtime: 0 ms, faster than 100.00% of Java online submissions for Closest Binary Search Tree Value.
Memory Usage: 39.2 MB, less than 23.19% of Java online submissions for Closest Binary Search Tree Value.

크기 비교해서 가장 작은 숫자를 curMax로 잡아주고
treenode val을 원래 찾던 값과 비교해서 더 비슷한 쪽으로 찾아가는 방식