Ericsson Interview Question
Software Engineer / DevelopersFairly straightforward O(n) solution:
public String removeDupes(int[] input){
if(input.length == 0 || input.length == 1) return input;
int prev = input[0];
String output = "" + prev;
for(int i=1; i<input.length; i++){
int cur = input[i];
if(prev != cur){
output += ", " + cur;
prev = cur;
}
}
return output;
}
@Kyle.
The approach will only work if the duplicate elements are always together as mentioned in the example. However it is not explicitly mentioned in the question. So if the sequence can be 111122223333311111 then you will op 1 multiple times. In that case, bitmap/hash can be used.
Hash the Key values to the global array. However we don't need to distinctly has each value here. So overriding the same value wont be an issue.
function (int a[])
{
for (int i=0;i<a.length();i++)
{
int key = a[i]/255; // Assuming the maximum difference in given value to be fully represented by the Ascii table..
global_array[key]=a[i];
}
// Now you can read the global array to get the value distinctly.
}
one more way is building a max heap or min heap will fix the problem. while inserting we can find out the element is inserted or not, if the value is already present print the value and move to next value.
#include<iostream>
#include<stdio.h>
#include<conio.h>
using namespace std;
void main(){
int arr[10],temp[10],i,j,k,n,flag;
cout<<"enter the number of elements: ";
cin>>n;
cout<<"enter the number: ";
for(i=0;i<n;i++)
cin>>arr[i];
temp[0]=arr[0];
k=1;
for(i=1;i<n;i++){
flag=0;
for(j=0;j<k;j++){
if(arr[i]==temp[j]){
flag=1;
break;
}
}
if(flag==0){
temp[k]=arr[i];
k++;
}
}
cout<<"the resultant array is: ";
for(i=0;i<k;i++)
cout<<" "<<temp[i];
_getch();
}
If array is sorted... then can be solved in Time Complexity - O(log n) and Space Complexity O(1). Otherwise, use hash maps... Time Complexity O(n) and Space Complexity O(n)...
I am giving solution for the sorted array scenario:-
#include<iostream>
using namespace std;
int rightBinarySearch(int *arr, int start, int end, int prev_mid,int key)
{
if ( start > end )
return prev_mid;
int mid = (end-start)/2 + start;
if ( arr[mid] == key )
return rightBinarySearch(arr,mid+1,end,mid,key);
else if (arr[mid] > key)
return rightBinarySearch(arr,start,mid-1,prev_mid,key);
else
return rightBinarySearch(arr,mid+1,end,prev_mid,key);
}
void Compressor(int* arr, int *len)
{
if ( !arr || *len < 2 )
return;
int i = 0, start = 0, end = *len;
while( start < end )
{
arr[i++] = arr[start];
start = rightBinarySearch(arr,start,end,start,arr[start]) + 1;
}
*len = i;
}
int main()
{
int arr[] = { 10,11,11,11,11 };
int len = 5;
Compressor(arr, &len);
for ( int i = 0; i<len; i++ )
cout << arr[i]<<" ";
return 0;
}
void remove_double (const char *src, char *dst)
{
const char *tmp_src = src;
while (*src) {
if (*src == *++tmp_src)
src++;
else {
*dst++ = *src;
*dst++ = ',';
src++;
}
}
*--dst = '\0';
}
int main()
{
char src[] = "11222222222222222222222222222222222222222222222222222222222222222222222222567888888888888888888888888";
char dst[128] = {0};
remove_double(src, dst);
printf("Data:%s\n", dst);
return 0;
}
if the element is only a character from ascii, you can use bitset with size of 255 to remember if it is repeated.
- Anonymous September 05, 2011