SWE Interview preparation

https://leetcode.com/problems/implement-trie-prefix-tree/ 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. --- Related problems 211-add-and-search-word-data-structure ---

https://leetcode.com/problems/is-subsequence/ Given a string  s  and a string  t , check if  s  is subsequence of  t . You may assume that there is only lower case English letters in both  s  and  t .  t  is potentially a very long (length ~= 500,000) string, and  s  is a short string (<=100). A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie,  "ace"  is a subsequence of  "abcde"  while  "aec"  is not). Example 1: s  =  "abc" ,  t  =  "ahbgdc" Return  true . Example 2: s  =  "axc" ,  t  =  "ahbgdc" Return  false . Follow up: If there are lots of incoming S, say S1, S2, ... , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code? ----

https://leetcode.com/problems/find-the-difference/ Given two strings  s  and  t  which consist of only lowercase letters. String  t  is generated by random shuffling string  s  and then add one more letter at a random position. Find the letter that was added in  t . Example: Input: s = "abcd" t = "abcde" Output: e Explanation: 'e' is the letter that was added. ---

https://leetcode.com/problems/permutations-ii/ Given a collection of numbers that might contain duplicates, return all possible unique permutations. Example: Input: [1,1,2] Output: [ [1,1,2], [1,2,1], [2,1,1] ] --- Related problems 46-permutations 78-subsets 90-subsets-ii 39-combination-sum 40-combination-sum-ii ---

https://leetcode.com/problems/permutations/ Given a collection of  distinct  integers, return all possible permutations. Example: Input: [1,2,3] Output: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] --- Related problems 47-permutations-ii 78-subsets 90-subsets-ii 39-combination-sum 40-combination-sum-ii ---

https://leetcode.com/problems/subsets-ii/ Given a collection of integers that might contain duplicates,  nums , return all possible subsets (the power set). Note:  The solution set must not contain duplicate subsets. Example: Input: [1,2,2] Output: [ [2], [1], [1,2,2], [2,2], [1,2], [] ] --- Intuition --- Related problems 78-subsets 46-permutations 47-permutations-ii 39-combination-sum 40-combination-sum-ii ---

https://leetcode.com/problems/subsets/ Given a set of  distinct  integers,  nums , return all possible subsets (the power set). Note:  The solution set must not contain duplicate subsets. Example: Input: nums = [1,2,3] Output: [ [3],   [1],   [2],   [1,2,3],   [1,3],   [2,3],   [1,2],   [] ] --- Intuition Generate all combinations, save combination at each stage --- Related problems 90-subsets-ii 46-permutations 47-permutations-ii 39-combination-sum 40-combination-sum-ii ---

https://leetcode.com/problems/count-number-of-teams/ There are  n  soldiers standing in a line. Each soldier is assigned a  unique   rating  value. You have to form a team of 3 soldiers amongst them under the following rules: Choose 3 soldiers with index ( i ,  j ,  k ) with rating ( rating[i] ,  rating[j] ,  rating[k] ). A team is valid if:  ( rating[i] < rating[j] < rating[k] ) or ( rating[i] > rating[j] > rating[k] ) where ( 0 <= i < j < k < n ). Return the number of teams you can form given the conditions. (soldiers can be part of multiple teams). Example 1: Input: rating = [2,5,3,4,1] Output: 3 Explanation: We can form three teams given the conditions. (2,3,4), (5,4,1), (5,3,1). Example 2: Input: rating = [2,1,3] Output: 0 Explanation: We can't form any team given the conditions. Example 3: Input: rating = [1,2,3,4] Output: 4 Constraints: n == rating.length 1 <= n <= 200 1 <= rating[i] <= 10^5 ---

https://leetcode.com/problems/swap-adjacent-in-lr-string/ In a string composed of  'L' ,  'R' , and  'X'  characters, like  "RXXLRXRXL" , a move consists of either replacing one occurrence of  "XL"  with  "LX" , or replacing one occurrence of  "RX"  with  "XR" . Given the starting string  start  and the ending string  end , return  True  if and only if there exists a sequence of moves to transform one string to the other. Example: Input: start = "RXXLRXRXL", end = "XRLXXRRLX" Output: True Explanation: We can transform start to end following these steps: RXXLRXRXL -> XRXLRXRXL -> XRLXRXRXL -> XRLXXRRXL -> XRLXXRRLX Note: 1 <= len(start) = len(end) <= 10000 . Both start and end will only consist of characters in  {'L', 'R', 'X'} . ---

https://leetcode.com/problems/sort-colors/ Given an array with  n  objects colored red, white or blue, sort them  in-place   so that objects of the same color are adjacent, with the colors in the order red, white and blue. Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively. Note:  You are not suppose to use the library's sort function for this problem. Example: Input: [2,0,2,1,1,0] Output: [0,0,1,1,2,2] Follow up: A rather straight forward solution is a two-pass algorithm using counting sort. First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's. Could you come up with a one-pass algorithm using only constant space? --- Time - O(n) Space - O(1) ---

https://leetcode.com/problems/fizz-buzz/ Write a program that outputs the string representation of numbers from 1 to  n . But for multiples of three it should output “Fizz” instead of the number and for the multiples of five output “Buzz”. For numbers which are multiples of both three and five output “FizzBuzz”. Example: n = 15, Return: [ "1", "2", "Fizz", "4", "Buzz", "Fizz", "7", "8", "Fizz", "Buzz", "11", "Fizz", "13", "14", "FizzBuzz" ] ---

https://leetcode.com/problems/invert-binary-tree/ https://workat.tech/problem-solving/practice/invert-binary-tree 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. --- Time - O(n) Space - O(h) ---

https://leetcode.com/problems/reverse-string/ Write a function that reverses a string. The input string is given as an array of characters  char[] . Do not allocate extra space for another array, you must do this by  modifying the input array  in-place  with O(1) extra memory. You may assume all the characters consist of  printable ascii characters . Example 1: Input: ["h","e","l","l","o"] Output: ["o","l","l","e","h"] Example 2: Input: ["H","a","n","n","a","h"] Output: ["h","a","n","n","a","H"]

https://leetcode.com/problems/shortest-distance-to-a-character/ Given a string  S  and a character  C , return an array of integers representing the shortest distance from the character  C  in the string. Example 1: Input: S = "loveleetcode", C = 'e' Output: [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0] Note: S  string length is in  [1, 10000]. C  is a single character, and guaranteed to be in string  S . All letters in  S  and  C  are lowercase. ----

https://leetcode.com/problems/height-checker/ Students are asked to stand in non-decreasing order of heights for an annual photo. Return the minimum number of students that must move in order for all students to be standing in non-decreasing order of height. Notice that when a group of students is selected they can reorder in any possible way between themselves and the non selected students remain on their seats. Example 1: Input: heights = [1,1,4,2,1,3] Output: 3 Explanation: Current array : [1,1,4,2,1,3] Target array : [1,1,1,2,3,4] On index 2 (0-based) we have 4 vs 1 so we have to move this student. On index 4 (0-based) we have 1 vs 3 so we have to move this student. On index 5 (0-based) we have 3 vs 4 so we have to move this student. Example 2: Input: heights = [5,1,2,3,4] Output: 5 Example 3: Input: heights = [1,2,3,4,5] Output: 0 Constraints: 1 <= heights.length <= 100 1 <= heights[i] <= 100 --- Intuition Sort a copy of the ar

https://leetcode.com/problems/reconstruct-itinerary/ Given a list of airline tickets represented by pairs of departure and arrival airports  [from, to] , reconstruct the itinerary in order. All of the tickets belong to a man who departs from  JFK . Thus, the itinerary must begin with  JFK . Note: If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary  ["JFK", "LGA"]  has a smaller lexical order than  ["JFK", "LGB"] . All airports are represented by three capital letters (IATA code). You may assume all tickets form at least one valid itinerary. Example 1: Input: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]] Output: ["JFK", "MUC", "LHR", "SFO", "SJC"] Example 2: Input: [[&qu

https://leetcode.com/problems/design-underground-system/ Implement the class  UndergroundSystem  that supports three methods: 1.  checkIn(int id, string stationName, int t) A customer with id card equal to  id , gets in the station  stationName  at time  t . A customer can only be checked into one place at a time. 2.  checkOut(int id, string stationName, int t) A customer with id card equal to  id , gets out from the station  stationName  at time  t . 3.  getAverageTime(string startStation, string endStation)   Returns the average time to travel between the  startStation  and the  endStation . The average time is computed from all the previous traveling from  startStation  to  endStation  that happened  directly . Call to  getAverageTime  is always valid. You can assume all calls to  checkIn  and  checkOut  methods are consistent. That is, if a customer gets in at time  t 1  at some station, then it gets out at time  t 2  with  t 2  > t 1 . All events happen i