SWE Interview preparation

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   Constraints: 1 <= len(start) == len(end) <= 10000 . Both start and end will only consist of characters in  {'L', 'R', 'X'} . --- ---

https://leetcode.com/problems/subarray-sums-divisible-by-k/ Given an array  A  of integers, return the number of (contiguous, non-empty) subarrays that have a sum divisible by  K .   Example 1: Input: A = [4,5,0,-2,-3,1] , K = 5 Output: 7 Explanation: There are 7 subarrays with a sum divisible by K = 5: [4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]   Note: 1 <= A.length <= 30000 -10000 <= A[i] <= 10000 2 <= K <= 10000 ---

https://leetcode.com/problems/longest-common-subsequence/ 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.   Example 1: Input: text1 = "abcde", text2 = "ace" Output: 3 Explanation: The longest common subsequence is "ace" and its length is 3. Example 2: Input: text1 = "abc", text2 = "abc" Output: 3 Explanation: The longest common subsequence is "abc" and its length is 3. Example 3: Input: text1 = "abc", text2 = "def" Output: 0 Explanation: There is n

https://leetcode.com/problems/dinner-plate-stacks/ You have an infinite number of stacks arranged in a row and numbered (left to right) from 0, each of the stacks has the same maximum  capacity . Implement the  DinnerPlates  class: DinnerPlates(int capacity)  Initializes the object with the maximum  capacity  of the stacks. void push(int val)  pushes the given positive integer  val  into the leftmost stack with size less than  capacity . int pop()  returns the value at the top of the rightmost non-empty stack and removes it from that stack, and returns  -1  if all stacks are empty. int popAtStack(int index)  returns the value at the top of the stack with the given  index  and removes it from that stack, and returns -1 if the stack with that given  index  is empty. Example: Input: ["DinnerPlates","push","push","push","push","push","popAtStack","push","push","popAtStack","popAtStack&

https://leetcode.com/problems/smallest-string-with-swaps/ You are given a string  s , and an array of pairs of indices in the string  pairs  where  pairs[i] = [a, b]  indicates 2 indices(0-indexed) of the string. You can swap the characters at any pair of indices in the given  pairs   any number of times . Return the lexicographically smallest string that  s  can be changed to after using the swaps.   Example 1: Input: s = "dcab", pairs = [[0,3],[1,2]] Output: "bacd" Explaination: Swap s[0] and s[3], s = "bcad" Swap s[1] and s[2], s = "bacd" Example 2: Input: s = "dcab", pairs = [[0,3],[1,2],[0,2]] Output: "abcd" Explaination: Swap s[0] and s[3], s = "bcad" Swap s[0] and s[2], s = "acbd" Swap s[1] and s[2], s = "abcd" Example 3: Input: s = "cba", pairs = [[0,1],[1,2]] Output: "abc" Explaination: Swap s[0] and s[1], s = "bca" Swap s[1] and s[2], s = "bac

https://leetcode.com/problems/maximum-profit-in-job-scheduling/ We have  n  jobs, where every job is scheduled to be done from  startTime[i]  to  endTime[i] , obtaining a profit of  profit[i] . You're given the  startTime  ,  endTime  and  profit  arrays, you need to output the maximum profit you can take such that there are no 2 jobs in the subset with overlapping time range. If you choose a job that ends at time  X  you will be able to start another job that starts at time  X .   Example 1: Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70] Output: 120 Explanation: The subset chosen is the first and fourth job. Time range [1-3]+[3-6] , we get profit of 120 = 50 + 70. Example 2: Input: startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60] Output: 150 Explanation: The subset chosen is the first, fourth and fifth job. Profit obtained 150 = 20 + 70 + 60. Example 3: Input: startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4] O

  https://leetcode.com/problems/sort-list/ Sort a linked list in  O ( n   log   n ) time using constant space complexity. Example 1: Input: 4->2->1->3 Output: 1->2->3->4 Example 2: Input: -1->5->3->4->0 Output: -1->0->3->4->5 ---

https://leetcode.com/problems/greatest-sum-divisible-by-three/ Given an array  nums  of integers, we need to find the maximum possible sum of elements of the array such that it is divisible by three.   Example 1: Input: nums = [3,6,5,1,8] Output: 18 Explanation: Pick numbers 3, 6, 1 and 8 their sum is 18 (maximum sum divisible by 3). Example 2: Input: nums = [4] Output: 0 Explanation: Since 4 is not divisible by 3, do not pick any number. Example 3: Input: nums = [1,2,3,4,4] Output: 12 Explanation: Pick numbers 1, 3, 4 and 4 their sum is 12 (maximum sum divisible by 3).   Constraints: 1 <= nums.length <= 4 * 10^4 1 <= nums[i] <= 10^4 --- Intuition When a number is divided by 3,  there are 3 possible remainders 0 => Exact multiple 1 2 If we track max sum for each remainder => ans = sum with remainder 0  Algo     Init - size 3 array with size 0 - max with remainders 0, 1, 2     Add current number to each sum, find the remainder => index in the sums array  

https://leetcode.com/problems/find-the-smallest-divisor-given-a-threshold/ Given an array of integers  nums  and an integer  threshold , we will choose a positive integer divisor and divide all the array by it and sum the result of the division. Find the  smallest  divisor such that the result mentioned above is less than or equal to  threshold . Each result of division is rounded to the nearest integer greater than or equal to that element. (For example: 7/3 = 3 and 10/2 = 5). It is guaranteed that there will be an answer.   Example 1: Input: nums = [1,2,5,9], threshold = 6 Output: 5 Explanation: We can get a sum to 17 (1+2+5+9) if the divisor is 1. If the divisor is 4 we can get a sum to 7 (1+1+2+3) and if the divisor is 5 the sum will be 5 (1+1+1+2). Example 2: Input: nums = [2,3,5,7,11], threshold = 11 Output: 3 Example 3: Input: nums = [19], threshold = 5 Output: 4   Constraints: 1 <= nums.length <= 5 * 10^4 1 <= nums[i] <= 10^6 nums.length <= threshold <

https://leetcode.com/problems/maximum-product-of-splitted-binary-tree/ Given a binary tree  root . Split the binary tree into two subtrees by removing 1 edge such that the product of the sums of the subtrees are maximized. Since the answer may be too large, return it modulo 10^9 + 7.   Example 1: Input: root = [1,2,3,4,5,6] Output: 110 Explanation: Remove the red edge and get 2 binary trees with sum 11 and 10. Their product is 110 (11*10) Example 2: Input: root = [1,null,2,3,4,null,null,5,6] Output: 90 Explanation: Remove the red edge and get 2 binary trees with sum 15 and 6.Their product is 90 (15*6) Example 3: Input: root = [2,3,9,10,7,8,6,5,4,11,1] Output: 1025 Example 4: Input: root = [1,1] Output: 1   Constraints: Each tree has at most  50000  nodes and at least  2  nodes. Each node's value is between  [1, 10000] . --- Intuition Compute total of all node values At each node - find sum of subtree rooted at that node Calculate product of sum(subtree) * (total - sum(su

https://leetcode.com/problems/remove-k-digits/ Given a non-negative integer  num  represented as a string, remove  k  digits from the number so that the new number is the smallest possible. Note: The length of  num  is less than 10002 and will be ≥  k . The given  num  does not contain any leading zero. Example 1: Input: num = "1432219", k = 3 Output: "1219" Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest. Example 2: Input: num = "10200", k = 1 Output: "200" Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes. Example 3: Input: num = "10", k = 2 Output: "0" Explanation: Remove all the digits from the number and it is left with nothing which is 0. ---

https://leetcode.com/problems/score-of-parentheses/ Given a balanced parentheses string  S , compute the score of the string based on the following rule: ()  has score 1 AB  has score  A + B , where A and B are balanced parentheses strings. (A)  has score  2 * A , where A is a balanced parentheses string.   Example 1: Input: "()" Output: 1 Example 2: Input: "(())" Output: 2 Example 3: Input: "()()" Output: 2 Example 4: Input: "(()(()))" Output: 6   Note: S  is a balanced parentheses string, containing only  (  and  ) . 2 <= S.length <= 50 ---- Intuition Only () contribute to final score ---

https://app.codesignal.com/interview-practice/task/MdHZFgZFERPPagfdD/description Note: Write a solution with  O(n)  complexity, since this is what you would be asked to do during a real interview. Given an array  a  composed of distinct elements, find the next larger element for each element of the array, i.e. the first element to the right that is greater than this element, in the order in which they appear in the array, and return the results as a new array of the same length. If an element does not have a larger element to its right, put  -1  in the appropriate cell of the result array. Example For  a = [6, 7, 3, 8] , the output should be nextLarger(a) = [7, 8, 8, -1] . In this array, the next larger element for  6  is  7 , for  7  is  8 , for  3  is  8  ( 7  is not a valid option since elements from  a  can only be compared to elements to their right), and for  8  there is no such element, so we put  -1  in the last cell. Input/Output [execution time limit] 3 seconds (java) [input]

https://app.codesignal.com/interview-practice/task/5vXzdE9yzjsoMZ9sk/description Given a string  str  and array of  pairs  that indicates which indices in the string can be swapped, return the  lexicographically largest  string that results from doing the allowed swaps. You can swap indices any number of times. Example For  str = "abdc"  and  pairs = [[1, 4], [3, 4]] , the output should be swapLexOrder(str, pairs) = "dbca" . By swapping the given indices, you get the strings:  "cbda" ,  "cbad" ,  "dbac" ,  "dbca" . The lexicographically largest string in this list is  "dbca" . Input/Output [execution time limit] 3 seconds (java) [input] string str A string consisting only of lowercase English letters. Guaranteed constraints: 1 ≤ str.length ≤ 10 4 . [input] array.array.integer pairs An array containing pairs of indices that can be swapped in  str  (1-based). This means that for each  pairs[i] , you can swap elements i

https://app.codesignal.com/interview-practice/task/Ki9zRh5bfRhH6oBau/description You have two arrays of strings,  words  and  parts . Return an array that contains the strings from  words , modified so that any occurrences of the substrings from  parts  are surrounded by square brackets  [] , following these guidelines: If several  parts  substrings occur in one string in  words , choose the longest one. If there is still more than one such part, then choose the one that appears first in the string. Example For  words = ["Apple", "Melon", "Orange", "Watermelon"]  and  parts = ["a", "mel", "lon", "el", "An"] , the output should be findSubstrings(words, parts) = ["Apple", "Me[lon]", "Or[a]nge", "Water[mel]on"] . While  "Watermelon"  contains three substrings from the  parts  array,  "a" ,  "mel" , and  "lon" ,  "mel