Microsoft Interview

Compute the smallest set of points

7/18/2021

As per one website below question was asked in Microsoft.

Let X be a set of n intervals on the real line. We say that a set of points P "stabs" X if every interval in X contains at least one point in P. Compute the smallest set of points that stabs X.
For example, given the intervals [(1, 4), (4, 5), (7, 9), (9, 12)], you should return [4, 9].

Please suggest your solution.

0 Comments

Largest sum of non-adjacent numbers

7/11/2021

0 Comments

Given an array of integers, write a function that returns the largest sum of non-adjacent numbers. Numbers can be 0 or negative.
For example, [2, 4, 6, 2, 5] should return 13, since we pick 2, 6, and 5. [5, 1, 1, 5] should return 10, since we pick 5 and 5.

[5, 20, 15, -2, 18] => 20 + 18 = 38
[4, 1, 6, 3, 2] => 4 + 6 + 2 = 12

Follow-up: Can you do this in O(N) time and constant space?

All such questions can be seen all over the Internet, just do Google search a little & one can solve these questions. Below is kind of same -

0 Comments

How far can you Go

7/4/2021

0 Comments

You are given an array of integers, where every value denotes the height of the building.
You are also given some Ladders & Bricks
If the height of the next building is more than current building, then you can use either Ladder
or Bricks but if next building height is less, then you can jump to next building directly.
So if next building height is more you need Ladder/Builder else you can move to next building without consuming any resource.

Conditions :
1) Ladder can be used for any height, can assume length of Ladder is infinite.
2) For height difference of e.g. 5, you will need 5 bricks, so 1 Brick covers 1 unit of height only.
3) If you use any Brick or Ladder to move ahead then it can't be used again.

Now you need to find the farthest index to which you can move using the given resources optimally. You will start from index 0.
e.g. heights : 4,12,2,7,3,18,20,3,19
Bricks : 10 & Ladders : 2

Answer: One can reach to index 7 with height 3, as either all resources are consumed to
reach here or don't have sufficient resources remaining.

Explanation :
You can use 8 Bricks to move from Building 4 to Building 12
Jump to building with height 2.
Use Ladder to move from Building 2 to Building 7
Jump to building with height 3.
Use Ladder to move from Building 3 to Building 18
Use 2 Bricks to move from Building 18 to Building 20
Jump to building with height 3.
So answer will be 7, that is last index in the given array to which you can move to, using the
given resources.

Approach : First consume all the ladders & keep the minimum gap where you have used the
ladder, one can use the sorted list or Priority Queue to keep the minimum gap at the top.
PriorityQueue concept has been suggested by one another reader & it will be performance
efficient.
After consuming all the ladders, if get any gap which is greater than the minimum gap used for ladder, then remove minimum gap to use for bricks & use ladder for new bigger gap. Also put this new in the collection being mantained above for ladders.

Solution :

0 Comments

Compute the smallest set of points

Largest sum of non-adjacent numbers

How far can you Go

Author

Archives

Categories