CareerCup

void dedupe(char *str)
{
int length = strlen(str);
int i=0,j=0;
char flag[256];
for(i=0; i<256; i++)
{
flag[i] = 0;
}
for(i=0; i<length; i++)
{
if(flag[str[i]] == 0)
{
flag[str[i]] = 1;
str[j] = str[i];
j++;
}
}
str[j] = '\0';
}

//C#
 //O(n)
        static char[] removeDuplicateChars(char[] _str)
        {
            bool[] charset = new bool[256];
            for (int i = 0; i < _str.Length; i++)
            {
                int val = _str[i];
                if (charset[val]) { _str[i] = ' '; }
                charset[val] = true;
            }
            return _str;
        }

My answer in JavaScript

(function(){
    window.dedupe = function(str){
        var i, curr = 0,
            res = "",
            hash = {},
            len = str.length;

        for (i=0; i < len; i++){
            if (hash[str[i]]){
                continue;
            }
            res += str[i];
            hash[str[i]] = true;
        }
        return res;
    }
})();

In Java:

public static String cleanString(String arg) {

String result = "";

for (int i = 0; i < arg.length(); i++) {

char c = arg.charAt(i);

if (result.indexOf(c) == -1) {
result += c;
}
}

return result;
}

any ans..

Do a mergesort, with slight changes to the merge part: when you find two elements equal, add only of them to the list.

#include <iostream>

using namespace std;

#define MAX_NUM_CHAR 256

char * dedupe(char * str);

int main(void) {

char str1[5] = {'a', 'b', 'c', 'a', '\0'};
char str2[8] = {'a', 'b', 'b', 'a', 'a', 'd', 'e', '\0'};

char * str = NULL;

str = dedupe(str1);
printf("%s\n", str);
str = dedupe(str2);
printf("%s\n", str);

return 0;
}

char * dedupe(char * str)
{

unsigned int i = 0, j = 0;;
unsigned int strLen = 0;
char hasChar[MAX_NUM_CHAR];

if(str == NULL) return NULL;

// init hasChar array
for(i = 0; i < MAX_NUM_CHAR; i++) {
hasChar[i] = 0;
}

strLen = strlen(str);
for(i = 0, j = 0; i < strLen; i++) {
if(hasChar[str[i]] == 0) {
str[j++] = str[i];
hasChar[str[i]] += 1;
} else ;
}
str[j] = '\0'; // here comes memory leak? in that string has more memory than necessary

return str;
}

int length = str.size();
bool bitmap[256];
init(); //false for all 256 elements
for(int i=0; i<length; i++)
if (bitmap[str[i]]) remove(str[i]);
else
bitmap[str[i]]=true;

How about this implementation? The algorithm is simple: maintain a dedupped string ended by pointer "end", and each time a new charactor pointer by "p" will compare to all the dedupped characters.

void RemoveDuplicates(char *str) {
if (str == NULL) return;
int len = strlen(str);
if (len <= 1) return;

char *end = str;
for (char *p = end + 1; *p; ++p) {
bool dup = false;
for (char *t = str; t <= end; ++t) {
if (*t == *p) {
dup = true;
break;
}
}
if (!dup) {
*++end= *p;
}
}
*++end= '\0';
}

public static String dedupe(String str) {
		int [] A = new int[256];
		StringBuffer sb = new StringBuffer();
		
		int len = str.length();
		for (int i=0; i<len; i++) {
			char c = str.charAt(i);
			if (A[c] == 0) {
				A[c] = 1;
				sb.append(c);
			}
		}
		
		return sb.toString();
	}

/*
Given a string *Str of ASCII characters, write the pseudo code to remove the duplicate elements present in them.
For example, if the given string is "Potato", then, the output has to be "Pota".
Additional constraint is, the algorithm has to be in-place( no extra data structures allowed) .
Extend your algorithm to remove duplicates in the string which consisted of UNICODE characters.
*/
#include<iostream>
using namespace std;
int main()
{
char a[20],*p;
p=a;
cin >> a;
while(*p)
{
char *s = (p+1);
while(*s)
{
if(*s == *p)
{
int i=0;
while(*(s+i))
{
if(*(s+i) == *p)
i++;
*s = *(s+i);
s++;
}
*s = '\0';
}
else
s++;
}
p++;
}
cout << a << endl;
system("pause");
return 0;
}

/*
Given a string *Str of ASCII characters, write the pseudo code to remove the duplicate elements present in them.
For example, if the given string is "Potato", then, the output has to be "Pota".
Additional constraint is, the algorithm has to be in-place( no extra data structures allowed) .
Extend your algorithm to remove duplicates in the string which consisted of UNICODE characters.
*/
#include<iostream>
using namespace std;
int main()
{
char a[20],*p;
p=a;
cin >> a;
while(*p)
{
char *s = (p+1);
while(*s)
{
if(*s == *p)
{
int i=0;
while(*(s+i))
{
if(*(s+i) == *p)
i++;
*s = *(s+i);
s++;
}
*s = '\0';
}
else
s++;
}
p++;
}
cout << a << endl;
system("pause");
return 0;
}

#import<stdio.h>
#import<string.h>
void  moveZeros(char* a)
{
        size_t len = strlen(a);
        int index0 = 0;
        int indexN = 0;
        for(int i = 0; i < len; i++)
        {
                if(a[i] != '@')
                {
                        int temp = a[i];
                        a[i] = a[index0];
                        a[index0] = temp;
                        index0++;
                }
        }
        a[index0] = '\0';
}
void dupeWithExtraSpace(char* str)
{
	int charArray[26] = {0};
	int i, j;
	i = j = 0;
	
	for(;i < strlen(str); i++)
	{
		if(charArray[str[i] - 'a'] == 0)
		{
			str[j] = str[i];
			charArray[str[i] - 'a'] = 1;
			j++;
		}
	}
	str[j] = '\0';
}

void dupeWithNoExtraSpace(char* str)
{
	char currChar;
	for(int i = 0; i < strlen(str); i++)
	{
		currChar = str[i];
		if(currChar != '@')
		{
			for(int j = i + 1; j < strlen(str); j++)
			{
				if(currChar == str[j])
				{
					str[j] = '@';
				}
			}
		}
	}
	moveZeros(str);
}

int main()
{
	char a[] = "ccbbbcdecdea";
	char b[] = "abcdabcdabcd";

	dupeWithNoExtraSpace(a);
	dupeWithExtraSpace(b);

	printf("%s \t %s \n",a , b);
}

The solution has two versions, one with extra space, and one without extra space. Without extra space, we need O(n!) time complex algo.
With extra space it is doen in O(n)

def dedupe(string):
    result = ""
    for i, letter in enumerate(string):
        if letter not in result:
            result += letter
    return result

Oops, correction:

def dedupe(input_str):
    result = ""
    for letter in input_str:
        if letter not in result:
            result += letter
    return result

Java code

public static void main(String[] args){
	String s="abcdaabbcdefghk";
	String r=dedupe(s);
	System.out.println(r);
	}	
	
	static String dedupe(String s){
 	char[] c=s.toCharArray();
		for(int i=0;i<c.length;i++){
			char tmp=c[i];
			for(int j=0;j<c.length;j++){
				if(i==j)
					continue;
				else
					if(tmp==c[j])
						c[j]=' ';
			}
		}
		String result=String.valueOf(c);
		return result.replaceAll("\\s", "");
	}

char* dedupe(char* str)
{
	char* strnew = new char;
	strnew[0] = '\0';

	int nLen = strlen(str);
	int nCount = 0;
	for(int i = 0 ; i <nLen; i++)
	{
		int nnLen = strlen(strnew);
		bool flag = 0;
		for(int j = 0 ; j < nnLen; j++)
		{
			if(strnew[j] == str[i])
			{
				flag = 1;	
			}

		}
		if(!flag)
		{
		
			strnew[nCount] = str[i];
			strnew[nCount+1] = '\0';
			nCount++;
		}
		

	}
	
	return strnew;
	
}

public static String dedupe(String s){
		if(s == null || s.length() < 2){
			return s;
		}
		
		boolean used[] = new boolean[256];
		Arrays.fill(used, false);
		
		StringBuffer sb = new StringBuffer();
		char[] sc = s.toCharArray();
		for(int i = 0; i < sc.length; i++){
			if(!used[(short) sc[i]]){
				sb.append(sc[i]);
				used[(short) sc[i]] = true;
			}
		}
		
		return sb.toString();
	}

In Java:

public static String cleanString(String arg) {
		
		String result = "";
		
		for (int i = 0; i < arg.length(); i++) {
			
			char c = arg.charAt(i);
			
			if (result.indexOf(c) == -1) {
				result += c;
			}
		}
		
		return result;
	}

public static String cleanString(String arg) {
		
		String result = "";
		
		for (int i = 0; i < arg.length(); i++) {
			
			char c = arg.charAt(i);
			
			if (result.indexOf(c) == -1) {
				result += c;
			}
		}
		
		return result;
	}

public static String cleanString(String arg) {
		
		String result = "";
	
		while (arg.length() > 0) {
			
			char c = arg.charAt(0);
			
			if (result.indexOf(c) == -1) {
				result += c;
				arg = arg.replace(String.valueOf(c), "");
			}
		}
		
		return result;

}

public static String cleanString(String arg) {
		
		String result = "";
	
		while (arg.length() > 0) {
			
			System.out.println(" arg " + arg + " result " + result);
			
			char c = arg.charAt(0);
			
			if (result.indexOf(c) == -1) {
				result += c;
				arg = arg.replace(String.valueOf(c), "");
			}
		}
		
		return result;
	}

I have a phone interview with facebook.Any tips or suggestions?