Below is the question asked in one coding interview round, I have given the code for 2 possible scenarios which I found in that question which was not cleared during the interview, I had with AthenaHealth. Please do try on different cases, as I have not tested it much. Will appreciate if you can inform me about the failing case here, so that I correct it & share on GitHub soon.
Scenario 1 : You are at position which has value 0 and you can use 'N' number of tokens to travel to other position.
Suppose you have an array or arraylist of tokens i.e. t such that value of each token will t(i) or t.get(i).
So this array is like the options you have for the tokens having the mentioned values.
And you can reach to position P from your position '0' if P = 0 + t(i). So you have to find the answer if it is possible
to get any combination of the given tokens but that combination should not have tokens more than 'N'.
Example below - In first row you will get 2 numbers 1st will be the number of tokens you can select i.e. 'N'
2nd number is the number of destinations for which you find the answers.
Second row will have the list of different kind of token options available to you to select from.
Then each row will have the destination value for which you need to find the answer.
Below explanation is mentioned against each question -
3 7
3 4 7
10 (Explanation : 3 + 7 = 10, 2 tokens will be fine which is still less than given limit of 3, so it is YES)
9 (Explanation : 3 + 3 +3 = 9, 3 tokens will work which is equal to the limit given, so it is YES)
11 (Explanation : 4 + 7 = 11, 2 tokens will be fine which is still less than given limit of 3, so it is YES))
13 (Explanation : 3 + 3 + 7 = 13, 3 tokens will work which is equal to the limit given, so it is YES)
2 (Explanation : No token has this value & none is maller than this also, so answer is NO)
15 (Explanation : 4 + 4 + 7 = 15, and the limit is 3 & here also 3 tokens are used, though it is possible with other available token values but it will breach the limit, so it is YES here)
5 (Explanation : It is not possible in any way with the given token values, so it is NO)
Scenario 2 : You are at position which has value 0 and you have got 'N' number of tokens to travel to other position.
Suppose you have an array or arraylist of tokens i.e. t such that value of each token will t(i) or t.get(i).
And you can reach to position P from your position '0' if P = 0 + t(i). So you have to find if you can reach the given destination
with the given tokens. Unlike scenario 1, here each token value can be used only once and the given value of 'N' must be equal to the provided tokens in second row, else it will be considered invalid input.
Example below - In first row you will get 2 numbers 1st will be the number of tokens you can use i.e. 'N'
2nd number is the number of destinations for which you find the answers.
Second row will have the list of different kind of token options available to you to select from.
Then each row will have the destination value for which you need to find the answer.
Below explanation is mentioned against each question -
3 5
3 4 7
10 (Explanation : 3 + 7 = 10, 2 tokens will be fine which is still less than given limit of 3, so it is YES))
9 (Explanation : This value cannot be derived using the given token values, so it is NO)
11 (Explanation : 4 + 7 = 11, 2 tokens will be fine which is still less than given limit of 3, so it is YES))
13 (Explanation : This value cannot be derived using the given token values, so it is NO)
14 (Explanation : 3 + 4 + 7 = 14, 3 tokens will work which is equal to the limit given, so it is YES)
Below is the code written for both the scenarios given above & will be sharing it on the GitHub mentioned on home page soon-
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
/**
* Working solution for 2 scenarios
* @author nitin
*
*/
public class Sol2 {
public static void main(String args[]) throws Exception {
Scanner scanner = new Scanner(System.in);
String first = scanner.nextLine();
String[] vals = first.split(" ");
if(vals.length != 2) {
System.out.println("Wrong number of inputs!!!!");
System.exit(1);
}
int toks = Integer.parseInt(vals[0]);
int Qs = Integer.parseInt(vals[1]);
String sec = scanner.nextLine();
String[] tok = sec.split(" ");
// This check block is for scenario 2
/*if(toks != tok.length) {
System.out.println("Wrong number of input tokens!!!!");
System.exit(1);
}*/
ArrayList<Integer> tokens = new ArrayList<>();
for(String t : tok) {
tokens.add(Integer.parseInt(t));
}
Collections.sort(tokens);
ArrayList<Integer> queries = new ArrayList<>();
for(int q = 0; q < Qs; q++) {
queries.add(scanner.nextInt());
}
scanner.close();
for(int q : queries) {
System.out.println(resultsScenario2(tokens, q, toks));
}
}
/**
* You are at position which has value 0 and you can use 'N' number of tokens to travel to other position.
Suppose you have an array or arraylist of tokens i.e. t such that value of each token will t(i) or t.get(i).
So this array is like the options you have for the tokens having the mentioned values.
And you can reach to position P from your position '0' if P = 0 + t(i). So you have to find the answer if it is possible
to get any combination of the given tokens but that combination should not have tokens more than 'N'.
* @param tokens
* @param place
* @param count
* @return
*/
public static String resultsScenario1(ArrayList<Integer> tokens, int place, int count) {
String result = "NO";
int temp = place;
int tempCount = count;
int cur = count;
if(place < tokens.get(0))
return "NO";
for(int i : tokens) {
if(temp/i <= tempCount && temp%i == 0)
return "YES";
else if(temp > i) {
int temp1 = temp;
while(cur > 0) {
cur--;
temp1 = temp - cur * i;
if(temp1 >= tokens.get(0) && (Collections.binarySearch(tokens, (temp1*(count-cur))) >= 0 || (cur == 1 && Collections.binarySearch(tokens, temp1) >= 0)))
return "YES";
}
cur = count;
}
}
return result;
}
/**
* You are at position which has value 0 and you have got 'N' number of tokens to travel to other position.
Suppose you have an array or arraylist of tokens i.e. t such that value of each token will t(i) or t.get(i).
And you can reach to position P from your position '0' if P = 0 + t(i). So you have to find if you can reach the given destination
with the given tokens. Unlike scenario 1, here each token value can be used only once and the given value of 'N' must be equal to the
provided tokens in second row, else it will be considered invalid input.
* @param tokens
* @param place
* @param count
* @return
*/
public static String resultsScenario2(ArrayList<Integer> tokens, int place, int count) {
int temp = place;
int pos = 0;
ArrayList<Integer> copyList = new ArrayList<>(tokens);
if(place < tokens.get(0))
return "NO";
for(int i : tokens) {
temp = temp - i;
int cur = count - 1;
copyList.remove(pos);
if(cur > 0 && Collections.binarySearch(copyList, temp) >= 0)
return "YES";
if(temp < copyList.get(0) && temp > 0)
return "NO";
if(resultsScenario2(copyList, temp, cur).equals("YES"))
return "YES";
else {
temp = place;
}
pos++;
copyList = new ArrayList<>(tokens);
}
return "NO";
}
}
Suppose you have an array or arraylist of tokens i.e. t such that value of each token will t(i) or t.get(i).
So this array is like the options you have for the tokens having the mentioned values.
And you can reach to position P from your position '0' if P = 0 + t(i). So you have to find the answer if it is possible
to get any combination of the given tokens but that combination should not have tokens more than 'N'.
Example below - In first row you will get 2 numbers 1st will be the number of tokens you can select i.e. 'N'
2nd number is the number of destinations for which you find the answers.
Second row will have the list of different kind of token options available to you to select from.
Then each row will have the destination value for which you need to find the answer.
Below explanation is mentioned against each question -
3 7
3 4 7
10 (Explanation : 3 + 7 = 10, 2 tokens will be fine which is still less than given limit of 3, so it is YES)
9 (Explanation : 3 + 3 +3 = 9, 3 tokens will work which is equal to the limit given, so it is YES)
11 (Explanation : 4 + 7 = 11, 2 tokens will be fine which is still less than given limit of 3, so it is YES))
13 (Explanation : 3 + 3 + 7 = 13, 3 tokens will work which is equal to the limit given, so it is YES)
2 (Explanation : No token has this value & none is maller than this also, so answer is NO)
15 (Explanation : 4 + 4 + 7 = 15, and the limit is 3 & here also 3 tokens are used, though it is possible with other available token values but it will breach the limit, so it is YES here)
5 (Explanation : It is not possible in any way with the given token values, so it is NO)
Scenario 2 : You are at position which has value 0 and you have got 'N' number of tokens to travel to other position.
Suppose you have an array or arraylist of tokens i.e. t such that value of each token will t(i) or t.get(i).
And you can reach to position P from your position '0' if P = 0 + t(i). So you have to find if you can reach the given destination
with the given tokens. Unlike scenario 1, here each token value can be used only once and the given value of 'N' must be equal to the provided tokens in second row, else it will be considered invalid input.
Example below - In first row you will get 2 numbers 1st will be the number of tokens you can use i.e. 'N'
2nd number is the number of destinations for which you find the answers.
Second row will have the list of different kind of token options available to you to select from.
Then each row will have the destination value for which you need to find the answer.
Below explanation is mentioned against each question -
3 5
3 4 7
10 (Explanation : 3 + 7 = 10, 2 tokens will be fine which is still less than given limit of 3, so it is YES))
9 (Explanation : This value cannot be derived using the given token values, so it is NO)
11 (Explanation : 4 + 7 = 11, 2 tokens will be fine which is still less than given limit of 3, so it is YES))
13 (Explanation : This value cannot be derived using the given token values, so it is NO)
14 (Explanation : 3 + 4 + 7 = 14, 3 tokens will work which is equal to the limit given, so it is YES)
Below is the code written for both the scenarios given above & will be sharing it on the GitHub mentioned on home page soon-
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
/**
* Working solution for 2 scenarios
* @author nitin
*
*/
public class Sol2 {
public static void main(String args[]) throws Exception {
Scanner scanner = new Scanner(System.in);
String first = scanner.nextLine();
String[] vals = first.split(" ");
if(vals.length != 2) {
System.out.println("Wrong number of inputs!!!!");
System.exit(1);
}
int toks = Integer.parseInt(vals[0]);
int Qs = Integer.parseInt(vals[1]);
String sec = scanner.nextLine();
String[] tok = sec.split(" ");
// This check block is for scenario 2
/*if(toks != tok.length) {
System.out.println("Wrong number of input tokens!!!!");
System.exit(1);
}*/
ArrayList<Integer> tokens = new ArrayList<>();
for(String t : tok) {
tokens.add(Integer.parseInt(t));
}
Collections.sort(tokens);
ArrayList<Integer> queries = new ArrayList<>();
for(int q = 0; q < Qs; q++) {
queries.add(scanner.nextInt());
}
scanner.close();
for(int q : queries) {
System.out.println(resultsScenario2(tokens, q, toks));
}
}
/**
* You are at position which has value 0 and you can use 'N' number of tokens to travel to other position.
Suppose you have an array or arraylist of tokens i.e. t such that value of each token will t(i) or t.get(i).
So this array is like the options you have for the tokens having the mentioned values.
And you can reach to position P from your position '0' if P = 0 + t(i). So you have to find the answer if it is possible
to get any combination of the given tokens but that combination should not have tokens more than 'N'.
* @param tokens
* @param place
* @param count
* @return
*/
public static String resultsScenario1(ArrayList<Integer> tokens, int place, int count) {
String result = "NO";
int temp = place;
int tempCount = count;
int cur = count;
if(place < tokens.get(0))
return "NO";
for(int i : tokens) {
if(temp/i <= tempCount && temp%i == 0)
return "YES";
else if(temp > i) {
int temp1 = temp;
while(cur > 0) {
cur--;
temp1 = temp - cur * i;
if(temp1 >= tokens.get(0) && (Collections.binarySearch(tokens, (temp1*(count-cur))) >= 0 || (cur == 1 && Collections.binarySearch(tokens, temp1) >= 0)))
return "YES";
}
cur = count;
}
}
return result;
}
/**
* You are at position which has value 0 and you have got 'N' number of tokens to travel to other position.
Suppose you have an array or arraylist of tokens i.e. t such that value of each token will t(i) or t.get(i).
And you can reach to position P from your position '0' if P = 0 + t(i). So you have to find if you can reach the given destination
with the given tokens. Unlike scenario 1, here each token value can be used only once and the given value of 'N' must be equal to the
provided tokens in second row, else it will be considered invalid input.
* @param tokens
* @param place
* @param count
* @return
*/
public static String resultsScenario2(ArrayList<Integer> tokens, int place, int count) {
int temp = place;
int pos = 0;
ArrayList<Integer> copyList = new ArrayList<>(tokens);
if(place < tokens.get(0))
return "NO";
for(int i : tokens) {
temp = temp - i;
int cur = count - 1;
copyList.remove(pos);
if(cur > 0 && Collections.binarySearch(copyList, temp) >= 0)
return "YES";
if(temp < copyList.get(0) && temp > 0)
return "NO";
if(resultsScenario2(copyList, temp, cur).equals("YES"))
return "YES";
else {
temp = place;
}
pos++;
copyList = new ArrayList<>(tokens);
}
return "NO";
}
}
