My first tech interview is a DISASTER but I learned…

My face after the interview☝

Warning: I am going to throw some self-pity in the beginning, so please feel free to skip to the bolded question to see what you want.

Thanks to Flatiron school, I got my first mock technical interview on skilled.com and after that, the first thought that struck me was: I am glad that it is not a real interview because it is a total disaster!! 😢

I am not saying that because of the interviewer or the website, actually, the interviewer is incredibly nice, but because me myself is horrible. It was a coding challenge. I was so nervous and lost during the process that after 30 mins doing nothing (YES, IT IS THAT BAD) I decided not to waste my interviewer’s time and ask him to help me and explain the solution. And he did, in a clear and patient way too. I was hit so badly and decided to take a break after the interview. 😫

Ok, enough self-pity. I really want to be stronger and strengthen my ruby skills so I want to write down what I have learned here as a note for future reference. Let me show you the coding question and its solution. Promise me, don’t laugh at me when you see the question and think why would I fail on such an easy question.

QUESTION

If you are given two inputs: a flight_length: duration of the flight in minutes, and a movie array of movie times in minutes, write a method where you can return a true value if any two different movies time will combine to exactly the duration time.

SOLUTION 1

   def movie_time_equals_flight_time(movies, flight_length)
       movies.each_with_index do |m1, i|
          movies.each_with_index do |m2, j|
           target = flight_length - m1
           
           # looking for the target in the rest of the array
           if m2 == target && i != j
               return true
           end
       end
      false
    end

First thing I learned from the interview is to break down the question:

1. Start from movie[0]
2. Get the total of movie[0]+movie[1]
3. Compare the total to flight_length
4. If they are equal, return true, if not, get the total of movie[0]+movie[2], and compare that with flight_length and decide if it should return true or do the loop again.
5. Leave the inner loop when there is no element in the movie array adding movie[0] equal the flight_length.
6. Start from movie[1] and go back to step 2 to find out if any element adding movie[1] will equal to flight_length.

So since we have to iterate twice, that is very intuitive to use two nested loops. But the problem is in terms of the time complexity, let’s say there are n elements in the array, it is going to cost O(n²) time. Because when you loop over the movie array in both the outside and inside loop, they combined take O(n) * O(n) time.

SOLUTION 2

What I have learned is that I can use hash to reduce the runtime:

def movie_time_equals_flight_time(movies, flight_length)
   movie_hash = {}
   movies.each_with_index do |m, i|
     movie_hash[m] = i
   end

  movies.each_with_index do |m, i|
    target = flight_length - m
     # looking for the target in the rest of the array
    if movie_hash[target] && movie_hash[target] != i
       return true
    end
  end
 false
end

In this solution, first, we want to throw the movies array into a hash, which will turn out to be a hash looks like {80: 1, 70: 2…}. That will cost O(n) time. And then to go through the second loop, we will go through O(n) time too. So in total, the complexity will still be O(n) time. And that should cost much less time than O(n²) when the array is getting much bigger.

But why should I think of using a hash to store the data in the first place? I learned that today because when you look up an element in an array, it is linear search, so for example, if you want to get to array[2], you will have to search through the array from the beginning and go through array[0] and array[1] first and that takes 3* time searching per element.

On the other way, when you search a hash like hash[key], it is like you get the address of your friend and you can go there directly. As a result, it only costs constant time, the time would be the time searching ONE element. So that would cost much less time once n is getting much bigger. Therefore, think about implementation using hash-based data structure first when solving any problems!

My Future Plan

So again, it is not a beautiful memory today in my interview. But still, it is a valuable experience because I learn from it! 💪My future plan will be: KEEP BUILDING THINGS! And I plan to work on more ruby exercises everyday. Wish I had 48 hours a day I want to do so much. Hopefully I will be a better Rubist in the future. Plus, please let me know if there’s something I understand wrong in the above solution and thus help me grow! Any advice will be appreciated. 🙌