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

Find the increasing order of combinations of the prime numbers in an array or list

Below question I got during the coding round in ServiceNow in Hyderabad & time for this was 1 hour & believe me, it took me 2 hours to write the logic at home with no time pressure, even for one of solution posted below I took the help from internet to get the methods, so surely I couldn't have done this coding in an hour & that too during the time constraint. And I was not able to think even near to this solution during that round in company there. But posting the solution now with question I got -
​
You are given an array/list of numbers. You need to find all possible combinations of the prime number present in that array/list, such that the numbers are in increasing order, i.e. all the numbers present in every combination are in increasing order. Below is the code for that -
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
​
public class Combinations {
 public static void main(String[] arg) {
//  int[] args = {-1, 3, 5, 7, 10, 20, 1902, 8233};
  int[] args = {1, 3, 10, 61, 13};
  List<Integer> primes = new ArrayList<>();
  
  // Below creates the list of prime numbers present in the array/list
  for(int number : args) {
   if(number == 2 || number == 3 || number == 7) {
    primes.add(number);
    continue;
   } else if(number < 0 || number == 0 || number == 1)
    continue;
   boolean isPrime = true;
   int sqrRoot = (int)Math.floor(Math.sqrt(number));
   int i = 2;
   for(; i <= sqrRoot; i++) {
    if(number%i == 0 && sqrRoot != 0) {
     isPrime = false;
     break;
    }
   }
   if(isPrime) {
    primes.add(number);
   }
  }
  // Below sorts the discovered prime numbers
  Collections.sort(primes);
  
  Integer[] arr = new Integer[primes.size()];
  for(int i = 1; i <= primes.size(); i++)
   printCombination(primes.toArray(arr), primes.size(), i);
 }
 // Below 2 methods are taken from https://www.geeksforgeeks.org/print-all-possible-combinations-of-r-elements-in-a-given-array-of-size-n/
 private static void combinationUtil(Integer arr[], int data[], int start,
   int end, int index, int r)
 {
  // Current combination is ready to be printed, print it
  if (index == r)
  {
   for (int j=0; j<r; j++)
    System.out.print(data[j]+" ");
   System.out.println("");
   return;
  }
  // replace index with all possible elements. The condition
  // "end-i+1 >= r-index" makes sure that including one element
  // at index will make a combination with remaining elements
  // at remaining positions
  for (int i=start; i<=end && end-i+1 >= r-index; i++)
  {
   data[index] = arr[i];
   combinationUtil(arr, data, i+1, end, index+1, r);
  }
 }
 // The main function that prints all combinations of size r
 // in arr[] of size n. This function mainly uses combinationUtil()
 static void printCombination(Integer arr[], int n, int r)
 {
  // A temporary array to store all combination one by one
  int data[]=new int[r];
  // Print all combination using temprary array 'data[]'
  combinationUtil(arr, data, 0, n-1, 0, r);
 }
}
Above code is elegant & surely it looks simpler but somehow its output is bit difficult to verify for the possible combinations.
Also in some test cases I executed, it worked quite slower than the below 2 methods. Plus below methods give the output in the ordered manner which makes it easier to verify the results.
Though I have not tested it for required number of test cases, please let me know if it fails for any case.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
​
public class Combinations {
 public static void main(String[] arg) {
//  int[] args = {-1, 3, 5, 7, 10, 20, 1902, 8233};
  int[] args = {1, 3, 10, 61, 13};
  List<Integer> primes = new ArrayList<>();
  
  // Below creates the list of prime numbers present in the array/list
  for(int number : args) {
   if(number == 2 || number == 3 || number == 7) {
    primes.add(number);
    continue;
   } else if(number < 0 || number == 0 || number == 1)
    continue;
   boolean isPrime = true;
   int sqrRoot = (int)Math.floor(Math.sqrt(number));
   int i = 2;
   for(; i <= sqrRoot; i++) {
    if(number%i == 0 && sqrRoot != 0) {
     isPrime = false;
     break;
    }
   }
   if(isPrime) {
    primes.add(number);
   }
  }
  // Below sorts the discovered prime numbers
  Collections.sort(primes);
  
  Integer[] arr = new Integer[primes.size()];
  Map<Integer, List<String>> finalRes = new LinkedHashMap<>();
  long start1 = System.currentTimeMillis();
  for(int i = 1; i <= primes.size(); i++)
   kick(primes.toArray(arr), finalRes, i);
  for(Integer num : finalRes.keySet()) {
   List<String> results = finalRes.get(num);
   for(String res : results)
    System.out.println(res);
  }
 }

​/**
  * @Created : Nitin Agrawal
  * @param primes : Sorted array of prime numbers
  * @param finalRes : It will be holding the results in ordered manner.
  * @param count : number of digits in the combination
  */
 public static void kick(Integer[] primes, Map<Integer, List<String>> finalRes, int count) {
  List<String> results = new ArrayList<>();
  int i = 0;
  int j = 0;
  int len = primes.length;
  for(int num : primes) {
   if(count == 1)
    results.add(num + "");
   while(i < len-1 && count > 1) {
    counter(primes, results, count-1, i, len-1, num+"");
    i++;
   }
   i = j+1;
   if(finalRes.get(num) == null)
    finalRes.put(num, results);
   else {
    List<String> results1 = finalRes.get(num);
    results1.addAll(results);
    finalRes.put(num, results1);
   }
   results = new ArrayList<>();
   j++;
  }
 }
 /**
  * @Created : Nitin Agrawal
  * @param primes
  * @param results
  * @param count
  * @param start
  * @param end
  * @param curr
  */
 private static void counter(Integer[] primes, List<String> results, int count, int start, int end, String curr) {
  if(start >= primes.length-1)
   return;
  String result = primes[start+1] + "";
  if(count > 0) {
   result = curr + ", " + result;
   count--;
  }
  if(count > 0) {
   counter(primes, results, count, start+1, end, result);
  }
  else
   results.add(result);
  if(primes.length-2 >= start && count > 0)
   counter(primes, results, count, start+2, end, result);
 }
Powered by Create your own unique website with customizable templates.