Medium

Implement a trie with insert, search, and startsWith methods. Example: Trie trie = new Trie(); trie.insert(“apple”); trie.search(“apple”); // returns true trie.search(“app”); // returns false trie.startsWith(“app”); // returns true trie.insert(“app”); trie.search(“app”); // returns true Note: You may assume that all inputs are consist of lowercase letters a-z. All inputs are guaranteed to be non-empty strings. Solution: class Trie { Trie[] children = new Trie[26]; boolean isLeaf = false; /** Initialize your data structure here. */ public Trie() { } /** Inserts a word into the trie. */ public void insert(String word) { Trie node = this; for (int i = 0; i < word.length(); i++) { char c = word.charAt(i); if (node.children[c - 'a'] == null) { node.children[c - 'a'] = new Trie();; } node = node.children[c - 'a']; } node.isLeaf = true; } /** Returns if the word is in the trie. */ public boolean search(String word) { Trie node = this; for (int i = 0; i < word.length(); i++) { char c = word.charAt(i); node = node.children[c - 'a']; if (node == null) { return false; } } return node.isLeaf; } /** Returns if there is any word in the trie that starts with the given prefix. */ public boolean startsWith(String prefix) { Trie node = this; for (int i = 0; i < prefix.length(); i++) { char c = prefix.charAt(i); node = node.children[c - 'a']; if (node == null) { return false; } } return true; } } /** * Your Trie object will be instantiated and called as such: * Trie obj = new Trie(); * obj.insert(word); * boolean param_2 = obj.search(word); * boolean param_3 = obj.startsWith(prefix); */

Given a collection of intervals, merge all overlapping intervals. Example 1: Input: [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6]. Example 2: Input: [[1,4],[4,5]] Output: [[1,5]] Explanation: Intervals [1,4] and [4,5] are considered overlapping. NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature. Solution: class Solution { public static int[][] merge(int[][] intervals) { Arrays.sort(intervals, Comparator.comparingInt(a -> a[0])); List<int[]> result = new ArrayList<>(); for (int[] curr : intervals) { if (result.isEmpty()) { result.add(curr); continue; } int[] prev = result.get(result.size() - 1); if (prev[1] < curr[0]) { result.add(curr); } else { prev[1] = Math.max(curr[1], prev[1]); } } return result.toArray(new int[0][0]); } }

Invert a binary tree. Example: Input: 4 / \ 2 7 / \ / \ 1 3 6 9 Output: 4 / \ 7 2 / \ / \ 9 6 3 1 Trivia: This problem was inspired by this original tweet by Max Howell: Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f*** off. Solution: ...

Koko loves to eat bananas. There are N piles of bananas, the i-th pile has piles[i] bananas. The guards have gone and will come back in H hours. Koko can decide her bananas-per-hour eating speed of K. Each hour, she chooses some pile of bananas, and eats K bananas from that pile. If the pile has less than K bananas, she eats all of them instead, and won’t eat any more bananas during this hour. ...

Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible. Note: The length of num is less than 10002 and will be ≥ k. The given num does not contain any leading zero. Example 1: Input: num = "1432219", k = 3 Output: "1219" Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest. Example 2: ...

Given a binary tree, return the inorder traversal of its nodes’ values. Example: Input: [1,null,2,3] 1 \ 2 / 3 Output: [1,3,2] Follow up: Recursive solution is trivial, could you do it iteratively? Solution: /** * 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 { private List<Integer> list = new ArrayList<>(); public List<Integer> inorderTraversal(TreeNode root) { if (root == null) { return Collections.emptyList(); } Stack<TreeNode> q = new Stack<>(); TreeNode curr = root; while (!q.isEmpty() || curr != null) { while (curr != null) { q.push(curr); curr = curr.left; } curr = q.pop(); list.add(curr.val); curr = curr.right; } return list; } public List<Integer> inorderTraversal2(TreeNode root) { if (root == null) { return Collections.emptyList(); } inorderTraversal(root.left); list.add(root.val); inorderTraversal(root.right); return list; } }

You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once. Find this single element that appears only once. Follow up: Your solution should run in O(log n) time and O(1) space. Example 1: Input: nums = [1,1,2,3,3,4,4,8,8] Output: 2 Example 2: Input: nums = [3,3,7,7,10,11,11] Output: 10 Constraints: 1 <= nums.length <= 10^5 0 <= nums[i] <= 10^5 Solution: ...

Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1. Example 1: Input: [0,1] Output: 2 Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1. Example 2: ```txt Input: [0,1,0] Output: 2 Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1. Note: The length of the given binary array will not exceed 50,000. ...