Amazon Interview Question Software Developers
Country: India
Interview Type: Phone Interview
function worstInfectedPerson(array, d) {
// assume sorted
let infectables = [];
let left = 0;
let right = 0;
for (let i = 0; i < array.length; ++i) {
let current = array[i];
while (array[left] < current - d) {
++left;
}
while (array[right] <= current + d) {
++right;
}
infectables[i] = { infected: right - left, index: i };
}
return infectables.sort( (a,b) => b.infected - a.infected )[0].index;
}
import java.util.ArrayList;
import java.util.Stack;
public class T1 {
private static int totalNum = 5;
private static int distance = 5;
private static int[] position = { 1, 3, 5, 9, 14 };
public static void main(String[] args) {
ArrayList<ArrayList<Integer>> spreading = new ArrayList<>();
for (int i = 0; i < totalNum; i++) {
ArrayList<Integer> inside = new ArrayList<>();
for (int j = 0; j < totalNum; j++) {
if (i == j) {
continue;
} else {
if (position[i] < position[j])
if (position[i] >= (position[j] - distance)) {
inside.add(position[j]);
}
if (position[i] > position[j])
if (position[i] <= (position[j] + distance)) {
inside.add(position[j]);
}
}
} // end for j
spreading.add(inside);
} // end for i
// result
System.out.println(spreading);
// Analyze the result
int max = 0;
int min = totalNum;
Stack<Integer> minSpreading = new Stack<>();
Stack<Integer> maxSpreading = new Stack<>();
int positionCount = 0;
for (ArrayList<Integer> inside : spreading) {
positionCount++;
int count = 0;
for (Integer getInside : inside) {
count++;
}
if (count > max) {
max = count;
maxSpreading.add(positionCount);
}
if (count < min) {
min = count;
minSpreading.add(positionCount);
}
}
System.out.println("max : " + maxSpreading.peek());
System.out.println("min : " + minSpreading.peek());
}
}
In python:
def spread(N,d,position):
if len(position)<2:
return len(position),len(position)
distances = []
first = position[0]
distance = 1
for i,second in enumerate(position[1:]):
print("OH:",first,second,distances)
if abs(second-first)<=d:
distance+=1
else:
distances.append(distance)
distance = 1
if i==len(position[1:])-1:
distances.append(distance)
first = second
return min(distances),max(distances)
def spread(N,d,position):
if len(position)<2:
return len(position),len(position)
distances = []
first = position[0]
distance = 1
for i,second in enumerate(position[1:]):
print("OH:",first,second,distances)
if abs(second-first)<=d:
distance+=1
else:
distances.append(distance)
distance = 1
if i==len(position[1:])-1:
distances.append(distance)
first = second
return min(distances),max(distances)
package problems;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
public class VirusInfection
{
private static int totalNum = 5;
private static int distance = 5;
private static int[] arr = { 1, 3, 5, 9, 14 };
public static void main(String[] args)
{
Map map = new HashMap();
for (int i = 0; i < totalNum; i++)
{
int count = 0;
for (int j = 0; j < totalNum; j++)
{
if (i == j)
{
continue;
} else
{
if (6 > Math.abs(arr[i] - arr[j]))
{
count++;
map.put(arr[i], count);
}
}
} // end for j
} // end for i
int min = Integer.MAX_VALUE, min_pos = 0;
int max = 0, max_pos = 0;
Set set = map.entrySet();
Iterator itr = set.iterator();
while (itr.hasNext())
{
Entry entry = (Entry) itr.next();
int pos = (int) entry.getKey();
int count = (int) entry.getValue();
if (count < min)
{
min = count;
min_pos = pos;
}
else if (count > max)
{
max = count;
max_pos = pos;
}
}
System.out.println("best case when infected person is at position " + min_pos + " : will infect :" + min);
System.out.println("worst case when infected person is at position " + max_pos + " : will infect :" + max);
}
}
public class VirusSpreadInPark {
public static void main(String[] args) {
//
final int d = 5;
final int[] pos = {1,3,5,9,14};
//{1,3,5,9,14}
// spreads with d = 5
//{2,2,3,2,1}
final int n = pos.length;
int[] res = new int[n];
for(int i = 0; i < n; i++) {
int count = 0;
for(int j = 0; j < n; j++) {
if(i == j) {
continue;
}
if(Math.abs(pos[j] - pos[i]) <= d) {
count++;
}
}
res[i] = count;
}
int maxId = 0, minId = 0, max = res[0], min = res[0];
for(int x = 0; x < n; x++) {
if(res[x] > max) {
max = res[x];
maxId = x;
}
if(res[x] < min) {
min = res[x];
minId = x;
}
}
System.out.println("\nMax Position: " + pos[maxId]);
System.out.println("Min Position: " + pos[minId]);
}
}
public class VirusSpreadInPark {
public static void main(String[] args) {
//
final int d = 5;
final int[] pos = {1,3,5,9,14};
//{1,3,5,9,14}
// spreads with d = 5
//{2,2,3,2,1}
final int n = pos.length;
int[] res = new int[n];
for(int i = 0; i < n; i++) {
int count = 0;
for(int j = 0; j < n; j++) {
if(i == j) {
continue;
}
if(Math.abs(pos[j] - pos[i]) <= d) {
count++;
}
}
res[i] = count;
}
int maxId = 0, minId = 0, max = res[0], min = res[0];
for(int x = 0; x < n; x++) {
if(res[x] > max) {
max = res[x];
maxId = x;
}
if(res[x] < min) {
min = res[x];
minId = x;
}
}
System.out.println("\nMax Position: " + pos[maxId]);
System.out.println("Min Position: " + pos[minId]);
}
}
Here is my solution in JavaScript:
{{function CalcWorstBest(PD, n, d) {
var minC=null, maxC=null;
var suspectC;
var suspectList = [];
for (i=0; i<n; i++) {
let cntC = 0;
suspectC = i+1;
for (j=0; j<n; j++) {
if (i!=j) {
if (Math.abs(PD[i] - PD[j]) <= d) {
cntC++;
}
}
}
suspectList.push({suspectC, cntC});
if (minC === null || cntC <= minC) {
minC = cntC;
}
if (maxC === null || cntC >= maxC) {
maxC = cntC;
}
}
return {listBest: (suspectList.filter((el)=>el.cntC==minC)),
listWorst: (suspectList.filter((el)=>el.cntC==maxC))
};
}
console.log(CalcWorstBest([1,3,5,9,10], 5, 5));}}
function CalcWorstBest(PD, n, d) {
var minC=null, maxC=null;
var suspectC;
var suspectList = [];
for (i=0; i<n; i++) {
let cntC = 0;
suspectC = i+1;
for (j=0; j<n; j++) {
if (i!=j) {
if (Math.abs(PD[i] - PD[j]) <= d) {
cntC++;
}
}
}
suspectList.push({suspectC, cntC});
if (minC === null || cntC <= minC) {
minC = cntC;
}
if (maxC === null || cntC >= maxC) {
maxC = cntC;
}
}
return {listBest: (suspectList.filter((el)=>el.cntC==minC)),
listWorst: (suspectList.filter((el)=>el.cntC==maxC))
};
}
console.log(CalcWorstBest([1,3,5,9,10], 5, 5));
public int[] getSpread(int[] inp, int d) {
int n = inp.length;
int[] spread = new int[n];
Arrays.fill(spread, 1);
traverseRight(inp, d, spread);
traverseLeft(inp, d, spread);
int bestCase = Arrays.stream(spread).min().getAsInt();
int worstCase = Arrays.stream(spread).max().getAsInt();
return new int[] { bestCase, worstCase };
}
private void traverseLeft(int[] inp, int d, int[] spread) {
int n = spread.length;
int p1 = n - 1;
int p2 = n - 1;
while (p2 >= 0) {
if (inp[p1] - inp[p2] > d) {
spread[p1] += p1 - p2 + 1;
p1--;
} else {
p2--;
}
if (p1 < p2) {
p2 = p1;
}
}
}
private void traverseRight(int[] inp, int d, int[] spread) {
int n = spread.length;
int p1 = 0;
int p2 = 0;
while (p2 < n) {
if (inp[p2 + 1] - inp[p1] > d) {
spread[p1] = p2 - p1 + 1;
p1++;
} else {
p2++;
}
if (p1 > p2) {
p2 = p1;
}
}
}
public int[] getSpread(int[] inp, int d) {
int n = inp.length;
int[] spread = new int[n];
Arrays.fill(spread, 1);
traverseRight(inp, d, spread);
traverseLeft(inp, d, spread);
int bestCase = Arrays.stream(spread).min().getAsInt();
int worstCase = Arrays.stream(spread).max().getAsInt();
return new int[] { bestCase, worstCase };
}
private void traverseLeft(int[] inp, int d, int[] spread) {
int n = spread.length;
int p1 = n - 1;
int p2 = n - 1;
while (p2 >= 0) {
if (inp[p1] - inp[p2] > d) {
spread[p1] += p1 - p2 + 1;
p1--;
} else {
p2--;
}
if (p1 < p2) {
p2 = p1;
}
}
}
private void traverseRight(int[] inp, int d, int[] spread) {
int n = spread.length;
int p1 = 0;
int p2 = 0;
while (p2 < n) {
if (inp[p2 + 1] - inp[p1] > d) {
spread[p1] = p2 - p1 + 1;
p1++;
} else {
p2++;
}
if (p1 > p2) {
p2 = p1;
}
}
}
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
int n,d,i;
scanf("%d",&n);
int A[n];
int B[n-1];
memset(B,0,n-1);
for(i=0;i<n;i++)
scanf("%d",&A[i]);
scanf("%d",&d);
for(i=0;i<n-1;i++)
{
B[i]=A[i+1]-A[i];
}
int min=B[0],max=B[0];
for(i=1;i<n-1;i++)
{
if(B[i]<min)
min=B[i];
if(B[i]>max)
max=B[i];
}
printf("Best case:%d Worst Case:%d",min-1,max);
return 0;
}
import java.util.HashMap;
import java.util.Map;
public class Virusspread {
public static void main (String args[])
{
int arr[] = {1,3,5,9,14};
int distance = 5;
Map<Integer,Integer> hm = new HashMap<Integer,Integer>();
int tempppl = 0;
int tempppl1 = 0;
int worstcase =0;
int bestcase =0;
for (int i= 0; i<arr.length;i++)
{
int min = arr[i]-distance;
int max = arr[i]+distance;
int pplaffected = 0;
for (int j=0; j<arr.length;j++)
{
if (i != j)
{
if (arr[j] > max-distance && arr[j] < max )
{
pplaffected += 1;
}
if(arr[j] > min && arr[j] < min+distance)
{
pplaffected += 1;
}
}
}
if (i==0) { tempppl = pplaffected; tempppl1 = pplaffected; }
if (pplaffected > tempppl )
{
worstcase = arr[i];
tempppl = pplaffected;
}
if (pplaffected < tempppl1)
{
bestcase = arr[i];
tempppl1 = pplaffected;
}
}
System.out.println("bestcase:: at position::"+ bestcase +" No of persons impacted::"+ tempppl1 );
System.out.println("worstcase:: at position::"+ worstcase +" No of persons impacted::"+ tempppl );
}
}
import java.util.HashMap;
import java.util.Map;
public class Virusspread {
public static void main (String args[])
{
int arr[] = {1,3,5,9,14};
int distance = 5;
Map<Integer,Integer> hm = new HashMap<Integer,Integer>();
int tempppl = 0;
int tempppl1 = 0;
int worstcase =0;
int bestcase =0;
for (int i= 0; i<arr.length;i++)
{
int min = arr[i]-distance;
int max = arr[i]+distance;
int pplaffected = 0;
for (int j=0; j<arr.length;j++)
{
if (i != j)
{
if (arr[j] > max-distance && arr[j] < max )
{
pplaffected += 1;
}
if(arr[j] > min && arr[j] < min+distance)
{
pplaffected += 1;
}
}
}
if (i==0) { tempppl = pplaffected; tempppl1 = pplaffected; }
if (pplaffected > tempppl )
{
worstcase = arr[i];
tempppl = pplaffected;
}
if (pplaffected < tempppl1)
{
bestcase = arr[i];
tempppl1 = pplaffected;
}
}
System.out.println("bestcase:: at position::"+ bestcase +" No of persons impacted::"+ tempppl1 );
System.out.println("worstcase:: at position::"+ worstcase +" No of persons impacted::"+ tempppl );
}
}
Goal :
based on distance between people N in positions L=[i,j,k..]
condition = distance < (postion[person1] - person[person2]) they are infected
if one of them get infect, what the spread score, position
best case = minimum spread score == a few or none of people will be infected
worse case = maxim spread score == a lot of people will be infected
algorithm :
loop on the list :
i=1 # we took first item and compare it with all the item in list
loop on the list : # nested loop
j=1
#now le'ts calc the distance, save the results if our condition is True
if list[i]-list[j]< distance and I is not equal to J:
Item I will infect item J, so let's increase score
score+=1
#after nest loop finishes, let's save item I and its score
results[i]=score
# then find min and max of results
def spread(N,L,d):
#check number of ppl
if N >0 :
#dic which will hold item, score
results={}
#first loop which will take first item in list and compare it with all the rest
for i in range(N):
#this item will have a score which should be saved at the end of each iteration
score=0
#second loop which iterate on all the list
for j in range(N):
# here we compare position of item I with J less or equal distance
# then item I will infect Item J
# since we iterate on same list, we ignore case I=J=infect itself
if abs(L[i]-L[j])<= d and j!=i:
score+=1
#we quit J loop, we save the score and item I in our dictionary
results[i]=score
print(results)
# Now, lets find maximun and minum score
#tuplecase=(item,score)
#bestcase score should be initialized with maximin Value ==> N, all ppl get infect
#so we can change it later while find minumum
bestcase=(0,N)
worsecase=(0,0)
#finding minum and maximum score, then updating our tuples
for key,value in results.items():
if (value>worsecase[1]):
worsecase=(key,value)
if (value<bestcase[1]):
bestcase=(key,value)
print("Best case : person in position ",bestcase[0]," get infect,","spread score: ",bestcase[1])
print("Worse case : person in position",worsecase[0]," get infect,","spread score: ",worsecase[1])
return False
spread(5,[1,3,5,9,14],5)
here is my solution in c++"
- jais October 16, 2020void solution(int n, vector<int> positions, int d) { vector<int> spreads; for(int i = 0; i < n; i++) { int spread = 0; for(int j = 0; j < n; j++) { if(i != j ) { if(abs(positions[j] - positions[i]) <= d) { spread++; } } } res.push_back(spread); } int minSpread = n; int maxSpread = 0; int minSpreadIndex = 0; int maxSpreadIndex = 0; for(int i = 0; i < n; i++) { if(minSpread < res[i]) { minSpread = res[i]; minSpreadIndex = i; } if(maxSpread > res[i]) { maxSpread = res[i]; maxSpreadIndex = i; } } cout << "max spread happened when person at position" << positions[maxSpreadIndex] << "get contaminated" << endl; cout << "min spread happened when person at position" << positions[minSpreadIndex] << "get contaminated" << endl; }