Coding Problems and Solutions-15
[1] Number of Ways to Wear Different Hats to Each Other — There are n people and 40 types of hats labeled from 1 to 40.
Given a list of list of integers hats, where hats[i] is a list of all hats preferred by the i-th person.
Return the number of ways that the n people wear different hats to each other.
Since the answer may be too large, return it modulo 10^9 + 7.
Example:
Input: hats = [[3,5,1],[3,5]]
Output: 4
Explanation: There are 4 ways to choose hats
(3,5), (5,3), (1,3) and (1,5)(https://leetcode.com/problems/number-of-ways-to-wear-different-hats-to-each-other/)
Approach — Use Bitmasking + Dynamic Programming.
f[k][h] — denotes the number of ways of assigning hats numbered 1 to h to the set of people represented by the integer ‘k’.
Thus if N=5, k=13 and h=8, then the binary representation for 13 = ‘01101’, denotes that hats 1 to 8 has been distributed to the 0-th, 3-rd and 4-th people.
f[k][h] can be computed by finding the people whose preferences has the h-th hat then using DP adding the number of ways f[k & ~(1<<i)][h-1] i.e. number of ways of assigning hats 1 to h-1 to all people except the i-th person.
[2] Longest Stick One Can Connect — You are given a bunch of sticks. For each stick, its two ends are labelled with two numbers (1-6, possibly same).
You can connect two stick A and B, if and only if one of numbers of stick A is the same as one of the numbers of stick B. For example, a stick with [1,5] can be connected with a stick with [1,4] by connecting the two ends labelled as 1. In this case, these two sticks will become one with longer length, and its two ends now becomes [4,5]. Assume for each given stick, its length is 1.
Example 1:
Input: [1, 2], [1, 3], [1, 4]
Output: 2
Explanation: You can choose any two of the given sticks, then connect them by
the ends labelled with 1. But there is no way to connect all 3 sticksExample 2:
Input: [1, 6], [3, 4], [5, 6], [4, 1]
Output: 4
Explanation: You can connect all four sticks in the following way:
[3, 4] <-> [4, 1] <-> [1, 6] <-> [6, 5]
Approach —Use Bitmasking + DP.
f[k][i][0] = max length stick formed with sticks represented by integer k ending with the i-th stick.
f[k][i][1] = number on the end-face of the final stick.
[3] Longest Increasing Subsequence — Given an unsorted array of integers, find the length of longest increasing subsequence.
Example:
Input: [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.(https://leetcode.com/problems/longest-increasing-subsequence/)
Approach — Maintain an array ‘f’ where f[h] is the minimum value of the last last integer of any subsequence of length h. Then at index ‘i’, do binary search over the minimum values in f to find the value which is ≤ arr[‘i’]. Let it be ‘j’
Thus maximum length of any subsequence ending with arr[‘i’] is j+1.
Update f[j+1]=min(f[j+1], arr[i]).
[4] Integer Distribution — You are given a list A of N integers (consider 1 — based indexing). Here, N is an even number. These integers must be distributed into N/2 pairs and the power of each of the pairs is added.
The power of a pair P(i, j) consisting of the i-th and j-th number is defined as bitwise XOR of the two numbers A[i] and A[j], that is A[i] ^ A[j] where 1 < i < N, 1 < j < N and i j.
Write a program to determine the minimum and the maximum possible sum of the N/2 pairs.
Example:
Input: [1,2,3,4]
Output: [6,10]
Explanation: Minimum occurs for (1 xor 4) + (2 xor 3) and Maximum occurs for (1 xor 2) + (3 xor 4)Approach — Use Bitmasking + DP
Each time pick 2 integers from the set bits, and using DP find the minimum of the remaining bits and add the XOR of the 2 integers. Note that we must only pick integers when the number of assigned bits is even.
[5] The maximum subarray — You are given an array of N elements. You are also given an integer K. You can select any subarray of the given array, delete that subarray from the array and join the remaining array elements. You can perform this operation at most once.
For example, if the array is [5, 7, 5, 4, 5, 8, 2] and you select [5, 4, 5] as the subarray that is deleted, then the resultant array becomes [5, 7, 8, 2].
You are required to find the length of the largest resultant array that contains an equal number of elements that are strictly greater and smaller than K.
Example:
Input: [5,7,2,8,7,4,5,9], K=5
Output: [5,7,2,4,5,9]
Explanation: Delete the sub-array [8,7]Approach — Create an array A with 1 if arr[i] > K, -1 if arr[‘i’] < K and 0 if arr[‘i’] = K. Then find the smallest subarray with sum equal to the sum of the new array A.
[6] Subsequence — Given an array A consisting of N distinct integers, and another array B consisting of M integers (not necessarily distinct). You need to find the minimum number of elements to be added in B so that A becomes sub-sequence of B, we can add elements at any position in array B.
A subsequence is a sequence that car be derived by deleting some or no elements from the sequence without changing the order of the remaining elements.
Example:
Input: A=[1,2,3,4,5], B=[2,5,6,4,9,12]
Output: 3
Explanation: Insert 1, 3 and 4 into B.(https://leetcode.com/discuss/interview-question/805619/Google-or-OA-2021-or-New-Grad-Role)
Approach — Create an array C with the indices of the elements of B in A. Then find the length of the longest increasing subsequence in C.
[7] Maximum Number of Coins You Can Get — There are 3n piles of coins of varying size, you and your friends will take piles of coins as follows:
- In each step, you will choose any 3 piles of coins (not necessarily consecutive).
- Of your choice, Alice will pick the pile with the maximum number of coins.
- You will pick the next pile with maximum number of coins.
- Your friend Bob will pick the last pile.
- Repeat until there are no more piles of coins.
Given an array of integers piles where piles[i] is the number of coins in the ithpile.
Return the maximum number of coins which you can have.
Example:
Input: piles = [2,4,1,2,7,8]
Output: 9
Explanation: Choose the triplet (2, 7, 8), Alice Pick the pile with 8 coins, you the pile with 7 coins and Bob the last one.
Choose the triplet (1, 2, 4), Alice Pick the pile with 4 coins, you the pile with 2 coins and Bob the last one.
The maximum number of coins which you can have are: 7 + 2 = 9.
On the other hand if we choose this arrangement (1, 2, 8), (2, 4, 7) you only get 2 + 4 = 6 coins which is not optimal.(https://leetcode.com/problems/maximum-number-of-coins-you-can-get/)
Approach — Sort the piles in decreasing order. Then in each turn, pick the 1st 2 piles from front and last pile from back. In this way you can guarantee than Bob will have least coins.
[8] Find Latest Group of Size M — Given an array arr that represents a permutation of numbers from 1 to n. You have a binary string of size n that initially has all its bits set to zero.
At each step i (assuming both the binary string and arr are 1-indexed) from 1 to n, the bit at position arr[i] is set to 1. You are given an integer m and you need to find the latest step at which there exists a group of ones of length m. A group of ones is a contiguous substring of 1s such that it cannot be extended in either direction.
Return the latest step at which there exists a group of ones of length exactly m. If no such group exists, return -1.
Example:
Input: arr = [3,5,1,2,4], m = 1
Output: 4
Explanation:
Step 1: "00100", groups: ["1"]
Step 2: "00101", groups: ["1", "1"]
Step 3: "10101", groups: ["1", "1", "1"]
Step 4: "11101", groups: ["111", "1"]
Step 5: "11111", groups: ["11111"]
The latest step at which there exists a group of size 1 is step 4.(https://leetcode.com/problems/find-latest-group-of-size-m/)
Approach — Track the starting and ending indices for each contiguous subarray of 1’s using 2 hash-maps. Update the hash maps with each insert. Also keep count of how many sub-array of 1’s have length m.
[9] Minimum Swaps to Arrange a Binary Grid — Given an n x n binary grid, in one step you can choose two adjacent rows of the grid and swap them.
A grid is said to be valid if all the cells above the main diagonal are zeros.
Return the minimum number of steps needed to make the grid valid, or -1 if the grid cannot be valid.
The main diagonal of a grid is the diagonal that starts at cell (1, 1) and ends at cell (n, n).
Example:
Input: grid = [[0,0,1],[1,1,0],[1,0,0]]
Output: 3(https://leetcode.com/problems/minimum-swaps-to-arrange-a-binary-grid/)
Approach — For each row, count the number of trailing zeros at the end. Then for each row ‘i’ starting from top, if count of trailing zeros is less than n-i-1, then find the next row below it with count at-least n-i-1 and then bring this row up by swapping. Repeat this for all rows starting from top.
[10] Maximum Length of Subarray With Positive Product — Given an array of integers nums, find the maximum length of a subarray where the product of all its elements is positive.
A subarray of an array is a consecutive sequence of zero or more values taken out of that array.
Return the maximum length of a subarray with positive product.
Example:
Input: nums = [0,1,-2,-3,-4]
Output: 3
Explanation: The longest subarray with positive product is [1,-2,-3] which has a product of 6.
Notice that we cannot include 0 in the subarray since that'll make the product 0 which is not positive.(https://leetcode.com/problems/maximum-length-of-subarray-with-positive-product/)
Approach — Count the number of negative integers till index i. Keep track of the first index where the count is even and the where the count is odd. At index i, if count is even then subtract the index of first even count else if it is odd then subtract the index of first odd count.
[11] Minimum Numbers of Function Calls to Make Target Array —
Your task is to form an integer array nums from an initial array of zeros arr that is the same size as nums.
Return the minimum number of function calls to make nums from arr.
The answer is guaranteed to fit in a 32-bit signed integer.
Example:
Input: nums = [1,5]
Output: 5
Explanation: Increment by 1 (second element): [0, 0] to get [0, 1] (1 operation).
Double all the elements: [0, 1] -> [0, 2] -> [0, 4] (2 operations).
Increment by 1 (both elements) [0, 4] -> [1, 4] -> [1, 5] (2 operations).
Total of operations: 1 + 2 + 2 = 5.(https://leetcode.com/problems/minimum-numbers-of-function-calls-to-make-target-array/)
Approach — First make all odd integers even by calling the function equal to the number of odd integers. Then call the function again to divide all integers by 2 (because now all integers are even). Repeat until final array is all zeros.
