SWE Interview preparation

  391 · Number of Airplanes in the Sky Description Given an list  interval , which are taking off and landing time of the flight. How many airplanes are there at most at the same time in the sky? If landing and taking off of different planes happen at the same time, we consider landing should happen at first. Example Example 1: Input : [(1, 10), (2, 3), (5, 8), (4, 7)] Output : 3 Explanation : The first airplane takes off at 1 and lands at 10 . The second ariplane takes off at 2 and lands at 3 . The third ariplane takes off at 5 and lands at 8 . The forth ariplane takes off at 4 and lands at 7 . During 5 to 6 , there are three airplanes in the sky. Example 2: Input: [( 1 , 2 ), ( 2 , 3 ), ( 3 , 4 )] Output: 1 Explanation: Landing happen before taking off. --- Clarifying questions What is expected when takeoff and land times are same Intuition Event scan algorithm Sort events by time Corner case when time is same, put land times first, so high water mark is ...

https://leetcode.com/problems/lemonade-change/ At a lemonade stand, each lemonade costs  $5 .  Customers are standing in a queue to buy from you, and order one at a time (in the order specified by  bills ). Each customer will only buy one lemonade and pay with either a  $5 ,  $10 , or  $20  bill.  You must provide the correct change to each customer, so that the net transaction is that the customer pays $5. Note that you don't have any change in hand at first. Return  true  if and only if you can provide every customer with correct change.   Example 1: Input: [5,5,5,10,20] Output: true Explanation: From the first 3 customers, we collect three $5 bills in order. From the fourth customer, we collect a $10 bill and give back a $5. From the fifth customer, we give a $10 bill and a $5 bill. Since all customers got correct change, we output true. Example 2: Input: [5,5,10] Output: true Example 3: Input: [10,10] Output: fal...

https://github.com/openset/leetcode/tree/master/problems/find-leaves-of-binary-tree https://leetcode.com/problems/find-leaves-of-binary-tree/ https://www.lintcode.com/problem/find-leaves-of-binary-tree/description Given a binary tree, collect a tree's nodes as if you were doing this: Collect and remove all leaves, repeat until the tree is empty.   Example: Input: [1,2,3,4,5]     1 / \ 2 3 / \ 4 5 Output: [[4,5,3],[2],[1]]   Explanation: 1. Removing the leaves  [4,5,3]  would result in this tree: 1 / 2   2. Now removing the leaf  [2]  would result in this tree: 1   3. Now removing the leaf  [1]  would result in the empty tree: [] ----- Intuition Need info from both left, and right child to determine if current node is leaf node Post Order DFS Consider looking up the tree from below where the level is...

https://leetcode.com/problems/connecting-cities-with-minimum-cost/ https://github.com/openset/leetcode/tree/master/problems/connecting-cities-with-minimum-cost There are  N  cities numbered from 1 to  N . You are given  connections , where each  connections[i] = [city1, city2, cost]  represents the cost to connect  city1  and  city2  together.  (A  connection  is bidirectional: connecting  city1  and  city2  is the same as connecting  city2  and  city1 .) Return the minimum cost so that for every pair of cities, there exists a path of connections (possibly of length 1) that connects those two cities together.  The cost is the sum of the connection costs used. If the task is impossible, return -1.   Example 1: Input: N = 3, connections = [[1,2,5],[1,3,6],[2,3,1]] Output: 6 Explanation: Choosing any 2 edges will connect all cities so we choose the minimum 2. Example 2: Input...

https://leetcode.com/problems/critical-connections-in-a-network/ There are  n  servers numbered from  0  to  n-1  connected by undirected server-to-server  connections  forming a network where  connections[i] = [a, b]  represents a connection between servers  a  and  b . Any server can reach any other server directly or indirectly through the network. A  critical connection  is a connection that, if removed, will make some server unable to reach some other server. Return all critical connections in the network in any order. Example 1: Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]] Output: [[1,3]] Explanation: [[3,1]] is also accepted. Constraints: 1 <= n <= 10^5 n-1 <= connections.length <= 10^5 connections[i][0] != connections[i][1] There are no repeated connections. ---

https://leetcode.com/problems/trapping-rain-water-ii/ Given an  m x n  matrix of positive integers representing the height of each unit cell in a 2D elevation map, compute the volume of water it is able to trap after raining. Example: Given the following 3x6 height map: [ [1,4,3,1,3,2], [3,2,1,3,2,4], [2,3,3,2,3,1] ] Return 4. The above image represents the elevation map  [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]  before the rain.   After the rain, water is trapped between the blocks. The total volume of water trapped is 4.   Constraints: 1 <= m, n <= 110 0 <= heightMap[i][j] <= 20000 ---

https://leetcode.com/problems/minimum-cost-to-connect-sticks/ https://github.com/openset/leetcode/tree/master/problems/minimum-cost-to-connect-sticks https://www.lintcode.com/problem/minimum-cost-to-connect-sticks/description You have some  sticks  with positive integer lengths. You can connect any two sticks of lengths  X  and  Y  into one stick by paying a cost of  X + Y .  You perform this action until there is one stick remaining. Return the minimum cost of connecting all the given  sticks  into one stick in this way.   Example 1: Input: sticks = [2,4,3] Output: 14 Example 2: Input: sticks = [1,8,3,5] Output: 30   Constraints: 1 <= sticks.length <= 10^4 1 <= sticks[i] <= 10^4 --- Intuition Stick continues to add to ans till only 1 remains.  If we take larger sticks in the beginning, ans will increase too much Take greedy approach - always the 2 min sticks After merging, we need to find 2 ...

https://leetcode.com/problems/longest-palindromic-substring/ Given a string  s , find the longest palindromic substring in  s . You may assume that the maximum length of  s  is 1000. Example 1: Input: "babad" Output: "bab" Note: "aba" is also a valid answer. Example 2: Input: "cbbd" Output: "bb"

https://leetcode.com/problems/meeting-rooms-ii/ https://www.lintcode.com/problem/meeting-rooms-ii/description Given an array of meeting time intervals consisting of start and end times  [[s1,e1],[s2,e2],...]  (s i  < e i ), find the minimum number of conference rooms required. Example 1: Input: [[0, 30],[5, 10],[15, 20]] Output: 2 Example 2: Input: [[7,10],[2,4]] Output: 1 --- Intuition Need to count the max number of overlaps Wrapper class - int time, boolean isStart Sort by time, if time is same => need to release the room first => Boolean.compare(a.isStart, b.isStart) Iterate through the sorted list of wrapper class     if start          rooms++     else          room--     ans= max(ans, rooms) --- Time - O(N log N) Space - O(N) --- Related problems 56-merge-intervals 252-meeting-rooms ---

https://leetcode.com/explore/challenge/card/30-day-leetcoding-challenge/531/week-4/3313/ https://leetcode.com/problems/first-unique-number You have a queue of integers, you need to retrieve the first unique integer in the queue. Implement the  FirstUnique  class: FirstUnique(int[] nums)  Initializes the object with the numbers in the queue. int showFirstUnique()  returns the value of  the first unique  integer of the queue, and returns  -1  if there is no such integer. void add(int value)  insert value to the queue. Example 1: Input: ["FirstUnique","showFirstUnique","add","showFirstUnique","add","showFirstUnique","add","showFirstUnique"] [[[2,3,5]],[],[5],[],[2],[],[3],[]] Output: [null,2,null,2,null,3,null,-1] Explanation: FirstUnique firstUnique = new FirstUnique([2,3,5]); firstUnique.showFirstUnique(); // return 2 firstUnique.add(5); // the queue is now [2,3,5,5] firstUnique.showFirs...

https://leetcode.com/problems/next-greater-element-i/ You are given two arrays  (without duplicates)   nums1  and  nums2  where  nums1 ’s elements are subset of  nums2 . Find all the next greater numbers for  nums1 's elements in the corresponding places of  nums2 . The Next Greater Number of a number  x  in  nums1  is the first greater number to its right in  nums2 . If it does not exist, output -1 for this number. Example 1: Input: nums1 = [4,1,2], nums2 = [1,3,4,2]. Output: [-1,3,-1] Explanation: For number 4 in the first array, you cannot find the next greater number for it in the second array, so output -1. For number 1 in the first array, the next greater number for it in the second array is 3. For number 2 in the first array, there is no next greater number for it in the second array, so output -1. Example 2: Input: nums1 = [2,4], nums2 = [1,2,3,4]. Output: [3,-1] Explanation:...

https://leetcode.com/problems/find-median-from-data-stream/ 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. For example, [2,3,4] , the median is  3 [2,3] , the median is  (2 + 3) / 2 = 2.5 Design a data structure that supports the following two operations: void addNum(int num) - Add a integer number from the data stream to the data structure. double findMedian() - Return the median of all elements so far. Example: addNum(1) addNum(2) findMedian() -> 1.5 addNum(3) findMedian() -> 2 Follow up: If all integer numbers from the stream are between 0 and 100, how would you optimize it? If 99% of all integer numbers from the stream are between 0 and 100, how would you optimize it? ----