[algogeeks] Re: Adobe Question
n*ceil(log_2n) On Sep 24, 9:23 am, Krunal Modi krunalam...@gmail.com wrote: But, how was it derived ? :( What is the intuition behind ? :( :( -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Adobe Question
@Dave sorry i didnt see k n (thought it was k=n) The intuition i guess would be at every powers of 2 it increases by 1 i.e 1=0 2=1 3=1+1=2 4=2+2=4 see the increase of 2 here 5=4+2=6 6=6+2=8 7=8+2=10 8=10+3=13 ..see the increase of 3 here i guess we can work on from here On Fri, Sep 24, 2010 at 9:53 AM, Krunal Modi krunalam...@gmail.com wrote: But, how was it derived ? :( What is the intuition behind ? :( :( -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: do this: two numbers with min diff
check for this input {7,8,5,1,3,4}
On Sep 23, 10:36 pm, Rishi Agrawal rishi.b.agra...@gmail.com wrote:
@Dave, I check for the values you suggested but the code worked fine. There
were other errors in the code. I have rectified them now.
The following code seems to be working fine and in O(n) time.
#include stdio.h
#include stdlib.h
void find_two_mins(int array[], int size)
{
int i,t;
int min1, min2;
if(array[0] = array[1]) {
min1=array[0];
min2=array[1];
} else {
min2=array[0];
min1=array[1];
}
for (i=2; isize; i++){
t=array[i];
if(t=min1) {
min2=min1;
min1=t;
continue;
}
if(t=min2) {
min2=t;
}
}
printf(\nMin elements are 1: %d 2: %d, min1,min2);
printf(\n Absolute difference between two minimum elements are %d\n\n,
abs(min1-min2));
}
int main()
{
//int array[10]={ 9,2,3,4,1,7,5,6,8,0};
//
//int array[10]={3,3,1,33,88,9098,112,33455,678,1};
//int array[10]={5,3,1,33,88,9098,112,33455,678,1};
//int array[10]={2,3,21,33,88,9098,112,33455,678,12};
int array[10]={3,2,21,33,88,9098,112,33455,678,12};
find_two_mins(array,10);
return 0;
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Adobe Question
what's the datatype of j? mathematically speaking, the while loop is
infinite for every j0...
On Sep 23, 6:19 am, Krunal Modi krunalam...@gmail.com wrote:
for(k=1 ; kn ; k++){
j=k;
while(j0){
j=j/2;
}
}
How many times while loop gets executed (for any n) ?
I don't want answer in terms of series (i.e, don't want any sigma, I
have that)
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] help required...
@coolfrog
in case of AB we asked to A know B after checking this we eliminate A n same
case go for CD den
A B CD
| |
AD
AD Same approach
|
D (D will be celebrity)
On Fri, Sep 24, 2010 at 10:57 AM, kartheek muthyala
kartheek0...@gmail.comwrote:
@coolfrog,
What I meant by remained is
Considering your case of A,B,C,D and B is the celebrity,
The sequence is
First A,B ask the question to A, then remained=B
Then B,C ask the question to B, then remained=B
Then B,D ask the question to B, then remained= B
Then ask A,C,D whether they know B
Then ask B whether they know A,C,D
So, that's how I said 3(n-1) questions...
Correct me if I am wrong
On Thu, Sep 23, 2010 at 8:32 PM, coolfrog$
dixit.coolfrog.div...@gmail.com wrote:
@kartheek
i am getting. this prudent approach
but what is add what remained to the remainder.
suppose u have A,B,C,D and B is celebrity ...
if( A knows B)
{ A is not celb.
if( B knows C){}
else{ C is not celb.
if (C knows B )
{ if( D knows B)
{ D is not celb.
only B remain... hence it celeb...
/* suppose if u have A,B,C,D,E
and B is celeb.
then again if (E knows B)
{E is not
celb
only B
remain... hence it celeb...
}
*/
}
}
}
}
look in every if condition we are Asking Sequentially to A
,B,C,D,E...
can these be correct solution
correct me plz... if wrong..
On Thu, Sep 23, 2010 at 12:56 AM, kartheek muthyala
kartheek0...@gmail.com wrote:
Take 2 persons, suppose say A and B
ask one of them the question about other
if A Knows B, then A cannot be the celebrity,
if A does not know B, then B cannot be the celebrity.
add what remained to the remainder.
repeat this process for the remaining n-1 until one or none remained.
Then if it is none then there is no celebrity.
If there is one ask the question whether this person is known by
remaining n-1 and this person does n't know the remaining n-1. So a total of
3(n-1) questions is used to determine the celeb.
Time complexity is O(n).
Repeat this for the remaining n-1 persons, if the remainder contain one
then
On Wed, Sep 22, 2010 at 9:37 PM, Divesh Dixit
dixit.coolfrog.div...@gmail.com wrote:
Among n people, a celebrity is defined as someone who is known to
everyone, but who knows no
one. Design and analyze to identify the celebrity, if one exists, by
asking only questions of the
following form: Excuse me, do you know person x? You will get a
binary answer for each such
question asked. Find the celebrity by asking only O(n) questions.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Thanks Regards
Umesh kewat
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For
[algogeeks] Microsoft interview question
Asked in microsoft interview Given a snapshot of an ongoing chess game, which probably is a one vs many game, identify whether it is a valid game or not. It would be great if someone would clarify on what conditions does validity of the game depend.. --Vrinda -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Amazon Interview
do the encoding like = 80 if der is other number then like 8(0)..and write the new file and when want to generate original do decoding in reverse On Thu, Sep 23, 2010 at 11:15 PM, janak chandar...@gmail.com wrote: http://en.wikipedia.org/wiki/Run-length_encoding On Wed, Sep 15, 2010 at 5:51 PM, bittu shashank7andr...@gmail.com wrote: A file is given with many 0s stored in continuous way , store it in another file such that when you store try saving the space by using minimum amount of space. When you want to create the original file , you should be able to do so with the new file created -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Umesh kewat -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] nth number of the series
There is a sequence of increasing numbers that have the same number of binary 1s in them. Given n, the number of 1 bits set in each number, write an algorithm or C program to find the n’th number in the series -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: ReVerse a string using recursion
use it like this
char* strrev(char *)
strrev(str)
void strrev(char *str)
{
xstrrev(str , 0, strlen(str)); // code posted by Nishant
}
:-)
On Sep 23, 11:35 pm, albert theboss alberttheb...@gmail.com wrote:
Ur function prototype is not similar to one i posted before
check it out
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: do this: two numbers with min diff
I got the problem statement wrong. For a input of 7,8,5,1,3,4 the answer should be 1 due to the difference between 3 and 4 or 7 and 8 or 4 and 5. Rather than 2 due to difference between 1 and 3 Sorry every one :-( -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: ReVerse a string using recursion
char * strRev(char* string)
{
static int ptr;
if(ptr == lengthOf(string)/2 || ptr == lengthOf(string/2)+1)
{
return string;
}
ptr++;
strRev(swap(string, ptr-1, lengthOf(string)-ptr-2));
}
where swap returns a string with the chars at the two positions
swapped.
I haven't tried out the code, but something along those lines should
work. I've used a static var coz of the Qs strict method signature
requirement.
where swap is a function that swaps the two chars
On Sep 23, 10:59 am, Albert alberttheb...@gmail.com wrote:
How to reverse a String using recursion in C without using any extra
memory?
the question seems to be simple.
char* strrev(char *)
{
...
...
...
}
Try to give all the answers for this prototype.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Fwd: another help please
Dear Rahul, Can you try writing hex digits in binary and try. 0x77 -- 0111 0111 0x03 -- 0011 --- AND 0011 -- 0x03 Cheers ! Mohit On Thu, Sep 23, 2010 at 10:25 PM, rahul rai raikra...@gmail.com wrote: Rahul K Rai rahulpossi...@gmail.com -- Forwarded message -- From: rahul rai raikra...@gmail.com Date: 2010/9/23 Subject: another help please To: Baljeet Kumar baljeetk...@gmail.com Rahul K Rai please explain me this please rahulpossi...@gmail.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: do this: two numbers with min diff
Printing the Array:
99 35 45 33 88 9098 112 33455 678 3
Min elements are 1: 3 2: 33
Absolute difference between two minimum elements are 30
On Fri, Sep 24, 2010 at 9:39 AM, Dave dave_and_da...@juno.com wrote:
@Rishi: Try it on the original data with a[1] changed from 12 to 35:
int array[10]={99,35,45,33,88,9098,112,33455,678,3};
What do you get as a result?
Dave
On Sep 23, 12:36 pm, Rishi Agrawal rishi.b.agra...@gmail.com wrote:
@Dave, I check for the values you suggested but the code worked fine.
There
were other errors in the code. I have rectified them now.
The following code seems to be working fine and in O(n) time.
#include stdio.h
#include stdlib.h
void find_two_mins(int array[], int size)
{
int i,t;
int min1, min2;
if(array[0] = array[1]) {
min1=array[0];
min2=array[1];
} else {
min2=array[0];
min1=array[1];
}
for (i=2; isize; i++){
t=array[i];
if(t=min1) {
min2=min1;
min1=t;
continue;
}
if(t=min2) {
min2=t;
}
}
printf(\nMin elements are 1: %d 2: %d, min1,min2);
printf(\n Absolute difference between two minimum elements are
%d\n\n,
abs(min1-min2));
}
int main()
{
//int array[10]={ 9,2,3,4,1,7,5,6,8,0};
//
//int array[10]={3,3,1,33,88,9098,112,33455,678,1};
//int array[10]={5,3,1,33,88,9098,112,33455,678,1};
//int array[10]={2,3,21,33,88,9098,112,33455,678,12};
int array[10]={3,2,21,33,88,9098,112,33455,678,12};
find_two_mins(array,10);
return 0;
}- Hide quoted text -
- Show quoted text -
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards,
Rishi Agrawal
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: do this: two numbers with min diff
You are solving the wrong problem. The problem is not asking for the
difference between the two minimum elements, but for the minimum
difference between any pair of elements. In the case
int array[10]={99,35,45,33,88,9098,112,33455,678,3};
the minimum difference is |35-33| = 2.
Dave
On Sep 24, 5:02 am, Rishi Agrawal rishi.b.agra...@gmail.com wrote:
Printing the Array:
99 35 45 33 88 9098 112 33455 678 3
Min elements are 1: 3 2: 33
Absolute difference between two minimum elements are 30
On Fri, Sep 24, 2010 at 9:39 AM, Dave dave_and_da...@juno.com wrote:
@Rishi: Try it on the original data with a[1] changed from 12 to 35:
int array[10]={99,35,45,33,88,9098,112,33455,678,3};
What do you get as a result?
Dave
On Sep 23, 12:36 pm, Rishi Agrawal rishi.b.agra...@gmail.com wrote:
@Dave, I check for the values you suggested but the code worked fine.
There
were other errors in the code. I have rectified them now.
The following code seems to be working fine and in O(n) time.
#include stdio.h
#include stdlib.h
void find_two_mins(int array[], int size)
{
int i,t;
int min1, min2;
if(array[0] = array[1]) {
min1=array[0];
min2=array[1];
} else {
min2=array[0];
min1=array[1];
}
for (i=2; isize; i++){
t=array[i];
if(t=min1) {
min2=min1;
min1=t;
continue;
}
if(t=min2) {
min2=t;
}
}
printf(\nMin elements are 1: %d 2: %d, min1,min2);
printf(\n Absolute difference between two minimum elements are
%d\n\n,
abs(min1-min2));
}
int main()
{
//int array[10]={ 9,2,3,4,1,7,5,6,8,0};
//
//int array[10]={3,3,1,33,88,9098,112,33455,678,1};
//int array[10]={5,3,1,33,88,9098,112,33455,678,1};
//int array[10]={2,3,21,33,88,9098,112,33455,678,12};
int array[10]={3,2,21,33,88,9098,112,33455,678,12};
find_two_mins(array,10);
return 0;
}- Hide quoted text -
- Show quoted text -
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards,
Rishi Agrawal- Hide quoted text -
- Show quoted text -
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: ReVerse a string using recursion
@nishanth : could u give me any solutions without global variable or static variable -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: ReVerse a string using recursion
@albert i think you know the solution and u r just testing others.so post the solution and stop this discussion.. On Sat, Sep 25, 2010 at 12:48 AM, albert theboss alberttheb...@gmail.comwrote: @nishanth : could u give me any solutions without global variable or static variable -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- :-) * Nishant Agarwal Computer Science and Engineering NIT Allahabad * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: ReVerse a string using recursion
sorry i dont know the solution. i just expecting such answer -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: ReVerse a string using recursion
i dont think that without giving 1st and last index, this is possible.i m using i and j as 1st and last index respectively On Sat, Sep 25, 2010 at 1:00 AM, albert theboss alberttheb...@gmail.comwrote: sorry i dont know the solution. i just expecting such answer -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- :-) * Nishant Agarwal Computer Science and Engineering NIT Allahabad * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: nth number of the series
The numbers listed in ascending order will always follow a pattern. 111 ... 1 (n digits, all 1's with no 0's between) 1011 ... 1 (n+1 digits, all 1's except a 0 in second from high order bit). 1101 ... 1 (n+1 digits, all 1's except a 0 in third from high order bit) The n'th element of this series will always be 111 .. 01 (n+1 digits, all 1's except a 0 in the second from lowest order bit). For example if n=4, we have 0 10111 11011 11101 So the number you want is 11101. The value of this in general is 2^(n+1) - 3. For our example n=4, this is 2^5-3 = 29 = 11101_2. It's pretty easy to give an algorithm that computes 2^(n+1) - 3. I'll let you do that. On Sep 24, 8:37 am, amit amitjaspal...@gmail.com wrote: There is a sequence of increasing numbers that have the same number of binary 1s in them. Given n, the number of 1 bits set in each number, write an algorithm or C program to find the n’th number in the series -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Microsoft interview question
Valid must mean that you can get from an initial board to the the current game state by a series of legal moves. This is a classic branch and bound game tree search problem. You could search either from a starting configuration and try to find the current game state. Or start from the current state, use 'backward' moves, and try to find the initial configuration. In this case, you'd have to include backward moves that 'untake' pieces that are missing from the current state. Or you could do a simultaneous search from both ends, looking for common states in the middle. You'd generally use a heuristic search. Problems like this often work well with A-Star. The heuristic evaluator would favor states closer to the desired end (either start or current). Gene On Sep 24, 6:26 am, vrinda vasishth vrindavasis...@gmail.com wrote: Asked in microsoft interview Given a snapshot of an ongoing chess game, which probably is a one vs many game, identify whether it is a valid game or not. It would be great if someone would clarify on what conditions does validity of the game depend.. --Vrinda -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Microsoft interview question
1.The soldiers are initially placed at row 2 or row 7th(each-one of white and either of black).Also let white ones be at row 2.So they can never be at row 1st.Incase it is so in the game,its not a valid game. 2.There are Bishops.Each color has one of its Bishop which moves diagonally on all white squares,and the other on all black squares.Incase it is not so,the game cannot be valid. 3.Now suppose,no black soldier ever moved.That is,all the black soldiers are at row 7th.This means that the elephant(i am sorry,I generally mess up with their names..:P) of any other player(except horse) cannot be in any row but 8th one. I know only 3 test cases.Incase any one has more,please elaborate. PS:Vrinda,I also got the same question..:P On Sat, Sep 25, 2010 at 2:49 AM, Gene gene.ress...@gmail.com wrote: Valid must mean that you can get from an initial board to the the current game state by a series of legal moves. This is a classic branch and bound game tree search problem. You could search either from a starting configuration and try to find the current game state. Or start from the current state, use 'backward' moves, and try to find the initial configuration. In this case, you'd have to include backward moves that 'untake' pieces that are missing from the current state. Or you could do a simultaneous search from both ends, looking for common states in the middle. You'd generally use a heuristic search. Problems like this often work well with A-Star. The heuristic evaluator would favor states closer to the desired end (either start or current). Gene On Sep 24, 6:26 am, vrinda vasishth vrindavasis...@gmail.com wrote: Asked in microsoft interview Given a snapshot of an ongoing chess game, which probably is a one vs many game, identify whether it is a valid game or not. It would be great if someone would clarify on what conditions does validity of the game depend.. --Vrinda -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
