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: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 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: 1 2 3 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: 1 2 3 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. ...

Invert a binary tree. Example: Input: 1 2 3 4 5 4 / \ 2 7 / \ / \ 1 3 6 9 Output: 1 2 3 4 5 4 / \ 7 2 / \ / \ 9 6 3 1 Trivia: This problem was inspired by this original tweet by Max Howell: ...

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: 1 2 3 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: 1 2 3 4 5 6 7 8 Input: [1,null,2,3] 1 \ 2 / 3 Output: [1,3,2] Follow up: Recursive solution is trivial, could you do it iteratively? ...

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: 1 2 Input: nums = [1,1,2,3,3,4,4,8,8] Output: 2 Example 2: 1 2 Input: nums = [3,3,7,7,10,11,11] Output: 10 Constraints: ...

Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1. Example 1: 1 2 3 4 5 6 7 8 9 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. ...