Frog puzzle to cross the river

Puzzle:

A frog wants to cross a river that is 11 feet across.

There are 10 stones in a line leading across the river, separated by 1 foot. He can either jump to the next stone or jump over a stone, and if he jumps over a stone he must land on the next one. The furthest he can jump is 2 feet. Also, he always moves forward (toward the other side of the river). In how many different ways can he cross the river?

For example, one way to cross would be 1,2,2,1,1,2,1  with representing the frog moving 1 foot forward to the next stone, and representing the frog jumping over one stone, moving 2 feet forward.

The total distance jumped must be 11 feet; that is, if the frog is at 10 feet, the frog can’t jump by 2 feet.

Hint: What are the possible conditions before getting to the stone?

Bonus: Try to come up with a recursive routine to calculate this value for  stones.

Solution:

Correct answer: 144

To get to (n+2)th stone, he could either come from (n+1)th  stone or nth  stone. For instance, the frog can either get to 5th  stone from 4th  stone or from the  3rd stone.

Let’s examine what this means with a few smaller examples. If there is one stone, then the frog can either jump on it, or jump over it:

Option 1 Stone
1 On
2 Over

If there are two stones, then the following options are available:

Option 1 Stone 2 Stone
1 On On
2 On Over
3 Over On

There are only 3 options, because the frog cannot jump over two stones straight to the other side. At most his jumps take him 2 feet forward.

If there are three stones, then the following options are available:

Option 1 Stone 2 Stone 3 Stone
1 On On On
2 On On Over
3 On Over On
4 Over On On
5 Over On Over

There are 5 options.

This is actually enough to start seeing a pattern. The number of ways to get to the 3 stone is a3 = a2+a1  or 5 = 3 +2 . If you continue with 4, 5, 6, etc. stones, you’ll find that this pattern continues. So, the number of ways to get to nth   stone is an = an-1+ an-2 or the famous Fibonacci numbers.

With this formula we can predict the 11 stone as the 11 term of the Fibonacci sequence,

 

Simple algorithm for fibonacci series:

def fibonacci(n):
        if n < 0:
                raise ValueError("invalid index!")
        if n==0:
                return 0
        if n==1:
                return 1
        return fibonacci(n-1) + fibonacci(n-2)
Advertisements

Technical interview mcq’s preparation -now it’s your easy choice

In the engineering student life, the easiest and/or the terrible part of the placement drive is the multiple choice questions round.

Why it is so easy?

Because it is the easiest part that you can finish within few minutes. If you are really talented it may take some time to think and complete or else if you don’t have any idea of that particular subject you could surely complete it within few minutes(by using inky-pinky method).

How the college students can cross this part with ease?

The preparation for this part should begin in the 1st year of your college days. When you go for technical symposium’s, in most of the colleges they will conduct an event called code debugging.

It is the most interesting event where most of the students feared to attend. Once you attend this event you may have an idea of syntactic error and debugging. These events are the base for your technical multiple choice questions.

If you don’t have any idea over this event no problem, you have lots of websites to prepare for technical MCQs. Here I have listed some of the best websites where you can refer for your preparation.

C

C++

Data Structure

JAVA

Self Assessment in GUVI

If you have gone through all these websites, then you can have a self-assessment test in GUVI, which will help you to know about your level of technical skills.

https://www.guvi.in/self_evaluation

self evalu.PNG

Here I have listed few points which may help you to know how about how this self-assessment will help you to get placed in any product based company?

test attended.PNG

  • Once you have completed your self-assessment you would have an idea of how to attend multiple choice questions.
  • The score you obtained in your test can be viewed in GUVI’s profile.
  • This profile can be seen by anyone, if once you have shortlisted for any company’s interview through GUVI, then there may be a chance of viewing your GUVI’s profile by the recruiters.
  • It will be an added value to catch the eye of your recruiters to know about your technical skills.