SWE Interview preparation

https://leetcode.com/explore/challenge/card/30-day-leetcoding-challenge/532/week-5/3315/ 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: Input: root = [0,1,0,0,1,0,null,null,1,0,0], arr = [0,0,1] Output: false Explanation: The path 0 -> 0 -> 1 does not exist, therefore it is not even a sequence. Example 3: Input: root = [0,1,0,0,1,0,null,null,1,0,0], arr = [0,1,1] Output: false Explanation: The path 0 -> 1

https://leetcode.com/explore/challenge/card/30-day-leetcoding-challenge/531/week-4/3313/ https://leetcode.com/problems/first-unique-number You have a queue of integers, you need to retrieve the first unique integer in the queue. Implement the  FirstUnique  class: FirstUnique(int[] nums)  Initializes the object with the numbers in the queue. int showFirstUnique()  returns the value of  the first unique  integer of the queue, and returns  -1  if there is no such integer. void add(int value)  insert value to the queue. Example 1: Input: ["FirstUnique","showFirstUnique","add","showFirstUnique","add","showFirstUnique","add","showFirstUnique"] [[[2,3,5]],[],[5],[],[2],[],[3],[]] Output: [null,2,null,2,null,3,null,-1] Explanation: FirstUnique firstUnique = new FirstUnique([2,3,5]); firstUnique.showFirstUnique(); // return 2 firstUnique.add(5); // the queue is now [2,3,5,5] firstUnique.showFirs

Given an array  nums  and a target value  k , find the maximum sum of a subarray that sums less than or equal 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 = 4 Output: 4 Explanation: The subarray [1, -1, 5, -2] sums to 3 and is closest <= k. Example 2: Input: nums = [3, -1, 2, 7] , k = 5 Output: 4 Explanation: The subarray [3, -1, 2] sums to 4 and is closest <= 5. 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 (prefix[j] - prefix[i - 1]) such that prefix[j] - prefix[i] <= k Instead of brute force, we can lookup complement prefix[index] - k from Tree Set If such complement exists, check if its potentially greater

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 Instead of brute force, we can

https://www.lintcode.com/problem/strobogrammatic-number-ii/description https://leetcode.com/problems/strobogrammatic-number-ii A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down). Find all strobogrammatic numbers that are of length = n. Example: Input: n = 2 Output: ["11","69","88","96"] --- Intuition All possible combinations  => DFS Fill in the string from two ends Terminate recursion when i reaches (n + 1) / 2 Skip 6, 9 for midpoint of odd length string Skip 0 for > 1 length string ---- Time - O(N) Space - O(N) --- Related problems strobogrammatic-number --- ---

https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/ Given a string  S  of  '('  and  ')'  parentheses, we add the minimum number of parentheses (  '('  or  ')' , and in any positions ) so that the resulting parentheses string is valid. Formally, a parentheses string is valid if and only if: It is the empty string, or It can be written as  AB  ( A  concatenated with  B ), where  A  and  B  are valid strings, or It can be written as  (A) , where  A  is a valid string. Given a parentheses string, return the minimum number of parentheses we must add to make the resulting string valid. Example 1: Input: "())" Output: 1 Example 2: Input: "(((" Output: 3 Example 3: Input: "()" Output: 0 Example 4: Input: "()))((" Output: 4 Note: S.length <= 1000 S  only consists of  '('  and  ')'  characters. ---- Time - O(N) Space - O(1) ---

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. Constraints: -10000 <= Node.val <= 10000 Node.random  is null

https://leetcode.com/problems/edit-distance/ Given two words  word1  and  word2 , find the minimum number of operations required to convert  word1  to  word2 . You have the following 3 operations permitted on a word: Insert a character Delete a character Replace a character Example 1: Input: word1 = "horse", word2 = "ros" Output: 3 Explanation: horse -> rorse (replace 'h' with 'r') rorse -> rose (remove 'r') rose -> ros (remove 'e') Example 2: Input: word1 = "intention", word2 = "execution" Output: 5 Explanation: intention -> inention (remove 't') inention -> enention (replace 'i' with 'e') enention -> exention (replace 'n' with 'x') exention -> exection (replace 'n' with 'c') exection -> execution (insert 'u') --- Related problems 161-one-edit-distance --- Intuition Inserting character from 1 string is equival

https://leetcode.com/problems/one-edit-distance https://www.lintcode.com/problem/one-edit-distance/description Given two strings  s  and  t , determine if they are both one edit distance apart. Note:   There are 3 possiblities to satisify one edit distance apart: Insert a character into  s  to get  t Delete a character from  s  to get  t Replace a character of  s  to get  t Example 1: Input: s = "ab", t = "acb" Output: true Explanation: We can insert 'c' into s  to get  t. Example 2: Input: s = "cab", t = "ad" Output: false Explanation: We cannot get t from s by only one step. Example 3: Input: s = "1203", t = "1213" Output: true Explanation: We can replace '0' with '1' to get  t. --- Related problems --- Intuition Corner cases when strings are null and 0 length dfs(i, j, moves) if (moves > 2) => return false if chars are same => dfs(i + 1, j + 1, moves) else dfs(i

https://leetcode.com/problems/remove-linked-list-elements/ Remove all elements from a linked list of integers that have value  val . Example: Input: 1->2->6->3->4->5->6, val = 6 Output: 1->2->3->4->5 -- Intuition Have a prev pointer If head.val == target    Set the prev to head.next else    prev = prev.next Preprocess Corner case, while head.val == target at the beginning of list -- Related problems 237-delete-node-in-linked-list ---

https://leetcode.com/problems/delete-node-in-a-linked-list/ https://workat.tech/problem-solving/practice/delete-node-linked-list 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: 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: Input: head = [4,5,1,9], node = 1 Output: [4,5,9] Explanation: You are given the third node with value 1, the linked list should become 4 -> 5 -> 9 after calling your function. Note: The linked list will have at least two elements. All of the nodes' values will be unique. The given node will not be the tail and it will always be a valid node of the linked list. Do not return anything from your function. ---- Intuition We cannot set the nex

https://leetcode.com/problems/next-greater-element-ii/ Given a circular array (the next element of the last element is the first element of the array), print the Next Greater Number for every element. The Next Greater Number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn't exist, output -1 for this number. Example 1: Input: [1,2,1] Output: [2,-1,2] Explanation: The first 1's next greater number is 2; The number 2 can't find next greater number; The second 1's next greater number needs to search circularly, which is also 2. Note:  The length of given array won't exceed 10000. --- Time - O(N) Space - O(N) -- Related problems 496-next-greater-element-i --

https://leetcode.com/problems/next-greater-element-i/ You are given two arrays  (without duplicates)   nums1  and  nums2  where  nums1 ’s elements are subset of  nums2 . Find all the next greater numbers for  nums1 's elements in the corresponding places of  nums2 . The Next Greater Number of a number  x  in  nums1  is the first greater number to its right in  nums2 . If it does not exist, output -1 for this number. Example 1: Input: nums1 = [4,1,2], nums2 = [1,3,4,2]. Output: [-1,3,-1] Explanation: For number 4 in the first array, you cannot find the next greater number for it in the second array, so output -1. For number 1 in the first array, the next greater number for it in the second array is 3. For number 2 in the first array, there is no next greater number for it in the second array, so output -1. Example 2: Input: nums1 = [2,4], nums2 = [1,2,3,4]. Output: [3,-1] Explanation: For number 2 in the first array, the next greater number fo

https://leetcode.com/problems/decode-ways/ A message containing letters from  A-Z  is being encoded to numbers using the following mapping: 'A' -> 1 'B' -> 2 ... 'Z' -> 26 Given a  non-empty  string containing only digits, determine the total number of ways to decode it. Example 1: Input: "12" Output: 2 Explanation:  It could be decoded as "AB" (1 2) or "L" (12). Example 2: Input: "226" Output: 3 Explanation:  It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6). --- Time - O(2 ^ N) - 2 branching at each recursive call - pure DFS Time - O(N) - each index is visited only once - memoized ---