SWE Interview preparation

https://leetcode.com/discuss/interview-question/418351/uber-internship-no-offer Uber used to call Ubercab, and they have a lot of "ubercab" stickers and assuming you can cut them into individual characters. You are now given a word in string, and return how many stickers you need to make the word --- Intuition Generic solution given source and target words Pre process => source chars freq, and target  chars  freq in HashMap's Ignore spaces in both source, and target for each char in target     ans = Math.max(ans, (int)Math.ceil(target freq * 1.0 / source freq)) --- Time - O(m + n) Space - O(1) = Character set size --- ---

https://leetcode.com/problems/palindrome-pairs/ Given a list of  unique  words, find all pairs of  distinct  indices  (i, j)  in the given list, so that the concatenation of the two words, i.e.  words[i] + words[j]  is a palindrome. Example 1: Input: ["abcd","dcba","lls","s","sssll"] Output: [[0,1],[1,0],[3,2],[2,4]] E xplanation : The palindromes are ["dcbaabcd","abcddcba","slls","llssssll"] Example 2: Input: ["bat","tab","cat"] Output: [[0,1],[1,0]] E xplanation : The palindromes are ["battab","tabbat"] ---

https://leetcode.com/problems/rearrange-string-k-distance-apart/ https://github.com/openset/leetcode/tree/master/problems/rearrange-string-k-distance-apart Given a non-empty string  s  and an integer  k , rearrange the string such that the same characters are at least distance  k  from each other. All input strings are given in lowercase letters. If it is not possible to rearrange the string, return an empty string  "" . Example 1: Input: s = "aabbcc" , k = 3 Output: "abcabc" Explanation: The same letters are at least distance 3 from each other. Example 2: Input: s = "aaabc" , k = 3 Output: "" Explanation: It is not possible to rearrange the string. Example 3: Input: s = "aaadbbcc" , k = 2 Output: "abacabcd" Explanation: The same letters are at least distance 2 from each other. --- Related problems 621-task-scheduler ---

https://leetcode.com/problems/find-duplicate-file-in-system/ Given a list of directory info including directory path, and all the files with contents in this directory, you need to find out all the groups of duplicate files in the file system in terms of their paths. A group of duplicate files consists of at least  two  files that have exactly the same content. A single directory info string in the  input  list has the following format: "root/d1/d2/.../dm f1.txt(f1_content) f2.txt(f2_content) ... fn.txt(fn_content)" It means there are  n  files ( f1.txt ,  f2.txt  ...  fn.txt  with content  f1_content ,  f2_content  ...  fn_content , respectively) in directory  root/d1/d2/.../dm . Note that n >= 1 and m >= 0. If m = 0, it means the directory is just the root directory. The  output  is a list of group of duplicate file paths. For each group, it contains all the file paths of the files that have the...

https://leetcode.com/problems/isomorphic-strings/ Given two strings  s  and  t , determine if they are isomorphic. Two strings are isomorphic if the characters in  s  can be replaced to get  t . All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself. Example 1: Input: s = "egg", t = "add" Output: true Example 2: Input: s = "foo", t = "bar" Output: false Example 3: Input: s = "paper", t = "title" Output: true Note: You may assume both  s  and  t  have the same length. --- Related problems 290-word-pattern 890-find-and-replace-pattern ---

https://leetcode.com/problems/sequence-reconstruction/ https://github.com/openset/leetcode/tree/master/problems/sequence-reconstruction https://www.lintcode.com/problem/sequence-reconstruction/description Check whether the original sequence  org  can be uniquely reconstructed from the sequences in  seqs . The  org  sequence is a permutation of the integers from 1 to n, with 1 ≤ n ≤ 10 4 . Reconstruction means building a shortest common supersequence of the sequences in  seqs  (i.e., a shortest sequence so that all sequences in  seqs  are subsequences of it). Determine whether there is only one sequence that can be reconstructed from  seqs  and it is the  org  sequence. Example 1: Input: org: [1,2,3], seqs: [[1,2],[1,3]] Output: false Explanation: [1,2,3] is not the only one sequence that can be reconstructed, because [1,3,2] is also a valid sequence that can be reconstructed. Example 2: Input: org: [1,2,3], seqs: [[1,...

https://leetcode.com/problems/implement-magic-dictionary/ Implement a magic directory with  buildDict , and  search  methods. For the method  buildDict , you'll be given a list of non-repetitive words to build a dictionary. For the method  search , you'll be given a word, and judge whether if you modify  exactly  one character into  another  character in this word, the modified word is in the dictionary you just built. Example 1: Input: buildDict(["hello", "leetcode"]), Output: Null Input: search("hello"), Output: False Input: search("hhllo"), Output: True Input: search("hell"), Output: False Input: search("leetcoded"), Output: False Note: You may assume that all the inputs are consist of lowercase letters  a-z . For contest purpose, the test data is rather small by now. You could think about highly efficient algorithm after the contest. Please remember to  RESET  your class variables declared in class MagicDictionary,...

https://leetcode.com/problems/diagonal-traverse-ii/ Given a list of lists of integers,  nums , return all elements of  nums  in diagonal order as shown in the below images. Example 1: Input: nums = [[1,2,3],[4,5,6],[7,8,9]] Output: [1,4,2,7,5,3,8,6,9] Example 2: Input: nums = [[1,2,3,4,5],[6,7],[8],[9,10,11],[12,13,14,15,16]] Output: [1,6,2,8,7,3,9,4,12,10,5,13,11,14,15,16] Example 3: Input: nums = [[1,2,3],[4],[5,6,7],[8],[9,10,11]] Output: [1,4,2,5,3,8,6,9,7,10,11] Example 4: Input: nums = [[1,2,3,4,5,6]] Output: [1,2,3,4,5,6] Constraints: 1 <= nums.length <= 10^5 1 <= nums[i].length <= 10^5 1 <= nums[i][j] <= 10^9 There at most  10^5  elements in  nums . --- Intuition Elements on same diagonal share same r + c Save the size of each row to compute output size Add to output in reverse from each list, since the addition is in reverse direction --- Time - O(R * C) Space - O(R * C) --- Related problems 49...

https://leetcode.com/problems/maximum-size-subarray-sum-equals-k https://www.lintcode.com/problem/maximum-size-subarray-sum-equals-k/description Given an array  nums  and a target value  k , find the maximum length of a subarray that sums to  k . If there isn't one, return 0 instead. Note: The sum of the entire  nums  array is guaranteed to fit within the 32-bit signed integer range. Example 1: Input: nums = [1, -1, 5, -2, 3] , k = 3 Output: 4 Explanation: The subarray [1, -1, 5, -2] sums to 3 and is the longest. Example 2: Input: nums = [-2, -1, 2, 1] , k = 1 Output: 2 Explanation: The subarray [-1, 2] sums to 1 and is the longest. Follow Up: Can you do it in O( n ) time? ---- Intuition Sub array sum => preprocess input to get range sum in const time => create prefix sum Sum from i to j = prefix[j] - prefix[i - 1],  length of subarray = j - 1 Problem reduces to Max (j - i) such that prefix[j] - prefix[i] = k I...

https://leetcode.com/problems/copy-list-with-random-pointer/ A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null. Return a  deep copy  of the list. The Linked List is represented in the input/output as a list of  n  nodes. Each node is represented as a pair of  [val, random_index]  where: val : an integer representing  Node.val random_index : the index of the node (range from  0  to  n-1 ) where random pointer points to, or  null  if it does not point to any node. Example 1: Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]] Output: [[7,null],[13,0],[11,4],[10,2],[1,0]] Example 2: Input: head = [[1,1],[2,1]] Output: [[1,1],[2,1]] Example 3: Input: head = [[3,null],[3,0],[3,null]] Output: [[3,null],[3,0],[3,null]] Example 4: Input: head = [] Output: [] Explanation: Given linked list is empty (null pointer), so return null. Constraint...

https://leetcode.com/problems/target-sum/ You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols  +  and  - . For each integer, you should choose one from  +  and  -  as its new symbol. Find out how many ways to assign symbols to make sum of integers equal to target S. Example 1: Input: nums is [1, 1, 1, 1, 1], S is 3. Output: 5 Explanation: -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 There are 5 ways to assign symbols to make the sum of nums be target 3. Note: The length of the given array is positive and will not exceed 20. The sum of elements in the given array will not exceed 1000. Your output answer is guaranteed to be fitted in a 32-bit integer. ----- Intuition Number of ways => DFS At each array index, we have two choices, + , - Terminate recursion when index == A.length * -- Can be memoized ---

https://leetcode.com/problems/number-of-ways-to-stay-in-the-same-place-after-some-steps/ You have a pointer at index  0  in an array of size  arrLen . At each step, you can move 1 position to the left, 1 position to the right in the array or stay in the same place  (The pointer should not be placed outside the array at any time). Given two integers  steps  and  arrLen , return the number of ways such that your pointer still at index  0  after  exactly  steps  steps. Since the answer may be too large, return it  modulo   10^9 + 7 . Example 1: Input: steps = 3, arrLen = 2 Output: 4 Explanation: There are 4 differents ways to stay at index 0 after 3 steps. Right, Left, Stay Stay, Right, Left Right, Stay, Left Stay, Stay, Stay Example 2: Input: steps = 2, arrLen = 4 Output: 2 Explanation: There are 2 differents ways to stay at index 0 after 2 steps Right, Left Stay, Stay Example ...