SDE - 1

Ninja wants to travel from his house to a given destination, which is ‘X’ miles from his house. Along the way, he needs to fill gas in his vehicle. He knows there are ‘Y’ stations in his way. He also knows the distance between the station and his house, and how many liters of gas that particular station has.

Ninja starts his journey, with an infinite capacity of the tank filled with ‘Z’ liters of starting fuel. Suppose his vehicle uses 1 liter of gas for every mile, and ninja can stop at any gas station, transfer all the available gas at that station and then move ahead.

Now, you need to find out what is the minimum number of stops Ninja must make to reach his desired destination.

Note:

Note that if Ninja reaches a particular stop with no fuel, it can still fill his tank at that stop and continue his journey ahead. Similarly, if he reaches his destination with no fuel, it is still considered to have arrived.

For example :

Given X = 10, Y = 4, ARR[Y] = {[1, 6], [2, 3], [3, 3], [6, 4]} and Z = 1
So the path followed in this case would look like this:

Ninja starts with 1L of gas. 
Drives to the first gas station at position 1, using 1L of gas, then refueling with 6L of gas.
Then, drive to position 6, using 5L of gas, then refueling 4L in the current 1L of gas, making it a total of 5L of gas.
Finally, drive to the destination consuming 4L of gas.
So, Ninja made 2 refueling stops before reaching the destination. So, you need to print 2. 

Given an array ‘arr’ of integer numbers, ‘arr[i]’ represents the number of pages in the ‘i-th’ book.

There are ‘m’ number of students, and the task is to allocate all the books to the students.

Allocate books in such a way that:

1. Each student gets at least one book.
2. Each book should be allocated to only one student.
3. Book allocation should be in a contiguous manner.

You have to allocate the book to ‘m’ students such that the maximum number of pages assigned to a student is minimum.

If the allocation of books is not possible, return -1.

Example:

Input: ‘n’ = 4 ‘m’ = 2 
‘arr’ = [12, 34, 67, 90]

Output: 113

Explanation: All possible ways to allocate the ‘4’ books to '2' students are:

12 | 34, 67, 90 - the sum of all the pages of books allocated to student 1 is ‘12’, and student two is ‘34+ 67+ 90 = 191’, so the maximum is ‘max(12, 191)= 191’.

12, 34 | 67, 90 - the sum of all the pages of books allocated to student 1 is ‘12+ 34 = 46’, and student two is ‘67+ 90 = 157’, so the maximum is ‘max(46, 157)= 157’.

12, 34, 67 | 90 - the sum of all the pages of books allocated to student 1 is ‘12+ 34 +67 = 113’, and student two is ‘90’, so the maximum is ‘max(113, 90)= 113’.

We are getting the minimum in the last case.

Hence answer is ‘113’.

Implement a Trie Data Structure which supports the following two operations:

Operation 1 - insert(word) - To insert a string WORD in the Trie.
Operation 2-  search(word) - To check if a string WORD is present in Trie or not.

Tell me about yourself.

What are your greatest strengths and weaknesses?

Why should we hire you?