u can use strtok to tokenise the string on the parameter of comma.
now maintain an array of linked lists or hashtable in which the key will be
a starting character.
On Fri, Jun 22, 2012 at 8:41 PM, Abhishek Sharma abhi120...@gmail.comwrote:
make a hashtable where,
key is the first character
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
Let u and r be the distance to move in the up and right directions. u=y2-y1
and r=x2-x1.
We have to move a total of u+r units. So the answer would be (u+r)!/u!r!
since we are counting only the distinct paths.
Each path from (x1,y1) to (x2,y2) may be expressed as a sequence of u+r
steps
Use a merge sort like procedure to count the number of inversions such that
0 appears after 1.
On Sat, Jun 23, 2012 at 11:34 AM, Gobind Kumar Hembram gobind@gmail.com
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'
If we use merge sort like procedure,ans will be 1 here it should be
3.we have to swap 0s and 1s linearly.
--
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
We need to sort as we count the inversions.
On Sat, Jun 23, 2012 at 11:56 AM, Gobind Kumar Hembram gobind@gmail.com
wrote:
If we use merge sort like procedure,ans will be 1 here it should be
3.we have to swap 0s and 1s linearly.
--
You received this message because you are subscribed
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
@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
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
@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;
@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
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
recursion internally uses one stack for maintaining the return
addresses.which all we need... :-)
On Friday, June 22, 2012 11:38:39 AM UTC+5:30, joker wrote:
@ALL this shud work :-)
#includeiostream
#includequeue
using namespace std;
queueint Q;
void rev()
{ if(!Q.empty())
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
bcaz choosing any vertical will automatically fix the horizontals and
vice verse
(u+r) C r= (u+r) C u
On Sat, Jun 23, 2012 at 1:08 PM, Kumar Vishal kumar...@gmail.com wrote:
Let u and r be the distance to move in the up and right directions.
u=y2-y1 and r=x2-x1.
(u+r) C r
On
Let u and r be the distance to move in the up and right directions.
u=y2-y1 and r=x2-x1.
(u+r)Cr
On Sat, Jun 23, 2012 at 11:40 AM, Guruprasad Sridharan
sridharan.mi...@gmail.com wrote:
Let u and r be the distance to move in the up and right directions.
u=y2-y1 and r=x2-x1.
We have to
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
@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
Some how I found that we need to run bfs twice to get the largest distance
between any two nodes of a tree. Please explain me how it works.
regards,
avinash
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web
@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
Is this similar to finding the diameter of a tree(longest disteance between
two leaves) ?? If yes than visit this link
http://www.cs.duke.edu/courses/spring00/cps100/assign/trees/diameter.html
On Sat, Jun 23, 2012 at 2:44 PM, Avinash jain.av...@gmail.com wrote:
Some how I found that we need to
Is longest path between two node in a tree is equal two logest path between
two leaves??
On Sat, Jun 23, 2012 at 5:35 PM, Navin Kumar algorithm.i...@gmail.comwrote:
Is this similar to finding the diameter of a tree(longest disteance
between two leaves) ?? If yes than visit this link
Write a function longest_palindrome, which takes an array of strings
as argument and returns the
longest palindrome in that array if any.Please give ideas how to
implement this function.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post
@bhaskar,rammar:
I don't think your algo willn not work for the following test case --
test case :
arr: 2 4 6 8
arr^2 : 6 8 10 10 12 14(sum of each unique pair in arr[i])
let's say target sum is 26
your solution will return true as they 12+14=26 but in 12 and 14, 8 is
no this problem is different from finding the longest path which is
actually maximum number of nodes covered in the longest path
On Sat, Jun 23, 2012 at 5:45 PM, Navin Kumar algorithm.i...@gmail.comwrote:
Is longest path between two node in a tree is equal two logest path
between two leaves??
What I can think
is case is :
10
/ \
6 13
/ \
4 5
/ \ \
6 7 8
/ \ \
9 a b
so from a-b is
a-7-4-2-5-8-b
1- Left Tree then
2- Right Tree
add them
On Sat, Jun 23, 2012 at 3:49 PM, Kumar Vishal kumar...@gmail.com wrote:
What I can think
What I can think
is case is :
1
/ \
2 3
/ \
4 5
/ \ \
6 7 8
/ \ \
9 a b
so from a-b is
a-7-4-2-5-8-b
On Sat, Jun 23, 2012 at 2:44 PM, Avinash jain.av...@gmail.com wrote:
Some how I found that we need to run bfs twice to get the largest distance
you are just finding the diameter of the tree. Remember the graph I am
talking about is weighted. So if two adjacent vertices has infinite weight
than that would be the longest distance between any two vertices in the
graph.
e.g. In you diagram suppose the sum of weight of the edges from a-b is
To do this question in O(n) time follow the post Segment trees in this
post of topcoder
http://community.topcoder.com/tc?module=Staticd1=tutorialsd2=lowestCommonAncestor
Here in this given algorithm preprocessing time in O(n) and query time is
O(log n).
--
Akshat Sapra
Under
yeah use pure virtual fxn..
On Fri, Jun 22, 2012 at 3:41 PM, himanshu kansal
himanshukansal...@gmail.com wrote:
i told the interviewer...bt he said thn the constt would not be accessible
to derived class alsohe told me dt u shld make the constt.
protecteddats why i ws confused...
@ALL
O(n^2 lg(n^2))
http://www.spoj.pl/problems/SUMFOUR/
my code :
http://ideone.com/kAPNB
plz. suggest some test case's :
On Sat, Jun 23, 2012 at 6:59 AM, Amol Sharma amolsharm...@gmail.com wrote:
@bhaskar,rammar:
I don't think your algo willn not work for the following test case --
Given an array of integers find a peak element of array in log(n) time.
for example if A={3,4,6,5,10} then peak element is 6 ( 65 64 ).
Regards.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
This is a variation of binary search, the difference being that we have to
search for an element that is greater than its immediate left one and
lesser than its immediate right one. Just implement binary search with
these additional constraints, thereby giving O(log n).
In case of any
As array is not sorted, how do you decide to move left or right ?
On Sun, Jun 24, 2012 at 12:41 AM, adarsh kumar algog...@gmail.com wrote:
This is a variation of binary search, the difference being that we have to
search for an element that is greater than its immediate left one and
lesser
@adarsh kumar
are u sure it's worst case will be O (log n) ??
i think iff array is fully sorted O(n) will be required to say NO
such element present
On Sat, Jun 23, 2012 at 1:11 PM, adarsh kumar algog...@gmail.com wrote:
This is a variation of binary search, the difference being that we have to
@sourabh:
for this particular question..
in your code replace
if(binary_search(c,c+size,-b[i]))
count++;
by
count+=upper_bound(c,c+size,-b[i])-lower_bound(c,c+size,-b[i]);
you are actually missing some of the quadruplesas there can be more
than one element with value -b[i] in the array
@ Amol Sharma
thanx got it..
yup, overlooked those case's :-) my bad..
On Sat, Jun 23, 2012 at 1:31 PM, Amol Sharma amolsharm...@gmail.com wrote:
@sourabh:
for this particular question..
in your code replace
if(binary_search(c,c+size,-b[i]))
count++;
by
@adarsh :its nt dat easy as u see it..
On Sun, Jun 24, 2012 at 1:45 AM, Sourabh Singh singhsourab...@gmail.comwrote:
@adarsh kumar
are u sure it's worst case will be O (log n) ??
i think iff array is fully sorted O(n) will be required to say NO
such element present
On Sat, Jun 23, 2012 at
just found a good resource for 1d and 2D version :
http://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf
On Sun, Jun 24, 2012 at 3:31 AM, sengar.mahi sengar.m...@gmail.com wrote:
@adarsh :its nt dat easy as u see it..
On Sun, Jun 24, 2012 at 1:45 AM, Sourabh Singh
@Hassan Monfared
was reading that link only. it's strange how he assume's we can leave
half of element's ??
– If A[n/2-1]A[n/2] then search for a peak among A[1]… A[n/2-1] ?? why ??
eg. 12 12 12 11 1 2 5 3
m i missing something ??
On Sat, Jun 23, 2012 at 10:02 PM, Hassan Monfared
I was amazed too, but Idea is about :
--
Otherwise: locally rising on some side
• Must be a peak in that direction
• So can throw away rest of array,
leaving a[0-i] or a[i+1-n].
--
i'm not sure yet and need to test with a code.
On Sun, Jun 24, 2012 at 9:45 AM, Sourabh
I think it can't be done in O(log n) as per given problem constraints.
It can be done in O(log n) if additional information that array is
bitonic is given.
--
Prakhar Jain
IIIT Allahabad
B.Tech IT 3rd Year
Mob no: +91 9454992196
E-mail: rit2009...@iiita.ac.in
jprakha...@gmail.com
On
42 matches
Mail list logo
