Monday, October 13, 2008
Tuesday, September 23, 2008
8 queens problem.
8 queens problem
Code :
#include
#include
#define QUEENNO 8
void placeQueen(int,int *);
int canBePlaced(int,int,int *);
void showBoard(int *);
main(){
int x[QUEENNO],i;
printf("The 8 Queens problems
");
placeQueen(0,x); /* start placing with the first Queen */
printf("end");
}
void placeQueen(int k,int *x){
int i,j;
char ch;
for(i=0;i<8;i++){
if(canBePlaced(k,i,x)){ /* can we place the k th Queen at the i th
column ? */
x[k]=i; /* place the k th Queen at i th column */
if(k==7){
showBoard(x); /* one result is found, show the board */
printf("Want to see more? [n->stop, any->continue] : ");
scanf("%c",&ch);
if(ch=='n' || ch=='N') exit(0);
}
if(k<7) placeQueen(k+1,x); /* still more Queens left, go for them
*/}
}
}
int canBePlaced(int k,int i,int *x){
int j;
for(j=0;j
return 0;
}
return 1;
}
void showBoard(int *x){
int i,j;
printf("-------------------------------------------------------");
printf(" ");
for(i=0;i<8;i++) printf("%d ",(i+1));
printf("");
for(i=0;i<8;i++){
printf("%d ",(i+1));
for(j=0;j<8;j++){
if(j==x[i])
printf("Q");
else printf("-");
printf(" ");
}
printf("");
}
printf("-------------------------------------------------");
}
Code :
#include
#include
#define QUEENNO 8
void placeQueen(int,int *);
int canBePlaced(int,int,int *);
void showBoard(int *);
main(){
int x[QUEENNO],i;
printf("The 8 Queens problems
");
placeQueen(0,x); /* start placing with the first Queen */
printf("end");
}
void placeQueen(int k,int *x){
int i,j;
char ch;
for(i=0;i<8;i++){
if(canBePlaced(k,i,x)){ /* can we place the k th Queen at the i th
column ? */
x[k]=i; /* place the k th Queen at i th column */
if(k==7){
showBoard(x); /* one result is found, show the board */
printf("Want to see more? [n->stop, any->continue] : ");
scanf("%c",&ch);
if(ch=='n' || ch=='N') exit(0);
}
if(k<7) placeQueen(k+1,x); /* still more Queens left, go for them
*/}
}
}
int canBePlaced(int k,int i,int *x){
int j;
for(j=0;j
return 0;
}
return 1;
}
void showBoard(int *x){
int i,j;
printf("-------------------------------------------------------");
printf(" ");
for(i=0;i<8;i++) printf("%d ",(i+1));
printf("");
for(i=0;i<8;i++){
printf("%d ",(i+1));
for(j=0;j<8;j++){
if(j==x[i])
printf("Q");
else printf("-");
printf(" ");
}
printf("");
}
printf("-------------------------------------------------");
}
microsoft questions.
MICROSOFT PROBLEMS
1: You are given 3 integer arrays A, B and C of length n1, n2 and n3 respectively. All arrays are sorted. We define triplet of these 3 arrays as (x, y, z) where x is any integer from A, y from B and z from C. We define distance of triplet as maximum difference among triplet elements, i.e. Maximum of x – y, y – z or z – x. Write a program to find minimum triplet distance. (means there are n1*n2*n3 number of possible triplets are possible...among all triplets which triplet has minimum distance...Give only distance, but not triplet elements). Your program must be as much efficient as possible.
2: It was string cruncher program. First remove all repeated consecutive substring with length 1, then delete substring of length 2 and so on...
Example: string is “abcabeccced”
After removing repeated substring of length 1: “abcababceccced” --> “abcababceced” (2 'c' are removed)
After removing repeated substring of length 2: “abcababceced” --> “abcabceced” (substring “ab” is removed)
and so on...
3: In unix there is a command called “tail”. Implement that command in C.
4: F(1) = 1.
F(2n) = F (n) and F(2n+1) = F(n) + F(n+1).
Develop recursive program.
5: You are given a linked list and a number n. You also have a function to delete all nodes from that list which are at position which multiple of n in the list.
Example: if number is 3 then delete 3rd, 6th, 9th ,...nodes form the list. Develop a program that tests whether given function works properly or not. (In short they are asking me to develop general program for all test cases. By running that program all tests can be performed.)
6: Difference between system call and API call
7: You have 2 sorted lists and a function that merge that 2 lists such that output is again sorted and duplicates are removed. That means output is union of those 2 lists in sorted form.
Example: First list is 2->3->5->6->8 and second list is 4->5->6->7 and output of function is 2->3->4->5->6->7->8.
General:
***1: Give a fast way to multiply a number by 7.
***2: Give a one-line C expression to test whether a number is a power of 2. [No loops allowed - it's a simple test.]
3: Give a very good method to count the number of ones in a "n" (e.g. 32) bit number.
ANS. Given below are simple solutions, find a solution that does it in log (n) steps.
Iterative
function iterativecount (unsigned int n)
begin
int count=0;
while (n)
begin
count += n & 0x1 ;
n >>= 1;
end
return count;
end
Sparse Count
function sparsecount (unsigned int n)
begin
int count=0;
while (n)
begin
count++;
n &= (n-1);
end
return count ;
end
***4: Write a small lexical analyzer - interviewer gave tokens. expressions like "a*b" etc.
***5: Write a routine that prints out a 2-D array in spiral order!
***6: What is a far pointer (in DOS)
***7: A real life problem - A square picture is cut into 16 squares and they are shuffled. Write a program to rearrange the 16 squares to get the original big square.
8: Write a program to find whether a given m/c is big-endian or little-endian!
9: What is a volatile variable?
10. What is the difference between "malloc" and "calloc"?
***11. Let f(k) = y where k is the y-th number in the increasing sequence of non-negative integers with the same number of ones in its binary representation as y, e.g. f(0) = 1, f(1) = 1, f(2) = 2, f(3) = 1, f(4) = 3, f(5) = 2, f(6) = 3 and so on. Given k >= 0, compute f(k).
***12. Given a rectangular (cuboidal for the puritans) cake with a rectangular piece removed (any size or orientation), how would you cut the remainder of the cake into two equal halves with one straight cut of a knife?
***13. Given a linked list in sorted order, now it is broken at a point and rearranged
eg:2-4-7-8-12-15......now it is broken after 7 and rearranged to 8-12-15-2-4-7
Suggest an algorithm to find a position to insert a number to its actual position
eg:if you have to insert 13,it must be inserted between 8 and 12.
Given a pointer to the starting node and it is a singly linked list
Ans. node n ; // node to be inserted
node *t = start;
while(t->value > n->value)
t =t ->next;
while(t->next->value < n->value)
{
t= t->next;
if((t->value > t->next->value ) && (t->value < n->value)) // in case we are entering a
{ // value greater than the
insert(n) after t;
flag =1 // greatest value
}
}
if(flag ==0)
{
if(t->next!=NULL )
insert(n) // insert n after t;
else
insert n at the start;
}
14. You're given an array containing both positive and negative integers and
required to find the subarray with the largest sum (O(N) a la KBL).
Write a routine in C for the above
15.Give a very good method To count the no of ones in a 32 bit no.
(caution: looping through testing each bit is not a solution.)
16. Assuming that locks are the only reason due to which deadlocks can occur in a system. What would be a foolproof method of avoiding deadlocks in the system.
17. How is the readers-writers problem solved? - using semaphores/ada .. etc.
18. Ways of optimizing symbol table storage in compilers.
19.There 3 ants at 3 corners of a triangle. they randomly start moving towards another corner.. what is the probability that they do not collide.
20.write an efficient algorithm and C code to shuffle a pack of cards. This is one of feedback process until we came up with one with no extra storage.
21.Given array of characters. How would you reverse it.
How would you reverse it without using indexing in array.
22.RPC Fundamentals.
23.Disk interleaving.
24.difference between Ethernet and an ATM.
25.how would you reverse the bits of a number with log N arithmetic operations. where N is the no of bits in integer.
26. Asked me to reverse the given n-bit unsigned integer?
I mean if 1011 is the i/p then o/p=1101
Time complexity should be as small as possible...try it out...
27. What is Lamport's algorithm for clock synchronization?
28. Write an efficient program to find the sum of a polynomial.
S = a_0 x^0 + a_1 x^1 + ...........+ a_n x^n.
1: You are given 3 integer arrays A, B and C of length n1, n2 and n3 respectively. All arrays are sorted. We define triplet of these 3 arrays as (x, y, z) where x is any integer from A, y from B and z from C. We define distance of triplet as maximum difference among triplet elements, i.e. Maximum of x – y, y – z or z – x. Write a program to find minimum triplet distance. (means there are n1*n2*n3 number of possible triplets are possible...among all triplets which triplet has minimum distance...Give only distance, but not triplet elements). Your program must be as much efficient as possible.
2: It was string cruncher program. First remove all repeated consecutive substring with length 1, then delete substring of length 2 and so on...
Example: string is “abcabeccced”
After removing repeated substring of length 1: “abcababceccced” --> “abcababceced” (2 'c' are removed)
After removing repeated substring of length 2: “abcababceced” --> “abcabceced” (substring “ab” is removed)
and so on...
3: In unix there is a command called “tail”. Implement that command in C.
4: F(1) = 1.
F(2n) = F (n) and F(2n+1) = F(n) + F(n+1).
Develop recursive program.
5: You are given a linked list and a number n. You also have a function to delete all nodes from that list which are at position which multiple of n in the list.
Example: if number is 3 then delete 3rd, 6th, 9th ,...nodes form the list. Develop a program that tests whether given function works properly or not. (In short they are asking me to develop general program for all test cases. By running that program all tests can be performed.)
6: Difference between system call and API call
7: You have 2 sorted lists and a function that merge that 2 lists such that output is again sorted and duplicates are removed. That means output is union of those 2 lists in sorted form.
Example: First list is 2->3->5->6->8 and second list is 4->5->6->7 and output of function is 2->3->4->5->6->7->8.
General:
***1: Give a fast way to multiply a number by 7.
***2: Give a one-line C expression to test whether a number is a power of 2. [No loops allowed - it's a simple test.]
3: Give a very good method to count the number of ones in a "n" (e.g. 32) bit number.
ANS. Given below are simple solutions, find a solution that does it in log (n) steps.
Iterative
function iterativecount (unsigned int n)
begin
int count=0;
while (n)
begin
count += n & 0x1 ;
n >>= 1;
end
return count;
end
Sparse Count
function sparsecount (unsigned int n)
begin
int count=0;
while (n)
begin
count++;
n &= (n-1);
end
return count ;
end
***4: Write a small lexical analyzer - interviewer gave tokens. expressions like "a*b" etc.
***5: Write a routine that prints out a 2-D array in spiral order!
***6: What is a far pointer (in DOS)
***7: A real life problem - A square picture is cut into 16 squares and they are shuffled. Write a program to rearrange the 16 squares to get the original big square.
8: Write a program to find whether a given m/c is big-endian or little-endian!
9: What is a volatile variable?
10. What is the difference between "malloc" and "calloc"?
***11. Let f(k) = y where k is the y-th number in the increasing sequence of non-negative integers with the same number of ones in its binary representation as y, e.g. f(0) = 1, f(1) = 1, f(2) = 2, f(3) = 1, f(4) = 3, f(5) = 2, f(6) = 3 and so on. Given k >= 0, compute f(k).
***12. Given a rectangular (cuboidal for the puritans) cake with a rectangular piece removed (any size or orientation), how would you cut the remainder of the cake into two equal halves with one straight cut of a knife?
***13. Given a linked list in sorted order, now it is broken at a point and rearranged
eg:2-4-7-8-12-15......now it is broken after 7 and rearranged to 8-12-15-2-4-7
Suggest an algorithm to find a position to insert a number to its actual position
eg:if you have to insert 13,it must be inserted between 8 and 12.
Given a pointer to the starting node and it is a singly linked list
Ans. node n ; // node to be inserted
node *t = start;
while(t->value > n->value)
t =t ->next;
while(t->next->value < n->value)
{
t= t->next;
if((t->value > t->next->value ) && (t->value < n->value)) // in case we are entering a
{ // value greater than the
insert(n) after t;
flag =1 // greatest value
}
}
if(flag ==0)
{
if(t->next!=NULL )
insert(n) // insert n after t;
else
insert n at the start;
}
14. You're given an array containing both positive and negative integers and
required to find the subarray with the largest sum (O(N) a la KBL).
Write a routine in C for the above
15.Give a very good method To count the no of ones in a 32 bit no.
(caution: looping through testing each bit is not a solution.)
16. Assuming that locks are the only reason due to which deadlocks can occur in a system. What would be a foolproof method of avoiding deadlocks in the system.
17. How is the readers-writers problem solved? - using semaphores/ada .. etc.
18. Ways of optimizing symbol table storage in compilers.
19.There 3 ants at 3 corners of a triangle. they randomly start moving towards another corner.. what is the probability that they do not collide.
20.write an efficient algorithm and C code to shuffle a pack of cards. This is one of feedback process until we came up with one with no extra storage.
21.Given array of characters. How would you reverse it.
How would you reverse it without using indexing in array.
22.RPC Fundamentals.
23.Disk interleaving.
24.difference between Ethernet and an ATM.
25.how would you reverse the bits of a number with log N arithmetic operations. where N is the no of bits in integer.
26. Asked me to reverse the given n-bit unsigned integer?
I mean if 1011 is the i/p then o/p=1101
Time complexity should be as small as possible...try it out...
27. What is Lamport's algorithm for clock synchronization?
28. Write an efficient program to find the sum of a polynomial.
S = a_0 x^0 + a_1 x^1 + ...........+ a_n x^n.
Subscribe to:
Comments (Atom)