(This question has been seen in the interviews of the following companies: Tiktok)

Tiktok Online Assessment Questions 2023

Multi Dimensional Selection

Given a 2-d array arr of size n x m, a selection is defined as an array of integers such that it contains at least [m/2] integers from each row of arr. The cost of the selection is defined as the maximum difference between any two integers of the selection.

Suppose k is the minimum cost of all the possible selections for the given 2-d array. Find the maximum value of the product of k * the number of integers considered in the selection with the minimum cost.

**Example**

Suppose n= 3, m = 2, and arr = [[1, 2], [3, 4], [8, 9]]

Some of the possible selections are [2, 3, 8], [1, 2, 3, 9], [1, 3, 4, 8, 9] etc. The cost of these selections are 8 - 2 = 6, 9 - 1 = 8, and 8 respectively.

Here the minimum cost of all the possible selections is 6. The possible selections with the cost 6 are [2, 4, 8] and [2, 3, 4, 8]. The maximum value of the required product is obtained using the latter selection i.e. 6 * 4 = 24. Hence the answer is 24.

**Function Description**

Complete the function getMaxProduct in the editor below.

getMaxProduct has the following parameter:

int arr[n][m]: the given 2-d array

Returns

int: the maximum possible product

**Constraints**

1 <= n <= 10^3

2 <= m <= 10^3

1 <= arr[i][j] <= 10^9

#### Get one-to-one training from Google Facebook engineers

##### Top-notch Professionals

Learn from Facebook and Google senior engineers interviewed 100+ candidates.

Most recent interview questions and system design topics gathered from aonecode alumnus.

One-to-one online classes. Get feedbacks from real interviewers.

##### Customized Private Class

Already a coding expert? - Advance straight to hard interview topics of your interest.

New to the ground? - Develop basic coding skills with your own designated mentor.

Days before interview? - Focus on most important problems in target company question bank.