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

Sort an array of integers.

Sometimes such question can be asked in the interviews check your knowledge on various sorting algorithms or concepts.
But will be better to know the kind of integers present in that array, like here array may contain many duplicate numbers & those numbers can be any in range 0 to 2 or 1 to 1000 or 1 to 1000000.
And I am not sure what algorithm, interviewer has thought for its solution or what response is expected from you.
And I can think about following approaches -

a) If the number of unique integers is quite small like if range is 0 to 2, then you can start with 3 pointers marking the position of last 0 visited & second pointer to mark the position of last 1 visited & 3rd pointer will keep on traversing the array & will also be pointing the position of last 2 visited. In this way you can sort such array in log(n) time.
But it is not possible if unique integers are many.
b) If the number of unique integers is quite large like 1 to 1000 or 1 to 1000000 etc.
Then one from many sorting algorithm can be suggested i.e. counting sort, as read in books.
To explain easily generally at many place it will be shown where you will be creating any array whose each index will be representing the integer & the value will be the number of times that integer occurs in the array.
But it is fine only when either you are not having a huge range of sparse numbers or range of integers is small where space in such array will not be wasted.


So if the range is huge & integers are sparse then you have to customise this approach a bit, like shown on geeksforgeeks for the characters.

For integers, I am doing the same steps but bit differently - 
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;

public class CountSort {

 public static void main(String[] args) {
  int[] array = {0,1,2,0,1,2,2,1,0,1,0,2,1,0,0,1,2,0,1,2,1,2,100,200,100,200,101,200,200};
  array = sort(array);
  for(int i : array)
   System.out.println(i);
 }

 private static int[] sort(int[] array) {
  int len = array.length;
  ArrayList<Integer> uniques = new ArrayList<>();
  HashMap<Integer, Integer> counts = new HashMap<>();
  for(int i : array) {
   Integer a = null;
   if((a=counts.get(i)) == null) {
    uniques.add(i);
    counts.put(i, 1);
   } else {
    counts.put(i,  a+1);
   }
  }

  Collections.sort(uniques);

  int next= 0;
  for(int i = 0; i < len;) {
   int num = uniques.get(next);
   int c = counts.get(num);
   while(c > 0) {
    array[i] = num;
    i++;
    c--;
   }
   next++;
  }
  return array;
 }
}
So I think its time complexity will be = nlog(n)
Powered by Create your own unique website with customizable templates.