Interview Question

Software Engineer Interview(Student Candidate)

Came up with a program to take a string and printed the

  characters that appear more than once in the exact order as they are in the original string.
Answer

Interview Answer

3 Answers

1

If the characters are within ASCII, then you can consider using an Array in which the index is the ASCII value and Array value contains how many times this character appears. Then go through the string to fill in this array.

Next go through the string the second time to print the character that appears more than once, this should give you the exact order as the original string.

Time Complexity: O(2n) = O(n)

Bo on Mar 1, 2012
0

I am not sure you need to go through the array a second time. The question asks to print print the characters that appear more than once in the same exact order as they are in the original string, which means that as soon as they appear a second time, you can print them out and the order will be preserved since you would be parsing the string from left to right.

Example:

void multipleChars(const char* instr)
{
    char clut[255];
    memset(clut, 0, 255);
    char* ch = instr;
    while (*ch != 0) {
        if (clut[*ch] == 1)
            printf(*ch);
        clut[*ch]++;
        ch++;
    }
}

what am I missing?

TTY on Jan 4, 2013
0

hi tty,
so 1 2 3 3 2, 3 will be printed first while 2 comes before 3?

ryan on Mar 24, 2013

Add Answers or Comments

To comment on this question, Sign In with Facebook or Sign Up