Friday, August 3, 2012

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

Wednesday, August 1, 2012

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.