Software Engineer

You are given a string 's', and a dictionary of words 'dict' containing 'n' words. Your task is to add spaces in 's' to form valid sentences, where each word is a word from the dictionary.

You need to return all possible sentences that can be formed using the given dictionary.

Note :

The same word from a dictionary can be used as many times as possible to make sentences.

You have been given a number of stairs. Initially, you are at the 0th stair, and you need to reach the Nth stair.

Each time, you can climb either one step or two steps.

You are supposed to return the number of distinct ways you can climb from the 0th step to the Nth step.

Note:

Note: Since the number of ways can be very large, return the answer modulo 1000000007.

Example :

N=3

We can climb one step at a time i.e. {(0, 1) ,(1, 2),(2,3)} or we can climb the first two-step and then one step i.e. {(0,2),(1, 3)} or we can climb first one step and then two step i.e. {(0,1), (1,3)}.

You are given an integer array 'ARR' of size ‘N’ and two integers ‘A’ and ‘B’. You need to find if there are two distinct indices in the array, such that the absolute difference of values on those indices is less than or equal to ‘B’ and the absolute difference of the indices is less than or equal to ‘A’.

Note :

Can you try to solve it in O(N) time ?

You are given an array “NUMS” consisting of N integers and an integer, K. Your task is to determine the maximum sum of an increasing subsequence of length K.

Note:

1. The array may contain duplicate elements.
2. The array can also contain negative integers.
3. Every element of the subsequence must be greater than or equal to the previous element.

The subsequence of an array is a sequence of numbers that can be formed by deleting some or no elements without changing the order of the remaining elements. For example, if the given array “NUMS” = {1, 2, 5, 4, 8}, then {1, 2, 5, 4, 8}, {1, 5, 8}, {2} are some of the valid subsequences whereas the sequence {4, 2} is not a valid subsequence as the order of the elements differ from the original array.

You have been given a Binary Search Tree of 'N' nodes, where exactly two nodes of the same tree were swapped by mistake.

Your task is to restore or fix the BST, without changing its structure and return the root of the corrected BST.

Note:

Given BST will not contain duplicates.

Example

A Binary Search Tree (BST) whose 2 nodes have been swapped is shown below.  

After swapping the incorrect nodes: 

Follow Up

Can you do this without using any extra space?