0

This is very common interview question:

There's a all-english sentence which contains only a duplicate word, for example:

input string: today is a good day is true

output: is

I have an idea:

  1. Read every character from the string, using some hash function to compute the hash value until get a space(' '), then put that hash value in a hash-table.

  2. Repeat Step 1 until the end of the string, if there's duplicate hash-value, then return that word, else return null.

Is that practical?

whoan
  • 8,143
  • 4
  • 39
  • 48
alwaysday1
  • 1,683
  • 5
  • 20
  • 36
  • 1
    If you calculate a hash value and put it into a into a hash table then you'll be generating a hash of a hash. If you have a hash table available then just store the words in it and check for existence. – Jackson Dec 15 '14 at 11:18
  • 1
    The solution is trivial and doesn't use the fact that there is exactly one duplicate in any way. I suspect this is a corruption of a quite different problem. – n. m. could be an AI Dec 15 '14 at 11:19
  • 1
    @n.m. How can you exploit the fact that there is exactly one duplicate ? IMO the only implication is that if you found no duplicate before the last word, you are done. The proposed solution is already pretty efficient, O(NC) in the number of characters and (close to) O(NW) in the number of words, what better can you do ? –  Dec 15 '14 at 13:05
  • @YvesDaoust I don't think you can exploit it, I think the problem is a product of nutation of a different problem, where the fact was exploitable. – n. m. could be an AI Dec 15 '14 at 14:45

3 Answers3

2

Your approach is reasonable(actually the best I can think of). Still take into account the fact that a collision may appear. Even if the hashes are the same, compare the words.

Ivaylo Strandjev
  • 69,226
  • 18
  • 123
  • 176
0

It would work, but you can make your life a lot easier.

Are you bound to a specific programming language?

If you code in c# for example, i would suggest you use the String.Split function (and split by " ") to transform your sentence into a list of words. Then you can easily find duplicates by using LINQ (see How to get duplicate items from a list using LINQ?) or by iterating through your list.

Community
  • 1
  • 1
H W
  • 2,556
  • 3
  • 21
  • 45
0

You can use the Map() function, and also return how many times the duplicate word is found in the string.

var a = 'sometimes I feel clever and sometimes not';

var findDuplicateWord = a => {
  var map = new Map();
  a = a.split(' ');

  a.forEach(e => {
    if (map.has(e)) {
      let count = map.get(e);
      map.set(e, count + 1);
    } else {
      map.set(e, 1);
    }
  });

  let dupe = [];
  let hasDupe = false;
  map.forEach((value, key) => {
    if (value > 1) {
      hasDupe = true;
      dupe.push(key, value);
    }
  });
  console.log(dupe);
  return hasDupe;
};

findDuplicateWord(a);

//output
/* Native Browser JavaScript  
[ 'sometimes', 2 ]
=> true */
Morris S
  • 2,337
  • 25
  • 30