SDE - Intern

You are given an array/list of words, your task is to check whether the individual words can be rearranged to form a circle.

Two words, ‘X’ and ‘Y’, can be put together in a circle if the last character of ‘X’ is the same as the first character of ‘Y’ or vice versa.

For Example:

For the array [ “TUNA”, “TIGER”, “RABBIT”, “RAT”, “ANTEATER” ],

A possible circle can be:

After years of research, Ninja is finally able to invent the time machine, and now he is back to the good old days when T9 keypads were being used in mobile phones.

Being a curious person, Ninja wants to find out all possible strings that can be formed by pressing the keys of the phone.

Formally, you are given a string S, that consists of digits from 2-9 (both inclusive), your task is to find out all the possible strings that can be formed from the input string by mapping the digits to the letters as in a T9 keypad. Then, print the strings in a lexicographically sorted order.

For Example:

If S = “34”, then all the possible letters that can be formed from string S are {“dg”, “dh”, “di”, “eg”, “eh”, “ei”, “fg”, “fh”, “fi”}.

You are given an array of integers ‘coins’ denoting the denomination of coins and another array of integers ‘freq’ denoting the number of coins of each denomination.

You have to find the number of ways to make the sum ‘V’ by selecting some(or all) coins from the array.

The answer can be very large. So, return the answer modulo 1000000007.

For Example :

‘N’ = 3, ‘coins’ = {1, 2, 3}, ‘freq’ = {1, 1, 3}, ‘V’ = 6

For the given example, we can make six by using the following coins:
{1, 2, 3}
{3. 3}
Hence, the answer is 2.