Saturday, January 2, 2010

for programming interview-part7

today we shall discuss a problem related to finding max sum in array such that max sum elements are not adjacent to each other.ie if the array element are given as
1,3,5,10=>13
1,7,9,21=>22
ans

#include < iostream >
using namespace std;
void FindMaxSum(int buf[],int cnt)
{
int incl = 0; // max sequence including the previous item
int excl = 0; // max sequence excluding the previous item
int excl_new=0;

for (int i = 0; i < cnt; i++)
{
// current max excluding i
if (incl > excl)
{excl_new = incl;
cout << "if\t" << excl_new << endl;
}
else
{
excl_new = excl;
cout << "else\t" << excl_new << endl;
}

// current max including i
incl = excl + buf[i];
excl = excl_new;


}
cout << "\nmax sum = " << ((incl > excl)? incl : excl) << endl;
}
int main()
{
int a[5]={3,2,7,10};
FindMaxSum(a,5);
getchar();
return 0;
}

we shall discuss another beautiful problem which is one of my all time favorites the knapsack problem.hope all of u would have studied about this in CLRS.

let W be max weight
let A[] be the array with articles of different weights.
let n be the max number of items

int findprice(int A[],int n)
{
int cost=0;
for(int i=0;i < n;++i)
cost+=max(findprice(A[],n-1),A[i]+findprice(W-A[i],n-1));
return cost;
}

here we can bring various optimization like using dynamic programming like storing in table the values instead of using subsequent rec call

Friday, January 1, 2010

for programming interviews part 7

hi today we shall discuss the problem related to arrays
12.how to left roate an array
#include < iostream >
int main()
{
using namespace std;
int a[5]={3,4,5,1,2};
int k=5,temp=0,i;
for(i=k;i < 5 ;++i)
{

temp=a[i];
a[i]=a[i-k];
a[i-k]=temp;
}
for(i=0;i < 5;++i)
cout << a[i] << endl;
cin.sync();
cin.get();
return 0;
}
14.how to find element in sorted array which is rotated in O(logn)

#include < iostream >
int main()
{
using namespace std;
int a[5]={2,3,4,5,1};
int mid=0,l=0,r=4,key=5;
while(l<=r)
{
mid=l+(r-l)/2;
if(a[mid]==key)
{
cout << mid;
break;
}
if(a[l] > a[mid])
{
if((key > a[mid])&&(key < a[l]))
l=mid+1;
else
r=mid-1;
}
else if(a[r] < a[mid])
{
if((key > a[r])&&( key < a[mid]))
r=mid-1;
else
l=mid+1;
}
else if(key < a[mid])
r=mid-1;
else
l=mid+1;
}



cin.sync();
cin.get();
return 0;
}

16.how to find product of elements in arrray for ith element the product shlould be all the element except ith element without using / operator

#include < iostream >
int main()
{
using namespace std;
int arr[5]={1,2,3,4,5};
int i=0,l=1,r=1;
int res[5]={1,1,1,1,1};
for(i=0;i < 5;++i)
{
res[i]*=l;
res[4-i]*=r;
l*=arr[i];
r*=arr[4-i];
}
for(i=0;i<5;++i)
cout << res[i] << endl;
cin.sync();
cin.get();
return 0;
}

Wednesday, December 30, 2009

for programming interviews part5

hi
today we shall discuss simple problems like


9.Write, efficient code for extracting unique elements from a sorted
list of array. e.g. (1, 1, 3, 3, 3, 5, 5, 5, 9, 9, 9, 9) -> (1, 3, 5, 9 }


#include < iostream >
int main()
{
using namespace std;
int a[20]={1, 1, 3, 3, 3, 5, 5, 5, 9, 9, 9, 9};
int i=0,k=0;
for(i=1;i < 20 ; ++i)
{
if(a[k]==a[i])
continue;
else
{
++k;
a[k]=a[i];
}
}
for(i=0;i < k ; ++i )
cout << a[i];
cin.sync();
cin.get();
return 0;
}


10
Give a fast way to multiply a number by 7

#include < iostream >
int main()
{
using namespace std;
long long int a=0;
cin>>a;
long long int k=a;
k=( a << 3 )-k;
cout << k;
cin.sync();
cin.get();
return 0;
}

11
how to remove characters of string2 from string1

#include < iostream >
#include < string >
#include < map >
int main()
{
using namespace std;
char s1[10],s2[10];
int i=0,j=0;
cout<< "nter string 1";
cin >> s1;
cout << "nter string 2";
cin >> s2;
map < char , int > mp;
i=0;
while(s2[i])
{
mp[s2[i]]=1;
++i;
}
int k=0;
while(s1[i])
{
if(!mp[s1[i]])
s1[k]=s1[i];
//cout << s1[k];
++k;
++i;
//cout << s1;
}

for(i=0; i < k; ++i)
cout << s1[i];

//cout << s1 << endl;
cin.sync();
cin.get();
return 0;
}

11.how does a bootstraploader work in a linux

whoa that was shocker.............!!!!!!!!!!.
dont worry
->the BIOS takes the H/W platform specific tasks
->Once the H/W is recognised and started correctly the BIOS loads and executes partition code
->the boot loader presents the user with the various boots options,it then loads the OS after decompressing it from memory and sets H/W and memory management before calling the start_kernel() method
->the start_kernel() performs major operations for initializations and spawing process like init(),schedulers.
->scheduler-it takes care of sys management when kernel goes dormant
->init-it takes care of displaying user scripts for non OS services that are available for user environment.
->the user gets login screen.


whats difference between segmentation and paging
segmentation->it basically has logical units of arbitrary size
it has user protection,its visible to user via programs
paging-its basically physical units of fixed size it remains hidden from user and not visible in his program.

Monday, December 28, 2009

programming interviews part4

today we shall discuss some problems which require some c features

1.how to find the machine is little endian or big endian

#include < iostream >
using namespace std;
int main()
{
int n=1;
if(*(char*)&n==1)
cout<<"small";
else
cout<<"big";
cin.sync();
cin.get();
return 0;
}

2.
wap for finding the sizeof a particular datatype without using sizeof()

#include < iostream >
//#define size(T)(*((char*)&T+1-*(char*)&T));
#define SIZEOF(var) (size_t)(&var+1) - (size_t)(&var)

using namespace std;
int main()
{
int a;
cout << SIZEOF(a);
cin.sync();
cin.get();
return 0;
}

3.wap for finding if stack grows upward or downwards


#include < iostream >
using namespace std;
int main()
{
auto int a; auto int b;
if((&b-&a)>0)
cout<<"down";
else
cout<<"up";
cin.sync();
cin.get();
return 0;
}

4.wap for converting from one endian to other

int myreversefunc(int num)
{
int byte0, byte1, byte2, byte3;

byte0 = (num & x000000FF) >> 0 ;
byte1 = (num & x0000FF00) >> 8 ;
byte2 = (num & x00FF0000) >> 16 ;
byte3 = (num & xFF000000) >> 24 ;

return((byte0 << 24) | (byte1 << 16) | (byte2 << 8) | (byte3 << 0));
}

5.
wap a c program for swapping nibbles in byte
nibble=4bits
byte=8bits
#include < stdio.h >

unsigned char swap_nibbles(unsigned char c)
{
unsigned char temp1, temp2;
temp1 = c & 0x0F;
temp2 = c & 0xF0;
temp1=temp1 << 4;
temp2=temp2 >> 4;

return(temp2|temp1); //adding the bits
}

int main()
{
char ch=0x34;
printf("\nThe exchanged value is %x",swap_nibbles(ch));
return 0;
}

6.wap for adding 2 numbers without +

some guys like(rancho in 3 idiots mite come up with answers like a-(-b)
which is somewhat acceptable if interviewer isn't like imperial college principal)

for others

#include < iostream >
using namespace std;
int main()
{
int a=5,b=4;
int c=0,d=0;
while(b!=0)
{
c=a^b;
d=a&b;
a=c;
d << = 1;
b=d;
}
cout << a;
cin.sync();
cin.get();
return 0;
}


7.wap for swapping two numbers without
temp variable

#include < iostream >
using namespace std;
int main()
{
int a=7,b=8;
a-=b;
b+=a;
a-=b;
a*=-1;
cout << a << endl << b;
cin.sync();
cin.get();
return 0;
}

Thursday, December 24, 2009

for programming interviews-part3

today we shall discuss a simple problems.
5.how do u find out if a no is divisible by 2 in a single line.?
int x;
x&&!(x&(x-1))

6.wap for single line swap of 2 integers without temp variable.

a^=b^=a^=b;

7.wap for finding max & min of 2 nos without branching?

min : (b-(!(a-b) &-(a < b ) ))
max : (a+(!(a-b) &-(a < b ) ))

8.wap for printing the self source code(this was asked to me in HP interview
actually the ans is quine(self printing code )
but the interviewer sed that it wasnt the answer he was expecting.
but i wrote the code for quine .he replied even a 7th grader could write tat code.....
ans:
char *f={"char*f=%c%s%c;main(){ printf(f,34,f,34,10);%c";main(){printf(f,34,f,34,10);}

9.how to print a matrix spiraaly
ans:
for(i=size(a) ,j=0;i > = 0; --i, ++j)
{
for(k=j;k < i; ++k)cout << a[j][k];
for(k=j;k < i; ++k)cout << a[k][i];
for(k=i;k > j; --k)cout << a[i][k];
for(k=j;k > j; --k)cout << a[k][j];
}
if(size(a)%2 == 0)
mid=size/2;
cout << a[mid][mid];

Wednesday, December 23, 2009

for programming interviews part-2

3.wap for sorting ones and 0 in most efficient way while preserving the order.

ans:the solution as many would have guessed has to be in O(n).and the usual 2 pointer approach is correct.but ek problem the order is not preserved hence we have to think of a different approach.we can use 2 ptr approach.a slight change.in the regular approach there is one ptr in front and 2nd ptr at the end of array.
but in my approach we can have 2 ptrs such that both are at front.

#include
using namespace std;
int main()
{
int arry[5]={1,1,1,0,1};
int i=0,j=0,k=0;
for(;k<5;++k)
{
if((i==j)&&(arry[i]!=0))
{
++i;
++j;
}

else if(i==j){
j++;
}
else if(arry[j]==0){
j++;
}
else if((arry[i] == 0) && (arry[j]!=0))
{
int tmp;
tmp = arry[j];
arry[j]=arry[i];
arry[i]=tmp;
i++;
j++;
}

}
for(i=4;i>=0;--i)
cout<cin.sync();
cin.get();
return 0;
}
u can use this approach to sort(separate) the given set of non 0 number and 0 .by putting 0 at end and prserving order.

4.shuffle a deck of cards.


int array[52];
for(i=0;i<52;++i)
{
int rand=rand()%52;
swap(a[i],a[rand]);
}



Tuesday, December 22, 2009

for programming interviews-part 1

hi from now on me writing blogs to answer various programming questions
to start with a simple one
1.Wap to find the largest sum subsequence in array of both +ve and -ve elements
for (int i = 0; i < array.Length; i++)
{
largest = largest > array[i] ? largest : array[i];

curMax = curMax + array[i];
if (curMax > maxSoFar)
{
maxSoFar = curMax;
maxEnd = i;
maxStart = curMaxStart;
allNegatives = false;
}
else if (curMax <= 0)
{
curMax = 0;
curMaxStart = i + 1;
}
}

if (allNegatives)
{
return largest;
}
return maxSoFar;
}
we need to find the sum and also the start and end points.

2.write a program to find out a solution for 8 queen problem?
(this was asked to me in my MS interview)
basically the solution for 8 queen problem consists on the following part.
1.we need to check if i-th and j-th column are empty or not
2.we need to check if the queen is placed in major diagonal t[i]-t[j]==(i-j)
3.or is it in minor diagonal t[j]-t[i]==(i-j)
t[i] is the presence of queen in row i and column t[i] meaning if t[4]=8 means that in 8th row the queen is present in 4 th column
heres the code.

void queen(int i)
{
for(t[i]=1;t[i]<=8;t[i]++)
{
if(i)
{
if(i==8)
print_solution();
else
queen(i+1);
}
}
int empty(int i)
{
int j;
j=1;

while(t[i]!=t[j] && abs(t[i]-t[j])!=(i-j) &&j<8)j++;

return((i==j)?1:0);
}

And here is one of the possible solutions



t[1] = [1] // This means the first square of the first row.
t[2] = [5] // This means the fifth square of the second row.
t[3] = [8] ..
t[4] = [6] ..
t[5] = [3] ..
t[6] = [7] ..
t[7] = [2] ..
t[8] = [4] // This means the fourth square of the last row.