On a Great Interview Question

Re:On a Great Interview Question by ttoinou on Wednesday April 12, 2023 @07:26PM (#35548503)

   Some come up with a greedy algorithm which finds the first prefix that is in the dictionary, and then returns whether the rest of the string is in the dictionary

I would do that straight away. I don't see the point of implementing the more complex and longer to code "double dictionary checking for all partitions of the string"

[ Parent | on HN ]

Re:On a Great Interview Question by behdad on Wednesday April 12, 2023 @07:28PM (#35548528)

Consider the string "thereis", and the dictionary {"there", "is"}. The greedy algorithm fails.

[ Parent | on HN ]

Re:On a Great Interview Question by behdad on Wednesday April 12, 2023 @11:38PM (#35550629)

My bad. The dictionary should be {"the", "there", "is"}.

[ Parent | on HN ]

Re:On a Great Interview Question by whiddershins on Wednesday April 12, 2023 @11:58PM (#35550756)

I am now getting that I didn’t understand what you meant by greedy.

[ Parent | on HN ]

Re:On a Great Interview Question by ttoinou on Thursday April 13, 2023 @06:35AM (#35553426)

Oh yeah makes sense, if we don't do that the greedy way we could simply continue the search if it hasn't been found. That's what I would have done

[ Parent | on HN ]