Lowest Common Multiple (LCM)

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

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)

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

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

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)

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

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

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;
    }

}