Re: [algogeeks] Re: Microsoft interview question
@Mohit: I dont think it really matters here.We just have to validate the snapshot of the game board.Number of players should not have any relevance here. On Sat, Sep 25, 2010 at 2:46 PM, mohit ranjan shoonya.mo...@gmail.comwrote: @Ashita, Your logic is fine for one vs one game, but as per question it's one vs many game Any idea what is that ? Mohit On Sat, Sep 25, 2010 at 1:18 PM, ashita dadlani ash@gmail.com wrote: 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.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.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.
Re: [algogeeks] Yahoo Question:Greatest Sub-sequential sum
@ashish:
what if the array is {-2,3,4,17,-8,9}?
On Wed, Sep 8, 2010 at 8:52 AM, Anand anandut2...@gmail.com wrote:
Maximum Value Contiguous Subsequence problem in O(n).
http://codepad.org/BhYxSlp4
On Tue, Sep 7, 2010 at 2:40 PM, ashish agarwal
ashish.cooldude...@gmail.com wrote:
yeah..it will be i=j+1;
it was misprinted
On Tue, Sep 7, 2010 at 10:57 AM, Sahana Gururaj sahan...@gmail.comwrote:
In the else if condition, the increment of the end index i should be
i=j+1, not i=j+i; Otherwise the algo is right, follows the principles of
Kadane's algo :
http://en.wikipedia.org/wiki/Maximum_subarray_problem#Kadane.27s_algorithm
On Mon, Sep 6, 2010 at 3:50 PM, ashish agarwal
ashish.cooldude...@gmail.com wrote:
int max=0,sum=0,begin=0,end=0,i=0;
for(int j=0 to n){
sum+=a[j];
if(maxsum){
max=sum;
begin=i;
end=j;
}
else if(sum0){
i=j+i;
sum=0;
}
return sum;
i will tell the starting index and j will tell ending index;
o(n);
correct me if i am wrong
On Mon, Sep 6, 2010 at 1:42 PM, bittu shashank7andr...@gmail.comwrote:
Given a sequence of integers, find a continuous subsequence which
maximizes the sum of its elements, that is, the elements of no other
single subsequence add up to a value larger than this one. An empty
subsequence is considered to have the sum 0; thus if all elements are
negative, the result must be the empty sequence.
Solution:O(n^2) i want O(nlogn)...???
#include stdio.h
#includeconio.h
#includeiostream.h
#includestdlib.h
int main()
{
int a[] = {-1 , -2 , 3 , 5 , 6 , -2 , -1 , 4 , -4 , 2 , -1};
int length = 11;
int begin, end, beginmax, endmax, maxsum, sum, i;
sum = 0;
beginmax = 0;
endmax = -1;
maxsum = 0;
for (begin=0; beginlength; begin++) {
sum = 0;
for(end=begin; endlength; end++) {
sum += a[end];
if(sum maxsum) {
maxsum = sum;
beginmax = begin;
endmax = end;
}
}
coutsum\t;
}
coutendl;
for(i=beginmax; i=endmax; i++) {
printf(%d\n, a[i]);
}
getch();
}
its has time complexity O(n^2) ..does better solution exist
--
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.
--
Sahana Gururaj
--
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.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Yahoo Question:Greatest Sub-sequential sum
@anand:
the maximum sum obtained from your solution is correct.
However,the subarray printed is not correct for the following case:
{-2,3,4,17,-8}
-8 is also getting printed which is not a part of thw subsequence.
On Sat, Sep 11, 2010 at 2:00 PM, ashita dadlani ash@gmail.com wrote:
@ashish:
what if the array is {-2,3,4,17,-8,9}?
On Wed, Sep 8, 2010 at 8:52 AM, Anand anandut2...@gmail.com wrote:
Maximum Value Contiguous Subsequence problem in O(n).
http://codepad.org/BhYxSlp4
On Tue, Sep 7, 2010 at 2:40 PM, ashish agarwal
ashish.cooldude...@gmail.com wrote:
yeah..it will be i=j+1;
it was misprinted
On Tue, Sep 7, 2010 at 10:57 AM, Sahana Gururaj sahan...@gmail.comwrote:
In the else if condition, the increment of the end index i should be
i=j+1, not i=j+i; Otherwise the algo is right, follows the principles of
Kadane's algo :
http://en.wikipedia.org/wiki/Maximum_subarray_problem#Kadane.27s_algorithm
On Mon, Sep 6, 2010 at 3:50 PM, ashish agarwal
ashish.cooldude...@gmail.com wrote:
int max=0,sum=0,begin=0,end=0,i=0;
for(int j=0 to n){
sum+=a[j];
if(maxsum){
max=sum;
begin=i;
end=j;
}
else if(sum0){
i=j+i;
sum=0;
}
return sum;
i will tell the starting index and j will tell ending index;
o(n);
correct me if i am wrong
On Mon, Sep 6, 2010 at 1:42 PM, bittu shashank7andr...@gmail.comwrote:
Given a sequence of integers, find a continuous subsequence which
maximizes the sum of its elements, that is, the elements of no other
single subsequence add up to a value larger than this one. An empty
subsequence is considered to have the sum 0; thus if all elements are
negative, the result must be the empty sequence.
Solution:O(n^2) i want O(nlogn)...???
#include stdio.h
#includeconio.h
#includeiostream.h
#includestdlib.h
int main()
{
int a[] = {-1 , -2 , 3 , 5 , 6 , -2 , -1 , 4 , -4 , 2 , -1};
int length = 11;
int begin, end, beginmax, endmax, maxsum, sum, i;
sum = 0;
beginmax = 0;
endmax = -1;
maxsum = 0;
for (begin=0; beginlength; begin++) {
sum = 0;
for(end=begin; endlength; end++) {
sum += a[end];
if(sum maxsum) {
maxsum = sum;
beginmax = begin;
endmax = end;
}
}
coutsum\t;
}
coutendl;
for(i=beginmax; i=endmax; i++) {
printf(%d\n, a[i]);
}
getch();
}
its has time complexity O(n^2) ..does better solution exist
--
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.
--
Sahana Gururaj
--
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.com.
For more options, visit this group at
http://groups.google.com
Re: [algogeeks] Yahoo Question:Greatest Sub-sequential sum
http://codepad.org/Jui20xme
http://codepad.org/Jui20xmea little modification over anand's code.
On Sat, Sep 11, 2010 at 2:33 PM, ashita dadlani ash@gmail.com wrote:
@anand:
the maximum sum obtained from your solution is correct.
However,the subarray printed is not correct for the following case:
{-2,3,4,17,-8}
-8 is also getting printed which is not a part of thw subsequence.
On Sat, Sep 11, 2010 at 2:00 PM, ashita dadlani ash@gmail.com wrote:
@ashish:
what if the array is {-2,3,4,17,-8,9}?
On Wed, Sep 8, 2010 at 8:52 AM, Anand anandut2...@gmail.com wrote:
Maximum Value Contiguous Subsequence problem in O(n).
http://codepad.org/BhYxSlp4
On Tue, Sep 7, 2010 at 2:40 PM, ashish agarwal
ashish.cooldude...@gmail.com wrote:
yeah..it will be i=j+1;
it was misprinted
On Tue, Sep 7, 2010 at 10:57 AM, Sahana Gururaj sahan...@gmail.comwrote:
In the else if condition, the increment of the end index i should be
i=j+1, not i=j+i; Otherwise the algo is right, follows the principles of
Kadane's algo :
http://en.wikipedia.org/wiki/Maximum_subarray_problem#Kadane.27s_algorithm
On Mon, Sep 6, 2010 at 3:50 PM, ashish agarwal
ashish.cooldude...@gmail.com wrote:
int max=0,sum=0,begin=0,end=0,i=0;
for(int j=0 to n){
sum+=a[j];
if(maxsum){
max=sum;
begin=i;
end=j;
}
else if(sum0){
i=j+i;
sum=0;
}
return sum;
i will tell the starting index and j will tell ending index;
o(n);
correct me if i am wrong
On Mon, Sep 6, 2010 at 1:42 PM, bittu shashank7andr...@gmail.comwrote:
Given a sequence of integers, find a continuous subsequence which
maximizes the sum of its elements, that is, the elements of no other
single subsequence add up to a value larger than this one. An empty
subsequence is considered to have the sum 0; thus if all elements are
negative, the result must be the empty sequence.
Solution:O(n^2) i want O(nlogn)...???
#include stdio.h
#includeconio.h
#includeiostream.h
#includestdlib.h
int main()
{
int a[] = {-1 , -2 , 3 , 5 , 6 , -2 , -1 , 4 , -4 , 2 , -1};
int length = 11;
int begin, end, beginmax, endmax, maxsum, sum, i;
sum = 0;
beginmax = 0;
endmax = -1;
maxsum = 0;
for (begin=0; beginlength; begin++) {
sum = 0;
for(end=begin; endlength; end++) {
sum += a[end];
if(sum maxsum) {
maxsum = sum;
beginmax = begin;
endmax = end;
}
}
coutsum\t;
}
coutendl;
for(i=beginmax; i=endmax; i++) {
printf(%d\n, a[i]);
}
getch();
}
its has time complexity O(n^2) ..does better solution exist
--
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.
--
Sahana Gururaj
--
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
Re: [algogeeks] Re: Write a C program to sort a stack in ascending order.
else{
ascending(s, i);
push(top);
}
}
@swinivas:why have you used ascending(s,i) here?
On Sat, Sep 11, 2010 at 6:40 PM, Srinivas lavudyasrinivas0...@gmail.comwrote:
reverse(stack *s){
IsEmpty(s)
return;
top = pop(s);
reverse(s);
ascending(s, top);
}
ascending(stack *s, int top){
IsEmpty(s){
push(top);
return;
}
i = pop(s);
if(i top){
ascending(s, top);
push(i);
}
else{
ascending(s, i);
push(top);
}
}
Please let me know if it wont work..thanks
On Jul 18, 6:58 am, xyombie brianbl...@gmail.com wrote:
What about a quick sort O(log n)
void sort_stack(Stack *src, Stack *dst)
{
if(! src-IsEmpty() )
{
Stack smaller, larger;
int pivot = src-Pop();
while(! src-IsEmpty() )
{
int tmp = src-Pop();
if(tmp pivot)
smaller-Push(tmp);
else
larger-Push(tmp);
}
sort_stack(smaller, dst);
dst-Push(pivot);
sort_stack(larger, dst);
}
}
On Jul 17, 9:28 am, vijay auvija...@gmail.com wrote:
Write a C program to sort a stack in ascending order. You should not
make any assumptions about how the stack is implemented. The following
are the only
functions that should be used to write this program:
Push | Pop | Top | IsEmpty | IsFull
The algorithm is O(N^2) and appears below.
Do we have any other better solution which is less than O(n * n) ?
void sort_stack(Stack * src, Stack * dest)
{
while (!src-IsEmpty())
{
Int tmp = src-Pop();
while(!dest-IsEmpty() dest-Top() tmp)
{
src-Push(dest-Pop());
}
dest-Push(tmp);
}
}
--
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: Write a C program to sort a stack in ascending order.
@Srinivas:
shouldn't it be:
i = pop(s);
if(i top){
ascending(s, i);
push(top);
}
else{
ascending(s, top);
push(i);
}
On Sat, Sep 11, 2010 at 6:52 PM, ashita dadlani ash@gmail.com wrote:
else{
ascending(s, i);
push(top);
}
}
@swinivas:why have you used ascending(s,i) here?
On Sat, Sep 11, 2010 at 6:40 PM, Srinivas
lavudyasrinivas0...@gmail.comwrote:
reverse(stack *s){
IsEmpty(s)
return;
top = pop(s);
reverse(s);
ascending(s, top);
}
ascending(stack *s, int top){
IsEmpty(s){
push(top);
return;
}
i = pop(s);
if(i top){
ascending(s, top);
push(i);
}
else{
ascending(s, i);
push(top);
}
}
Please let me know if it wont work..thanks
On Jul 18, 6:58 am, xyombie brianbl...@gmail.com wrote:
What about a quick sort O(log n)
void sort_stack(Stack *src, Stack *dst)
{
if(! src-IsEmpty() )
{
Stack smaller, larger;
int pivot = src-Pop();
while(! src-IsEmpty() )
{
int tmp = src-Pop();
if(tmp pivot)
smaller-Push(tmp);
else
larger-Push(tmp);
}
sort_stack(smaller, dst);
dst-Push(pivot);
sort_stack(larger, dst);
}
}
On Jul 17, 9:28 am, vijay auvija...@gmail.com wrote:
Write a C program to sort a stack in ascending order. You should not
make any assumptions about how the stack is implemented. The following
are the only
functions that should be used to write this program:
Push | Pop | Top | IsEmpty | IsFull
The algorithm is O(N^2) and appears below.
Do we have any other better solution which is less than O(n * n) ?
void sort_stack(Stack * src, Stack * dest)
{
while (!src-IsEmpty())
{
Int tmp = src-Pop();
while(!dest-IsEmpty() dest-Top() tmp)
{
src-Push(dest-Pop());
}
dest-Push(tmp);
}
}
--
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: Write a C program to sort a stack in ascending order.
@Srinivas:
Sorry for the confusion.
But if we have a stack {5,8,3,4,2} with 5 as the last input,ie,top,
do we have to arrange the stack such that s={2,3,4,5,8}with 2 as the top?
if I am getting it correct,then shouldn't your algo be modified slightly as
follows:?
reverse(stack *s){
IsEmpty(s)
return;
top = pop(s);
reverse(s);
ascending(s, top);
}
ascending(stack *s, int top){
IsEmpty(s){
push(top);
return;
}
i = pop(s);
if(i top){
push(top);
}
else{
ascending(s, top);
push(i);
}
}
On Sat, Sep 11, 2010 at 7:04 PM, ashita dadlani ash@gmail.com wrote:
@Srinivas:
shouldn't it be:
i = pop(s);
if(i top){
ascending(s, i);
push(top);
}
else{
ascending(s, top);
push(i);
}
On Sat, Sep 11, 2010 at 6:52 PM, ashita dadlani ash@gmail.com wrote:
else{
ascending(s, i);
push(top);
}
}
@swinivas:why have you used ascending(s,i) here?
On Sat, Sep 11, 2010 at 6:40 PM, Srinivas
lavudyasrinivas0...@gmail.comwrote:
reverse(stack *s){
IsEmpty(s)
return;
top = pop(s);
reverse(s);
ascending(s, top);
}
ascending(stack *s, int top){
IsEmpty(s){
push(top);
return;
}
i = pop(s);
if(i top){
ascending(s, top);
push(i);
}
else{
ascending(s, i);
push(top);
}
}
Please let me know if it wont work..thanks
On Jul 18, 6:58 am, xyombie brianbl...@gmail.com wrote:
What about a quick sort O(log n)
void sort_stack(Stack *src, Stack *dst)
{
if(! src-IsEmpty() )
{
Stack smaller, larger;
int pivot = src-Pop();
while(! src-IsEmpty() )
{
int tmp = src-Pop();
if(tmp pivot)
smaller-Push(tmp);
else
larger-Push(tmp);
}
sort_stack(smaller, dst);
dst-Push(pivot);
sort_stack(larger, dst);
}
}
On Jul 17, 9:28 am, vijay auvija...@gmail.com wrote:
Write a C program to sort a stack in ascending order. You should not
make any assumptions about how the stack is implemented. The
following
are the only
functions that should be used to write this program:
Push | Pop | Top | IsEmpty | IsFull
The algorithm is O(N^2) and appears below.
Do we have any other better solution which is less than O(n * n) ?
void sort_stack(Stack * src, Stack * dest)
{
while (!src-IsEmpty())
{
Int tmp = src-Pop();
while(!dest-IsEmpty() dest-Top() tmp)
{
src-Push(dest-Pop());
}
dest-Push(tmp);
}
}
--
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: Array Problem
a={1,2,2,3,4}
b={1,2,3,3,4}
in this case???
elements are not equal but they certainly consist equal set of
integers(1,2,3,4) which is what question says.
On Sun, Aug 22, 2010 at 7:53 AM, UMarius mar...@aseara.ro wrote:
@Nikhil : I considered the array to be a linked list. xoring the
indexes helps when you don't know how many elements you have.
Marius.
On Aug 22, 5:04 am, Nikhil Agarwal nikhil.bhoja...@gmail.com wrote:
@marius Why are you xorring the indexes along with nos.?any special
reason?
On Sun, Aug 22, 2010 at 7:19 AM, UMarius mar...@aseara.ro wrote:
@Dave: I read the question correctly and for A = { 1 , 2} B = { 2 , 1}
the output is correct.
Maybe I didn't explain the steps correctly. This is the code:
for(int i = 0 ; i arr1.Length ; i++)
{
arr1XOR ^= arr1[i];
arr1XOR ^= i;
arr1SUM += arr1[i];
arr1MUL *= arr1[i];
}
for (int i = 0; i arr2.Length; i++)
{
arr2XOR ^= arr2[i];
arr2XOR ^= i;
arr2SUM += arr2[i];
arr2MUL *= arr2[i];
}
if(arr1XOR == arr2XOR arr1SUM == arr2SUM arr1MUL ==
arr2MUL)
{
//SAME VALUES - IDENTICAL ARRAYS
}
else
{
//NOT IDENTICAL
}
Please correct me if I'm wrong.
Marius.
On Aug 22, 3:45 am, Dave dave_and_da...@juno.com wrote:
@UMarius: A = {1,2}, B = {2,1} fails your test. If you reread the
original problem, you see that the question is not whether the arrays
are identical (which is easily determined by simply comparing them
element-by-element in O(n)), but whether they contain the same
values,
possibly in a different order.
Dave
On Aug 21, 11:01 am, UMarius mar...@aseara.ro wrote:
What about this?
1. xor all elements of each array and their corresponding indexes
sum all the elements of each array mul all elements of each array
2. if all results are the same then the arrays are identical
Nice to meet you all, I just joined and this is my first post :)
...
Given two arrays of numbers, find if each of the two arrays have
the
same set of integers ? Suggest an algo which can run faster than
NlogN
without extra space?- 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
algogeeks%2bunsubscr...@googlegroups .com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Thanks Regards
Nikhil Agarwal
Senior Undergraduate
Computer Science Engineering,
National Institute Of Technology,
Durgapur,Indiahttp://tech-nikk.blogspot.comhttp://
beta.freshersworld.com/communities/nitd
--
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.
[algogeeks]
You have a string say foobarfoo in which fo and oo aree repeated twice.You have to find all such repeated pairs in O(n) time,The string can only have alphanumeric elements in it. -- 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]
write the test cases for rectangle overlap. -- 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: Modified Binary Search
its possible.first apply binary search to find the index where the array is rotated. eg.a=[8,9,1,2,3,4,56,7] first apply binary search to find the value i=2. now we have 2 sub sorted arrays,ie, from i=0 to i=1 and from i=2 to i=8. apply binary search to these sub sorted arrays each of which will take time logn. hence total time:O(3logn)=O(logn) On Sun, Aug 8, 2010 at 12:04 PM, Manjunath Manohar manjunath.n...@gmail.com wrote: hey wait a sec,.. we wont be given the k value.. -- 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: Modified Binary Search
first of all Gene..this is not he but she :P and secondly,can you please mention the details you are talking about so that we can reach to a solution? On Sun, Aug 8, 2010 at 7:48 PM, Gene gene.ress...@gmail.com wrote: Well, then, you must say that in the problem! To to find k, ashita dadlani's solution works fine, except he has left out important details. This binary search is a bit tricker that the one to find a value. On Aug 8, 2:34 am, Manjunath Manohar manjunath.n...@gmail.com wrote: hey wait a sec,.. we wont be given the k value.. -- 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] Adobe Ques
@ashish:yours is not a generalized solution.Here you are assuming that u know r=3. What if we need to generalize the solution? On Wed, Jul 14, 2010 at 11:58 PM, Ashish Goel ashg...@gmail.com wrote: for (int i=0;in-r+1;i++) printf(%c%c%c , a[i],a[i+1],a[i+2]); Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Wed, Jul 14, 2010 at 6:23 PM, ankit mahendru ankit.mahend...@gmail.com wrote: Write the code to print combinations of a given array (n r were given) e.g for abcde .r=3 ...print abc, bcd' cde etc -- 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
