CODEWITHSUNDEEP
databasedata-structuresstring-matchingsuffix-tree
helloworld
helloworld

Reputation: 15

Building a suffix tree for a string matching algorithm in large database

I had an internship interview last week and I was given a question regarding searching for a particular string in a large database. I was totally clueless about it during the interview though I just gave a reply the"multi-level hashing" as that was the only hin I knew which had the best time efficiency, After a bit googling I think the answer he expected was that of suffix tree. Now during my search I found my algorithms for building suffix trees and there were even research papers on how to build suffix tree!! So is it really possible to implement the suffix tree for string matching algorithm especially during interview time?

It would be great if someone can throw light on it.

Thanks in advance

Upvotes: 1

Views: 1340

Answers (1)

Vinicius Braz Pinto
Vinicius Braz Pinto

Reputation: 8289

Usually the interviewer don't need a precise answer for these kind of questions, they're more interested in the way you think about the problem and try to solve it.

Of course, mentioning known algorithms to solve the problem would be a plus, but I find it hard to believe that someone would require "suffix tree" as an answer for that question.

That being said, I don't consider the algorithms to build suffix trees trivial to implement.

Upvotes: 3

Related Questions