SWE Interview preparation

https://leetcode.com/problems/meeting-scheduler/description/ Given the availability time slots arrays  slots1  and  slots2  of two people and a meeting duration  duration , return the  earliest time slot  that works for both of them and is of duration  duration . If there is no common time slot that satisfies the requirements, return an  empty array . The format of a time slot is an array of two elements  [start, end]  representing an inclusive time range from  start  to  end . It is guaranteed that no two availability slots of the same person intersect with each other. That is, for any two time slots  [start1, end1]  and  [start2, end2]  of the same person, either  start1 > end2  or  start2 > end1 .   Example 1: Input: slots1 = [[10,50],[60,120],[140,210]], slots2 = [[0,15],[60,70]], duration = 8 Output: [60,68] Example 2: Input: slots1 = [[10,50],[60,120],[140,210]], ...

 https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/ Given the  head  of a sorted linked list,  delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list . Return  the linked list  sorted  as well .   Example 1: Input: head = [1,2,3,3,4,4,5] Output: [1,2,5] Example 2: Input: head = [1,1,1,2,3] Output: [2,3]   Constraints: The number of nodes in the list is in the range  [0, 300] . -100 <= Node.val <= 100 The list is guaranteed to be  sorted  in ascending order. ---- Intuition Maintain previous pointer - initialized to dummy node before head while head != null      if duplicates found          while duplicates               advance head          disconnect start of duplicate          prev.next = head.next      else ...

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/ https://workat.tech/problem-solving/practice/two-sum-sorted Given an array of integers that is already  sorted in ascending order , find two numbers such that they add up to a specific target number. The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Note: Your returned answers (both index1 and index2) are not zero-based. You may assume that each input would have  exactly  one solution and you may not use the  same  element twice. Example: Input: numbers = [2,7,11,15], target = 9 Output: [1,2] Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2. ---

https://leetcode.com/problems/max-consecutive-ones-iii/ Given an array  A  of 0s and 1s, we may change up to  K  values from 0 to 1. Return the length of the longest (contiguous) subarray that contains only 1s.  Example 1: Input: A = [1,1,1,0,0,0,1,1,1,1,0] , K = 2 Output: 6 Explanation: [1,1,1,0,0, 1 ,1,1,1,1, 1 ] Bolded numbers were flipped from 0 to 1. The longest subarray is underlined. Example 2: Input: A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1] , K = 3 Output: 10 Explanation: [0,0, 1,1, 1 , 1 ,1,1,1, 1 ,1,1 ,0,0,0,1,1,1,1] Bolded numbers were flipped from 0 to 1. The longest subarray is underlined. Note: 1 <= A.length <= 20000 0 <= K <= A.length A[i]  is  0  or  1   -----

https://leetcode.com/problems/interval-list-intersections/ Given two lists of  closed  intervals, each list of intervals is pairwise disjoint and in sorted order. Return the intersection of these two interval lists. (Formally, a closed interval  [a, b]  (with  a <= b ) denotes the set of real numbers  x  with  a <= x <= b .  The intersection of two closed intervals is a set of real numbers that is either empty, or can be represented as a closed interval.  For example, the intersection of [1, 3] and [2, 4] is [2, 3].) Example 1: Input: A = [[0,2],[5,10],[13,23],[24,25]] , B = [[1,5],[8,12],[15,24],[25,26]] Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]] Reminder: The inputs and the desired output are lists of Interval objects, and not arrays or lists. Note: 0 <= A.length < 1000 0 <= B.length < 1000 0 <= A[i].start, A[i].end, B[i].start, B[i].end < 10^9 --- C...

https://leetcode.com/problems/valid-palindrome/ Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases. Note:  For the purpose of this problem, we define empty string as valid palindrome. Example 1: Input: "A man, a plan, a canal: Panama" Output: true Example 2: Input: "race a car" Output: false ---

https://leetcode.com/problems/longest-substring-without-repeating-characters/ Given a string, find the length of the  longest substring  without repeating characters. Example 1: Input: "abcabcbb" Output: 3 Explanation: The answer is "abc" , with the length of 3. Example 2: Input: "bbbbb" Output: 1 Explanation: T he answer is "b" , with the length of 1. Example 3: Input: "pwwkew" Output: 3 Explanation: The answer is "wke" , with the length of 3. Note that the answer must be a substring , "pwke" is a subsequence and not a substring. --- Intuition Record unique character, and its last seen position Sliding window - Expand till you see unique characters Shrink when next character is duplicate - shrink window to exclude duplicate character ---

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....

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/convert-sorted-list-to-binary-search-tree/ Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST. For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of  every  node never differ by more than 1. Example: Given the sorted linked list: [-10,-3,0,5,9], One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST: 0 / \ -3 9 / / -10 5 --- Intuition Find the mid point of list using fast, slow pointers mid element of list is root of tree set the prev to mid to null head to prev is first half - left child .. recurse mid.next is second half - right child ..recurse * base case of recursion is when head == mid .. only one element in the list --- Time - O( log N) - we divide the list log N times till 1 element Space - O( log N) - recursion call stack --- Re...