Posts

Showing posts from November, 2022

Max Meetings in a Room

 https://workat.tech/problem-solving/practice/max-meetings-in-a-room Given the start and finish time of  n  meetings and just one room to conduct them, find the maximum number of meetings that can be accommodated in that room. The start and end times are given in minutes from 12:00 AM Example: Meetings (Start, End): [(3, 29), (50, 93), (88, 92), (54, 67), (50, 87)] Max possible meetings: 3 Testing Input Format The first line contains an integer ‘ T ’ denoting the number of test cases. For each test case, the input contains the following lines: The first line contains an integer  n  denoting the numbers of meetings. The next  n  lines, each have two space-separated integers-  start i  and  end i  denoting the start and end time of each meeting. Output Format One line for each test case, with the maximum number of meetings possible. Sample Input 4 5 3 29 50 93 88 92 54 67 50 87 5 66 77 55 94 73 79 90 97 43 62 7 57 62 36 80 50 94 12 75...

Bottom View of Binary Tree

Image
 https://workat.tech/problem-solving/practice/bottom-view-binary-tree There are different ways to look at a binary tree. The bottom view of a binary tree contains the set of nodes that will be visible if you look at the binary tree from the bottom. Note: If there are multiple bottom-most nodes for a horizontal distance from root, use the later one in level-order traversal. Given the root node of a binary tree, return an array containing the node elements in the bottom view, from left to right. Testing Input Format The first line contains an integer  T  denoting the number of test cases. For each test case, the input has 2 lines: The first line contains an integer  n  denoting the number of nodes in the tree (including the NULL nodes). The second line contains  n  space-separated integers that will form the binary tree. The integers follow level order traversal of the tree where -1 indicates a NULL node. Output Format For each test case, the output cont...

Top View of Binary Tree

Image
 https://workat.tech/problem-solving/practice/top-view-binary-tree There are different ways to look at a binary tree. The top view of a binary tree contains the set of nodes that will be visible if you look at the binary tree from the top. Given the root node of a binary tree, return an array containing the node elements in the top view, from left to right. Note: The first level is traversed left to right. Testing Input Format The first line contains an integer  T  denoting the number of test cases. For each test case, the input has 2 lines: The first line contains an integer  n  denoting the number of nodes in the tree (including the NULL nodes). The second line contains  n  space-separated integers that will form the binary tree. The integers follow level order traversal of the tree where -1 indicates a NULL node. Output Format For each test case, the output contains a line with space-separated integers representing the top view of the binary tree. S...

Negative numbers in sorted array

Negative numbers in sorted array Given a sorted array of integers, find the number of negative numbers. Expected Time Complexity: O(log n) Examples Array: [-5, -3, -2, 3, 4, 6, 7, 8] Answer: 3 Array: [0, 1, 2, 3, 4, 6, 7, 8] Answer: 0 --- Intuition Sorted array => binary search Find last index of number matching condition If does not match condition - switch search space to other half if matches condition - save, and reduce search space in current half --- Complexity Time - O(log N) Space - O(1) - iterative --- ---

391 · Number of Airplanes in the Sky

  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 ...

6. Zigzag Conversion

 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 ...