Product Engineer

You are given an array ‘ARR’ of size ‘N’ and an integer ‘M’. You have to split the array into ‘M’ non-overlapping, non-empty subarrays such that the maximum of all the subarray’s sum is the minimum possible. Your task is to return the minimum of the maximum of all the subarray’s sum.

For example:

You are given ‘ARR’ = [7, 2, 6, 10, 8] and ‘M’ = 2. We split the array as [ 7, 2, 6] and [10, 8], the maximum of 7 + 2 + 6  and 10 + 8 is 18, which is the minimum possible.

You are given an array 'A' of length 'N' consisting only of integers. You are also given three integers 'X', 'Y' and 'SUM'. Count the number of pairs ('i', 'j') where 'i' < 'j' such that ('A[i]' * 'X' + 'A[j]' * 'Y') = 'SUM'.

Example :

'N' = 3, 'A' = {3, 1, 2, 3}, 'X' = 4, 'Y'= 2, 'SUM' = 14

For 'i' = 1, 'j' = 2, Value of the expression = 4 * 3 + 2 * 1 = 14.
For 'i' = 1, 'j' = 3, Value of the expression = 4 * 3 + 2 * 2 = 16.
For 'i' = 1, 'j' = 4, Value of the expression = 4 * 3 + 2 * 3 = 18.
For 'i' = 2, 'j' = 3, Value of the expression = 4 * 1 + 2 * 2 = 8.
For 'i' = 2, 'j' = 4, Value of the expression = 4 * 1 + 2 * 3 = 10.
For 'i' = 3, 'j' = 4, Value of the expression = 4 * 2 + 2 * 3 = 14.

The possible pairs are :
(1, 3), (3,4)

Ninja developed a love for arrays and strings so this time his teacher gave him an array of strings, ‘A’ of size ‘N’. Each element of this array is a string. The teacher taught Ninja about prefixes in the past, so he wants to test his knowledge.

A string is called a complete string if every prefix of this string is also present in the array ‘A’. Ninja is challenged to find the longest complete string in the array ‘A’.If there are multiple strings with the same length, return the lexicographically smallest one and if no string exists, return "None".

Note :

String ‘P’ is lexicographically smaller than string ‘Q’, if : 

1. There exists some index ‘i’ such that for all ‘j’ < ‘i’ , ‘P[j] = Q[j]’ and ‘P[i] < Q[i]’. E.g. “ninja” < “noder”.

2. If ‘P’ is a prefix of string ‘Q’, e.g. “code” < “coder”.

Example :

N = 4
A = [ “ab” , “abc” , “a” , “bp” ] 

Explanation : 

Only prefix of the string “a” is “a” which is present in array ‘A’. So, it is one of the possible strings.

Prefixes of the string “ab” are “a” and “ab” both of which are present in array ‘A’. So, it is one of the possible strings.

Prefixes of the string “bp” are “b” and “bp”. “b” is not present in array ‘A’. So, it cannot be a valid string.

Prefixes of the string “abc” are “a”,“ab” and “abc” all of which are present in array ‘A’. So, it is one of the possible strings.

We need to find the maximum length string, so “abc” is the required string.

You have been given a grid containing some oranges. Each cell of this grid has one of the three integers values:

Value 0 - representing an empty cell.

Value 1 - representing a fresh orange.

Value 2 - representing a rotten orange.

Every second, any fresh orange that is adjacent(4-directionally) to a rotten orange becomes rotten.

Your task is to find out the minimum time after which no cell has a fresh orange. If it's impossible to rot all the fresh oranges then print -1.

Note:

1. The grid has 0-based indexing.
2. A rotten orange can affect the adjacent oranges 4 directionally i.e. Up, Down, Left, Right.

A Directed Acyclic Graph (DAG) is a directed graph that contains no cycles.

Topological Sorting of DAG is a linear ordering of vertices such that for every directed edge from vertex ‘u’ to vertex ‘v’, vertex ‘u’ comes before ‘v’ in the ordering. Topological Sorting for a graph is not possible if the graph is not a DAG.

Given a DAG consisting of ‘V’ vertices and ‘E’ edges, you need to find out any topological sorting of this DAG. Return an array of size ‘V’ representing the topological sort of the vertices of the given DAG.

For example, Consider the DAG shown in the picture.

In this graph, there are directed edges from 0 to 1 and 0 to 3, so 0 should come before 1 and 3. Also, there are directed edges from 1 to 2 and 3 to 2 so 1 and 3 should come before 2.

So, The topological sorting of this DAG is {0 1 3 2}.

Note that there are multiple topological sortings possible for a DAG. For the graph given above one another topological sorting is: {0, 3, 1, 2}

Note:

1. It is guaranteed that the given graph is DAG.
2. There will be no multiple edges and self-loops in the given DAG.
3. There can be multiple correct solutions, you can find any one of them. 
4. Don’t print anything, just return an array representing the topological sort of the vertices of the given DAG.

You are given an array containing ‘N’ integers. You need to find if it’s possible to convert the given sequence into an Arithmetic Progression by rearranging the array elements, print “true” if it is possible, else print “false”.

For Example :

If ‘N’ = 5, ‘ARR’ = {2, 4, 10, 8, 6}

You can rearrange ‘ARR’ to now become {2, 4, 6, 8, 10} this is an arithmetic progression. Therefore we will print “true”.

You have been given a Binary Search Tree and a target value. You need to find out whether there exists a pair of node values in the BST, such that their sum is equal to the target value.

A binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree whose internal nodes each store a value greater than all the values keys in the node's left subtree and less than those in its right subtree.

Follow Up:

Can you solve this in O(N) time, and O(H) space complexity?

Design the Database Schema of Spotify

You are given an integer ‘N’ and an array ‘A’ of size ‘N’ containing positive integers.

You have ‘N’ friends, and you want to give each of them some candies. The ‘ith’ friend will be happy if they receive at least ‘A[i]’ candies. You want to distribute candies among your friends to fulfill the following two conditions.

No two friends have the same number of candies.

Every friend is happy.

Your task is to find the minimum candies required for distributing such that both conditions are met. If no distribution fulfills both given conditions, report it.

Example :

‘N’ = 5, ‘A’ = [3, 3, 2, 5, 1]
If we distribute candies in the following manner [4, 3, 2, 5, 1],
Each friend will be happy as they have at least received ‘A[i]’ candies, and no two friends got the same number of candies.
Hence, the answer is (4 + 3 + 2 + 5 + 1) = 15. It’s guaranteed that this is the minimum number of candies required.

Introduce Yourself.

Describe some situations from your life where you learned something or faced a problem or overcame some difficulty