Facebook Interview Question


Country: India
Interview Type: Written Test




Comment hidden because of low score. Click to expand.
5
of 7 vote

#include<stdio.h>

int main()
{
char s[1000000];
int p[257],i,j,f,r,p1,p2,k,t;
scanf("%s",s);
for(i=0;i<257;i++)
p[i]=-1;
for(i=0;s[i]!='\0';i++)
{
r=1;
p1=-1;
p2=-1;
for(j=0;p[j]!=-1;j++)
{
if(p1==-1 && p[j]==s[i])
{
p1=j;
for(k=j+1;p[k]!=-1;k++)
{
if(p[k]>s[i])
{
p2=k;
break;
}
}
if(p2>-1)
{
for(k=p1+1;k<p2;k++)
{
r=0;
for(t=i+1;s[t]!='\0';t++)
{
if(s[t]==p[k])
{
r=1;
break;
}
}
if(r==0)
break;
}
}
}
if(p2>-1 && r==1)
p[j]=p[j+1];
}
if(p2>-1 && r==1)
p[j-1]=s[i];
else if(p1==-1)
p[j]=s[i];
}
printf("\n");
for(i=0;p[i]!=-1;i++)
printf("%c",p[i]);
return 0;
}

- Ashish August 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The program satisfies both the test cases...
1)
Input: babab
Output: ba
2)
Input:
nlhthgrfdnnlprjtecpdrthigjoqdejsfkasoctjijaoebqlrgaiakfsbljmpibkidjsrtkgrdnqsknbarpabgokbsrfhmeklrle

output: tsocrpkijgdqnbafhmle

- Ashish August 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Algorithm :
Let P[] has the required unique and beautiful string and let s[] has the input string.
For each character c in s do the following steps :-
1) check for occurrence of c in P.
if(not found)
append c in P;
else
{
p1=position of c in P;
find character c1 in P after p1 which is lexicographically greater than c;
if(c1 found)
{
p2=position of c1 in P;
see whether characters between p1 and p2 are repeated in input string after c;
if(yes)
{
shift all characters from p1+1 to left by 1 position in P;
P[end]=c;
}
}
}

- Ashish August 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice greedy algorithm. One question about:
"find character c1 in P after p1 which is lexicographically greater than c;"
What if there could several c1's in P after p1 which are greater than c?

- hwer.han August 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Ashish: I may understood the question differently, but in your second output 'a' is coming before 'e', should't 'a' be the last character?

- babbupandey August 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@hwer Even if we have several c1's, taking the first c1 suffices. Because we are just checking for the condition under which we can update the position of the current character that we are looking at in the output string.

- rajkumarsaikorian August 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@babbupandey : in order to keep the most lexicographically greater characters on left preserving the order, this happens.

- Ashish August 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Ashish, this should NOT happen.

- jiangok2006 August 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Check out my solution below. The one starts with "How about this?". It has O(nlogk) time complexity where k is the number of possible distinct characters. Does the time complexity of the algo here is O(n*k)?

- Anonymous August 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Ashish : For most lexicographic order why wont we sort it in decreasing manner i.e. for [a..z] sort it according to z to a.

- Psycho August 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Ashish : If I understand the algo correctly ..I think it will give wrong output for test case abba ?
it will give ab while correct output should be ba.

- vish August 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@vish : execute n check...i got it as "ba".

- Anonymous September 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Doesn't this sounds like sort input sting in reverse order?

- daydreamer September 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Ashish : Why are we doing this ? "see whether characters between p1 and p2 are repeated in input string after c;"

- maverick September 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

what is r in your code....?? and why you are initialising them as 1,-1, -1...

- bismoy October 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

could you please explain your code little more in brief :) i feel like your algorithm isnt that clear for me...:)

- bismoy October 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Great algorithm. Here is the java version:

public static void main(String[] args) {
    assert "bac".equals(produce("abacb"));
    assert "cba".equals(produce("bacba"));
    assert "ba".equals(produce("babab"));
    assert "tsocrpkijgdqnbafhmle".equals(produce("nlhthgrfdnnlprjtecpdrthigjoqdejsfkasoctjijaoebqlrgaiakfsbljmpibkidjsrtkgrdnqsknbarpabgokbsrfhmeklrle"));
}

private static String produce(String str) {
    int[] remaining = new int[26];
    for (int i = 0; i < str.length(); i++) {
        char ch = str.charAt(i);
        remaining[ch - 'a']++;
    }

    StringBuilder output = new StringBuilder();
    for (int i = 0; i < str.length(); i++) {
        char ch = str.charAt(i);
        int prevOccIndex = output.indexOf("" + ch);
        if (prevOccIndex == -1) {
            output.append(ch);
        } else {
            int lexGreaterIndex = -1;
            for (int j = prevOccIndex + 1; j < output.length(); j++) {
                if (output.charAt(j) > ch) {
                    lexGreaterIndex = j;
                    break;
                }
            }
            if (lexGreaterIndex != -1) {
                boolean allHaveSubs = true;
                for (int j = prevOccIndex + 1; j < lexGreaterIndex; j++) {
                    if (remaining[output.charAt(j) - 'a'] <= 0) {
                        allHaveSubs = false;
                        break;
                    }
                }
                if (allHaveSubs) {
                    output.delete(prevOccIndex, lexGreaterIndex);
                    output.append(ch);
                }
            }
        }
        remaining[ch - 'a']--;
    }
    return output.toString();
}

- Safi December 10, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

I didn't understand the question correctly. If the given input string is str1, we have to 'produce' a new string str2 out of str1. So that means we might have to remove some characters from str1. So length of str2 might be less than str1. And according to the definition of beautifulness str2 can not be more beautiful than str1 because it's length might be smaller than str1 !! Can you please elaborate with an example ?

- rkt August 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

you dont have to find a more beautiful string than the input string, instead, you have to find the most beautiful subsequence from the input string which should alse be unique.

The following test cases were provided at the time of test:

Input: babab
Output: ba

Input:
nlhthgrfdnnlprjtecpdrthigjoqdejsfkasoctjijaoebqlrgaiakfsbljmpibkidjsrtkgrdnqsknbarpabgokbsrfhmeklrle


output: tsocrpkijgdqnbafhmle

- swati.2332 August 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

According to your program what will be output of string "aba"?

- Vishwanath August 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

"ba" I suppose...

- rajkumarsaikorian August 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This comment has been deleted.

- Administrator August 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Bah

- Anonymous August 06, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I am thinking of the following approach, please correct me if I am wrong:
Input = (0,10^6] length string
Read characters one by one
Keep a bitmap of the read characters, if the character has been read, then discard it and move to next
Keep a max-heap of characters, put the incoming character in the max-heap
Remove the characters from max-heap one-by-one and we will have the beautiful string

- babbupandey August 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

That would work if you're allowed to rearrange the order of s2, but it was my understanding that the only operation you were allowed to do was to delete characters from s2.

- Martin August 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I'm assuming the substring doesn't have to be contiguous.
One observation is that every unique character in s2 will be in the solution s1, the question is which one, if there are duplicates. Which one to choose depends on the character that comes after, because we want to increase lexicographical order. For example, if we have "aba", we have a choice which 'a' to take. If we choose the first one, then we the decrease lexicographical order compared to choosing the second 'a'. I propose an algorithm that steps through s2 and greedily chooses every character it sees. When it runs into a character it has already seen, there is the choice whether to keep the one it already has, or go with the newer one. That depends on which character that comes after the first occurrence. If it is 'smaller' then we keep it the first occurrence, otherwise we choose the second one.

string most_beautiful(string str) {
  vector<int> taken(256, -1);
  string partial = "";
  for (int i = 0; i < str.length(); i++) {
    char c = str[i];
    int taken_pos = taken[c];
    if (taken_pos == -1) {
      // If this character not taken before, add it
      partial += c;
      taken[c] = partial.size()-1;
    }
    else {
      if (taken_pos+1 < partial.length() &&
          partial[taken_pos+1] > c) {
        // The second occurrence is better, so delete the first one
        partial.erase(taken_pos);
        // Need to update affected indices in 'taken'
        for (int j = taken_pos; j < partial.size(); j++) taken[partial[j]] = j;
        // Add the latest occurrence
        partial += c;
        taken[c] = partial.size()-1;
      }
    }
  }
  return partial;
}

- Martin August 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

I though about the same greedy approach. But realized it will fail in certain cases.

For example:
Input: bacba
The above algo will output bca.
But the expected output is cba.

- Anonymous August 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about like this?

S: is the input string
Cnt[]: array or hash where Cnt[i] is the number of occurences of character i in S.

- In one pass, we can calculate the number of occurences of each character in S by just using hash or array.

As scanning the string from left to right,
Maintain the most beautiful string say P that could be produced from the substring 0..i for each index i.

For each i,
    - Decrement Cnt[S[i]] by 1.
    If S[i] is not in P: 
     - Append it to the P and remove all the characters in P that are smaller than S[i] and that have at least one occurence (using Cnt[]) in the substring i+1...n of S. 
    Else: 
     - Skip it.

- Anonymous August 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

One improvement to add, min heap can be used for removing the characters that are smaller than S[i]. This will give an O(nlogn) time complexity.

- Anonymous August 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

To be more precise,
O(n log(min(k,n)) ) where k is the number of possible distinct characters.
O(nlogk), if k < n
O(nlogn), if k > n
O(n) if k is assumed to be constant (e.g, 26 only alphabet letters)

- Anonymous August 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Because longer strings are always more "beautiful", and because our output string must be "unique", we know that the most beautiful valid output string should be some permutation of the unique characters in the input string. We can easily find the set of unique input characters, sort them by lexicographical value, and add them to the output string in sorted order (resulting in the optimal output string in terms of "beauty"). However, this could lead to an output string which could not be created by simply removing input characters. To fix this, we need some way of ensuring that our output character ordering exists (not necessarily consecutively) somewhere in the input string.

Eg. Imagine we have the input string INPUT == "addabacdb". Then the optimal valid output is "dbac", because it is the most beautiful unique string whose character ordering exists in INPUT. We can see this by denoting removed characters with '-': "-d--ba-c--". The lexicographically sorted set of unique characters in this example is UNQ = {'d', 'c', 'b', 'a'}. We start at UNQ[0] == 'd', and attempt to add it to the (empty) output string OUTSTR without breaking the rules. This amounts to finding the first position of 'd' in INPUT and ensuring that all the rest of the characters in UNQ ('c', 'b', 'a') can be found somewhere after that position. In this case, the first occurance of 'd' is INPUT[1], so we must ensure that 'c', 'b', and 'a' can all be found after INPUT[1]. They can, so we can safely append 'd' to OUTSTR, remove it from UNQ, and move on to the next character in UNQ. We also set CURPOS, representing the last INPUT position we added to the output, to 1.

At this point, we have:
OUTSTR = "d"
CURPOS == 1
UNQ = {'c', 'b', 'a'}

We again look at UNQ[0] == 'c'. We search INPUT, starting from CURPOS == 1, and find a 'c' at INPUT[6]. Unfortunately, one of the remaining characters in UNQ ('a') cannot be found after INPUT[6]. This means we cannot added 'c' to the output yet. So, we move on to UNQ[1] == 'b'. Searching again from CURPOS == 1, we find a 'b' at INPUT[4]. Both 'c' and 'a' can be found after INPUT[4], so we can go ahead and append 'b' to OUTSTR, remove it from UNQ, and set CURPOS = 4.

Now, we have:
OUTSTR = "db"
CURPOS == 4
UNQ = {'c', 'a'}

We start again at UNQ[0], which is still 'c', and try again to add it to the output. Starting from CURPOS == 4, we find a 'c' at INPUT[6]. However, we still cannot add 'c' to the output, because the remaining 'a' in UNQ cannot be found anywhere after INPUT[6]. We move on to UNQ[1] == 'a' and, starting from CURPOS == 4, we find it at INPUT[5]. The remaining 'c' in UNQ can be found after INPUT position 5, so we go ahead and add 'a' to OUTSTR, remove it from UNQ, and set CURPOS = 5.

Now, we have:
OUTSTR = "dba"
CURPOS == 5
UNQ = {'c'}

Because we are left with only one remaining character in UNQ, we can safely add it to OUTSTR and call it a day. OUTSTR now contains the most "beautiful" valid output string "dbac".

Here's my C++ code, with appropriate variables named to match the explanation above:

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <sstream>
#include <list>

using namespace std;

// Type that represents a unique input char and its rightmost
// position in the input string
typedef pair<char, int> unqchar;

// Comparator for unqchar's
struct compare_unqchar
{
	bool operator()(unqchar& lhs, unqchar& rhs)
	{
		return ((int)lhs.first > (int)rhs.first);
	}
};

string beautify(string INPUT)
{
	map<char, int> unqmap;

    stringstream OUTSTR;
    
    // Iterate through INPUT from left to right,
    // noting the rightmost position of each unique char. When
	// determining whether I can move a given element of UNQ to OUTSTR,
	// I will simply look at the pre-recorded rightmost input positions of the remaining
	// elements of UNQ to ensure that they exist to the right of position of the character
	// I'm trying to output.
	
    for(int i = 0; i < INPUT.size(); i++)
    {
        unqmap[INPUT[i]] = i;
    }
    
    // Sort descending by lexographic values of keys
    vector<unqchar> unqvec(unqmap.begin(), unqmap.end());
	std::sort(unqvec.begin(), unqvec.end(), compare_unqchar());

	// Copy to a list for O(1) removal, later in the algorithm
	list<unqchar> UNQ(unqvec.begin(), unqvec.end());

	int CURPOS = 0;
	while(UNQ.size() > 0)
	{
		bool restart = false;

		// Iterate through remaining chars in UNQ, trying to 
		// insert them into the output string in sorted order without breaking the rules
		for(list<unqchar>::iterator it = UNQ.begin(); it != UNQ.end() && !restart; it++)
		{
			char ch = it->first;
			
			// Search INPUT for the target char, starting from CURPOS
			for(int i = CURPOS; i < INPUT.size(); i++)
			{
				// Found the target char in the INPUT string... 
				// check if all the remaining chars in UNQ
				// can be found at positions after INPUT[i].
				// If so, add the target char to OUTSTR
				// and remove it from UNQ. If not, try the next element of UNQ.
				if(INPUT[i] == ch)
				{
					bool accept = true;

					// If any of the remaining unique chars can't be found after the target char, reject.
					for(list<unqchar>::iterator it2 = UNQ.begin(); it2 != UNQ.end() && accept; it2++)
					{
						if(it2->second < i)
							accept = false;
					}

					if(accept)
					{
						OUTSTR << ch;
						CURPOS = i;
						UNQ.remove(*it);
						restart = true;
					}
					
					break;
				}
			}
		}
	}
	
	return OUTSTR.str();
}

- Donnie DeBoer August 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yikes - sorry about the whitespace in the code. First time posting on here.

- Donnie DeBoer August 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

What is your time complexity?

- toprider September 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

{{
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
#define M 1000004
char hash[M][30],s[30],str[M];
int flag[M]={0},m[30]={0};
int main()
{
int i,j;
scanf("%s",str);
for(i=strlen(str)-1;i>=0;i--)
{
flag[i]=0;
if(i+1<strlen(str))
{
for(j=0;j<26;j++)
{
hash[i][j]=hash[i+1][j];
if(hash[i][j])
flag[i]++;
}
}
hash[i][str[i]-'a']++;
if(hash[i][str[i]-'a']==1)
flag[i]++;
//printf("%d\n",flag[i]);


}
int start=0,k=0,ii=flag[0];
while(ii)
{
int mx=ii,mxi=start;
char mxa='0';
for(i=start;i<strlen(str);i++)
{
if(flag[i]>=mx&&!m[str[i]-'a'])
{
if(mxa-'a'<str[i]-'a'||mxa=='0')
{
mxa=str[i];
mxi=i;
//printf("ii:%d i:%d c:%c\n",ii,i,mxa);
}
}
}
//printf("%c\n",str[mxi]);
m[mxa-'a']=1;
s[k++]=mxa;
for(i=start+1;i<strlen(str);i++)
{
if(hash[i][mxa-'a'])
flag[i]--;
}
ii--;
start=mxi+1;
}
s[k]='\0';
printf("\n%s\n",s);

}

}}

- Pratik kumar April 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Make a hash table of the values where each entry (of an index)contains the no of characters after the index(including it).
Then suppose the most beautiful string is found of length l then search the array for remaining (f-l) [f=total no of distinct char in the string ] length by looking the flag array,which stores the number of distinct characters after index i.
also remove the occurrences of previously chosen character from the flag array.....
Exit when l=f.

- Pratik kumar April 13, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

The time complex is O(n*K) for this solution, the K is 128 in this case.
And the time complex can be reduced into O(n*lgK) if using hash set instead of using vector<char>.

string mostBeautifulUniqueString(string sInput){
    vector<char> chars;
    for (int i = 0; i < sInput.size(); ++i)
        if (find(chars.begin(), chars.end(), sInput[i]) == chars.end())    
            chars.push_back(sInput[i]);
            
    sort(chars.begin(), chars.end());
    
    string sOutput = "";
    
    for (int i = chars.size()-1; i >= 0; --i)
        sOutput.push_back(chars[i]);
 
    return sOutput;
}

int main(void){
    string s = "";
    getline(cin, s);
    cout<< mostBeautifulUniqueString(s);
    return 0; 
}

- junyang.gao May 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

I guess we have to find the Longest (lexicographically decreasing) subsequence of the given string.

- Anonymous August 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Well, not longest AND lexicographically decreasing. Just find the longest subsequences, and if there are more than one, choose the best.

What I don't get from the question though is that s1 is reproducible from s2 by removing 'some' characters. There is nothing specified about s1 being a contiguous sequence within s2.

- Martin August 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

O(n) iterative.

#include <stdio.h>
#include <string.h>
#include <malloc.h>

static char *
most_beautiful_unique_string(const char *str, int n)
{
int a[256];
int i;
char *result = (char *)malloc(257);
char *writer = result;

while (n--) {
a[(int)*str++] = 1;
}

for (i = 255; i >= 0; --i) {
if (a[i] == 1) {
*writer++ = (char)i;
}
}

*writer = '\0';
return result;
}

- Anonymous October 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

I am assuming it is not case sensitive.

int charMap[256];

for ( i = 0; i < 256; i++) {
charMap[i] = 0;
}

for ( i = 0; i < str.length(); i++) {
charMap[str.at(i)] + =1;
}

for ( i = 0; i < str.length(); i++) {
if ( charMap[str.at(i)]) == 1) {
cout<< str.at(i);
charMap[str.at(i)] -= 1;
} else {
bool foundGreater = false;
for ( j = str.at(i) + 1; j < 256; j++ ) {
if ( charMap[str.at(j)] > 0) {
greaterFound = true;
}
}
if ( !foundGreater ) {
cout<< str.at(i)
}
charMap[str.at(i)] -= 1;

}

- Anonymous January 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

static String mostBeautifulUniquProduction(String s1){
		
		ArrayList<Character> selected = new ArrayList<Character>();
		HashMap<Character, Integer> charMap = new HashMap<Character, Integer>();
		for (int index = 0; index < s1.length(); index++){
			Integer count = 1;
			if (charMap.containsKey(s1.charAt(index))){
				count += charMap.get(s1.charAt(index));
			}
			charMap.put(s1.charAt(index), count);
		}
		
		Comparator<Character> newComparator = new Comparator<Character>() {

			@Override
			public int compare(Character o1, Character o2) {
				return -1 * (o1.compareTo(o2));
			}
		};
		PriorityQueue<Character> pQueue = new PriorityQueue<Character>(charMap.keySet().size(), newComparator);
		pQueue.addAll(charMap.keySet());
		
		
		for (int itr = 0 ; itr < s1.length(); itr++){
			if (pQueue.isEmpty()) break;
			Character biggest = pQueue.peek();
			Character key = s1.charAt(itr);
			Integer count = charMap.get(key);
			if (count == 1){
				selected.add(key);
				count -= 1;
			} else if (key.equals(biggest)){
				selected.add(key);
				count = 0;
				pQueue.poll();
			} else {
				count -= 1;
			}
			charMap.put(key, count);
		}
		return getStringRepresentation(selected);
	}
	
	static String getStringRepresentation(ArrayList<Character> list)
	{    
	    StringBuilder builder = new StringBuilder(list.size());
	    for(Character ch: list)
	    {
	        builder.append(ch);
	    }
	    return builder.toString();
	}

- cengin May 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

// this function prints the most beautiful string using C#.
// A hashtable is constructed to record the positions of each char.
// The hashtable keys are examed from the greatest (e.g. 'z) to the 
// smallest (e.g. 'a') one by one against the input string. If this char
// is duplicated, keep the first one that is greater than its next neigbor and
// delete all other occurrences by marking as spaces (do not shift chars so as
// to reduce cost). At last, print the string by ignoring spaces.
//
// Assumption: the input string does not use spaces so that spaces can be used as marker.
// If the input string does not have dup chars, the original string is printed as it is 
// already the most beautiful one.
void f(string s)
{
   HashTable<char, List<int>> h = new HashTable<char, List<int>>();
   
   //
   // construct the hash table using s, recording the positions of each char.
   //
   for(int i=0;i<s.length;++i)
   {
      if(!h.Contains(s[i]))
      {
         List<int> list = new List<int>();
         list.Add(i);
         h.Add(s[i], list);
      }
      else
      {
         h[s[i]].Add(i);
      }
   }
  
   // sort keys so that we can remove the chars from 'z' to 'a'.
   h.Keys.Sort();

   for(int i=h.Keys.Count-1; i>-1;i--)
   {
      char ch = h.Keys[i];

      // if this char has >1 occurrences
      if(h[ch].Count>1)
      {
            bool OneKept = false; // is one such char kept from deleting?

            for(int j=0;j<h[ch].Count;++j)
            {
               int idxS = h[ch][j];
               int nextNonSpace = idxS+1;

               while(nextNonSpace < s.length && s[nextNonSpace] == ' ' ) 
                    nextNonSpace++;

               if(!OneKept && (nextNonSpace >= s.length || s[idxS] > s[nextNonSpace] || j == h[ch].Count-1))
               {
                   OneKept=true;
               }
               else
               {
                   // delete other dup chars by marking as space.
                   // don't shift chars to avoid heavy cost.
                   s[idxS] = ' ';
               }
            } 
      }
   }
      
   for(int i=0;i<s.length;++i)
   {  
      if(s[i]!=' ')
      {
         Console.Write(s[i]+" ");
      }
   }
}

- jiangok2006 August 20, 2012 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More