Some simple problems to ask in programming interviews. They can be used for initial screening and to put the candidate in a comfort zone. These problems are easy to explain and understand and can be implemeneted in less than 30 lines of code. Though they are simple, solving them require understanding of recurssion, invariants, data structures, time/space complexity, pointers etc. All solutions presented here are in C/C++.
Problem 1: Find the length of a NULL terminated array.
Obvious first solution using iteration:
int length (int* arr[])
{
int len = 0;
int i = 0;
while (arr[i] != NULL)
{
++len;
++i;
}
return len;
}
Test code:
int main ()
{
int x = 45;
int y = 30;
int z = 50;
int* a[4] = {&x, &y, &z, NULL};
printf ("%d\n", length (a)); // => 3
return 0;
}
Can you do that using recursion?
Solution where candidate demonstrates knowledge about recursion and pointers:
int length (int* arr[])
{
if (*arr == NULL) return 0;
return (1 + length (++arr));
}
How will you take advantage of tail-call optimization, if the language implementation supports that?
Solution where candidate shows that he is familiar with non-imperative programming styles, pointer arithmetic and recursion:
int length_helper (int* arr[], int len_so_far)
{
if (*arr == NULL) return len_so_far;
return length_helper (++arr, ++len_so_far);
}
int length (int* arr[])
{
return length_helper (arr, 0);
}
Is it possible to combine length and length_helper into one function?
Answer: Use optional arguments (or varargs).
Problem 2: Write a function to compute the sum of the first n squares.
Iterative solution:
int add_n_squares (int n)
{
int sum = 0;
int i = 0;
for (; i < n+1; ++i)
{
sum += (i * i);
}
return sum;
}
int main ()
{
int x = 4;
int y = 3;
int z = 5;
printf ("%d\n", add_n_squares (x)); // 30
printf ("%d\n", add_n_squares (y)); // 14
printf ("%d\n", add_n_squares (z)); // 55
return 0;
}
What is the time complexity of this function?
Correct answer: O(n)
Can you make this function execute in constant time and space?
One possible Solution:
int add_n_squares (int n)
{
return n * (n + 1) * (2 * n + 1) / 6;
}
As we are not hiring a mathematician, it can be ignored even if the candidate fails to come up with this solution.
Problem 3: Write a function to compute the dot-product of two vectors.A dot product is computed by multiplying corresponding elements and then adding up the resulting products. For example, the dot product of [45, 30] and [10, 5] is 600.(From
Paradigms of Artificial Intelligence Programming by Peter Norvig).
Iterative solution:
int dot_product (int a[], int b[], int size)
{
int i = 0;
int result = 0;
while (i < size)
{
int prod = a[i] * b[i];
result += prod;
++i;
}
return result;
}
Recursive solution:
int dot_product (int a[], int b[], int size)
{
if (size == 0) return 0;
return ((a[0] * b[0]) + dot_product (++a, ++b, --size));
}
Complete solution in C++:
// shift.cpp
#include <iostream>
#include <string>
void shift (const std::string& s, int by,
bool encode, std::string& res)
{
size_t len = s.size ();
for (size_t i = 0; i < len; ++i)
{
if (encode) res += (s[i] + by);
else res += (s[i] - by);
}
}
// Pass the string to shift and number of characters
// to shift as arguments.
int
main (int argc, char **argv)
{
int shift_by = atoi (argv[2]);
std::string encoded;
shift (argv[1], shift_by, true, encoded);
std::cout << "encoded: " << encoded << '\n';
std::string decoded;
shift (encoded, shift_by, false, decoded);
std::cout << "decoded: " << decoded << '\n';
return 0;
}
Test runs of the program:
> ./shift hello 3
encoded: khoor
decoded: hello
> ./shift hello 5
encoded: mjqqt
decoded: hello
> ./shift hello 0
encoded: hello
decoded: hello
> ./shift hello -1
encoded: gdkkn
decoded: hello
