Coding Problems and Solutions-7
[1] Largest Perimeter Island — Find the largest perimeter of an island given a 2 dimensional array of 1’s and 0’s representing land and water respectively.
Land = 1
Water = 0
Island = contiguous 1’s that are adjacent to other 1’s to the left, right, up, or down
Edge of an island = any 1 that is adjacent to a 0 OR grid boundary to the left, right, up, or down
Perimeter = total # of 1’s on the edge of an island
Example:
Input:
[[1, 0, 1, 1, 1],
[1, 0, 1, 1, 1],
[0, 1, 0, 1, 1]]Output: 7 (Island on the right)
(https://leetcode.com/discuss/interview-question/535473/Facebook-or-Phone-or-Largest-Perimeter-Island)
Approach — Use BFS (union-find) to find the largest island. For all points in largest island perimeter consists of:
- For each row the minimum and maximum columns.
- For each column the minimum and maximum rows.
[2] Shortest Distance from All Buildings —Y ou want to build a house on an empty land which reaches all buildings in the shortest amount of distance. You can only move up, down, left and right. You are given a 2D grid of values 0, 1 or 2, where:
- Each 0 marks an empty land which you can pass by freely.
- Each 1 marks a building which you cannot pass through.
- Each 2 marks an obstacle which you cannot pass through.
For example, given three buildings at (0,0), (0,4), (2,2), and an obstacle at (0,2):
1 - 0 - 2 - 0 - 1
| | | | |
0 - 0 - 0 - 0 - 0
| | | | |
0 - 0 - 1 - 0 - 0The point (1,2) is an ideal empty land to build a house, as the total travel distance of 3+3+1=7 is minimal. So return 7.
Approach — Use BFS to find the maximum distance of an empty land from any building. Choose the empty land with the minimum of max distance from any building.
[3] Candy Crush 1D — Write a function to crush candy in one dimensional board. In candy crushing games, groups of like items are removed from the board. In this problem, any sequence of 3 or more like items should be removed and any items adjacent to that sequence should now be considered adjacent to each other. This process should be repeated as many time as possible.
You should greedily remove characters from left to right.
Example 1:
Input: "aaabbbc"
Output: "c"
Explanation:
1. Remove 3 'a': "aaabbbc" => "bbbc"
2. Remove 3 'b': "bbbc" => "c"Example 2:
Input: "aabbbacd"
Output: "cd"
Explanation:
1. Remove 3 'b': "aabbbacd" => "aaacd"
2. Remove 3 'a': "aaacd" => "cd"(https://leetcode.com/discuss/interview-question/380650/)
Follow Up — What is the minimum size string you can obtain ?
Approach — Use backtracking.
Example:
Input: "aaabbbacd"
Output: "cd"
Explanation:
1. Remove 3 'b': "aaabbbacd" => "aaaacd"
2. Remove 4 'a': "aaaacd" => "cd"[4] Sliding Window Maximum — 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. Return the max sliding window.
Follow up:
Could you solve it in linear time?
Example:
Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
Output: [3,3,5,5,6,7]
Explanation: Window position Max
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
(https://leetcode.com/problems/sliding-window-maximum/)
Approach — Use max-heap with sliding window. At any time keep on removing any element in the heap with position less than the start of sliding window before taking the current sliding window minimum.
In Linear Time:
Approach — Use double ended queue. Idea is to maintain a deque in decreasing order of values i.e. the first element is the highest in the sliding window, 2nd element is next highest and so on.
For each i if the 1st element in deque is within the sliding window range of i, then it is kept else it is removed.
To maintain decreasing order, when the i-th element is added at the end remove all smaller elements from the end and then add.
[5] Find Most Similar Path In Graph — Imagine an undirected graph where the nodes represent airports.
For example:
Now, given this graph, write a function that accepts this graph and a path as input and finds a path in the graph most similar to it. The path is represented as a list of strings.
Example 1:
def find_most_similar_path(graph, ["ATH", "TBS", "DME"])
>>> ["ATH", "TBS", "DME"]Explanation: This path exists int he graph, so it itself is the most similar path.
def find_most_similar_path(graph, ["AXX", "TBS", "DME"])
>>> ["ATH", "TBS", "DME"]Explanation: The airport code AXX doesn’t exist. So they probably meant to say ATH.
def find_most_similar_path(graph, ["KPG", "DPS", "SIN", "AUH"])
>>> ["KUL", "DPS", "CGK", "AUH"]Explanation: The airport code KPG doesn’t exist, so they probably meant KUL. The airport code SIN exists, but there’s no direct route to AUH from there. So they probably meant to say CGK.
(https://leetcode.com/discuss/interview-question/691300/google-onsite-find-most-similar-path-in-graph)
Approach — Use BFS.
[6] Friend Circles — There are N students in a class. Some of them are friends, while some are not. Their friendship is transitive in nature. For example, if A is a direct friend of B, and B is a direct friend of C, then A is an indirect friend of C. And we defined a friend circle is a group of students who are direct or indirect friends.
Given a N*N matrix M representing the friend relationship between students in the class. If M[i][j] = 1, then the ith and jth students are direct friends with each other, otherwise not. And you have to output the total number of friend circles among all the students.
Example:
Input:
[[1,1,0],
[1,1,0],
[0,0,1]]
Output: 2
Explanation:The 0th and 1st students are direct friends, so they are in a friend circle.
The 2nd student himself is in a friend circle. So return 2.(https://leetcode.com/problems/friend-circles/)
Approach — Use Union-Finding with BFS. Create adjacency list from adjacency matrix, then do BFS.
[7] Sum of Nodes with Even-Valued Grandparent — Given a binary tree, return the sum of values of nodes with even-valued grandparent. (A grandparent of a node is the parent of its parent, if it exists.)
If there are no nodes with an even-valued grandparent, return 0.
Example:
Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
Output: 18
Explanation: The red nodes are the nodes with even-value grandparent while the blue nodes are the even-value grandparents.(https://leetcode.com/problems/sum-of-nodes-with-even-valued-grandparent/)
Approach — Use BFS and maintain the parent and grandparent of a node.
[8] Course Schedule — There are a total of n courses you have to take, labeled from 0 to n-1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.
There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.
Example:
Input: 4, [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3] or [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both
courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0.
So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3] .(https://leetcode.com/problems/course-schedule-ii/)
Approach — Use Topological Sorting.
[9] Sort Items by Groups Respecting Dependencies — There are n items each belonging to zero or one of m groups where group[i] is the group that the i-th item belongs to and it's equal to -1 if the i-th item belongs to no group. The items and the groups are zero indexed. A group can have no item belonging to it.
Return a sorted list of the items such that:
- The items that belong to the same group are next to each other in the sorted list.
- There are some relations between these items where
beforeItems[i]is a list containing all the items that should come before thei-th item in the sorted array (to the left of thei-th item).
Return any solution if there is more than one solution and return an empty list if there is no solution.
Example:
Input: n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3,6],[],[],[]]
Output: [6,3,4,1,5,2,0,7](https://leetcode.com/problems/sort-items-by-groups-respecting-dependencies/)
Approach — Topological Sorting
[10] Sequence Reconstruction — Check whether the original sequence org can be uniquely reconstructed from the sequences in seqs. The org sequence is a permutation of the integers from 1 to n, with 1 ≤ n ≤ 10^4.
Reconstruction means building a shortest common supersequence of the sequences in seqs (i.e., a shortest sequence so that all sequences in seqs are subsequences of it). Determine whether there is only one sequence that can be reconstructed from seqs and it is the org sequence.
Example 1:
Input:
org: [1,2,3], seqs: [[1,2],[1,3]]Output:
falseExplanation:
[1,2,3] is not the only one sequence that can be reconstructed, because [1,3,2] is also a valid sequence that can be reconstructed.
Example 2:
Input:
org: [1,2,3], seqs: [[1,2]]Output:
falseExplanation:
The reconstructed sequence can only be [1,2].
Example 3:
Input:
org: [1,2,3], seqs: [[1,2],[1,3],[2,3]]Output:
trueExplanation:
The sequences [1,2], [1,3], and [2,3] can uniquely reconstruct the original sequence [1,2,3].
Approach — To reconstruct sequence all consecutive 2-subsequences must be present. At minimum all consecutive 2-subsequences in ‘org’ must be present in the ‘seqs’. If not return False.
In [1,2,3,4], consecutive 2-subsequences are [1,2], [2,3] and [3,4]
Also if the ‘seqs’ contain additional subsequences then it should be a sub-sequence in ‘org’ too.
[11] Alien Dictionary — There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of non-empty words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.
Example:
Given the following words in dictionary,
[
"wrt",
"wrf",
"er",
"ett",
"rftt"
]The correct order is: "wertf".
Approach — Use Topological Sorting. Based on the sequence of words create dependencies between characters. For any 2 consecutive words, consider the earliest characters which differ in those two words.
