Microsoft Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
Algorithm:
1) Scan the string from left to right and construct the count array.
2) Again, scan the string from left to right and check for count of each
character, if you find an element who's count is 1, return it.
prashantsitm, what if there are negative integers in the array? How do you build the count array?
It will work for negative integers also
as we can use
if(num<0)
{
num=(num*-1)+9;
}
so the numbers who are negative wll be in array at index more than 10,while positive integers are at less than 10,and while giving output again multiply the numbers at index more than 10 with -1.
}
Hi all,
I think we can create balanced tree out of the array, like AVL tree
For “N” elements it will take O (N log N)
While creating the Tree we can discard all the elements which are already in the Tree.
Now just go for a walk in the Tree which will take O(Z) <=O(N)
So overall complexity is O(N log N +N)
Which is O( N Log N)
Logic- Sort the array by bubble sort Checking every last two number in the array. If they are not equal print them.. This require the same complexity as bubble sort (nlogn) and no extra space.
Program:
void PrintNonDuplicateElement(int a[])
{
int len = sizeof(a)/sizeof(a[0]);
int i,r,temp, count = 0;
for (int j= len-1;j>=1;j--)
{
i = 0;
r = j;
count++;
while(i<r)
{
if (a[i] > a[r])
{
temp = a[i];
a[i] = a[r];
a[r] = temp
}
i++;
}
if ( (count%2) == 0
&& (a[r] != a[r+1]))
{
printf("%d , %d", a[r],a[r+1]);
}
}
}
Can't we use a Hashmap for this ? So that we can eliminate the keys which has a count value > 1 and print out the rest, in which case we have a o(n+m)
This is the best solution for this and the time would be O(n). Also, you would only need to traverse the array once. ^_^
int arr[]=new int[]{1,2,1,3,3};
Set s=new HashSet();
for (int a: arr)
{
if(!s.add(a))
System.out.println("duplicate"+a);
}
Complexity is O(n)
sort the array using heap sort which takes o (n log n). Print the unique values in o(n)
- Sunil February 10, 2012