SDE - 1

Reverse the given string word-wise. The last word in the given string should come at 1st place, the last-second word at 2nd place, and so on. Individual words should remain as it is.

Given an array/list of length ‘N’, you are supposed to return the majority element of the array/list.

The majority element is the element that appears more than floor(N/2) times in the given array/list.

Note:

You may assume that the given array/list is non-empty and the majority element always exists in the array.

You have been given 'N' ropes of different lengths, we need to connect these ropes into one rope. The cost to connect two ropes is equal to sum of their lengths. We need to connect the ropes with minimum cost.

The test-data is such that the result will fit into a 32-bit integer.

You are given a 2-dimensional array/list having N rows and M columns, which is filled with ones(1) and zeroes(0). 1 signifies land, and 0 signifies water.

A cell is said to be connected to another cell, if one cell lies immediately next to the other cell, in any of the eight directions (two vertical, two horizontal, and four diagonals).

A group of connected cells having value 1 is called an island. Your task is to find the number of such islands present in the matrix.

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 [].

You are given D dice, each having F faces numbered 1 to F, both inclusive. The task is to find the possible number of ways to roll the dice together such that the sum of face-up numbers equal the given target S.

Note :

As the answer can be large, return your answer modulo 10^9  + 7.

Follow Up :

Can you solve this using not more than O(S) extra space?