Barclays Capital Interview Question
Senior Software Development EngineersCountry: United States
public class Test {
public static void main(String[] args) {
char[] charArr ={'a','b','a','a','c','d',' ','a','e','a','c','b','b','f','g',' '};
//remove the duplicate char by ' '
for(int i=0;i<charArr.length;i++){
for(int j=0;j<charArr.length;j++){
if((i!=j)&& charArr[i] != ' ' && charArr[i]==charArr[j]){
charArr[j] = ' ';
}
}
}
// push the blank to end
for(int k=0;k<charArr.length ;k++){
for(int l=k+1;l<charArr.length;l++)
if(charArr[k] == ' ' && charArr[l] != ' ' ){
charArr[k] = charArr[l];
charArr[l] = ' ';
}
}
for(int ii=0;ii<charArr.length;ii++){
System.out.println("-----------: " + charArr[ii]);
}
}
}
Time complexity is O(n^2)
Use bit array of size 256.
Do one scan of the give array and while scanning set ar[character] = true.
In second scan, take a charater, check if ar[character] is true, if true, don't do anything, else set it as empty.
In third scan, swap the blank with characters to bring them in the front. To do this, you can use two index one to hold blank position and when other reaches a character swap character and move that until you reach blank that is less than or equal to running index.
1.Easy way is to use any of efficient sorting method(o(nlogn, merge sort)), or any other to sort given array.
2.Then trace array in o(n) to remove duplicates by simply advancing pointer on encounter of previous char.
correct me if I m wrong
public static void removeDuplicates(){
char[] chArray = {'a','a','b','c','a','b','d','c','c','d','a','a'};
char[] finalArray = new char[12];
int k = 0;
System.out.println(chArray);
for (int i = 0; i < chArray.length ; i++){
char tmpChar = chArray[i];
for (int j = i+1; j < chArray.length; j++){
if (chArray[j] == tmpChar){
chArray[j] = ' ';
}
}
if (chArray[i] != ' '){
finalArray[k] = chArray[i];
k++;
}
}
System.out.println(finalArray);
}
#include<stdio.h>
#include<conio.h>
int* merge(int a[],int first1,int first2)
{
int i=0;
int temp;
for(i=first1;i<first2;i++)
{
if(a[i]>a[first2])
{
temp=a[i];
a[i]=a[first2];
a[first2]=temp;
first2++;
}
else if(a[i]==a[first2])
a[i]=0;
}
return a;
}
int* divide(int array[],int first,int last)
{
int mid=((first+last)/2);
int i;
if(first!=last)
{
divide(array,first,mid);
divide(array,mid+1,last);
array=merge(array,first,mid+1);
}
return array;
}
void main()
{
int array[]={2,2,3,6,5,6,7,9,7,9};
int i=0;
int *a;
int *ptr=NULL;
clrscr();
a=divide(array,0,9);
for(i=0;i<10;i++)
{
if(ptr==NULL)
{
if(a[i]==0)
ptr=&a[i];
}
else
{
if(a[i]!=0)
{
*ptr=a[i];
a[i]=0;
ptr++;
}
}
}
for(i=0;i<10;i++)
{
printf("%d\n",a[i]);
}
getch();
}
public static void removeDupl(char a[]){
boolean ind[]=new boolean[26];//Used to indicate if the char already exists
int currIndex=0; //Used to indicate last index of unique chars
for(int i=0;i<a.length;i++){
int val=a[i]-'a';
if(ind[val])//Check in the ind if char already exists
{
a[i]='\0';
}
else
{
ind[val]=true;
if(i!=0){
currIndex++;
a[currIndex]=a[i];
if(currIndex!=i)
a[i]='\0';
}
}
}
System.out.print(a);
}
public class FindingUniqueVakuesInArray
{
public void findUnique(char[]ch )
{
boolean alphabets[]=new boolean[255];
for(int i=0;i<ch.length;i++)
{
if(alphabets[i]!=true)
{
int x = ch[i];
alphabets[x]=true;
}
}
for(int j=0;j<alphabets.length;j++)
{
if(alphabets[j]==true)
{
System.out.print((char)j+" ");
}
}
}
public class FindingUniqueVakuesInArray
{
public void findUnique(char[]ch )
{
boolean alphabets[]=new boolean[255];
for(int i=0;i<ch.length;i++)
{
if(alphabets[i]!=true)
{
int x = ch[i];
alphabets[x]=true;
}
}
for(int j=0;j<alphabets.length;j++)
{
if(alphabets[j]==true)
{
System.out.print((char)j+" ");
}
}
}
no need of O(n^2)
- EK MACHCHAR May 04, 2013When the universe is finite you can always fall back on counting sort or a modification thereof.
O(n) + constant space