I actually misremembered in my first post about this being three questions long. It was actually four, but the two in this were fairly similar which is why I misremembered.
In any case, from the first question it was easy to determine that I was going to go in to a downward spiral from there. From this point on we are dealing with a basic binary tree. This is laid out in a very simple way with each node has two children and a string inside of it.
Code:
struct node
{
char* name;
node* child_left;
node* child_right;
};
So the layout is really simple, basically the easiest binary tree representation one can make. So the first simple exercise to do this time around is to output the tree using regular C++ methods. The way the output is wanted is to first output the left child, then the current node, then the right child. So all we get is a function that gets a root node and spams all the output to cout. Here's what the function definition looks like.
Code:
// Example structure:
// -"bar"-
// / \
// -"foo"- nullptr
// / \
// "baz" nullptr
// prints string: "bazfoobar"
void print_string(node* root)
{
}
Fairly simple right? Now there are a couple ways to go about this. We'll just show the one that I managed to generate in my stress filled hour of time.
Code:
if (!root)
return;
print_string(root->child_left);
std::cout << root->name;
print_string(root->child_right);
Alright, top notch we did it. The code is simple and clean due to the recursion of calling itself. This is about what I got after a bit of fussing around. The only real issue with this code is the fact that we are using recursion. While it makes everything look nice, there is overhead in doing so due to having to build and destroy the callstack throughout each of the calls. Which if you're printing the binary tree you don't really care about speed anyway, so who cares. It may be something to worry about later though. If someone wants to whip up a way to do it without recursion for fun then have at it.
The next exercise is similar to the previous one, this time around we are prepending a string to the binary tree. So basically walk down the entire left side of the tree and stick it on to the very left. The function definition is as follows.
Code:
void prepend_string(node* root, char* name)
{
}
Alright, so you get a root node and a character pointer. Some additional details are that the new node is generated using regular c++ new routines, and I wasn't told if we are required to generate new address space for the new name string. For the exercise I assume you didn't, this may have been a mistake but really it's a minor implementation details.
Code:
node* current_node = root;
for(; current_node->child_left; current_node = current_node->child_left) {}
current_node->child_left = new node;
current_node->child_left->name = name;
This is roughly the code I generated at the time. Albeit it was probably a fair bit dirtier at the time of writing during the phone conversation. During this point of the interview I was getting exceedingly frazzled and my mind was dying on me from nervousness. Again, I wasn't told if I needed to allocate memory for the new name so I just did an assignment. Which if anything it would be just a simple allocate and string copy.
So these two were fairly easy to do once again, I spent far too long implementing these due to being overly nervous. Probably didn't help that during this time a large amount of vehicles were driving by due to school being let out, and I had decided to do this interview outside a coffee shop. So the next post will be the final question that I completely balls up and wasn't even able to complete even though it was another easy exercise.
