Anyways, I had an interview for Red Hat Canada today. It was for a 16-month Software Engineering Intern position. I thing working there would be awesome, and give me a lot of experience since I would be exposed to an entire development process of a project.
The two guys that interviewed me were previously interns there, and later came back for full time positions. This was cool, cause I got to hear about their experiences with the company back when they were students.
First, they asked me a few basic questions, software engineering questions and about my past work experience:
- What do you know about this company?
- Why are you interested in working here?
- Do you have any experience with Linux and open source software?
- What kind of projects have you done in the past?
- What are the challenges of working in a team? How did you deal with a member of a team who didn't do his work or put in as much effort as the others?
- What did you do in your previous job? What did you learn? How was it?
The interview was going pretty smoothly at that point. I told them that I work in a UNIX environment at school, mentioned the team project I had in my Software Engineering class in second year and used it as an example in a few questions.
I talked about my job last term at CIBC as a Web-Application Developer. I talked about my responsibilities and also the improvements I made to the User Interface based on user feedback (they liked this part).
Then they got into the technical questions.
The interviewer informed me that they don't expect me to know the correct answer for all of the questions but they are more interested in my thought process so I should think-out-loud when answering questions and just try to think of the best solution.
- What C compiler have you used? - gcc
- The input to gcc is a source file. What is the output? - binary file
- What is the machine language in a binary file called? - Assembly
- Suppose you were writing a compiler. How would you do it? - ...
This is where things started getting tricky. They basically asked what the main parts of a compiler would be, what are the important things it needs to do. Thankfully I have read about compilers in the past so I knew what to say: lexical analysis, parsing source code, generating equivalent machine code and optimization.
- So, optimization is supposed to make the generated code more efficient. Give us an example of code that would be optimized by a compiler?
: |
When I said that to them, they answered "Well, that's the point. We wanted to give you a question that you can't answer, and then have you try to answer it. We don't expect to get the right answer from you, we just want to hear how you would approach the problem."
They quickly gave me an example: An if statement that will always evaluate to false.
This is an example of 'unreachable code'. In this case, the compiler would completely remove the if statement and its contents from the binary file, since they will have no impact on the state and execution of the program.
I gave them another example that followed this structure (code after a return statement), but I couldn't think of much else.
Another example is a loop that executes, say, always 3 times. Rather then executing the loop, the compiler might convert the loop into 3 separate blocks of code (using statements from inside the loop), eliminating the need for a loop, because it would be more efficient in assembly to write the same thing 3 times.
1) Another interesting question I was asked:
You have 2 light bulbs. There is a 100-story building and you can drop the bulbs from it, however they will break after being thrown from a specific floor or any floors above it. You can reuse a bulb thrown which does not break. Find the floor where thrown bulbs will start breaking.
I got this one right away. Try to answer it yourself and find the best case solution. Answer is given below.
2) One more:
You have an integer array of up to 1 million unique numbers between 0 and 1'000'000. One of the numbers repeats. Find the number. The solution should minimize time, memory use does not matter.
Unfortunately it took me a while to answer this one, when it shouldn't have. The solution is really easy, and I know I have solved this problem before. I gave 2 different solutions, but I couldn't find the one that minimized time. After a moment, one of the interviewers drew the problem on the board and the best solution hit me right away when I saw the drawing. See if you can figure it out. Answer is below.
ANSWERS: Obviously both problems can be solved iteratively (for #2, array must be sorted first), but that is not very efficient.
1)
Drop the first bulb every 10 floors until it breaks. Then drop the second bulb every floor through the previous 10 floors.
Example:2)
Bulb 1 dropped from floor 10, 20, 30, breaks after dropped from 40.
Bulb 2 dropped from 31, 32, breaks at 33.
Answer is 33.
Create a second array A of length 1'000'000. For each number n in your main array, increment the value at A[n]. If the value has been incremented before, you found the repeated number. You can use a boolean array too.
There was a few other technical questions, but those were the most interesting. And there ya go, that's my interview. I really didn't expect compiler questions, hehe.
I also had a chance to ask them about their work later on. It sounds like it would be a great work experience.
Well, all I can do now is wait and see what happens. I can expect the final answer some time next week.
I also had a chance to ask them about their work later on. It sounds like it would be a great work experience.
Well, all I can do now is wait and see what happens. I can expect the final answer some time next week.
Wow, I always make my blog entries long, don't I? Well, let's hope I at least start posting more often :)
