CareerCup

JS solution (makes sense for a Frontend Position)

var inp=[1,2,4,4,6,5,3,3,7,7,7,9,1];
var map = {};
var out = inp.filter(function(data,index,array){
  if(typeof map[data] == 'undefined'){
    map[data]=true;
    return true;
  }else return false;
});

Is extra space allowed
If yes then BST will be the best bet....
Time complexity : O(nlogn)

1. We can use Hashing here is space is not the constraint. O(n)
2. If space is the constrain the we can take the BST and in this we search for the new number if it is in BST the we return else we create new node for new number.

1. We can use Hashing here is space is not the constraint. O(n)
2. If space is the constrain the we can take the BST and in this we search for the new number if it is in BST the we return else we create new node for new number. O(nlogn)

Hash will work.
Another way is to sort the numbers using any O(nlogn) time algorithm and then do a linear scan.

We can use the array itself as a Min Heap which has root as the minimum element. Start from item 1 to n of the given array and keep inserting in the min heap. During insertion if we find the item already present then we dont insert and continue with next item. This Min Heap will be created as an almost complete binary tree in-place in the given array itself.
So this will be in-place O(nlogn) approach.

The way suggested by @fitish is also in place but will require an extra O(n) scan after the sort.

Please comment if you have any.

Interviewer did give any constraints concerning space, so my solution was to create an 'output' array, loop through the original and keep track of whether a value had been seen before using a hash. If not, push it onto the output array.

I think this and some similar problems are related to Element Distinctness problem (EDP). One can see : "Element Discreteness Problem" in wiki.

So the algo may be:

Sort ascending array to make it partially ordered
i = 0;
if (array[i] - array[++i])
put those into output array
print out output array

a[]=integer input array. n is size of a[].
short lookup[MAX_INT_VAL]={0}; //initialize all to false.
int top=0;
for(int i=0;i<n;i++)
{
if(lookup[a[i]]==0)
{
lookup[a[i]]=1;
a[top++]=a[i];
}
}
n=top;

now i guess we have the same array with all the duplicates removed

Why isnt anyone using a HashSet or any Set implementation.
The algo is:
for every integer in inputarray
{
if (!integerset.add)
{
duplicate detected, scrap it
}
}
return integerset

this is main example for Set interface in java doc...
please comment on my thoughts..

It can be done in O(n) using hashmap, and also if we create BST by ignoring creation of nodes with duplicate nodes. I tried to program in Java, source code below:

BSTNode.java:


/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/

package careercup.google;

/**
*
* @author Harit
*/
public class BSTNode {
private int value;
private int leftChild;
private int rightChild;

public BSTNode(int v){
value = v;
leftChild = -1;
rightChild = -1;
}

public int getValue(){
return this.value;
}

public int getChild(boolean left){
if(left){
return this.leftChild;
}
else{
return this.rightChild;
}
}
public void setChild(int child, boolean left){
if(left){
this.leftChild = child;
}else{
this.rightChild = child;
}
}
}

RemDupArrayBST:

/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/

package careercup.google;

import java.util.ArrayList;

/**
*
* @author Harit
*/
public class RemDupArrayBST {
/* Output Array of Nodes */
private static ArrayList<BSTNode> nodes = new ArrayList<BSTNode>();
private static int parent = -1;
private static boolean left = false;

public static void main(String args[]){
/* Sample Input Array */
//int[] input_array = new int[]{3,1,2,1};
//int[] input_array = new int[]{3,5,4,2,1,2,3,1};
int[] input_array = new int[]{1,2,3,2,4,4};
/* end sample input */

for(int i=0; i<input_array.length; i++){
if(nodes.size() == 0){
/* tree is empty, add root */
BSTNode node = new BSTNode(input_array[i]);
nodes.add(node);
}else{
/* search if node already exists */
if(!contains(input_array[i])){
BSTNode node = new BSTNode(input_array[i]);
nodes.add(node);
nodes.get(parent).setChild(nodes.size()-1, left);
}else{
System.out.println(input_array[i] + " : already exists - ignoring");
}
}
}

/* final print */
System.out.print("Inorder Traversal: ");
inOrderTraverse(nodes.get(0));

System.out.println("");

System.out.print("PostOrder Traversal: ");
postOrderTraverse(nodes.get(0));

System.out.println("");

System.out.print("PreOrder Traversal: ");
preOrderTraverse(nodes.get(0));

System.out.println("");
}

private static boolean contains(int value){
int index = 0;
while(index >= 0){
if (nodes.get(index).getValue() == value){
return true;
}
if (nodes.get(index).getValue() > value){
parent = index;
left = true;
index = nodes.get(index).getChild(true);
}else{
parent = index;
left = false;
index = nodes.get(index).getChild(false);
}
}
return false;
}

private static void inOrderTraverse(BSTNode node){
if(node == null){
return;
}
if(node.getChild(true) != -1){
inOrderTraverse(nodes.get(node.getChild(true)));
}
System.out.print(node.getValue() + " ");
if(node.getChild(false) != -1){
inOrderTraverse(nodes.get(node.getChild(false)));
}
}

private static void postOrderTraverse(BSTNode node){
if(node == null){
return;
}
if(node.getChild(true) != -1){
postOrderTraverse(nodes.get(node.getChild(true)));
}
if(node.getChild(false) != -1){
postOrderTraverse(nodes.get(node.getChild(false)));
}
System.out.print(node.getValue() + " ");
}

private static void preOrderTraverse(BSTNode node){
if(node == null){
return;
}
System.out.print(node.getValue() + " ");
if(node.getChild(true) != -1){
preOrderTraverse(nodes.get(node.getChild(true)));
}
if(node.getChild(false) != -1){
preOrderTraverse(nodes.get(node.getChild(false)));
}
}
}

def remove_dups(A):
  uniq_set = set()
  uniq_list = []
  for a in A:
    if a not in uniq_set:
      uniq_set.add(a)
      uniq_list.append(a)
  return uniq_list

Array in question is already seems sorted.
int i=1;
int j=0;
while(i<n)
{
while(a[i++] == a[j]);
a[j++] = a[i++];
}
a[0..j] will have required elements.

JS solution (makes sense for a Frontend Position)

var inp=[1,2,4,4,6,5,3,3,7,7,7,9,1];
var map = {};
var out = inp.filter(function(data,index,array){
  if(typeof map[data] == 'undefined'){
    map[data]=true;
    return true;
  }else return false;
});

Simple Javascript solution

var a = [1,2,4,6,3,4,4,3,2,2,7,3,6,8];
var removeDup = function(){
	for(i=0;i<a.length;){//IMPORTANT LINE
		if(a[i-1] ==a[i]){
			a.splice(i,1);
		}
		else{
			i++;
		}
	}
	return a;
}
document.writeln(removeDup());

if(typeof(Array.prototype.rmDuplicate)==='undefined'){
    Array.prototype.rmDuplicate = function(){
         var arr = [],
             input = this;
         this.forEach(function(v,i){
             if(arr.indexOf(v)===-1){
                arr.push(v);
             }
         })
       return arr;
      }
    }
         
     var array = [1,2,3,3,3];
     document.write(array.rmDuplicate());

This is in Javascript:

a = [1,2,3,2,4,4];
var out = [];
a.filter(function(item){
  if(out.indexOf(item) === -1){
      out.push(item);  
  }
}); 
a = out;
console.info(a);

JS solution similar to one that has been written

function sortArray(array){
		var newArray = [];
		for(var i=0; i<array.length; i++){
			if( newArray.indexOf(array[i]) == -1 ){
				newArray.push(array[i]);
			}
		}
		return newArray;
	}

var res = [];
      var len = arr.length;
      // Start timing now
      for(var i = 0; i < len; i++) {
        if(res.indexOf(arr[i]) == -1) {
          res.push(arr[i])
        }
      }

This has a running time of O(n) which is not bad..

[1, 2, 3, 2, 1, 3, 4, 5].reduce(function(prev, current) {
        (prev.indexOf(current) < 0) && prev.push(current);
        return prev;
    }, []);

function removeDuplicates(elements){
var map = {};
for(var i = 0; i < elements.length; i++){
map[elements[i]] = true;
}
var result = [];
for(var j in map ){
result.push(parseInt(j, 10));
}

return result;
}

console.log(removeDuplicates([1,2,4,4,6,5,3,3,7,7,7,9,1]));

Array.prototype.removeDuplicates = function () {
  return this.filter((element,index, array) => array.slice(0, index).indexOf(element) === -1);
}
[1,2,3,4,1,3,5,2,6].removeDuplicates(); // [1, 2, 3, 4, 5, 6]

Javascript:

let sourceArray = [1,2,3,2,4,4];
let removeDuplicates = array => {
	let targetArray = [];
  
	array.map(number => {
    if(!targetArray.includes(number)){
      targetArray.push(number);
    }
  });

  console.log(targetArray);
};

removeDuplicates(sourceArray);

function removeDuplicates(list){
  const numbers = new Set();
  let clean = [];
  for (let i=0;i<list.length; i++){
    if (!numbers.has(list[i])){
      clean.push(list[i]);
      numbers.add(list[i]);
    }
  }
  return clean;
}

console.log(removeDuplicates([1,2,3,2,4,4]));