About 2 months ago, I was notified by a friend, about some job openings for Software Engineers, at her company. I am pretty comfortable in my current position, but this other company looks pretty cool. Things like flex time, no dress code, high tech environment, and free coffee, makes me think that it could be the perfect job.
After a couple hours of research, it also looks like this company has high standards and employs really talented people. Not just a “Web Development” company, they expect you to understand Big O notation, and different design patterns. I consider myself an “Average Web Geek”, but I did receive a Masters in Computer Science, and my interests have always leaned more towards the engineering of software, compared to the assembly line culture that some IT companies represent.
I talked to the recruiter of this company, pretty standard stuff. She tells me that there are 4 phases to the interview process. There is first contact, that is that talk with the recruiting officer. Then there is a “homework” assignment, so the engineers can evaluate my initial coding skills. Then there is a phone interview with an engineer. Finally, there is a face-to-face. With the exception of the “homework” it is pretty standard.
Now, I should explain, I enjoy my job. But I am frustrated by the lack of a technical track. My company is looking for people to build web sites, then spend the rest of their professional lives as non-technical managers. I am also realizing there is a significant amount of co-workers who do not take as much pride as I do in engineering, and innovation. I consider myself the “Average” web geek, because I don’t see myself as anything special. Though, when I look around my office, I see a lot of people who are comfortable with their position, and the fact that they have no need to advance their knowledge, or experience. So, as happy as I am, I need to expand, and continue to advance my technical experience. This other company looks to have the direction I want to focus on.
The recruiter sends me the assignment. There are a couple questions about object oriented programming, and a Java interface for which I am required to supply an implementation. Question 1 is “What is an abstract class? Describe a common pattern that requires the use of abstract classes?” This is interesting. Normally I would use this as a question in a phone interview. It is a pretty basic question to test someone's basic object oriented knowledge. The other questions are specific to Java.
Based on the Job description, I know that they want an engineer with a large amount of Java experience, along with Spring, Hibernate, and JUnit. So, even though it isn’t required, I make sure that the code I send with the implementation class, contains these these concepts.
After a couple weeks, I hear back from them. They want to to set up a phone interview with a Lead Engineer. At this point, I am pretty excited. They seem like a pretty high tech company, with some really smart employees. So, I agree with excitement. The call comes in a couple days later. I take the call in the parking lot of a Trader Joes. I was expecting the interviewer to ask about my Java experience, shoot me some questions about Spring and Hibernate. Maybe test my knowledge of Java core concepts. But no, he hits me with a question to evaluate how I think.
He says “Lets say you are designing a card game, and you need a method to shuffle the cards. Describe the algorithm to do it.”
This question is very familiar, since I had it as a test question in my algorithms class during my graduate studies. Unfortunately, that was about 8 years ago. Though it shouldn’t be too hard. So, my first answer is to use 2 arrays. 1 contains 52 Card objects, and the other is empty. Then, using a random number generator, I would grab cards at random, and store them in the other array. Now, my current job hardly requires me to consider algorithms which are really speedy. Our datasets are small, and the schedules are short. So, usually the first solution is fine. So, I was expecting his next question… “What about the blank cells in the original array? Are you concerned about those?”
Yes, of course. So, without thinking about redesigning the algorithm, I tell him that each time we remove a Card object, we can recreate the array with the size decremented. As I am talking I am realizing how stupid, and inefficient this sounds. So I say, “It will work, but it isn’t efficient.” He then asks me to describe the performance in Big O notation. So…. there are n Card objects in the array (n = 52) , looping through the array n times to remove the Card objects. Then I would recreate the array as n-1, for each card. That is n*(n-1). Making the performance O(n^2), aka quadratic. Not very good considering that there is a better way.
After a couple minutes, it comes to me. There is actually a much simpler solution. I don’t need 2 arrays. Using just the original array of Card objects, I can generate 2 random numbers, and swap the cards. The random number generator, and swap function, would run in constant time, O(1). That leave the number of iterations. Therefore, the performance is O(n), aka linear. Much better.
The following code represents this algorithm:
public static void shuffleCards(Card[] deck) {
Random generator = new Random();
// shuffle the cards
for (int i = 0 ; i < deck.length ; i ++) {
int x1 = generator.nextInt(n) + 1;
int x2 = generator.nextInt(n) + 1;
Card card1 = deck[x1];
Card card2 = deck[x2];
deck[x1] = card2;
deck[x2] = card1;
}
}
This was the answer he was looking for. At this point, I could have pointed out that the code could be simplified by using the java.util.Collections class, which has a shuffle(List<?> list) method, and runs in linear time.
The phone interview continues with me asking questions about companies, and him asking a couple more questions about my experience. I guess I made an impression, since the recruiter schedules a series of face-to-face interviews. That will happen in the next week. So we would see what happens.
The moral of the story is, that there is a difference between being a average web coder, and a software engineer. I want to see what else is out there, so I have to break out of my IT shell and focus on the foundations which I learned in those Computer Science courses. It is very easy to grow comfortable and content in a stable position. But time keeps moving, and if you don’t keep learning, you can find yourself stuck. I hope one day I’ll consider myself to be more then just an Average Web Geek.
Posts
