Software Developer

You are given an array/list ‘arr’ of size ‘n’. Your task is to find the maximum product possible by taking any subset of the array/list ‘arr’.

Since the product can be large, return it modulo 10^9+7

For example:

Let arr=[-1,-1,-2,4,3] 

We can take the subset {-1,-2,4,3} which will have the product as 24. We can verify that this is the largest product possible. Hence we return 24.

You have been given a matrix of ‘N’ rows and ‘M’ columns filled up with integers. Find the minimum sum that can be obtained from a path which from cell (x,y) and ends at the top left corner (1,1).

From any cell in a row, we can move to the right, down or the down right diagonal cell. So from a particular cell (row, col), we can move to the following three cells:

Down: (row+1,col)
Right: (row, col+1)
Down right diagonal: (row+1, col+1)

You have been given a Binary Tree of integers. You are supposed to return the reverse of the level order traversal.

For example:

For the given binary tree

The reverse level order traversal will be {7,6,5,4,3,2,1}.

You are given two strings S and X containing random characters. Your task is to find the smallest substring in S which contains all the characters present in X.

Example:

Let S = “abdd” and X = “bd”.

The windows in S which contain all the characters in X are: 'abdd', 'abd', 'bdd', 'bd'. 
Out of these, the smallest substring in S which contains all the characters present in X is 'bd'. 
All the other substring have a length larger than 'bd'.

You have been given a Binary Tree having 'n' nodes.

A Symmetric tree is a binary tree whose mirror image is the same as the original tree.

Find out whether the given tree is symmetric or not.

Example :

Input: Let the binary tree be:

Output: YES

Explanation: As we can see in the image, the original tree is the same as the mirrored tree.

Ninja has enrolled in a system design course at Coding Ninjas, and his first assignment is to create a search autocomplete system for a search engine.

Ninja is given ‘N’ sentences ‘SENTENCES’ and ‘N’ integers ‘TIMES’, where ‘TIMES’[i] is the number of times the ‘SENTENCES’[i] was typed. Now, the instructor will input a test sentence(at least one word and end with ‘#’). As Ninja’s best friend, can you help him with the assignment?

Your task is to implement the AutocompleteSystemclass:

• AutocompleteSystem(String[] sentences, int[] times)Initializes the object with the sentences and times arrays.
• List input(char c)This indicates that the user typed the character c.
  • Returns an empty array [], if c == '#' and stores the inputted sentence in the system.
  • Returns the top 3 historical hot sentences with the same prefix as the sentence already typed. If there are fewer than 3matches, return them all.

Here are the specific rules:

• A sentence’s hot degree is defined as the number of times a user typed the same sentence before.
• The returned top 3 hot sentences should be sorted by hot degree (The first is the hottest one). If several sentences have the same hot degree, use ASCII-code order (smaller one appears first).
• If less than three hot sentences exist, return as many as possible.
• When the input is a special character, it means the sentence ends, and in this case, you need to return an empty list.

For Example:

Input:
["AutocompleteSystem","input","input","input"]
[[["i want to join faang","icecream","i love coding ninjas"],[4,3,1],["i"],["s"],["#"]]

Output:
[null,["i want to join faang","icecream","i love coding ninjas"],[],[]]

Explanation:
* AutocompleteSystem obj = new AutocompleteSystem(["i want to join faang","icecream","i love coding ninjas"],[4,3,1]); 
* obj.input(“i”); // return ["i want to join faang","icecream","i love coding ninjas"]. There are three sentences that have prefix "I".
* obj.input(“s”); // return []. There is no sentence with prefix “is”
* obj.input(“#”); // return [].