Technical Interview Questions

Lowest Common Ancestor

2012-02-16T00:10:00.000-08:00

Question: Given values of two nodes in a binary search tree, write a function to find lowest common ancestor of these two nodes. Lowest common ancestor can be described as a parent node that is common and closest to both the given nodes. (If both the nodes are present in the tree the NULL check is not required, also assuming that -1 is an invalid data value.)

Time Complexity: O(log(n))

int
lowest_common_ancestor(tree *t, int value1, int value2)
{
// Check required if nodes with input
// values are not present in the tree
if (t == NULL) {
return -1;
}

if (t->data < value1 && t->data < value2) {
return lowest_common_ancestor(t->right, value1, value2);
} else if (t->data > value1 && t->data > value2) {
return lowest_common_ancestor(t->left, value1, value2);
} else {
return t->data;
}

}

Maximum Sum Sub-array (Kadane's Algorithm)

2011-07-28T00:42:00.000-07:00

Question: Given an array of integers (both positive and negative), find the sub-array with maximum sum. Example: An array {-1, 2, -5, 4, -1, 3, 2, -7, 6} should return maximum sum(8), start index(3), end index(6) i.e. {4, -1, 3, 2}.

Time Complexity: O(n)

maximum_sum_subarray(int *array, int length, int *max_sum, int *max_start, int *max_end)
{
int cur_sum = 0, cur_start = 0, cur_end = 0;

for (cur_end = 0; cur_end < length; cur_end++) {
cur_sum += array[cur_end];
if (cur_sum > *max_sum) {
*max_sum = cur_sum;
*max_start = cur_start;
*max_end = cur_end;
}

if (cur_sum < 0) {
cur_sum = 0;
cur_start = cur_end + 1;
}
}
}

Palindrome

2011-07-14T00:07:00.000-07:00

Question: Write a program to find whether a given string is a palindrome or not. [A palindrome is a word, phrase, number or other alpha-numeric sequence that can be read the same way in either direction]
Time complexity: O(n)

bool
palindrome (char *str)
{
int len = (strlen(str) - 1);
int count = 0;

for (count = 0; count < len; count++, len--) {
if (str[count] != str[len]) {
return (FALSE);
}
}

return (TRUE);
}

Sum of the nodes of binary tree

2011-07-13T22:42:00.000-07:00

Question: Write a function to calculate the sum of binary search tree nodes?
Time Complexity: O(n)

int
sum_of_tree_nodes(tree *t)
{
if (t == NULL) {
return 0;
} else {
return (sum_of_tree_nodes(t->right) +
t->data +
sum_of_tree_nodes(t->left));
}
}

String Permutation

2011-06-29T01:58:00.000-07:00

Question: Write a program to display all permutation of alphabets in the string ? For example: string 'xyz' has following possible permutations:
xyz
xzy
yxz
yzx
zxy
zyx

// initial call: permutations("xyz", 0)

void permutations(char *str, int level)
{
int i = 0;
int len = strlen(str);

if (level == len)

{
// Termination Condition
printf("%s\n", output);
return;
}

for (i = 0; i < len; i++)
{
if (flag[i]) continue;
output[level] = str[i];
flag[i] = 1;
permutations(str, level + 1);
flag[i] = 0;
}
}

String Combination

2011-06-29T01:48:00.000-07:00

Question: Write a program to display all combinations of alphabets in a given string ? For example: string 'xyz' has following possible combinations:
x
xy
xyz
xz
y
yz
z

// initial call: combinations("xyz", 0, 0)

void combinations(char *str, int start, int level)

{

int i = 0;
int len = strlen(str);

if (start == len) {

// Termination Condition

return;

}

for(i = start; i < len; i++)

{

output[level] = str[i];

output[level + 1] = '\0';

printf("%s\n", output);

combinations(str, i + 1, level + 1);

}

Fibonacci Number

2011-06-29T00:42:00.000-07:00

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 - numbers in this series are known as Fibonacci numbers. By definition, each subsequent Fibonacci number is sum of previous two Fibonacci numbers. First two Fibonacci numbers are 0 and 1.

Write a program to efficiently calculate the Nth Fibonacci number.

Time Complexity: O(n)

unsigned int fibonacci(unsigned int n)

{
unsigned int n1 = 1, n2 = 0;
unsigned int x, result;

if (n < 2) {
return n;
}
for (x = 2; x <= n; x++) {
result = n1 + n2;
n2 = n1;
n1 = result;
}
return (result);
}

On the contrary, a very simple recursive implementation of fibonacci has exponential complexity.

unsigned int fibonacci(unsigned int n)
{
if (n < 2) {
return n;
}
return (fibonacci(n - 1) + fibonacci(n - 2));
}

Missing Number

2011-06-17T17:40:00.000-07:00

Question: Given an array of integers of size n. This array has integer values starting from x, incrementing by 1. The final array element is n+x (instead of n + x - 1) i.e. it is missing one integer in between. Write a function to identify this missing number.

Example: array[5] = { 2,3,4,6,7 }; missing number is 5.

Time Complexity: O(log n)

int missing_number(int *a, int len)
{
int mid = len / 2;

if (len == 1) {
printf ("missing number is %d\n", a[0] + 1);
return (a[0] + 1);
}

if ((a[0] + mid) == a[mid])
{
// first half of array is not missing a number
missing_number(&a[mid], len - mid);
} else {
// second half of array is not missing a number
missing_number(a, mid);
}
}

Valid Binary Search Tree

2011-06-15T23:56:00.000-07:00

Question: Write a function to find whether a given binary tree is a binary search tree ?

Find below a recursive algorithm to find whether a given binary search tree is valid or not. This algorithm, starting from the root node, at each node verifies whether current node data lies between min and max possible value for that node and also check if the left and right subtree are valid binary search trees. Since node data in my tree is an integer, thus starting min and max values used are 0x80000000 and 0x7fffffff. However, these values will depend on minimum and maximum possible values of the key. In addition, following algorithm assumes no duplicate keys; if duplicate keys are present, the condition in line 8 and 9 needs to be modified.

Time complexity: O(n)

bool
is_valid_bst_helper(tree *t, int min, int max)
{
if (t == NULL) {
return TRUE;
}

if (t->data > min &&
t->data < max &&
is_valid_bst_helper(t->left, min, t->data) &&
is_valid_bst_helper(t->right, t->data, max)) {
return TRUE;
}

return FALSE;
}

bool
is_valid_bst(tree *t)
{
return(is_valid_bst_helper(t, 0x80000000, 0x7fffffff));
}

The First Post

2011-06-15T23:43:00.000-07:00

I have worked as software engineer for over a decade and during this time I have been on both side of the interview table... multiple times. I always wanted to start a blog on good interview questions, questions that make you think, questions that are sometimes left unanswered but you knew deep down that you could have done it. This blog will focus on coding, algorithms, data structures, puzzles and more and I will strive to provide best possible answers (with help of the readers). The questions will not be a one time post, their solution will be modified as and when something better is available. Overtime we will build a good repository of good interview questions and answers. Please feel free to email me your favorite interview questions so that we can challenge our fellow readers.

Disclaimer:
Code in this blog is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program. If not, see <http://www.gnu.org/licenses/>.