Microsoft Interview Question
Software Engineer InternsCountry: United States
Interview Type: In-Person
you can do like this....extra space is required.....but if extra space is not allowed then apply mergsort on array.....at the time of merging put only one instance of integer by discarding all duplicates....complexity is O(nlogn)
Set s = new HashSet();
List l = Array.asList();
s.add(l);
l.add(s);
Array output=1.toArray();
If extra space is not to be used then use simple merge sort for the array and then as the array is sorted then all duplicate elements will appear consecutively. So they can be easily removed and then return the array . Time complexity is O(nlogn). But if it is to be done in O(n) then I think that we have to use an extra space in the form of a hash.
1. Sort the input array.
2. Traverse the sorted array and fill the result array without duplicates.
void GetSortedArray(int* pArr, int n, int* & pResultArr, int& nrElems)
{
if (pArr == Null || n <= 0)
return NULL;
qSort(pArr, n);
vector<int> result;
for (int i = 0; i < n -1; i++)
{
if (pArr[i] != pArr[i+1])
result.push_back(pArr[i]);
}
result.push_back(pArr[i]);
nrElems = result.Count();
pResultArr = new int[nrElems];
Copy(result, pResultArr);
}
I think sorting is a little overkill, because we do not need these elements to be sorted at all. Couple of possible options:
1. Hash table
1. Using the idea from Set. Insert these elements into binary search tree. During insertion, all the duplicated elements will be filtered out.
1. agreed (or if range of integers is small, just use an array or bit vector of flags)
Your other solution is O(n^2) in worst case to insert n elements for a regular BST. Average/Best case is O(n*lg(n)) to insert n elements.
So one would require a RedBlack, AVL, or similar balanced tree to even match a comparison sort solution.
def solve(input):
dict = {}
i = 0
res = []
while i < len(input):
if input[i] not in dict:
res.append(input[i])
dict[input[i]]=''
i += 1
pass
return res
if __name__ == '__main__':
input = [1, 2, 2, 3, 3, 4]
print "Input : ", input
print "result : ", solve(input)
pass
import java.util.*;
class duplicate
{
public int[] removeDuplicate(int []ar)
{
HashSet hs=new HashSet();//it will not allow duplicates to enter
int i,j=0;
int []newArray=new int[ar.length];//initialize new array of same length of given array
for(i=0;i<ar.length;i++)
{
hs.add(ar[i]);
}
Iterator ir=hs.iterator();
while(ir.hasNext())
{
newArray[j]=Integer.parseInt(ir.next().toString());
j++;
}
return newArray;
}
public static void main(String args[])
{
duplicate d=new duplicate();
int []a={20,10,12,10,15,10};
int []b=d.removeDuplicate(a);
for(int i=0;i<b.length;i++)
{
System.out.println(b[i]);
}
}
}
Try this in java:
int [] array=new int []{1,14,9,2,7,15,6,3,4,11,8,5,14,7,6,7,8,3,9,2,13,11,12};
List<Integer> myList = new ArrayList<Integer> ();
for (int i=0; i<array.length; i++)
{
if (!myList.contains(array[i]))
myList.add(array[i]);
}
Collections.sort(myList);
During interviews, they wouldn't want you to use a built in sort as they want to know you know whats going on. Implement your own sort.
Simplest solution would be to maintain a counter for every number as you proceed through an array. For eg= Array A = [1,2,3,3,3,4,5] , Counter[1] = 1, counter[2] = 1 counter [3] =1, then when a pointer comes to 3 again, it will not add that element into a result array as counter[3] is already one. This will take O(n) time. The solution is best suited when space constraints are not given.
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include <map>
#include <string.h>
//method one:use map, since no hashmap, we can use stl c++ map implemented by rb tree.
typedef std::map<int,bool> Map;
int removeDup(int * a, int length){
if (!a ||length <=1) return length;
std::cout<<"Not null"<<std::endl;
Map m;
Map::iterator it;
int index = 0;
for (int i = 0;i<length;i++){
it = m.find(a[i]);
if (it == m.end()){
m[a[i]]=true;
//std::cout<<"Not dup "<<
if (index != i){
a[index] = a[i];
}
index++;
}
}
std::cout<<index<<std::endl;
return index;
}
Note:c++ has no hashmap, so here I use the stl map which is implemented by RB tree. If the number of elements are not quite large, look up and insertion can be considered as constant. However, one can implement his own hashmap to do this. The time complexity is O(n).
// Build Binary Search tree by reading each element and add only unique element-
// now readback each element in inorder traversal to return back
// O(nlogn) Time and O(n + n) space complexity
// wrote on notedpad hence no compile error checking performed...
public int[] GetUniqeRecord(int[] arr)
{
if(arr == null) return null;
if(arr.Length == 1) return arr;
// Build Binary search tree
int count;
Node root = CreateBinaryTree(arr,out count);
return uniqueRecord(root);
// Readh binary search tree
}
public class Node
{
public int data{get;set;}
public Node left{get;set;}
public Node right{get;set;}
public Node(int data)
{
this.data = data;
}
}
publc int[] uniqueRecord(Node root,int count)
{
Stack s = new Stack();
int[] arr = new int[count];
Node n = root;
s.Push(n);
int i=0;
while(!s.IsEmpty() || n!= null)
{
if(n != null)
{
s.push(n);
arr[i++] = n.data;
n = n.left;
}
else
{
n= s.Pop();
n = n.right;
}
}
return arr;
}
public Node CreateBinaryTree(int[] arr,ref int cout)
{
Node root = null;
root = new Node(arr[0]);
Node temp = null;
node pre;
bool duplicate = false;
for(int i=1;i<arr.Legth-1;i++)
{
temp = root;
duplicate = false;
while(temp != null)
{
pre = temp;
if(arr[i] > temp.data)
{
temp = temp.right;
}
else if(arr[i] < temp.data)
{
temp = temp.left;
}
else
{
duplicate = true;
break;
}
}
if(!duplicatae)
{
if(arr[i] > pre.data)
pre.right = new Node(arr[i]);
else
pre.left = new Node(arr[i]);
count++;
}
}
}
used HashSet and an additional array, the space complexity is not O(n). Not efficient solution. Please suggest how can I improve it.
public class Unique {
public static void main(String[] args){
int[] dup={1,2,4,3,2,2,1,3,4,5,7,6,8,9,8,8,7};
Set set=new HashSet();
for(int i=0;i<dup.length;i++){
if(!set.contains(dup[i])) {
set.add(dup[i]);
}
}
int size=set.size() ;
int[] unique=new int[size];
int k=0;
for(int i=0;i<dup.length;i++){
if(set.contains(dup[i])){
unique[k++]=dup[i];
set.remove(dup[i]); //removing from the set as soon as it is added to the array
}
}
for(int i=0;i<size;i++){
System.out.print(unique[i]);
}
}
}
We can store the array in a HashSet and then covert back the HashSet in array. This will remove the duplicate elements. please Correct me if I am wrong.
- Ghosh September 20, 2013