## ADP Interview Question for abcs

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
0
of 0 vote

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).

Comment hidden because of low score. Click to expand.
0
of 0 vote

skw_kevin
skw_kevin-
can you explain why GCD is used? Also, when I try to evaluate your approach with the answer of 10 it does not work.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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));
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#!/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] );

for (my \$i = 0; \$i <= \$N; \$i++) {
}
my \$count_of_passes = 0;
my \$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);
}
\$currient = \$new_pos;
\$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];
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#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 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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

I question is copied from Code Gladiator coding context
Please try it on own because next round is tough.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}
}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}
}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);

}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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);

}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Note there are no restrictions on value of L. It could be positive, negative or much greater than N. I believe solutions in this post haven't considered it. use module to solve.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````<?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);
?>``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;``````

}}

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.