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

XOR Linked List

Write a memory efficient Doubly Linked List with the following structure

typedef struct ListNode
{     int data;
       struct ListNode *ptrdiff;
};

where ptrdiff pointer contains the difference between the pointer to the next node and the pointer to previous node.Pointer difference is calculated using XOR operation

ptrdiff= pointer to previous node  XOR  pointer to next node

XOR List Representation:
Let us call the address variable in XOR representation npx (XOR of next and previous)
Node A:
npx = 0 XOR add(B) // bitwise XOR of zero and address of B
Node B:
npx = add(A) XOR add(C) // bitwise XOR of address of A and address of C
Node C:
npx = add(B) XOR add(D) // bitwise XOR of address of B and address of D
Node D:
npx = add(C) XOR 0 // bitwise XOR of address of C and 0

Traversal of XOR Linked List:
We can traverse the XOR list in both forward and reverse direction. While traversing the list we need to remember the address of the previously accessed node in order to calculate the next node’s address. For example when we are at node C, we must have address of B. XOR of add(B) and npx of C gives us the add(D). The reason is simple: npx(C) is “add(B) XOR add(D)”. If we do xor of npx(C) with add(B), we get the result as “add(B) XOR add(D) XOR add(B)” which is “add(D) XOR 0″ which is “add(D)”. So we have the address of next node. Similarly we can traverse the list in backward direction.

Useful Links:
http://en.wikipedia.org/wiki/XOR_linked_list
http://www.linuxjournal.com/article/6828?page=0,0
http://www.geeksforgeeks.org/archives/12367

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

Insert a substring in a string

C program to insert substring into a string: This code inserts the target string into the source string.

For example if the source string is "c programming" and target string is " is amazing" (please note there is space at beginning) and if we add target string to source string at position 14 then we obtain the string "c programming is amazing". In our c code we will make a function which perform the desired task and we pass three arguments to it the source string, target string and position. You can insert the string at any valid position.

 Code:

#include <string.h>
#include <stdlib.h>
#include <iostream>

void insert_substring(char*, char*, int);
char* substring(char*, int, int);

main()
{
   char text[100], substring[100];
   int position;

   printf("Enter some text\n");
   gets(text);

   printf("Enter the string to insert\n");
   gets(substring);

   printf("Enter the position to insert\n");
   scanf("%d", &position);

   insert_substring(text, substring, position);

   printf("%s\n",text);
   system("pause");

   return 0;
}

void insert_substring(char *a, char *b, int position)
{
   char *f, *e;
   int length;

   length = strlen(a);

   f = substring(a, 1, position - 1 );     
   e = substring(a, position, length-position+1);

   strcpy(a, "");
   strcat(a, f);
   free(f);
   strcat(a, b);
   strcat(a, e);
   free(e);
}

char *substring(char *string, int position, int length)
{
   char *pointer;
   int c;

   pointer =(char*) malloc(length+1);

   if( pointer == NULL )
       exit(EXIT_FAILURE);

   for( c = 0 ; c < length ; c++ )
      *(pointer+c) = *((string+position-1)+c);      

   *(pointer+c) = '\0';

   return pointer;
}

Generate Random Numbers

#include <stdio.h>
#include <stdlib.h>
 
int main() {
  int c, n;
 
  printf("Ten random numbers in [1,100]\n");
 
  for (c = 1; c <= 10; c++) {
    n = rand()%100 + 1;
    printf("%d\n", n);
  }
 
  return 0;
} 

Find parity of an unsigned integer

Parity: Parity of a number refers to whether it contains an odd or even number of 1-bits. The number has “odd parity”, if it contains odd number of 1-bits and is “even parity” if it contains even number of 1-bits.

Main idea of the below solution is – Loop while n is not 0 and in loop unset one of the set bits and invert parity.

Algorithm: getParity(n)
1. Initialize parity = 0
2. Loop while n != 0      
      a. Invert parity 
             parity = !parity
      b. Unset rightmost set bit
             n = n & (n-1)
3. return parity

Example:
 Initialize: n = 13 (1101)   parity = 0

n = 13 & 12  = 12 (1100)   parity = 1
n = 12 & 11 = 8  (1000)   parity = 0
n = 8 & 7 = 0  (0000)    parity = 1

Code:

# include <stdio.h> # define  bool int bool getParity(unsigned int n) {     bool parity = 0;     while (n)     {         parity = !parity;         n      = n & (n - 1);     }            return parity; } int main() {     unsigned int n = 7;     printf("Parity of no %d = %s",  n,              (getParity(n)? "odd": "even"));           getchar();     return 0; }

Above solution can be optimized by using lookup table.
Time Complexity: The time taken by above algorithm is proportional to the number of bits set. Worst case complexity is O(Logn).
Uses: Parity is used in error detection and cryptography.