You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad. Suppose you have n versions [1, 2, …, n] and you want to find out the first bad one, which causes all the following ones to be bad. ...
Given a binary search tree, write a function kthSmallest to find the kth smallest element in it. Note: You may assume k is always valid, 1 ≤ k ≤ BST’s total elements. Example 1: Input: root = [3,1,4,null,2], k = 1 3 / \ 1 4 \ 2 Output: 1 Example 2: Input: root = [5,3,6,2,4,null,null,1], k = 3 5 / \ 3 6 / \ 2 4 / 1 Output: 3 Follow up: What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine? ...
Given a string, your task is to count how many palindromic substrings in this string. The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters. Example 1: Input: "abc" Output: 3 Explanation: Three palindromic strings: "a", "b", "c". Example 2: Input: "aaa" Output: 6 Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa". ``` Note: ``` The input string length won't exceed 1000. ``` Solution ```java class Solution { public int countSubstrings(String s) { int n = s.length(); int[][] a = new int[n][n]; int count = 0; for (int i = 0; i < n; i++) { a[i][i] = 1; count++; } for (int col = 1; col < n; col++) { for (int row = 0; row < col; row++) { if (row == col - 1 && s.charAt(col) == s.charAt(row)) { a[row][col] = 1; count++; } else if (a[row + 1][col - 1] == 1 && s.charAt(col) == s.charAt(row) ) { a[row][col] = 1; count++; } } } return count; } } ```  
Given an array of strings, group anagrams together. Example: Input: ["eat", "tea", "tan", "ate", "nat", "bat"], Output: [ ["ate","eat","tea"], ["nat","tan"], ["bat"] ] Note: All inputs will be in lowercase. The order of your output does not matter. Solution class Solution { public List<List<String>> groupAnagrams(String[] strs) { Map<String, List<String>> map = new HashMap<>(); int[] c = new int[26]; for (String s : strs) { Arrays.fill(c, 0); for (int i = 0 ; i < s.length(); i++) { c[s.charAt(i) - 'a']++; } String code = Arrays.toString(c); List<String> list = map.get(code); if (list == null) { list = new ArrayList<>(); } list.add(s); map.put(code, list); } return new ArrayList<>(map.values()); } } Solution 2021-11-15 class Solution { public List<List<String>> groupAnagrams(String[] strs) { Map<String, List<String>> keyToList = new HashMap<>(); for (String s: strs) { char[] charString = s.toCharArray(); Arrays.sort(charString); String sortedWord = String.valueOf(charString); List<String> anagrams = keyToList.getOrDefault(sortedWord, new ArrayList<>()); anagrams.add(s); keyToList.put(sortedWord, anagrams); } List<List<String>> res = new ArrayList<>(); for (var anagrams: keyToList.values()) { res.add(anagrams); } return res; } }
Given a non-empty binary tree, find the maximum path sum. For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root. Example 1: Input: [1,2,3] 1 / \ 2 3 Output: 6 Example 2: ...
Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area. Example: Input: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 Output: 4 Solution class Solution { public int maximalSquare(char[][] matrix) { int n = matrix.length; if (n == 0) { return 0; } int m = matrix[0].length; int[][] dp = new int[n][m]; int answer = 0; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (matrix[i][j] == '1') { dp[i][j] = 1; if (i > 0 && j > 0) { dp[i][j] += Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])); } answer = Math.max(answer, dp[i][j]); } } } return answer * answer; } }
Given two strings text1 and text2, return the length of their longest common subsequence. A subsequence of a string is a new string generated from the original string with some characters(can be none) deleted without changing the relative order of the remaining characters. (eg, “ace” is a subsequence of “abcde” while “aec” is not). A common subsequence of two strings is a subsequence that is common to both strings. If there is no common subsequence, return 0. ...
Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index. Example 1: Input: nums = [2,3,1,1,4] Output: true Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index. Example 2: Input: nums = [3,2,1,0,4] Output: false Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index. Constraints: ...
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put. get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item. ...
Given a binary tree where each path going from the root to any leaf form a valid sequence, check if a given string is a valid sequence in such binary tree. We get the given string from the concatenation of an array of integers arr and the concatenation of all values of the nodes along a path results in a sequence in the given binary tree. Example 1: Input: root = [0,1,0,0,1,0,null,null,1,0,0], arr = [0,1,0,1] Output: true Explanation: The path 0 -> 1 -> 0 -> 1 is a valid sequence (green color in the figure). Other valid sequences are: 0 -> 1 -> 1 -> 0 0 -> 0 -> 0 Example 2: ...