Technical Interview Questions

Convert a binary search tree into a sorted doubly link list

2013-08-20T15:58:00.000-07:00

Question: Given a binary tree, write a program to convert a binary search tree into a sorted doubly link list (tree->left will be list->prev, while tree->right will be list->next). This is an in-place algorithm with constant space requirement.

Time Complexity: O(n)

void
tree2list(tree *t, tree **prev, tree **head)
{
if (!t)
return;

tree2list(t->left, prev, head);

if (*prev == NULL) {
*head = t;
} else {
t->left = *prev;
(*prev)->right = t;
}
*prev = t;

tree2list(t->right, prev, head);

}

This functions is called with prev = NULL, and the head will point to the first node of the doubly link list after the function call.

Maximum distance between any two nodes of a Binary Tree (a.k.a Diameter or Width of the Tree)

2013-08-13T12:32:00.003-07:00

Question: Given a binary tree, write a program to find maximum distance between any two nodes of the tree.

Time Complexity: O(n)

int

diameter(tree *t)
{
/* left diamter, right diameter, node diameter */
int ld, rd, nd;

if (!t) {
return 0;
}

ld = diameter(t->left);
rd = diameter(t->right);
nd = height(t->left) + height(t->right) + 1;

return max3(ld, rd, nd);
}

Slightly more efficient algorithm, this calculates the height of the tree along with diameter.

int
diameter2(tree *t, int *height)
{
/* left diameter, right diameter, node diameter */
int ld, rd, nd;

/* left height, right height */
int lh, rh;

if (!t) {
*height = 0;
return 0;
}

ld = diameter2(t->left, &lh);
rd = diameter2(t->right, &rh);
nd = lh + rh + 1;

*height = max(lh, rh) + 1;
return max3(ld, rd, nd);

}

max3 - returns maximum of the three arguments

Height of a Binary Tree

2013-08-13T12:25:00.002-07:00

Question: Given a binary tree, write a program to find height of the tree.

Time Complexity: O(n)

int
height(tree *t)
{
int lh, rh;

if (!t) {
return 0;
}

lh = height(t->left);
rh = height(t->right);

return max(lh, rh) + 1;

}

Mirror a Binary Tree

2013-05-03T01:40:00.002-07:00

Question: Given a binary tree, write a program to mirror the tree (i.e. swap left and right nodes of the original tree).

Time Complexity: O(n)

tree *
tree_mirror(tree *t)
{
tree *tmp = NULL;

if (!t) {
return NULL;
}

tmp = (tree *) malloc (sizeof(tree));
if (!tmp) {
exit(ENOMEM);
}

tmp->data = t->data;
tmp->right = tree_mirror(t->left);
tmp->left = tree_mirror(t->right);

return (tmp);
}

Duplicate a Binary Tree

2013-05-03T01:36:00.000-07:00

Question: Given a binary tree, write a program to duplicate the tree (i.e. create an exact copy of the tree).

Time Complexity: O(n)

tree *

tree_duplicate(tree *t)

{

tree *tmp = NULL;

if (!t) {

return NULL;

}

tmp = (tree *) malloc (sizeof(tree));

if (!tmp) {

exit(ENOMEM);

}

tmp->data = t->data;

tmp->left = tree_duplicate(t->left);

tmp->right = tree_duplicate(t->right);

return (tmp);

}

Lowest Common Multiple (LCM)

2012-03-28T14:34:00.000-07:00

Question: The least common multiple (LCM), also known as the lowest common multiple, of two or more non-zero integers is the smallest positive integer that is a integer multiple of both the numbers. Provide an efficient algorithm to compute LCM of two numbers.

We have an efficient algorithm to compute GCD, we will use a simple mathematical formula to find the LCM using GCD algorithm.

Time Complexity: O(n)

/* mod method */

int gcd(int n1, int n2)

{

int temp;

while (n2 != 0) {

temp = n2;

n2 = n1 % n2;

n1 = temp;

}

return n1;

}

int lcm(int n1, int n2)

{

return ((n1 * n2) / gcd(n1, n2));

}

Binary Tree Traversal - Recursive and Iterative

2012-03-28T01:06:00.001-07:00

Following code illustrates various binary tree traversal algorithms - both recursively and iteratively. All algorithms provided below are DFS algorithms.

Time Complexity: O(n) - for all algorithms

/* recursive pre order traversal */

void pre_order_traversal_recursive(tree2 *t)

{

if (t == NULL) {

return;

}

/* process node here */

printf ("%d ", t->data);

pre_order_traversal_recursive(t->left);

pre_order_traversal_recursive(t->right);

}

/* recursive in order traversal */

void in_order_traversal_recursive(tree2 *t)

{

if (t == NULL) {

return;

}

in_order_traversal_recursive(t->left);

/* process node here */

printf ("%d ", t->data);

in_order_traversal_recursive(t->right);

}

/* recursive post order traversal */

void post_order_traversal_recursive(tree2 *t)

{

if (t == NULL) {

return;

}

post_order_traversal_recursive(t->left);

post_order_traversal_recursive(t->right);

/* process node here */

printf ("%d ", t->data);

}

/* iterative pre order traversal */

void pre_order_traversal_iterative(tree2 *t)

{

while (t) {

/* condition to control type of traversal */

if (((t->left && !t->left->visited) || !t->left) &&

((t->right && !t->right->visited) || !t->right)) {

/* process node here */

printf("%d ", t->data);

}

/* actual tree traversal */

if (t->left && !t->left->visited) {

t = t->left;

} else if (t->right && !t->right->visited) {

t = t->right;

} else {

t->visited = 1;

t = t->parent;

}

/* iterative in order traversal */

void in_order_traversal_iterative(tree2 *t)

{

while (t) {

/* condition to control type of traversal */

if (((t->left && t->left->visited) || !t->left) &&

((t->right && !t->right->visited) || !t->right)) {

/* process node here */

printf("%d ", t->data);

}

/* actual tree traversal */

if (t->left && !t->left->visited) {

t = t->left;

} else if (t->right && !t->right->visited) {

t = t->right;

} else {

t->visited = 1;

t = t->parent;

}

/* iterative post order traversal */

void post_order_traversal_iterative(tree2 *t)

{

while (t) {

** Following condition controls the type of tree traversal

** PRE ORDER : !t->left->visited and !t->right->visited

** IN ORDER : t->left->visited and !t->right->visited

** POST ORDER : t->left->visited and t->right->visited

if (((t->left && t->left->visited) || !t->left) &&

((t->right && t->right->visited) || !t->right)) {

/* process node here */

printf("%d ", t->data);

}

/* actual tree traversal */

if (t->left && !t->left->visited) {

t = t->left;

} else if (t->right && !t->right->visited) {

t = t->right;

} else {

t->visited = 1;

t = t->parent;

}

Please note that recursive algorithm will also work on regular tree data structure (i.e. without parent and visited). However, iterative algorithms only works with following data structure:

typedef struct tree2_s {

u32 data;

struct tree2_s *left;

struct tree2_s *right;

struct tree2_s *parent;

u32 visited;

} tree2;

Determining Byte Order (Endianness)

2012-03-27T03:18:00.002-07:00

Question: One of the commonly asked question is how will you determine the byte order of the machine using a c program. The byte order can be either little endian or bid endian.

A little endian system will store the least significant byte of any multibyte data field at the lowest memory address. Example:

0xaabbccdd will be stored as ddccbbaa

0x00000001 will be stored as 01000000

bool is_little_endian()

{
int i = 1;
char *c = (char *)&i;
return (*c);
}

bool is_little_endian2()
{
union {
int i;
char c;
} u;

u.i = 1;
return(u.c);
}

Reverse a Singly Linked List - Recursive and Iterative

2012-03-20T03:44:00.000-07:00

Question: Write a C program to reverse a singly linked list.

Find below both recursive and iterative functions to reverse a link list. Both functions have same time complexity. Recursive function is called as head = list_reverse1(head, NULL), it returns a pointer to the head of the new list. Iterative function call is self explanatory.

Time Complexity: O(n)

/* recursive */

list *list_reverse_recursive(list *curr, list *prev)
{
list *head = NULL;

if (curr == NULL) {
return prev;
}

head = list_reverse_recursive(curr->next, curr);
curr->next = prev;

return head;
}

/* iterative */
void list_reverse_iterative(list **head)
{
list *prev = NULL, *curr = *head, *next = NULL;

while (curr != NULL) {
next = curr->next;

curr->next = prev;
prev = curr;
curr = next;
}
*head = prev;
}

Sieve of Eratosthenes - Prime Numbers

2012-03-19T01:35:00.002-07:00

Question: Provide a simple algorithm that prints all prime numbers smaller than given number N.

The sieve of Eratosthenes is a simple algorithm for finding all prime numbers up to any given number N. It does so by iteratively marking multiples of prime numbers starting from 2.

Time Complexity: O(n)

int soe(int n, int *array)
{
int x, y;

for (x = 2; x <= (n/2); x++)
{
if (array[x] == 1) continue;

for (y = 2 * x; y < n; y += x) {
array[y] = 1;
}
}
}

Array is memset to zero before calling this function. Once above function has processed the array, array index between 2 and N with value zero are prime numbers.

Prime numbers less than 100: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

Prime numbers less than 1000: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997

Euclid's Algorithm - Greatest Common Divisor (GCD)

2012-03-18T22:08:00.002-07:00

Question: The greatest common divisor (GCD), also known as the greatest common factor (GCF), or highest common factor (HCF), of two or more non-zero integers, is the largest positive integer that divides both the numbers without a remainder. Provide an efficient algorithm to compute GCD of two numbers.

The Euclid's algorithm is an efficient method for computing the greatest common divisor.

int gcd(int n1, int n2)
{
int temp;

if (!n1) {
return n2;
}

while (n2 != 0) {
temp = n2;
n2 = n1 % n2;
n1 = temp;
}

return n1;
}

Reverse the order of words in a string

2012-03-16T09:29:00.000-07:00

Q: Write a C program to reverse the order of words in a string. For simplicity, space has been chosen as word delimiter and punctuation is considered part of the word.

Example:
Input: Can you reverse the words in this string.
Output: string. this in words the reverse you Can

Time Complexity: O(log(n))

void reverse_word(char *word, int length)
{
int start;
int end = length - 1;
char temp;

for (start = 0; start < end; start++, end--) {
temp = word[start];
word[start] = word[end];
word[end] = temp;
}
}

void reverse_string(char *string)
{
int index;
int string_length = strlen(string);
int word_start_index = 0;
int word_length = 0;

// Reverse the original string
reverse_word(string, string_length);

for (index = 0; index < string_length; index++) {
// found word delimiter
if (string[index] == ' ') {
reverse_word(&string[word_start_index], word_length);
word_length = 0;
word_start_index = index + 1;
} else {
word_length++;
}
}

// Reverse the last word
if (word_length) {
reverse_word(&string[word_start_index], word_length);
}
}

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 -3, 2, -4, 4, -1, 3, 2, -5, 4 should return the sum as eight, sub-array start index is 3 and sub-array end index is 6.

Time Complexity: O(n)

int
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);<br>

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/>.