[algogeeks] Find max sum of elements in an array ( with twist)
Given a array with +ve and -ve integer , find the maximum sum such that you are not allowed to skip 2 contiguous elements ( i.e you have to select atleast one of them to move forward). eg :- 10 , 20 , 30, -10 , -50 , 40 , -50, -1, -3 Output : 10+20+30-10+40-1 = 89 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Better data structure/Algorithm to handle the following porblem
B+ tree is used by database... i guess same can be used here. On 28 Dec 2014 16:13, kumar raja rajkumar.cs...@gmail.com wrote: which is like a table in database, and produces results for user queries. Data is: in txt file. ID, FIRSTNAME, LASTNAME, AGE, SALARY, TITLE 1, venkatesh, kumar, 21, 3, reporter 2, kiran, kannan, 45, 9000, chairman 3, pradeep, mishra, 35, 15000, manager 4, suman, raj, 35, 12000, manager user query will be like select firstName, lastName where age25 orderby salary dsc dsc - for descending you have to produce appropriate records. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Distributed System problem
It is a system design problem . Suppose a http request is sent to server . Now Server maintains cache for fast retrieval . if link is present int the cache then it just takes a data from cache and return it to user but if not , then user will fetch that http address and then store it in its cache and return same to the user . Problem is that there are many server and many global cache as expected in distributed system. Now when request is received by a server then how can we maintain global cache such that server can know which cache to query instead of querying each global cache as it will be inefficient. one approach can be.. maintain 26 global cache . Now when request is received by server it check the web link say , www.*a*bc.com ... here server will query cache-1 . Similarly cache-2 will take care of links with starts from b...www.*b*bc.com and so on above method will avoid duplicity in caches but will not be very efficient as a cache may have higher query rate than others... any other approach ?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Distributed System problem
approach i have mentioned have flaws . so what other approaches we can try to solve this ? On Sun, Dec 14, 2014 at 2:23 PM, SOMU somnath.nit...@gmail.com wrote: Then the Domain name is altered from abc to bbc .. That indirectly means that the nameserver will change. So in that case the Cache will point to the New NameServer .. Thanks, Somnath Singh On Sun, Dec 14, 2014 at 2:04 PM, atul anand atul.87fri...@gmail.com wrote: It is a system design problem . Suppose a http request is sent to server . Now Server maintains cache for fast retrieval . if link is present int the cache then it just takes a data from cache and return it to user but if not , then user will fetch that http address and then store it in its cache and return same to the user . Problem is that there are many server and many global cache as expected in distributed system. Now when request is received by a server then how can we maintain global cache such that server can know which cache to query instead of querying each global cache as it will be inefficient. one approach can be.. maintain 26 global cache . Now when request is received by server it check the web link say , www.*a*bc.com ... here server will query cache-1 . Similarly cache-2 will take care of links with starts from b...www.*b*bc.com and so on above method will avoid duplicity in caches but will not be very efficient as a cache may have higher query rate than others... any other approach ?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Re: Solving coin change problem with limited coins.
@Don : i am intersted in DP bottom up approach with less time complexity.
solving it recursively is a simpler approach...
On 15 May 2014 22:25, Don dondod...@gmail.com wrote:
How about this:
const int N = 6;
unsigned int coins[N] = {100,50,25,10,5,1};
unsigned int count[N] = {2, 1, 1, 5, 4, 10};
int best = 10;
int minCoins(int s, int f=0, int d=0)
{
if (d == 0) best = s; // It can never take more than s coins
if (s 1) return 0; // No coins required
if (d = best) return 100; // We've already used too many coins.
int result=best;
for(int i = f; i N; ++i) // Don't regress
{
if (count[i]) // Only try coins which are available
{
if (coins[i] s) // Try using this coin
{
--count[i];
int sum = 1 + minCoins(s-coins[i], i, d+1);
if (sum result) sum = result;
if ((d == 0) (sum best)) best = sum;
++count[i];
}
else if (coins[i] == s) return 1; // This coin is all we need
}
}
return result;
}
int main()
{
int s;
scanf(%d, s);
printf(The fewest coins to total to %d is %d\n, s, minCoins(s));
return 0;
}
On Thursday, May 15, 2014 1:35:12 AM UTC-4, atul007 wrote:
Solving coin change problem with limited coins.
Given an array of denominations and array Count , find minimum number of
coins required to form sum S.
for eg: coins[]={1,2,3};
count[]={1,1,3};
i.e we have 1 coin of 1$ , 1 coin of 2$ , 3 coins of 3$.
input S = 6
output = 2
possible combination : 3+3 = 6
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Solving coin change problem with limited coins.
Solving coin change problem with limited coins.
Given an array of denominations and array Count , find minimum number of
coins required to form sum S.
for eg: coins[]={1,2,3};
count[]={1,1,3};
i.e we have 1 coin of 1$ , 1 coin of 2$ , 3 coins of 3$.
input S = 6
output = 2
possible combination : 3+3 = 6
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Remove minimum set of vertices to make the grap divided into more than one component
find articulation point in graph On 29 Apr 2014 16:56, shashi kant shashiski...@gmail.com wrote: Problem is as follows: 1. Given a connected graph. 2. Remove a vertex out of it and if graph is divided into two components return that vertex. 3. else find a set of vertices to be removed that will divide graph into more than 1 component. Please Help me out here .. probably min-cut problem http://www.geeksforgeeks.org/minimum-cut-in-a-directed-graph/ is suitable here. *Thanks Regards,* *Shashi Kant * *Think positive and find fuel in failure* http://thinkndoawesome.blogspot.com/ *Senior Software Engineer* *Samsung Research India Bangalore .* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Re: maximum subsquare such that all four borders are filled black
@Don: what is the point of considering s=2 when we have already found
s=3.As question says find the maximum subsquare. Which is of size 3 and
this the expected outcome.
On Mon, Mar 31, 2014 at 11:28 PM, Don dondod...@gmail.com wrote:
00
00
010100
011100
01
00
In this case, when i and j are 1, your algorithm will set s = 3. The if
statement will fail, and it will never notice that it could have formed a
square with s=2.
Don
On Sunday, March 30, 2014 9:49:21 AM UTC-4, atul007 wrote:
@don : According to question we want to find the maximum subsquare.
can you give me test case for which this wont work?
On Fri, Mar 28, 2014 at 9:41 PM, Don dond...@gmail.com wrote:
No, that is not the same.
It won't find a square smaller than s.
Don
On Thursday, March 27, 2014 2:56:29 AM UTC-4, atul007 wrote:
@Don : your algo time complexity is O(n^2)
It can be reduced to this :-
// Now look for largest square with top left corner at (i,j)
for(i = 0; i n; ++i)
for(j = 0; j n; ++j)
{
s = Min(countRight[i][j], countDown[i][j]);
if (countRight[i][j] countDown[i][j]
(countRight[i+s][j] = s) (countDown[i][j+s] = s) smax)
{
bestI = i; bestJ = j; max = s;
}
}
On 1/25/13, Don dond...@gmail.com wrote:
The worst case I know of is when the matrix is solid black except for
the lower right quadrant. In this case, it does break down into
O(n^3)
runtime. It took about 8 times as long to run n=4000 as it took for
n=2000.
Don
On Jan 24, 10:29 am, Don dondod...@gmail.com wrote:
I'm not sure I understand your case. However, I stated that there
are
cases where it is worse than O(N^2). The runtime is highly dependent
on the contents of the matrix. In many cases it takes fewer than N^2
iterations. Occasionally it takes more. On average it seems to be
roughly O(N^2), but again that depends a lot on what is in the
matrix.
I got that result by trying different ways of filling the matrix. I
tried things like randomly setting each pixel with various
probabilities, placing random horizontal and vertical segments,
placing random squares, or placing random filled squares. I did all
of
those both in black on white and white on black. In all of those
cases, going from n=1000 to n=2000 resulted in a runtime increase of
less than a factor of 4.
Don
On Jan 23, 10:33 pm, bharat b bagana.bharatku...@gmail.com wrote:
@Don: the solution is very nice.. But, how can u prove that it is
O(n^2)..
for me it seems to be O(n^3) ..
Ex: nxn matrix .. all 1s from (n/2,0) to (n/2,n/2).
all 1s from (n/2,0) to (n,0).
On Thu, Jan 17, 2013 at 9:28 PM, Don dondod...@gmail.com wrote:
The downside is that it uses a bunch of extra space.
The upside is that it is pretty fast. It only does the
time-consuming
task of scanning the matrix for contiguous pixels once, it only
searches for squares larger than what it has already found, and
it
doesn't look in places where such squares could not be. In
practice
it
performs at O(n^2) or better for most inputs I tried. But if you
are
devious you can come up with an input which takes longer.
Don
On Jan 17, 10:14 am, marti amritsa...@gmail.com wrote:
awesome solution Don . Thanks.
On Thursday, January 17, 2013 12:38:35 AM UTC+5:30, marti
wrote:
Imagine there is a square matrix with n x n cells. Each cell
is
either
filled with a black pixel or a white pixel. Design an
algorithm
to
find the
maximum subsquare such that all four borders are filled with
black
pixels;
optimize the algorithm as much as possible
--
--
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send
an email to algogeeks+...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Re: maximum subsquare such that all four borders are filled black
@don : According to question we want to find the maximum subsquare.
can you give me test case for which this wont work?
On Fri, Mar 28, 2014 at 9:41 PM, Don dondod...@gmail.com wrote:
No, that is not the same.
It won't find a square smaller than s.
Don
On Thursday, March 27, 2014 2:56:29 AM UTC-4, atul007 wrote:
@Don : your algo time complexity is O(n^2)
It can be reduced to this :-
// Now look for largest square with top left corner at (i,j)
for(i = 0; i n; ++i)
for(j = 0; j n; ++j)
{
s = Min(countRight[i][j], countDown[i][j]);
if (countRight[i][j] countDown[i][j]
(countRight[i+s][j] = s) (countDown[i][j+s] = s) smax)
{
bestI = i; bestJ = j; max = s;
}
}
On 1/25/13, Don dond...@gmail.com wrote:
The worst case I know of is when the matrix is solid black except for
the lower right quadrant. In this case, it does break down into O(n^3)
runtime. It took about 8 times as long to run n=4000 as it took for
n=2000.
Don
On Jan 24, 10:29 am, Don dondod...@gmail.com wrote:
I'm not sure I understand your case. However, I stated that there are
cases where it is worse than O(N^2). The runtime is highly dependent
on the contents of the matrix. In many cases it takes fewer than N^2
iterations. Occasionally it takes more. On average it seems to be
roughly O(N^2), but again that depends a lot on what is in the matrix.
I got that result by trying different ways of filling the matrix. I
tried things like randomly setting each pixel with various
probabilities, placing random horizontal and vertical segments,
placing random squares, or placing random filled squares. I did all of
those both in black on white and white on black. In all of those
cases, going from n=1000 to n=2000 resulted in a runtime increase of
less than a factor of 4.
Don
On Jan 23, 10:33 pm, bharat b bagana.bharatku...@gmail.com wrote:
@Don: the solution is very nice.. But, how can u prove that it is
O(n^2)..
for me it seems to be O(n^3) ..
Ex: nxn matrix .. all 1s from (n/2,0) to (n/2,n/2).
all 1s from (n/2,0) to (n,0).
On Thu, Jan 17, 2013 at 9:28 PM, Don dondod...@gmail.com wrote:
The downside is that it uses a bunch of extra space.
The upside is that it is pretty fast. It only does the
time-consuming
task of scanning the matrix for contiguous pixels once, it only
searches for squares larger than what it has already found, and it
doesn't look in places where such squares could not be. In
practice
it
performs at O(n^2) or better for most inputs I tried. But if you
are
devious you can come up with an input which takes longer.
Don
On Jan 17, 10:14 am, marti amritsa...@gmail.com wrote:
awesome solution Don . Thanks.
On Thursday, January 17, 2013 12:38:35 AM UTC+5:30, marti wrote:
Imagine there is a square matrix with n x n cells. Each cell
is
either
filled with a black pixel or a white pixel. Design an
algorithm
to
find the
maximum subsquare such that all four borders are filled with
black
pixels;
optimize the algorithm as much as possible
--
--
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] explanation of solution required.
Hello, i found this question online and its solution tooBut i am not able to fully understand the solution.Need your help to proof correctness of the algo. Question is as follows :- *Question:* *Given an array A and a number S', provide an efficient algorithm (nlogn) to find a number K such that if all elements in A greater than K are changed to K, the sum of all elements in the resulting array will be S'.* *Example, given A: [90,30,100,40,20] and S' = 210, K will be 60.* *Ans)* #!/usr/bin/env python A = [90, 30, 100, 40, 20] S = 210 K = 60 A= sorted(A) prev = 0 sum = 0 for index, value in enumerate(A): # What do we need to set all subsequent values to to get the desired sum? solution = (S - sum) / (len(A) - index) # That answer can't be too big or too small. if prev solution = value: print solution sum += value prev = value -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Re: maximum subsquare such that all four borders are filled black
@Don : your algo time complexity is O(n^2)
It can be reduced to this :-
// Now look for largest square with top left corner at (i,j)
for(i = 0; i n; ++i)
for(j = 0; j n; ++j)
{
s = Min(countRight[i][j], countDown[i][j]);
if (countRight[i][j] countDown[i][j]
(countRight[i+s][j] = s) (countDown[i][j+s] = s) smax)
{
bestI = i; bestJ = j; max = s;
}
}
On 1/25/13, Don dondod...@gmail.com wrote:
The worst case I know of is when the matrix is solid black except for
the lower right quadrant. In this case, it does break down into O(n^3)
runtime. It took about 8 times as long to run n=4000 as it took for
n=2000.
Don
On Jan 24, 10:29 am, Don dondod...@gmail.com wrote:
I'm not sure I understand your case. However, I stated that there are
cases where it is worse than O(N^2). The runtime is highly dependent
on the contents of the matrix. In many cases it takes fewer than N^2
iterations. Occasionally it takes more. On average it seems to be
roughly O(N^2), but again that depends a lot on what is in the matrix.
I got that result by trying different ways of filling the matrix. I
tried things like randomly setting each pixel with various
probabilities, placing random horizontal and vertical segments,
placing random squares, or placing random filled squares. I did all of
those both in black on white and white on black. In all of those
cases, going from n=1000 to n=2000 resulted in a runtime increase of
less than a factor of 4.
Don
On Jan 23, 10:33 pm, bharat b bagana.bharatku...@gmail.com wrote:
@Don: the solution is very nice.. But, how can u prove that it is
O(n^2)..
for me it seems to be O(n^3) ..
Ex: nxn matrix .. all 1s from (n/2,0) to (n/2,n/2).
all 1s from (n/2,0) to (n,0).
On Thu, Jan 17, 2013 at 9:28 PM, Don dondod...@gmail.com wrote:
The downside is that it uses a bunch of extra space.
The upside is that it is pretty fast. It only does the time-consuming
task of scanning the matrix for contiguous pixels once, it only
searches for squares larger than what it has already found, and it
doesn't look in places where such squares could not be. In practice
it
performs at O(n^2) or better for most inputs I tried. But if you are
devious you can come up with an input which takes longer.
Don
On Jan 17, 10:14 am, marti amritsa...@gmail.com wrote:
awesome solution Don . Thanks.
On Thursday, January 17, 2013 12:38:35 AM UTC+5:30, marti wrote:
Imagine there is a square matrix with n x n cells. Each cell is
either
filled with a black pixel or a white pixel. Design an algorithm
to
find the
maximum subsquare such that all four borders are filled with
black
pixels;
optimize the algorithm as much as possible
--
--
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Re: strictly sorting by adding or subtracting a range of numbers
@bhargav : could you please explain your algorithmn
On 3/25/14, bhargav krishna yb ybbkris...@gmail.com wrote:
Even i completed it :). It was from one of the coding challenges...
public class Hill {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Integer[] l = new Integer[] {15,5, 4, 3, 2, 8};
hill(l);
}
public static void hill(Integer[] l) {
int max = 0;
for(int i=0;il.length;i++) {
if(maxl[i]) {
max = l[i];
}
}
int min =0 ;
while(true) {
int av = (max+min)/2;
if(min==max) {
if(isHill(l, av)) {
System.out.println(min);
}
else {
System.out.println(broke);
}
break;
}
if(isHill(l, av)) {
max = av;
}
else {
min= av+1;
}
}
}
public static Boolean isHill(Integer[] l, int i) {
int prev = -1;
for(int j=0;jl.length;j++) {
int max = Math.max(prev+1, l[j]-i);
if(Math.abs(max-l[j])i) {
return false;
}
prev = max;
}
return true;
}
}
On Tue, Mar 25, 2014 at 10:14 AM, Dan dant...@aol.com wrote:
I just stumbled upon this one (I know, a little late). At least this
way...
it's too late to be helpful if it was a Homework assignent. :-)
This is one of those problems that, at first, appears difficult, but ,
upon
closer inspection, turns out to have a very straight forward (elegant?)
solution.
Take any two adjacent values from the list... call them a b
In the worst case scenario, the value of a is higher than the value
of
b... a b
Therefore, we need an X value that solves the inequality a - X
b + X
Rearrange this equation just slightly to another equivalent equation...
a
- b2X
This indicates that a slightly different (but, still equivalent) problem
can
be solved to arrive at a correct solution.
Only allow values from 0 to 2X, [0,2X] to be added to the original
values
in the array (ie. no subtractions). This simplifies things greatly and
allows for a clear algorithm solution that can be easily performed in a
single pass through the array. Essentially, you find a value of 2X that
works... then divide that in half, and convert the resulting float type
value to a whole integer value to get the final X value that solves the
'original' problem statement.
The fortran code below has been tested and appears to work just fine.
The real algorithm of note is the function routine:FUNCTION
TransformArray( v ).
Note that the important code is only 7 simple lines long and should
be easy to recode in most any language.
It runs extremely fast, even for array sizes of 1.
There's also 'fluff' code here, written to test multiple test sets to
check
the value of X arrived and to time everything. at is the desired answer.
Does anyone know of any Practical applications for this algorithm?? I'm
guessing it's just an interesting problem.
Dan:-)
Module Transform
Contains
Function TransformArray( v ) Result(x)
!---
! Find a minium X value to transform the array, v(:)
! Transformed array values can be negative. It is a trivial task to
! alter this to guarantee no negative values in the transformed array.
!---
Integer, intent(in) :: v(:)
Integer :: x
Integer :: i, b
x = 0
b = v(1)
Do i = 2, Size(v)
b = Max( b+1, v(i) )
x = Max( x , b-v(i) )
End Do
x = Ceiling( x/2.0 ) ! smallest integer greater/equal to the
value.
End Function TransformArray
Subroutine Validate_X( v, x )
!-
! Given a value of x, see if the array can be successfully transformed
! This is merely code to see if the X value arrived at is correct.
!-
Integer, intent(in) :: v(:)
Integer, intent(in) :: x
Integer, allocatable :: vt(:), xt(:)
Integer :: i, n
n = Size(v)
Allocate( vt(n), xt(n) )
vt(1) = v(1) - x
xt(1) = -x
Do i = 2, n
vt(i) = Max( vt(i-1)+1, v(i)-x )
xt(i) = vt(i)-v(i)
End Do
write(*,'(a,2i6)') ' v = ', v
write(*,'(a,2i6)') ' xt = ', xt
write(*,'(a,2i6)') ' vt = ', vt
If( Any( abs(xt) x ) ) Then
write(*,'(a)' ) ' A higher x value was required during the
transformation.'
write(*,'(a,i0,a)') ' X = ', x, ' does not work.'
End If
If( Any( vt(1:n-1) = vt(2:n) ) )
write(*,'(a)') ' ERROR: Transformed array is not in Strictly
Ascending
order!'
End Subroutine Validate_X
End Module Transform
Program Main
!--
Use Transform
Implicit None
Integer, parameter :: nmax=1
Integer :: n, x
Integer, allocatable :: v(:)
Real,allocatable :: r(:)
Integer :: it1, it2
Allocate( v(nmax),
[algogeeks] Data structure question
1) - When u login, it retrieves all the unread mails only. Which data structure should you use ? 2)- If you get an event invitation then u have to be notified . eg if u have two event invitations, one is in the next hour and other one 2 months later, the one that is tomorrow will be given a higher priority and sent to u before any other event or mail.What data structure should you use? 3) - If the events are added to your calendar on the server ,the server should handle the query : Find if there is a time slot on a particular date in a particular time range of the given duration. What data structure will you use ?eg - find a free timeslot on 31st of august between 6 AM to 7 PM of 30 min duration. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Integer partition problem - DP
Problem is similar to coin change problem(i.e given an array of coins denomination , Find number of ways to create N Rupees).So given input K...fill up array from 1 to K.and use this array and a input to coin change problem On Sat, Mar 1, 2014 at 9:55 PM, kumar raja rajkumar.cs...@gmail.com wrote: Given an integer how many number of ways u can partition the number? e.g. 3 can be written as 3,1+2,1+1+1 and 4 can be written as 4, 1+1+1+1,2+2,1+3,1+1+2 So for 3 -- 3 for 4 --5. The order of the elements in the partition does not matter. So how to calculate the number of ways to partition the given number? Can someone give idea on how to write the recurrence relation for the problem? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Find 3 digit number.
Given a number N, find the smallest 3 digits number such that product of its digits is equal to N. For Eg:- for input 24 , output :138 (1*3*8 = 24) for input 36 , output :149 (1*4*9 = 36) for input 100 , output : 455 (4*5*5 = 100) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Re: Generate random number from 1 to 10.
@don : awesome +1 . I was not aware of George Marsaglia's Multiply
With Carry generator. But it is soo clll . If you have any good link
for its proof or explanation of the idea behind it then please mention it.
I never knew generating random number can be few lines of code :)
Thanks :)
On Sat, Feb 8, 2014 at 1:28 AM, Don dondod...@gmail.com wrote:
A random generator will not always (or even usually) produce a permutation
of the possible values before repeating.
If you call my function 10 million times and tally up the results, you
will get a distribution with about a million of each value, as close as you
would expect for a random sample.
Your question was to randomly generate values in the range 1-10, not to
generate permutations.
Here is a way to generate a permutation without swapping:
unsigned int X = time(0);
int n[10];
n[0] = 10;
for(i = 1; i 10; ++i)
{
X = 63663 * (X65535) + (X16);
int j = (X 65535) % (i+1);
n[i] = n[j];
n[j] = i;
}
// n now contains a permutation of the values 1-10.
On Thursday, February 6, 2014 11:33:53 PM UTC-5, atul007 wrote:
@don: algo look fine..i tested it ,but it did not generate 1-10 with
probabilty of 1/10 everytime.
actually question was asked in an intrview.
question started with displaying all elements in an array randomly
without repetition i.e only once( probabilty 1/10)...which can be done with
fisher yates .
then interviewer said that u are not allowed to swap elements which is
requied in fishr yates.
his hint was: how will you generate randomly number from 1-10 without use
of rand() function.
expected time complexity : O(n)
On 7 Feb 2014 03:17, Don dond...@gmail.com wrote:
Just noticed that you asked for 1-10, and my code will clearly generate
0-9. Add one for the desired range.
Don
On Wednesday, February 5, 2014 4:29:26 PM UTC-5, Don wrote:
// Using George Marsaglia's Multiply With Carry generator
int rnd10()
{
static unsigned int x = time(0);
x = 63663 * (x65535) + (x16);
return (x 65535) % 10;
}
On Sunday, February 2, 2014 2:51:47 AM UTC-5, atul007 wrote:
Generate random number form 1 - 10 with probability of 1/10.You are
not allowed to used rand() function.
any simple way of achieving above with using any complex
implementation of random number generators algorithm .
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send
an email to algogeeks+...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Re: Generate random number from 1 to 10.
@don: algo look fine..i tested it ,but it did not generate 1-10 with
probabilty of 1/10 everytime.
actually question was asked in an intrview.
question started with displaying all elements in an array randomly without
repetition i.e only once( probabilty 1/10)...which can be done with fisher
yates .
then interviewer said that u are not allowed to swap elements which is
requied in fishr yates.
his hint was: how will you generate randomly number from 1-10 without use
of rand() function.
expected time complexity : O(n)
On 7 Feb 2014 03:17, Don dondod...@gmail.com wrote:
Just noticed that you asked for 1-10, and my code will clearly generate
0-9. Add one for the desired range.
Don
On Wednesday, February 5, 2014 4:29:26 PM UTC-5, Don wrote:
// Using George Marsaglia's Multiply With Carry generator
int rnd10()
{
static unsigned int x = time(0);
x = 63663 * (x65535) + (x16);
return (x 65535) % 10;
}
On Sunday, February 2, 2014 2:51:47 AM UTC-5, atul007 wrote:
Generate random number form 1 - 10 with probability of 1/10.You are not
allowed to used rand() function.
any simple way of achieving above with using any complex implementation
of random number generators algorithm .
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Generate random number from 1 to 10.
Generate random number form 1 - 10 with probability of 1/10.You are not allowed to used rand() function. any simple way of achieving above with using any complex implementation of random number generators algorithm . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] changing structure of binary tree based on gravity and node selected.
Imagine a binary tree lying on the floor with nodes as balls and edges as threads, you are given a pointer to a node. When you pick the tree from that node up what will be the structure of the tree. You have gravity changing the structure of the tree -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Solving equation
Hello, How to solve an equation with one unknown variable ? operator allowed are : + , - for eg . input could be :- x + ( 5 + 4 ) = 6 (x - 7) + 7 = (x + 1) - 5 If operator also allows * (multiply) , then what change in algorithm is required. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Re: Median Finding in Sorted Arrays
@dave : could you provide pseudo code for ur approach On 6 Jan 2014 07:39, Dave dave_and_da...@juno.com wrote: Use a binary search. Assume that you have arrays a[m] and b[n] sorted in ascending order. If a[i] is the kth smallest element, then b[k-i-2] must be smaller than a[i], and b[k-i-1] must be larger (assuming arrays are zero-based). After using a binary search to find the value of i to meet this condition with k = (m+n)/2, you have to determine if a[i] or b[k-i-1] is the final answer. The complexity is O(log m). Dave On Sunday, January 5, 2014 5:34:12 AM UTC-6, Sanjay Rajpal wrote: Hi guys, Please help me in finding median of two sorted arrays of length m and n in minimum possible time. Thanks, Sanjay -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] coloring problem Dynamic programming
@saurabh : i did not get your algo for modified ques i.e No 3 adjacent
houses should get same color
according to your recurrence
answer[i][j][1] = min(answer[i-1][t][0],answer[i-1][t][1]) + colorvalue[j] for
all t from 1 to k except j.
now suppose in some case *answer[i-1][t][0] *is found minimum in
above recurrence .
*answer[i-1][t][0] *means that i - 2 and i - 1 are of same color say for eg
color green.
answer[i][j][1] is not colored same as i-1 house (green in this case)
...now say it is colored with color yellow.
hence,
answer[i][j][1] is sum of house with color green+green+yellow.
i am not able to understand , how it is taking care that 3 adjacent are
colored
different.
could you please clarify my doubt.
On Thu, Dec 26, 2013 at 5:25 PM, Saurabh Paliwal
saurabh.paliwa...@gmail.com wrote:
@atul anand :- no, we need not use all the colors.
@kumar raja :- sorry dude for replying this late. Continuing with the
previous idea, I extend the solution for the modified problem as
1. let answer[i][j][0] represent minimum cost of coloring i houses when
ith house is colored with jth color and so is the (i-1)th house.
2. let answer[i][j][1] represent minimum cost of coloring i houses when
ith house is colored with jth color and (i-1)th is not.
The recurrence will be
3. *answer[i][j][0] = answer[i-1][j][1] + colorvalue[j]*
4. *answer[i][j][1] = min(answer[i-1][t][0],answer[i-1][t][1]) +
colorvalue[j]* for all t from 1 to k except j.
// In the first problem, I mistakenly wrote colorvalue[t] here. It will be
colorvalue[j] there. ( sorry for the confusion )
5. finally solution will be min(answer[n][j][0], answer[n][j][1]) for all
j from 1 to k.
6. initial settings -: answer[1][j][0] = answer[1][j][1] = colorvalue[j].
Also now that I read the problem, I guess colorvalue is not fixed for
every color, so that will be a 2-D matrix as well.
*replace every colorvalue[j] with colorvalue[i][j] in the above
recurrences*. ( i is the house number, j is the color number )
On Wed, Dec 18, 2013 at 10:16 PM, atul anand atul.87fri...@gmail.comwrote:
@kumar : i have one doubt regarding this question.Do we have to use all
K colors[K] to color all building.
for example :-
color[3]={1,2,10};
now if we have to color 6 building then i can use only 1st 2 color to
color all building and never 10 ...is this allowed ???
building[N]={1,2,1,2,1,2}
On Sun, Dec 15, 2013 at 12:44 AM, kumar raja
rajkumar.cs...@gmail.comwrote:
You have 'n' houses and 'k' colors. The cost of coloring a house with
one of the 'k' colors is different from coloring another house with same
color. The cost of coloring the house with different colors are different.
So now how to colour the 'n' houses such that no two adjcent houses will
get the same color and the total coloring cost for 'n' houses is minimized.
Regards,
Kumar Raja.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send
an email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
-Saurabh Paliwal
B-Tech. Comp. Science and Engg.
IIT ROORKEE
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] coloring problem Dynamic programming
@kumar : i have one doubt regarding this question.Do we have to use all K
colors[K] to color all building.
for example :-
color[3]={1,2,10};
now if we have to color 6 building then i can use only 1st 2 color to color
all building and never 10 ...is this allowed ???
building[N]={1,2,1,2,1,2}
On Sun, Dec 15, 2013 at 12:44 AM, kumar raja rajkumar.cs...@gmail.comwrote:
You have 'n' houses and 'k' colors. The cost of coloring a house with one
of the 'k' colors is different from coloring another house with same color.
The cost of coloring the house with different colors are different. So now
how to colour the 'n' houses such that no two adjcent houses will get the
same color and the total coloring cost for 'n' houses is minimized.
Regards,
Kumar Raja.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] coloring problem Dynamic programming
@saurabh : answer[i][j] = min(answer[i-1][t]) + colorvalue[t] where t varies from 1 to k except j. how this DP is taking care of the case where no adjacent house if of same color. what i understand from the DP is the following :- find minimum cost of coloring previous house with color t ( min(answer[i-1][t]) ) and add colorvalue[t] to it for finding minimum cost of coloring answer[i][j]. where t varies from 1 to k except j. - is taking care that ignore coloring house if it of same as colorvalue[t]. I dont see the above restriction of taken care of ... please explain and correct me if i am wrong. On Sun, Dec 15, 2013 at 9:47 AM, Saurabh Paliwal saurabh.paliwa...@gmail.com wrote: what is the issue with the usual recurrence :- Let answer[i][j] represent minimum cost of coloring i houses with ith house colored with jth color. answer[i][j] = min(answer[i-1][t]) + colorvalue[t] where t varies from 1 to k except j. initial setting :- answer[1][j] = colorvalue[j] final answer is min(answer[n][j]) for all j from 1 to k. Time complexity = O(n*k*k) Space complexity = O(k) if only 2 rows are taken ( effectively only 2 are required ). On Sun, Dec 15, 2013 at 12:44 AM, kumar raja rajkumar.cs...@gmail.comwrote: You have 'n' houses and 'k' colors. The cost of coloring a house with one of the 'k' colors is different from coloring another house with same color. The cost of coloring the house with different colors are different. So now how to colour the 'n' houses such that no two adjcent houses will get the same color and the total coloring cost for 'n' houses is minimized. Regards, Kumar Raja. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- -Saurabh Paliwal B-Tech. Comp. Science and Engg. IIT ROORKEE -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] coloring problem Dynamic programming
ohh shoots...my bad.got this condition wrong t varies from 1 to k except j. now got it :)..ignore my previous comment :) :) On Tue, Dec 17, 2013 at 11:47 PM, atul anand atul.87fri...@gmail.comwrote: @saurabh : answer[i][j] = min(answer[i-1][t]) + colorvalue[t] where t varies from 1 to k except j. how this DP is taking care of the case where no adjacent house if of same color. what i understand from the DP is the following :- find minimum cost of coloring previous house with color t ( min(answer[i-1][t]) ) and add colorvalue[t] to it for finding minimum cost of coloring answer[i][j]. where t varies from 1 to k except j. - is taking care that ignore coloring house if it of same as colorvalue[t]. I dont see the above restriction of taken care of ... please explain and correct me if i am wrong. On Sun, Dec 15, 2013 at 9:47 AM, Saurabh Paliwal saurabh.paliwa...@gmail.com wrote: what is the issue with the usual recurrence :- Let answer[i][j] represent minimum cost of coloring i houses with ith house colored with jth color. answer[i][j] = min(answer[i-1][t]) + colorvalue[t] where t varies from 1 to k except j. initial setting :- answer[1][j] = colorvalue[j] final answer is min(answer[n][j]) for all j from 1 to k. Time complexity = O(n*k*k) Space complexity = O(k) if only 2 rows are taken ( effectively only 2 are required ). On Sun, Dec 15, 2013 at 12:44 AM, kumar raja rajkumar.cs...@gmail.comwrote: You have 'n' houses and 'k' colors. The cost of coloring a house with one of the 'k' colors is different from coloring another house with same color. The cost of coloring the house with different colors are different. So now how to colour the 'n' houses such that no two adjcent houses will get the same color and the total coloring cost for 'n' houses is minimized. Regards, Kumar Raja. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- -Saurabh Paliwal B-Tech. Comp. Science and Engg. IIT ROORKEE -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] [Algogeeks] Longest increasing sub sequence length in linear time
can be done with nlogn i dont think so O(n) is possible... On 17 Dec 2013 01:30, bujji jajala jajalabu...@gmail.com wrote: Given an Array of integers (A1,A2,...,An) of length n, Find the maximum possible length of increasing sub sequence formed from A1, A2,,An. I read that it is possible to compute in linear time as mentioned in algorithm design manual bySkiena. -Thanks Bujji -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Re: Saving and restoring Binary trees in files
@Don : +1 ..got it ..thanks
On Wed, Nov 13, 2013 at 10:35 PM, Dave dave_and_da...@juno.com wrote:
@Don: Excellent solution. It requires little extra data to be stored, and
it is easy to implement.
Dave
On Wednesday, November 13, 2013 9:31:47 AM UTC-6, Don wrote:
The data file contains the pre-order traversal. For each node indicate
the contents of the node and two bits to indicate if it has a left and/or
right subtree. I did this with a tree containing strings. Each node was one
line in the file, with the first character being 'A' if the node is a leaf,
'B' if it has only a left subtree, 'C' if it has only a right subtree, and
'D' if it has both left and right subtrees. Then you read the line, store
the string minus the first character, and recursively build the left and
then right subtree, as appropriate.
Don
On Monday, November 11, 2013 1:20:05 PM UTC-5, atul007 wrote:
@don : i did not get it , what will be data in file?
On Mon, Nov 11, 2013 at 10:14 PM, Don dond...@gmail.com wrote:
Save in preorder, tagging each node with two bits indicating if that
node has a left and right subtree.
Then rebuild like this:
Tree rebuild()
{
Tree result = readNode();
Tree-left = hasLeftSubtree ? rebuild() : 0;
Tree-right = hasRightSubtree ? rebuild() : 0;
return result;
}
On Friday, November 8, 2013 1:00:35 PM UTC-5, atul007 wrote:
@don : it is not BST , it is binary tree ...so your approach will
not work in this case.
@kumar : save pre-order and in-order traversal with some delimiter in
b/w traversals.
pre-order : a b c d e
in-order : c b e a d
write in file :-
a b c d e # c b e a d
now use pre-order and in-order traversal to re-create binary tree.
2) consider null node as # ..now write in file preorder traversal.
for eg : a b c # # # d # #
3) save level order traversal of binary tree, where each level uses
# to distinguish between levels and * to mark null nodes
eg : a # b c # e *
a - level 1
b c - level 2
e NULL - level 3
shortcoming in 2 and 3 is use of character that can be part of tree
itself.So if node can contain # then you have to use some other
character to distinguish.
for solution 1 , you can write traversal in 2 lines instead of using
#
On 11/8/13, Vishnu vish...@gmail.com wrote:
1) save the nodes(value, left and right pointer) in pre-order
traversal
2) also save pointers of all node in same order
to restore
1) create new N nodes
2) do pointer mapping from old - new
3) restore nodes and replace old pointers to new
On Fri, Nov 8, 2013 at 8:50 PM, Don dond...@gmail.com wrote:
Save it in pre-order.
Rebuild by inserting nodes in the order they occur in the file.
On Friday, November 8, 2013 8:33:19 AM UTC-5, kumar raja wrote:
What is the effective way to save and restore the binary trees to
files
effectively?
Regards,
Kumar Raja.
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it,
send an
email to algogeeks+...@googlegroups.com.
--
Thanks,
Vishnu
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it,
send an
email to algogeeks+...@googlegroups.com.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send
an email to algogeeks+...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Re: Saving and restoring Binary trees in files
@don : i did not get it , what will be data in file?
On Mon, Nov 11, 2013 at 10:14 PM, Don dondod...@gmail.com wrote:
Save in preorder, tagging each node with two bits indicating if that node
has a left and right subtree.
Then rebuild like this:
Tree rebuild()
{
Tree result = readNode();
Tree-left = hasLeftSubtree ? rebuild() : 0;
Tree-right = hasRightSubtree ? rebuild() : 0;
return result;
}
On Friday, November 8, 2013 1:00:35 PM UTC-5, atul007 wrote:
@don : it is not BST , it is binary tree ...so your approach will
not work in this case.
@kumar : save pre-order and in-order traversal with some delimiter in
b/w traversals.
pre-order : a b c d e
in-order : c b e a d
write in file :-
a b c d e # c b e a d
now use pre-order and in-order traversal to re-create binary tree.
2) consider null node as # ..now write in file preorder traversal.
for eg : a b c # # # d # #
3) save level order traversal of binary tree, where each level uses
# to distinguish between levels and * to mark null nodes
eg : a # b c # e *
a - level 1
b c - level 2
e NULL - level 3
shortcoming in 2 and 3 is use of character that can be part of tree
itself.So if node can contain # then you have to use some other
character to distinguish.
for solution 1 , you can write traversal in 2 lines instead of using #
On 11/8/13, Vishnu vish...@gmail.com wrote:
1) save the nodes(value, left and right pointer) in pre-order traversal
2) also save pointers of all node in same order
to restore
1) create new N nodes
2) do pointer mapping from old - new
3) restore nodes and replace old pointers to new
On Fri, Nov 8, 2013 at 8:50 PM, Don dond...@gmail.com wrote:
Save it in pre-order.
Rebuild by inserting nodes in the order they occur in the file.
On Friday, November 8, 2013 8:33:19 AM UTC-5, kumar raja wrote:
What is the effective way to save and restore the binary trees to
files
effectively?
Regards,
Kumar Raja.
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send
an
email to algogeeks+...@googlegroups.com.
--
Thanks,
Vishnu
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send
an
email to algogeeks+...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Re: Saving and restoring Binary trees in files
@don : it is not BST , it is binary tree ...so your approach will not work in this case. @kumar : save pre-order and in-order traversal with some delimiter in b/w traversals. pre-order : a b c d e in-order : c b e a d write in file :- a b c d e # c b e a d now use pre-order and in-order traversal to re-create binary tree. 2) consider null node as # ..now write in file preorder traversal. for eg : a b c # # # d # # 3) save level order traversal of binary tree, where each level uses # to distinguish between levels and * to mark null nodes eg : a # b c # e * a - level 1 b c - level 2 e NULL - level 3 shortcoming in 2 and 3 is use of character that can be part of tree itself.So if node can contain # then you have to use some other character to distinguish. for solution 1 , you can write traversal in 2 lines instead of using # On 11/8/13, Vishnu vishnu...@gmail.com wrote: 1) save the nodes(value, left and right pointer) in pre-order traversal 2) also save pointers of all node in same order to restore 1) create new N nodes 2) do pointer mapping from old - new 3) restore nodes and replace old pointers to new On Fri, Nov 8, 2013 at 8:50 PM, Don dondod...@gmail.com wrote: Save it in pre-order. Rebuild by inserting nodes in the order they occur in the file. On Friday, November 8, 2013 8:33:19 AM UTC-5, kumar raja wrote: What is the effective way to save and restore the binary trees to files effectively? Regards, Kumar Raja. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- Thanks, Vishnu -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Message distribution through rooted tree dynamic programming
we can first count number of nodes in a subtree below each node.Now transfer message to max(count(root-left),count-root-right); On 11/1/13, kumar raja rajkumar.cs...@gmail.com wrote: Suppose we need to distribute a message to all the nodes in a rooted tree. Initially, only the root node knows the message. In a single round, any node that knows the message can forward it to at most one of its children. Design an algorithm to compute the minimum number of rounds required for the message to be delivered to all nodes. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] variation of LIS problem
using idea mentioned in below link , we can solve this similar problem
in O(n^2*k).
http://stackoverflow.com/questions/12862077/number-of-increasing-strings-of-length-k
On 10/26/13, atul anand atul.87fri...@gmail.com wrote:
@saurabh : i did not get ur algo...can you please explain with an example
On 26 Oct 2013 08:21, Saurabh Paliwal saurabh.paliwa...@gmail.com
wrote:
if all the elements are positive then we can reverse the array and
multiply all of them by -1. Now apply LIS algorithm O(nlog(n)) and since
it
gives the answer for all k=n with the minimum sum, this will be the
answer
multiplied by -1.
On Sat, Oct 26, 2013 at 12:12 AM, kumar raja
rajkumar.cs...@gmail.comwrote:
I think O(nlogn) solution is possible for this problem. First find the
largest increasing subsequence in O(nlogn) time.
http://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms
From this one u have LIS array M and parent array P. Now traverse
through
the array M and for all the length values = k , u can print the k
elements using Parent array P. I guess the step of printing the array
elements wont be greater than O(n logn).
So it is bounded by O(nlogn) . In the worst case it might go up to
O(n^2). But i am not sure of this.
On 25 October 2013 00:17, atul anand atul.87fri...@gmail.com wrote:
OK, i got now why you were using min-heap.
now consider this example :-
200,12,33,1,55,100
K=3
insert 200
12 200...cannot insert
33 200...cannot insert
.
.
.
100200 cannot insert
output : 200 (not lenght of k)
output should be : 33,55,100
On 10/24/13, pankaj joshi joshi10...@gmail.com wrote:
Max-heap should not used in this case,
why min heap? -- this is because program has to decide the smallest
element
in k-group.
in your example if i consider k =3 than
insert 1
insert 2
insert 5
insert 10
size of heap ==4 so delete root of min- heap (which is 1),
insert 100
30 cant insert because temp = 100 and 30temp
insert 8 cant insert temp = 100 and 8temp
(500temp)size of heap ==4 so delete root of min-heap(which is 2)
insert 555
now if i check the heap elements
{5, 10, 100 , 555}
On Thu, Oct 24, 2013 at 11:25 PM, atul anand
atul.87fri...@gmail.comwrote:
in your updated algo , you should be using max-heap not min-heap.
check your algo for :-
1,2,5,10,100,30,8,555
let me know if it work fine.If it is working fine then i need more
clarity of your algo
On 10/24/13, pankaj joshi joshi10...@gmail.com wrote:
@Saurabh:
As per the question the elements of sub-sequence should be
increasing,
so the solution will be {5} and as per the program.
* but as written longest sub-sequence of k =2, so it should be
{2,3}
for
this case. (there should be backtrack in this case.)
@atul: increasing sub sequence is checked by condition, not by
Min-heap,
but min heap is used for storing the largest elements.
So it is preferable DS,
On Thu, Oct 24, 2013 at 8:35 PM, atul anand
atul.87fri...@gmail.com
wrote:
@pankaj : how can you maintain increasing sub-sequence using
heapyour soln is for finding finding K largest element in the
array...so it wont work.
On 10/24/13, Saurabh Paliwal saurabh.paliwa...@gmail.com wrote:
check for {5,2,3} and K = 2.
On Thu, Oct 24, 2013 at 7:41 PM, pankaj joshi
joshi10...@gmail.com
wrote:
@ Saurabh,
I have done a correction on algo
temp =0
loop n to a[]
if a[i]temp
if min-heap(root) a[i]
if min-heap(count)==k
delete root in min- heap
inseart a[i] in min - heap
As i have made the condition: min-heap, (condition size should
be
always
k) for this particular case.
And in the example {5,2,1,10,9,30,8,55} if K =3
insert 5
2 is less so do nothing
1 is less so do nothing
insert 10
9 is less so do nothing
insert 30
8 is less so do nothing
insert 55 (before inserting 50 delete the root of heap as
count
of
heap
==
3), deleted root was - 5
so the output will be
{10,30,55}
and if k is 4
than
{5, 10, 30 , 55)
On Thu, Oct 24, 2013 at 6:20 PM, Saurabh Paliwal
saurabh.paliwa...@gmail.com wrote:
You must be mistaken in the definition of heaps, or maybe the
question,
look at the updated question I put up there.
On Thu, Oct 24, 2013 at 5:48 PM, pankaj joshi
joshi10...@gmail.comwrote:
hi all,
nlog(k) is the solution i think.
can anyone suggest more optimal?
solution:
create a min-heap, (condition size should be always k)
temp =0
loop n to a[]
if a[i]temp
if min-heap(root) a[i]
delete root in min- heap
inseart a[i] in min - heap
at the end of main loop the min-heap will contain the final
sequence.
On Thu, Oct 24, 2013 at 8
Re: [algogeeks] variation of LIS problem
@saurabh : i did not get ur algo...can you please explain with an example
On 26 Oct 2013 08:21, Saurabh Paliwal saurabh.paliwa...@gmail.com wrote:
if all the elements are positive then we can reverse the array and
multiply all of them by -1. Now apply LIS algorithm O(nlog(n)) and since it
gives the answer for all k=n with the minimum sum, this will be the answer
multiplied by -1.
On Sat, Oct 26, 2013 at 12:12 AM, kumar raja rajkumar.cs...@gmail.comwrote:
I think O(nlogn) solution is possible for this problem. First find the
largest increasing subsequence in O(nlogn) time.
http://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms
From this one u have LIS array M and parent array P. Now traverse through
the array M and for all the length values = k , u can print the k
elements using Parent array P. I guess the step of printing the array
elements wont be greater than O(n logn).
So it is bounded by O(nlogn) . In the worst case it might go up to
O(n^2). But i am not sure of this.
On 25 October 2013 00:17, atul anand atul.87fri...@gmail.com wrote:
OK, i got now why you were using min-heap.
now consider this example :-
200,12,33,1,55,100
K=3
insert 200
12 200...cannot insert
33 200...cannot insert
.
.
.
100200 cannot insert
output : 200 (not lenght of k)
output should be : 33,55,100
On 10/24/13, pankaj joshi joshi10...@gmail.com wrote:
Max-heap should not used in this case,
why min heap? -- this is because program has to decide the smallest
element
in k-group.
in your example if i consider k =3 than
insert 1
insert 2
insert 5
insert 10
size of heap ==4 so delete root of min- heap (which is 1),
insert 100
30 cant insert because temp = 100 and 30temp
insert 8 cant insert temp = 100 and 8temp
(500temp)size of heap ==4 so delete root of min-heap(which is 2)
insert 555
now if i check the heap elements
{5, 10, 100 , 555}
On Thu, Oct 24, 2013 at 11:25 PM, atul anand
atul.87fri...@gmail.comwrote:
in your updated algo , you should be using max-heap not min-heap.
check your algo for :-
1,2,5,10,100,30,8,555
let me know if it work fine.If it is working fine then i need more
clarity of your algo
On 10/24/13, pankaj joshi joshi10...@gmail.com wrote:
@Saurabh:
As per the question the elements of sub-sequence should be
increasing,
so the solution will be {5} and as per the program.
* but as written longest sub-sequence of k =2, so it should be {2,3}
for
this case. (there should be backtrack in this case.)
@atul: increasing sub sequence is checked by condition, not by
Min-heap,
but min heap is used for storing the largest elements.
So it is preferable DS,
On Thu, Oct 24, 2013 at 8:35 PM, atul anand
atul.87fri...@gmail.com
wrote:
@pankaj : how can you maintain increasing sub-sequence using
heapyour soln is for finding finding K largest element in the
array...so it wont work.
On 10/24/13, Saurabh Paliwal saurabh.paliwa...@gmail.com wrote:
check for {5,2,3} and K = 2.
On Thu, Oct 24, 2013 at 7:41 PM, pankaj joshi
joshi10...@gmail.com
wrote:
@ Saurabh,
I have done a correction on algo
temp =0
loop n to a[]
if a[i]temp
if min-heap(root) a[i]
if min-heap(count)==k
delete root in min- heap
inseart a[i] in min - heap
As i have made the condition: min-heap, (condition size should
be
always
k) for this particular case.
And in the example {5,2,1,10,9,30,8,55} if K =3
insert 5
2 is less so do nothing
1 is less so do nothing
insert 10
9 is less so do nothing
insert 30
8 is less so do nothing
insert 55 (before inserting 50 delete the root of heap as count
of
heap
==
3), deleted root was - 5
so the output will be
{10,30,55}
and if k is 4
than
{5, 10, 30 , 55)
On Thu, Oct 24, 2013 at 6:20 PM, Saurabh Paliwal
saurabh.paliwa...@gmail.com wrote:
You must be mistaken in the definition of heaps, or maybe the
question,
look at the updated question I put up there.
On Thu, Oct 24, 2013 at 5:48 PM, pankaj joshi
joshi10...@gmail.comwrote:
hi all,
nlog(k) is the solution i think.
can anyone suggest more optimal?
solution:
create a min-heap, (condition size should be always k)
temp =0
loop n to a[]
if a[i]temp
if min-heap(root) a[i]
delete root in min- heap
inseart a[i] in min - heap
at the end of main loop the min-heap will contain the final
sequence.
On Thu, Oct 24, 2013 at 8:50 AM, atul anand
atul.87fri...@gmail.comwrote:
@Saurabh Paliwal : yes
On 10/24/13, Saurabh Paliwal saurabh.paliwa...@gmail.com
wrote:
Do you mean
*of all the increasing subsequences of length k
Re: [algogeeks] variation of LIS problem
@pankaj : how can you maintain increasing sub-sequence using
heapyour soln is for finding finding K largest element in the
array...so it wont work.
On 10/24/13, Saurabh Paliwal saurabh.paliwa...@gmail.com wrote:
check for {5,2,3} and K = 2.
On Thu, Oct 24, 2013 at 7:41 PM, pankaj joshi joshi10...@gmail.com wrote:
@ Saurabh,
I have done a correction on algo
temp =0
loop n to a[]
if a[i]temp
if min-heap(root) a[i]
if min-heap(count)==k
delete root in min- heap
inseart a[i] in min - heap
As i have made the condition: min-heap, (condition size should be always
k) for this particular case.
And in the example {5,2,1,10,9,30,8,55} if K =3
insert 5
2 is less so do nothing
1 is less so do nothing
insert 10
9 is less so do nothing
insert 30
8 is less so do nothing
insert 55 (before inserting 50 delete the root of heap as count of heap
==
3), deleted root was - 5
so the output will be
{10,30,55}
and if k is 4
than
{5, 10, 30 , 55)
On Thu, Oct 24, 2013 at 6:20 PM, Saurabh Paliwal
saurabh.paliwa...@gmail.com wrote:
You must be mistaken in the definition of heaps, or maybe the question,
look at the updated question I put up there.
On Thu, Oct 24, 2013 at 5:48 PM, pankaj joshi
joshi10...@gmail.comwrote:
hi all,
nlog(k) is the solution i think.
can anyone suggest more optimal?
solution:
create a min-heap, (condition size should be always k)
temp =0
loop n to a[]
if a[i]temp
if min-heap(root) a[i]
delete root in min- heap
inseart a[i] in min - heap
at the end of main loop the min-heap will contain the final sequence.
On Thu, Oct 24, 2013 at 8:50 AM, atul anand
atul.87fri...@gmail.comwrote:
@Saurabh Paliwal : yes
On 10/24/13, Saurabh Paliwal saurabh.paliwa...@gmail.com wrote:
Do you mean
*of all the increasing subsequences of length k in this array, find
the one
with maximum sum ?*
On Wed, Oct 23, 2013 at 10:52 PM, atul anand
atul.87fri...@gmail.comwrote:
Given an array with N elements and integer K . Find sum of longest
increasing sub-sequence of length K elements such that
sub-sequence
found
is maximum among all K max su-sequence.
Eg arr[]={5,2,1,10,9,30,8,55}
K = 3
output : 10,30,55sum = 10+30+55 = 95
if K=4
output : 5,10,30,55 sum = 5+10+30+55 =100
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it,
send an
email to algogeeks+unsubscr...@googlegroups.com.
--
-Saurabh Paliwal
B-Tech. Comp. Science and Engg.
IIT ROORKEE
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it,
send an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send
an email to algogeeks+unsubscr...@googlegroups.com.
--
Regards,
Pankaj Kumar Joshi
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send
an email to algogeeks+unsubscr...@googlegroups.com.
--
-Saurabh Paliwal
B-Tech. Comp. Science and Engg.
IIT ROORKEE
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send
an
email to algogeeks+unsubscr...@googlegroups.com.
--
Regards,
Pankaj Kumar Joshi
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
-Saurabh Paliwal
B-Tech. Comp. Science and Engg.
IIT ROORKEE
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] variation of LIS problem
in your updated algo , you should be using max-heap not min-heap.
check your algo for :-
1,2,5,10,100,30,8,555
let me know if it work fine.If it is working fine then i need more
clarity of your algo
On 10/24/13, pankaj joshi joshi10...@gmail.com wrote:
@Saurabh:
As per the question the elements of sub-sequence should be increasing,
so the solution will be {5} and as per the program.
* but as written longest sub-sequence of k =2, so it should be {2,3} for
this case. (there should be backtrack in this case.)
@atul: increasing sub sequence is checked by condition, not by Min-heap,
but min heap is used for storing the largest elements.
So it is preferable DS,
On Thu, Oct 24, 2013 at 8:35 PM, atul anand atul.87fri...@gmail.com
wrote:
@pankaj : how can you maintain increasing sub-sequence using
heapyour soln is for finding finding K largest element in the
array...so it wont work.
On 10/24/13, Saurabh Paliwal saurabh.paliwa...@gmail.com wrote:
check for {5,2,3} and K = 2.
On Thu, Oct 24, 2013 at 7:41 PM, pankaj joshi joshi10...@gmail.com
wrote:
@ Saurabh,
I have done a correction on algo
temp =0
loop n to a[]
if a[i]temp
if min-heap(root) a[i]
if min-heap(count)==k
delete root in min- heap
inseart a[i] in min - heap
As i have made the condition: min-heap, (condition size should be
always
k) for this particular case.
And in the example {5,2,1,10,9,30,8,55} if K =3
insert 5
2 is less so do nothing
1 is less so do nothing
insert 10
9 is less so do nothing
insert 30
8 is less so do nothing
insert 55 (before inserting 50 delete the root of heap as count of
heap
==
3), deleted root was - 5
so the output will be
{10,30,55}
and if k is 4
than
{5, 10, 30 , 55)
On Thu, Oct 24, 2013 at 6:20 PM, Saurabh Paliwal
saurabh.paliwa...@gmail.com wrote:
You must be mistaken in the definition of heaps, or maybe the
question,
look at the updated question I put up there.
On Thu, Oct 24, 2013 at 5:48 PM, pankaj joshi
joshi10...@gmail.comwrote:
hi all,
nlog(k) is the solution i think.
can anyone suggest more optimal?
solution:
create a min-heap, (condition size should be always k)
temp =0
loop n to a[]
if a[i]temp
if min-heap(root) a[i]
delete root in min- heap
inseart a[i] in min - heap
at the end of main loop the min-heap will contain the final
sequence.
On Thu, Oct 24, 2013 at 8:50 AM, atul anand
atul.87fri...@gmail.comwrote:
@Saurabh Paliwal : yes
On 10/24/13, Saurabh Paliwal saurabh.paliwa...@gmail.com wrote:
Do you mean
*of all the increasing subsequences of length k in this array,
find
the one
with maximum sum ?*
On Wed, Oct 23, 2013 at 10:52 PM, atul anand
atul.87fri...@gmail.comwrote:
Given an array with N elements and integer K . Find sum of
longest
increasing sub-sequence of length K elements such that
sub-sequence
found
is maximum among all K max su-sequence.
Eg arr[]={5,2,1,10,9,30,8,55}
K = 3
output : 10,30,55sum = 10+30+55 = 95
if K=4
output : 5,10,30,55 sum = 5+10+30+55 =100
--
You received this message because you are subscribed to the
Google
Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from
it,
send an
email to algogeeks+unsubscr...@googlegroups.com.
--
-Saurabh Paliwal
B-Tech. Comp. Science and Engg.
IIT ROORKEE
--
You received this message because you are subscribed to the
Google
Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it,
send an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it,
send
an email to algogeeks+unsubscr...@googlegroups.com.
--
Regards,
Pankaj Kumar Joshi
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it,
send
an email to algogeeks+unsubscr...@googlegroups.com.
--
-Saurabh Paliwal
B-Tech. Comp. Science and Engg.
IIT ROORKEE
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it,
send
an
email to algogeeks+unsubscr...@googlegroups.com.
--
Regards,
Pankaj Kumar Joshi
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send
an
email to algogeeks+unsubscr...@googlegroups.com
Re: [algogeeks] variation of LIS problem
OK, i got now why you were using min-heap.
now consider this example :-
200,12,33,1,55,100
K=3
insert 200
12 200...cannot insert
33 200...cannot insert
.
.
.
100200 cannot insert
output : 200 (not lenght of k)
output should be : 33,55,100
On 10/24/13, pankaj joshi joshi10...@gmail.com wrote:
Max-heap should not used in this case,
why min heap? -- this is because program has to decide the smallest element
in k-group.
in your example if i consider k =3 than
insert 1
insert 2
insert 5
insert 10
size of heap ==4 so delete root of min- heap (which is 1),
insert 100
30 cant insert because temp = 100 and 30temp
insert 8 cant insert temp = 100 and 8temp
(500temp)size of heap ==4 so delete root of min-heap(which is 2)
insert 555
now if i check the heap elements
{5, 10, 100 , 555}
On Thu, Oct 24, 2013 at 11:25 PM, atul anand
atul.87fri...@gmail.comwrote:
in your updated algo , you should be using max-heap not min-heap.
check your algo for :-
1,2,5,10,100,30,8,555
let me know if it work fine.If it is working fine then i need more
clarity of your algo
On 10/24/13, pankaj joshi joshi10...@gmail.com wrote:
@Saurabh:
As per the question the elements of sub-sequence should be increasing,
so the solution will be {5} and as per the program.
* but as written longest sub-sequence of k =2, so it should be {2,3}
for
this case. (there should be backtrack in this case.)
@atul: increasing sub sequence is checked by condition, not by
Min-heap,
but min heap is used for storing the largest elements.
So it is preferable DS,
On Thu, Oct 24, 2013 at 8:35 PM, atul anand atul.87fri...@gmail.com
wrote:
@pankaj : how can you maintain increasing sub-sequence using
heapyour soln is for finding finding K largest element in the
array...so it wont work.
On 10/24/13, Saurabh Paliwal saurabh.paliwa...@gmail.com wrote:
check for {5,2,3} and K = 2.
On Thu, Oct 24, 2013 at 7:41 PM, pankaj joshi joshi10...@gmail.com
wrote:
@ Saurabh,
I have done a correction on algo
temp =0
loop n to a[]
if a[i]temp
if min-heap(root) a[i]
if min-heap(count)==k
delete root in min- heap
inseart a[i] in min - heap
As i have made the condition: min-heap, (condition size should be
always
k) for this particular case.
And in the example {5,2,1,10,9,30,8,55} if K =3
insert 5
2 is less so do nothing
1 is less so do nothing
insert 10
9 is less so do nothing
insert 30
8 is less so do nothing
insert 55 (before inserting 50 delete the root of heap as count of
heap
==
3), deleted root was - 5
so the output will be
{10,30,55}
and if k is 4
than
{5, 10, 30 , 55)
On Thu, Oct 24, 2013 at 6:20 PM, Saurabh Paliwal
saurabh.paliwa...@gmail.com wrote:
You must be mistaken in the definition of heaps, or maybe the
question,
look at the updated question I put up there.
On Thu, Oct 24, 2013 at 5:48 PM, pankaj joshi
joshi10...@gmail.comwrote:
hi all,
nlog(k) is the solution i think.
can anyone suggest more optimal?
solution:
create a min-heap, (condition size should be always k)
temp =0
loop n to a[]
if a[i]temp
if min-heap(root) a[i]
delete root in min- heap
inseart a[i] in min - heap
at the end of main loop the min-heap will contain the final
sequence.
On Thu, Oct 24, 2013 at 8:50 AM, atul anand
atul.87fri...@gmail.comwrote:
@Saurabh Paliwal : yes
On 10/24/13, Saurabh Paliwal saurabh.paliwa...@gmail.com
wrote:
Do you mean
*of all the increasing subsequences of length k in this array,
find
the one
with maximum sum ?*
On Wed, Oct 23, 2013 at 10:52 PM, atul anand
atul.87fri...@gmail.comwrote:
Given an array with N elements and integer K . Find sum of
longest
increasing sub-sequence of length K elements such that
sub-sequence
found
is maximum among all K max su-sequence.
Eg arr[]={5,2,1,10,9,30,8,55}
K = 3
output : 10,30,55sum = 10+30+55 = 95
if K=4
output : 5,10,30,55 sum = 5+10+30+55 =100
--
You received this message because you are subscribed to the
Google
Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from
it,
send an
email to algogeeks+unsubscr...@googlegroups.com.
--
-Saurabh Paliwal
B-Tech. Comp. Science and Engg.
IIT ROORKEE
--
You received this message because you are subscribed to the
Google
Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from
it,
send an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the
Google
Groups Algorithm Geeks
[algogeeks] variation of LIS problem
Given an array with N elements and integer K . Find sum of longest
increasing sub-sequence of length K elements such that sub-sequence found
is maximum among all K max su-sequence.
Eg arr[]={5,2,1,10,9,30,8,55}
K = 3
output : 10,30,55sum = 10+30+55 = 95
if K=4
output : 5,10,30,55 sum = 5+10+30+55 =100
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] variation of LIS problem
@Saurabh Paliwal : yes
On 10/24/13, Saurabh Paliwal saurabh.paliwa...@gmail.com wrote:
Do you mean
*of all the increasing subsequences of length k in this array, find the one
with maximum sum ?*
On Wed, Oct 23, 2013 at 10:52 PM, atul anand
atul.87fri...@gmail.comwrote:
Given an array with N elements and integer K . Find sum of longest
increasing sub-sequence of length K elements such that sub-sequence
found
is maximum among all K max su-sequence.
Eg arr[]={5,2,1,10,9,30,8,55}
K = 3
output : 10,30,55sum = 10+30+55 = 95
if K=4
output : 5,10,30,55 sum = 5+10+30+55 =100
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
-Saurabh Paliwal
B-Tech. Comp. Science and Engg.
IIT ROORKEE
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Breaking a string problem (Dynamic programming)
Question seems similar to matrix chain multiplication problemhere you need to find min cost.. Recurrence for this could be the following , please validate it. DP(i,j) = j + (j - i) * min( DP(i , k) , DP(k, j) ) for all i k j i j On Sat, Oct 12, 2013 at 12:54 PM, kumar raja rajkumar.cs...@gmail.comwrote: I was not able to figure out the solution to the problem in CLRS book. A certain string-processing language offers a primitive operation which splits a string into two pieces. Since this operation involves copying the original string, it takes n units of time for a string of length n, regardless of the location of the cut. Suppose, now, that you want to break a string into many pieces. The order in which the breaks are made can affect the total running time. For example, if you want to cut a 20-character string at positions 3 and 10 (say size of this set is k), then making the first cut at position 3 incurs a total cost of 20+17=37, while doing position 10 first has a better cost of 20+10=30. So the task is to find out which sequence gives the minimum cost and what is that sequence out of k! possible sequences. I have seen the solutions in stack overflow using divide and conquer, but i would like to know how to solve this problem using DP. Someother solutions in the web shows it can be solved in O(n^3) or O(n^2) but no where i have seen the sub problem(Optimal substructure) defined. I was not able to identify sub problems and make a recurrence relation out of it.Can someone please throw light on this? I just want to develop approach to solve the DP problems. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Generating random number without using rand()
Hello, Given integer N , How to generate random number from 0 to N without using rand() function. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Find the max element of sets of size K
question is different...here we have to find max of k elements in the
window..not max subarry of size kfoe eg input is say ... 1 4 5 66 7 9
and k=3
then output should be
(1,4,5) = 5
(4,5,66) = 66
(5,66,7)=66
(66,7,9)=66
output - 5,66,66,66
On 19 Sep 2013 19:00, igor.b...@gmail.com igor.b...@gmail.com wrote:
Hey, isn't it as simple as:
1. Start at sum of the first K elements.
2. Move the window of size K by one element to the right at each step.
Subtract the left, add the right = get the new sum. Keep the maximum.
This executes in O(n) steps, requires O(1) memory. The code in C++ seems
to be trivial:
pairint, int max_k(int a[], int n) {
int sum_k = accumulate(a, a+k, 0);
int max_sum = sum_k, max_id = 0;
for (int i = k; i n; ++i) {
sum_k = sum_k - a[i - k] + a[i];
if (sum_k max_sum) {
max_sum = sum_k;
max_id = i - k + 1;
}
}
return make_pair(max_id, max_sum);
}
... or do I miss something?
On Wednesday, September 11, 2013 7:14:24 AM UTC-4, kumar raja wrote:
I heard there exists a O(n) algorithm in DP? Does anyone has the idea
about it?
On 11 September 2013 03:21, Aaquib Javed aaqui...@gmail.com wrote:
http://www.geeksforgeeks.org/maximum-of-all-subarrays-of-size-k/
On Tue, Sep 10, 2013 at 11:46 PM, kumar raja rajkuma...@gmail.com
wrote:
suppose we have n numbers and k =n.
Then a1,a2... ak is one set.
then a2,a3 ak+1 is other set.
...
so totally we can have n-k+1 sets.
how to figure out the maximum elements of all these k size sets with
least possible time complexity and space complexity?
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send
an email to algogeeks+...@googlegroups.com.
--
Aaquib Javed
B.Tech. Final Year
Electronics Comm Engineering
MNNIT Allahabad.
+91-8953519834
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send
an email to algogeeks+...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] determine if 2 BSTs will be identical or not based on input order of its keys
http://www.geeksforgeeks.org/check-for-identical-bsts-without-building-the-trees/ On Thu, Jun 6, 2013 at 11:27 AM, Sambhavna Singh coolsambha...@gmail.comwrote: I came across this question on careercup: how do we go about finding whether the BSTs formed by the given input order would be identical or not without actually forming the tree? Link: http://www.careercup.com/question?id=19016700 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] amazon f2f round question ..
@karthikeyan : It is an acyclic graph not a binary tree. your solution
will work if given graph is a binary tree.
problem can be solved using dfs as suggested above
On 5/11/13, Karthikeyan V.B kartmu...@gmail.com wrote:
Since it is an acyclic graph, find the appropriate node that can be the
root of this tree.
Now apply the logic to find the diameter of the tree here, which finds the
longest path in the graph as follows:
int diameter(Tree * t) { if (t == 0) return 0; int lheight =
height(tree-left); int rheight = height(tree-right); int ldiameter =
diameter(tree-left); int rdiameter = diameter(tree-right); return
max(lheight + rheight + 1, max(ldiameter,rdiameter)); }
int height(Tree * t)
{
if (t == 0)
{ return 0; } else { return 1 + max(height(t-left),height(t-right)); } }
On Sat, May 11, 2013 at 10:59 PM, Aman Jain pureama...@gmail.com wrote:
In a connected and acyclic graph,that is a tree, we can apply this
approach
1. apply *dfs *on any random node and find the longest distant node from
this node.Let us say this node i*s u*.
2. from this no*de u*, again apply* dfs* to find longest distant node
from this node.Let us say that node is v.
(u,v) is the required pair of nodes.
On Sat, May 11, 2013 at 7:16 PM, MAC macatad...@gmail.com wrote:
Given an acyclic graph. Give an algorithm to find the pair of nodes
which
has the maximum distance between them, i.e. the maximum number of edges
in
between them
any suggestion ?
thanks
--mac
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send
an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] amazon f2f round question ..
@Karthikeyan : Given graph is directed and does not carry edge
weight.So you cannot use pris/kruskal algo to convert them to
tree.Even if you tweak prism/krukal algo to form a tree , you can
never guarantee that each node will have only 2 child , it can have
more than 2 children.So your terminology of using t-.left and t-right
wont work here.nevertheless it will fail for simple cases mentioned
below :-
given graph :-
(a)-(b)
(a)-(c)
(b)-(c)
output should be (a) - (b) -(c)
now to convert into tree as you have mentioned above you have to
remove edge (b)-(c).
so output will be (a)-(b) or (a)-(c)
which is wrong.
On 5/12/13, Karthikeyan V.B kartmu...@gmail.com wrote:
@atul anand : acyclic graph can be converted to a tree using prim/kruskal
or by finding an appropriate node that can act like the root of a tree
On Sun, May 12, 2013 at 5:55 PM, atul anand atul.87fri...@gmail.com
wrote:
@karthikeyan : It is an acyclic graph not a binary tree. your solution
will work if given graph is a binary tree.
problem can be solved using dfs as suggested above
On 5/11/13, Karthikeyan V.B kartmu...@gmail.com wrote:
Since it is an acyclic graph, find the appropriate node that can be the
root of this tree.
Now apply the logic to find the diameter of the tree here, which finds
the
longest path in the graph as follows:
int diameter(Tree * t) { if (t == 0) return 0; int lheight =
height(tree-left); int rheight = height(tree-right); int ldiameter =
diameter(tree-left); int rdiameter = diameter(tree-right); return
max(lheight + rheight + 1, max(ldiameter,rdiameter)); }
int height(Tree * t)
{
if (t == 0)
{ return 0; } else { return 1 + max(height(t-left),height(t-right));
}
}
On Sat, May 11, 2013 at 10:59 PM, Aman Jain pureama...@gmail.com
wrote:
In a connected and acyclic graph,that is a tree, we can apply this
approach
1. apply *dfs *on any random node and find the longest distant node
from
this node.Let us say this node i*s u*.
2. from this no*de u*, again apply* dfs* to find longest distant node
from this node.Let us say that node is v.
(u,v) is the required pair of nodes.
On Sat, May 11, 2013 at 7:16 PM, MAC macatad...@gmail.com wrote:
Given an acyclic graph. Give an algorithm to find the pair of nodes
which
has the maximum distance between them, i.e. the maximum number of
edges
in
between them
any suggestion ?
thanks
--mac
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it,
send
an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send
an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send
an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Re: Find the number of islands/connected components
{*1*,* 1*, 0, 0, 0},
{0, *1*, 0, 0, *1*},
{*1*, 0, 0, *1*, *1*},
{0, 0, 0, 0, 0},
{*1*, 0, *1*, 0, *1*}
above different set of color represent different island.Simple DFS is
used to find all the island
On Fri, Apr 26, 2013 at 3:11 AM, Don dondod...@gmail.com wrote:
The complexity is still O(ROWS*COLS) because each location in the
matrix will be visited once by the loop and once by DFS. Once a
location has been visited by DFS, it is marked as visited and can't be
visited again.
Don
On Apr 25, 5:11 pm, rahul sharma rahul23111...@gmail.com wrote:
What will be complexity if all elements in matrix are 1..
when first dfs will call then all matrix will be scanned setting each
element to visited...
then again loop contiues to scan all the elements..plz explain
On Thu, Apr 11, 2013 at 2:04 AM, rahul sharma rahul23111...@gmail.com
wrote:
{*1*,* 1*, 0, 0, 0},
{0, *1*, 0, 0, *1*},
{*1*, 0, 0, *1*, *1*},
{0, 0, 0, 0, 0},
{*1*, 0, *1*, 0, *1*}
Can anybody eplain how there are 5 islands in above matrix..thnx in
advance
source:-http://www.geeksforgeeks.org/find-number-of-islands/
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks]
//code sketch
row_len=R;
col_len=C;
r_start=0,col_start=0;
while (x R*C)
{
for i=r_start to col_len
keep extracting value from 1D and add it to mat[r_start][i]=arr[p++];
r_start++;
for i=r_start to row_len
keep extracting value from 1D and add it to mat[i][col_len]=arr[p++];
col_len--;
for( i=col_len;i=col_start;i--)
keep extracting value from 1D and add it to mat[row_len][i]=arr[p++];
row_len--;
for( i=row_len ; i =r_start;i--)
keep extracting value from 1D and add it to
mat[i][col_start]=arr[p++];
col_start++;
}
keep on running above 4 loops till R*C times .
note : take care of 1D array bound , if all values are consumed then fill
with zero , add this checking in every loop.
On Thu, Apr 18, 2013 at 12:34 PM, w.s miller wentworth.miller6...@gmail.com
wrote:
given a 1D array.The task is to convert it in to a 2D array and values
should be filled spirally while filling from 1D array
the size of 1D array is multiple of a constant say n.
the number of rows and columns of 2D array will be given.
say number of rows =R
say number of columns = C
k*n = R*C. where k*n =number of elements in 1D array
if (R*C number of elements in 1D array)
then rest of the values will be zeros.
e.g.
n=5; k=3
R= 6
C= 3
input 1D array=[1,0,0,0,1,0,0,0,0,0,1,1,1,1,0]
output 2D array
1 0 0 0 1 0
1 0 0 0 0 0
1 1 1 0 0 0
here as 5*36*3 so ..18 -15 = 3
i.e 3 remaining values are filled as zeros.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] [Algorithm] Get Target
are we allowed to use operation only once or multilpe times? On Fri, Mar 22, 2013 at 6:27 AM, prankur gupta duke.lnm...@gmail.comwrote: Hi All, Could you help me this question. This was asked at Yelp Interview. Given 6 integers and 1 target value, write a function to get the target value using 6 integers with any on these operations +,*,-,/ Thanks -- PRANKUR GUPTA Masters Student (CSE) State University of New York Stony Brook University prgu...@cs.stonybrook.edu -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Re: Median in stream of running integers
@rahul : yes
On 3/24/13, rahul sharma rahul23111...@gmail.com wrote:
So we need to implement prelocate down for deletion?
On Sunday, March 24, 2013, atul anand atul.87fri...@gmail.com wrote:
yeah implementation is wrong.
On 3/24/13, tec technic@gmail.com wrote:
The heap implementation is wrong to only prelocate up on deletion top.
15
/\
14 13
/ \/ \
1211109
/\/\/\/\
8 7 6 5 4 3 2 1
For example, for the above heap, when deleteTop is called, 1 is moved to
top, and heaplify is called on node 9, which does nothing and leave the
heap in an invalid state.
Comapring l and r child to find maximum/minimum is only needed in
prelocate
down, not in prelocate up.
2013/3/24 rahul sharma rahul23111...@gmail.com
And also in heapify y we r not comapring l and r chid to find maximum?
On Sun, Mar 24, 2013 at 6:07 PM, rahul sharma
rahul23111...@gmail.comwrote:
I was goin thorugh question on this link
http://www.geeksforgeeks.org/median-of-stream-of-integers-running-integers/
My doubt is y we uses prelocate up in case of deletion also.In
deletion
we use pre locate down.But y here we used pre locate up..plz
xplain.thnx
in
advance
// Heapification
// Note that, for the current median tracing problem
// we need to heapify only towards root, always
void heapify(int i)
{
int p = parent(i);
// comp - differentiate MaxHeap and MinHeap
// percolates up
if( p = 0 comp(A[i], A[p]) )
{
Exch(A[i], A[p]);
heapify(p);
}
}
int deleteTop()
{
int del = -1;
if( heapSize -1)
{
del = A[0];
Exch(A[0], A[heapSize]);
heapSize--;
heapify(parent(heapSize+1));
}
return del;
}
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send
an
email to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
--
__
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send
an
email to algogeeks+unsubscr...@googlegroups.com.
For more options, visit
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] FInd unique element.
use hashmap On Fri, Feb 22, 2013 at 12:58 AM, marti amritsa...@gmail.com wrote: How do I Find the Unique Element that Appears exactly k Times in an Array? the problem is given an integer array, only one integer appears* k* times, all the other integers appears *m* times in the array (*k**m*). Find out that integer. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Question
related to this problem, link given below :- http://groups.google.com/group/algogeeks/browse_thread/thread/7cfb0a6f7d121d92/0adc692fad1bab40?hl=enlnk=gstq=DP+equation+for+interval+problem#0adc692fad1bab40 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Pointers Usage
@shady : It allows us to allocate m/m dynamically ..which in itself is very big advantage. m/m consumption can be ignored , if you compare with the flexibility it provides. eg:- int *arr=(int *)malloc(sizeof(int) * 100); now m/m consumption here is 100*4+8;// extra 8 wont hurt if you compare with the advantage. another advantage:- suppose dere are 1000 integer value stored in m/m...a1,a2,a3,a4a100...now among all these only one is active at a particular time T. now to make it more interesting,suppose multiple threads want to find which one is active at a particular time T. it would be better if we have int *active pointer. now anyone among a1,a2,a3a100 becomes active then we store its address to *active.All threads now just need to synchronize and check *active pointer to find which one is active at a particular time T among a1,a2,a3...a10 instead of checking each variable which is time consuming and may corrupt at some time. I hope it helps. now suppose mutiple threads are accessing sam --
Re: [algogeeks] Trie Implementaion Issues
executed your code..working fine by commenting cmnt2 and un-commenting cmnt1 --
Re: [algogeeks] Re: Coin denomination
It can be solved using DP here is the recurrence eqn:- coin[ i ] = 1+coin[ i - denom( j ) ] if i =1 and 1 j ArrayLen(denom) base cases :- c[ i ]= inf if j 0 c[ i ] = 0 if j==0 On 12/23/12, Dave dave_and_da...@juno.com wrote: @Shady. That still didn't answer my question. Maybe I didn't frame it very well, so let me try again. Are you naming coins that you have one of or an infinite supply of? I.e., if you want to use two of a coin to make a certain sum, does it count in the N as one coin or two? More specifically, if I want to make 7 as (5,1,1), do I list the coins as (1,5), which is N=2, or (1,1,5), which is N=3? Dave On Saturday, December 22, 2012 4:34:24 AM UTC-6, shady wrote: We have *all kinds of denominations (1, 2, 3, R)*... therefore to cover this range, we generally select coins like this 1, 2, 4, 8, 16... but in this case... we can select* any N coins from R*, such that it *minimizes the average coins used for all values in the range R*... like . 6 can be represented by 2, 4 15 - (1, 2, 4, 8) 10 - (2, 8) On Sat, Dec 22, 2012 at 1:59 PM, Dave dave_an...@juno.com javascript:wrote: @Shady: I'm not sure what you mean by output N coins. With U.S. coins, you can need up to 4 pennies, 1 nickel, 2 dimes, 1 quarter, and 1 half-dollar (or 4 pennies, 1 nickel, 2 dimes, and 3 quarters, if you don't use half-dollars, which are uncommon) to make any amount from 1 to 99 cents. So should you output distinct coins (1,5,10,25,50), or repeat the coins the required number of times (1,1,1,1,5,10,10,25,50)? Dave On Friday, December 21, 2012 4:01:52 PM UTC-6, shady wrote: Given R and N, output N coins in the range from 1 to R such that average number of coins needed to represent all the number in the range is minimized. Any idea ? hints ? -- -- --
Re: [algogeeks] Re: Coin denomination
correction above :-
It can be solved using DP
here is the recurrence eqn:-
coin[ i ] = 1+ min{ coin[ i - denom( j ) ] } if i =1 and 1 j ArrayLen(denom)
base cases :- c[ i ]= inf if i 0
c[ i ] = 0 if i==0
--
Re: [algogeeks] Sieve
i had implemented Sieve of Eratosthenes long time back...
what i did was the following :-
say N is the range and we want to find all prime number within this range.
take size of temp array[] to half = N/2...as we only care of odd
numbers.Prime number 2 can be handled explicitly.
run outer loop for
for(i=3 ; i(sqrt(N))/2;i=i+2) // consider only odd i
{
for(j=i^2; (j/2) N/2 ; j+= i*2) // here I am excluding even multiple
of j by incrementing it by 2*i
set(j,false);
}
when i ran this algo for N=200 , it took 45.302 ms
On Sat, Dec 8, 2012 at 2:44 AM, Don dondod...@gmail.com wrote:
I know that the Sieve of Eratosthenes is a fast way to find all prime
numbers in a given range.
I noticed that one implementation of a sieve spends a lot of time
marking multiples of small primes as composite. For example, it takes
1000 times as long to mark off all of the multiples of five as it
takes to mark off the multiples of 5003. In addition, when it is
marking off the multiples of larger primes, most of them are multiples
of small primes. In fact, if it could skip over multiples of 2,3,5,7,
and 11, the sieve would be about 5 times faster.
Can someone describe a way to make a sieve faster by not having to
deal with multiples of the first few prime numbers?
Don
--
--
Re: [algogeeks] reverse a string efficiently
considering '+' , here will take Cn time . Here '+' is for concatenate ,
now this concatenation taking place in constant time?? , i dont think
so..internally it will be adding elements to new m/m space and for that it
need to traverse each character...so it will take cn time.
so T(n) =T(n/2) + cn = nlogn
On Tue, Nov 27, 2012 at 11:17 AM, shady sinv...@gmail.com wrote:
what is the time complexity of this?
str_reverse(str){
if(isempty(str)) return str;
else if(length(str) = even) then split str into str_1 and str_2; (of
equal length)
return str_reverse(str_2)+str_reverse(str_1);
else split str into str_1, str_2, str_3; //if str is odd length, e.g.
len = 7, split by 1-3 | 4 | 5-7
return str_reverse(str_3)+str_2+str_reverse(str_1);
}
--
--
Re: [algogeeks] fastest sequential access
@shady : as subject says fastest sequential access , then if i am not getting it wrong.we only care of sequential access a value not modifying the linked list. so i guess double linked list would be helpful 1) bcozz it can move in both the direction , so if linked list is sorted then it would be a great help 2) if you want to insert element at the end of linked list then if will be better than vector so i guess it required 1-2 more parameter to decide ,which one to use. On Wed, Nov 21, 2012 at 8:21 PM, shady sinv...@gmail.com wrote: which data structure among the follow has fastest sequential access ? i) vector ii) Singly linked list iii) Doubly linked list it won't be doubly linked list as it involves more pointer manipulations than singly linked list... -- --
Re: [algogeeks] Repeating element with constraints
yes correct...missed that :( , But we can use method given in the above
geekforgeeks link to find those 2 elements :
set_bit_no = xor ~(xor-1);
/* Now divide elements in two sets by comparing rightmost set
bit of xor with bit at same position in each element. */
for(i = 0; i size; i++)
{
if(arr[i] set_bit_no)
x = x ^ arr[i]; /*XOR of first set in arr[] */
else
y = y ^ arr[i]; /*XOR of second set in arr[] */
}
for(i = 1; i = n; i++)
{
if(i set_bit_no)
x = x ^ i; /*XOR of first set in arr[] and {1, 2, ...n }*/
else
y = y ^ i; /*XOR of second set in arr[] and {1, 2, ...n } */
}
printf(\n The two repeating elements are %d %d , x, y);
now we just need to check if any of these two elements found is present in
the given array , if yes then other element in the missing one.
On Mon, Nov 19, 2012 at 12:07 PM, Rushiraj Patel rushi4...@gmail.comwrote:
@atul : In the second for loop...temp will also contain one which is
being missing along with the one which is being repeated.
kindly check it once again.
On Mon, Nov 19, 2012 at 11:44 AM, atul anand atul.87fri...@gmail.comwrote:
array has all distinct elements ans lie b/w 1 to n , now bcozz they are
all distinct except 1 element means it should have all element with range 1
to n...except 1 element , which can be any element b/w 1 to n.
temp=arr[0]
*for i=1 to n
temp=temp^arr[i]; *
//now temp will contain all distinct elements except one which is
repeated(they cancel out)
*for i=1 to n
temp=temp ^ i; *
// now this will cancel out distinct elements excluding one which is
repeated.
temp will contain that repeated element
On Sun, Nov 18, 2012 at 7:31 PM, shady sinv...@gmail.com wrote:
Given an array of size n, which has all distinct elements between 1 to n
with one element repeating, which also implies that one element is missing.
How to find the repeating element without using extra space and linear
time complexity ?
Any way to do it with exor ? :P
--
--
--
--
Re: [algogeeks] Repeating element with constraints
array has all distinct elements ans lie b/w 1 to n , now bcozz they are all distinct except 1 element means it should have all element with range 1 to n...except 1 element , which can be any element b/w 1 to n. temp=arr[0] *for i=1 to n temp=temp^arr[i]; * //now temp will contain all distinct elements except one which is repeated(they cancel out) *for i=1 to n temp=temp ^ i; * // now this will cancel out distinct elements excluding one which is repeated. temp will contain that repeated element On Sun, Nov 18, 2012 at 7:31 PM, shady sinv...@gmail.com wrote: Given an array of size n, which has all distinct elements between 1 to n with one element repeating, which also implies that one element is missing. How to find the repeating element without using extra space and linear time complexity ? Any way to do it with exor ? :P -- --
Re: [algogeeks] Tree - sum problem
from each node , make 4 recursive call 1) you consider this node as part of the solution i.e left=target - currentNode-data is passed , and consider current-left for next recursion 2)you consider this node as part of the solution i.e left=target - currentNode-data is passed , and consider current-right for next recursion 3) do not consider this node as part of the solution i.e target is passed and consider current-left for next 3) do not consider this node as part of the solution i.e target is passed and consider current-right for next recursion keep track of path in an arr[] as you move on. On 11/15/12, Amitesh Singh singh.amit...@gmail.com wrote: Given a binary search tree and a target value, find all the paths (if there exists more than one) which sum up to the target value. It can be any path in the tree. It doesn't have to be from the root. -- Amitesh -- --
Re: [algogeeks] Advice needed
use enum
On Sat, Oct 27, 2012 at 3:21 AM, rahul sharma rahul23111...@gmail.comwrote:
There is question asked like
O/p of following in C(32 bit OS)
#include iostream
#includestdio.h
using namespace std;
bool IsEqual(char * a)
{
printf(abc);
return true;
}
int main()
{
char str[30];
printf(%d,sizeof(sizeof(IsEqual(str;
getchar();
return 0;
}
I run with .cppi know o/p and all in c++...but c doesn't support
bool.so what should i write in answer as it is asked in written..so wat
should be writen
4 i.e the answer in c++ or should i write that c doesn't support bool
plez comment
--
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] Check if a binary tree is Binary Search Tree or not.
@vishal : as discussed in previous post , your solution wont work for certain test cases...and i dont think so , checking tree in inorder way is complex .It is simple to implement , you just need to call tree recursively in Inorder way and keep track of prev node and compare prev node with current node if prev node current then fine move ahead or report fail. On Tue, Nov 6, 2012 at 12:39 PM, vishal chaudhary vishal.cs.b...@gmail.comwrote: hi all, yes you can do it that way, but the thing is why are you increasing the complexity of the problem by again checking the inorder traversal output to be checked for increasing order. just traverse through the ones recursively(as we do it in the inoder traversal) through all the nodes and check whether the left child is less than the root and root is smaller than the right node. Warm Regards Vishal Chaudhary BE(Hons) Computer Science and Engineering BITS Pilani On Tue, Nov 6, 2012 at 12:34 AM, shady sinv...@gmail.com wrote: Hi, Can we check this by just doing an inorder traversal, and then checking if it is in increasing order or not ? -- 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] Check if a binary tree is Binary Search Tree or not.
@vaibhav : by not using extra space...i guess you mean that you were not allowed to use one extra pointer.bcozz space complexity will remain constant for inorder approch. On Tue, Nov 6, 2012 at 1:07 AM, vaibhav shukla vaibhav200...@gmail.comwrote: yes ofcourse... dats the easiest i suppose... but in one of my interviews, i told this approach, but was then asked not to use space (which i was ,to store inorder) So for such cases, you must try other approaches as well. (DO inorder,keep track of previously visited node and compare it with current node for value greater,or less accordingly.) On Tue, Nov 6, 2012 at 12:34 AM, shady sinv...@gmail.com wrote: Hi, Can we check this by just doing an inorder traversal, and then checking if it is in increasing order or not ? -- 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. -- best wishes!! Vaibhav -- 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: Check if a binary tree is Binary Search Tree or not.
@Don : your algo wont work for following tree :-
30
/ \
20 31
/ \
9 41
above tree is not a BST bcozz here 41 should lie on the right side of the
30but it is not.
so we need to keep track of max and min as we move left or right part of
the tree.and each node should lie b/w that min and max range.
for more details : http://www.geeksforgeeks.org/archives/3042
@shady : yes correct..you can do in that way.
On Tue, Nov 6, 2012 at 1:18 AM, Don dondod...@gmail.com wrote:
That would work. But a simpler approach is:
bool isBinTree(root *t)
{
return (!t) || ((!t-left || (t-value t-left-value))
(!t-right || (t-value t-right-value))
isBinTree(t-left) isBinTree(t-right));
}
On Nov 5, 2:04 pm, shady sinv...@gmail.com wrote:
Hi,
Can we check this by just doing an inorder traversal, and then checking
if
it is in increasing order or not ?
--
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] Time Complexity Analysis
building tree will take O(n) time but for each node we need to find max i.e i = max (inorder, start, end); so complexity in worst case will we O(n^2). On Tue, Nov 6, 2012 at 12:26 AM, shady sinv...@gmail.com wrote: Sorting takes linear time, but it doesnt get repeated n times, it is like - T(n) = 2*T(n/2) + O(n) worst case solution is O(n^2) it is similar to quick sort On Mon, Nov 5, 2012 at 9:15 PM, rahul sharma rahul23111...@gmail.comwrote: dude n for build tree and n in this for finding maximun??so n*(n/2)=o(n^2) On Mon, Nov 5, 2012 at 8:54 PM, shady sinv...@gmail.com wrote: Here the time complexity of the solution should be O(n * log(n)) http://www.geeksforgeeks.org/archives/21781 -- 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.
Re: [algogeeks] swap objects without temp variable
a=a^b; b=a^b; a=a^b; need to check if a and b are equal or not , bcozz a^a =0 On Mon, Nov 5, 2012 at 2:02 AM, manish narayan.shiv...@gmail.com wrote: Swapping two objects (not integers/chars),without using temp...? my solution is using xor operation..is that right and ny other solutions ? -- 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/-/OxVSnZ1QjzMJ. 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] You are given two 32-bit numbers, N and M, and two bit positions, i and j.
check out my comment ...i had posted it log time back on
geekforgeeks...search for atull007 int the below link.
let me know it does not work
http://www.geeksforgeeks.org/forum/topic/adobe-interview-question-for-software-engineerdeveloper-fresher-about-bit-magic-1
On Thu, Nov 1, 2012 at 4:00 AM, rahul sharma rahul23111...@gmail.comwrote:
You are given two 32-bit numbers, N and M, and two bit positions, i and j.
Write a method to set all bits between i and j in N equal to M (e.g., M
becomes a substring of N located at i and starting at j).
EXAMPLE:
Input: N = 100, M = 10101, i = 2, j = 6
Output: N = 10001010100
Following is code...guys i think that in line no. 5 (1j) this should
be replaced with (1j+1).means we have to shift 1 left by j+1 bits..Line
no. 5 should be
int left = max - ((1 j+1) - 1);
plz comment ???
public static int updateBits(int n, int m, int i, int j) {
2 int max = ~0; /* All 1’s */
3
4 // 1’s through position j, then 0’s
5 int left = max - ((1 j) - 1);
6
7 // 1’s after position i
8 int right = ((1 i) - 1);
9
10 // 1’s, with 0s between i and j
11 int mask = left | right;
12
13 // Clear i through j, then put m in there
14 return (n mask) | (m i);
15 }
--
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] Informatica written que : C output
its seem to me that output buffer is not flushing ..to do so you need
to add \n while printing hello i.e
printf(Hello\n);
it was working for you when the else {} part was un-commented because you
are using \n in this statement
//printf( %d - %d \n , tmp[i], count); -- if you remove \n from here
then same problem will be reproduced
On Mon, Oct 29, 2012 at 12:47 PM, Rahul Kumar Patle
patlerahulku...@gmail.com wrote:
can anyone explain the reason for weird output producing by this code..
it is giving output hello many time 30 but as code's logic it should
print only 9 time
it runs correctly when i comment out statements inside else{}
thanks in advance
#includestdio.h
#includestdlib.h
int count = 0;
main()
{
int tmp[10] , i;
int n = 0;
for(i=0;i9;i++)
{
tmp[i]=fork();
if(tmp[i]0)
break;
else
{
//count++;
printf(Hello);
//printf( %d - %d \n , tmp[i], count);
}
}
}
--
Thanks and Regards:
Rahul Kumar Patle
M.Tech, School of Information Technology
Indian Institute of Technology, Kharagpur-721302,
Indiahttp://www.iitkgp.ac.in/
Mobile No: +91-8798049298, +91-9424738542
Alternate Email: rahulkumarpa...@hotmail.com
[image:
Linkedin]http://www.linkedin.com/profile/view?id=106245716trk=tab_pro
[image: Twitter] https://twitter.com/rahulkumarpatle
https://www.facebook.com/rkpatle
--
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] C Macro
if you think the your expanded version is incorrect.You are wrong , because int * will hold pointer but you are not allocating address of x ..instead you are allocating x value as an address of x to *t.This wont work. so to make it work you need to save the address of x and y in temp pointers i.e int *p.*q; p=x; q=y; int t; t=*p; *p=*q; *q=t; now you can convert it into macro. On 10/29/12, rahul sharma rahul23111...@gmail.com wrote: @atul...mistakenly i have put w at place of t in my last post...i wana say On Mon, Oct 29, 2012 at 10:07 AM, dCoder bansal@gmail.com wrote: Just replace your macro with its definition and you will understand. its not doing swapping of pointers...plz explain @dCode i expanded..but its fine...please tell #includestdio.h #define swap(a,b,c) c t;t=a,a=b,b=t int main int x=10,y=20; int *p,*q; swap(x,y,int*); int * t; t=x; x=y; y=t; There is int* at the end..there is som problem with my keyborad...:(.acc to me axpanded version is above..but not swapping two pointerssplz comment On Sun, Oct 28, 2012 at 9:16 PM, rahul sharma rahul23111...@gmail.comwrote: its now doing swapping of pointers...plz explain On Sun, Oct 28, 2012 at 8:08 PM, atul anand atul.87fri...@gmail.comwrote: it should swap On 10/28/12, rahul sharma rahul23111...@gmail.com wrote: Why the following code is not able to swap two macros???although it is easily swapping 2 variables #includestdio.h #define swap(a,b,c) c t;t=a,a=b,b=t int main int x=10,y=20; int *p,*q; swap(x,y,int); -- 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. -- 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] C Macro
well they should not , if you see it closely pointer p and q
contain contain address of a and x.
and swap() macro will swap value these pointers are holding i.e adress
of a and xbut will it reflect address of a and x ???...NO
so if you print the address p and q ...before and after the swap then
you should see that after swap p will be holding address of x and
q will be holding address of a..that it
On 10/29/12, rahul sharma rahul23111...@gmail.com wrote:
I have taken form book...i am writing exact code
#includestdio.h
#define swap(a,b,c) c t;t=a,a=b,b=t;
int main()
{
float a,x;
a=20.0;
x=30.0;
float *p,*q;
p=a,q=x;
swap(p,q,float*);
printf(%f %f,a,x);
getchar();
}
o/p=20.000 30.000
why not swapped???
On Mon, Oct 29, 2012 at 11:01 PM, atul anand
atul.87fri...@gmail.comwrote:
if you think the your expanded version is incorrect.You are wrong ,
because int * will hold pointer but you are not allocating address of
x ..instead you are allocating x value as an address of x to *t.This
wont work.
so to make it work you need to save the address of x and y in temp
pointers i.e
int *p.*q;
p=x;
q=y;
int t;
t=*p;
*p=*q;
*q=t;
now you can convert it into macro.
On 10/29/12, rahul sharma rahul23111...@gmail.com wrote:
@atul...mistakenly i have put w at place of t in my last post...i wana
say
On Mon, Oct 29, 2012 at 10:07 AM, dCoder bansal@gmail.com wrote:
Just replace your macro with its definition and you will understand.
its not doing swapping of pointers...plz explain
@dCode i expanded..but its fine...please tell
#includestdio.h
#define swap(a,b,c) c t;t=a,a=b,b=t
int main
int x=10,y=20;
int *p,*q;
swap(x,y,int*);
int * t;
t=x;
x=y;
y=t;
There is int* at the end..there is som problem with my
keyborad...:(.acc to me axpanded version is above..but not
swapping
two pointerssplz comment
On Sun, Oct 28, 2012 at 9:16 PM, rahul sharma
rahul23111...@gmail.comwrote:
its now doing swapping of pointers...plz explain
On Sun, Oct 28, 2012 at 8:08 PM, atul anand
atul.87fri...@gmail.comwrote:
it should swap
On 10/28/12, rahul sharma rahul23111...@gmail.com wrote:
Why the following code is not able to swap two macros???although
it
is
easily swapping 2 variables
#includestdio.h
#define swap(a,b,c) c t;t=a,a=b,b=t
int main
int x=10,y=20;
int *p,*q;
swap(x,y,int);
--
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.
--
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
Re: [algogeeks] four umbers sum to given value
becoz you are sorting the aux[] , it seems to fine by replacing it with i j
On 10/28/12, rahul sharma rahul23111...@gmail.com wrote:
I wana ask that ccan i replcae while condiion with the condition as follow
while(ij)
code reference :http://www.geeksforgeeks.org/archives/23338
void findFourElements (int arr[], int n, int X)
{
int i, j;
// Create an auxiliary array to store all pair sums
int size = (n*(n-1))/2;
struct pairSum aux[size];
/* Generate all possible pairs from A[] and store sums
of all possible pairs in aux[] */
int k = 0;
for (i = 0; i n-1; i++)
{
for (j = i+1; j n; j++)
{
aux[k].sum = arr[i] + arr[j];
aux[k].first = i;
aux[k].sec = j;
k++;
}
}
// Sort the aux[] array using library function for sorting
qsort (aux, size, sizeof(aux[0]), compare);
// Now start two index variables from two corners of array
// and move them toward each other.
i = 0;
j = size-1;
while (i size j =0 )
{
if ((aux[i].sum + aux[j].sum == X) noCommon(aux[i], aux[j]))
{
printf (%d, %d, %d, %d\n, arr[aux[i].first], arr[aux[i].sec],
arr[aux[j].first], arr[aux[j].sec]);
return;
}
else if (aux[i].sum + aux[j].sum X)
i++;
else
j--;
}
}
--
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] C Macro
it should swap On 10/28/12, rahul sharma rahul23111...@gmail.com wrote: Why the following code is not able to swap two macros???although it is easily swapping 2 variables #includestdio.h #define swap(a,b,c) c t;t=a,a=b,b=t int main int x=10,y=20; int *p,*q; swap(x,y,int); -- 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] C Macro
didnt get you... first it was now working , now its working...!!! please write clearly about your doubts. -- 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] Design a method to find the frequency of occurrences of any given word in a book.
Trie or hash map can b used On 10/24/12, rahul sharma rahul23111...@gmail.com wrote: -- 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] adobe questions
use hash map...with key as original node and value as duplicate of this node duplicate node next and random pointer is set to NULL initially. now traverse whole linked list keep on adding node. after this do another traversal of orig linked list taking key as orig node ..duplicate=fetch value at this key(orig) make duplicate node next and random ptr to duplicate-next=fetch_value_from_hash(orig-next) duplicate-random=fetch_value_from_hash(orig-random) On Tue, Oct 23, 2012 at 2:06 PM, saket narayan.shiv...@gmail.com wrote: There is one linked list having two pointer one as usual next and other is random pointer pointing to any random node in list. write algo to make a duplicate of it. Note:- Original list is const, Can't be modified. i know O(n) solution when list can be modified , and o(n^2) when list can be modified. any one with O(n) solution when list couldnt be modified . -- 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/-/5RLLbA5iod0J. 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] fibonicci recursive help
http://www.geeksforgeeks.org/archives/10120 On 10/21/12, rahul sharma rahul23111...@gmail.com wrote: Guys i have read an article somewhere regarding optimization of recursive fibonicci so that we donot need to calculate the sum that we have already calculated... In case if factorial,we donot need to find factorial that we have already calculated... I just forgot where i read from..may br from coreman ..but i am not able to find this again in coreman..may be i have read online..anybody please shar link from whr i can read these..it would be of great help..thnx in advance -- 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] Longest increasing subsequence
@rahul : nope it wont work ..check for this input :-
input = 1, 2,3,6,4 ,101, 6
by removing msis[i] msis[j] + arr[i] condition then you are
excluding the max sub-sequence found from j=0 to i.
On 10/21/12, rahul sharma rahul23111...@gmail.com wrote:
but if there are -ve numbers then arr[i]arr[j] only is sufficeient as it
become falsecomment if wrng
On Sat, Oct 20, 2012 at 11:59 PM, Saurabh Kumar
srbh.ku...@gmail.comwrote:
If your inputs are only positive numbers then that condition you pointed
out is indeed redundant. But if you want your program to work for
negative
numbers as well, you need that condition.
Also, you should initialize max = msis[0]; before running the loop for
calculating 'max' :
/* Pick maximum of all msis values */
max = msis[0];for ( i = 0; i n; i++ )
if ( max msis[i] )
max = msis[i];
On 20 October 2012 22:58, rahul sharma rahul23111...@gmail.com wrote:
http://www.geeksforgeeks.org/archives/19248
/* Dynamic Programming implementation of Maximum Sum Increasing
Subsequence (MSIS) problem */
#includestdio.h
/* maxSumIS() returns the maximum sum of increasing subsequence in arr[]
of
size n */
int maxSumIS( int arr[], int n )
{
int *msis, i, j, max = 0;
msis = (int*) malloc ( sizeof( int ) * n );
/* Initialize msis values for all indexes */
for ( i = 0; i n; i++ )
msis[i] = arr[i];
/* Compute maximum sum values in bottom up manner */
for ( i = 1; i n; i++ )
for ( j = 0; j i; j++ )
if ( arr[i] arr[j] msis[i] msis[j] + arr[i])
msis[i] = msis[j] + arr[i];
/* Pick maximum of all msis values */
for ( i = 0; i n; i++ )
if ( max msis[i] )
max = msis[i];
/* Free memory to avoid memory leak */
free( msis );
return max;
}
/* Driver program to test above function */
int main()
{
int arr[] = {1, 101, 2, 3, 100, 4, 5};
int n = sizeof(arr)/sizeof(arr[0]);
printf(Sum of maximum sum increasing subsequence is %d\n,
maxSumIS( arr, n ) );
getchar();
return 0;
}
I wana ask inner for loop has two conditons ...cant we remove condition
onryt of operator.
As miss[j] would containg arr[j]or arr[j]+somethngif arr[i]arr[j]
then miss[i] is always miss[j]+arrp[i]
so cant we remove second condtion of operator plz correct if m
wrng
--
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.
Re: [algogeeks] fibonicci recursive help
google searched it : geeksforgeeks + Fibonacci number ;) ;) On 10/21/12, rahul sharma rahul23111...@gmail.com wrote: thnx a lot atul...was looking for that only...can u plz tell me under which section u get this post On Sun, Oct 21, 2012 at 4:03 PM, atul anand atul.87fri...@gmail.com wrote: http://www.geeksforgeeks.org/archives/10120 On 10/21/12, rahul sharma rahul23111...@gmail.com wrote: Guys i have read an article somewhere regarding optimization of recursive fibonicci so that we donot need to calculate the sum that we have already calculated... In case if factorial,we donot need to find factorial that we have already calculated... I just forgot where i read from..may br from coreman ..but i am not able to find this again in coreman..may be i have read online..anybody please shar link from whr i can read these..it would be of great help..thnx in advance -- 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.
Re: [algogeeks] Microsoft Interview Question
@Rahul : yes i know and actually i posted this query on geeksforgeeks. you can find my solution in comments , search for atul007 in the provided link.It will work for all cases. now to find all path you need to do small modification on the same code. On Tue, Oct 16, 2012 at 9:31 AM, Rahul Kumar Patle patlerahulku...@gmail.com wrote: @atul: in your solution object only can move down or right direction. but in my problem object is free to move in any direction and hence there are chances of cycle.. how to memoize cycle. if there is cycle then your approach will give infinite solution. consider this maze 1 1 0 0 0 1 1 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 1 1 1 you can see that object can take path M[0][0] - M[0][1] - M[1][1]- M[1][2]- M[][]- M[][] OR M[0][0] - M[1][0] - M[1][1]- M[1][2]- M[][]- M[][] But simple approach will also take path M[0][0] - M[0][1] - M[1][1]- M[1][0]- M[0][0]- M[0][1] -- CYCLE how you will avoid these cycles... On Tue, Oct 16, 2012 at 8:58 AM, atul anand atul.87fri...@gmail.comwrote: http://www.geeksforgeeks.org/archives/13376 On Tue, Oct 16, 2012 at 8:56 AM, atul anand atul.87fri...@gmail.comwrote: can be done simply by backtracking . On Sat, Oct 13, 2012 at 12:31 AM, Rahul Kumar Patle patlerahulku...@gmail.com wrote: Pls help to solve this que.. does any one have DP solution for following que. http://www.geeksforgeeks.org/archives/24488 section 5/question 2 Write a program to find all the possible paths from a starting point to dest point in a maze(2-D array). ex:1 0 1 0 1 1 1 1 0 1 0 1 0 0 1 1 If there is a block it’s represented by 0. If there is a path it’s represented by 1. -- Thanks and Regards: Rahul Kumar Patle M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, Indiahttp://www.iitkgp.ac.in/ Mobile No: +91-8798049298, +91-9424738542 Alternate Email: rahulkumarpa...@hotmail.com [image: Linkedin]http://www.linkedin.com/profile/view?id=106245716trk=tab_pro [image: Twitter] https://twitter.com/rahulkumarpatle https://www.facebook.com/rkpatle -- 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. -- Thanks and Regards: Rahul Kumar Patle M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, Indiahttp://www.iitkgp.ac.in/ Mobile No: +91-8798049298, +91-9424738542 Alternate Email: rahulkumarpa...@hotmail.com [image: Linkedin]http://www.linkedin.com/profile/view?id=106245716trk=tab_pro [image: Twitter] https://twitter.com/rahulkumarpatle https://www.facebook.com/rkpatle -- 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: Microsoft Interview Question
@jaspreet : i dont find much difference between using BFS or backtracking...which is doing similar to DFS. On Tue, Oct 16, 2012 at 4:28 AM, Jaspreet Singh jassajjassaj...@gmail.comwrote: BFS On Sun, Oct 14, 2012 at 4:21 PM, Rahul Kumar Patle patlerahulku...@gmail.com wrote: response awaited!!! anyone?? On Sat, Oct 13, 2012 at 12:31 AM, Rahul Kumar Patle patlerahulku...@gmail.com wrote: Pls help to solve this que.. does any one have DP solution for following que. http://www.geeksforgeeks.org/archives/24488 section 5/question 2 Write a program to find all the possible paths from a starting point to dest point in a maze(2-D array). ex: 1 0 1 0 1 1 1 1 0 1 0 1 0 0 1 1 If there is a block it’s represented by 0. If there is a path it’s represented by 1. -- Thanks and Regards: Rahul Kumar Patle M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, Indiahttp://www.iitkgp.ac.in/ Mobile No: +91-8798049298, +91-9424738542 Alternate Email: rahulkumarpa...@hotmail.com [image: Linkedin]http://www.linkedin.com/profile/view?id=106245716trk=tab_pro [image: Twitter] https://twitter.com/rahulkumarpatle https://www.facebook.com/rkpatle -- Thanks and Regards: Rahul Kumar Patle M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, Indiahttp://www.iitkgp.ac.in/ Mobile No: +91-8798049298, +91-9424738542 Alternate Email: rahulkumarpa...@hotmail.com [image: Linkedin]http://www.linkedin.com/profile/view?id=106245716trk=tab_pro [image: Twitter] https://twitter.com/rahulkumarpatle https://www.facebook.com/rkpatle -- 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] Microsoft Interview Question
can be done simply by backtracking . On Sat, Oct 13, 2012 at 12:31 AM, Rahul Kumar Patle patlerahulku...@gmail.com wrote: Pls help to solve this que.. does any one have DP solution for following que. http://www.geeksforgeeks.org/archives/24488 section 5/question 2 Write a program to find all the possible paths from a starting point to dest point in a maze(2-D array). ex: 1 0 1 0 1 1 1 1 0 1 0 1 0 0 1 1 If there is a block it’s represented by 0. If there is a path it’s represented by 1. -- Thanks and Regards: Rahul Kumar Patle M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, Indiahttp://www.iitkgp.ac.in/ Mobile No: +91-8798049298, +91-9424738542 Alternate Email: rahulkumarpa...@hotmail.com [image: Linkedin]http://www.linkedin.com/profile/view?id=106245716trk=tab_pro [image: Twitter] https://twitter.com/rahulkumarpatle https://www.facebook.com/rkpatle -- 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] Microsoft Interview Question
http://www.geeksforgeeks.org/archives/13376 On Tue, Oct 16, 2012 at 8:56 AM, atul anand atul.87fri...@gmail.com wrote: can be done simply by backtracking . On Sat, Oct 13, 2012 at 12:31 AM, Rahul Kumar Patle patlerahulku...@gmail.com wrote: Pls help to solve this que.. does any one have DP solution for following que. http://www.geeksforgeeks.org/archives/24488 section 5/question 2 Write a program to find all the possible paths from a starting point to dest point in a maze(2-D array). ex: 1 0 1 0 1 1 1 1 0 1 0 1 0 0 1 1 If there is a block it’s represented by 0. If there is a path it’s represented by 1. -- Thanks and Regards: Rahul Kumar Patle M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, Indiahttp://www.iitkgp.ac.in/ Mobile No: +91-8798049298, +91-9424738542 Alternate Email: rahulkumarpa...@hotmail.com [image: Linkedin]http://www.linkedin.com/profile/view?id=106245716trk=tab_pro [image: Twitter] https://twitter.com/rahulkumarpatle https://www.facebook.com/rkpatle -- 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] Virtual functions in constructor
http://www.parashift.com/c++-faq/virtual-functions.html On Wed, Oct 10, 2012 at 2:16 AM, rahul sharma rahul23111...@gmail.comwrote: Guys i have read that concept of virtual fxn is not applicable in case of constructors..I means using virtual function in constructors always call local function..i wan to read more on this..can nybody explain use of virtual functions in constructor or provide me with a link for this.. thnx -- 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] Min Edges to be added to DAG to make it Strongly connected?
i have doubts in miscof answer , your question says that given graph is a DAG ,but in miscof's reply he is considering directed graph which contain say n strongly connected component , so if we consider dat there are n strongly connected component in your graph then that graph is not a DAG(this will violates your question). But if you are considering all nodes in a given strongly connected graph as a single node then given graph will form DAG. so there is lot of difference in the twoso please clarify your question. On Wed, Oct 10, 2012 at 1:26 AM, KK kunalkapadi...@gmail.com wrote: This is the linkhttp://apps.topcoder.com/forums/?module=ThreadthreadID=764182start=0mc=4#1614862to the answer given by misof.. and it worked!! On Sunday, 7 October 2012 00:41:48 UTC+5:30, kailash wrote: @atul: No,it's not the correct answer. Let's take an example of star like DAG:- A --B--C | V D This DAG contains only one cut vertex(B) but we need to add two edges to make it strongly connected. On Sat, Oct 6, 2012 at 7:37 PM, atul anand atul.8...@gmail.com wrote: find no. of cut vertex in the DAGthat will be the ans. On 6 Oct 2012 19:33, KK kunalka...@gmail.com wrote: Given a DAG(Directed Acyclic Graph). How to find out the minimum number of edges that needs to be added so that the given graph becomes Strongly Connected? -- 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/-/PbR3j9S5OXUJhttps://groups.google.com/d/msg/algogeeks/-/PbR3j9S5OXUJ . To post to this group, send email to algo...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+...@** googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en 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 algo...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+...@** googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en. -- -- ‘Kailash Bagaria’ B-tech 4th year Computer Science Engineering Indian Institute of Technology, Roorkee Roorkee, India (247667) -- 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/-/O5kS0uhrsr4J. 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] rectangle of max sum MS Q
@priya : i dont knw , how you came up with these values ...!!! and aove code given is not a full code , it just a sketch of code to make you understand.Before moving further,i would like to clarify that innner K-loop is running kadane algo(full code is not written). so i cut short in this by discussing the idea behind it After finding cumulative sum of each column ..moving top to bottom , Suppose we get this :- 1 0 0 0 1 1 1 -2 1 2 2 -4 2 3 2 -3 now IDEA is start from last row. -- ( I-Loop is handling this ) negate values i each cell of first row from the each cell for last row -- ( j-Loop is handling this ) i.e 2-1 , 3-0 , 2-0, -3-0 == 1,3,2,-3 1,3,2,-3 == now run kadane algo on this last row only and update max ( K-loop is doing this) similarly , when we increment j i.e now we move to second row which j loop is handling. do the same :- 2-1,3-1, 2-1,-3-2 // --- run kadane algo on this and update max. now when j loop ends , then we are moving to second last row and doing the same ...as we did with last row in above example. i hope now you get it.. On 10/9/12, Priya Dhingra priya.dhingr...@gmail.com wrote: i dnt know how ur algo is handling the case like [c2 d2 ,c3 d3] or [c1 d1, c2 d2 ,c3 d3] as i run this loop it is considering the following matrices i=3 j=0 nd k=0 to 3 [a2 a3 a4],[a2 b2,a3 b3,a4 b4].[a2 b2 c2,a3 b3 c3,a4 b4 c4],[a2 b2 c2 d2 ,a3 b3 c3 d3,a4 b4 c4 d4] i=3 j=1 nd k=0 to 3 [a3 a4], [a3 b3, a4 b4],[a3 b3 c3, a4 b4 c4 d4],[a3 b3 c3 d3 ,a4 b4 c4 d4] i=3 j=2 k =0 to 3 [a4] [a4 b4] [a4 b4 c4] [a4 b4 c4 d4] i=2 j=0 k=0 to 3 [a2 a3] [a2 b2,a3 b3],[a2 b2 c2,a3 b3 c3],[a2 b2 c2 d2 ,a3 b3 c3 d3] i=2 j=1 k=0 to 3 [a2] [a3 b3] [a3 b3 c3] [a3 b3 c3 d3] i=1 j= k =0 to 3 [a2] [a2 b2] [a2 b2 c2][a2 b2 c2 d2] On Mon, Oct 8, 2012 at 9:53 PM, atul anand atul.87fri...@gmail.com wrote: @Priya : if first row is the max one , then it is actually boundary case which you can be handled easily,once you are done which above algo. please note that only first row need to checked if it max not every row , above algo is handling this . you can also modify given algo which will handle this boundary case. for rest of the cases it will work fine. It is handling cases like... c2d2 c3d3 etc... please try to understand idea behind the given algo ,let me know in case you have any further doubt. On Mon, Oct 8, 2012 at 10:52 PM, Priya Dhingra priya.dhingr...@gmail.comwrote: @atul if the largest matrix is [a1 b1 c1 d1 ] i mean if it is the first row or if it is [c2 d2.i think then then ur code wont be giving the right answer. c3 d3] correct me if i'm wrong On Monday, January 16, 2012 7:51:46 AM UTC-8, atul007 wrote: find cumulative sum of each column. now for each arr[x][y] = sum of arr[i=0 to x] [j] ; a1 b1 c1 d1 a2 b2 c2 d2 a3 b3 c3 d3 a4 d4 c4 d4 now we have reduced this problem to find max-subarray . which can be efficiently calculated using kadane's algo for each row. NOTE: now suppose if row = 0 does not participate in calculating max sum matrix so u need to subtract a1 from a2,a3,a4 similarly for other element in row 1,2,3. now updated matrix considered i.e from (row =1 to row =3 ). for this updated matrix, each[x][y] is the sum of arr[i=1 to x] [j]. similarly do for other elements. On Mon, Jan 16, 2012 at 6:55 AM, Ashish Goel ash...@gmail.com wrote: given a m*n matrix, find the subset rectangle with max sum (any other rectangle taken would have lesser sum) Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algo...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+...@** googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en. -- 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/-/4jFUDHYfBqUJ. 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. -- Best Regards Priya Dhingra -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email
Re: [algogeeks] finding element in array with minimum of comparing
@ Mangal : well if see the soln carefully then before loop starts elem is
assigned to arr[0] and copy of arr[0] is saved to temp. This will make sure
that the elem exists in the arr[] ,so it will never reach arr[-1] . when
size become =0 then it will come out of the loop bcoz of the assignment
done before.So it acts like a delimiter for termination of loop.
But there could be possibility that *actual arr[]* contains elem at
position arr[0], dats why it is saved to temp and checking is done at the
end , after the while() loop if temp is elem or not .
i hope now you got the solution , *very poor analysis of the given solution
i will say *;) ;) ;)
On Mon, Oct 8, 2012 at 12:31 AM, Mangal Dev Gupta dev.it...@gmail.comwrote:
*@Dave while( arr[--size] != elem );*
*Exception will come when it will encounter a[-1]*
*i dont know if this loop will ever end... very poor solution i will say
*
On Sat, Oct 6, 2012 at 10:00 PM, Umer Farooq the.um...@gmail.com wrote:
Well actually, I've just gone through Dave's code thoroughly and I
believe that his code is most appropriate.
Thanks viper11 for providing the explanation.
As for my code, I'd like to replace
while (i!=j)
with
while (i j)
because != won't work for middle element if the number of elements are
odd ... and it also won't work if the number of elements are even.
Anyway, thanks Dave for providing us with such a great solution. Please
keep posting! :-)
And others, thanks for pointing out the issue in my code.
On Sat, Oct 6, 2012 at 9:03 PM, Kalidhakani J kanikali...@gmail.comwrote:
@umer - what if the element to be searched is at the middle of the
array? your code doesn't handles this. check out.
On Sat, Oct 6, 2012 at 3:38 AM, icy` vipe...@gmail.com wrote:
nice solution, Dave!
@Umer -- if the sought ele is first, then Dave's code has it sitting in
the variable temp for a little while. Loop will stop when size is 0,
since arr[0]==elem. Now he throws temp back into arr[0], which will return
index 0 from the last compare line.
On Wednesday, October 3, 2012 2:08:56 AM UTC-4, Umer Farooq wrote:
@Dave Thanks for pointing that out.
But I still can't get what if elem is on first element or it is not
present in the array? How is your code going to handle that situation?
@Atul, Well yes, In the given question, the number of iterations were
2n. Which I have reduced to n+n/2.
On Tue, Oct 2, 2012 at 11:13 PM, atul anand atul.8...@gmail.comwrote:
@umer : how no. of comparison are reduced to half by moving both
sidesyou have 2 if condition inside, so you are making 2
comparisons at each iteration + n/2 comparison for while loop so
number of comparisons are n+n/2
On 10/2/12, Umer Farooq the@gmail.com wrote:
why don't we try it from both ends ... something like this:
int i = 0; j = size-1;
while (i != j)
{
if (arr[i] == elem)
return arr[i];
if (arr[j] == elem)
return arr[j];
}
this way, we have eliminated half of the comparisons in for loop?
What do
you guys say?
On Tue, Oct 2, 2012 at 12:18 PM, rafi rafiw...@gmail.com wrote:
Vikas is right!
while (n) is equal to (while n!=0)
you have 2n compares!
בתאריך יום שני, 1 באוקטובר 2012 12:12:21 UTC+2, מאת vikas:
still there is no improvement, compiler will generate the code to
compare
with zero here. what you have accomplished is , hide it from
human eyes
On Monday, 1 October 2012 15:25:09 UTC+5:30, Navin Kumar wrote:
@atul:
still it won't compare 0 th element. Slight modification in your
code:
n=*sizeof(arr)*;
do
{
if(elem==arr[*--n*])
print found;
}while(n);
On Mon, Oct 1, 2012 at 9:50 AM, atul anand atul.8...@gmail.com
wrote:
yes, but there no need of checking outside the loop
n=sizeof(arr)-1;
do
{
if(elem==arr[n])
print found;
n--;
}while(n);
On Mon, Oct 1, 2012 at 9:33 AM, Navin Kumar
algorit...@gmail.comwrote:
@atul: keep one more checking outside loop for element at 0 th
index.
Because when n = 0 the your loop come out from the loop
without
comparing
it.
On Mon, Oct 1, 2012 at 8:55 AM, atul anand
atul.8...@gmail.comwrote:
n=sizeof(arr);
n--;
while(n)
{
if(elem=arr[n])
print found;
n--;
}
On Sun, Sep 30, 2012 at 2:56 PM, רפי וינר rafiw...@gmail.com
wrote:
Hi
i was in an interview and was given a simple function
int arrExsits(int* arr,int size,int elem){
for (int i=0;isize;++i)
if(elem==arr[i])
return i;
return -1;
}
this function does 2n compares
n- the if statment
n-check that i is smaller then size
i was suppose to give an optimal (less compares) solution so
i gave
int arrExsits(int* arr,int size,int elem){
if (arr[size-1]==elem)
return size-1;
arr[size-1]=elem]
for (int i=0;;++i)
if(elem==arr[i]){
if (i!=size-1)
return i
Re: [algogeeks] rectangle of max sum MS Q
@Priya : if first row is the max one , then it is actually boundary case which you can be handled easily,once you are done which above algo. please note that only first row need to checked if it max not every row , above algo is handling this . you can also modify given algo which will handle this boundary case. for rest of the cases it will work fine. It is handling cases like... c2d2 c3d3 etc... please try to understand idea behind the given algo ,let me know in case you have any further doubt. On Mon, Oct 8, 2012 at 10:52 PM, Priya Dhingra priya.dhingr...@gmail.comwrote: @atul if the largest matrix is [a1 b1 c1 d1 ] i mean if it is the first row or if it is [c2 d2.i think then then ur code wont be giving the right answer. c3 d3] correct me if i'm wrong On Monday, January 16, 2012 7:51:46 AM UTC-8, atul007 wrote: find cumulative sum of each column. now for each arr[x][y] = sum of arr[i=0 to x] [j] ; a1 b1 c1 d1 a2 b2 c2 d2 a3 b3 c3 d3 a4 d4 c4 d4 now we have reduced this problem to find max-subarray . which can be efficiently calculated using kadane's algo for each row. NOTE: now suppose if row = 0 does not participate in calculating max sum matrix so u need to subtract a1 from a2,a3,a4 similarly for other element in row 1,2,3. now updated matrix considered i.e from (row =1 to row =3 ). for this updated matrix, each[x][y] is the sum of arr[i=1 to x] [j]. similarly do for other elements. On Mon, Jan 16, 2012 at 6:55 AM, Ashish Goel ash...@gmail.com wrote: given a m*n matrix, find the subset rectangle with max sum (any other rectangle taken would have lesser sum) Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algo...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+...@** googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en. -- 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/-/4jFUDHYfBqUJ. 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] Min Edges to be added to DAG to make it Strongly connected?
yeah i read it wrongly .. i thought ques was asking to find total strongly connected component in the graph On 10/7/12, bharat b bagana.bharatku...@gmail.com wrote: @atul : if there is no cut vertex, that doesn't mean that graph is strongly connected ... On Sat, Oct 6, 2012 at 7:37 PM, atul anand atul.87fri...@gmail.com wrote: find no. of cut vertex in the DAGthat will be the ans. On 6 Oct 2012 19:33, KK kunalkapadi...@gmail.com wrote: Given a DAG(Directed Acyclic Graph). How to find out the minimum number of edges that needs to be added so that the given graph becomes Strongly Connected? -- 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/-/PbR3j9S5OXUJ. 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.
Re: [algogeeks] Min Edges to be added to DAG to make it Strongly connected?
find no. of cut vertex in the DAGthat will be the ans. On 6 Oct 2012 19:33, KK kunalkapadi...@gmail.com wrote: Given a DAG(Directed Acyclic Graph). How to find out the minimum number of edges that needs to be added so that the given graph becomes Strongly Connected? -- 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/-/PbR3j9S5OXUJ. 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] C doubt
ch=i++[s]; // in this value is assigned first and then increment will take place...bcozz you are using post increment. here i does not have any other option it has to do post increment before [] comes...but it will not assign value to 'i' ( i.e incremented 'i' value) so compiler will do something like this ch=*(i + s); i=i+1; ch=++i[s]; // in this case compiler will rewrite it to something like this , ch=++(*(i+s)); // this will increment the value at i[s], pre-increment is taking place ...so updated i[s] value will be assigned o ch if you do somthing like this :- ch=i[s]++; // here post increment is happening , so compiler will rewrite it somthing like this // ch will contain old value but if you print i[s] , it will print incremented value of i[s]; ch=*(i+s); i[s]=i[s] + 1; On 10/6/12, rahul sharma rahul23111...@gmail.com wrote: char ch ch=i++[s]; printf(%c,ch); this will print i[s],then i is incrementrd after assigning to ch ch=++i[s];// this will inccrement value at i[s] My question is what is role of priority which is making them behaving differentI am not getting y not first i is incremented then i[s] is assigned plz tell -- 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] finding element in array with minimum of comparing
@umer : how no. of comparison are reduced to half by moving both
sidesyou have 2 if condition inside, so you are making 2
comparisons at each iteration + n/2 comparison for while loop so
number of comparisons are n+n/2
On 10/2/12, Umer Farooq the.um...@gmail.com wrote:
why don't we try it from both ends ... something like this:
int i = 0; j = size-1;
while (i != j)
{
if (arr[i] == elem)
return arr[i];
if (arr[j] == elem)
return arr[j];
}
this way, we have eliminated half of the comparisons in for loop? What do
you guys say?
On Tue, Oct 2, 2012 at 12:18 PM, rafi rafiwie...@gmail.com wrote:
Vikas is right!
while (n) is equal to (while n!=0)
you have 2n compares!
בתאריך יום שני, 1 באוקטובר 2012 12:12:21 UTC+2, מאת vikas:
still there is no improvement, compiler will generate the code to
compare
with zero here. what you have accomplished is , hide it from human eyes
On Monday, 1 October 2012 15:25:09 UTC+5:30, Navin Kumar wrote:
@atul:
still it won't compare 0 th element. Slight modification in your code:
n=*sizeof(arr)*;
do
{
if(elem==arr[*--n*])
print found;
}while(n);
On Mon, Oct 1, 2012 at 9:50 AM, atul anand atul.8...@gmail.com wrote:
yes, but there no need of checking outside the loop
n=sizeof(arr)-1;
do
{
if(elem==arr[n])
print found;
n--;
}while(n);
On Mon, Oct 1, 2012 at 9:33 AM, Navin Kumar
algorit...@gmail.comwrote:
@atul: keep one more checking outside loop for element at 0 th index.
Because when n = 0 the your loop come out from the loop without
comparing
it.
On Mon, Oct 1, 2012 at 8:55 AM, atul anand
atul.8...@gmail.comwrote:
n=sizeof(arr);
n--;
while(n)
{
if(elem=arr[n])
print found;
n--;
}
On Sun, Sep 30, 2012 at 2:56 PM, רפי וינר rafiw...@gmail.com
wrote:
Hi
i was in an interview and was given a simple function
int arrExsits(int* arr,int size,int elem){
for (int i=0;isize;++i)
if(elem==arr[i])
return i;
return -1;
}
this function does 2n compares
n- the if statment
n-check that i is smaller then size
i was suppose to give an optimal (less compares) solution so i gave
int arrExsits(int* arr,int size,int elem){
if (arr[size-1]==elem)
return size-1;
arr[size-1]=elem]
for (int i=0;;++i)
if(elem==arr[i]){
if (i!=size-1)
return i;
return -1;
}
this solution works and it has n+2 compares the first one another n
and the second inner if.
they told me it's good (and I've passed) but they told just for my
knowledge that there is a better N compare solution.
I've searched the web but couldn't find it.
anybody knows?
Thanks
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algo...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+...@googlegroups.com**.
For more options, visit this group at http://groups.google.com/**
group/algogeeks?hl=enhttp://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 algo...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+...@googlegroups.com**.
For more options, visit this group at http://groups.google.com/**
group/algogeeks?hl=enhttp://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 algo...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+...@googlegroups.com**.
For more options, visit this group at http://groups.google.com/**
group/algogeeks?hl=en
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 algo...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+...@googlegroups.com**.
For more options, visit this group at http://groups.google.com/**
group/algogeeks?hl=en
http://groups.google.com/group/algogeeks?hl=en.
--
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/-/SwuLNscTCOoJ.
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.
--
Umer
--
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
Re: [algogeeks] Facebook question!
void combination(char str[2][100],int len,int row,int j)
{
static char prn[3];
int i=0,k=0,p=0;
if(j==2)
{
prn[j]='\0';
printf(\n%s,prn);
}
for(p=row;plen;p++)
{
for(k=0;kstrlen(str[row]);k++)
{
prn[j]=str[row][k];
combination(str,len,p+1,j+1);
}
}
}
call : combination(str,len,0,0);// len = number of words in your eg call will be
combination(str,2,0,0);
On 9/30/12, ~*~VICKY~*~ venkat.jun...@gmail.com wrote:
Given 'n' arrays each of variable sizes. Write code to print all
combinations. Each combination contains one element from one array each.
For eg:
string str[]={hello, how}
op will be
hh
ho
hw
eh
eo
ew
lh
lo
lw
lh
lo
lw
oh
oo
ow
15 sets would come, includes repetition.
My approach had bugs and didn't work. Help would be appreciated.
--
Cheers,
Vicky
--
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] Facebook question!
my prev code was incorrect :-
here is the correct code :-
void combination(char str[3][100],int len,int row,int j)
{
static char prn[3];
int i=0,k=0,p=0;
if(j==2)
{
prn[j]='\0';
printf(\n%s,prn);
return;
}
for(p=row;plen;p++)
{
for(k=0;kstrlen(str[p]);k++)
{
prn[j]=str[p][k];
combination(str,len,p+1,j+1);
}
}
}
call : combination(str,len,0,0); // len = number of words
for input : str[3][100]={hello,how,a};
output :-
hh
ho
hw
ha
eh
eo
ew
ea
lh
lo
lw
la
lh
lo
lw
la
oh
oo
ow
oa
ha
oa
wa
On 10/1/12, ~*~VICKY~*~ venkat.jun...@gmail.com wrote:
Hi atul,
Thanks for your response. I found your idea matches very much with my
approach which i claimed buggy. The problem in my code is that It prints
some extra strings in the end. For eg for the below input it prints
24(5*3+3*3) comb instead of 15(5*3). I couldn't recognize how to resolve
it. Could any1 help me out.
#includeiostream
#includestring
#includecstdio
string str[]={hello, how,a};
void print_all(string sel, int k,int n)
{
if(k == n){
static int count =1;
coutcount++ selendl;
return;
}
for(int i = k; i n ; i++)
{
for(int j = 0; j str[i].length(); j++)
{
print_all(sel+str[i][j], k+1,n);
}
}
}
int main()
{
print_all(,0,2);
}
//code ends
On Mon, Oct 1, 2012 at 12:33 AM, atul anand atul.87fri...@gmail.com
wrote:
void combination(char str[2][100],int len,int row,int j)
{
static char prn[3];
int i=0,k=0,p=0;
if(j==2)
{
prn[j]='\0';
printf(\n%s,prn);
}
for(p=row;plen;p++)
{
for(k=0;kstrlen(str[row]);k++)
{
prn[j]=str[row][k];
combination(str,len,p+1,j+1);
}
}
}
call : combination(str,len,0,0);// len = number of words in your eg call
will be
combination(str,2,0,0);
On 9/30/12, ~*~VICKY~*~ venkat.jun...@gmail.com wrote:
Given 'n' arrays each of variable sizes. Write code to print all
combinations. Each combination contains one element from one array
each.
For eg:
string str[]={hello, how}
op will be
hh
ho
hw
eh
eo
ew
lh
lo
lw
lh
lo
lw
oh
oo
ow
15 sets would come, includes repetition.
My approach had bugs and didn't work. Help would be appreciated.
--
Cheers,
Vicky
--
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.
--
Cheers,
Vicky
--
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] finding element in array with minimum of comparing
n=sizeof(arr);
n--;
while(n)
{
if(elem=arr[n])
print found;
n--;
}
On Sun, Sep 30, 2012 at 2:56 PM, רפי וינר rafiwie...@gmail.com wrote:
Hi
i was in an interview and was given a simple function
int arrExsits(int* arr,int size,int elem){
for (int i=0;isize;++i)
if(elem==arr[i])
return i;
return -1;
}
this function does 2n compares
n- the if statment
n-check that i is smaller then size
i was suppose to give an optimal (less compares) solution so i gave
int arrExsits(int* arr,int size,int elem){
if (arr[size-1]==elem)
return size-1;
arr[size-1]=elem]
for (int i=0;;++i)
if(elem==arr[i]){
if (i!=size-1)
return i;
return -1;
}
this solution works and it has n+2 compares the first one another n and
the second inner if.
they told me it's good (and I've passed) but they told just for my
knowledge that there is a better N compare solution.
I've searched the web but couldn't find it.
anybody knows?
Thanks
--
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] finding element in array with minimum of comparing
yes, but there no need of checking outside the loop
n=sizeof(arr)-1;
do
{
if(elem==arr[n])
print found;
n--;
}while(n);
On Mon, Oct 1, 2012 at 9:33 AM, Navin Kumar algorithm.i...@gmail.comwrote:
@atul: keep one more checking outside loop for element at 0 th index.
Because when n = 0 the your loop come out from the loop without comparing
it.
On Mon, Oct 1, 2012 at 8:55 AM, atul anand atul.87fri...@gmail.comwrote:
n=sizeof(arr);
n--;
while(n)
{
if(elem=arr[n])
print found;
n--;
}
On Sun, Sep 30, 2012 at 2:56 PM, רפי וינר rafiwie...@gmail.com wrote:
Hi
i was in an interview and was given a simple function
int arrExsits(int* arr,int size,int elem){
for (int i=0;isize;++i)
if(elem==arr[i])
return i;
return -1;
}
this function does 2n compares
n- the if statment
n-check that i is smaller then size
i was suppose to give an optimal (less compares) solution so i gave
int arrExsits(int* arr,int size,int elem){
if (arr[size-1]==elem)
return size-1;
arr[size-1]=elem]
for (int i=0;;++i)
if(elem==arr[i]){
if (i!=size-1)
return i;
return -1;
}
this solution works and it has n+2 compares the first one another n and
the second inner if.
they told me it's good (and I've passed) but they told just for my
knowledge that there is a better N compare solution.
I've searched the web but couldn't find it.
anybody knows?
Thanks
--
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.
Re: [algogeeks] spoj problem EASYMATH
@Wladimir : you have to use formula given in below link http://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle On Fri, Sep 28, 2012 at 12:26 AM, Wladimir Tavares wladimir...@gmail.comwrote: what happens when a = 3, d = 5 a, a + d, d +2, a +3 d = 3,8,13,18? Wladimir Araujo Tavares *Federal University of Ceará http://lia.ufc.br/%7Ewladimir/ Homepage http://lia.ufc.br/%7Ewladimir/ | Maratonahttps://sites.google.com/site/quixadamaratona/| * On Thu, Sep 27, 2012 at 8:57 AM, atul anand atul.87fri...@gmail.comwrote: @ashish : here is the generalized equation http://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle note : you need to take LCM of a,a+d,a+2d etc etcwhenever you are dividing to find count On Thu, Sep 27, 2012 at 2:55 AM, ashish pant asheesh...@gmail.comwrote: thanks for your reply.. actually i was thinking the same thing.. but I am facing problems in finding the unique multiples of a+3d and a+4d as applying inclusion exclusion principle in this way is getting too difficult due to large no of factors to be added and subtracted.. is der any other approach or any way to simplify the process.. -- 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.
Re: [algogeeks] spoj problem EASYMATH
@ashish : here is the generalized equation http://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle note : you need to take LCM of a,a+d,a+2d etc etcwhenever you are dividing to find count On Thu, Sep 27, 2012 at 2:55 AM, ashish pant asheesh...@gmail.com wrote: thanks for your reply.. actually i was thinking the same thing.. but I am facing problems in finding the unique multiples of a+3d and a+4d as applying inclusion exclusion principle in this way is getting too difficult due to large no of factors to be added and subtracted.. is der any other approach or any way to simplify the process.. -- 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] CodeChef Problem
the example given in the link , tried 2-3 other example ..it seems to work for them.Maybe problem is not that simple and may fail for some tricky test case.So please correct me if i am wrong:- input : 2 3 4 1 1 sort(input) : 1 1 2 3 4 k=3 from end keep on adding till k-1 add position 4 become : 4+3+2 (cost 5 : 3 + 2) add position 2 : 1+1 (cost 1 :1) add position 2 to 4 : 4+3+2+1+1(cost 2 ) total cost : 5+1+2 = 8 On Tue, Sep 25, 2012 at 1:23 AM, Krishnan aariyankrish...@gmail.com wrote: http://codeforces.com/contest/227/problem/D How to approach this problem can anybody help? -- 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] microsoft_c++_qstn
voilate sequence point rule...acc to c++ standard
no complier to trust
On 25 Sep 2012 21:27, Ravi Ranjan ravi.cool2...@gmail.com wrote:
#includeiostream.h
int rec(int i)
{
static int d=1;
if(i=5)
return i;
d=d+i;
i=i+i;
rec(d);
}
int main()
{
coutrec(1);
return 0;
}
various compilers give diffrent result... why so???
n how d value is calculated by differnt compilers.. whhat is d correct
output n which compiler to trust??
--
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] microsoft_c++_qstn
*i = i + i; // *this voilate sequence point rule output is compiler dependent. On Tue, Sep 25, 2012 at 9:59 PM, Ravi Ranjan ravi.cool2...@gmail.comwrote: @atul so 8 will be the answer or is it not fixed??? -- 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] microsoft_c++_qstn
correct...my fault On Wed, Sep 26, 2012 at 12:04 AM, shady sinv...@gmail.com wrote: this is not a sequence point rule... there is only one way of evaluation here. correct me if wrong... On Tue, Sep 25, 2012 at 11:26 PM, atul anand atul.87fri...@gmail.comwrote: *i = i + i; // *this voilate sequence point rule output is compiler dependent. On Tue, Sep 25, 2012 at 9:59 PM, Ravi Ranjan ravi.cool2...@gmail.comwrote: @atul so 8 will be the answer or is it not fixed??? -- 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.
