C++ Interview Questions Part 2

  • 0

C++ Interview Questions Part 2

Category : Learning

Want create site? Find Free WordPress Themes and plugins.

PART 2: This is next 5 C++ interview questions written as interview story. Our candidate is Samantha.

Introduction

This is second part of the C++ programming questions article written as interview story.

You can find the PART 1 here.

C++ Interview Story #2

The second interview candidate of the day is Samantha. Samantha has a background in computer science, and has worked as an embedded device programmer in the automotive industry for several years. Samantha has successfuly passed online C++ test, so I am quite sure in her technical skills. Now it’s time to check her C++ knowledge on live interview.

We make ourselves comfortable and chat a bit about Samantha’s experiences in embedded software. “It’s a very different world,” she says. “Everything has to be small and efficient. On the one hand, it’s a nice puzzle. On the other, it gets really frustrating sometimes.”

[Question #1]

After the introductory chat, I throw my first interview question to see whether Samantha would qualify for the C++ role she’s interviewing for.

Here’s what I ask her:

“For starters, could you tell me what ‘undefined behavior’ means, and how it’s different from ‘unspecified behavior’?”

“Sure,” she says, somehow seeming relieved. “UB means that the standard guarantees nothing about how the program should behave. It might work, it might crash, it might make demons fly out of your nose. In short, this is something you always want to avoid.”

I encourage her to go on.

“Unspecified behavior… I think you mean implementation-defined? As the word says, the standard requires the behavior to be well-defined, but leaves the definition up to the compiler implementation. You want to avoid IB in portable code, but sometimes there’s no way around it. For example, on one CPU architecture I worked with, we needed a special attribute to use the correct calling conventions for functions.”

I want to know about practice as well as theory, so I ask:

“Could you give some examples of undefined behavior?”

Samantha answers without hesitation. “Most common would be dereferencing a null or wild pointer, or otherwise accessing uninitialized memory, like going beyond the bounds of an array. Deleting the same memory twice, or more generally deleting a wild pointer. Reading uninitialized values is another, like if you declare int x; but don’t assign it a value. Many people think you just get garbage, and this is often true in practice, but it’s actually UB so anything could happen.”

I nod for her to continue, so she does:

“Let’s see, what else… arithmetic errors, like division by zero. You may cause a CPU trap, or for all you know it just sets an error bit, gives you a weird value, and you never hear about it again. It’s undefined, so you cannot rely on it.”

A comprehensive enumeration! It’s clear that she has some experience. But let’s see how thorough she really is.

[Question #2]

“Here’s a code snippet,” I say, showing her the code. “Find as many bugs in it as you can!”

#include <vector.h>

void main(int argc, char** argv)
{
    int n;
    if (argc > 1)
        n = argv[0];
    int* stuff = new int[n];
    vector<int> v(100000);
    delete stuff;
    return 0;
}

“Sooo… vector.h? That’s a C-like header, but vector is a C++ construct. It should just be vector, without the .h. Incidentally, where it’s being used, it lacks the std:: namespace reference. I’m not sure about void main… doesn’t that need to be int main in C++? I always use int, but I’m not sure if the standard requires it. But if you’re returning a value, like here, it definitely needs to be int. The rest of the signature is fine…”

Samantha traces the code with her finger, visibly wincing when she gets to the assignment.

“Ouch, if no arguments are given, n is not initialized. And if we do initialize it, better not set it to a pointer! Maybe they wanted to parse it as an integer. That would not go down well either, because argv[0] is the name of the program, not the first argument.”

She continues with the next line:

“I wonder why stuff is a raw array, not just a vector, because the author clearly knows about vector? That would also prevent the memory leak in case the vector allocation throws an exception. And the delete call should be delete[]. Although in practice it will probably work for an array of simple integers, it’s still UB.”

“Wow!” I say, genuinely impressed. “I think you got them all.”

“Well,” she says, “it’s just a toy program. It gets a lot harder in code that actually does something useful.”

[Question #3]

“True that,” I concur. “Let’s see if we have any of that lying around. How about this… could you write a template to tell me if its argument is a pointer?”

“Like a type trait?” she asks, not waiting for an answer. “I think there’s something like std::is_pointer already. It would look something like this:”

template<typename T> struct is_pointer {
    enum { value = false; };
};
template<typename T> struct is_pointer<T*> {
    enum { value = true; };
}

“Template overload resolution will pick the most specific one, so if the type is a pointer, the last one will be selected. Otherwise it falls back to the first.”

“Why the anonymous enums, and not simply a static const bool?” I wonder out loud. My own solution used this, and compiled fine.

“For one, the constants would still occupy memory space, so it’s not a 100% compile time construct anymore,” Samantha explains. “More importantly, you’d need to redefine the existence of value outside the template in order for it to exist, because the assignment of a value in this case does not make it into an actual definition. It would work in some cases, but would fail if you take the address, for example. Strange but true.”

[Question #4]

Such remarks clearly point towards experience as well as deep knowledge, and are a very positive signal in interviews.

“Nice,” I say, “I didn’t know that! While we’re on the subject of templates, suppose I have a function called insertion_sort which sorts an std::array. Because insertion sort is relatively slow, it should only be used on short arrays. I would like a compile-time check that the array is no longer than 128 elements. Could you write that?”

“So I guess the signature is something like this?” Samantha asks, writing down some code:

template<typename T, size_t N>
void insertion_sort(std::array<T, N> &array);

I confirm.

“Okay,” she nods. “We cannot specialize a template based on a range of values without listing each out individually, but we can use SFINAE magic from std::enable_if. Off the top of my head, and I might be slightly off on syntax here, but I think it goes like this…”

template<typename T, size_t N>
std::enable_if_t<N <= 128, void>
insertion_sort(std::array<T, N> &array);

Highlighting the enable_if_t construct, she explains: “Before C++14, I think we’d have to write std::enable_if<…>::type. This is just a slight shortcut.”

[Question #5]

“Yep, quite right,” I say. It’s a happy coincidence that I had to use this construct yesterday, otherwise I wouldn’t have known. “Let’s write some more interesting code. Could you design the interface for a max heap class? We’ll continue with the implementation later.”

“Wow, it’s been a while since I’ve done that!” Samantha laughs, “I hope I can remember how that works! But the API should be easy enough. Let’s see what we need. Copy and move operations, like the standard containers. Add a value; find and remove the maximum value; maybe size?”

She can see I’m smiling, so she continues:

“Iterators might be nice as well, but I’ll leave them out for now. For implementation, a heap is most efficiently stored in an array. If I base the implementation on a std::vector, I get all the move and copy stuff for free.”

template<typename T>
class MaxHeap {
    public:
        void add(T const &value);
        T const &max() const;
        T remove_max();
        size_t size() const;
    private:
        std::vector<T> elements;
};

Many candidates, when presented with such a question, will implicitly assume integers. It’s nice to see that Samantha starts off with a template, which will make the code more reusable, and writing it more interesting. She also takes care of const correctness. There’s no mention of noexcept, but then again, it might be reasonable for all of these functions except size() to throw an exception.

“Okay,” Samantha says. “So now let’s implement insertion. The array holds nodes in a top-to-bottom order, with the nodes in each row stored from left to right. To find the parent of a node, we shift out the least significant bit. This is a max heap, so we need to make sure that all of a node’s children are smaller than or equal to the node itself. If I recall correctly, you normally start by adding the element to the end of the array, then bubble it up as far as required. Here goes…”

void add(T const &value) {
    size_t index = elements.size();
    elements.push_back(value);
    while (elements[index >> 1] < elements[index]) {
        std::swap(elements[index >> 1], elements[index]);
        index >>= 1;
    }
}

After writing this, she mentally walks through the code to verify it, explaining: “I could add an extra check for when we reach the top, but if the < operator is properly implemented, we’ll eventually compare the element to itself if it reaches the top, and the loop will terminate. Note that I only use the < operator here, none of the other comparison operators, which is common in C++ standard library algorithms as well.”

She continues with even more detail:

“The max() and size() functions are trivial:”

T const &max() const { return elements.front(); }
size_t size() const { return elements.size(); }

Again, she explains what she’s doing:

“In line with the standard library containers, I decided not to throw an exception if the heap is empty, and just chalk that up to undefined behavior. And now for removal: the textbook technique is to remove the topmost (first) element, put the last element into its place, then bubble it down to restore the heap property.”

T remove_max() {
    T max = elements.front();
    elements.front() = elements.back();
    elements.pop_back();
    size_t index = 0;
    while (true) {
        size_t left = index >> 1;
        size_t right = left + 1;
        if (elements[left] < elements[index] && elements[right] < elements[index]) {
            // Heap property is OK: element is larger than its children.
            break;
        } else if (elements[left] < elements[right]) {
            // Right child is the largest.
            std::swap(elements[index], elements[right]);
            index = right;
        } else {
            // Left child is the largest.
            std::swap(elements[index], elements[left]);
            index = left;
        }
    }
    return max;
}

It takes her less than 10 minutes to write all that, with minimal corrections along the way.

At the end, here’s what she says:

“That’s the basic idea, but I left out an important bit so I could get the basic structure down. We need to check for left and right to be within the bounds of the vector, otherwise we will invoke undefined behaviour. So it’s not complete yet.”

“That’s okay,” I say. “I see where you are going with this, and we’re out of time for this interview. Do you have any questions for me in return? About the company, the job opening, the interview process, anything at all?”

“Yeah,” she says, smiling slightly. “I was wondering if you’d ever implemented a heap yourself in practice…”

I grin. “To be honest, I haven’t. All the more impressive that you could just write it down like that.”

I mean it. Textbook algorithms knowledge is nice, but the ability to turn it (or any other problem specification) into functioning, well-designed code is what we are really looking for. Before I even leave the interview room, I have already made up my mind that Samantha will be a definite hire.

Conclusion

There are as many interview styles as there are interviewers, and as many interview methodologies as there are companies. The above are just samples of how C++ interviews could play out, depending on the company, the open position, the interviewer, the candidate, and the coding questions asked.

We hope our readers got some useful info which could be used in their own interviews.

Author: Mike_my_name

Did you find apk for android? You can find new Free Android Games and apps.