Skip to content
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 twitter logo github logo ・1 min read

Do you think you can? (3 Part Series)

1) Can you answer this google interview question? 2) Can you solve the fastest horse 🐴 algorithm problem? 3) 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!

twitter logo DISCUSS (3)
Discussion
markdown guide
 

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

 

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.

 

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

Classic DEV Post from Oct 25 '19

Add google-like search query to your website or Database

kapeel kokane profile image
Coder by day, Content creator by night, Learner at heart!