Coding Problems and Solutions-4

[1] Given an int array wood representing the length of n pieces of wood and an int k. It is required to cut these pieces of wood such that more or equal to k pieces of the same length len are cut. What is the longest len you can get?

Example:

Input: wood = [232, 124, 456], k = 7
Output: 114
Explanation: We can cut it into 7 pieces if any piece is 114 long, however we can't cut it into 7 pieces if any piece is 115 long.

(https://leetcode.com/discuss/interview-question/354854/)

Approach — Use binary search

[2] Shortest Distance To Character — Given a string S and a character C, return an array of integers representing the shortest distance from the character C in the string.

Example:

Input: S = "loveleetcode", C = 'e'
Output: [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]

(https://leetcode.com/problems/shortest-distance-to-a-character/)

[3] Task Scheduler — Given a char array representing tasks CPU need to do. It contains capital letters A to Z where different letters represent different tasks. Tasks could be done without original order. Each task could be done in one interval. For each interval, CPU could finish one task or just be idle.

However, there is a non-negative cooling interval n that means between two same tasks, there must be at least n intervals that CPU are doing different tasks or just be idle.

You need to return the least number of intervals the CPU will take to finish all the given tasks.

Example:

Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation: A -> B -> idle -> A -> B -> idle -> A -> B.

(https://leetcode.com/problems/task-scheduler/)

Approach — For time slot i, consider the task with the highest remaining count. If the highest remaining count task has been taken within the last n slots, then place the task into the slot n+1 distance away from the last slot for the same task and continue with the current slot.

[4] Pancake Sorting — Given an array A, we can perform a pancake flip: We choose some positive integer k ≤ A.length then reverse the order of the first k elements of A. We want to perform zero or more pancake flips (doing them one after another in succession) to sort the array A.

Array A is permutation of 1 to N.

(https://leetcode.com/problems/pancake-sorting/)

Approach — Start by placing N in its correct position i.e. end of array. Followed by N-1, N-2 and so on.

[5] Design a data structure that supports all following operations in average O(1) time.

1. insert(val) : Inserts an item val to the collection.
2. remove(val) : Removes an item val from the collection if present.
3. getRandom() : Returns a random element from current collection of elements. The probability of each element being returned is linearly related to the number of same value the collection contains.

(https://leetcode.com/problems/insert-delete-getrandom-o1-duplicates-allowed/)

Approach — Use doubly linked list for insert and removal. For getRandom, use an array to append nodes.

Whenever a node from middle of list is removed replace it with the node at the tail of the list.

Generate random number between 0 and length of list-1 and fetch the node corresponding to the random number in the node array.

[6] Minimum remove to make valid parenthesis — Given a string s of ‘(‘ and ‘)’ and lowercase English characters.

Your task is to remove the minimum number of parentheses, in any positions so that the resulting parentheses string is valid and return any valid string.

Formally, a parentheses string is valid if and only if:

• It is the empty string, contains only lowercase characters, or
• It can be written as AB (A concatenated with B), where A and B are valid strings, or
• It can be written as (A), where A is a valid string.

Example:

Input: s = "lee(t(c)o)de)"
Output: "lee(t(c)o)de"
Explanation: "lee(t(co)de)" , "lee(t(c)ode)" would also be accepted.

(https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses/)

Approach — During forward iteration remove a right parenthesis whenever the number of right parenthesis exceeds the number of left parenthesis.

Similarly during backward iteration, remove a left parenthesis whenever the number of left parenthesis exceeds the number of right parenthesis.

[7] Add and Search Word — Design a data structure that supports the following two operations:

void addWord(word)
bool search(word)

search(word) can search a literal word or a regular expression string containing only letters a-z or ‘.’. A ‘.’ means it can represent any one letter.

Example:

addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true

(https://leetcode.com/problems/add-and-search-word-data-structure-design/)

Approach — Use compressed Trie (Radix Tree)

[8] Minimum number of refueling stops — A car travels from a starting position to a destination which is ‘target’ miles east of the starting position.

Along the way, there are gas stations. Each stations[i] represents a gas station that is stations[i][0] miles east of the starting position, and has stations[i][1] liters of gas.

The car starts with an infinite tank of gas, which initially has startFuel liters of fuel in it. It uses 1 liter of gas per 1 mile that it drives.

When the car reaches a gas station, it may stop and refuel, transferring all the gas from the station into the car.

What is the least number of refueling stops the car must make in order to reach its destination? If it cannot reach the destination, return -1.

Note that if the car reaches a gas station with 0 fuel left, the car can still refuel there. If the car reaches the destination with 0 fuel left, it is still considered to have arrived.

Example:

Input: target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]
Output: 2
Explanation: 
We start with 10 liters of fuel.
We drive to position 10, expending 10 liters of fuel.  We refuel from 0 liters to 60 liters of gas.
Then, we drive from position 10 to position 60 (expending 50 liters of fuel),
and refuel from 10 liters to 50 liters of gas.  We then drive to and reach the target.
We made 2 refueling stops along the way, so we return 2.

(https://leetcode.com/problems/minimum-number-of-refueling-stops/)

Approach — Use dynamic programming to compute f[k][i] i.e. the maximum amount of fuel present after k stops at the i-th station.

f[k][i] = max(f[k-1][0] — (stations[i][0]-stations[0][0]), f[k-1][1] — (stations[i][0]-stations[1][0]), f[k-1][2] — (stations[i][0]-stations[2][0]), …) + stations[i][1]

[9] Stuck Key — Given a dictionary of valid words, write a function that accepts a string to determine if the string has a typo that is strictly caused by a stuck key.

Example:

Input:
Dictionary: { hello, cat, world, dog, bird, grass, green, help, greet, great }
String: bbbirrrdddd
Output: True
Explanation: The character's 'b', 'r', & 'd' all repeat. Assuming their keys got stuck, we can form the word 'bird', which exists in the dictionary.

Example:

Input:
Dictionary: { hello, cat, world, dog, bird, grass, green, help, greet, great }
String: gggraasssa
Output: False
Explanation: The a at the end is not the result of a stuck key, and thus it is impossible for it to exist in the dictionary.

(https://leetcode.com/discuss/interview-question/679321/Google-or-Onsite-or-Determine-if-word-is-typo-because-of-stuck-key)

Using Trie based approach.

[10] Meeting Rooms — Given a list of meetings for a given day in a conference center, return a list of time slots during which the most number of concurrent meetings are held.
Each meeting has a start time and end time and occupies a single room in a
conference center.

Input:
(100,300) // meeting 1, 1:00 am to 3:00 am
(145,215) // meeting 2
(200,230) // meeting 3
(215,300) // meeting 4
(215,400) // meeting 5
(500,600) // meeting 6
(600,700) // meeting 7

Output:
(215,230) // 4 concurrent meetings: 1,3,4,5

(https://leetcode.com/discuss/interview-question/679396/Bloomberg-or-Onsite-or-Concurrent-Meetings)

Approach — Sort by end times and use min-heap to maintain the current smallest end time. For each meeting check if start time exceeds or equals minimum end time of running meetings. If it is then remove that meeting from heap and add this new meeting else simply add the new meeting.

For maximum concurrent meetings, for each start time if it is less than the current minimum times of all running meetings then the interval [start_time, minimum_running_time] occurs in all meetings currently running i.e. length of heap.

[11] Accounts Merge — Given a list accounts, each element accounts[i] is a list of strings, where the first element accounts[i][0] is a name, and the rest of the elements are emails representing emails of the account.

Now, we would like to merge these accounts. Two accounts definitely belong to the same person if there is some email that is common to both accounts. Note that even if two accounts have the same name, they may belong to different people as people could have the same name. A person can have any number of accounts initially, but all of their accounts definitely have the same name.

After merging the accounts, return the accounts in the following format: the first element of each account is the name, and the rest of the elements are emails in sorted order. The accounts themselves can be returned in any order.

Example:

Input: 
accounts = [["John", "johnsmith@mail.com", "john00@mail.com"], ["John", "johnnybravo@mail.com"], ["John", "johnsmith@mail.com", "john_newyork@mail.com"], ["Mary", "mary@mail.com"]]
Output: [["John", 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com'],  ["John", "johnnybravo@mail.com"], ["Mary", "mary@mail.com"]]

(https://leetcode.com/problems/accounts-merge/)

Approach — Use union find.