DEV Community

loading...
Cover image for Can you crack this google interview question? The maximum subsequence problem.

Can you crack this google interview question? The maximum subsequence problem.

comscience profile image kapeel kokane ・1 min read

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!

Discussion (3)

Collapse
imrj profile image
imrj

Google and their arrogant black book based interview questions, most of them with no real world applicability on their own

Collapse
jmfayard profile image
Jean-Michel Fayard πŸ‡«πŸ‡·πŸ‡©πŸ‡ͺπŸ‡¬πŸ‡§πŸ‡ͺπŸ‡ΈπŸ‡¨πŸ‡΄

@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.

A. On the hiring side, we found that brainteasers are a complete waste of time. How many golf balls can you fit into an airplane? How many gas stations in Manhattan? A complete waste of time. They don’t predict anything. They serve primarily to make the interviewer feel smart.

Years ago, we did a study to determine whether anyone at Google is particularly good at hiring. We looked at tens of thousands of interviews, and everyone who had done the interviews and what they scored the candidate, and how that person ultimately performed in their job. We found zero relationship. It’s a complete random mess, except for one guy who was highly predictive because he only interviewed people for a very specialized area, where he happened to be the world’s leading expert.

nytimes.com/2013/06/20/business/in...

Collapse
comscience profile image
kapeel kokane Author

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.

Forem Open with the Forem app