1.
Given a square matrix mat[][], turn it by 90 degrees in an clockwise direction without using
any extra space
Input: mat[][] = {{1, 2, 3},
{4, 5, 6},
{7, 8, 9}}
Output: {{7, 4, 1},
{8, 5, 2},
{9, 6, 3}}
Input: mat[][] = {{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11,12}
{13, 14, 15, 16}}
Output: {{13, 9, 5, 1},
{14, 10, 6, 2},
{15, 11, 7, 3},
{16, 12, 8, 4}
2. Write a function “runCustomerSimulation” that takes following two inputs
1. An integer ‘n’: total number of computers in a cafe and a string:
2. A sequence of uppercase letters ‘seq’: Letters in the sequence occur in pairs. The first
occurrence indicates the arrival of a customer; the second indicates the departure of
that same customer.
A customer will be serviced if there is an unoccupied computer. No letter will occur more than two
times.
Customers who leave without using a computer always depart before customers who are currently
using the computers. There are at most 20 computers per cafe.
For each set of input the function should output a number telling how many customers, if any walked
away without using a computer. Return 0 if all the customers were able to use a computer.
runCustomerSimulation (2, “ABBAJJKZKZ”) should return 0
runCustomerSimulation (3, “GACCBDDBAGEE”) should return 1 as ‘D’ was not able to get any
computer
runCustomerSimulation (3, “GACCBGDDBAEE”) should return 0
runCustomerSimulation (1, “ABCBCA”) should return 2 as ‘B’ and ‘C’ were not able to get any
computer.
runCustomerSimulation(1, “ABCBCADEED”) should return 3 as ‘B’, ‘C’ and ‘E’ were not able to get any
computer.
Below are simple steps to find number of customers who could not get any computer.
1. Initialize result as 0.
2. Traverse the given sequence. While traversing, keep track of occupied computers (this can be
done by keeping track of characters which have appeared only once and a computer was
available when they appeared). At any point, if count of occupied computers is equal to ‘n’,
and there is a new customer, increment result by 1.
The important thing is to keep track of existing customers in cafe in a way that can indicate whether
the customer has got a computer or not. Note that in sequence “ABCBCADEED”, customer ‘B’ did not
get a seat, but still in cafe as a new customer ‘C’ is next in sequence.
3. Given an array, arr[] construct a product array, res[] where each element in res[i] is the
product of all elements in arr[] except arr[i]. Return this resultant array, res[].
Note: Each element is res[] lies inside the 32-bit integer range.
Input: arr[] = [10, 3, 5, 6, 2]
Output: [180, 600, 360, 300, 900]
Explanation: For i=0, res[i] = 3 * 5 * 6 * 2 is 180.
For i = 1, res[i] = 10 * 5 * 6 * 2 is 600.
For i = 2, res[i] = 10 * 3 * 6 * 2 is 360.
For i = 3, res[i] = 10 * 3 * 5 * 2 is 300.
For i = 4, res[i] = 10 * 3 * 5 * 6 is 900.
Input: arr[] = [12, 0]
Output: [0, 12]
Explanation: For i = 0, res[i] is 0.
For i = 1, res[i] is 12.
Constraints:
2 <= arr.size() <= 105
-100 <= arr[i] <= 100
4. Maximum Value in Knapsack
You are given N items, each with a weight and a value, and a knapsack that can carry a maximum
weight of W. Your task is to determine the maximum total value that can be obtained by
selecting a subset of these items, ensuring that the total weight does not exceed W.
Each item can either be included or excluded (0/1 Knapsack).
Input: N = 3, W = 50
weights = [10, 20, 30]
values = [60, 100, 120]
Output: 220
Explanation: Pick items with weights 20 and 30 (100 + 120 = 220).
Input: N = 2, W = 5
weights = [4, 5]
values = [1, 2]
Output: 2
Explanation: Pick the second item (value 2).
Constraints:
● 1 ≤ N ≤ 1000
● 1 ≤ W ≤ 10^4
● 1 ≤ weights[i] ≤ 10^4
● 1 ≤ values[i] ≤ 10^4
5. Minimum Cost of Encoding
You are given a list of N different characters, each with a corresponding frequency of occurrence.
Your task is to determine the minimum cost required to encode all the characters using Huffman
Coding.
The cost of encoding is calculated as the sum of all merge operations where two lowest-
frequency nodes are combined in a binary tree. The cost of merging two nodes is equal to the
sum of their frequencies.
Input: N = 5
characters = ['a', 'b', 'c', 'd', 'e']
frequencies = [10, 20, 30, 40, 50]
Output: 190
Explanation: The minimum cost of merging operations is 190.
Input: N = 4
characters = ['x', 'y', 'z', 'w']
frequencies = [5, 7, 12, 20]
Output: 44
Constraints:
● 1 ≤ N ≤ 10^5
● 1 ≤ frequencies[i] ≤ 10^6
● The sum of all frequencies will not exceed 10^9.
6. You are given a list of N different characters, each with a corresponding frequency of
occurrence. You need to construct a binary prefix encoding using Huffman Coding and return the
sum of all encoded string lengths multiplied by their respective frequencies. Each character’s
encoded length is determined by its depth in the Huffman tree (i.e., the number of bits used in
its encoding). Your task is to return the weighted sum of all encoded string lengths.
Input:
N=4
characters = ['a', 'b', 'c', 'd']
frequencies = [5, 7, 10, 20]
Output: 82
Input:
N=3
characters = ['x', 'y', 'z']
frequencies = [4, 8, 12]
Output: 44
Constraints:
● 1 ≤ N ≤ 10^5
● 1 ≤ frequencies[i] ≤ 10^6
● The sum of all frequencies will not exceed 10^9.
● The characters are distinct.
