jinalshah2007
BAN USER- 0of 0 votes
AnswersWe have n punching bags in a row. Mr Lee is going to practice with them for the upcoming Boxing tournament.
- jinalshah2007 in United States
Each bag has a resistance level. Mr Lee can punch a bag if its resistance is greater than 0. He is an extremely hard puncher: when Mr Lee punches a bag, not only is its resistance set to 0 (ie: the bag is destroyed), but also the resistances of its immediately adjacent neighbors( one on left and other on right ) are decreased by one. If at any point of time the resistance of a bag drops to zero or less it is considered as destroyed. A punch on a bag with resistance greater than 0 has no impact on an immediate neighbour which is already destroyed.
Mr Lee wants to maximize his (very expensive) workout sessions, and would like to punch on these bags as much as possible. For any set of punching bags, what is the maximum number of punches that he can perform?
Input Format
On the only line of input there are n characters describing the resistances of the bags from 1 to n.
Ouput Format
On the only line of the output print an integer describing the maximum number of punches Mr Lee can punch for that set of bags.
Sample Input
11
Sample Ouput
1
Sample Input
021
Sample Output
2
Explanation
In the first example there are two bags, and we can punch only one of them before destroying both. In the second example we can punch on the third bag and then on the second bag to obtain two punches.
Constraints
Each bag has a resistance level between 0 and 3 ( inclusive ) and the number of bags is not more than 100.| Report Duplicate | Flag | PURGE
Algorithm - 0of 0 votes
AnswersGiven a sequence of integers a[1],a[2],...,a[n], we call a sequence b[1], ..., b[m] an alternating sequence if:
- jinalshah2007 in United States
for every odd 1 < i <= m, we have b[i] < b[i-1],
for every even 1 < i <= m, we have b[i] > b[i-1].
Given a sequence of integers a[1], ..., a[n], your program must find the length of the longest alternating subsequence. (we define a[i1], ..., a[im] to be a subsequence if 1<=i1< i2<...<im<=n.)
Input
First line of input contains the length of sequence n (1<=n<=200,000). The second line contains n space seperated integers a[1], ..., a[n] (1 <= a[i] <= 10^9).
Output
Output is just a single integer number which denotes the length of longest alternating subsequence.
Sample Input
10
1 2 3 4 5 6 5 4 3 2
Sample Output
3
Explanation: On many alternating subsequences of length three, some are 1 6 2, 3 5 3, 4 6 2 etc. There is no alternating subsequence of length greater than three.
Note : A sequence with just two elements, such that the second element is greater than first is a valid alternating sequence. Moreover a sequence with only one element is also considered an alternating sequence.| Report Duplicate | Flag | PURGE
Algorithm - 0of 2 votes
AnswersGiven a character array. Find if there exists a path from O to X. Here is an example
- jinalshah2007 in United States
. . . . . . .
. . . . . . .
w . . . . . .
w .w.w..
. . . . O . .
. . w. . . .
. . . X . . .
You have to just keep in mind that you cannot go through 'W'.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Brain Teasers Dynamic Programming - 0of 0 votes
AnswersWrite a program for Palindrome
- jinalshah2007 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 0of 0 votes
AnswersGiven a binary tree and 2 values. Write a function to find the 1st common ancestor in the binary tree.
The method I have used is that the common ancestor is the one who would have value between the given 2 values. So for example if the values are 3 and 10. so the common ancestor would be a node with value greater than 3 and less than 10.
here is my code.public Node getCommonAncestor(Node root,int a, int b) { if((root.value>a && root.value<b) || (root.value<a&&root.value>b)) { if(checkvalue(root,a) && checkvalue(root,b)) { return root; } else { return null; } } else if(root.value>a && root.value>b) { if(root.left != null) { return getCommonAncestor(root.left,a,b) } else { return null; } } else { if(root.right != null) { return getCommonAncestor(root.right,a,b) } else { return null; } } } public boolean checkvalue(Node root,int a) { if(check.value == a) { return true; } else if(check.value>a) { if(check.left != null) { return checkvalue(check.left,a) } else { return false; } } else { if(check.right != null) { return checkvalue(check.right,a) } else { return false; } } } class Node { int value; Node left; Node right; }
Can you suggest whether I am right or not?
- jinalshah2007 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - 0of 0 votes
AnswersGiven a binary tree and 2 values. Write a function to find the 1st ancestor of the binary tree.
- jinalshah2007 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer
Sorry ..... it was a binary search tree my mistake in writing the question
- jinalshah2007 March 23, 2012
I agree with NewCoderInTown, Here is the code to do that
if you are still concerned with complexity you can't do it more better than this.
- jinalshah2007 April 18, 2012