## ADP Interview Question for Developer Program Engineers

Country: India
Interview Type: Written Test

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

import java.util.ArrayList;
import java.util.Scanner;

public class Question2 {
static int count;

public static void main(String[] args) {

Scanner s = new Scanner(System.in);

System.out.println("Enter No to check");

int num = Integer.parseInt(s.next());

ArrayList<Double> al = new ArrayList();

for (int x = 1; x <= num; x++) {

for (int y = 1; y <= num; y++) {

if (y > x) {
double result = (double) x / y;

if (al.contains(result)) {

} else {
System.out.println(x + "/" + y);

count++;
}

}
}

}
System.out.println(count);
}
}

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

``````def count(n) :
counter = 0
k = 2
while(k <= n) :
counter += euler_brute(k)
k += 1
return counter

def gcd(p,q) :
if q == 0 :
return p
else :
return gcd(q, p%q)

def euler_brute(l) :
phi = 0
for j in range(1, l+1) :
if gcd(j,l) == 1 :
phi += 1
return phi
#test
print(count(5))``````

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

import java.util.ArrayList;
import java.util.Scanner;
public class Question2 {
static int count;
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
System.out.println("Enter No to check");
int num = Integer.parseInt(s.next());
ArrayList<Double> al = new ArrayList();
for (int x = 1; x <= num; x++) {
for (int y = 1; y <= num; y++) {
if (y > x) {
double result = (double) x / y;
if (al.contains(result)) {
} else {
System.out.println(x + "/" + y);
count++;
}
}
}

}
System.out.println(count);
}
}

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

import java.util.ArrayList;
import java.util.Scanner;

public class Question2 {
static int count;
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
System.out.println("Enter No to check");
int num = Integer.parseInt(s.next());
ArrayList<Double> al = new ArrayList();
for (int x = 1; x <= num; x++) {
for (int y = 1; y <= num; y++) {
if (y > x) {
double result = (double) x / y;
if (al.contains(result)) {
} else {
System.out.println(x + "/" + y);
count++;
}
}
}}
System.out.println(count);
}}

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

import java.util.ArrayList;import java.util.Scanner;public class Question2{static int count;public static void main(String[] args){Scanner s = new Scanner(System.in);System.out.println("Enter No to check");int num = Integer.parseInt(s.next());ArrayList<Double> al = new ArrayList();for (int x = 1; x <= num; x++) {for (int y = 1; y <= num; y++) {if (y > x) {double result = (double) x / y;if (al.contains(result)) {} else { al.add(result);System.out.println(x + "/" + y);count++;}}}}System.out.println(count);}}

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

1.So basically the solution could be the recursive function, which takes N as argument, and then makes this N a divisior of a fraction. And then inside, there would be a while loop. And every repetition of the while loop would represent one fraction from 1/N to N-1/N {if N = 4 then 1/4;2/4;3/4}. During every repetition of while loop we check if the fraction is reducable. If its not reducable we increase the counter by one. Counter will track every valid fraction that we need to count. After while loop we return another call to our function with N reduced by one. The base case of recursion would occur when N == 1. In that case we return the counter. So for example if N = 4, then every repetition of while loop represent 1/4, 2/4, 3/4.

EDIT:<s> (But in cases when N is an odd number we don't need to run while loop because every fraction in that case would not be reducable, so in this case we would just increment our counter by current N -1. For example if N = 5 then 1/5, 2/5, 3/5, and 4/5 are all not reducable so we don't need to check that and just increment counter by N-1.)</s>.Unfortunately i was wrong in this one. The fraction is irreducible only if divisor is a prime number not odd number:(

2. To check if fraction is reducable we would need to check if Greatest Common Divisor of Dividend and Divisor of our fraction is bigger than 1. If it's bigger than a fraction is reducable and we do not count it.

3. In my code Greatest Common Divisior function is named NWD(int a, int b), divident of a fraction = l, and divisor = m.

``````public static int countFractions(int n, int counter)
{
if(n < 1)return -1; //error
if(n == 1)return counter;
int l = 1;//dividend
int m = n;//divisor
while(l < m)
{
if(!isReducable(l++, m))counter++;
}
return countFractions(n - 1, counter);
}

private static boolean isReducable(int l, int m)
{
return (NWD(m,l) > 1);
}
//NWD function is Just Greatest Common Divisor
private static int NWD(int a, int b)
{
if(b == 0)
{
return a;
}else
{
return NWD(b, a % b);
}
}``````

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

A fraction p/q is irreducible and smaller equal 1 if gcd(p,q)=1 and p < q.
Hence the number of irreducible functions of the form i/j where i < j equals phi(j)
where phi is the Euler's totient function, that is summing phi(j) over j= 2,..,n
(n being the input number) we get the desired result.
So:
1. First get prime numbers smaller or equal than input number n via Eratostene's sieve and store them in an array O(nlog(log(n))).

2. For every i=2,...,n compute Euler's totient function phi(i) via the product formula using the array of primes obtained in the previous step to find the prime factors of i.

3. Finally sum all phi(i).

``````from random import  randint
import time

def count_irr(n) :
primes = eratostene(n)
nr = 0
for i in range (2, n+1) :
k = 2
phi_i = i
check = i
#distinc_primes = []
while k <= i :
if primes[k-2] and i%k == 0 :
phi_i = phi_i*(1-1/k)
check = int(i/k)
#        distinc_primes.append(k)
elif primes[k-2] and k > check:
break
k += 1
nr += phi_i
return int(nr)

def eratostene(n):
num = [True]*(n-1)
i = 2
while(i*i <= n):
if num[i-2] == True :
j = i*i-2
while( j < n-1 ):
num[j] = False
j = j + i
i += 1
return num

#test with 12 random integers between 1 and 1000
a = []
for i in range(1, 13) :
a.append(randint(1, 1000))

c = []

start_time = time.time()
for k in a :
x = count_irr(k)
c.append(x)
t_0 = (-start_time + time.time())

# Typical execution time is below 0.5seconds
print('Execution time is %s seconds' % t_0)

for i in range(0, len(a)) :
print('n= %s and nr_irr_frac=%s' % (a[i], c[i]))``````

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

Unless I am missing something. Solution is very simple with O(n^2) runtime

``````def countUniqueFraction(n):

ufraction = set()
count = 0
for i in range(1,n+1):
for j in range(i+1, n+1):

return len(ufraction)``````

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

The key here is that for non reduce-able fraction the gcd(greatest common divisor) of the numerator and denominator must be 1 or in other words they must be co-prime.

``````int gcd(int a,int b){
if(b==0)
return a;
return gcd(b,a%b);
}
bool isNonReduceableFraction(int numerator,int denominator){
if(gcd(numerator,denominator)==1)
return true;
return false;
}``````

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

``````int getNumberofReducibleFractions(int n){
HashSet<Double> fractionSet = new HashSet<Double>();

if(n<=0){
return 0;
}

for(double i = 1; i<=n; i++){
double j = i;
while(j<=n){
double d = (double) (i/j);
if(d < 1.0){
}
j++;

}

}
return fractionSet.size();
}``````

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

``````int getNumberofReducibleFractions(int n){
HashSet<Double> fractionSet = new HashSet<Double>();

if(n<=0){
return 0;
}

for(double i = 1; i<=n; i++){
double j = i;
while(j<=n){
double d = (double) (i/j);
if(d < 1.0){
}
j++;

}

}
return fractionSet.size();``````

}

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

import java.util.ArrayList;

public class Test {
public static void main(String[] args) {
int n = 4, count = 0;
ArrayList<Double> temp = new ArrayList<>();
Double dou;
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j++) {
//System.out.println(i+"/"+j);
dou = ((double)i / (double)j);
if (dou != 1) {
if (!temp.contains(dou)) {
System.out.println(i+"/"+j);
count++;
}
}
}
}
System.out.println(count);
}
}

// 1/1, 1/2,1/3,1/4,2/2,2/3,2/4,3/3,3/4,4/4

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

import java.util.ArrayList;

public class Test {
public static void main(String[] args) {
int n = 4, count = 0;
ArrayList<Double> temp = new ArrayList<>();
Double dou;
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j++) {
//System.out.println(i+"/"+j);
dou = ((double)i / (double)j);
if (dou != 1) {
if (!temp.contains(dou)) {
System.out.println(i+"/"+j);
count++;
}
}
}
}
System.out.println(count);
}
}

// 1/1, 1/2,1/3,1/4,2/2,2/3,2/4,3/3,3/4,4/4

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

import java.util.ArrayList;
import java.util.Scanner;

public class Test {
public static void main(String[] args) {
int n, count = 0;

Scanner s = new Scanner(System.in);
System.out.println("Please Enter Fraction Nunber to check");
n = Integer.parseInt(s.next());
s.close();
//n = 4;
ArrayList<Double> temp = new ArrayList<>();
Double dou;
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j++) {
dou = ((double)i / (double)j);
if (dou != 1) {
if (!temp.contains(dou)) {
System.out.println(i+"/"+j);
count++;
}
}
}
}
System.out.println(count);
}
}

// 1/1, 1/2,1/3,1/4,2/2,2/3,2/4,3/3,3/4,4/4

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

Which one is correct code

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

import java.util.ArrayList;
import java.util.Scanner;

public class Test {
public static void main(String[] args) {
int n, count = 0;

Scanner s = new Scanner(System.in);
System.out.println("Please Enter Fraction Nunber to check");
n = Integer.parseInt(s.next());
s.close();
//n = 4;
ArrayList<Double> temp = new ArrayList<>();
Double dou;
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j++) {
dou = ((double)i / (double)j);
if (dou != 1) {
if (!temp.contains(dou)) {
System.out.println(i+"/"+j);
count++;
}
}
}
}
System.out.println(count);
}
}

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

import java.util.ArrayList;
import java.util.Scanner;

public class Test {
public static void main(String[] args) {
int n, count = 0;

Scanner s = new Scanner(System.in);
System.out.println("Please Enter Fraction Nunber to check");
n = Integer.parseInt(s.next());
s.close();
//n = 4;
ArrayList<Double> temp = new ArrayList<>();
Double dou;
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j++) {
dou = ((double)i / (double)j);
if (dou != 1) {
if (!temp.contains(dou)) {
System.out.println(i+"/"+j);
count++;
}
}
}
}
System.out.println(count);
}
}

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.