Java · JavaScript · Programming

Interesting Algorithm Questions for interview

Find the duplicates in an array in O(n) time

There is actually no algorithm to give perfect O(n) time for processing.
However, there is a way to find the solution in worst case scenario of O(2n) i.e O(n).

ke’s comment about the complexity being O(n2) is indeed correct.
You can read more about it at Stackoverflow.com post.

I present the solution below in JavaScript and Java.
It is a simple solution based on Associative Arrays in JavaScript and Hash Maps in Java.
In each case you store the elements of input array into a hash based datastructure.
This ensures that you do not repeat the same element and can count the number of instances of duplicate elements.

JavaScript solution

//find the duplicates in an array in O(n)
function findDupsInArray() {
    
    var arr = new Array("1","1","2","3","1","3","4","4","5","5","5","5","23","55","23");

    var assArr = new Array();

    for(i=0;i<arr.length;i++) 
    {
        if(arr[i] in assArr) 
        {
            assArr[arr[i]] = assArr[arr[i]]+1;
        } 
        else 
        {
            assArr[arr[i]] = 1;
        }
    }

    for(var key in assArr) {
        alert(key + ' = ' + assArr[key]);
    }

}

findDupsInArray();

Java Solution

package algorithms;

import java.util.Map;
import java.util.HashMap;

/**
 *
 * @author amitrai
 */
public class FindDuplicatesInArray {

    public static void main(String[] args) {

        String[] arr = {"1","1","2","3","1","3","4","4","5","5","5","5","23","55","23"};

        Map dataMap = new HashMap();

        for(int i=0;i<arr.length;i++) {

            if(dataMap.containsKey(arr[i])) {
                dataMap.put(arr[i], dataMap.get(arr[i])+1);
            } else {
                dataMap.put(arr[i], 1);
            }

        }

        for(String key : dataMap.keySet()) {
            System.out.println(key+"="+dataMap.get(key));
        }

    }

}
Advertisements

2 thoughts on “Interesting Algorithm Questions for interview

  1. Not correct. First, there is no difference between O(n) and O(2n). Second, containsKey itself has O(n) worst case time so you get O(n²) overall.

    Credits: Thanks to D. and Y. for confirming my hunch on this.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s