• RSS
  • Facebook
  • Twitter

Knowledge is Power.

  • Who you are ?

    Working on machines without understanding them ? Then you should be here..

  • Where you are ?

    Geographical location should not become a barrier to Share our knowledge.

  • What do you do ?

    Puzzles and Interview question are intended to be discussed here.

    Thursday, February 25, 2010

    Given a string of ASCII characters, write the write a program 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)

    Idea for an O(n) solution :

    Let’s start with ['a','b','a','c','a','a','d','b','c']
    [i:j:'a','b','a','c','a','a','d','b','c'] – [0,0,0,0] (character map for a,b,c,d)
    1st charcter is an ‘a’, it’s not in the map, so we add it and increment i&j
    ['a',i:j:'b','a','c','a','a','d','b','c'] – [1,0,0,0]
    2nd character is ‘b’, same procedure as before
    ['a','b',i:j:'a','c','a','a','d','b','c'] – [1,1,0,0]
    third character is an ‘a’, this is already in the map, so we clear the spot, and increment only i
    ['a','b',j:0,i:'c','a','a','d','b','c'] – [1,1,0,0]
    fourth character is ‘c’, which is not in the map; since i and j are different we add ‘c’ to the map, move it to position j, clear position i and increment i and j.
    ['a','b','c',j:0,i:'a','a','d','b','c'] – [1,1,1,0]
    fifth and sixth character are handled like the third
    ['a','b','c',j:0,0,0,i:'d','b','c'] – [1,1,1,0]
    seventh character is ‘d’, which is not in the map, so we handle it like the fourth one.
    ['a','b','c','d',j:0,0,0,i:'b','c'] – [1,1,1,1]
    last two are like third case.
    ['a','b','c','d',j:0,0,0,0,0]:i – [1,1,1,1]
    i has incremented beyond the range of the array so we’re done. We have j unique characters starting from position 0.
    Code :

    public static void main(String[] args) {
    char[] a = {‘a’,'b’,'a’,'c’,'a’,'a’,'d’,'b’,'c’};
    boolean[] ascii = new boolean[256];
    int j=0;
    for(int i=0;i<255;i++){
    ascii[i] = false;
    }
    for(int i=0; i {
    if(ascii[a[i]] == false)
    {
    ascii[a[i]] = true;
    a[j] = a[i];
    if (i != j)
    {
    a[i] = ‘0′;
    }
    j++;
    i++;
    }
    else if (ascii[a[i]] == true)
    {
    a[j]=’0′;
    a[i]=’0′;
    i++;
    }
    }

    0 comments:

    Post a Comment