Given an array w of positive integers, where w[i] describes the weight of index i, write a function pickIndex which randomly picks an index in proportion to its weight. Note: 1 <= w.length <= 10000 1 <= w[i] <= 10^5 pickIndex will be called at most 10000 times. Example 1: 1 2 3 4 Input: ["Solution","pickIndex"] [[[1]],[]] Output: [null,0] Example 2: ...
There are 2N people a company is planning to interview. The cost of flying the i-th person to city A is costs[i][0], and the cost of flying the i-th person to city B is costs[i][1]. Return the minimum cost to fly every person to a city such that exactly N people arrive in each city. Example 1: 1 2 3 4 5 6 7 8 9 Input: [[10,20],[30,200],[400,50],[30,20]] Output: 110 Explanation: The first person goes to city A for a cost of 10. The second person goes to city A for a cost of 30. The third person goes to city B for a cost of 50. The fourth person goes to city B for a cost of 20. The total minimum cost is 10 + 30 + 50 + 20 = 110 to have half the people interviewing in each city. Note: ...
Write a function to delete a node (except the tail) in a singly linked list, given only access to that node. Given linked list – head = [4,5,1,9], which looks like following: Example 1: 1 2 3 Input: head = [4,5,1,9], node = 5 Output: [4,1,9] Explanation: You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function. Example 2: ...
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 string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n). Example: 1 2 Input: S = "ADOBECODEBANC", T = "ABC" Output: "BANC" Note: If there is no such window in S that covers all characters in T, return the empty string “”. If there is such window, you are guaranteed that there will always be only one unique minimum window in S. Solution: ...
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? ...