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/zigzag-conversion/ The string  "PAYPALISHIRING"  is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility) P A H N A P L S I I G Y I R And then read line by line:  "PAHNAPLSIIGYIR" Write the code that will take a string and make this conversion given a number of rows: string convert(string s, int numRows);   Example 1: Input: s = "PAYPALISHIRING", numRows = 3 Output: "PAHNAPLSIIGYIR" Example 2: Input: s = "PAYPALISHIRING", numRows = 4 Output: "PINALSIGYAHRPI" Explanation: P I N A L S I G Y A H R P I Example 3: Input: s = "A", numRows = 1 Output: "A"   Constraints: 1 <= s.length <= 1000 s  consists of English letters (lower-case and upper-case),  ','  and  '.' . 1 <= numRows <= 1000 --- Intuition Concatenate characters sequentially ...

https://leetcode.com/problems/meeting-rooms/ https://github.com/openset/leetcode/tree/master/problems/meeting-rooms https://www.lintcode.com/problem/meeting-rooms/description Given an array of meeting time intervals consisting of start and end times  [[s1,e1],[s2,e2],...]  (s i  < e i ), determine if a person could attend all meetings. Example 1: Input: [[0,30],[5,10],[15,20]] Output: false Example 2: Input: [[7,10],[2,4]] Output: true --- Related problems 253-meeting-rooms-ii 56-merge-intervals 391-number-of-airplanes-in-sky max-meetings-in-room --- Intuition Check for overlaps, if overlap => false To check for overlaps, we need to pick one way of ordering rooms Sort by start time or end time ascending - doesn't matter which time If start time of current < end time of previous => overlap => return false --- Time - O(N log N) Space - O(1) ---

https://leetcode.com/problems/employee-free-time/ https://github.com/openset/leetcode/tree/master/problems/employee-free-time We are given a list  schedule  of employees, which represents the working time for each employee. Each employee has a list of non-overlapping  Intervals , and these intervals are in sorted order. Return the list of finite intervals representing  common, positive-length free time  for  all  employees, also in sorted order. Example 1: Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]] Output: [[3,4]] Explanation: There are a total of three employees, and all common free time intervals would be [-inf, 1], [3, 4], [10, inf]. We discard any intervals that contain inf as they aren't finite.   Example 2: Input: schedule = [[[1,3],[6,7]],[[2,4]],[[2,5],[9,12]]] Output: [[5,6],[7,9]]   (Even though we are representing  Intervals  in the form  [x, y] , the objects inside are  Intervals , not lists or arr...

https://leetcode.com/problems/diagonal-traverse-ii/ Given a list of lists of integers,  nums , return all elements of  nums  in diagonal order as shown in the below images. Example 1: Input: nums = [[1,2,3],[4,5,6],[7,8,9]] Output: [1,4,2,7,5,3,8,6,9] Example 2: Input: nums = [[1,2,3,4,5],[6,7],[8],[9,10,11],[12,13,14,15,16]] Output: [1,6,2,8,7,3,9,4,12,10,5,13,11,14,15,16] Example 3: Input: nums = [[1,2,3],[4],[5,6,7],[8],[9,10,11]] Output: [1,4,2,5,3,8,6,9,7,10,11] Example 4: Input: nums = [[1,2,3,4,5,6]] Output: [1,2,3,4,5,6] Constraints: 1 <= nums.length <= 10^5 1 <= nums[i].length <= 10^5 1 <= nums[i][j] <= 10^9 There at most  10^5  elements in  nums . --- Intuition Elements on same diagonal share same r + c Save the size of each row to compute output size Add to output in reverse from each list, since the addition is in reverse direction --- Time - O(R * C) Space - O(R * C) --- Related problems 49...

https://leetcode.com/problems/clone-graph/ Given a reference of a node in a  connected  undirected graph. Return a  deep copy  (clone) of the graph. Each node in the graph contains a val ( int ) and a list ( List[Node] ) of its neighbors. class Node { public int val; public List<Node> neighbors; } Test case format: For simplicity sake, each node's value is the same as the node's index (1-indexed). For example, the first node with  val = 1 , the second node with  val = 2 , and so on. The graph is represented in the test case using an adjacency list. Adjacency list  is a collection of unordered  lists  used to represent a finite graph. Each list describes the set of neighbors of a node in the graph. The given node will always be the first node with  val = 1 . You must return the  copy of the given node  as a reference to the cloned graph. Example 1: Input: adj...

https://leetcode.com/problems/merge-intervals/ Given a collection of intervals, merge all overlapping intervals. Example 1: Input: [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6]. Example 2: Input: [[1,4],[4,5]] Output: [[1,5]] Explanation: Intervals [1,4] and [4,5] are considered overlapping. --- Clarifying questions Are time stamps which are exactly the same considered overlapping - example 2    Intuition Two approaches 1. Event Scan algorithm 2. Merge intervals --- Event Scan Event class - capture point, and isStart boolean for each interval point Sort with custom comparator if point values are same Boolean.compare(e2.isStart, e1.isStart) -- put Start points first * When counter becomes zero -- start to current point is merged interval --- Merge Intervals Sorting by start time allows to do Left to Right scan and merge overlapping with easy check Set pr...

https://leetcode.com/problems/pascals-triangle/ Given a non-negative integer  numRows , generate the first  numRows  of Pascal's triangle. In Pascal's triangle, each number is the sum of the two numbers directly above it. Example: Input: 5 Output: [ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ] --- Related problems 119-pascals-triangle-ii ---

https://leetcode.com/problems/triangle/ Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below. For example, given the following triangle [ [ 2 ], [ 3 ,4], [6, 5 ,7], [4, 1 ,8,3] ] The minimum path sum from top to bottom is  11  (i.e.,  2  +  3  +  5  +  1  = 11). Note: Bonus point if you are able to do this using only  O ( n ) extra space, where  n  is the total number of rows in the triangle. --- ---

https://leetcode.com/problems/rank-teams-by-votes/ In a special ranking system, each voter gives a rank from highest to lowest to all teams participated in the competition. The ordering of teams is decided by who received the most position-one votes. If two or more teams tie in the first position, we consider the second position to resolve the conflict, if they tie again, we continue this process until the ties are resolved. If two or more teams are still tied after considering all positions, we rank them alphabetically based on their team letter. Given an array of strings  votes  which is the votes of all voters in the ranking systems. Sort all teams according to the ranking system described above. Return  a string of all teams   sorted  by the ranking system. Example 1: Input: votes = ["ABC","ACB","ABC","ACB","ACB"] Output: "ACB" Explanation: Team A was ranked first place by 5 voters. No other team was vot...