SWE Interview preparation

https://leetcode.com/problems/find-lucky-integer-in-an-array/ Given an array of integers  arr , a lucky integer is an integer which has a frequency in the array equal to its value. Return  a lucky integer  in the array. If there are multiple lucky integers return the  largest  of them. If there is no lucky integer return  -1 . Example 1: Input: arr = [2,2,3,4] Output: 2 Explanation: The only lucky number in the array is 2 because frequency[2] == 2. Example 2: Input: arr = [1,2,2,3,3,3] Output: 3 Explanation: 1, 2 and 3 are all lucky numbers, return the largest of them. Example 3: Input: arr = [2,2,2,3,3] Output: -1 Explanation: There are no lucky numbers in the array. Example 4: Input: arr = [5] Output: -1 Example 5: Input: arr = [7,7,7,7,7,7,7] Output: 7 Constraints: 1 <= arr.length <= 500 1 <= arr[i] <= 500 ---

https://leetcode.com/problems/compare-strings-by-frequency-of-the-smallest-character/ Let's define a function  f(s)  over a non-empty string  s , which calculates the frequency of the smallest character in  s . For example, if  s = "dcce"  then  f(s) = 2  because the smallest character is  "c"  and its frequency is 2. Now, given string arrays  queries  and  words , return an integer array  answer , where each  answer[i]  is the number of words such that  f(queries[i])  <  f(W) , where  W  is a word in  words . Example 1: Input: queries = ["cbd"], words = ["zaaaz"] Output: [1] Explanation: On the first query we have f("cbd") = 1, f("zaaaz") = 3 so f("cbd") < f("zaaaz"). Example 2: Input: queries = ["bbb","cc"], words = ["a","aa","aaa","aaaa"] Output: [1,2] Explanation: On the first query only f("bbb") < f(...

https://leetcode.com/problems/search-in-rotated-sorted-array-ii/ Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e.,  [0,0,1,2,2,5,6]  might become  [2,5,6,0,0,1,2] ). You are given a target value to search. If found in the array return  true , otherwise return  false . Example 1: Input: nums = [2 ,5,6,0,0,1,2] , target = 0 Output: true Example 2: Input: nums = [2 ,5,6,0,0,1,2] , target = 3 Output: false Follow up: This is a follow up problem to  Search in Rotated Sorted Array , where  nums  may contain duplicates. Would this affect the run-time complexity? How and why? ----

https://leetcode.com/problems/evaluate-reverse-polish-notation/ Evaluate the value of an arithmetic expression in  Reverse Polish Notation . Valid operators are  + ,  - ,  * ,  / . Each operand may be an integer or another expression. Note: Division between two integers should truncate toward zero. The given RPN expression is always valid. That means the expression would always evaluate to a result and there won't be any divide by zero operation. Example 1: Input: ["2", "1", "+", "3", "*"] Output: 9 Explanation: ((2 + 1) * 3) = 9 Example 2: Input: ["4", "13", "5", "/", "+"] Output: 6 Explanation: (4 + (13 / 5)) = 6 Example 3: Input: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"] Output: 22 Explanation: ...

https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/ Given a  n  x  n  matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix. Note that it is the kth smallest element in the sorted order, not the kth distinct element. Example: matrix = [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15] ], k = 8, return 13. Note: You may assume k is always valid, 1 ≤ k ≤ n 2 ---- Intuition 0, 0 is first candidate Next two candidates are 0, 1 and 1, 0 With two numbers, its easy to directly compare. This boundary of search will expand over time, and we need access to lowest number from candidates We can use min priority queue to get us the lowest number from candidates Put both 0, 1 and 1,0 into Priotity Queue k-- Take min from top and then add its neighbors 1, 1 is neighbor for both 0, 1 and 1,0 To prevent double counting, we apply a check Add r, c + 1 -- always Add r + 1, c...

https://leetcode.com/problems/find-k-pairs-with-smallest-sums/ You are given two integer arrays  nums1  and  nums2  sorted in ascending order and an integer  k . Define a pair  (u,v)  which consists of one element from the first array and one element from the second array. Find the k pairs  (u 1 ,v 1 ),(u 2 ,v 2 ) ...(u k ,v k )  with the smallest sums. Example 1: Input: nums1 = [1,7,11] , nums2 = [2,4,6] , k = 3 Output: [[1,2],[1,4],[1,6]] Explanation: The first 3 pairs are returned from the sequence:   [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6] Example 2: Input: nums1 = [1,1,2], nums2 = [1,2,3], k = 2 Output: [1,1],[1,1] Explanation: The first 2 pairs are returned from the sequence:   [1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3] Example 3: Input: nums1 = [1,2], nums2 = [3], k = 3 Output: [1,3],[2,3] Explanation: All possible pairs are returned from the sequence: [...

https://www.lintcode.com/problem/moving-average-from-data-stream/description https://leetcode.com/problems/moving-average-from-data-stream Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window. Example: MovingAverage m = new MovingAverage(3); m.next(1) = 1 m.next(10) = (1 + 10) / 2 m.next(3) = (1 + 10 + 3) / 3 m.next(5) = (10 + 3 + 5) / 3  ---