SDE - 1

You are given a binary tree in which each node contains an integer value and a number ‘K’. Your task is to print every path of the binary tree with the sum of nodes in the path as ‘K’.

Note:

1. The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

2. Output the paths in the order in which they exist in the tree from left to right. Example: In the below example, path {1,3} is followed by {3,1} and so on.

Example:

For K = 4 and tree given below:

The possible paths are:
1 3
3 1
-1 4 1
4 
-1 5

The sum of values of nodes of each of the above-mentioned paths gives a sum of 4.

Design a data structure that stores a mapping of a key to a given value and supports the following operations in constant time.

1. INSERT(key, value): Inserts an integer value to the data structure against a string type key if not already present. If already present, it updates the value of the key with the new one. This function will not return anything.

2. DELETE(key): Removes the key from the data structure if present. It doesn't return anything.

3. SEARCH(key): It searches for the key in the data structure. In case it is present, return true. Otherwise, return false.

4. GET(key): It returns the integer value stored against the given key. If the key is not present, return -1. 

5. GET_SIZE(): It returns an integer value denoting the size of the data structure. 

6. IS_EMPTY(): It returns a boolean value, denoting whether the data structure is empty or not. 

Note :

1. Key is always a string value.
2. Value can never be -1.

Operations Performed :

First(Denoted by integer value 1):  Insertion to the Data Structure. It is done in a pair of (key, value).

Second(Denoted by integer value 2):  Deletion of a key from the Data Structure.

Third(Denoted by integer value 3): Search a given key in the Data Structure.

Fourth(Denoted by integer value 4): Retrieve the value for a given key from the Data Structure.

Fifth(Denoted by integer value 5): Retrieve the size of the Data Structure.

Sixth(Denoted by integer value 6): Retrieve whether the Data Structure is empty or not.

You are given an infinite supply of coins of each of denominations D = {D0, D1, D2, D3, ...... Dn-1}. You need to figure out the total number of ways W, in which you can make a change for value V using coins of denominations from D. Print 0, if a change isn't possible.

You have been given an integer array/list 'ARR' of size 'N'. Write a solution to check if it could become non-decreasing by modifying at most 1 element.

We define an array as non-decreasing, if ARR[i] <= ARR[i + 1] holds for every i (0-based) such that (0 <= i <= N - 2).

Tell me about yourself.
Why should we hire you?
What are your strengths and weaknesses?