This is a short mini-series that I'm writing about a potential job opportunity that I had available to me. I had a practical programming challenge placed upon me that was three questions long. Each question will be a part of the series.
These questions are fairly simple and straight forward, although I managed to bomb on all three of them. I was very nervous during this since it wasn't ever something I had done. The location I had chose to do three questions was also less than ideal since I was sitting at a coffee shop next to a busy street. The only thing I got told was to have a browser and a keyboard available to me. All three of these are programming challenges, in increasing difficulty with each one.
The first programming challenge is exceedingly simple
All this function does is take an string represented by a vector of characters and reverses it. The argument is passed by reference, so the result is passed in the same argument it was received in. A very simple response to this would be to use the STL's standard reverse function
That's one way of going about it, but you need to do it manually for the person that is conducting this little quiz. A naive approach is to use a temporary vector.
Alright, that's doing it ourselves, but that looks pretty ugly. Not to mention we are using a temporary vector that will end up being the same size as the string that we passed in. This memory overhead is a big no no, so we've got to reverse this string without that memory overhead. Let's do something a little bit more creative...
Now that's more like it, that's not using a stupid amount of memory and we're doing it by ourselves. This is the answer that I eventually wound up with that took a fair bit longer than I wanted. But of course, this is about me choking on three very simple problems due to me being overly nervous. We could have very easily copied how the STL does it with how their std::reverse function works.
If anyone else has any ideas how they would implement a simple vector reverse, how would you do it? The next two parts include working with simple binary trees.
----Part 2----
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.
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.
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.
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.
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.
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.
----Part 3----
Alright, the final regret in the job interview that completely blew it for me. So to recap I spent roughly 40 minutes on the previous problems getting increasingly nervous and frustrated during the entire thing. My brain as basically gone at this point, and I was working with binary trees which I don't have any direct experience with dealing with. So all around this last question was going to be a good time. So here it is , the final function that had to be implemented
That's it. That's all it was, a simple delete tree function. It iterates through all the elements of the tree and deletes them. So having a mental breakdown at this moment in time it takes me a few minutes to pump out some terrible code that uses recursion.
Still not told if we we need to allocate and destroy the C string at this point. Still doesn't really matter, since it's just a minor implementation detail. Note to those reading is that my solution at that time was not this clean and I messed it up severely multiple times before getting to that solution. But alright, that code works. The interviewer wants a non-recursive version of it. Because like we said earlier, we don't want the overhead of a bunch of recursive calls.
This bent me over and did my raw, at that moment I knew I was screwed, I had struggled with the recursive version and I'll completely blow this one. At this point I may as well as have been a stump, I was a fool, a mess, I was on the outside looking in. Screaming to myself mentally to calm down and think it through logically.
I couldn't, I was done. Ten minutes of me mumbling to myself and stuttering I hadn't had anything to show. The interviewer pitied me and gave me the answer instead. It's incredibly simple and clean, it hurt me more than any words could.
It made complete sense, the interviewer asked me if I understood how it worked. I cringed, I understood it completely. I fumbled out a few words saying I did plus some other unintelligible nonsense at the time. I had lost completely, there was nothing I could do. This is my regret, and it is one of the largest in my collection. If I redid the interview now I would still be a nervous mess just because of the companies reputation and have had wanting to work there since I was a child. I completely blew it with this company, and for that I regret.
These questions are fairly simple and straight forward, although I managed to bomb on all three of them. I was very nervous during this since it wasn't ever something I had done. The location I had chose to do three questions was also less than ideal since I was sitting at a coffee shop next to a busy street. The only thing I got told was to have a browser and a keyboard available to me. All three of these are programming challenges, in increasing difficulty with each one.
The first programming challenge is exceedingly simple
Code:
// Reverse the std::vector given.
void reverse(std::vector<char>& str)
{
}
All this function does is take an string represented by a vector of characters and reverses it. The argument is passed by reference, so the result is passed in the same argument it was received in. A very simple response to this would be to use the STL's standard reverse function
Code:
std::reverse(str.begin(), str.end());
That's one way of going about it, but you need to do it manually for the person that is conducting this little quiz. A naive approach is to use a temporary vector.
Code:
std::vector<char> rev_str;
for (auto it : str)
rev_str.emplace(rev_str.begin(), it);
str = rev_str;
Alright, that's doing it ourselves, but that looks pretty ugly. Not to mention we are using a temporary vector that will end up being the same size as the string that we passed in. This memory overhead is a big no no, so we've got to reverse this string without that memory overhead. Let's do something a little bit more creative...
Code:
const size_t string_length = str.size();
for (size_t i = 0; i < (string_length / 2); ++i)
std::swap(str[i], str[string_length - i - 1]);
Now that's more like it, that's not using a stupid amount of memory and we're doing it by ourselves. This is the answer that I eventually wound up with that took a fair bit longer than I wanted. But of course, this is about me choking on three very simple problems due to me being overly nervous. We could have very easily copied how the STL does it with how their std::reverse function works.
If anyone else has any ideas how they would implement a simple vector reverse, how would you do it? The next two parts include working with simple binary trees.
----Part 2----
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.
----Part 3----
Alright, the final regret in the job interview that completely blew it for me. So to recap I spent roughly 40 minutes on the previous problems getting increasingly nervous and frustrated during the entire thing. My brain as basically gone at this point, and I was working with binary trees which I don't have any direct experience with dealing with. So all around this last question was going to be a good time. So here it is , the final function that had to be implemented
Code:
void delete_tree(node* root)
{
// Use c++ delete
}
That's it. That's all it was, a simple delete tree function. It iterates through all the elements of the tree and deletes them. So having a mental breakdown at this moment in time it takes me a few minutes to pump out some terrible code that uses recursion.
Code:
if (!root)
return;
delete_tree(root->child_left);
delete_tree(root->child_right);
delete root;
Still not told if we we need to allocate and destroy the C string at this point. Still doesn't really matter, since it's just a minor implementation detail. Note to those reading is that my solution at that time was not this clean and I messed it up severely multiple times before getting to that solution. But alright, that code works. The interviewer wants a non-recursive version of it. Because like we said earlier, we don't want the overhead of a bunch of recursive calls.
This bent me over and did my raw, at that moment I knew I was screwed, I had struggled with the recursive version and I'll completely blow this one. At this point I may as well as have been a stump, I was a fool, a mess, I was on the outside looking in. Screaming to myself mentally to calm down and think it through logically.
I couldn't, I was done. Ten minutes of me mumbling to myself and stuttering I hadn't had anything to show. The interviewer pitied me and gave me the answer instead. It's incredibly simple and clean, it hurt me more than any words could.
Code:
std::vector<node*> elements;
elements.push_back(root);
while (elements.size())
{
auto it = elements.back();
elements.pop_back();
if (!it)
continue;
elements.push_back(it->child_left);
elements.push_back(it->child_right);
delete it;
}
It made complete sense, the interviewer asked me if I understood how it worked. I cringed, I understood it completely. I fumbled out a few words saying I did plus some other unintelligible nonsense at the time. I had lost completely, there was nothing I could do. This is my regret, and it is one of the largest in my collection. If I redid the interview now I would still be a nervous mess just because of the companies reputation and have had wanting to work there since I was a child. I completely blew it with this company, and for that I regret.