C/C++ Interview Exam (with answers)
=================================

1. Where in memory are the variables stored?

* Global variables
* Static variables
* Constant data types
* Local variables (declared and defined in functions)
* Variables declared in *main* function
* Dynamically allocated space

    Please answer here...
    * data
    * data
    * code / data
    * stack
    * stack
    * heap

2. What are the modifiers "volatile" and "mutable"? When should they be used?

    A mutable field can be changed even in an object accessed through a const pointer or reference, or in a const object, so the compiler knows not to stash it in R/O memory. A volatile location is one that can be changed by code the compiler doesn't know about (e.g. some kernel-level driver), so the compiler knows not to optimize e.g. register assignment of that value under the invalid assumption that the value "cannot possibly have changed" since it was last loaded in that register. Very different kind of info being given to the compiler to stop very different kinds of invalid optimizations.

3. Are the following legal or illegal uses of const pointers? Which lines are illegal ones? What are the benefits of using const?

~~~c
// Question 3
const char *str = "hello";
char c = *str;
str++;
*str = 'a';
str[1] = 'b';
~~~

    Lines 4, 5 are illegal. The benefit of using the const keyword is that the compiler might be able to make optimizations based on the knowledge that the value of the variable will not change. In addition, the compiler will try to ensure that the values won't be changed inadvertently.

4. What is the output of the following program?

~~~c++
// Question 4
#include <iostream>

class A
{
public:
A(int n = 0)
: m_n(n)
{
std::cout << 'd';
}

A(const A& a)
: m_n(a.m_n)
{
std::cout << 'c';
}

private:
int m_n;
};

void f(const A &a1, const A &a2 = A())
{
}

int main()
{
A a(2), b;
const A c(a), &d = c, e = b;
b = d;
A *p = new A(c), *q = &a;
static_cast<void>(q);
delete p;
f(3);
std::cout << std::endl;

return 0;
}
~~~

    ddcccdd

5. Please write a function to shuffle a vector of integers.

~~~c++
// Question 5
#include <vector>
#include <stdexcept>
#include <iostream>

class Shuffler
{
public:
static void shuffle(std::vector<int>& sequence)
{
// TODO: Waiting to be implemented

}
};

#ifndef RunTests
int main()
{
std::vector<int> v = { 1, 2, 3, 4, 5, 6 };
Shuffler::shuffle(v);
return 0;
}
#endif
~~~

~~~c++
/*
Solution for reference,
tested with g++ (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0
*/

#include <random>
class Shuffler
{
public:
static void shuffle(std::vector<int>& sequence)
{
// shuffle the vector by sequence.size() times of swapping two random indices

// random number generator
std::random_device rd;
std::default_random_engine eng(rd());
std::uniform_int_distribution<int> distr(0, sequence.size() - 1);

for (int i=sequence.size()-1; i >= 0; --i)
std::swap(sequence[i], sequence[distr(eng)]);
}
};

// Solution for reference #2
#include <ctime>
class Shuffler
{
public:
static void shuffle(std::vector<int>& sequence)
{
if (sequence.size() <= 1)
return;
srand(time(NULL));
for (int rand_len=sequence.size()-1; rand_len>1; --rand_len)
{
int index = ((double)rand() / (RAND_MAX + 1.0)) * rand_len;
std::swap(sequence[index], sequence[rand_len]);
}
}
};
~~~

6. Implement function *countNumbers* that accepts a sorted vector of integers and counts the number of vector elements that are less than the parameter *lessThan*. For example, the following program should return 2 because there are two vector elements less than 4. (Note: the vector size may be extremely large.)

~~~c++
// Question 6
#include <vector>
#include <stdexcept>
#include <iostream>

class SortedSearch
{
public:
static int countNumbers(
const std::vector<int>& sortedVector, int lessThan)
{
// TODO: Waiting to be implemented

}
};

#ifndef RunTests
int main()
{
std::vector<int> v = { 1, 3, 5, 7 };
std::cout << SortedSearch::countNumbers(v, 4);
return 0;
}
#endif
~~~

~~~ c++
// Solution for reference: Binary search -> O(logN)
class SortedSearch
{
public:
static int countNumbers(
const std::vector<int>& sortedVector, int lessThan)
{
if (sortedVector.size() == 0)
return 0;
int left = 0, right = sortedVector.size() - 1, mid;
while (left + 1 < right)
{
mid = (left + right) / 2;
if (lessThan > sortedVector[mid])
left = mid;
else
right = mid;
}
if (sortedVector[right] < lessThan)
return sortedVector.size();
else if (sortedVector[left] < lessThan)
return left + 1;
else
return 0;
}
};
~~~

7. The following code is for inserting an element at the front of a list. Please correct it if you find anything inappropriate, and describe what you find.

~~~c++
struct IntElement
{
int data;
IntElement *next;
};

bool insertInFront (IntElement *head, int data) {
IntElement *newElem = new IntElement;
if (!newElem) return false;

newElem->data;
head = newElem;

return true;
}
~~~

   The preceding code is incorrect because it only updates the local copy of the head pointer. Correct one should pass in a pointer to the head pointer.

~~~c++
// reference solution
bool insertInFront (IntElement **head, int data) {
IntElement *newElem = new IntElement;
if (!newElem) return false;

newElem->data = data;

newElem->next = *head;
*head = newElem;

return true;
}
~~~

~~~c++
// an alternative solution (passing pointer by reference)
bool insertInFront1 (IntElement* &head, int data) {
IntElement *newElem = new IntElement;
if (!newElem) return false;

newElem->data = data;

newElem->next = head;
head = newElem;

return true;
}
~~~