CareerCup

if i understood properly "from an array and sorted array", i have two arrays one sorted and one unsorted

for unsorted array:
1) hash table
2) buckets (much like hashing though)
3) make BST of all elements
4) sort it and do methods that i will use in sorted array :D

for sorted array:
1) check consecutive elements
2) one can use hash/bucket/BST but they have same effect as checking consecutive elemetns

I love it when they say things like "which one is the best" or whatever. I had an interview recently where they asked me some bullshit question, and I wrote the code, and the questioner asked "is that optimal" and I (without the intention of being a dick) automatically asked "optimal in space or time?". The questioner seemed clueless about my counter. It was a shitty company anyways.

1. Unsorted Array
Sort - O(nlog(n))
Compare consecutive elements - O(n)

Overall - O(nlogn)

2. Sorted Array
Compare consecutive elements - O(n)
Hash Table would not be space optimal

Bucket Sort would also be not space optimal

<pre lang="" line="1" title="CodeMonkey32969" class="run-this">/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package javaapplication1;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

/**
*
* @author lalit
*/
public class RemoveDuplicate {

Map map1= new HashMap<Integer,Integer>();

public Map removeDuplicates(int [] A){

Map map = new HashMap<Integer,Integer>();

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

if(!map.containsKey(A[i]))map.put(A[i],1);
else map.put(A[i],new Integer((Integer)map.get(A[i]))+new Integer(1));


}
return map;
}

public void initialize(){

int [] array = new int[]{4,5,2,5,6,2,6,7,1,1,8,4,7,1};
map1=removeDuplicates(array);
displayMap();
}

public void displayMap(){

Set set = map1.entrySet();
Iterator it = set.iterator();

while(it.hasNext()){
Map.Entry entry = (Map.Entry<Integer, Integer>)it.next();
System.out.println(entry.getKey()+" "+entry.getValue());
}


}

public static void main(String args[]){
new RemoveDuplicate().initialize();
}

}
</pre><pre title="CodeMonkey32969" input="yes">
</pre>

O(n) space, O(n) time. Can handle sorted and unsorted. Sorted version can be done O(1) space and O(n) time.

/* In-place duplicate removal.
 * returns unique number of elements.
 */
int remove_duplicates(int *a, int n)
{
    struct list_node **hash_table;
    struct list_node *allocated_memory, *next_alloc;
    struct list_node *curr;
    int *writer, *reader;
    int bucket, count;

    /* N buckets are more promising minimum hash collisions. */
    hash_table = (struct list_node **)malloc(sizeof(struct list_node*) * n);
    memset(hash_table, 0, sizeof(struct list_node*) * n);

    /* Pre alloc all the link list nodes. */
    allocated_memory = next_alloc = (struct list_node *)malloc(sizeof(struct list_node) * n);
    memset(allocated_memory, 0, sizeof(struct list_node) * n);

    writer = reader = a;
    count = n;
    while (count--) {
        for (curr = hash_table[*reader % n]; curr != NULL; curr = curr->next) {
            if (curr->data == *reader) {
                break;
            }
        }

        /* If not found. */
        if (curr == NULL) {
            /*alloc*/
            curr = next_alloc++;
            curr->data = *reader;
            /* inserting to hash table. */
            curr->next = hash_table[*reader % n];
            hash_table[*reader % n] = curr;

            /* write in the result. */
            *writer++ = *reader;
        }
        ++reader;
    }

    free(hash_table);
    free(allocated_memory);

    return (writer - a);
}

traverse through each element from the unsorted element and check whether the value is present or not in the unsorted array using binary search...

use a hash table and store the frequency of every values. remove all the elements that have frequency more than one...

If the array is unsorted this has an nlogn lower bound. Can be reduced to the element uniqueness problem.