In today's article, let us look at an algorithm problem related to strings.
Problem Statement
Given a main string S and a dictionary of smaller strings D
Can you find the largest string present in the dictionary that is a subsequence of the main string S?
Substring: A string a is said to be a sub-sequence of another string b if b contains all the strings present in the string a and also in the same order.
Do give it a try and compare your solution with the ones discussed in this video.
Solution
Hope that helped, Cheers!
Top comments (3)
Google and their arrogant black book based interview questions, most of them with no real world applicability on their own
@imrj
Laszlo Bock, senior vice president of people operations at Google, deserves a lot of credits for digging in the data and finding out that the Google style of interviews - that everybody copied in order to be the next Google - was a total waste of time.
nytimes.com/2013/06/20/business/in...
Well, while that is true about most of the brain teasers, it does not particularly apply to this question. It is a proper sub-sequence match problem that has several applications in Search, graph traversal, dictionaries just to state a few.