Maximum Sum Sub-array (Kadane's Algorithm)

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

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

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

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

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

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

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

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

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