Many technical companies, particularly ones that require plenty of problem solving like to pose technical problems to interviewees to gauge how it is they think through potential problems they’ll run into at their new job. Although the answer themselves aren’t necessarily as important as your ability to display how you think through these problems, having a few practiced out can help with what can be a stressful situation.
Question 1: Algorithm Questions
Interviewers love to give algorithm questions, and this is because they test two things: 1. They test how many types of typical computing problems you’ve encountered before, and 2. they let you gauge problem solving skills. In software development a lot of solutions are simply rephrased solutions to typical problems. Look at arrays, anyone who’s used them for any amount of time has probably run into several of these problems already. Enumerating arrays, sorting them , finding an element, etc. If you can’t come up with a potential solution to these problems then that is very scary to an employer. More importantly however is that you demonstrate the ability to tackle the problem if you don’t know right off the bat how to solve it. In this example I’ll give the one I’ve been asked and heard of people being asked the most.
In objective C a lot if not all of our list organization is done with NSCollections, but there are other data structures that have their own pros and cons to arrays. In this case it is the linked list. Instead of having every element of the list lined up in order after the first list element, each element contains at least two pieces of information: The object the list node stores, and a pointer to the next list node. Then there’s also the doubly linked list which simply has an additional pointer that points to the previous list node.
Remember even though you may not have the best solution to this problem already, you should be able to formulate a plan to how you might solve this, and it’s your ability to do this that’s most important. I might ask myself, how does a linked list iterate through itself? It does so by having a pointer pointing to the current node, and for every iteration, it becomes the current node’s next node. OK, now how do we know if the list is looped? Well how about we draw a node diagram with a loop to help us?
Now the problem becomes more clear. I know the most optimal solution, but previously I’ve answered this problem by adding a boolean for each node that remembers if the function has iterated through the current node yet, and if it has you know the list is looped. The optimal solution, which you may or may not arrive at yourself in the allotted time is to have two pointers going through the loop, one that grabs the next list node for each iteration, and one that grabs the next-next list node. This way, when you go through the list, one will do so at twice the speed. If there is a loop in the list then the fast pointer will eventually point to the same node, and when it does you return that the list is in fact a loop. And if any of the pointers reach a null, then you know you’ve reached the end of a list and haven’t looped.
boolean hasLoop(Node first) {
// list does not exist..so no loop either.
if(first == null)
return false;
Node slow, fast; // create two references.
// make both refer to the start of the list
slow = fast = first;
while(true) {
slow = slow.next; // 1 hop.
if(fast.next != null)
fast = fast.next.next; // 2 hops.
else
return false; // next node null => no loop.
// if either hits a null pointer, it's not a
if(slow == null || fast == null) loop.
return false;
// if the two ever meet...we must have a loop.
if(slow == fast)
return true;
}
}I personally wouldn’t implement this in objective c, since this isn’t ever a problem you’d run into since this is all implemented for you. However if you have to inline new functions for whatever reason this is how you’d do it in C++. Even though iOS handles this all within its core framework, being able to go through the steps to solve this problem goes a long way towards demonstrating the right problem solving skills that iOS developers are expected to have.
Question #2 : Faulty Code Questions
Many times employers will come prepared with samples of code that have a known problem in it and its up to you to figure it out. Considering that much of your time as a developer is spent debugging code of your own or sometimes even code that others have written, this is an important skill to demonstrate.
Imagine you wanted to record the time that your application was launched, so you created a class that defined a global variable in its header: NSString *startTime;. Then, in the class’ implementation, you set the variable as follows:
+ (void)initialize {
NSDateFormatter *formatter = [[NSDateFormatter alloc] init];
[formatter setDateStyle:NSDateFormatterNoStyle];
[formatter setTimeStyle:NSDateFormatterMediumStyle];
startTime = [formatter stringFromDate:[NSDate date]];
}
If you then added the following line to the application:didFinishLaunchingWithOptions:method in your AppDelegate:
NSLog(@"Application was launched at: %@", startTime);
what would you expect to be logged in the debugger console? How could you fix this to work as expected?
The problem with this code is that the global date object, startTime was never set.
Question 3: Under the hood functionality
There are many situations where understanding how the program is beneficial. One question that seems to come up very frequently on blogs and developers websites seems to relate to the ARC (Automated Reference Counter) which determines what referenced objects aren’t being used any more and can be removed from memory. Retain counts are the way in which memory is managed in Objective-C. When you create an object, it has a retain count of 1. When you send an object a retain message, its retain count is incremented by 1. When you send an object a release message, its retain count is decremented by 1. When you send an object a autorelease message, its retain count is decremented by 1 at some stage in the future. If an objectʼs retain count is reduced to 0, it is deallocated.
Mark's Pattern Buffer 