Flipkart SDE - 2 PS/ DS Round

Round 1

Questions:

Question 1:

Maria is the event organizer of the Sarah Birthday party. Maria has planned a multilevel game for the kids. She has planned a level-1 game for kids that is to collect balls in the bucket given a certain time period. Each pair of kids who has collected the maximum number of balls will be eligible for the level-2 game.

Please help Maria to find out all the pairs of kids who have won level-1 games.

You are given an array arr of number of balls collected by kid i, find out the pairs of kids who have collected maximum number of balls.

Example:
Input : arr[] = {1, 2, 1, 2, 0, 2, 1}
Output : 3
Explanation: The maximum possible pair sum where i<j is 4, which is given by 3 pairs, so the answer is 3. The pairs are (2, 2), (2, 2), and (2, 2).

Input : arr[] = {1, 4, 3, 3, 5, 1}
Output : 1
Explanation: The pair 4, 5 yields the maximum sum i.e., 9 which is given by 1 pair only.

Question 2:

Given a sorted dictionary (array of words) of an alien language, find the order of characters in the language.

Examples:
Input: words[] = {“baa”, “abcd”, “abca”, “cab”, “cad”}
Output: Order of characters is ‘b’, ‘d’, ‘a’, ‘c’.
Explanation: Note that words are sorted and in the given language “baa” comes before “abcd”, therefore ‘b’ is before ‘a’ in output. Similarly, we can find other orders.

Input: words[] = {“caa”, “aaa”, “aab”}
Output: Order of characters is ‘c’, ‘a’, ‘b’.