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: 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.
Given a string s, find the length of the longest substring t that contains at most 2 distinct characters. Example 1 Input: "eceba" Output: 3 Explanation: t is "ece" which its length is 3. Example 2 Input: "ccaabbb" Output: 5 Explanation: t is "aabbb" which its length is 5. Solution class Solution { public int lengthOfLongestSubstringTwoDistinct(String s) { HashMap<Character, Integer> countMap = new HashMap<Character, Integer>(); int left = 0; int max = 0; for (int i = 0; i < s.
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path. Note You can only move either down or right at any point in time. Example: Input: [ [1,3,1], [1,5,1], [4,2,1] ] Output: 7 Explanation: Because the path 1→3→1→1→1 minimizes the sum. Solution class Solution { public int minPathSum(int[][] grid) { if (grid == null || grid.
Given a sorted array, two integers k and x, find the k closest elements to x in the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred. Example 1 Input: [1,2,3,4,5], k=4, x=3 Output: [1,2,3,4] Example 2 Input: [1,2,3,4,5], k=4, x=-1 Output: [1,2,3,4] Note The value k is positive and will always be smaller than the length of the sorted array.
Given a string, find the length of the longest substring T that contains at most k distinct characters. Example 1 Input: s = "eceba", k = 2 Output: 3 Explanation: T is "ece" which its length is 3. Example 2 Input: s = "aa", k = 1 Output: 2 Explanation: T is "aa" which its length is 2. Solution class Solution { public int lengthOfLongestSubstringKDistinct(String s, int k) { Map<Character, Integer> countMap = new HashMap<>(); int left = 0; int max = 0; for(int i = 0; i < s.
Given an Iterator class interface with methods: next() and hasNext(), design and implement a PeekingIterator that support the peek() operation – it essentially peek() at the element that will be returned by the next call to next(). Example: Assume that the iterator is initialized to the beginning of the list: [1,2,3]. Call next() gets you 1, the first element in the list. Now you call peek() and it returns 2, the next element.
Implement FreqStack, a class which simulates the operation of a stack-like data structure. FreqStack has two functions: push(int x), which pushes an integer x onto the stack. pop(), which removes and returns the most frequent element in the stack. If there is a tie for most frequent element, the element closest to the top of the stack is removed and returned. Example 1 Input: ["FreqStack","push","push","push","push","push","push","pop","pop","pop","pop"], [[],[5],[7],[5],[7],[4],[5],[],[],[],[]] Output: [null,null,null,null,null,null,null,5,7,5,4] Explanation: After making six .
On an N x N board, the numbers from 1 to N*N are written boustrophedonically starting from the bottom left of the board, and alternating direction each row. For example, for a 6 x 6 board, the numbers are written as follows: You start on square 1 of the board (which is always in the last row and first column). Each move, starting from square x, consists of the following:
Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value. Example [2,3,4], the median is 3 [2,3], the median is (2 + 3) / 2 = 2.5 Design a data structure that supports the following two operations: void addNum(int num) - Add a integer number from the data stream to the data structure.
Design a Tic-tac-toe game that is played between two players on a n x n grid. You may assume the following rules: A move is guaranteed to be valid and is placed on an empty block. Once a winning condition is reached, no more moves is allowed. A player who succeeds in placing n of their marks in a horizontal, vertical, or diagonal row wins the game. Example: Given n = 3, assume that player 1 is "X" and player 2 is "O" in the board.