Say Hello to Pramp

My first experience with the website and the algorithm question I got asked

Alright so I’ve been out of bootcamp for 2 months now and I’ve had a lot to do. Keeping up with the latest tech events to attend, networking, applying for jobs, making sure my resume and LinkedIn look great, and on top of all of that I’ve been practicing Data Algorithms and Structures.

Recently I was introduced to Pramp a free peer 2 peer platform to bring software engineers from all directions to improve on their interview skills. It’s a really cool site where you ask someone to interview you and they interview you in return. It has options for Behavioral, Data Structures, System Design, Frontend, Applied Data Science, and Practice with a friend. For my first time I decided to jump into Data Structures and I got hit with a difficult question. I’ll review it down below 🥲.

Small example of window sliding

First off let me preface this article with that I’m not very far in my understanding of Data Algorithms and Structures. In fact I’m in the Colt Steele’s udemy course and I’m still in section 6 which is basically the first chapter. However, I still practice so that I can build the muscle and eventually get back into the course feeling a bit more confident. This question went over the knowledge that I do know from the course and pushed me to really explore how to use the tools I’ve learned.

Given an array of unique characters arr and a string str, Implement a function getShortestUniqueSubstring that finds the smallest substring of str containing in arr. Return “ ”(empty string) if such a substring doesn’t exist. Come up with an asymptotically optimal solution and analyze the time and space complexities

This was my first question and it seemed simple enough but woof it’s gonna bite if you’re not ready.

Alright so the first tool I thought to use was 2 pointers. I knew that I was going to need to traverse through the string to check against the array. I also thought to use a Frequency Counter in the question so I can make sure that there was at least 1 of each Array Letter inside of the string. As I was explaining this I wasn’t feeling all the confident about my answer and eventually asked for help from my “Interviewer” peer. They helped me flesh out a bit more that I should use a second frequency counter for the string and use those 2 pointers to create a ‘window’ that will add or subtract from the values of the second frequency counter. While it took a bit of explanation and understanding to get to this point I never got to writing out the code for this problem.

Well that only led me to try and do it on my own with the tools that I understood. I start with my variables:

1. First make 2 objects arrCounter and strCounter that will keep track of all the frequencies of the letters that we are interacting with.
2. We then create our 2 pointers i & j , set to 1 and 2 respectively
3. Last we create our currentSubstring and set it to an empty string

Then I set all of the array’s elements to keys and create their values accordingly using a helper method.

After that since I already know that no matter what i and j will be counted once we start. Even if we have one element in the array this will still work

Now for my loop on the string, originally I kept using i as the way to keep track of when to break out of the loop but after some help from a friend I decided to use j .

In the loop if we don’t have all the necessary key, values then we increase j and add to the value of the character that j is at. If we have all the necessary key, values then we move the window via i and subtract accordingly from the value of the character that i is at while on the string.

It does seem that my helper function checkEntries loops through and creates an O(n²) time. However, because it can escape if the entries don’t match at any point it might be something smaller but I’m unsure. I know that space is O(1) since I’m not making an unlimited amount of objects or anything else that increases. This solution may not be the fastest but on my machine it runs as 225ms which is definitely not the worst.

Check out full solution here:

Sources:

Practice Live Job Interviews - For Free