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 duplicate numbers in an array.

4/24/2018

1 Comment

 
Question : During the interview with GlobalLogic, I was asked to find the duplicate numbers
​                   in the given array of random number.
                 ​  Numbers are random & you don't know in what range these numbers lie, i.e. you
​                   just know the size of array but no information is available about the numbers in it
​                   before hand. No collection can be used.
                  ​And the complexity of this should be O(n). Another issue is with these interviewers,
​                  they themselves are not ready to clear the question & force you to make mistakes.
​Solution : I am not sure about an effective solution here.
​                 Though we can find the such duplicate numbers in below ways. Coding for this is
​                 quite simple & I am not giving any code for these, will just give the approach.
 Case 1 : If collections can be used then we can use -
​               (A) HashSet, keep on adding the elements in this hashset & if add() returns false
​                     then it means number is repeated & add this number to your result array. This
​                     array you will return from your method as you are giving all the repeated
​                     numbers
​               (B) If you need to find how many times each number is appearing in the array or
                     repeating in the array. Use HashMap, where key will be the number & value will
​                     be the count of appearance. So keep on updating this hashmap while iterating
​                     through the received array of numbers.
    ​                 Once done, you can browse/iterate the above hashmap to get the required
​                     results. So here running complexity, you can get around O(n) but will take extra
​                     space for collections.
​Case 2 : If collections can't be used -
​              Sort the received array of numbers with your favourite sorting algorithm. And then
​              iterate through the sorted array, every repeated number will adjacent to each other in
​              sorted array & that you can identify. 
​              So here running time will be quite dependent on the sorting algorithm used.

​If you have better approach please let me know.
1 Comment
Whole Pack Magazine link
6/19/2023 10:44:10 am

Very creeative post

Reply



Leave a Reply.

    Author

    Nitin Agrawal

    Archives

    April 2018

Powered by Create your own unique website with customizable templates.