Array manuplation

Given a array of random integers, sort the odd elements in descending order and even numbers in ascending order. Optimize for time complexity.
e.g. for i/p (1,4,5,2,3,6,7) O/p = (7,5,3,1,2,4,6)

Answer :
We can solve this by doing a simple bubble sort, with the below logic

1. if first number and second number are odd >> compare and exchange >> push lower odd to first
2. if first is odd and second is even >> no exchange >> we want odd in the first
3. if first is even and second is also even >> compare and exhange >> push higher even number to last
4. if first is even and second is odd >> always exchange >> since we want odd numbers first

Here is the complete solution in C

#include <stdio.h>

int a[] = {1,4,5,2,3,6,7};
int len = 7;

void main(void)
{
    int i,j, temp;
    for(i = 0; i < len-1; i++)
    {
        for(j = 0; j< len-1; j++)
        {
         if( a[j] %2  != 0) 
         {     // first odd number
             if(a[j+1] % 2 != 0) 
             {   
                 // second odd number
                 if(a[j] < a[j+1]) 
                 {
                     temp = a[j+1];
                     a[j+1] = a[j];
                     a[j] = temp;
                 }
             }
             else 
             {     // second even number 
                 //do nothing
             }
         }
         else 
         {     // first even number
             if(a[j+1] % 2 != 0) 
             {   
                 // second odd number
                 // always interchange
                 temp = a[j+1];
                 a[j+1] = a[j];
                 a[j] = temp;
             }
             else
             {
                 // second even number
                 if(a[j] > a[j+1])
                 {
                     temp = a[j+1];
                     a[j+1] = a[j];
                     a[j] = temp;
                 }
             }
         }
        }
    }
    for(i=0; i<len; i++)
    printf("%d ", a[i]);
}

Find the Odd ball

You are given 80 balls and out of which only 1 has more weight than other 79. also, you are given weighing machine which can weigh any number of balls of 2 sets( 40 40 or 25 25 etc) at one time

Answer:
Assume the ball we need to find is X. Divide into 3 groups, A (27 balls), B (27 balls), C (26 balls)

Step 1: Weight A vs B, whichever is heavier has X. If equal, then C has X. If C has X, choose a random ball in A and put into C so that C has 27 balls.

Step 2: After step 1, we determine which group has X, and the group size is 27. Divide into 3 smaller groups, each of size 9, and repeat the same procedure.

In short, we have, 80 -> 27 -> 9 -> 3 -> 1, 4 steps in total to find X.

In general , if there are n balls , log_3(n) is the answer, or find out how many powers 3 should be raised to cross the total number of balls

Sub Strings

write a code for which input is a string and set of characters acting as delimiters. Cut the given string where ever delimiters occur and return all the set of sub strings. For eg: given string abbcdeffghujsb and delimiter set:c,g,j hen output should be: abb, deff, u, sb

Answer goes as below

char delimiter[] = {'c', 'j' , 'f'};

void get_sub_str(const char *str, char *dl, int dn)
{
    char temp[1024];
    int i, j, len = 0;
    int ssu = 0; // sub string update
    for(i=0; str[i]!='\0'; i++)
    {
       for(j=0; j<dn; j++)
       {
           if( str[i] == dl[j])
               ssu = 1;
       }
       if(ssu == 1)
       {
           temp[len] = '\0';
           printf("%s\n", temp);
           len = 0;
           ssu = 0;
           i++;
       }
       temp[len] = str[i];
       len++;
    }
}

Signed and Unsigned

1. What is the output of the following program

main() {
    unsigned int a = 10;
    int b = -19;
    puts((a+b)>0? "Positive":"Negative");
}

Answer : Positive
Explanation : When signed and unsigned arithmetic is done, signed is converted to unsigned and result will be unsigned, ANSI C standard.

Linked List Example

Recently I was recalling my linked list concepts, and I found that I know the concepts, but when programming I am missing something. So I thought I should do it once again, so I made a simple program, which can add / delete elements from linked list. here it is for your reference.

shetty.h, this file contains the basic type definitions required.

#ifndef __SHETTY_H_
#define __SHETTY_H_

typedef struct le {
    int ld;
    le *next;
} le;

typedef struct lh {
    le *next;
} lh;

#endif // __SHETTY_H_

Shetty.cpp, this file contains all the functionality required to add or delete from the linked list. The comments are self explanatory.

#include "shetty.h"
#include "malloc.h"
#include "stdio.h"

lh list;

/********************************************
** This function adds an element to Linked
** list, the head to list and element to be
** added is given as params.
** lst - pointer to the head of the list
** ld  - an integer data, u can change this
**       to whatever type you want to.
********************************************/
void add_list(lh *lst, int ld)
{
    le *element;
    le **tmp;
    element = (le *) malloc (sizeof(*element));
    element->ld = ld;
    element->next = NULL;

    tmp = &(lst->next);
    while(*tmp!=NULL)
        tmp = &((*tmp)->next);
    *tmp = element;
}

/********************************************
** This function removes an element from the
** Linked list
********************************************/
void remove_list(lh *lst, int ld)
{
    le **tmp, **prev;
    le *deleted;

    tmp = &(lst->next);
    prev = tmp;
    while(*tmp!=NULL)
    {
        if((*tmp)->ld == ld)
        {
            deleted  = (*prev)->next;      
            (*prev)->next = (*tmp)->next;
            free(deleted);                  
        }
            prev = tmp;
            tmp = &((*tmp)->next);
    }
}

/**************************************
** Display the list to see elements
**************************************/
void disp_list(lh *lst)
{
    le **tmp;
    tmp = &(lst->next);
    while(*tmp!=NULL)
    {
        printf("%d\t", (*tmp)->ld);
        tmp = &((*tmp)->next);
    }
    printf("\n");
}
int main(void)
{
    list.next = NULL;
    add_list(&list, 25);
    add_list(&list, 30);
    disp_list(&list);
    add_list(&list, 45);
    disp_list(&list);
    add_list(&list, 55);
    disp_list(&list);
}

Here, only one thing is important in dealing with linked list. i.e we need to get the address of the next pointer in a temp variable, and then change this variable with different address as we traverse the list. We should not modify any of the pointers in the list while traversing, unless we want to add or delete from the list.