店面
First we talked about my CV, I had to tell about me and one project I did during my studies.
题目 https://leetcode.com/problems/valid-parentheses/
The interviewer modified the question using as input a general string, not only made of parenthesis. I programmed everything pretty well and quickly using a stack and helper functions to check if the character was an open parenthesis or a closed parenthesis and one to check if the closed matched the open one.
Follow Up:
Imagine you know have not only three types of parenthesis, but a huge amount of different types:
"<>", "aA", "\ /", "bB" , …, where every pair corresponds to open and closed parenthesis. How would you solve it ?
I answered that of course I don’t want to create a helper function that checks every single parenthesis type and proposed to use:
int[] positionsOpen = new int[256]
where we could store at the position of the open Parenthesis, the corresponding “closing” character position, and the same could be done using:
int[] positionsClosed = new int[256]
for the other direction of mapping.
(I could have directly used a HashMap, but probably used this kind of data structure because of the interview pressure). He said that this was fine, but then wanted me to use only one of these two arrays. After some help, I arrived to the conclusion that positionsOpen was sufficient and that we could push only the corresponding closed parenthesis to the stack, s.t. we could then just check if the peek of the stack (now a closed parenthesis) was equal to the current character. If not, we could just go on with the loop. I had to implement a new function doing this. He said that there was a small problem but he didn’t care about it because he just wanted to see if I understood the concept.
Then he asked for complexities, ( O(N) time and O(N) space) and asked what is the O(N) space case. I answered that this case occurred when the string was made of open parenthesis only.
Last but not least, he wanted to know how I could improve the program if I the stack had a capacity which was smaller than the string size. After some thinking and some help, I arrived to the following idea:
Imagine your stack has capacity 4 and the string has as first 5 characters only open parenthesis, then you would arrive at the situation where:
Stack = '(', '(', '(', '('
and the next parenthesis is open, you could check if the string has at least 5 remaining characters left, to return directly false if this was not the case. Apparently this was what he wanted to hear.
At the end he said he was happy with the results and let me ask one question about the job, which he answered on a very accurate way. (By the way, I suggest to everyone to prepare a good question to show that you researched facts about the company, my question was " I have heard from an employee that often the analytics and sales teams communicate with programmers to pass on what enhancement to the terminal seem to be in demand by clients. Do also engineers sometimes communicate with clients?"
Interview time: 1h 2min
Solved Exercise on LeetCode:
Easy 150
Medium 135
Hard 2
After 24h they invited me to the onsite interview in London.
Between the phone interview and the Onsite I have exercised all the Bloomberg questions asked within the last year, also the hard ones, solving additional:
Medium 41
Hard 15
上门
I did the onsite about one month later. It started at 12:30 in the London office. After all kind of introduction the first interview started, three engineers in total. One (a very strange person I was scared of) was talking, the other two just asked a few questions.
Question:
Given the welsh alphabet:
a b c ch d dd e f ff g ng h i j l ll m n o p ph r rh s t th u w y
and a list of strings, how would you sort the strings according to that alphabet ?
I have solved the exercise with some help, the idea was to create a hashmap with the corresponding alphabet positions of every “character” (sometimes one letter, sometimes two, thus actually a string) and to create a comparator that loops through two words (while loop) with indices that jump by 1 or by 2 and compares the characters as long as they are equal. It was not easy because you need to always take into account the possibility of having a “letter” made of two characters. I did a few mistakes which I was able to solve with a little bit of help.
Follow up:
- How do you test the code ?
- What if now you have also capital letters ? ex. “Ddaf” (dd is contained in the alphabet). I said that I would use toLoweCase() for the comparison and he was happy with that.
They let me ask some questions and the interview finished, I was really satisfied with my result. I evaluated this exercise as not an easy one (I solved about 400 leetcode ex., never seen something similar to this) and I could solve it pretty well. They told me they were going to let me know (it was the first day in London and I had to stay for two days because they said that sometimes one day is not sufficient) and escorted me out of the building. There, I realized that something went wrong. I have been waiting for the entire day and the entire morning of the day after, hoping to get a call/email where they told me to go back for the second part of the interview, but nothing.
After two months of preparation and I huge amount of solved exercises, I really didn’t know if to feel stupid or just unlucky.
I believe that a good interview experience doesn’t mean being offered cakes and biscuits with orange juice, but it means being treated not on a superficial way. I have prepared a total of two months for this interview and I don’t know how they could evaluate my performance in one 40 minutes interview (which in my opinion was not bad at all), and how they could make me (and other people) wait about 24 hours refreshing the email and hoping to have some news. At least they could have told me: “Enjoy London!”. Because all of these reasons, it has undoubtedly been the worst interview experience I have ever had. Still waiting for a feedback.
There is one thing I have learned from this long and intensive interview process: the welsh alphabet has also double letter characters!!!