DEV Community

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

Posted on

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

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)

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
 
kokaneka profile image
kapeel kokane

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.