A professor wants to see if two students have cheated when writing a paper. Design a function :

hasCheated(String s1,String s2, int N) that evaluates to true if two strings have a common substring of length N.

Additional question after implementation. Assume you don't have the possibility of using String.contains() and String.substring(). How would you implement this.

Questions about complexity of my solution.

Overall a very friendly interviewer, was saying "Good" the entire time, but no idea if he wanted to keep me focused or if it was really good.

Question

A professor wants to see if two students have cheated when writing a paper. Design a function :

hasCheated(String s1,String s2, int N) that evaluates to true if two strings have a common substring of length N. 

Additional question after implementation. Assume you don't have the possibility of using String.contains() and String.substring(). How would you implement this. 

Questions about complexity of my solution.

Overall a very friendly interviewer, was saying "Good" the entire time, but no idea if he wanted to keep me focused or if it was really good.

Potential Facebooker · Accepted Answer

What about classical dynamic programming way to find longest common string? That would be O(N^2).

Sigiloso · Answer

My approach was : I searched for all the substrings in s2 of length = N and checked if s1.contains(substrings).

Ehsan · Answer

We could use a tree to store all sequences of length "N" in the first paper (O(lengthOfpaper * N)). Then read second paper and verify if any of the substrings are in the set.

Meta

Pergunta de entrevista da empresa Meta

Respostas da entrevista

Empresas seguidas

Buscas de vagas