Editors note: To prevent painting an unsavory picture of the Bungie interview process, I edited part 1. I should have made it clear that it was my own neurosis at play, and not Bungie trying to be malicious. Though it may have come across that way, it was not my intent. If you hadn’t seen the edit, I’ll summarize: I received the test a few days later due to a glitch in the system.
I received the test in a word document. While gearing up for the test, I thought about all the different ways I could try for “extra credit.” One thing that sets me apart from other developers is my strength in a number of languages: C++, C#, Perl and Python are all languages that I can effective tackle any problem in. I thought that perhaps answering the test in all four languages might show off my skillset. After all, the position I was applying for was actually a C#/.Net Developer so why not do the test in both languages? Great, that will show them how eager I am to work for Bungie!
The test consisted of three questions:
- Write a function that is constrained for time and space that given a char* sentence, returns the sentence with the words in reverse order. Example: “How now brown cow” becomes “cow brown now How.” The function can modify the original char* array
- Write a function that is contrained for time and space that given a a linked-list with a random pointer to an arbitrary element and a pointer to the next element, returns a new copy of the linked-list with no dependancies on the orignal list. The function can modify the original linked list, but must restore the linked-list to it’s original state prior to completion
- Write a generalized Boggle program, that given a NxN board of characters, and a dictionary, returns all the possible words.
Use proper engineering principles, but understand that developer time is important. Because of the skill-set of the team reviewing your code, use only C/C++, and language and library references are okay, but no external help for the “meat” of the algorithms.
Well fuck. There goes my extra credit attempt. What else could I come up with? I could try to write a graphical implementation of Boggle, but under the time contraints, it would be a close call. I was given a week to do the project, but the HR lady said because of my “free time” I should probably finish sooner.
I let the problems sit on the backburner while I went about finishing up what I was doing.
Then it was time to tackle the problems. I had an idea of how to tackle the string and boggle problem, but not the linked list one, so I started with the string.
I came up with a simple algorithm:
- Create a temporary buffer the size of the sentence
- Keeping track of the end of a word, and the start of a word, starting from the end of the sentence, move the start-word-tracker backwards, until you find a space.
- Copy the letters between start-word-tracker+1 and end-word-tracker to the temp buffer.
- Move the end-word-tracker to where the start-word-tracker-1 is, checking to make sure you don’t move past the end of the sentence, and repeat 2-4, until you reach the beggining of the sentence
- Copy the temp buffer to the original, and return
Great, this solves the problem and only requires one-pass through the sentence plus the copies to the buffer. However it requires allocating a temporary buffer, doubling the size of memory. So time complexity O(n) and space complexity O(n). Since there is no way to iterate all the words in the sentence, time complexity O(n) is probably the best we will achieve. But we should be able to beat the space requirements. The problem description itself gave the hint: you’re free to modify the original string. So I figured out that we should be able to copy the characters in place to the original string.
Not trivial.
The algorithm I came up with for this was quite a bit more complex. It essentially swaps the last word with the first word, moving in one word space towards the middle per swap. If one word is larger than the other, we store it in a temporary variable. The problem with this, was the extra values needed to keep track of where we were in the sentence. Analysis on this approach was space complexity O(1) on the best case (we never have to reallocate a temp variable), O(m) average case and worst case. Not great, but a little better than the faster, quicker to code solution. Since this solution was a bit more kludgy I knew there had to be a better way to solve this. Unfortunately I was unable to figure out the “trick.” Turns out if you first reverse all the letters in a sentence, then reverse the letters in a word, you’ll end up with the desired answer:
“How now brown cow” => “woc nworb won woH” => “cow brown now How”
This can be done inplace (space complexity O(1)) and in linear time ( O(n) ). This is the best solution. Too bad I didn’t get it. But, what if I show the progression I made from the “obvious” answer to an answer that is slightly better. Perhaps partial credit is in order? Maybe that’s how I can show how good of a developer I am! I decided to attempt to answer the question twice: one for the obvious answer, and one for the better more optimal answer.
For the second problem, the obvious solution was to use an associative container (std::map) to store a quick lookup between the original list node, and the new list node. The algorithm looks like this:
For each list node:
- create a new list node
- store the new list node into a map, using the original list node as the key
Once complete, for each list node in the original and new list:
- Set new_list_node->random to point to map[org_list_node->random]
This works! Time complexity O(n) because we make two traversals of the list. Space complexity O(n) because we make two copies of each node used in the map. Is there a way to copy the linked-list without using a map? Of course, and the question had a hint: you can temporarily modify the original list, so long as you restore it upon program completion.
So we know we can modify the original list, but have to restore it. So that gives us essentially 4 pointers to work with: the original lists next and random pointer, and the new lists next and random pointers. The easiest way to see the algorithm is to visualize it.
First pass: create the new list, and associate it’s next pointer correctly. 
Second pass: for each element in both lists, assign new->next to original->next, and then orginal->next to new.
Third pass: for each element in both lists, assign new->random to original->random->next, iff original->random is not null.
Fourth pass: for each element in both lists, assign original->next to new->next, then new->next to orginal->next->next, iff original->next is not null.
So visually you should be able to tell what is going on. Analysis of this algorithm: Time complexity O(n), Space complexity O(1). It may be possible to improve by only doing a single pass through the linked list, but that still is O(n) [admitedly if N is large, and you end up paging, a single pass is most definitely preferred to 4...]was pretty happy with this answer.
Part 3 will have the solution to the final problem, and the conclusion to this wacky adventure! Stay tuned.