[algogeeks] Re: Question asked in Amazon online test
Let's define a term RANDOMNESS of array as... summation of position of each 1's for eg RANDOMNESS for (0,0,1,0,1,0,1,1) will be 23 now calculate max possible RANDOMNESS for the given array (each 1 on max possible right position) here it will be 26 so ans will be-- MAX RANDOMNESS of given array - RANDOMNESS of given array On Saturday, June 23, 2012 11:34:55 AM UTC+5:30, zerocool142 wrote: Given an array containing sequence of bits (0 or 1), you have to sort this array in the ascending order i.e. all 0' in first part of array followed by all 1's. The constraints is that you can swap only the adjacent elements in the array. Find the minimum number of swaps required to sort the given input array. Example: Given the array (0,0,1,0,1,0,1,1) the minimum number of swaps is 3. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/rugRBg0Q0-kJ. To post to this group, send email to algogeeks@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: Question asked in Amazon Online Test
count=0; Start parsing from left to right If operator push in stack. In number add in queue and increment count by one, if count == 2 then pop from stack add in queue, decrements the count by one. On Friday, 29 June 2012 19:46:43 UTC+5:30, zerocool142 wrote: Given an integer expression in a prefix format (i.e. the operator precedes the number it is operating on) , print the expression in the post fix format . Example: If the integer expression is in the prefix format is *+56-78, the postfix format expression is 56+78-*. Both of these correspond to the expression (5+6)*(7-8). -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/N4YE_XpyWjAJ. To post to this group, send email to algogeeks@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: Question asked in Amazon Online Test
I think this algo is correct. On Sunday, 1 July 2012 13:06:17 UTC+5:30, Ashu wrote: count=0; Start parsing from left to right If operator push in stack. In number add in queue and increment count by one, if count == 2 then pop from stack add in queue, decrements the count by one. On Friday, 29 June 2012 19:46:43 UTC+5:30, zerocool142 wrote: Given an integer expression in a prefix format (i.e. the operator precedes the number it is operating on) , print the expression in the post fix format . Example: If the integer expression is in the prefix format is *+56-78, the postfix format expression is 56+78-*. Both of these correspond to the expression (5+6)*(7-8). -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/rDtvZKTNNQcJ. To post to this group, send email to algogeeks@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: Question asked in Amazon Online Test
*Using Stack : *
j = 0;
for ( int i = 0; i prefix.len(); i++ ) {
if ( isOperator(prefix[i]) ) stk.push(prefix[i]);
else {
postfix[j] = prefix[i];
j++;
while ( !stk.empty() stk.top == '#' ) {
stk.pop();
postfix[j] = stk.top();
j++;
stk.pop();
}
stk.push('#');
}
}
--
Akshat Sapra
Under Graduation(B.Tech)
IIIT-Allahabad(Amethi Campus)
*--*
sapraaks...@gmail.com
akshatsapr...@gmail.com
rit20009008@ rit20009...@gmail.comiiita.ac.in
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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: Question asked in Amazon online test
Hi,
This one is quite easy. You have to calculate the number of one's before
every zero and add them up. That's it.
public class Test1 {
public void printArray(int[] tmpArr) {
for (int i : tmpArr) {
System.out.println(i);
}
}
public int calculateMinSwaps(int[] tmpArr) {
int minSwaps = 0;
int numberOfOne = 0;
for (int i : tmpArr) {
if (i == 1) {
numberOfOne++;
} else {
minSwaps += numberOfOne;
}
}
return minSwaps;
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Test1 test1 = new Test1();
int[] minSwaps = {
1,1,1,0,0,0,1,0
};
// test1.printArray(minSwaps);
int minswap = test1.calculateMinSwaps(minSwaps);
System.out.println(minswap);
}
}
On Saturday, June 23, 2012 11:34:55 AM UTC+5:30, zerocool142 wrote:
Given an array containing sequence of bits (0 or 1), you have to sort
this array in the ascending order i.e. all 0' in first part of array
followed by all 1's. The constraints is that you can swap only the
adjacent elements in the array. Find the minimum number of swaps
required to sort the given input array.
Example: Given the array (0,0,1,0,1,0,1,1) the minimum number of swaps
is 3.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/XDJ5a5YfykEJ.
To post to this group, send email to algogeeks@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: Question asked in Amazon online test
get the right most zero and left most one if index of right most zero is less than the index of left most one ,the problem is solved other wise swap 0 and 1 and so on... i argue this will give minimum swaps... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/ELCan59xll4J. To post to this group, send email to algogeeks@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: Question asked in Amazon online test
will bubble sort give number of swaps?? I tried the (bubble sort) code of 1,0,0,1,1,0,1 swapcount = 5 and for the array (0,0,1,0,1,0,1,1)swapcount = 3 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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: Question asked in Amazon online test
@deepika yes, it's giving number of swaps. still Linear time solution would be better :-) On Fri, Jun 22, 2012 at 11:38 PM, deepikaanand swinyanand...@gmail.com wrote: will bubble sort give number of swaps?? I tried the (bubble sort) code of 1,0,0,1,1,0,1 swapcount = 5 and for the array (0,0,1,0,1,0,1,1)swapcount = 3 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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: Question asked in Amazon online test
i think it can be done in O(n) for each 1, calculate no. of zeros in right and adding all no. of zeros in right of all 1's will give no. of swaps. correct me if i am wrong On Sat, Jun 23, 2012 at 12:19 PM, Sourabh Singh singhsourab...@gmail.comwrote: @deepika yes, it's giving number of swaps. still Linear time solution would be better :-) On Fri, Jun 22, 2012 at 11:38 PM, deepikaanand swinyanand...@gmail.com wrote: will bubble sort give number of swaps?? I tried the (bubble sort) code of 1,0,0,1,1,0,1 swapcount = 5 and for the array (0,0,1,0,1,0,1,1)swapcount = 3 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- *DARPAN BAWEJA* *3rd year, I.T* *MNNIT Allahabad* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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: Question asked in Amazon online test
@ALL
see if this work's :
#includeiostream
using namespace std;
int a[8]={0,0,1,0,1,0,1,1};
int count_zero(int size)
{ int i,count =0;
for(i=0;isize;i++) if(!a[i]) count++;
return count;
}
int solve(int size)
{ int num_zero=count_zero(size);
int p_zero,p_one,i;
int count=0;
p_zero=0;
for(p_one=0;p_onesize p_zeronum_zero;p_one++)
{
if(!a[p_one])
{ count+=(p_one-p_zero);
p_zero++;
a[p_one]=1;
}
}
return count;
}
main()
{ printf(%d\n,solve(8));
system(pause);
return 0;
}
On Sat, Jun 23, 2012 at 12:09 AM, Darpan Baweja darpan.bav...@gmail.com wrote:
i think it can be done in O(n)
for each 1, calculate no. of zeros in right
and adding all no. of zeros in right of all 1's will give no. of swaps.
correct me if i am wrong
On Sat, Jun 23, 2012 at 12:19 PM, Sourabh Singh singhsourab...@gmail.com
wrote:
@deepika
yes, it's giving number of swaps.
still Linear time solution would be better :-)
On Fri, Jun 22, 2012 at 11:38 PM, deepikaanand swinyanand...@gmail.com
wrote:
will bubble sort give number of swaps??
I tried the (bubble sort) code of 1,0,0,1,1,0,1 swapcount = 5
and for the array (0,0,1,0,1,0,1,1)swapcount = 3
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
DARPAN BAWEJA
3rd year, I.T
MNNIT Allahabad
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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: Question asked in Amazon online test
@saurabh..wat array r u getting finallyis it all 1's or in sorted
order for the input
int a[8]={1,1,1,0,1,0,1,1};
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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: Question asked in Amazon online test
if we just need to determine number of swaps, it can be Done in O(n) Ex : 11100010 start counting number of zeros from the end so we have zeroCount = 1 whenever we encounter a 1 we add current zeroCount to numberOfSwaps so numberOfSwaps = 1 and so on the final value of numberOsSwaps is the answer correct me if i am wrong -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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: Question asked in Amazon online test
start scanning the array from last .. maintain two pointers. one for last
encountered zero. second for moving backward. whenever you encounter the
one just swap it with the last zero. enhance the pointer till next zero
encounters. at last you will have the number of swaps.
I think my solution works if i hv not misunderstood the problem..
Correct me if I am wrong.
Regards
Rajesh Pandey
On Sat, Jun 23, 2012 at 12:51 PM, Sourabh Singh singhsourab...@gmail.comwrote:
@ALL
see if this work's :
#includeiostream
using namespace std;
int a[8]={0,0,1,0,1,0,1,1};
int count_zero(int size)
{ int i,count =0;
for(i=0;isize;i++) if(!a[i]) count++;
return count;
}
int solve(int size)
{ int num_zero=count_zero(size);
int p_zero,p_one,i;
int count=0;
p_zero=0;
for(p_one=0;p_onesize p_zeronum_zero;p_one++)
{
if(!a[p_one])
{ count+=(p_one-p_zero);
p_zero++;
a[p_one]=1;
}
}
return count;
}
main()
{ printf(%d\n,solve(8));
system(pause);
return 0;
}
On Sat, Jun 23, 2012 at 12:09 AM, Darpan Baweja darpan.bav...@gmail.com
wrote:
i think it can be done in O(n)
for each 1, calculate no. of zeros in right
and adding all no. of zeros in right of all 1's will give no. of swaps.
correct me if i am wrong
On Sat, Jun 23, 2012 at 12:19 PM, Sourabh Singh
singhsourab...@gmail.com
wrote:
@deepika
yes, it's giving number of swaps.
still Linear time solution would be better :-)
On Fri, Jun 22, 2012 at 11:38 PM, deepikaanand swinyanand...@gmail.com
wrote:
will bubble sort give number of swaps??
I tried the (bubble sort) code of 1,0,0,1,1,0,1 swapcount = 5
and for the array (0,0,1,0,1,0,1,1)swapcount = 3
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
DARPAN BAWEJA
3rd year, I.T
MNNIT Allahabad
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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: Question asked in Amazon online test
It will work because we need to swap only adjacent elements. So we do a
sweep from left to right finding the number of ones encountered to the left
of a zero when we find a zero. We keep adding the number as we sweep the
entire length.
On Sat, Jun 23, 2012 at 1:14 PM, deepikaanand swinyanand...@gmail.comwrote:
@saurabh..wat array r u getting finallyis it all 1's or in sorted
order for the input
int a[8]={1,1,1,0,1,0,1,1};
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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: Question asked in Amazon online test
@all
yaa.. For getting number of swaps.. we have to calculate total number of
zeroes on the right for each '1' and on adding them
we will get the number of swaps. and in O(n) time.
On Sat, Jun 23, 2012 at 1:16 PM, Guruprasad Sridharan
sridharan.mi...@gmail.com wrote:
It will work because we need to swap only adjacent elements. So we do a
sweep from left to right finding the number of ones encountered to the left
of a zero when we find a zero. We keep adding the number as we sweep the
entire length.
On Sat, Jun 23, 2012 at 1:14 PM, deepikaanand swinyanand...@gmail.comwrote:
@saurabh..wat array r u getting finallyis it all 1's or in sorted
order for the input
int a[8]={1,1,1,0,1,0,1,1};
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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: Question asked in Amazon online test
@deepika anand
solution given by me is for getting number of swap's in O(n)
as far as sorting goes any O(n lgn) algo can be used .
if count sort is allowed then O(n) for sorting also.[constant extra space.. ]
On Sat, Jun 23, 2012 at 12:49 AM, ashish jain ashishjainco...@gmail.com wrote:
@all
yaa.. For getting number of swaps.. we have to calculate total number of
zeroes on the right for each '1' and on adding them
we will get the number of swaps. and in O(n) time.
On Sat, Jun 23, 2012 at 1:16 PM, Guruprasad Sridharan
sridharan.mi...@gmail.com wrote:
It will work because we need to swap only adjacent elements. So we do a
sweep from left to right finding the number of ones encountered to the left
of a zero when we find a zero. We keep adding the number as we sweep the
entire length.
On Sat, Jun 23, 2012 at 1:14 PM, deepikaanand swinyanand...@gmail.com
wrote:
@saurabh..wat array r u getting finallyis it all 1's or in sorted
order for the input
int a[8]={1,1,1,0,1,0,1,1};
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
