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
Develop a code to store n numbers in the list and find if there any 2 numbers in the list whose sum is equal to the number passed to the method.
And that method will return true if such 2 numbers exist in the list else will return false.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

/**
 * @author Nitin Agrawal
 * Below class contains 2 methods to find if any 2 numbers exist in the created
 * list whose sum is equal to the passed value.
 */
public class TwoSumImpl {

 private ArrayList<Integer> list = new ArrayList<>();
 private boolean isSorted = false;
 private int size;
 private int lastValue;

 /**
  * Below method adds the numbers to the list.
  * Currently this method is not synchronized, so if multiple threads try to
  * insert the numbers in the list then it will impact the performance to find
  * the result. So for multiple threaded environment, this method can be made
  * synchronized at the object level.
  */
 public void store(int value) {
  list.add(value);
  /**
   * Below will determine if the sorting is required after the addition of
   * new number to the list.
   */
  //  if(isSorted && value < list.get(list.size()-2))
  if(isSorted && value < lastValue)
   isSorted = false;
  lastValue = value;
  size++;
 }

​/**
  * @param value
  * @return boolean
  * Below method determines if any two numbers are present in the list whose
  * sum is equal to the value passed. In worst case its complexity will be nlogn.
  * In case of multiple thread environment, it may give wrong results,
  * so for such scenarios synchronize the method.
  * It should perform faster than other methods given below.
  */
 public boolean isSumFastest(int value) {

/**
* Below condition is to stop sort() to execute every time this method is
* called.
*/
if(!isSorted) {
    Collections.sort(list);
    isSorted = true;
}
int last = size - 1;

if(value < list.get(0) || value > list.get(last) + list.get(last-1))
   return false;
// Integer[] array = list.subList(0, size).toArray(new Integer[size]);
int i = 0;
int rem = 0;
while(i < last) {
   rem = value - list.get(i);
   if(Collections.binarySearch(list, rem) > i)
       return true;
   i++;
}
return false;

 /**
  * @param value
  * @return boolean
  * Below method determines if any two numbers are present in the list whose
  * sum is equal to the value passed.
  * In case of multiple thread environment, it may give wrong results,
  * so for such scenarios synchronize the method.
  * It is slower than isSum2() and even slower than isSum1() sometimes
  * but sometimes it surprises for some values to be the fastest method.
  * and needs correction to give the correct results for large lists.
  * It is also not suggested for use till its issue is resolved.
  */
 public boolean isSum(int value) {

  boolean isSwitch = false;

  /**
   * Below condition is to stop sort() to execute every time this method is
   * called.
   */
  if(!isSorted) {
   Collections.sort(list);
   isSorted = true;
  }
  //  int last = list.size()-1;
  int last = size - 1;
  int start = 0;

  if(value < list.get(0) || value > list.get(last) + list.get(last-1))
   return false;
  while(last > start) {
   if(!isSwitch) {
    int rem = value - list.get(last);
    Integer[] array = list.subList(0, last).toArray(new Integer[last]);

    /**
     * Binary search is used to find the second number, if present
     * in the remaining list in logn time.
     */
    if(rem > array[0] && rem < array[--last] && Arrays.binarySearch(array, rem) >= 0) {
     return true;
    }
    isSwitch = true;
   } else {
    int rem = value - list.get(start);
    Integer[] array = list.subList(++start, last).toArray(new Integer[last]);

    /**
     * Binary search is used to find the second number, if present
     * in the remaining list in logn time.
     */
    try {
    if(rem > array[start] && Arrays.binarySearch(array, rem) >= 0) {
     return true;
    }
    } catch(NullPointerException e) {
     return false;
    }
    isSwitch = false;
   }
  }
  return false;

 }

 /**
  * @param value
  * @return boolean
  * Below method determines if any two numbers are present in the list whose
  * sum is equal to the value passed.
  * In case of multiple thread environment, it may give wrong results,
  * so for such scenarios synchronize the method.
  * It is the fastest method among the 3 here in general but can be slower than isSum()
  * sometimes. It can be suggested to use for large lists with stable performance.
  */
 public boolean isSum2(int value) {
  /**
   * Below condition is to stop sort() to execute every time this method is
   * called.
   */
  if(!isSorted) {
   Collections.sort(list);
   isSorted = true;
  }
  int last = size - 1;

  /**
   * Below condition has to check all n-1 elements in worst case scenario
   */
  for(int i = last; i > 0; i--) {
   int rem = value - list.get(i);
   Integer[] array = list.subList(0, i).toArray(new Integer[i]);

   /**
    * Binary search is used to find the second number, if present
    * in the remaining list in logn time.
    */
   if(Arrays.binarySearch(array, rem) >= 0) {
    return true;
   }
  }
  return false;
 }

 /**
  * @param value
  * @return boolean
  * Below method determines if any two numbers are present in the list whose
  * sum is equal to the value passed. In worst case its complexity will be n*n.
  * In case of multiple thread environment, it may give wrong results,
  * so for such scenarios synchronize the method.
  * It is the slowest and you will not get the result in time for large lists,
  * so not suggested to use except to test for small lists.
  */
 public boolean isSum1(int value) {
  if(!isSorted) {
   Collections.sort(list);
   isSorted = true;
  }
  
  int last = size - 1;

  int rem = 0;
  int count = last;
  while(count > 0) {
   rem = value - list.get(count);
   if(rem >= list.get(0) && rem < list.get(last)) {
    for(int i = last; i >= 0; i--) {
     int temp = 0;
     while(rem >= list.get(temp)) {
      for(int j = temp; j < i; j++) {
       if(rem == list.get(temp)) {
        return true;
       }
      }
      temp++;
     }
    }
   }
   count--;
  }
  return false;
 }

 public static void main(String[] args) {
  TwoSumImpl twoSum = new TwoSumImpl();
  for(int i = 1; i < 100000; i++) {
   twoSum.store(i);
  }
  long start = System.currentTimeMillis();
  System.out.println(twoSum.isSum(3));
  System.out.println("Time taken by isSum() : " + (System.currentTimeMillis() - start) + " ms");

  start = System.currentTimeMillis();
  System.out.println(twoSum.isSum1(3));
  System.out.println("Time taken by isSum1() : " + (System.currentTimeMillis() - start) + " ms");

  start = System.currentTimeMillis();
  System.out.println(twoSum.isSum2(3));
  System.out.println("Time taken : by isSum2() " + (System.currentTimeMillis() - start) + " ms");

 }
}

Better way to search in sorted Array -
int s1 = 0;
int l1 = size-1;
while(s1 < l1 && !result) {
  if(data[s1]+data[l1] == sum)
     result = true;
  else if(data[s1]+data[l1] > sum)
     l1--;
  else if(data[s1]+data[l1] < sum)
     s1++;
}


Best way to check if such 2 numbers exist -
public static boolean doesExist(int[] arr, int sum) {
   boolean result = false;
   HashSet<Integer> hs = new HashSet<>();
   for(int num : arr) {
       if(result = hs.contains(sum-num))
         break;
       hs.add(num);
    }
    return result;
}​


Powered by Create your own unique website with customizable templates.