Background:
I'm not from Tier-I, II colleges. I don't work in top startups. I work in an unpopular service based startup. I applied to Google a few times with no hopes of getting a callback. A Recruiter from google called me when I was least expecting it. We scheduled a screening session. I asked for 3 months of time for the first phone interview. I never appeared for FAANG interviews earlier. After 3 months of preparation, I felt that I need some more time. After 45 more days, I appeared for the interview.

The Question:
There is a broken keyboard in which space gets typed when you type the letter 'e'. Given an input string which is the output from the keyboard. A dictionary of possible words is also provided as an input parameter of the method. Return a list of possible actual input typed by the user.

Example Input: String: "can s r n " Dictionary: ["can", "canes", "serene", "rene", "sam"]
Expected Output: ["can serene", "canes rene"]

Outcome:
The interview didn't go well. I kept trying to solve the problem using backtracking/DFS. I couldn't come up with a solution to the problem. The next morning I felt that using a Trie could be a potential approach to solve the problem. The followed up with the recruiter after a week. She responded after another week. She said that they couldn't move forward with my candidature at the moment. She offered to stay in touch and see how things turn out.

My Preparation:
I didn't realize the depth until I started my preparation.
It's been 4 years since I was out of college. So I started with easy leetcode problems. I paused to learn the data structures and algorithms which I forgot. It was difficult to prepare despite my full-time job.

The lockdown really helped me with my preparation. Due to work from home, I could easily manage both work and my preparation.

I kept making routines, followed them and restructured the routine based on my progress. Once I got familiar with popular data structures and algorithms I solved easy & medium problems on leetcode. I scheduled one mock interview every weekend.

After solving around 70 problems, I realized that I need to get back to learn concepts in depth.

I started leetcode premium. I started topic wise easy problems based on frequency. I set up pomodoro timer while solving the problems. I maintained an excel sheet of visited problems. I color coded problems that are to be visited again. I tracked the time spent on each problem.

Once I was comfortable with easy problems, I started Medium problems. I didn't go topic wise because, we should be able to recognize the topic by ourselves in the interview. I continued weekly mock interviews. I felt burnt out sometimes. I took a break to get back afresh. I used several online resources for my preparation. Some of those include leetcode, popular free mock interviewing sites, mycodeschools and many more youtube channels, MIT courses so on.

By the time of my interview, I had solved around 275 problems on leetcode. Today I'm at 300 problems. Hoping to get better with each day. "Keeping momentum is easier than building momentum" - I read this quote somewhere during this lockdown. It has been motivating me to keep up the streak.

All the best!