SWE Interview preparation

https://leetcode.com/problems/sliding-window-median/ Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value. Examples: [2,3,4]  , the median is  3 [2,3] , the median is  (2 + 3) / 2 = 2.5 Given an array  nums , there is a sliding window of size  k  which is moving from the very left of the array to the very right. You can only see the  k  numbers in the window. Each time the sliding window moves right by one position. Your job is to output the median array for each window in the original array. For example, Given  nums  =  [1,3,-1,-3,5,3,6,7] , and  k  = 3. Window position Median --------------- ----- [1 3 -1] -3 5 3 6 7 1 1 [3 -1 -3] 5 3 6 7 -1 1 3 [-1 -3 5] 3 6 7 -1 1 3 -1 [-3 5 3] 6 7 3 1 3 -1 -3 [5 3 6] 7 5 1 3 -1 -3...

https://leetcode.com/problems/the-skyline-problem/ A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are  given the locations and height of all the buildings  as shown on a cityscape photo (Figure A), write a program to  output the skyline  formed by these buildings collectively (Figure B).   The geometric information of each building is represented by a triplet of integers  [Li, Ri, Hi] , where  Li  and  Ri  are the x coordinates of the left and right edge of the ith building, respectively, and  Hi  is its height. It is guaranteed that  0 ≤ Li, Ri ≤ INT_MAX ,  0 < Hi ≤ INT_MAX , and  Ri - Li > 0 . You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0. For instance, the dimensions of all buildings in Figure A are recorded as:  [ [2 9 10], [3 7 15], [5 12...

https://leetcode.com/problems/third-maximum-number/ Given a  non-empty  array of integers, return the  third  maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n). Example 1: Input: [3, 2, 1] Output: 1 Explanation: The third maximum is 1. Example 2: Input: [1, 2] Output: 2 Explanation: The third maximum does not exist, so the maximum (2) is returned instead. Example 3: Input: [2, 2, 3, 1] Output: 1 Explanation: Note that the third maximum here means the third maximum distinct number. Both numbers with value 2 are both considered as second maximum. --- Time - O(n log 3) => O(n) Space - O(n) - for Set, PQ also has contains method that can reduce space to O(1)

https://leetcode.com/problems/top-k-frequent-elements/ Given a non-empty array of integers, return the  k  most frequent elements. Example 1: Input: nums = [1,1,1,2,2,3] , k = 2 Output: [1,2] Example 2: Input: nums = [1] , k = 1 Output: [1] Note: You may assume  k  is always valid, 1 ≤  k  ≤ number of unique elements. Your algorithm's time complexity  must be  better than O( n  log  n ), where  n  is the array's size. --- Intuition Top K, Max K, Most K => Min Heap Traverse the array We capture the min freq words from 1 upto current element in the min heap If heap size grows beyond k, then top element is least frequent word so far, not a candidate for final solution, so we trash it At the end of array traversal we've trashed out less frequent words, and k remain ---- Time - O(n * log(k)) Space - O(k) ---

https://leetcode.com/problems/k-closest-points-to-origin/ We have a list of  points  on the plane.  Find the  K  closest points to the origin  (0, 0) . (Here, the distance between two points on a plane is the Euclidean distance.) You may return the answer in any order.  The answer is guaranteed to be unique (except for the order that it is in.) Example 1: Input: points = [[1,3],[-2,2]] , K = 1 Output: [[-2,2]] Explanation: The distance between (1, 3) and the origin is sqrt(10). The distance between (-2, 2) and the origin is sqrt(8). Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin. We only want the closest K = 1 points from the origin, so the answer is just [[-2,2]]. Example 2: Input: points = [[3,3],[5,-1],[-2,4]] , K = 2 Output: [[3,3],[-2,4]] (The answer [[-2,4],[3,3]] would also be accepted.) Note: 1 <= K <= points.length <= 10000 -10000 < points[i][0] < 10000 -10000 < points[i][1] ...