I applied through a consultancy firm, and my resume was shortlisted. A Walmart Labs recruiter was very eager to set up a telephonic interview as quickly as possible, citing the urgency to fill the position. The telephonic interview was scheduled for a week after the discussion with the recruiter.

The interviewer asked me about my current and prior projects. After that discussion (about 8-10 minutes), he asked an algorithm-related question. I came up with a solution, but it was not optimal. He then asked another algorithm question. My initial answer was not optimal, but with a few hints, I came up with an optimal solution. I was asked to write pseudocode for it, which I did correctly to the best of my knowledge.

I was informed that HR would get in touch with me "soon." However, there has been no communication from HR in over three weeks.

Given two strings, S1 and S2, find if S2 is a substring of S1 in O(n) time (where n is the size of string S1).