• 1

• 11.9k
• 1
• 20
• 46

For what it's worth, I feel your pain about not getting any useful feedback from an interview. At least they actually told you that you didn't get the job! I've had companies (very well known, well-respected companies) not contact me to let me know I didn't get the job. In any event, here are some improvements that I think you could make.

#Naming Your functions are named reasonably well, but your variables are not. Instead of pN, just write node. Instead of s, write size or length. It will make your code far easier to read. Also, Hungarian notation (prefixing variables with a letter to indicate type) is out-of-fashion. Even if it weren't, I'm not sure you've done it correctly. A pointer to a pointer to a node should be ppN, not pN, shouldn't it?

The name merge_two_first_sublists() is really confusing. Why are they called first? And why don't you pass the function 2 lists? Even if you implement it in O(1) space, you can still pass in the pointer to each list. And if you do it that way you can use it even for lists that aren't contiguous.

In merge_sort() you have a variable simply named l. This is a dangerous name. In many fonts, it looks like a numeral 1. In general 1-letter variable names are a bad idea. I can give a pass for loop counters i and j, but beyond that, you should really avoid them.

#Classes You're programming in an object-oriented language, but you aren't using objects, which is a little odd. Why aren't insert_before(), remove() and skip() methods on a List class? It's not clear to me from the requirements you posted that it wouldn't be acceptable to do it that way. It would encapsulate the list in a convenient way and protect it from being modified elsewhere.

#Overuse of Pointers C++ has a lot of ways to avoid using pointers. The reason it has them is because pointers are extremely error prone and code that uses raw pointers is a maintenance headache. You've doubled-down on pointers and are using pointers-to-pointers in every function. It doesn't look to me like you need them in most of the functions. For example, why can't skip() be written like this:

template <typename T>
Node<T> *skip(Node<T> *pN, size_t s) {
 while (s-- && pN)
 pN = pN->next;
 return pN;
}

What do you gain by using a pointer to a pointer?

How does insert_before() even work? The first argument is a pointer-to-a-pointer to the node we wish to insert after the second argument, n. So we have to end up with n->next assigned to the address of the "after" node. Don't we also need to have the "after" node's next pointer pointing to whatever n->next was pointing to before the call? I don't see that happening anywhere. And for the life of me, I can't figure out what the last line of the function is doing. Why do you set the pointer that was pointing to the pointer to the "after" node to point to the "before" node? What does that accomplish?

Why does remove() return anything? I wouldn't expect a remove() function to return any value. I'd just expect it to remove the node in question from the list. But it doesn't even take a list an as argument, just a pointer to a pointer to a node. This is going to be difficult to use and maintain, in my experience.

I recommend avoiding pointers at all if you can. In C++ you can use references instead of pointers in many cases. With C++11 and later, you can use shared_ptr and unique_ptr where appropriate. The requirements do say that the list uses pointers, so at least encapsulate them as best you can. If you have to have a function that modifies a pointer that's an argument you can pass in a reference to a pointer instead of a pointer to a pointer.