Tuesday, July 26, 2011
Given that you Can store integers in strings. Right an increment function in C that will increment a given integer by one
A Reader send me mail to solve this probloem :) will tryy to do it asap :)
Labels:Data
Google Interview
Monday, July 25, 2011
Find The Maximum Sum in Triangle From Top to Bottom (Euler Problem) . Don't Forget to Check the Code for Triangle Which has 100s of Base :)
An Anonymous reader sent me the problem & ii posted it here
ohh but i forgot that Problem is already solved & posted few months back . so i am not giving to d same again excpet providing the link
Problem Discription
Given a triangle like the following
3
4 6
1 5 0 1.
How many nodes would you have, for 20 rows? 2. How to find the largest sum from the top of the triangle to the one of the nodes at the bottom. In other words, if you consider it as a tree, find the max sum of all paths from root to the leaf.
Thinking Process & Approach Here
This involves maths stuff rather then considering tree (it wont work check below link for detail ) or applying computer science & problem is already famous (Euler problem ) as we have to find the maximum sum in triangle we have given a big triangle which has many small triangle only thing u need to know a triangle has 3 vertexes so that you can approach :)
and a detailed description,explaination & solution you can find here
http://shashank7s.blogspot.com/2011/04/project-euler-problem-67-finding.html
let me know if i missed something or any other approach to solve it
one think that would recommands to geeks try out the recursive solution for the same problem :)
ohh but i forgot that Problem is already solved & posted few months back . so i am not giving to d same again excpet providing the link
Problem Discription
Given a triangle like the following
3
4 6
1 5 0 1.
How many nodes would you have, for 20 rows? 2. How to find the largest sum from the top of the triangle to the one of the nodes at the bottom. In other words, if you consider it as a tree, find the max sum of all paths from root to the leaf.
Thinking Process & Approach Here
This involves maths stuff rather then considering tree (it wont work check below link for detail ) or applying computer science & problem is already famous (Euler problem ) as we have to find the maximum sum in triangle we have given a big triangle which has many small triangle only thing u need to know a triangle has 3 vertexes so that you can approach :)
and a detailed description,explaination & solution you can find here
http://shashank7s.blogspot.com/2011/04/project-euler-problem-67-finding.html
let me know if i missed something or any other approach to solve it
one think that would recommands to geeks try out the recursive solution for the same problem :)
Labels:Data
Google Interview
Given a positive integer n, find the minimum number of steps that takes n to 1 eg: 1.)For n = 1 , output: 0 2.) For n = 4 , output: 2 ( 4 /2 = 2 /2 = 1 ) 3.) For n = 7 , output: 3 ( 7 -1 = 6 /3 = 2 /2 = 1 )
On a positive integer, you can perform any one of the following 3 steps. 1.) Subtract 1 from it. ( n = n - 1 ) , 2.) If its divisible by 2, divide by 2. ( if n % 2 == 0 , then n = n / 2 ) , 3.) If its divisible by 3, divide by 3. ( if n % 3 == 0 , then n = n / 3 ). Using These Conditions Solve Above Question Efficiently ?
Approach / Idea: One can think of greedily choosing the step, which makes n as low as possible and conitnue the same, till it reaches 1. If you observe carefully, the greedy strategy doesn't work here. Eg: Given n = 10 , Greedy --> 10 /2 = 5 -1 = 4 /2 = 2 /2 = 1 ( 4 steps ). But the optimal way is --> 10 -1 = 9 /3 = 3 /3 = 1 ( 3 steps ). So, we need to try out all possible steps we can make for each possible value of n we encounter and choose the minimum of these possibilities.
It all starts with recursion :). F(n) = 1 + min{ F(n-1) , F(n/2) , F(n/3) } if (n>1) , else 0 ( i.e., F(1) = 0 ) . Now that we have our recurrence equation, we can right way start coding the recursion. Wait.., does it have over-lapping subproblems ? YES. Is the optimal solution to a given input depends on the optimal solution of its subproblems ? Yes... Bingo ! its DP :) So, we just store the solutions to the subproblems we solve and use them later on, as in memoization.. or we start from bottom and move up till the given n, as in dp. As its the very first problem we are looking at here, lets see both the codes.
Memoization
[code]
int memo[n+1]; // we will initialize the elements to -1 ( -1 means, not solved it yet )
int getMinSteps ( int n )
{
if ( n == 1 ) return 0; // base case
if( memo[n] != -1 ) return memo[n]; // we have solved it already :)
int r = 1 + getMinSteps( n - 1 ); // '-1' step . 'r' will contain the optimal answer finally
if( n%2 == 0 ) r = min( r , 1 + getMinSteps( n / 2 ) ) ; // '/2' step
if( n%3 == 0 ) r = min( r , 1 + getMinSteps( n / 3 ) ) ; // '/3' step
memo[n] = r ; // save the result. If you forget this step, then its same as plain recursion.
return r;
}
[/code]
Bottom-Up DP
[code]
int getMinSteps ( int n )
{
int dp[n+1] , i;
dp[1] = 0; // trivial case
for( i = 2 ; i < = n ; i ++ )
{
dp[i] = 1 + dp[i-1];
if(i%2==0) dp[i] = min( dp[i] , 1+ dp[i/2] );
if(i%3==0) dp[i] = min( dp[i] , 1+ dp[i/3] );
}
return dp[n];
}
Labels:Data
Dynamic Programming
,
Facebook Interview
,
Google Interview
Sunday, July 24, 2011
You have a set of ants moving on an horizontal segment of length n. Each ant can randomly move either right or left. When an ant takes a direction, she stays in that direction until she either drops out of the segment or it bumps with another ant. In this case, the ant changes her direction. Can you formalize the system and describe what will happen after t iterations?
Labels:Data
Google Interview
Subscribe to:
Posts
(
Atom
)