Nitin Agrawal
Contact -
  • Home
  • Interviews
    • Secret Receipe
    • InterviewFacts
    • Resume Thoughts
    • Daily Coding Problems
    • BigShyft
    • Companies
    • Interviews Theory
  • Programming Languages
    • Java Script >
      • Tutorials
      • Code Snippets
    • Reactive Programming >
      • Code Snippets
    • R
    • DataStructures >
      • LeetCode Problems >
        • Problem10
        • Problem300
      • AnagramsSet
    • Core Java >
      • Codility
      • Program Arguments OR VM arguments & Environment variables
      • Java Releases >
        • Java8 >
          • Performance
          • NasHorn
          • WordCount
          • Thoughts
        • Java9 >
          • ServiceLoaders
          • Lambdas
          • List Of Objects
          • Code Snippets
        • Java14 >
          • Teeing
          • Pattern
          • Semaphores
        • Java17 >
          • Switches
          • FunctionalStreams
          • Predicate
          • Consumer_Supplier
          • Collectors in Java
        • Java21 >
          • Un-named Class
          • Virtual Threads
          • Structured Concurrency
      • Threading >
        • ThreadsOrder
        • ProducerConsumer
        • Finalizer
        • RaceCondition
        • Executors
        • Future Or CompletableFuture
      • Important Points
      • Immutability
      • Dictionary
      • Sample Code Part 1 >
        • PatternLength
        • Serialization >
          • Kryo2
          • JAXB/XSD
          • XStream
        • MongoDB
        • Strings >
          • Reverse the String
          • Reverse the String in n/2 complexity
          • StringEditor
          • Reversing String
          • String Puzzle
          • Knuth Morris Pratt
          • Unique characters
          • Top N most occurring characters
          • Longest Common Subsequence
          • Longest Common Substring
        • New methods in Collections
        • MethodReferences
        • Complex Objects Comparator >
          • Performance
        • NIO >
          • NIO 2nd Sample
        • Date Converter
        • Minimum cost path
        • Find File
      • URL Validator
    • Julia
    • Python >
      • Decorators
      • String Formatting
      • Generators_Threads
      • JustLikeThat
    • Go >
      • Tutorial
      • CodeSnippet
      • Go Routine_Channel
      • Suggestions
    • Methodologies & Design Patterns >
      • Design Principles
      • Design Patterns >
        • TemplatePattern
        • Adapter Design Pattern
        • Proxy
        • Lazy Initialization
        • CombinatorPattern
        • Singleton >
          • Singletons
        • Strategy
  • Frameworks
    • Apache Velocity
    • React Library >
      • Tutorial
    • Spring >
      • Spring Boot >
        • CustomProperties
        • ExceptionHandling
        • Custom Beans
        • Issues
      • Quick View
    • Rest WebServices >
      • Interviews
      • Swagger
    • Cloudera BigData >
      • Ques_Ans
      • Hive
      • Apache Spark >
        • ApacheSpark Installation
        • SparkCode
        • Sample1
        • DataFrames
        • RDDs
        • SparkStreaming
        • SparkFiles
    • Integration >
      • Apache Camel
    • Testing Frameworks >
      • JUnit >
        • JUnit Runners
      • EasyMock
      • Mockito >
        • Page 2
      • TestNG
    • Blockchain >
      • Ethereum Smart Contract
      • Blockchain Java Example
    • Microservices >
      • Messaging Formats
      • Design Patterns
    • AWS >
      • Honeycode
    • Dockers >
      • GitBash
      • Issues
      • Kubernetes
  • Databases
    • MySql
    • Oracle >
      • Interview1
      • SQL Queries
    • Elastic Search
  • Random issues
    • TOAD issue
    • Architect's suggestions
  • Your Views

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";
 }
}
Powered by Create your own unique website with customizable templates.