|
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 <cstddef>
#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 <class t=""> struct _node
{
T _data;
_node<t>* _next;
_node(const T&, _node<t>*);
~_node();
};
template <class t=""> class stack
{
private:
_node<t>* _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.
};
|
|
|
|
|
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 top and pop functions. The call to top gives you a reference to the value at the top of the stack. So you can display that with cout/printf. Follow that with a call to pop and the value you just looked at is now removed, ready for the next call to top. And so on.
|
|
|
|
|
Right. All my attempts, including reinterpret_cast, to instantiate the _node class, which is private in _stack, yield compile errors.
|
|
|
|
|
You do not use reinterpret_cast to change public/private. However, I think there is something missing in that header file; I'd like to see their implementation.
|
|
|
|
|
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; #include "stack.h"
#include <iostream>
template <class t>
stack<t>::stack()
{
_head = nullptr;
_size = 0;
}
template <class t>
stack<t>::~stack()
{
}
template <class t>
size_t stack<t>::size() const
{
return _size;
}
template <class t>
T& stack<t>::top() const
{
return _head->_data;
}
template <class t>
void stack<t>::push(const T& item)
{
}
template <class t>
void stack<t>::pop()
{
}
template <class t>
void stack<t>::invert()
{
}
int main()
{
stack<int> myStack;
std::cout << "stack size = " << myStack.size() << std::endl;
return 0;
}
modified 18-May-20 5:09am.
|
|
|
|
|
|
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<t>*); 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 <class t=""> struct _node Seriously? 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<class T>
_node<T>::_node (const T& dat, _node<T>* ptr) :
_data (dat),
_next (ptr)
{
}
template<class T>
_node<T>::~_node ()
{
}
template<class T>
stack<T>::stack () :
_size (0),
_head (nullptr)
{
}
template<class T>
stack<T>::~stack ()
{
while (_head)
{
_node<T>* ptr = _head->_next;
delete _head;
_head = ptr;
}
}
template<class T>
size_t stack<T>::size () const
{
return _size;
}
template<class T>
T& stack<T>::top () const
{
if (!_size)
throw std::exception ("empty_stack");
return _head->_data;
}
template<class T>
void stack<T>::push (const T& data)
{
_node<T>* node = new _node<T> (data, _head);
_head = node;
_size++;
}
template<class T>
void stack<T>::pop ()
{
if (!_size)
return;
_node<T>* ptr = _head->_next;
delete _head;
_head = ptr;
--_size;
}
template<class T>
void stack<T>::invert ()
{
_node<T>* prev = nullptr;
_node<T>* crt = _head;
while (crt)
{
_node<T>* next = crt->_next;
crt->_next = prev;
prev = crt;
crt = next;
}
_head = prev;
}
I don't want to go on here talking about the dangers of not providing a copy constructor when you are knee-deep in pointer manipulations, not respecting the "big three" (or big five) rule, and so on and so forth.
For the "unit test" part you can write something like this:
int main (int argc, char** argv)
{
stack<int> the_stack;
cout << "Empty stack has size " << the_stack.size () << endl;
the_stack.push (1);
the_stack.push (2);
the_stack.push (3);
the_stack.push (4);
the_stack.push (5);
cout << "5 elements pushes, size is " << the_stack.size () << endl;
cout << "Top element is " << the_stack.top () << endl;
the_stack.invert ();
cout << "Stack inverted elements are (from top):" << endl;
int n = the_stack.size ();
for (int i = 0; i < n; i++)
{
cout << "Element " << i + 1 << " is " << the_stack.top () << endl;
the_stack.pop ();
}
return 0;
}
To wrap it up, my advice would be to look for an environment where they hire based on your work portfolio, where they understand that a coder must be also a person with good communication skills and with a good understanding of the problem domain. Build a portfolio of code writing high-quality code and learning from masters (Knuth, Wirth, Djikstra and so many others). Remember: if you cannot write your code to read like a poem, make it at least like a novel.
Mircea
|
|
|
|
|
That was my first thought too, that the company's culture, or at least this part of it, must be shite.
|
|
|
|
|
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 t and upper case T is 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 <class t=""> struct _node. I'm sorry but if I want to go ahead I need to change stack.h.
After I change it to template <class T> 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<int> 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 typedef at 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 <iostream>
typedef char* T; #include "stack.h"
template <class t>
_node<t>::_node(const T& item, _node<t>* next)
{
_data = item;
_next = next;
}
template <class t>
_node<t>::~_node()
{
}
template <class t>
stack<t>::stack()
{
_head = nullptr;
_size = 0;
}
template <class t>
stack<t>::~stack()
{
}
template <class t>
size_t stack<t>::size() const
{
return _size;
}
template <class t>
T& stack<t>::top() const
{
if (_size == 0)
throw std::exception("Stack contains no items");
return _head->_data;
}
template <class t>
void stack<t>::push(const T& item)
{
_node<t>* newNode = new _node<t>(item, _head);
_head = newNode;
_size++;
}
template <class t>
void stack<t>::pop()
{
if (_size > 0)
{
_node<t>* popNode = _head;
_head = popNode->_next;
delete popNode;
_size--;
}
}
template <class t>
void stack<t>::invert()
{
if (_size > 1)
{
_node<t>* current = _head;
_node<t>* next = nullptr;
_node<t>* temp;
while (current)
{
temp = current->_next;
current->_next = next;
next = current;
current = temp;
}
_head = next;
}
}
void pusher(stack<T>& theStack, T* items)
{
while (*items != 0)
{
theStack.push(*items);
std::cout << "Push " << *items << " onto the stack" << std::endl;
items++;
}
std::cout << " Top item = " << theStack.top() << ", stack size = " << theStack.size() << std::endl << std::endl;
}
void popper(stack<T>& theStack)
{
while (theStack.size() > 0)
{
T& foo = theStack.top();
std::cout << " Top item = " << foo << ", stack size = " << theStack.size() << std::endl;
theStack.pop();
}
std::cout << " stack size = " << theStack.size() << std::endl << std::endl;
}
int wmain(
int argc,
wchar_t** argv
)
{
stack<T> myStack;
T listA[] = { "Foo", "Bar", "Poo", 0 };
pusher(myStack, listA);
popper(myStack);
T listB[] = { "The", "rain", "in", "Spain", "falls", "mainly", "in", "the", "plain", 0 };
pusher(myStack, listB);
std::cout << std::endl << "Invert the stack" << std::endl;
myStack.invert();
popper(myStack);
std::cout << std::endl << "Press <enter> to continue ... ";
std::cin.get();
return 0;
}
|
|
|
|
|
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.
|
|
|
|
|
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.
|
|
|
|
|
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<T> 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!" 
|
|
|
|
|
Mircea Neacsu wrote: template <class t=""> struct _node
The ="" characters are not really there. The CodeProject editor mistranslates tab characters in some instances.
|
|
|
|
|
Tim, I am close to a working solution but there are still a couple of loose ends to tie up. Do you have the original copies of the stack.h and CMakeLists.txt files that you could post here?
|
|
|
|
|
What does QueryPerformanceFrequency measure? units per second?
|
|
|
|
|
Here's how I get the current time (in ticks):
TimePoint SysTickTimer::Now() const
{
if(available_)
{
LARGE_INTEGER now;
QueryPerformanceCounter(&now);
return TimePoint(now.QuadPart);
}
else
{
_timeb now;
_ftime_s(&now);
auto msecs = 1000LL * now.time;
return TimePoint(msecs + now.millitm);
}
}
My Windows 10 installation, running on a Dell XPS15, has 10^7 ticks per second (1 tick = 0.1 usecs). This is determined by
LARGE_INTEGER frequency;
if(QueryPerformanceFrequency(&frequency))
{
available_ = true;
ticks_per_sec_ = frequency.QuadPart;
}
|
|
|
|
|
it`s ticks per second. Thanks Greg for showing how you handle it.
|
|
|
|
|
|
thanks, I got it working.
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
