Given a string, remove all chars from the string that are present in say another string called filter.

Question

filter question · Accepted Answer

put all characters from filter in a hashmap. Iterate through chars in string doing a lookup to see if char is in hashmap. If it is remove it. O(m) for insertion, O(n) for iterating through string, runtime is O(n + m) = O(n)

Ashish · Answer

Better approach:

Assign each character in the Alphabet a prime number
say
a = 2, b = 3, c = 5 and so on.. 
So we have 26 prime numbers representing characters.

Now, multiply together the filter characters' prime equivalents. 
Say, filter = ade , primeFilter = 2 * 7 * 11 = 154.

Now, scan the given string character by character, divide the primeFilter with the characters' prime equivalent

say, 'f' = 13, 154 / 13, NOT DIVISIBLE, not filtered
'b' = 3, 154/3, NOT DIVISIBLE, not filtered
'd' = '11'. 154/11, DIVISIBLE, thus filtered.

Has the same O(m+n), but is more cool. ;)

Kenjiro · Answer

Asdf, we cannot assume that we are dealing only with ASCII characters. Some alphabets may have 5000+ characters.

randm · Answer

Ashish, how do you plan to generate prime numbers?

Karthikeyan · Answer

Check the following link for the solution in Java implementation :
http://myvedham.blogspot.in/2013/03/delete-characters-contained-in-another.html?view=sidebar

Meta

Pergunta de entrevista da empresa Meta

Respostas da entrevista

Empresas seguidas

Buscas de vagas