Nitin Agrawal
Contact -
  • Home
  • Interviews
    • Secret Receipe
    • InterviewFacts
    • Resume Thoughts
    • Daily Coding Problems
    • BigShyft
    • CompanyInterviews >
      • InvestmentBanks >
        • ECS
        • Bank Of America
        • WesternUnion
        • WellsFargo
      • ProductBasedCompanies >
        • CA Technologies
        • Model N India
        • Verizon Media
        • Oracle & GoJek
        • IVY Computec
        • Nvidia
        • ClearWaterAnalytics
        • ADP
        • ServiceNow
        • Pubmatic
        • Expedia
        • Amphora
        • CDK Global
        • CDK Global
        • Epic
        • Sincro-Pune
        • Whiz.AI
        • ChargePoint
      • ServiceBasedCompanies >
        • Altimetrik
        • ASG World Wide Pvt Ltd
        • Paraxel International & Pramati Technologies Pvt Ltd
        • MitraTech
        • Intelizest Coding Round
        • EPAM
    • Interviews Theory
  • Programming Languages
    • Java Script >
      • Tutorials
      • Code Snippets
    • Reactive Programming >
      • Code Snippets
    • R
    • DataStructures >
      • LeetCode Problems
      • AnagramsSet
    • Core Java >
      • Codility
      • Program Arguments OR VM arguments & Environment variables
      • Java Releases
      • Threading >
        • ThreadsOrder
        • ProducerConsumer
        • Finalizer
        • RaceCondition
        • Executors
        • Future Or CompletableFuture
      • Important Points
      • Immutability
      • Dictionary
      • 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
        • Decorator
        • Proxy
        • Lazy Initialization
        • CombinatorPattern
        • RequestChaining
        • Singleton >
          • Singletons
  • Frameworks
    • Apache Velocity
    • Spring >
      • Spring Boot >
        • CustomProperties
        • ExceptionHandling
        • 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
  • 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.