description for house robber and egg dropping puzzle

sherxon · Aug 31, 2018 · dcd7b97 · dcd7b97
1 parent aeb3caf
commit dcd7b97
Showing 1 changed file with 38 additions and 0 deletions.
diff --git a/src/problems/Medium.txt b/src/problems/Medium.txt
@@ -3090,3 +3090,41 @@ Note:
 
 1 <= words.length <= 50
 1 <= pattern.length = words[i].length <= 20
+
+
+200)  House Robber 2
+
+A robber is planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at
+this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have
+security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
+
+You are given a list of non-negative integers representing the amount of money of each house, we need to determine the maximum amount of
+money the robber can rob tonight without alerting the police.
+
+Eg: Suppose you are given an array of money of houses like   [2,3,2] , max amount of money robber can rob is 3, as he cannot rob
+house 1 (money = 2) and then rob house 3 (money = 2),  because they are adjacent houses.
+
+201) Egg Dropping Puzzle
+The following is a description of the instance of this famous puzzle involving n=2 eggs and a building with k=36 floors.
+
+Suppose that we wish to know which stories in a 36-story building are safe to drop eggs from, and which will cause the eggs to
+break on landing. We make a few assumptions:
+
+…..An egg that survives a fall can be used again.
+…..A broken egg must be discarded.
+…..The effect of a fall is the same for all eggs.
+…..If an egg breaks when dropped, then it would break if dropped from a higher floor.
+…..If an egg survives a fall then it would survive a shorter fall.
+…..It is not ruled out that the first-floor windows break eggs, nor is it ruled out that the 36th-floor do not cause an egg to break.
+
+If only one egg is available and we wish to be sure of obtaining the right result, the experiment can be carried out in only one way.
+ Drop the egg from the first-floor window; if it survives, drop it from the second floor window. Continue upward until it breaks.
+  In the worst case, this method may require 36 droppings. Suppose 2 eggs are available. What is the least number of egg-droppings
+   that is guaranteed to work in all cases?
+The problem is not actually to find the critical floor, but merely to decide floors from which eggs should be dropped so that total
+ number of trials are minimized.
+
+ Here, we need to design a solution to a general problem with n eggs and k floors.
+
+ Eg: For 10 floors and 2 eggs, minimum number of trials in worst case with 2 eggs and 10 floors is 4,
+     as we can first drop egg from 4th floor, if it doesn't break, then from 7th and then from 9th and eventually 10.