Problem: Given N elements, in one operation you can merge adjacent elements (i.e. sum them up into one element), you have to do exactly K operations, what is the minimum possible obtainable value of the maximum of the resultant array.

Example
Elements: 1 2 3
K : 1
Output: 3 (by merging 1 and 2 we get 3, if we merged 2 and 3 we would get 5 which is > 3)

I can do this problem in O(N^2) complexity by Dynamic Programming, but can better time complexity be achieved?

Hello this is a Question asked in Clumio last year

I've been thinking about how to solve it, by connecting the friends to new nodes for interests but I can't seem to find a good way to find a group of friends which have maximum number of interest in common. Can anyone suggest a possible approach to this problem please?

This is yet another Interview question of Media.net. Trying to apply dp on this is hard and I can't solve it. I looked up solutions on stackoverflow and GeeksforGeeks but they are all wrong. Can anyone give a correct approach or an idea on how to solve it please?

Problem: Given a matrix N by M, The task is to find the area wise largest rectangular sub-matrix such that each column and each row of the submatrix is strictly increasing

Example:
{{1, 2, 3},
{4, 5, 6},
{1, 2, 3}}

Output: 6

Explanation: The largest sorted submatrix is
{{1, 2, 3},
{4, 5, 6}}

Here are some cases in which the given solutions on the above mentioned sites fail

Case 1

{{1, 4},
{2, 3}}
Correct output: 2

Case 2

{{1, 2, 3},
{0, 5, 6},
{1, 2, 3}}
Correct output: 4

Explanation: The largest sorted submatrix is

{{2, 3},
{5, 6}}

This is a question asked in Media.net interview, I have been thinking along the lines of Dijkstra but trying to be greedy in Dijkstra can end up giving no solutions, so I can't come up with a clear way of solving it

Problem: Given a graph in which each node represents a city. Some cities are connected to each other through bidirectional roads. The length of each road is also given. Some of the cities have hotels. Given a start city and a destination city and a value K which represents the maximum distance that can be travelled by a person in one day, find the minimum number of days in which the person can reach his destination (or tell if it is impossible for the given K). (Note : If the distance travelled in one day is exceeding K, the person can rest in the city which has a hotel in it, if there is no hotel in that city this implies you have to choose another path. Next day, the person can start from that city and the distance travelled get reset to 0).
(The last statement was confusing for me, perhaps it means something along if the intended distance exceeds K you have to reset your distance by resting in a city with hotel)

How would you go about solving this one?

Hello, this is a question asked to me in the JP Morgan Interview and I had no idea how to solve it, please tell me how you would have approached this problem or how would you go about solving it, because I couldn't find any pattern or how do I implement it

Question: Given a number, find the minimum number of steps you need to convert it to 0, you are allowed the following two operations

Operation 1: Change the last binary digit of the number
Example: 8 which in binary is (1000) you can convert the last 0 to 1 or vice versa so 1000 -> 1001

Operation 2: If at a position the binary digit is 1, and all binary digits to its right are 0 then you can change the binary digit to the left of that position
Example: in 1001 for the last binary digit it is 1, and there are no 1s to its right therefore we can change the binary digit to its left, as 1001 -> 1011

Constraints: 1 <= n <= 1e5

Example: for input 8 it will take 15 steps
1000 -> 1001 -> 1011 -> 1010 -> 1110 -> 1111 -> 1101 -> 1100 -> 0100 -> 0101 -> 0111 -> 0110 -> 0010 -> 0011 -> 0001 -> 0000

We had this question at our Internship test
Given a matrix 3 by 3 consisting of numbers from 1 to 9 (all numbers are present and randomly arranged)
Example
2 5 7
1 4 3
6 8 9

Convert this matrix into the below matrix

1 2 3
4 5 6
7 8 9

You are allowed to swap adjacent tiles (tiles that share a common side), but only on the condition that sum of the numbers on the tiles should be prime
For example: In above example you can swap tile with 2 and tile with 5 with each other, but tile with 6 and tile with 8 can't be swapped with each other
Find the minimum number of steps needed to get to the desired state

I was thinking of something along the lines of Backtracking but couldn't come up with a correct solution, how would you approach it?

We had this question on our Internship test, and I couldn't figure out how to do it, help please

Given a string s and a number p find number of unique special strings that can be formed using the given string
A special string is a permutation of string made from a subsequence of s, whose sum of ASCII values of its characters is divisible by p
Example: s = "ab", p = "2"
answer = 1
all possible unique strings = "a","b","ab", "ba"
respective sums = 97, 98, 195, 195
reason: since there is only one number (98) which is divisible by 2 so total answer = 1
Constraints: |s| <= 20 and 1 <= p <= 200
print the answer modulo 1000000007

So we had an Interview Question at Codenation, This is the question Question Image. I understand that we can do the update node and sum of values through segment trees but what I can't understand is how to find the aith beautiful number, can someone help me out please! Also the constraints of X in the question are below 10^5