SWE Interview preparation

https://leetcode.com/problems/first-unique-character-in-a-string/ Given a string, find the first non-repeating character in it and return it's index. If it doesn't exist, return -1. Examples: s = "leetcode" return 0. s = "loveleetcode", return 2. Note:  You may assume the string contain only lowercase letters. --- First unique character means we have to check all characters, time complexity is linear Time  - O(n) Space  - O(1)

https://leetcode.com/problems/range-sum-query-immutable/ Given an integer array  nums , find the sum of the elements between indices  i  and  j  ( i  ≤  j ), inclusive. Example: Given nums = [-2, 0, 3, -5, 2, -1] sumRange(0, 2) -> 1 sumRange(2, 5) -> -1 sumRange(0, 5) -> -3 Note: You may assume that the array does not change. There are many calls to  sumRange  function. ---

https://leetcode.com/problems/find-peak-element/ A peak element is an element that is greater than its neighbors. Given an input array  nums , where  nums[i] ≠ nums[i+1] , find a peak element and return its index. The array may contain multiple peaks, in that case return the index to any one of the peaks is fine. You may imagine that  nums[-1] = nums[n] = -∞ . Example 1: Input: nums = [1,2,3,1] Output: 2 Explanation: 3 is a peak element and your function should return the index number 2. Example 2: Input: nums = [ 1,2,1,3,5,6,4] Output: 1 or 5 Explanation: Your function can return either index number 1 where the peak element is 2,   or index number 5 where the peak element is 6. Note: Your solution should be in logarithmic complexity. --- Intuition Use standard binary search with loop termination l <= r if arr[mid] > arr[mid - 1] => mid is potential answer, save it, continue search with l = mid + 1 else discar...

https://leetcode.com/problems/peak-index-in-a-mountain-array/ Let's call an array  A  a  mountain  if the following properties hold: A.length >= 3 There exists some  0 < i < A.length - 1  such that  A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1] Given an array that is definitely a mountain, return any  i  such that  A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1] . Example 1: Input: [0,1,0] Output: 1 Example 2: Input: [0,2,1,0] Output: 1 Note: 3 <= A.length <= 10000 0 <= A[i] <= 10^6 A is a mountain, as defined above. ---- Intuition Linear scan is trivial To do better than linear we need to use info that this is a mountain array, so sorted increasing till the peak, then sorted descending --- Standard binary search - loop termination l <= h if arr[mid] > arr[mid - 1] => we found potential ...

https://leetcode.com/problems/flood-fill/ An  image  is represented by a 2-D array of integers, each integer representing the pixel value of the image (from 0 to 65535). Given a coordinate  (sr, sc)  representing the starting pixel (row and column) of the flood fill, and a pixel value  newColor , "flood fill" the image. To perform a "flood fill", consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color as the starting pixel), and so on. Replace the color of all of the aforementioned pixels with the newColor. At the end, return the modified image. Example 1: Input: image = [[1,1,1],[1,1,0],[1,0,1]] sr = 1, sc = 1, newColor = 2 Output: [[2,2,2],[2,2,0],[2,0,1]] Explanation: From the center of the image (with position (sr, sc) = (1, 1)), all pixels connected by a path of the same color as...

https://leetcode.com/problems/island-perimeter/ You are given a map in form of a two-dimensional integer grid where 1 represents land and 0 represents water. Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells). The island doesn't have "lakes" (water inside that isn't connected to the water around the island). One cell is a square with side length 1. The grid is rectangular, width and height don't exceed 100. Determine the perimeter of the island. Example: Input: [[0,1,0,0], [1,1,1,0], [0,1,0,0], [1,1,0,0]] Output: 16 Explanation: The perimeter is the 16 yellow stripes in the image below: --- Intuition Each cell with value contributes the number of borders + number of neighbors with 0 value to the  perimeter Iterative is faster than calling a helper function to loop in four directions --- Time - O(r * c)...

https://leetcode.com/problems/move-zeroes/ Given an array  nums , write a function to move all  0 's to the end of it while maintaining the relative order of the non-zero elements. Example: Input: [0,1,0,3,12] Output: [1,3,12,0,0] Note : You must do this  in-place  without making a copy of the array. Minimize the total number of operations. -- Time - O(n) Space - O(1) ---

https://leetcode.com/problems/can-place-flowers/ Suppose you have a long flowerbed in which some of the plots are planted and some are not. However, flowers cannot be planted in adjacent plots - they would compete for water and both would die. Given a flowerbed (represented as an array containing 0 and 1, where 0 means empty and 1 means not empty), and a number  n , return if  n  new flowers can be planted in it without violating the no-adjacent-flowers rule. Example 1: Input: flowerbed = [1,0,0,0,1], n = 1 Output: True Example 2: Input: flowerbed = [1,0,0,0,1], n = 2 Output: False Note: The input array won't violate no-adjacent-flowers rule. The input array size is in the range of [1, 20000]. n  is a non-negative integer which won't exceed the input array size. --

https://leetcode.com/problems/remove-duplicates-from-sorted-array/ Given a sorted array  nums , remove the duplicates  in-place  such that each element appear only  once  and return the new length. Do not allocate extra space for another array, you must do this by  modifying the input array  in-place  with O(1) extra memory. Example 1: Given nums = [1,1,2] , Your function should return length = 2 , with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the returned length. Example 2: Given nums = [0,0,1,1,1,2,2,3,3,4] , Your function should return length = 5 , with the first five elements of nums being modified to  0 , 1 , 2 , 3 , and  4 respectively. It doesn't matter what values are set beyond the returned length. Clarification: Confused why the returned value is an integer but your answer is an array? Note that the input array is passed in by  refe...

https://leetcode.com/problems/intersection-of-two-arrays/ Given two arrays, write a function to compute their intersection. Example 1: Input: nums1 = [1,2,2,1] , nums2 = [2,2] Output: [2] Example 2: Input: nums1 = [4,9,5] , nums2 = [9,4,9,8,4] Output: [9,4] Note: Each element in the result must be unique. The result can be in any order. ---

https://leetcode.com/problems/n-th-tribonacci-number/ The Tribonacci sequence T n  is defined as follows:  T 0  = 0, T 1  = 1, T 2  = 1, and T n+3  = T n  + T n+1  + T n+2  for n >= 0. Given  n , return the value of T n . Example 1: Input: n = 4 Output: 4 Explanation: T_3 = 0 + 1 + 1 = 2 T_4 = 1 + 1 + 2 = 4 Example 2: Input: n = 25 Output: 1389537 Constraints: 0 <= n <= 37 The answer is guaranteed to fit within a 32-bit integer, ie.  answer <= 2^31 - 1 . --- Intuition Similar to Fibonacci series F(N) = F(N - 1) + F(N - 2) + F(N - 3) We just need last three entries, no need for full DP table ---- Time - O(n) Space - O(1) --- Related problems climbing-stairs ---

https://leetcode.com/problems/climbing-stairs/ You are climbing a stair case. It takes  n  steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? Note:  Given  n  will be a positive integer. Example 1: Input: 2 Output: 2 Explanation: There are two ways to climb to the top. 1. 1 step + 1 step 2. 2 steps Example 2: Input: 3 Output: 3 Explanation: There are three ways to climb to the top. 1. 1 step + 1 step + 1 step 2. 1 step + 2 steps 3. 2 steps + 1 step --- Intuition How can we reach stair n One step from n - 1 or Two steps from n - 2 # ways to reach n = # ways to reach (n -1) + # ways to reach (n - 2) F(n) = F(n - 1) + F(n -2) Recursion with memoization. We do not need all past entries, just two last ones are sufficient - constant space -- Time - O(n) Space - O(1) -- Related problems min-cost-climbing-stairs

https://leetcode.com/problems/most-common-word/ Given a paragraph and a list of banned words, return the most frequent word that is not in the list of banned words.  It is guaranteed there is at least one word that isn't banned, and that the answer is unique. Words in the list of banned words are given in lowercase, and free of punctuation.  Words in the paragraph are not case sensitive.  The answer is in lowercase. Example: Input: paragraph = "Bob hit a ball, the hit BALL flew far after it was hit." banned = ["hit"] Output: "ball" Explanation: "hit" occurs 3 times, but it is a banned word. "ball" occurs twice (and no other word does), so it is the most frequent non-banned word in the paragraph. Note that words in the paragraph are not case sensitive, that punctuation is ignored (even if adjacent to words, such as "ball,"), and that "hit" isn't the answer even though it occurs more because i...

https://leetcode.com/problems/longest-common-prefix/ Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string  "" . Example 1: Input: ["flower","flow","flight"] Output: "fl" Example 2: Input: ["dog","racecar","car"] Output: "" Explanation: There is no common prefix among the input strings. Note: All given inputs are in lowercase letters  a-z . ---