How is this possible?
-
Tim ONeil wrote:
// then add a reasonable set of unit tests, with output, to main.cpp.
You are supposed to add code in main to display the values, which you extract by repeated calls to the
topandpopfunctions. The call totopgives you a reference to the value at the top of the stack. So you can display that withcout/printf. Follow that with a call topopand the value you just looked at is now removed, ready for the next call totop. And so on. -
Right. All my attempts, including reinterpret_cast, to instantiate the _node class, which is private in _stack, yield compile errors.
-
Right. All my attempts, including reinterpret_cast, to instantiate the _node class, which is private in _stack, yield compile errors.
Here is a version that builds, but without most of the implementation. I am not sure how much this differs from what you tried.
typedef int T; // I am not sure about this, but it seems to work.
#include "stack.h"
#includetemplate
stack::stack()
{
_head = nullptr;
_size = 0;
}template
stack::~stack()
{
// empty destructor
}template
size_t stack::size() const
{
//return the size of the stack
return _size;
}template
T& stack::top() const
{
//return a reference to the top value. Throw an exception if the stack is empty.
return _head->_data;
}template
void stack::push(const T& item)
{
//push a new value onto the stack
}template
void stack::pop()
{
//remove the top value from the stack. Do nothing if the stack is empty.
}template
void stack::invert()
{
//reverse the order of the entire stack, so that 1,2,3,4,5 becomes 5,4,3,2,1 and so on.
}int main()
{
stack myStack;
std::cout << "stack size = " << myStack.size() << std::endl;return 0;}
-
I recently lost out on a great job because I couldn't pass the coding challenge. I was given a header file that I COULD NOT modify, and asked to fill it out with a stack with a linked list backbone. The problem was to reverse stack data (integers) such that nodes 1..4 contained 1, 2, 3, 4, and the output would be 4, 3, 2, 1. I easily wrote this, with one problem: none of the methods in the class signatures contained any output method other than top(), which returned the top node. Everything else was a void method. So I modified the size() method t]such that it output the values of each node. I believe this is where I failed. The code contained a "node" class with a data member and a pointer to the next node. The stack class had a pop method, a push method, that size method, top, and that's about it. Both were templates. Other than adding a friend class or resorting to dirty pointer tricks, I could not figure out how to display the data members of the node class. I really don't understand how this is a valid problem to pose. Here is the header I was given: #include #pragma once //a basic stack class. //Implement all member functions in the file stack.cpp. // then add a reasonable set of unit tests, with output, to main.cpp. //Don't modify stack.h or CMakeLists.txt at all, unless you spot a mistake. template struct _node { T _data; _node* _next; _node(const T&, _node*); ~_node(); }; template class stack { private: _node* _head; size_t _size; public: stack(); ~stack(); size_t size() const; //return the size of the stack T& top() const; //return a reference to the top value. Throw an exception if the stack is empty. void push(const T&); //push a new value onto the stack void pop(); //remove the top value from the stack. Do nothing if the stack is empty. void invert(); //reverse the order of the entire stack, so that 1,2,3,4,5 becomes 5,4,3,2,1 and so on. //Your function should work in the most effecient way you can devise, ideally without allocating any memory on the heap. };
Sorry for the late reply, busy day :) The good news is that you should be happy you didn't get the job. I'm fairly sure it would have been a miserable work environment. Who in this day and age still hires based on such "code challenges"? What they forgot is that the code challenge tells as much about the one who wrote it as it does about the one who solves it. In this case: - have they not heard that names starting with underscores are reserved the implementation? It says: "we are such primadonnas we don't care about frigging standards!" - you have
_node(const T&, _node*);Who is "T" and "t"? You should at least bother to run your header through a compiler to see you that you don't have any syntax errors. If you are at it, look also for a spell-checker: it's "efficient" not "effecient". This shows lack of respect for the person you are interviewing. -template struct _nodeSeriously? Show me the compiler that doesn't flag it as an error. - the instructions suck also: "Implement all member functions in the file stack.cpp" Have you not heard that template implementations are normally in the same .h file? If I put it in stack.cpp, then in main.cpp I have to include "stack.cpp". Yey! The code itself is fairly bland. I suspect they wanted to see you do some pointer acrobatics in the "invert" member function:template
_node::_node (const T& dat, _node* ptr) :
_data (dat),
_next (ptr)
{
}template
_node::~_node ()
{
}template
stack::stack () :
_size (0),
_head (nullptr)
{
}template
stack::~stack ()
{
while (_head)
{
_node* ptr = _head->_next;
delete _head;
_head = ptr;
}
}template
size_t stack::size () const
{
return _size;
}template
T& stack::top () const
{
if (!_size)
throw std::exception ("empty_stack");return _head->_data;
}template
void stack::push (const T& data)
{
_node* node = new _node (data, _head);
_head = node;
_size++;
}template
void stack::pop ()
{
if (!_size)
return;_node* ptr = _head->_next;
delete _head;
_head = ptr;
--_size;
}template
void stack::invert ()
{
_node* prev = nullptr;
_node* crt = _head;
while (crt)
{
_node* next = crt->_next;
crt->_next = prev;
prev = crt;
crt = next;
}
_head = prev;
}I don't wa
-
Sorry for the late reply, busy day :) The good news is that you should be happy you didn't get the job. I'm fairly sure it would have been a miserable work environment. Who in this day and age still hires based on such "code challenges"? What they forgot is that the code challenge tells as much about the one who wrote it as it does about the one who solves it. In this case: - have they not heard that names starting with underscores are reserved the implementation? It says: "we are such primadonnas we don't care about frigging standards!" - you have
_node(const T&, _node*);Who is "T" and "t"? You should at least bother to run your header through a compiler to see you that you don't have any syntax errors. If you are at it, look also for a spell-checker: it's "efficient" not "effecient". This shows lack of respect for the person you are interviewing. -template struct _nodeSeriously? Show me the compiler that doesn't flag it as an error. - the instructions suck also: "Implement all member functions in the file stack.cpp" Have you not heard that template implementations are normally in the same .h file? If I put it in stack.cpp, then in main.cpp I have to include "stack.cpp". Yey! The code itself is fairly bland. I suspect they wanted to see you do some pointer acrobatics in the "invert" member function:template
_node::_node (const T& dat, _node* ptr) :
_data (dat),
_next (ptr)
{
}template
_node::~_node ()
{
}template
stack::stack () :
_size (0),
_head (nullptr)
{
}template
stack::~stack ()
{
while (_head)
{
_node* ptr = _head->_next;
delete _head;
_head = ptr;
}
}template
size_t stack::size () const
{
return _size;
}template
T& stack::top () const
{
if (!_size)
throw std::exception ("empty_stack");return _head->_data;
}template
void stack::push (const T& data)
{
_node* node = new _node (data, _head);
_head = node;
_size++;
}template
void stack::pop ()
{
if (!_size)
return;_node* ptr = _head->_next;
delete _head;
_head = ptr;
--_size;
}template
void stack::invert ()
{
_node* prev = nullptr;
_node* crt = _head;
while (crt)
{
_node* next = crt->_next;
crt->_next = prev;
prev = crt;
crt = next;
}
_head = prev;
}I don't wa
That was my first thought too, that the company's culture, or at least this part of it, must be shite.
Robust Services Core | Software Techniques for Lemmings | Articles
-
Sorry for the late reply, busy day :) The good news is that you should be happy you didn't get the job. I'm fairly sure it would have been a miserable work environment. Who in this day and age still hires based on such "code challenges"? What they forgot is that the code challenge tells as much about the one who wrote it as it does about the one who solves it. In this case: - have they not heard that names starting with underscores are reserved the implementation? It says: "we are such primadonnas we don't care about frigging standards!" - you have
_node(const T&, _node*);Who is "T" and "t"? You should at least bother to run your header through a compiler to see you that you don't have any syntax errors. If you are at it, look also for a spell-checker: it's "efficient" not "effecient". This shows lack of respect for the person you are interviewing. -template struct _nodeSeriously? Show me the compiler that doesn't flag it as an error. - the instructions suck also: "Implement all member functions in the file stack.cpp" Have you not heard that template implementations are normally in the same .h file? If I put it in stack.cpp, then in main.cpp I have to include "stack.cpp". Yey! The code itself is fairly bland. I suspect they wanted to see you do some pointer acrobatics in the "invert" member function:template
_node::_node (const T& dat, _node* ptr) :
_data (dat),
_next (ptr)
{
}template
_node::~_node ()
{
}template
stack::stack () :
_size (0),
_head (nullptr)
{
}template
stack::~stack ()
{
while (_head)
{
_node* ptr = _head->_next;
delete _head;
_head = ptr;
}
}template
size_t stack::size () const
{
return _size;
}template
T& stack::top () const
{
if (!_size)
throw std::exception ("empty_stack");return _head->_data;
}template
void stack::push (const T& data)
{
_node* node = new _node (data, _head);
_head = node;
_size++;
}template
void stack::pop ()
{
if (!_size)
return;_node* ptr = _head->_next;
delete _head;
_head = ptr;
--_size;
}template
void stack::invert ()
{
_node* prev = nullptr;
_node* crt = _head;
while (crt)
{
_node* next = crt->_next;
crt->_next = prev;
prev = crt;
crt = next;
}
_head = prev;
}I don't wa
I think you missed the point which said "you must not modify stack.h". Part of the test is to keep the implementation separate from the header. Yes, I know purists would say that is wrong, but it is perfectly acceptable in the context of this test. And the difference between the lower case
tand upper caseTis important for the implementation. -
I think you missed the point which said "you must not modify stack.h". Part of the test is to keep the implementation separate from the header. Yes, I know purists would say that is wrong, but it is perfectly acceptable in the context of this test. And the difference between the lower case
tand upper caseTis important for the implementation.Maybe you can add some explanations an I might learn something from this. I'm using Visual Studio 2019 and it barks at me for
template struct _node. I'm sorry but if I want to go ahead I need to change stack.h. After I change it totemplate struct _node(that seems the only plausible alternative to me), and I put the my code in stack.cpp, all goes well until link time when it says it cannot find the implementation functions. This is normal (in my mind) because the templates haven't been instantiated. How is the compiler to know that it needs to generate a stack of "int" when compiling stack.cpp and how it can generate said stack when compiling main.cpp. I could probably force it to create one by placing an instantiation of stack in stack.cpp. No one does anything like that.Mircea
-
Maybe you can add some explanations an I might learn something from this. I'm using Visual Studio 2019 and it barks at me for
template struct _node. I'm sorry but if I want to go ahead I need to change stack.h. After I change it totemplate struct _node(that seems the only plausible alternative to me), and I put the my code in stack.cpp, all goes well until link time when it says it cannot find the implementation functions. This is normal (in my mind) because the templates haven't been instantiated. How is the compiler to know that it needs to generate a stack of "int" when compiling stack.cpp and how it can generate said stack when compiling main.cpp. I could probably force it to create one by placing an instantiation of stack in stack.cpp. No one does anything like that.Mircea
Mircea, here is my implementation, using the original unchanged stack.h file. Like you I would not choose to do it this way, but I was trying to follow the rules as defined by the people who set the test. The key (which I originally struggled with) is the
typedefat the beginning of stack.cpp. I have not implemented the destructors, as they are not important for the purpose of this test. And the two helper functions (pusher&popper) are just to save a bit of typing. I welcome your feedback.#include
typedef char* T; // this implementation will use simple C-style strings
#include "stack.h"template
_node::_node(const T& item, _node* next)
{
_data = item;
_next = next;
}template
_node::~_node()
{}
template
stack::stack()
{
_head = nullptr;
_size = 0;
}template
stack::~stack()
{
// empty destructor
}template
size_t stack::size() const
{
//return the size of the stack
return _size;
}template
T& stack::top() const
{
//return a reference to the top value. Throw an exception if the stack is empty.
if (_size == 0)
throw std::exception("Stack contains no items");return \_head->\_data;}
template
void stack::push(const T& item)
{
//push a new value onto the stack
_node* newNode = new _node(item, _head);
_head = newNode;
_size++;
}template
void stack::pop()
{
//remove the top value from the stack. Do nothing if the stack is empty.
if (_size > 0)
{
_node* popNode = _head;
_head = popNode->_next;
delete popNode;
_size--;
}
}template
void stack::invert()
{
//reverse the order of the entire stack, so that 1,2,3,4,5 becomes 5,4,3,2,1 and so on.
if (_size > 1)
{
_node* current = _head;
_node* next = nullptr;
_node* temp;while (current) { temp = current->\_next; current->\_next = next; next = current; current = temp; } \_head = next; }}
void pusher(stack& theStack, T* items)
{
while (*items != 0)
{
theStack.push(*items);
std::cout << "Push " << *items << " onto the stack" << std::endl;
items++;
}
std::cout << " Top item = " << -
Maybe you can add some explanations an I might learn something from this. I'm using Visual Studio 2019 and it barks at me for
template struct _node. I'm sorry but if I want to go ahead I need to change stack.h. After I change it totemplate struct _node(that seems the only plausible alternative to me), and I put the my code in stack.cpp, all goes well until link time when it says it cannot find the implementation functions. This is normal (in my mind) because the templates haven't been instantiated. How is the compiler to know that it needs to generate a stack of "int" when compiling stack.cpp and how it can generate said stack when compiling main.cpp. I could probably force it to create one by placing an instantiation of stack in stack.cpp. No one does anything like that.Mircea
-
Mircea, here is my implementation, using the original unchanged stack.h file. Like you I would not choose to do it this way, but I was trying to follow the rules as defined by the people who set the test. The key (which I originally struggled with) is the
typedefat the beginning of stack.cpp. I have not implemented the destructors, as they are not important for the purpose of this test. And the two helper functions (pusher&popper) are just to save a bit of typing. I welcome your feedback.#include
typedef char* T; // this implementation will use simple C-style strings
#include "stack.h"template
_node::_node(const T& item, _node* next)
{
_data = item;
_next = next;
}template
_node::~_node()
{}
template
stack::stack()
{
_head = nullptr;
_size = 0;
}template
stack::~stack()
{
// empty destructor
}template
size_t stack::size() const
{
//return the size of the stack
return _size;
}template
T& stack::top() const
{
//return a reference to the top value. Throw an exception if the stack is empty.
if (_size == 0)
throw std::exception("Stack contains no items");return \_head->\_data;}
template
void stack::push(const T& item)
{
//push a new value onto the stack
_node* newNode = new _node(item, _head);
_head = newNode;
_size++;
}template
void stack::pop()
{
//remove the top value from the stack. Do nothing if the stack is empty.
if (_size > 0)
{
_node* popNode = _head;
_head = popNode->_next;
delete popNode;
_size--;
}
}template
void stack::invert()
{
//reverse the order of the entire stack, so that 1,2,3,4,5 becomes 5,4,3,2,1 and so on.
if (_size > 1)
{
_node* current = _head;
_node* next = nullptr;
_node* temp;while (current) { temp = current->\_next; current->\_next = next; next = current; current = temp; } \_head = next; }}
void pusher(stack& theStack, T* items)
{
while (*items != 0)
{
theStack.push(*items);
std::cout << "Push " << *items << " onto the stack" << std::endl;
items++;
}
std::cout << " Top item = " <<Aha! You didn't respect the requirements either: "then add a reasonable set of unit tests, with output, to main.cpp" :) If you move your main to a different CPP file you will run into errors. The other thing I don't understand is why you mix the "T" and "t". Otherwise your implementation is almost exactly like mine. In the invert function, I like my variable names (prev, crt, next) a bit more than yours but this is such a stylistic detail that I'm not going to argue about. I did mention it however because I'm a bit anal :) (Some people would call me an anal a..hole but that's a bit pleonastic, isn't it?).
Mircea
-
Aha! You didn't respect the requirements either: "then add a reasonable set of unit tests, with output, to main.cpp" :) If you move your main to a different CPP file you will run into errors. The other thing I don't understand is why you mix the "T" and "t". Otherwise your implementation is almost exactly like mine. In the invert function, I like my variable names (prev, crt, next) a bit more than yours but this is such a stylistic detail that I'm not going to argue about. I did mention it however because I'm a bit anal :) (Some people would call me an anal a..hole but that's a bit pleonastic, isn't it?).
Mircea
Mircea Neacsu wrote:
add a reasonable set of unit tests, with output, to main.cpp"
Ah you caught me, I will try that sometime and let you know how it goes. I did not mix "T" and "t", they are set like that in the header file. So I found a way to implement the code without changing them. As I said earlier, I would not do it this way if I had the choice.
Mircea Neacsu wrote:
I like my variable names (prev, crt, next)
I have to admit it took me a few goes to get that right, hence the names which (at the time) seemed most reasonable.
Mircea Neacsu wrote:
a bit pleonastic
I am embarrassed to admit that I had to check my dictionary for "pleonasm". I had assumed you are Romanian, but your bio says Canadian; that makes me feel a bit better.
-
Mircea Neacsu wrote:
add a reasonable set of unit tests, with output, to main.cpp"
Ah you caught me, I will try that sometime and let you know how it goes. I did not mix "T" and "t", they are set like that in the header file. So I found a way to implement the code without changing them. As I said earlier, I would not do it this way if I had the choice.
Mircea Neacsu wrote:
I like my variable names (prev, crt, next)
I have to admit it took me a few goes to get that right, hence the names which (at the time) seemed most reasonable.
Mircea Neacsu wrote:
a bit pleonastic
I am embarrassed to admit that I had to check my dictionary for "pleonasm". I had assumed you are Romanian, but your bio says Canadian; that makes me feel a bit better.
Quote:
I had assumed you are Romanian, but your bio says Canadian; that makes me feel a bit better.
I am Romanian but I've called Canada home for many years now. Too bad my accent is not as good as my vocabulary :)
Mircea
-
Quote:
I had assumed you are Romanian, but your bio says Canadian; that makes me feel a bit better.
I am Romanian but I've called Canada home for many years now. Too bad my accent is not as good as my vocabulary :)
Mircea
Canada has long been a favourite place although I have not spent nearly enough time there. My brother lives in Toronto, about 10 minutes drive from CodeProject HQ (according to Google). Visited there in 2008 for a wedding, and also went up to Manitoulin island to stay with an aunt for a few days. I visited Vancouver a number of times in the 60s while working on a merchant ship. Went back in 2014 for another wedding, and was reminded why I love that city and its environs. Sadly it's a bit late to think about emigrating, and all my, and my wife's, immediate family are close at hand here.
-
I recently lost out on a great job because I couldn't pass the coding challenge. I was given a header file that I COULD NOT modify, and asked to fill it out with a stack with a linked list backbone. The problem was to reverse stack data (integers) such that nodes 1..4 contained 1, 2, 3, 4, and the output would be 4, 3, 2, 1. I easily wrote this, with one problem: none of the methods in the class signatures contained any output method other than top(), which returned the top node. Everything else was a void method. So I modified the size() method t]such that it output the values of each node. I believe this is where I failed. The code contained a "node" class with a data member and a pointer to the next node. The stack class had a pop method, a push method, that size method, top, and that's about it. Both were templates. Other than adding a friend class or resorting to dirty pointer tricks, I could not figure out how to display the data members of the node class. I really don't understand how this is a valid problem to pose. Here is the header I was given: #include #pragma once //a basic stack class. //Implement all member functions in the file stack.cpp. // then add a reasonable set of unit tests, with output, to main.cpp. //Don't modify stack.h or CMakeLists.txt at all, unless you spot a mistake. template struct _node { T _data; _node* _next; _node(const T&, _node*); ~_node(); }; template class stack { private: _node* _head; size_t _size; public: stack(); ~stack(); size_t size() const; //return the size of the stack T& top() const; //return a reference to the top value. Throw an exception if the stack is empty. void push(const T&); //push a new value onto the stack void pop(); //remove the top value from the stack. Do nothing if the stack is empty. void invert(); //reverse the order of the entire stack, so that 1,2,3,4,5 becomes 5,4,3,2,1 and so on. //Your function should work in the most effecient way you can devise, ideally without allocating any memory on the heap. };
-
Aha! You didn't respect the requirements either: "then add a reasonable set of unit tests, with output, to main.cpp" :) If you move your main to a different CPP file you will run into errors. The other thing I don't understand is why you mix the "T" and "t". Otherwise your implementation is almost exactly like mine. In the invert function, I like my variable names (prev, crt, next) a bit more than yours but this is such a stylistic detail that I'm not going to argue about. I did mention it however because I'm a bit anal :) (Some people would call me an anal a..hole but that's a bit pleonastic, isn't it?).
Mircea
Mircea Neacsu wrote:
If you move your main to a different CPP file you will run into errors.
But not too difficult to fix with a little thought. The problem is that the implementation in stack.cpp is still a bunch of templates, so when compiled it does not generate any code. I discovered this by generating the assembly listing. So I added the following dummy function to stack.cpp which instantiates one of every template function and it compiles and links cleanly.
void sample()
{
stack dummy;
dummy.push("A");
dummy.size();
dummy.top();
dummy.pop();
dummy.invert();
}Oh, and I missed the part in the original which said "do not amend stack.h unless you see any mistakes". The mistake of course was all those lower case 't's in the templates. Changing them to upper case fixes it. So my take home is that I learned a few useful things, including how not to use templates. But I think the test was valid as it is a good challenge for the candidate. Had he got it right it would probably have created an opportunity to discuss the whole thing with the people who devised the test. I don't think they are as dumb as first appears.
-
Right. All my attempts, including reinterpret_cast, to instantiate the _node class, which is private in _stack, yield compile errors.
-
Canada has long been a favourite place although I have not spent nearly enough time there. My brother lives in Toronto, about 10 minutes drive from CodeProject HQ (according to Google). Visited there in 2008 for a wedding, and also went up to Manitoulin island to stay with an aunt for a few days. I visited Vancouver a number of times in the 60s while working on a merchant ship. Went back in 2014 for another wedding, and was reminded why I love that city and its environs. Sadly it's a bit late to think about emigrating, and all my, and my wife's, immediate family are close at hand here.
Yes, both Toronto and Vancouver are beautiful places. I live in Montreal that used to be a wondrous place before this COVID thing. If you ever come visit, I'd bet you will enjoy it. Cheers, Mircea
-
Mircea Neacsu wrote:
If you move your main to a different CPP file you will run into errors.
But not too difficult to fix with a little thought. The problem is that the implementation in stack.cpp is still a bunch of templates, so when compiled it does not generate any code. I discovered this by generating the assembly listing. So I added the following dummy function to stack.cpp which instantiates one of every template function and it compiles and links cleanly.
void sample()
{
stack dummy;
dummy.push("A");
dummy.size();
dummy.top();
dummy.pop();
dummy.invert();
}Oh, and I missed the part in the original which said "do not amend stack.h unless you see any mistakes". The mistake of course was all those lower case 't's in the templates. Changing them to upper case fixes it. So my take home is that I learned a few useful things, including how not to use templates. But I think the test was valid as it is a good challenge for the candidate. Had he got it right it would probably have created an opportunity to discuss the whole thing with the people who devised the test. I don't think they are as dumb as first appears.
Richard MacCutchan wrote:
I don't think they are as dumb as first appears.
You are too generous. Me, the eternal optimist, at the question "Can people be that dumb?" I always answer "Yes! they can!" :laugh:
