SDE - 1

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.

For a given array with N elements, you need to find the length of the longest subsequence from the array such that all the elements of the subsequence are sorted in strictly increasing order.

Strictly Increasing Sequence is when each term in the sequence is larger than the preceding term.

For example:

[1, 2, 3, 4] is a strictly increasing array, while [2, 1, 4, 3] is not.

Aahad and Harshit always have fun by solving problems. Harshit took a sorted array consisting of distinct integers and rotated it clockwise by an unknown amount. For example, he took a sorted array = [1, 2, 3, 4, 5] and if he rotates it by 2, then the array becomes: [4, 5, 1, 2, 3].

After rotating a sorted array, Aahad needs to answer Q queries asked by Harshit, each of them is described by one integer Q[i]. which Harshit wanted him to search in the array. For each query, if he found it, he had to shout the index of the number, otherwise, he had to shout -1.

For each query, you have to complete the given method where 'key' denotes Q[i]. If the key exists in the array, return the index of the 'key', otherwise, return -1.

Note:

Can you solve each query in O(logN) ?

Given an array parent which represents a binary tree such that parent-child relationship is defined by ('PARENT'[i], 'i') which means that parent of i is 'PARENT'[i]. The value of the root node will be i if -1 is present at 'PARENT'[i].

For example:

For the parent array {1, -1, 1}, the tree will be:- 

As, parent of 0 is 'PARENT'[0] i.e. 1.
1 is the root as 'PARENT'[1] = -1.
Parent of 2 is 'PARENT'[2] i.e. 1.

Similarly for the parent array { 1, 2, -1}, the tree will be:-

Your task is to create the Binary tree from the given parent array.

Note:

From the parent array, multiple binary trees may be possible. You have to create a binary tree in such a way that these conditions satisfy:-

If the node has a left child as well as a right child, make sure the left child is smaller than the right child. 

If the node has only one child, make sure it has an only left child. 

For {1, -1, 1}, the accepted tree will be:- 

And for {1, -1}, the accepted tree will be, 

Instead of 

You have been given an N*M matrix filled with integer numbers, find the maximum sum that can be obtained from a path starting from any cell in the first row to any cell in the last row.

From a cell in a row, you can move to another cell directly below that row, or diagonally below left or right. So from a particular cell (row, col), we can move in three directions i.e.

Down: (row+1,col)
Down left diagonal: (row+1,col-1)
Down right diagonal: (row+1, col+1)

You are given an array 'ARR' of 'N' positive integers. Your task is to find if we can partition the given array into two subsets such that the sum of elements in both subsets is equal.

For example, let’s say the given array is [2, 3, 3, 3, 4, 5], then the array can be partitioned as [2, 3, 5], and [3, 3, 4] with equal sum 10.

Follow Up:

Can you solve this using not more than O(S) extra space, where S is the sum of all elements of the given array?

Build Search Functionality, for a Hotel booking system like OYO, which should results in relevant search result based on User query. Constraints were as follows:-
1. User Query can be anything.
2. Hotel Records/Data can be Huge.
3. Have to respond with relevant search result even if user query is not correct. Have to respond with closest relevant result.



Schema of Data:-
Hotel ABC,
Name: 1, Hotel ABC, 2. Hotel XYZ.

Description: 1. 100 character -> “5 star hotel….”

Geo {
India
Asia
}


Facilities (upto 10) [
Swimming pool,
Free Lunch.

].


Following Important Questions were asked during the discussion of this problem.
Q:-1. How do you divide your data?
Q:2. how do we do a best relevant search for hotel product.
Q:3. How do you store the data?