SDE - 1

Given a string 'S', you are supposed to return the number of distinct substrings(including empty substring) of the given string. You should implement the program using a trie.

Note :

A string ‘B’ is a substring of a string ‘A’ if ‘B’ that can be obtained by deletion of, several characters(possibly none) from the start of ‘A’ and several characters(possibly none) from the end of ‘A’. 

Two strings ‘X’ and ‘Y’ are considered different if there is at least one index ‘i’  such that the character of ‘X’ at index ‘i’ is different from the character of ‘Y’ at index ‘i’(X[i]!=Y[i]).

You are given a string 'S' containing dots(.) and asterisks(*) only, where the dot represents free spaces, and the asterisk denotes lamps. A lamp can lighten up its own cell as well as its immediate neighboring cells. You need to determine the minimum number of extra lamps that have to be installed at some free spaces in the string so that the whole string will be illuminated i.e. all the indices of the string can have access to the light of some lamp.

Note :

If a lamp is present at index 'I', then it illuminates index 'I' - 1, 'I' and 'I' + 1.

If a lamp is present at index 0, then it illuminates only 0 and 1.

Given that the length of the string is greater than or equal to 2.

If a lamp is present at the last index, then it illuminates the last and the second last index, given that the length of the string is greater than or equal to 2.

The length of each string is guaranteed to be at least 1.

You live in the country with ‘V’ cities that have ‘E’ roads. You are in city ‘S’ with a car having ‘P’ amount of petrol in it. Roads are bidirectional and consume your petrol. Each road has a description ‘X’, ‘Y’ and ‘Z’, which means city ‘X’ and ‘Y’ have a road between them which consumes ‘Z’ amount of petrol. You want to visit the city ‘D’. Your task is to check if it's possible to visit ‘D’ from ‘S’ using ‘P’ amount of petrol.

For Example:

In the given graph, if we want to reach from node 1 to node 4 with ‘P’ = 10, then our answer is ‘Yes’ because there exists path 1 -> 3 -> 4, which takes 7 amount of petrol, which is less than the given value of ‘P’ so it is possible and hence, the answer is ‘Yes’.

Given N pairs of parentheses, write a function to generate and print all combinations of well-formed parentheses. That is, you need to generate all possible valid sets of parentheses that can be formed with a given number of pairs.

Given two tables, one containing the details of students including student ID and another containing details of the results obtained by the students find the names of students who go to greater than 90%. This included a trick question as both the tables didn’t have a common column like student id. (Learn)

You are given an array 'ARR' of integers of length 'N' and a positive integer 'K'. You need to find the maximum elements for each and every contiguous subarray of size K of the array.

For example

'ARR' =  [3, 4, -1, 1, 5] and 'K' = 3
Output =  [4, 4, 5]

Since the maximum element of the first subarray of length three ([3, 4, -1]) is 4, the maximum element of the second subarray of length three ([4, -1, 1]) is also 4 and the maximum element of the last subarray of length three ([-1, 1, 5]) is 5, so you need to return [4, 4, 5].