Inline functions in C

Discuss use of inline functions in C

http://www.greenend.org.uk/rjk/tech/inline.html

Event Driven Programming

In computer programming, event-driven programming or event-based programming is a programming paradigm in which the flow of the program is determined by events—e.g., sensor outputs or user actions (mouse clicks, key presses) or messages from other programs or threads.
Event-driven programming can also be defined as an application architecture technique in which the application has a main loop which is clearly divided down to two sections:

• the first is event selection (or event detection)
• the second is event handling.

In embedded systems the same may be achieved using interrupts instead of a constantly running main loop; in that case the former portion of the architecture resides completely in computer hardware

Useful Links:
http://en.wikipedia.org/wiki/Event-driven_programming

Point of transition from 0 to 1 in an infinite sorted array

Given an input array of size unknown with all 1's in the beginning and 0's in the end. Find the index in the array from where 0's start, consider there are millions of 1's and 0's in the array .i.e array is very big e.g array contents 1111111.......1100000.........0000000

Strategy:

Since the array is infinitly increasing i.e. we don't know arrry size in advance, so we can't directly apply traditional BinarySearch (in which we partition the problem size in half in each iteration, kind of top down approach). We can apply reverse of BinarySearch approach.
We can think of sorted infinite 0 and 1 array as infinite size bit stream on disk with 0 set bits followed by 1 bits.

Approach: 
Start with first bit, if it is 1 we are lucky and got the switch index, else if it is 0 check the 2,4,8,16,32,64.... 2^n bits till we get first 1 set bit index say its 'i'. (We are moving by power of 2, rather than 3, 4 etc, because it minimizes the range of data to find the element). Now we have to find between index i/2 to i where the swich happened and this can be done by simple binary search (size of the array to look into is i/2).
Time Complexity: log(N), N is index at which switch happened.

An even faster solution would be to use bit operators as they are faster so instead of comparing with you could XOR with 1 and the index where it gives a 0 on XORing is the required index where first 0 is present.

Programming Puzzles

The following links are useful for programming teasers / simple puzzles.

http://www.coderanch.com/forums/f-71/Programming
http://www.geekinterview.com/talk/brainteasers/

RTOS specifc Questions

RTOS vs GPOS 

GPOS:- no time boundation,task hasnt got any time limit to
finish work. 

------------------- 

An RTOS is a special case of GPOS. 
1. In RTOS every task must have a priority.
2. Pre-emption is a must feature.
3. Priority Inheritance is must otherwise priority 
inversion may cause unbounded wait.

------------------- 
RTOS:- time boundation, task has to complete work within
given time frame. For this preemtive scheduling is must.OS uses Round

Robin scheduling. 

------------------- 

GPOS USES A MONOLITHIC ARCHITECTURE WHILE 
RTOS USES A FLAT MEMORY ARCHITECTURE.  

BIT Manipulation puzzles

Convert number 2 --> 37 without using any other operator but bitwise ? 

Solution:
#include<stdio.h>
#include<stdlib.h>
int main(void)
{
   int x = 2;
    printf("X before :%d\n",x);
    x = (x<<x<<x) |  x<<!!x | !!x ;
    printf("X After  :%d\n",x);
     getchar();
     return(0);
} 

OS Boot Sequence

Explain OS boot sequence

http://www.webopedia.com/DidYouKnow/Hardware_Software/2004/BootProcess.asp
http://en.wikipedia.org/wiki/Booting
http://www.pcguide.com/ref/mbsys/bios/bootSequence-c.html

CPU cycle

what do you mean by CPU cycle and why is it important ?

http://en.wikipedia.org/wiki/Instruction_cycle

Implement malloc

How to implement malloc ?

http://www.ibm.com/developerworks/linux/library/l-memory/
http://lambda.uta.edu/cse5317/notes/node45.html
http://simplestcodings.blogspot.in/2010/08/custom-malloc-function-implementation.html

Scan for a bit pattern in a stream of bits

We need to scan for a 16 bit word in a bit stream. It is not guaranteed to be aligned on byte or word boundaries.
There are various brute force methods; using tables and/or shifts.But what is the best way to do this ?

Qualcomm Interview Questions & Tips

The following things are important for Interviews in Qualcomm

1.Why do you want to switch company ?
Be specific in your answer.

2.Resume
Know each and everything about your resume and projects.

3.What was the most difficult technical issue that you had and how did you solve it?

4.The following topics are very important

----String Manipulation
----BIT manipulation
----C Concepts

Prime Numbers

Find all the prime numbers less than or equal to a given integer n

Prime Number Generation upto a specific count:

#include<stdio.h>
 
main()
{
   int n, i = 3, count, c;
 
   printf("Enter the number of prime numbers required\n");
   scanf("%d",&n);
 
   if ( n >= 1 )
   {
      printf("First %d prime numbers are :\n",n);
      printf("2\n");
   }
 
   for ( count = 2 ; count <= n ;  )
   {
      for ( c = 2 ; c <= i - 1 ; c++ )
      {
         if ( i%c == 0 )
            break;
      }
      if ( c == i )
      {
         printf("%d\n",i);
         count++;
      }
      i++;
   }         
 
   return 0;
}

There are many logic to check prime numbers, one given below is more 

efficient then above method.
for ( c = 2 ; c 
//only checking from 2 to square root of number is sufficient. 

Program for Prime Number or not:

#include<stdio.h>
main()
{
   int n, c = 2;
 
   printf("Enter a number to check if it is prime\n");
   scanf("%d",&n);
 
   for ( c = 2 ; c <= n - 1 ; c++ )
   {
      if ( n%c == 0 )
      {
         printf("%d is not prime.\n", n);
  break;
      }
   }
   if ( c == n )
      printf("%d is prime.\n", n);
 
   return 0;
}

Prime Numbers Less than a number:

#include <stdio.h>
#include <iostream>
int main()
{
   int n,i=1,j,c;
   printf("Enter Number Of Terms");
   printf("Prime Numbers Are Following\n");
   scanf("%d",&n);
   while(i<=n)
   {
      c=0;
      for(j=1;j<=i;j++)
      {
              if(i%j==0)
        c++;
       }
           if(c==2)
           printf("%d\n",i);
           i++;
        }
        system("pause");
        return 0;
}

Efficient Method for Prime Numbers:

We can use Sieve of Eratosthenes method:

• Create a list of consecutive integers from two to n: (2, 3, 4, ..., n).
• Initially, let p equal 2, the first prime number.
• Strike from the list all multiples of p less than or equal to n. (2p, 3p, 4p, etc.)
• Find the first number remaining on the list after p (this number is the next prime); replace p with this number.
• Repeat steps 3 and 4 until p2 is greater than n.
• All the remaining numbers in the list are prime.
  
  void GeneratePrimes(int N)
  { bitset<1000> b;
  for(int i = 2; i < N; i )
       { if(!b[i])
                { //Mark all multiples of i to 1 as there are not prime numbers int k = 2;
                while((i * k) < N){ b[i * k] = 1; k ; }
       }
    for(int i = 2; i < N; i )
           { if(!b[i]) cout << i << " "; }
  }

Links:
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Structure & Bit Fields

Both C and C++ allow integer members to be stored into memory spaces smaller than the compiler would ordinarily allow. These space-saving structure members are called bit fields, and their width in bits can be explicitly declared. Bit fields are used in programs that must force a data structure to correspond to a fixed hardware representation and are unlikely to be portable.
The syntax for declaring a bit field is as follows:

>>-type_specifier--+------------+--:--constant_expression--;---><
                   '-declarator-'
 
 

A bit field declaration contains a type specifier followed by an optional declarator, a colon, a constant integer expression that indicates the field width in bits, and a semicolon. A bit field declaration may not use either of the type qualifiers, const or volatile.
The C99 standard requires the allowable data types for a bit field to include qualified and unqualified _Bool, signed int, and unsigned int. In addition, this implementation supports the following types.

• int
• short, signed short, unsigned short
• char, signed char, unsigned char
• long, signed long, unsigned long
• long long, signed long long, unsigned long long

In all implementations, the default integer type for a bit field is unsigned.
C++ extends the list of allowable types for bit fields to include any integral type or enumeration type.
In either language, when you assign a value that is out of range to a bit field, the low-order bit pattern is preserved and the appropriate bits are assigned.
Bit fields with a length of 0 must be unnamed. Unnamed bit fields cannot be referenced or initialized. A zero-width bit field can cause the next field to be aligned on the next container boundary where the container is the same size as the underlying type of the bit field.
Bit fields are also subject to the align compiler option. Each of the align suboptions gives a different set of alignment properties to the bit fields. For a full discussion of the align compiler option and the #pragmas affecting alignment, see XL C/C++ Compiler Reference.
The following restrictions apply to bit fields. You cannot:

• Define an array of bit fields
• Take the address of a bit field
• Have a pointer to a bit field
• Have a reference to a bit field

The following structure has three bit-field members kingdom, phylum, and genus, occupying 12, 6, and 2 bits respectively:

struct taxonomy {
     int kingdom : 12;
     int phylum : 6;
     int genus : 2;
     };

Alignment of Bit Fields
If a series of bit fields does not add up to the size of an int, padding can take place. The amount of padding is determined by the alignment characteristics of the members of the structure.
The following example demonstrates padding, and is valid for all implementations. Suppose that an int occupies 4 bytes. The example declares the identifier kitchen to be of type struct on_off:

struct on_off {
                  unsigned light : 1;
                  unsigned toaster : 1;
                  int count;            /* 4 bytes */
                  unsigned ac : 4;
                  unsigned : 4;
                  unsigned clock : 1;
                  unsigned : 0;
                  unsigned flag : 1;
                 } kitchen ;

The structure kitchen contains eight members totalling 16 bytes. The following table describes the storage that each member occupies:

Member Name	Storage Occupied
light	1 bit
toaster	1 bit
(padding -- 30 bits)	To the next int boundary
count	The size of an int (4 bytes)
ac	4 bits
(unnamed field)	4 bits
clock	1 bit
(padding -- 23 bits)	To the next int boundary (unnamed field)
flag	1 bit
(padding -- 31 bits)	To the next int boundary

All references to structure fields must be fully qualified. For instance, you cannot reference the second field by toaster. You must reference this field by kitchen.toaster.
The following expression sets the light field to 1:

  kitchen.light = 1;

When you assign to a bit field a value that is out of its range, the bit pattern is preserved and the appropriate bits are assigned. The following expression sets the toaster field of the kitchen structure to 0 because only the least significant bit is assigned to the toaster field:

  kitchen.toaster = 2;

Reference Links:

http://publib.boulder.ibm.com/infocenter/macxhelp/v6v81/

index.jsp?topic=%2Fcom.ibm.vacpp6m.doc%2Flanguage%2Fref%2Fclrc03defbitf.htm

http://c-faq.com/struct/bitfields.html

C Program to calculate factorial of a number

Iterative:

int findFactorial(int num){

    int i,f=1;

    for(i=1;i<=num;i++)

      f=f*i;

     return f;

}
Recursive:

fact(int n)
{
    int fact;
    if(n==1)
        return(1);
    else
        fact = n * fact(n-1);
    return(fact);
}

C Program to Calculate pow(x,n)

Write brute force ,recursion and divide and conquer approach to get pow(x,n) in?

Recursion:
int pow(int x, int y)
{
  if(y == 1) return x ;
  return x * pow(x, y-1) ;
}

Modified Recursion with Min. Number of multiplications:

  double power(double x, unsigned int n)
{
   if (!n) return 1.0;
   if (n == 1) return x;
   double result = power(x, n/2);
   result *= result;
   return (n&1) ? result*x : result;
}

Divide and conquer

#include < stdio.h >
int main(int argc, char*argv[])
{
  printf("\n[%d]\n",pow(5,4));
}
int pow(int x, int n)
{
  if(n==0)return(1);
  else if(n%2==0)
  {
    return(pow(x,n/2)*pow(x,(n/2)));
  }
  else 
  {
    return(x*pow(x,n/2)*pow(x,(n/2)));
  }
}  

Sorted Insert in a Linked List

Insert elements in sorted manner in the following Linked List

1.Singly
2.Doubly
3.Circular

String Manipulation Problems

1.Divide a string in n equal parts
http://www.geeksforgeeks.org/divide-a-string-in-n-equal-parts/

2.Remove Spaces / Trim a string
http://www.geeksforgeeks.org/remove-spaces-from-a-given-string/

Variation 1:
Remove multiple spaces from a string and keep only 1 space in between two words.You are also required to remove leading and trailing spaces in order to make a sentence.
http://www.geeksforgeeks.org/remove-extra-spaces-string/

3.atoi() and itoa()
http://www.geeksforgeeks.org/write-your-own-atoi/
http://www.geeksforgeeks.org/implement-itoa/

4.String Text Justification
http://www.programcreek.com/2014/05/leetcode-text-justification-java/

5.Escape all % characters in a string; % is the escape character
Example :
Input : India has GDP of 10% in 2009
Output : Input has GDP of 10%% in 2009
Strategy:

It is usually not be possible to do this in-place since the original unescaped string may not have enough space in the array to store the additional escape characters. But if we create a new array, O(n) algo is possible, though space complexity will increase.

String escapePercent(String input) {
    StringBuilder sb = new StringBuilder();
    char[] str = input.toCharArray();

    for (int i = 0; i < input.length(); i++) {
        if (str[i] == ‘%’) sb.append(‘%’);
        sb.append(str[i]);
    }

    return new String(sb);
}

6. Remove duplicates from a string
Variation 1 http://www.geeksforgeeks.org/recursively-remove-adjacent-duplicates-given-string/
Variation 2 http://www.geeksforgeeks.org/remove-all-duplicates-from-the-input-string/
Variation 3 Write a function that deletes consecutive identical character sets of size 1, 2, 3. For example if aabbabc is given as input after first iteration, it should be ababc and after that it should become abc. if aabbcabc is given it should give abcabc after first interation, no change in second iteration and abc after third iteration.
Variation 4 http://www.geeksforgeeks.org/check-string-can-become-empty-recursively-deleting-given-sub-string/
Variation 3 Solution
The approach is based on Sliding window approach where in a window, the first & last characters are being compared.
#include <stdio.h>
#include <string.h>

void rem(char *str,int N,int k)
{
        int low,high,i,j,L;

        for(L=1;L<=k;L++)
        {
                i=L;j=L;
                while(i<N)
                {
                        low=i-L;high=i;
                        if(low>=0)
                        {
                                if(str[low]!=str[high])
                                        str[j++]=str[i];
                        }
                        i++;
                }
                str[j]='\0';
                N=j;
                printf("%s\n\n",str);
        }
       
}

int main()
{
        char str[]="abcabcabcabc",k=3;
        rem(str,strlen(str),k);
        return 0;
}

The above algo can be further simplified.

void rem(char *str,int N,int k)
{
        int low,high,i,j,len,top;

        for(len = 1; len <= k; ++len)
        {
                top  = len;
                for(low = 0,high = low+len; high < N; ++high,++low)
                {
                        if(str[high] && str[low] != str[high])
                                str[top++] = str[high];
                }
                str[top++] = '\0';
                N = top;
                printf("%s\n",str);
        }

}

7. Remove specified characters from a string
You are given 2 strings. The first string is the input string that needs to be cleaned (in place) and the second string contains characters that need to be removed from the the first string. For example if string1 = "teetotaller" and removeString= "ae" then the output (cleaned string) will look like "ttotllr".

Strategy:

• Loop through individual characters of string1 and check if they exist in the removeString.
• Copy a character back to the input string only if it doesn't exist in removeString.
• Terminate the string with a NULLCHAR ('\0').

Code:

#include<stdio.h>
#include<string.h>

int main()
{ 
char str[]="teeetotalleer";
char toremove[]="aae";
int i=0,j=0;
int flag[256]={0};

while(toremove[i]!='\0')
   {flag[toremove[i]]++;
   i++;}
   
i=0;
while(str[i]!='\0')
   { 
    if(flag[str[i]]==0)
       str[j++]=str[i];
    i++;
   }
str[j]='\0';      
printf("\n%s",str);
getchar();
return 0;

} 

//Removes the specified characters from an input string
void RemoveCharacters(char str[], char remove[])
{
int strLen = strlen(str);
int removeStrLen = strlen(remove);

bool removeCharacterFlags[128] = {false}; // assume ASCII character set

// set the flag for characters present in the remove string
for(int i=0; i<removeStrLen; i++)
{
    removeCharacterFlags[remove[i]] = true;
}

int destIndex = 0;      // index within the input string where the next
                        // clean character will go.
for(int i=0; i<strLen; i++)
{
    if(!removeCharacterFlags[str[i]])
    {
        str[destIndex++] = str[i];
    }
}
str[destIndex] = '\0';
}

Thread safe & Reentrant code in C

What do you mean by thread safe and reentrant code in C

Useful Links:-
http://en.wikipedia.org/wiki/Thread_safety
http://en.wikipedia.org/wiki/Reentrancy_%28computing%29
http://publib.boulder.ibm.com/infocenter/aix/v6r1/index.jsp?topic=%2Fcom.ibm.aix.genprogc%2Fdoc%2Fgenprogc%2Fwriting_reentrant_thread_safe_code.htm
Rentrancy Guide:-http://www.ibm.com/developerworks/linux/library/l-reent/index.html

staic vs const vs static const vs const volatile

explain the difference between static, const & static const varibales  & methods.

const volatile:
const volatile usigned int *REG_A = (usigned int *) init_hardware_n_return_address of REG_A();

In the above snippet function "init_hardware_n_return_address of REG_A()" modifies the content of the REG_A( register A say) of a peripheral device , say after initiatialising it ( which cause the content of R/W register REG_A modified by peripheral itself) and returns the address of REG_A to the program .

The assignment in the above snippet implies here that content of REG_A can be modifiable only be external sources like peripheral hardware itself and and your code is not supposed to modify the content of REG_A . Also whenever such variable is encountered compiler should "load " it value every time instead of doing any code optimasation
Typically memory mapped variables are one consumers for such usage

Concept of Indivisible Operations:

Those of you who are familiar with techniques that involve hardware interrupts and other ‘real time’ aspects of programming will recognise the need for volatile types. Related to this area is the need to ensure that accesses to data objects are ‘atomic’, or uninterruptable.
Be careful not to assume that any operations written in C are uninterruptable. For example,

extern const volatile unsigned long realtimeclock;

could be a counter which is updated by a clock interrupt routine. It is essential to make it volatile because of the asynchronous updates to it, and it is marked const because it should not be changed by anything other than the interrupt routine. If the program accesses it like this:

unsigned long int time_of_day;

time_of_day = real_time_clock;

there may be a problem. What if, to copy one long into another, it takes several machine instructions to copy the two words making up real_time_clock and time_of_day? It is possible that an interrupt will occur in the middle of the assignment and that in the worst case, when the low-order word of real_time_clock is 0xffff and the high-order word is 0x0000, then the low-order word of time_of_day will receive 0xffff. The interrupt arrives and increments the low-order word of real_time_clock to 0x0 and then the high-order word to 0x1, then returns. The rest of the assignment then completes, with time_of_day ending up containing 0x0001ffff and real_time_clock containing the correct value, 0x00010000.
This whole class of problem is what is known as a critical region, and is well understood by those who regularly work in asynchronous environments. It should be understood that Standard C takes no special precautions to avoid these problems, and that the usual techniques should be employed.
The header ‘signal.h’ declares a type called sig_atomic_t which is guaranteed to be modifiable safely in the presence of asynchronous events. This means only that it can be modified by assigning a value to it; incrementing or decrementing it, or anything else which produces a new value depending on its previous value, is not safe.

Compiler interpretation of const volatile:

Let us see an example to understand how compilers interpret volatile keyword. Consider below code, we are changing value of const object using pointer and we are compiling code without optimization option. Hence compiler won’t do any optimization and will change value of const object.

/* Compile code without optimization option */ #include <stdio.h> int main(void) {     const int local = 10;     int *ptr = (int*) &local;     printf("Initial value of local : %d \n", local);     *ptr = 100;     printf("Modified value of local: %d \n", local);     return 0; }

When we compile code with “–save-temps” option of gcc it generates 3 output files
1) preprocessed code (having .i extention)
2) assembly code (having .s extention) and
3) object code (having .o option).
We compile code without optimization, that’s why the size of assembly code will be larger (which is highlighted in red color below).
Output:

[narendra@ubuntu]$ gcc volatile.c -o volatile –save-temps
  [narendra@ubuntu]$ ./volatile
  Initial value of local : 10
  Modified value of local: 100
  [narendra@ubuntu]$ ls -l volatile.s
  -rw-r–r– 1 narendra narendra 731 2016-11-19 16:19 volatile.s
  [narendra@ubuntu]$

---------------------------------------- 

Let us compile same code with optimization option (i.e. -O option). In thr below code, “local” is declared as const (and non-volatile), GCC compiler does optimization and ignores the instructions which try to change value of const object. Hence value of const object remains same.

/* Compile code with optimization option */ #include <stdio.h> int main(void) {     const int local = 10;     int *ptr = (int*) &local;     printf("Initial value of local : %d \n", local);     *ptr = 100;     printf("Modified value of local: %d \n", local);     return 0; }

For above code, compiler does optimization, that’s why the size of assembly code will reduce.
Output:

[narendra@ubuntu]$ gcc -O3 volatile.c -o volatile –save-temps
  [narendra@ubuntu]$ ./volatile
  Initial value of local : 10
  Modified value of local: 10
  [narendra@ubuntu]$ ls -l volatile.s
  -rw-r–r– 1 narendra narendra 626 2016-11-19 16:21 volatile.s

----------------------------------------- 

Let us declare const object as volatile and compile code with optimization option. Although we compile code with optimization option, value of const object will change, because variable is declared as volatile that means don’t do any optimization.

/* Compile code with optimization option */ #include <stdio.h> int main(void) {     const volatile int local = 10;     int *ptr = (int*) &local;     printf("Initial value of local : %d \n", local);     *ptr = 100;     printf("Modified value of local: %d \n", local);     return 0; }

Output:

[narendra@ubuntu]$ gcc -O3 volatile.c -o volatile –save-temp
  [narendra@ubuntu]$ ./volatile
  Initial value of local : 10
  Modified value of local: 100
  [narendra@ubuntu]$ ls -l volatile.s
  -rw-r–r– 1 narendra narendra 711 2016-11-19 16:22 volatile.s
  [narendra@ubuntu]$

The above example explains how compilers interpret volatile keyword. As a practical example, think of touch sensor on mobile phones. The driver abstracting touch sensor will read the location of touch and send it to higher level applications. The driver itself should not modify (const-ness) the read location, and make sure it reads the touch input every time fresh (volatile-ness). Such driver must read the touch sensor input in const volatile manner.

Useful Links:
http://embeddedgurus.com/barr-code/2012/01/combining-cs-volatile-and-const-keywords/
http://msdn.microsoft.com/en-us/library/145yc477%28v=vs.80%29.aspx

Static in C

Discuss all the details regarding Static variables in C.

Static (and global) variables are initialized during the compile-time, so the initial values will simply be embeded in the executable file itself.

1.static is the default storage class for global variables. The two variables below (count and road) both have a static storage class.

static int Count; int Road; main() { printf("%d\n", Count); printf("%d\n", Road); }

2.'static' can also be defined within a function. If this is done, the variable is initalised at compilation time and retains its value between calls. Because it is initialsed at compilation time, the initalistation value must be a constant.

void Func(void) { static Count=1; }

3.There is one very important use for 'static'. Consider this bit of code.

char *Func(void); main() { char *Text1; Text1 = Func(); } char *Func(void) { char Text2[10]="martin"; return(Text2); }

'Func' returns a pointer to the memory location where 'Text2' starts BUT Text2 has a storage class of auto and will disappear when we exit the function and could be overwritten by something else. The answer is to specify:

static char Text[10]="martin";

The storage assigned to 'Text2' will remain reserved for the duration if the program.

4.The static storage class specifier can only be applied to the following names:

• Objects
• Functions
• Class members
• Anonymous unions

You cannot declare any of the following as static:

• Type declarations
• Function declarations within a block
• Function parameters 

5.The keyword static is the major mechanism in C to enforce information hiding. C++ enforces information hiding through the namespace language feature and the access control of classes.

Note:

Static (becoming global in header files) variables can be defined in .h file. However, their definition should also be provided in the same header file. But , doing this makes the static variable as a private copy of the header file ie it cannot be used elsewhere. In normal cases, this is not intended from a header file.However you should make sure that the header is accepted only once by including #ifndef and #ifdef. By this the compiler will not raise errors saying redefinition of same variable.

#ifndef __static_var_definitions__
#define __static_var_definitions__

static int gblCounter;

#endif