Friday, August 3, 2012
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:
Useful Links:
http://en.wikipedia.org/wiki/Event-driven_programming
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.
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
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.
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.
Subscribe to:
Posts (Atom)