Loading...

Wednesday, June 19, 2013

Find a number in a rotated sorted array.

Here is program i wrote

#include <stdio.h>
#include <iostream>

using namespace std;

void rotateArray( int *a , int size, int rotation)
{
int len = size;
if (len < rotation ) return;
int *temp = new int [rotation];
int i = 0;
int temp_index = 0;
for ( i = len-rotation; i < len;i++)
temp[temp_index++] = a[i];
for ( i = len-rotation -1;  i>=0; i--)
a[i+rotation] = a[i];
for ( i = 0; i < rotation;i++)
a[i] = temp[i];
delete temp;
}


void search( int *a, int size, int number)
{
int low = 0;
int high = size -1;
while (low <= high)
{
int mid = low+(high - low)/2;
if ( number == a[mid] )
{
cout<<"Got number @"<<mid<<endl;
return;
}
if ( a[low] < a[mid]) //Lower part sorted
{
if ( a[mid] > number && a[low] <= number )
high = mid-1;
else
low = mid+1;
}
else //Upper part sorted
{
if ( a[mid] < number && a[high] >= number )
low = mid+1;
else
high = mid-1;
}
}
cout<<"Number is not present in array"<<endl;
}

void printArray ( int *a, int size)
{
for ( int i = 0; i < size;i++)
cout <<a[i]<<" ";
cout<<endl;

}
int main()
{
int arr[] = { 1, 2,3,4,5,6,7,8,9 };
int size = sizeof(arr)/sizeof(arr[0]);
rotateArray(arr, size, 3);
printArray(arr, size);
search(arr, size, 8);
return 0;
}



Tuesday, June 18, 2013

Adding two number wihtout arithmatic operation and without loop


Here is algo:

1. Receive A and B as input.
2. if A or B is zero then goto step 8.
3. xor_a_b = A^B
4. and_a_b = A & B << 1
5. A = xor_a_b
6. B = and_a_b
7. goto step 2
8. Print non zero value of A, B



Lets try doing some example to understand how things work with above logic
A | B | A^B | A&B|A&B<<1
2  | 3 | 01     | 10| 100
1 | 4 | 101|0|0
0|5

If Any of operand is zero, return other operand which is Sum. So 5 is answer.

Let try with other arguments

A | B | A^B | A&B|A&B<<1
5  | 7 | 010    | 101| 1010
2 | 10 | 1000|10|100
8|4|1100|0|0
12|0

So operand 2 is zero, so result is 12.

Monday, June 17, 2013

[C++] Main function as Inline??

Main can not be inline in C++.

Compiler start program invocation by calling main method and if main is inlined there wont be any address for main method and compiler wont be able to call main (off-course depend on linker )


[JAVA]Lazy vs eager Loading

JVM loads referenced classes which have not been linked to runtime system.
There are two ways classes are linked with runtime
1. Initial Class files
2. Policy based either eager or lazy.

Eager loads all the classes at startup of program execution.
Lazy loading will load classes when actually needed i.e.
a) Instance of class is created.
b) subclass is initialized.
c) One of static field initialized.

Feel free to add your comments.