CareerCup

static String replaceAllWords2(String original, String find, String replacement) {
    StringBuilder result = new StringBuilder(original.length());
    String delimiters = "+-*/(),. ";
    StringTokenizer st = new StringTokenizer(original, delimiters, true);
    while (st.hasMoreTokens()) {
        String w = st.nextToken();
        if (w.equals(find)) {
            result.append(replacement);
        } else {
            result.append(w);
        }
    }
    return result.toString();
}

It can be done in O(N) time by using algorithms like KMP.

I do not think it is possible or a good idea to write KMP code during interivew

use strtok to split all words based on space. go through the word list forming the new char* replacing where ever strcmp yields a match.. quick and easy but may be not optimal..

if the word to be replaced is way larger than the word itself how will this work...

tr filter in unix does it for you.
I am not sure if interviewer was expecting you to write code in c or c++ / or he wanted to know whether u know stuff beyond c/c++.
whenever u get interviewed try to understand the intent of the question rather than just start writing code.

also, question may be ambigious so he expects you to ask all questions i.e. all edge cases.

in c++ .
we can use hashset to store all words encountered in sentence and replace the word that we want.

using strtok to split sounds good option but the spliting is not always based on space it can be , or something else hence to create the new char* can get tricky.

This is simple actually. Code is lil complicated but pseudo code can be written for this.

use Sieve of Eratosthenes algorithm.. it takes space in o(n) but its a linear time algorithm..

What if put all the words in a Queue and when we are dequeuing check for the word to changed? Split the words based on spaces and enqueue them.