ADP Interview Question abcs
Country: India
Interview Type: In-Person
Javacode and testcase:
package dev.random;
public class BallPassProblem
{
public int getNumberOfPasses(int numberOfFriends, int jumpCount, int maxNumber)
{
int[] friends = new int[numberOfFriends];
int countInPosition=0;
friends[0]++;
countInPosition = friends[0];
int ballPosition = 0;
int maxIndexInArray = numberOfFriends - 1;
int countOfPasses=1;
jumpCount++;
while (countInPosition < maxNumber)
{
if (countInPosition % 2 == 0)
{
int tempBallPosition = ballPosition - jumpCount;
ballPosition = (tempBallPosition < 0) ? maxIndexInArray + (tempBallPosition) : tempBallPosition;
}
else
{
int tempBallPosition = ballPosition + jumpCount;
ballPosition = (tempBallPosition > maxIndexInArray) ? (tempBallPosition - maxIndexInArray) : tempBallPosition;
}
countInPosition = ++friends[ballPosition];
countOfPasses++;
}
return countOfPasses;
}
}
//testcase:
package dev.random;
import org.junit.Test;
import static junit.framework.TestCase.assertEquals;
public class BallPassProblemTest
{
@Test
public void testGetNumberOfPasses() throws Exception
{
BallPassProblem problem = new BallPassProblem();
assertEquals(10, problem.getNumberOfPasses(5,2,3));
}
}
I am new to this website. I don't know why I can't submit a reply to a reply. So I copy my previous (fixed) answer, appended by my explanation to it.
Find the greatest common divisor (GCD) of N and L. Then the ball comes back to person #1 after N/GCD(N,L) passing. So the answer should be (M-1)*N/GCD(N,L).
Oh there is a tiny mistake in my previous formula. I think I have fixed it. It should be (M-1)*N/GCD(N,L), instead of M*N/GCD(N,L), because once a person reaches the ball for M times, the game stops, and the M-th round is not completed. Only (M-1) rounds are completed.
The intuition of the formula is this: When the group of people passing the ball, starting from person #1, the ball must come back to #1 some time. (Why? Hint: the number of people is finite. Hint2: proof by contradiction.)
How many passing has been made before the ball comes back? The answer is N*GCD(N,L). (Why? Hint: When GCD(N,L)=1, how many numbers have been covered before the ball comes back to #1? Does every number covered? When GCD(N,L)=2, how many numbers have been covered before the ball comes back to #1? Does every number covered? or only half? If only half have been covered, will the other half of numbers be covered if the ball starts at person#2? What if GCD(N,L)=3?)
Think about the above questions, you will find that if GCD(N,L)=x, only 1/x of those people have touched the ball before the ball comes back to person#1. If you start passing the ball from person#k (where 1<k<x) instead of person#1, another group of people will touch the ball. See this wikipedia page for more theoretical knowledge: en.wikipedia[DOT]org/wiki/Ring_(mathematics) )
So, starting from person#1, when the ball comes back to person#1 there have been N/GCD(N,L) people touch the ball once. Or equivalently, there have been N/GCD(N,L) many passing. Then, no matter whether the passing direction is changed, those people who have touched the ball will touch it again within the next N/GCD(N,L) passing. If the limit M is not reached, these N/GCD(N,L) people keep passing the ball. Other people will never have opportunity to touch it.
When will the repetition stop? When SomeONE is going to touch the ball for the M-th time. How many times has the ball come back to person#1 before that? M-1. So there are (M-1)*(N/GCD(N,L)) many passing.
#!/usr/bin/perl
use warnings;
use strict;
our $DEBUG = 0;
chomp( our $N = $ARGV[0] );
chomp( our $M = $ARGV[1] );
chomp( our $L = $ARGV[2] );
my @receives;
for (my $i = 0; $i <= $N; $i++) {
$receives[$i] = 0;
}
my $count_of_passes = 0;
my $currient = 1;
$receives[$currient] += 1;
do {
my $new_pos;
if ( ($receives[$currient] % 2) == 0 ) {
$new_pos = get_position_to_left($currient);
} else {
$new_pos = get_position_to_right($currient);
}
print("\$receives[$currient] = $receives[$currient], \$new_pos = $new_pos\n") if ($DEBUG);
$currient = $new_pos;
$receives[$currient] += 1;
$count_of_passes += 1;
} while ( $receives[$currient] < $M );
print("\$N=$N, \$M=$M, \$L=$L\n");
print("Count of passes from direct counting:\t$count_of_passes\n");
$count_of_passes = ($M - 1)*$N / greatest_common_divisor($N, $L);
print("Count of passes with GCD halp:\t\t$count_of_passes\n");
# ========================================================================== #
sub get_position_to_right {
my $currient = shift();
my $l;
($L > $N) ? ($l = $L % $N) : ($l = $L);
print("go-to-right ") if ($DEBUG);
if ( $currient - $l > 0 ) {
return $currient - $l;
} else {
return $N + ($currient - $l);
}
}
sub get_position_to_left {
my $currient = shift();
my $l;
($L > $N) ? ($l = $L % $N) : ($l = $L);
print("go-to-left ") if ($DEBUG);
if ( $currient + $l <= $N ) {
return $currient + $l;
} else {
return ($currient + $l) - $N;
}
}
# ========================================================================== #
sub greatest_common_divisor {
my $arg1 = shift();
my $arg2 = shift();
my @dividers1;
my @dividers2;
my @common_dividers;
my ($i, $j);
for( $i = 1; $i <= $arg1; $i++ ) {
if( !($arg1 % $i) ) {
$dividers1[ scalar(@dividers1) ] = $i;
}
}
for( $i = 1; $i <= $arg2; $i++ ) {
if( !($arg2 % $i) ) {
$dividers2[ scalar(@dividers2) ] = $i;
}
}
print("Dividers1: @dividers1\n") if ($DEBUG);
print("Dividers2: @dividers2\n") if ($DEBUG);
foreach $i (@dividers1) {
foreach $j (@dividers2) {
if ($i == $j) {
$common_dividers[scalar(@common_dividers)] = $i;
}
}
}
print("Common Dividers for $arg1 and $arg2: @common_dividers\n") if ($DEBUG);
return $common_dividers[$#common_dividers];
}
#include <iostream>
#include <vector>
class ball_passing
{
int no_of_frnds;
int jump;
int max_count;
public:
ball_passing(int n, int m, int l) :jump(l), max_count(m), no_of_frnds(n){};
void ball_throw()
{
std::vector<int> frnds(no_of_frnds);
int next = 0; //start with frnd 1
int passes = 0;
frnds[next]++;
while (frnds[next] < max_count)
{
++passes;
if (frnds[next] % 2 == 0)
{
next = (next + jump) < no_of_frnds ? (next + jump) : (next + jump - no_of_frnds);
}
else
{
next = (next + no_of_frnds - jump) < no_of_frnds ? (next + no_of_frnds - jump) : (next - jump) ;
}
++frnds[next];
}
std::cout << "\nTotal passes:" << passes;
}
};
int main()
{
ball_passing bp(5,3,2);
bp.ball_throw();
return 0;
}
Hi Guys,
I write below program and its working fine for sample and also successfully submitted to techgig but marks was very less. I want to know what are the problems in my code.
public static int totalPasses(int input1,int input2, int input3) {
int N = input1;
int M = input2;
int L = input3;
int max = 0;
int index = 0;
int totalPasses = 0;
int[] arr = new int[N];
while (max != M) {
int currentPass = arr[index];
currentPass= currentPass+1;
arr[index] =currentPass;
max = Math.max(max, currentPass);
if (max == M) {
break;
}
totalPasses++;
if (currentPass % 2 == 0) {
for (int i = 1; i <= L+1; i++) {
index--;
if (index == -1) {
index = N - 1;
}
}
} else {
for (int i = 1; i <= L+1; i++) {
index++;
if (index == N) {
index = 0;
}
}
}
}
return totalPasses;
}
Hi Gus,
My solution passes test cases but marks was very less. Can anyone point out problems in below code
public static int totalPass(int input1,int input2,int input3) {
int N = input1;
int M = input2;
int L = input3;
int max = 0;
int index = 0;
int totalPasses = 0;
int[] arr = new int[N];
while (max != M) {
int currentPass = arr[index];
currentPass= currentPass+1;
arr[index] =currentPass;
max = Math.max(max, currentPass);
if (max == M) {
break;
}
totalPasses++;
if (currentPass % 2 == 0) {
for (int i = 1; i <= L+1; i++) {
index--;
if (index == -1) {
index = N - 1;
}
}
} else {
for (int i = 1; i <= L+1; i++) {
index++;
if (index == N) {
index = 0;
}
}
}
}
return totalPasses;
}
class Ideone
{
public static int passCount(int input1,int input2,int input3)
{
//Write code here
int ballPosition = 1 ;
int friend[] = new int[input1+1];
friend[ballPosition] = 1 ;
int countOfPerson = friend[ballPosition] ;
int count = 0;
while(countOfPerson <= input2){
if(countOfPerson%2 == 0 ){
friend[ballPosition]++;
int tempBallPosition = ballPosition - input3 - 1;
ballPosition =tempBallPosition<=0 ? (input1 + tempBallPosition):tempBallPosition ;
System.out.println("ballPosition left" + ballPosition);
friend[ballPosition]++;
count++ ;
countOfPerson = friend[ballPosition];
System.out.println("countOfPerson left"+countOfPerson);
}else{
friend[ballPosition]++;
int tempBallPosition = ballPosition + input3 + 1 ;
ballPosition = tempBallPosition>input1 ? (tempBallPosition-input1): tempBallPosition ;
System.out.println("ballPosition right" + ballPosition);
friend[ballPosition]++;
count++;
countOfPerson = friend[ballPosition];
System.out.println("countOfPerson right"+countOfPerson);
}
}
return count ;
}
public static void main (String[] args) throws java.lang.Exception
{
int result = passCount(5,3,2);
System.out.println("result"+result);
}
}
class Ideone
{
public static int passCount(int input1,int input2,int input3)
{
//Write code here
int ballPosition = 1 ;
int friend[] = new int[input1+1];
friend[ballPosition] = 1 ;
int countOfPerson = friend[ballPosition] ;
int count = 0;
while(countOfPerson <= input2){
if(countOfPerson%2 == 0 ){
friend[ballPosition]++;
int tempBallPosition = ballPosition - input3 - 1;
ballPosition =tempBallPosition<=0 ? (input1 + tempBallPosition):tempBallPosition ;
System.out.println("ballPosition left" + ballPosition);
friend[ballPosition]++;
count++ ;
countOfPerson = friend[ballPosition];
System.out.println("countOfPerson left"+countOfPerson);
}else{
friend[ballPosition]++;
int tempBallPosition = ballPosition + input3 + 1 ;
ballPosition = tempBallPosition>input1 ? (tempBallPosition-input1): tempBallPosition ;
System.out.println("ballPosition right" + ballPosition);
friend[ballPosition]++;
count++;
countOfPerson = friend[ballPosition];
System.out.println("countOfPerson right"+countOfPerson);
}
}
// System.out.println(count);
return count ;
}
public static void main (String[] args) throws java.lang.Exception
{
int result = passCount(5,3,2);
System.out.println("result"+result);
}
}
Hello Friends,
My Solution :
function passCount($noOfPlayer, $maxPass, $number) {
$playerNo = 1;
$arr[$playerNo] = 1;
$ballPassTime = 0;
while ($arr[$playerNo] != $maxPass) {
$ballPassTime++;
if ($arr[$playerNo] % 2 !== 0) {
$playerNo = $playerNo + $number + 1;
} else {
$playerNo = $playerNo + $number;
}
if ($playerNo > $noOfPlayer) {
$playerNo -= $noOfPlayer;
}
if (array_key_exists($playerNo, $arr)) {
$arr[$playerNo] += 1;
} else {
$arr[$playerNo] = 1;
}
if (in_array($maxPass, $arr)) {
return $ballPassTime;
}
}
}
echo passCount(5, 3, 2);
<?php
function getPassCount($noOfPlayer, $maxPass, $number) {
$playerNo = 1;
$arr[$playerNo] = 1;
$ballPassTime = 0;
while ($arr[$playerNo] != $maxPass) {
$ballPassTime++;
if ($arr[$playerNo] % 2 !== 0) {
$playerNo = $playerNo + $number + 1;
} else {
$playerNo = $playerNo + $number;
}
if ($playerNo > $noOfPlayer) {
$playerNo -= $noOfPlayer;
}
if (array_key_exists($playerNo, $arr)) {
$arr[$playerNo] += 1;
} else {
$arr[$playerNo] = 1;
}
if (in_array($maxPass, $arr)) {
return $ballPassTime;
}
}
}
echo getPassCount(5, 3, 2);
?>
public class CandidateCode
{
public static int passCount(int input1,int input2,int input3)
{
//Write code here
int N=input1;
int M=input2;
int L=input3;
int output=0;
int Pos=1;
int[] ternCount= new int[N];
if(N > 0 && M >0 && L>0)
{
while((ternCount[Pos-1])<M)
{
if( (++ternCount[Pos-1])!=M )
{
if(ternCount[Pos-1]%2!=0)//odd
{
Pos=MoveRight(Pos,L,N);
}
else
{
Pos=MoveLeft(Pos,L,N);
}
output++;
}
else
{
return output;
}
}
return (output);
}
else
return -1;
}
public static int MoveLeft(int cur,int moveTimes,int total )
{
int Pos = (cur+moveTimes)%total;
return Pos==0 ? total : Pos;
}
public static int MoveRight(int cur,int moveTimes,int total )
{
int Pos=(total+cur-moveTimes)%total;
return Pos==0 ? total : Pos;
}
}
public class CandidateCode
{
public static int passCount(int input1,int input2,int input3)
{
//Write code here
int N=input1;
int M=input2;
int L=input3;
int output=0;
int Pos=1;
int[] ternCount= new int[N];
if(N > 0 && M >0 && L>0)
{
while((ternCount[Pos-1])<M)
{
if( (++ternCount[Pos-1])!=M )
{
if(ternCount[Pos-1]%2!=0)//odd
{
Pos=MoveRight(Pos,L,N);
}
else
{
Pos=MoveLeft(Pos,L,N);
}
output++;
}
else
{
return output;
}
}
return (output);
}
else
return -1;
}
public static int MoveLeft(int cur,int moveTimes,int total )
{
int Pos = (cur+moveTimes)%total;
return Pos==0 ? total : Pos;
}
public static int MoveRight(int cur,int moveTimes,int total )
{
int Pos=(total+cur-moveTimes)%total;
return Pos==0 ? total : Pos;
}
}
public class CandidateCode
{
public static int passCount(int input1,int input2,int input3)
{
//Write code here
int N=input1;
int M=input2;
int L=input3;
int output=0;
int Pos=1;
int[] ternCount= new int[N];
if(N > 0 && M >0 && L>0)
{
while((ternCount[Pos-1])<M)
{
if( (++ternCount[Pos-1])!=M )
{
if(ternCount[Pos-1]%2!=0)//odd
{
Pos=MoveRight(Pos,L,N);
}
else
{
Pos=MoveLeft(Pos,L,N);
}
output++;
}
else
{
return output;
}
}
return (output);
}
else
return -1;
}
public static int MoveLeft(int cur,int moveTimes,int total )
{
int Pos = (cur+moveTimes)%total;
return Pos==0 ? total : Pos;
}
public static int MoveRight(int cur,int moveTimes,int total )
{
int Pos=(total+cur-moveTimes)%total;
return Pos==0 ? total : Pos;
}
}
public class CandidateCode
{
public static int passCount(int input1,int input2,int input3)
{
//Write code here
int N=input1;
int M=input2;
int L=input3;
int output=0;
int Pos=1;
int[] ternCount= new int[N];
if(N > 0 && M >0 && L>0)
{
while((ternCount[Pos-1])<M)
{
if( (++ternCount[Pos-1])!=M )
{
if(ternCount[Pos-1]%2!=0)//odd
{
Pos=MoveRight(Pos,L,N);
}
else
{
Pos=MoveLeft(Pos,L,N);
}
output++;
}
else
{
return output;
}
}
return (output);
}
else
return -1;
}
public static int MoveLeft(int cur,int moveTimes,int total )
{
int Pos = (cur+moveTimes)%total;
return Pos==0 ? total : Pos;
}
public static int MoveRight(int cur,int moveTimes,int total )
{
int Pos=(total+cur-moveTimes)%total;
return Pos==0 ? total : Pos;
}
}
public class CandidateCode
{
public static int passCount(int input1,int input2,int input3)
{
//Write code here
int N=input1;
int M=input2;
int L=input3;
int output=0;
int Pos=1;
int[] ternCount= new int[N];
if(N > 0 && M >0 && L>0)
{
while((ternCount[Pos-1])<M)
{
if( (++ternCount[Pos-1])!=M )
{
if(ternCount[Pos-1]%2!=0)//odd
{
Pos=MoveRight(Pos,L,N);
}
else
{
Pos=MoveLeft(Pos,L,N);
}
output++;
}
else
{
return output;
}
}
return (output);
}
else
return -1;
}
public static int MoveLeft(int cur,int moveTimes,int total )
{
int Pos = (cur+moveTimes)%total;
return Pos==0 ? total : Pos;
}
public static int MoveRight(int cur,int moveTimes,int total )
{
int Pos=(total+cur-moveTimes)%total;
return Pos==0 ? total : Pos;
}}
Find the greatest common divisor (GCD) of N and L. Then the ball comes back to person #1 after N/GCD(N,L) passing. So the answer should be (M-1)*N/GCD(N,L).
- skw_kevin March 28, 2016