Coding Problems and Solutions-3

[1] Find the length of the longest substring with k unique characters in a given string.

Example:

"aabbcc", k = 3
There are substrings with exactly 3 unique characters
{"aabbcc" , "abbcc" , "aabbc" , "abbc" }
Max is "aabbcc" with length 6.

[2] All O(1) Data Structure — Implement a data structure supporting the following operations:

1. Inc(Key) — Inserts a new key with value 1. Or increments an existing key by 1. Key is guaranteed to be a non-empty string.
2. Dec(Key) — If Key’s value is 1, remove it from the data structure. Otherwise decrements an existing key by 1. If the key does not exist, this function does nothing. Key is guaranteed to be a non-empty string.
3. GetMaxKey() — Returns one of the keys with maximal value. If no element exists, return an empty string.
4. GetMinKey() — Returns one of the keys with minimal value. If no element exists, return an empty string.

Challenge: Perform all these in O(1) time complexity.

(https://leetcode.com/problems/all-oone-data-structure/)

Approach — Use Doubly Linked List and HashMap.

Maintain a sorted doubly linked list.

Use ‘node_map’ to map key to node pointers and ‘val_node_map’ to map a value to the first and the last node corresponding to the value in the sorted doubly linked list.

[3] Street Fighter — Create an API, which will have two functions :

register — which takes sequence of keys and register a special move, like in a street fighter game UDLR(up, down, left, right) can be registered to special move “Fireball”.

emit — takes a single key and returns the list of registered sequence(s) that were completed by key press

register(“UDLR”, “Fireball”);
register(“DLRU”, “Punch”);
register(“LR”, “Kick”);

emit(“U”);
emit(“D”);
emit(“L”);
emit(“R”); — returns a list containing {“Fireball” and “kick”}
emit(“U”); — return a {“Punch”}
emit(“U”);
emit(“U”);

(https://leetcode.com/discuss/interview-question/672160/Google-or-Phone-or-Street-Fighter)

(https://leetcode.com/problems/stream-of-characters/)

Approach — Use Trie to register the keystrokes and the moves. Store the move associated with a sequence at the leaf node of each keystroke sequence.

For each emit maintain states for the current nodes in the Trie.

Then for each emit, check all possible nodes from the last emit which can be reached and update the current nodes. If current node is a leaf then return the move associated with it.

[4] Serialize and Desialize Binary Tree — Assuming only positive and negative integers serialize into a single integer array with no null values.

(https://leetcode.com/problems/serialize-and-deserialize-binary-tree/)

Approach — Serialize as follows:

[root.val] + [len(left_serialized_array)] + left_serialized_array + [len(right_serialized_array)] + right_serialized_array

Deserialize recursively.

[5] Reorganize String — Given a string S, check if the letters can be rearranged so that two characters that are adjacent to each other are not the same.

If possible, output any possible result. If not possible, return the empty string.

Example:

Input: S = "aab"
Output: "aba"

(https://leetcode.com/problems/reorganize-string/)

Approach — Use greedy approach to take the character with highest occurrence.

If the character with highest occurrence is same as last character then take the character with 2nd highest occurrence.

Use priority queue.

[6] Tallest Possible Building — City makes a plan for buildings and parking lots on land. The land can be divided into equal sized tiles. Each tile is either a building or parking lot. The height difference between building/parking lots on two adjacent tiles is no more than one. The locations of parking lots on the land are fixed. Write a function to find what is the highest building can be planned. [Adjacency only includes left, right, up and down. Specifically diagonal is not considered — two tiles share an edge to be considered as adjacent]

Example 1
Input

- - -
- - -
- - P

Output: 4 with following arrangement

4 3 2
3 2 1
2 1 P

Example 2
Input

- - P
- - -
- - P

Output: 3 with following arrangement

2 1 P
3 2 1
2 1 P

(https://leetcode.com/discuss/interview-question/672508/Google-L5-or-Onsite-or-Tallest-possible-building)

Approach — Do BFS from each Parking slot and update the current height of the building at slot (i, j).

current_height[i][j] = min(current_height[i][j], height_discovered_from_BFS)

[7] There are numerous houses in the line,numbered from 0, which user can visit. Each house its own amount of energy supply and coins supply. User starts the journey at house 0.

At each house visited, user either takes the entire energy form this house (for increasing own energy) or takes all coins from this house travelling from the house with number i to a house with number i+1 costs 1 energy unit and its not possible to skip any house in between which means that before visiting the house with number i, user has to visit house 0,1,2,…, i-1 first.

User can end the journey at any house, since it is not required to visit all the houses.

Assuming that there are n houses in a line, the ith house has house_energy[i] energy and house_coins[i] coins, and user start the energy with initial_energy energy, what’s the maximum number of coins user can collect maintaining the condition can collect maintain the condition of always having non-negative energy ?

Approach — Use DP.

max_coins(i, energy) = maximum coins collected till i-th house and having ‘energy’ left

max_coins(i, energy) = max(coins[i] + max_coins(i+1, energy-1), max_coins(i+1, energy+energies[i]-1))

n houses
initial_energy = 1
house_energy[]= {1,5,3,3,1}
house_coins[] = {3,23,9,2,2}
Constraints
1 <= n <= 1000
0 <= initial_energy <= 10^14
0 <= house_energy <= 10^3
0 <= house_coins <= 10^3
There are 5 houses with energies as 1, 5, 3, 3, 1 respectively and coins as 3, 23, 9, 2, 2 respectively and initial energy as 1. 
The best way to gain maximum coins is to get energy from the first house i.e. 1 and coins from the second and third house that is 23 + 9.
Cannot go any further, since 2 energy was used. The maximum number of coins collected is 32 coins

[8] Add Strings — Given two non-negative integers num1 and num2 represented as string, return the sum of num1 and num2.

(https://leetcode.com/problems/add-strings/)

[9] Insert Interval — Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

(https://leetcode.com/problems/insert-interval/)

Approach — Use binary search to find the left-most and right-most interval that should overlap with the given interval. Then merge all intervals in between.

[10] Reconstruct Itinerary — Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.

Note:

1. If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary [‘JFK’, ‘LGA’] has a smaller lexical order than [‘JFK’, ‘LGB’].
2. All airports are represented by three capital letters (IATA code).
3. You may assume all tickets form at least one valid itinerary.

Example:

Input: [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Output: ["JFK","ATL","JFK","SFO","ATL","SFO"]
Explanation: Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"].
             But it is larger in lexical order.

(https://leetcode.com/problems/reconstruct-itinerary/)

Approach — For each starting airport sort the tickets based on the ending airport and then do DFS starting from each ‘JFK’ ticket.

[11] Queue Reconstruction By Height — Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h.

Write an algorithm to reconstruct the queue.

Example:

Input:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
Output:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

(https://leetcode.com/problems/queue-reconstruction-by-height/)

Approach — Sort the people by their heights in increasing order. For people with same height place the person having lesser number of people with height greater than equal to before.

Then starting from the end place the person at the queue index corresponding to the number of persons of height greater than or equal to

i.e. if a person with height H has n people with height greater than or equal to H, then place the person at index n+1.