Amazon Interview Question
Software Engineer in TestsCountry: United States
Interview Type: Phone Interview
{
naturalNumbersArray = []
Jarray = []
for i in range(1,101):
naturalNumbersArray.append(i)
ip = input().strip().split(" ")
for i in ip:
if i :
Jarray.append(int(i))
number = input()
number = int(number)
currIndex = number-1
for i in Jarray:
shiftIndex = (currIndex+1)%i * (currIndex - currIndex/i)
if shiftIndex == 0:
print("Will die while at index",currIndex+1)
exit(0)
else:
if shiftIndex <= currIndex:
currIndex = shiftIndex
print(number,"will survive")
}
If the element in Jarray evenly divides the current index value then it dies instantly else it gets shifted (currIndex - currIndex/i) times forward in the naturalNumbersArray i.e it shifts its position towards right and assigning new index value to it.
naturalNumbersArray = []
Jarray = []
for i in range(1,101):
naturalNumbersArray.append(i)
ip = input().strip().split(" ")
for i in ip:
if i :
Jarray.append(int(i))
number = input()
number = int(number)
currIndex = number-1
for i in Jarray:
shiftIndex = (currIndex+1)%i * (currIndex - currIndex/i)
if shiftIndex == 0:
print("Will die while at index",currIndex+1)
exit(0)
else:
if shiftIndex <= currIndex:
currIndex = shiftIndex
print(number,"will survive")
If an element in Jarray divides currIndex evenly naturalNumbersArray element's index dies instantly else it shifts its position (currIndex-currIndex/i) times i.e shifting position towards right and if possible finally it survives, if no element in the Jarray is able to divide its position evenly.
In ZoomBA:
// returns -1 if does not go bye bye,
// else returns the index
will_bye_bye( n , J ){
// one liner in ZoomBA
r = [1:n+1]
for ( i = 0 ; i < size(J) ; i+=1 ){
// select those whose index is divisible by the item index
r = select ( r ) :: { J[i] /? ($.index + 1) }
if( empty(r) || r[-1] != n ){ return i }
}
return -1
}
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
vector <int> numbers(1e6);
vector <int> number_indces(1e6);
int divisor [] = {2,3,4};
// you can sort the divisor and eliminate the multiplier of small divisors
vector <int> div (divisor,divisor+3);
for(int i = 0 ; i < 1e6;i++){
numbers[i] = i;
number_indces[i] = i;
}
cin >> n;
bool die = false;
int divIdx = -1;
for(int i = 0 ; i < div.size();i++){
if(n%div[i] == 0){
die = true;
divIdx = i;
break;
}
}
if(!die){
cout <<"it will survive" <<endl;
}else{
for(int i = 0 ; i <= divIdx;i++){
int idx = 0;
for(int j = 0 ; j < numbers.size();j++){
if(i == divIdx && numbers[j] == n){
cout << "The number will die in index = "<<number_indces[j] << endl;
break;
}
if(number_indces[j] != -1){
if(numbers[j]%div[i] == 0){
number_indces[j] = -1;
}else{
number_indces[j] = idx++;
}
}
}
}
}
return 0;
}
public class Survival {
public static void main(String[] args) {
int a[] = {1,2,3,4,5,6,7,8,9,10};
int b[] = {2,3,4};
System.out.println(isSurvive(a,b,9));
}
public static int isSurvive(int a[], int b[], int n){
int pos = findPos(a,n);
int curpos = pos;
for (int i=0;i<b.length;i++){
if(curpos%b[i]==0){
System.out.println("It will die at pos: "+(curpos-1));
return curpos-1;
}
else{
int temp;
temp = curpos/b[i];
curpos = curpos - temp;
}
}
System.out.println("It Survived");
return -1;
}
public static int findPos(int a[],int n){
HashMap<Integer,Integer> hm = new HashMap<Integer,Integer>();
for(int i=0;i<a.length;i++){
hm.put(a[i],i);
}
return hm.get(n) + 1;
}
}
static void Main(string[] args)
{
var n = 6;
var J = new[]{2, 3, 4};
var a = Enumerable.Range(1, 10).ToList();
bool willDie = false;
var nIndex = a.IndexOf(n) + 1;
if (nIndex == 0)
{
Console.WriteLine(true);
return;
}
foreach (var jump in J)
{
if (nIndex % jump == 0)
{
willDie = true;
break;
}
nIndex -= nIndex/jump;
}
Console.WriteLine(willDie);
}
First we need find the index of the natural number in the stream. In the given example, the index of n is n-1.
/**
*
* @param initialIndex: the index of some element in the original series of natural numbers.
* @param operations: int array to hold the operation.
* @param indexOfOperation: index of the target operation.
* @param indexOfCurrentOperation: the current operation in recursive computation.
* The initial value is 0; final value is indexOfOperation;
* this value increases by 1 in each recursion.
* @return
*/
public boolean isAlive(int initialIndex, int[] operations, int indexOfTargetOperation, int indexOfCurrentOperation){
if(indexOfCurrentOperation > indexOfTargetOperation) return true;
int operation = operations[indexOfCurrentOperation];
if((initialIndex+1)%operation == 0){
System.out.println("die in operation: "+operation);
return false;
}
//index of the surviving element in new array after the operation
initialIndex = initialIndex-(initialIndex+1)/operation;
indexOfCurrentOperation++;
return isAlive(initialIndex, operations, indexOfTargetOperation, indexOfCurrentOperation);
}
def Remove():
i = 0
data = []
while i < 1111:
data.append(i+1)
i = i + 1
j = [2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40]
for each in j:
if each - 1 > len(data):
print ("out of range at: ", each)
index = each - 1
while index < len(data):
data.pop(index)
index = index + each - 1
print data
public int isSurvied(int[] arr, int[] j)
{
if (arr == null || arr.Length == 0)
return -1;
if (j == null || j.Length == 0)
return arr.Length - 1;
int count = arr.Length;
for(int i = 0; i < j.Length; i++)
{
count = count/j[i] + count %j[i];
}
if (count > 0)
return count - 1;
else
return -1;
}
public int isSurvied(int[] arr, int[] j)
{
if (arr == null || arr.Length == 0)
return -1;
if (j == null || j.Length == 0)
return arr.Length - 1;
int count = arr.Length;
for(int i = 0; i < j.Length; i++)
{
count = count/j[i] + count %j[i];
}
if (count > 0)
return count - 1;
else
return -1;
}
public static int isSurvied(int[] arr, int[] j)
{
if (arr == null || arr.Length == 0)
return -1;
if (j == null || j.Length == 0)
return arr.Length - 1;
int count = arr.Length;
for(int i = 0; i < j.Length; i++)
{
count = count/j[i] + count %j[i];
}
if (count > 0)
return count - 1;
else
return -1;
}
public int isSurvied(int[] arr, int[] j)
{
if (arr == null || arr.Length == 0)
return -1;
if (j == null || j.Length == 0)
return arr.Length - 1;
int count = arr.Length;
for(int i = 0; i < j.Length; i++)
{
count = count/j[i] + count %j[i];
}
if (count > 0)
return count - 1;
else
return -1;
}
public static int isSurvied(int[] arr, int[] j)
{
if (arr == null || arr.Length == 0)
return -1;
if (j == null || j.Length == 0)
return arr.Length - 1;
int count = arr.Length;
for(int i = 0; i < j.Length; i++)
{
count = count/j[i] + count %j[i];
}
if (count > 0)
return count - 1;
else
return -1;
}
public static int isSurvied(int[] arr, int[] j)
{
if (arr == null || arr.Length == 0)
return -1;
if (j == null || j.Length == 0)
return arr.Length - 1;
int count = arr.Length;
for(int i = 0; i < j.Length; i++)
{
count = count/j[i] + count %j[i];
}
if (count > 0)
return count - 1;
else
return -1;
}
The question is not clear. What number the j array starts from ? always 2 or anything else. Like if it has 1 on some index then what?. If j has numbers 2 or greater than two then I have very simple answer.
public int countDie(int[] arr,int[] j,int[] result)
{
int count = arr.length;
for(int i=0;i<j.length;i++)
{
count = count/j[i];
result[0] = count;
result[1] = i;
result[2] = i-1;
if(count == 0)
{
return i;
}
}
return 0;
}
where result[0] is the number of elements survive, the result[1] has the position where it will die and the result[2] has the position where last it survived. The return is the dieng position while return 0 means will survive.
The question is not clear. What are the possible operations in j? if it contained 1 then which element to remove. ? What is the function of n?. What I understood is if j has 2 or greater numbers then this is very simple.
public int countDie(int[] arr,int[] j,int[] result)
{
int count = arr.length;
for(int i=0;i<j.length;i++)
{
count = count/j[i];
result[0] = count;
result[1] = i;
result[2] = i-1;
if(count == 0)
{
return i;
}
}
return 0;
}
where return 0 means survived, return i means died at ith position, result[0] means remaining elements count. result[1] meains position at which died, result[i] means position at which last survived
If Jth element evenly divides the Nth element index then it died.
- rohit December 09, 2016else the Nth element gets displaced by (CurrentIndex/Jth element)
Ex:
nums = 1,2,3,4,5,6,7,8,9,10
j = 2,3,4
n = 9
1st iter: j=2
1,3,5,7,9
9th index gets displaced by (9-9/2)
2nd iter: j=3
1,3,7,9
9th index gets displaced by (9-5/2)
3rd iter: j=4
9th index evenly divides 4 - So it died