Re: [algogeeks] Amazon Written Test Q1
if you know the range then you can use something like count sort, but as here nothing is mentioned you have to take at least O(nlogn) time as the lower bound of comparision sort is O(nlogn) On Sun, Jan 30, 2011 at 6:10 PM, bittu shashank7andr...@gmail.com wrote: Sort the Doubly Linked List..In Minim time complexity...is it possible to sort doubly linked list in O(n)..can some one provide..tutorial ,code or algo fro thiswhen u will fright with with amazon..you will see this question..as it is..so try it now.. Thanks Shashank -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: google questions
I am proposing a solution for problem 2.. 2. Given a text file, implement a solution to find out if a pattern similar to wild cards can be detected. fort example find if a*b*cd*, or *win or *def* exists in the text. Whatever be the pattern sort it must be regular expression. So in principle, there always exists a deterministic finite automata with exactly one finite state to accept the pattern. Thus, the problem can be solved. For example take the case for a*b*cd*. The automaton can can written as: 1.Set state=1. 2. Scan the string until end of string is reached. 2.1. If state is 1 and the letter is a then do not change the state. If the state is 1 and the letter is b then go to state 2. if the state is 1 and the letter is c then go to state 3. if the state is 1 and the letter is d then go to state 4. if the state is 2 and letter is a then go to state 4. if the state is 2 and the letter is b then do not change the state. if the state is 2 and the letter is c the go to state 3. if the state is 2 and the letter is d then go to state 4. if the state is 3 and the letter is a,b or c then go to state 4. if the state is 3 and the letter is d then do not change state. if the state is 4 then do not change state. 3. If the state is 3 output accept else output reject. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Microsoft Written test questions required
Try to solve GATE question papers on data structures, tress DBMS and OS. Also try to solve exploring C. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: wooden log problem
if you have n points to cut and a wooden log of lenght l,choose mid[l]
and choose a point which is closer to this l and do this for all
segments
On Jan 31, 10:14 am, ritu ritugarg.c...@gmail.com wrote:
You are given a wooden log of length n. It has n+1 grooves marked on
it from 0 to n. You are given an array containing numbers within the
range of 1 to n-1. These elements of the array represents the points
on the log at which u need to cut the wooden log. Now the cost of
cutting a log is proportional to the length of the original log being
cut.
Eg: n=15 and A={1,5,9}
Now when u make a cut at 1, the cost is n (the size of original log)
When u cut at 9, the cost will be n-1 as the length of the new
original log is 1 to n i.e n-1
When u cut at 5, since 5 lies between 1 and 9 and the length of this
log is 9-1=8, so the cost will be 8.
--
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: SPOJ PROBLEM
std::cout ∞ std::endl; taunt -- 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: top search queries
@Srikar In your first approach you cant simply ignore the queries that are not present in the heap because you have a stream of queries and you never know if the query that you are about to ignore is going be received frequently or not in future. Your approach is like find the top 100 queries from the stream and keep updating the frequencies of only those queries using heap and hash table. If you have to process some 1,00,000 , with a space for only 100 elements you cant find the frequencies correctly. this is a nice article related to this : http://www.americanscientist.org/issues/pub/the-britney-spears-problem On Tue, Feb 1, 2011 at 8:09 PM, sankalp srivastava richi.sankalp1...@gmail.com wrote: @guy above juver++ The solution , i don't think can get better than this , because you need to store the querries anyway (at least for the output ) -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to 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: SPOJ PROBLEM
does this has to do with floating point representation of numbers {IEE 754}
{single precision }
then the number would be
like
like for 32 bit field
put 0 in the sign field
all 1 in biased exponent field{8}
and all zeros in the mantissa field{23}
http://en.wikipedia.org/wiki/Single_precision_floating-point_format
also infinity is not equal to {1/machine tolerance=(2^-23)} for some
machines
one thing for sure is that
you can never come up with something bigger by adding one to {infinity}
and never subtract 1 from machine tolerance
correct me if i am wrong please
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: codechef problem
Don't answer this problem , it's from codechef February challenge ! On Feb 2, 6:11 pm, tech rascal techrascal...@gmail.com wrote: In a plane given n points (x1,y1) (x2,y2)(xn,yn), find the the maximum number of collinear points. plz tell me the best way to do that. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Minimum positive-sum subarray
@above guy with cheers and all and snehal
the best way to prove wrong is by a test case , so ,
-1 -2 3 4
Ricky's solution will give the answer as 4 , while the answer is 7
@snehal .
[quote]if indices starting at 1
bothers you then take
P[i]= A[0] + A[1] + + A[i]
its one and the same thing.. [\Quote]
I'm really not that stupid to bother about an off-by-one error :-)
Your algo rephrased :-
P[i] = A[1] + A[2] + … + A[i]
so ,
P[1]=-1
P[2]=-3
P[3]=0
P[4]=4
Q[i].Value = P[i].
Q[i].Index = i
So ,
Q[1]=-1 , 1
Q[2]=-3 , 2
Q[3]=0 , 3
Q[4]=4 , 4
Now , as u said , let's sort it
new Q={{4 , 4} ,{0 , 3} ,{-1 , 1} ,{-3 , 3}}
You din mention anything after this , so I dunnoe what you plan up
from here . How are we going to get the answer {3 , 4 } from here ?
Now ,
On Feb 2, 10:06 pm, Ricky rajeevpo...@gmail.com wrote:
Hi you can try the following code snippet:
int array[] = {11, -12, 15, -3, 8, -9, 1, 8, 10, -2};
int length = 10;
int max = 0;
int current = 0;
for (int i = 0; i length; i++)
{
current += array[i];
max = max current ? max : current;
}
std::coutMax is : max;
Cheers!!
On Feb 2, 9:04 pm, snehal jain learner@gmail.com wrote:
@ above
didnt get you? why is the solution wrong? and if indices starting at 1
bothers you then take
P[i]= A[0] + A[1] + + A[i]
its one and the same thing..
On Wed, Feb 2, 2011 at 6:02 PM, sankalp srivastava
richi.sankalp1...@gmail.com wrote:
This solution is wrong , never has it been said that the indices will
occur from 1.i (if that is the case , you don't need to sort ,
just return the maximum /minimum sum obtained as a result)
The indices were b/w i..j such that 1=i=j=n
O(n) solution does not exist .The state space tree will have n! leaf
nodes(because there is some ordering on the input data , otherwise it
would have 2^n leaf nodes) .Traversing the tree will take O(log n!)
steps , or O(n log n)
In fact a slight modification to this , the subset sum problem id NP-
complete .
But with the Q[i] array , you can get the answer with simple recursion
( or bfs or state space search or dp ) .
On Feb 2, 1:33 pm, snehal jain learner@gmail.com wrote:
@ above
its nt any homework question.. i found it a good question... aftr
spending a
lot of time i came up with following solution
Given Input Array A
form the prefix sum array P of A.
i.e P[i] = A[1] + A[2] + … + A[i]
Now create another array Q of pairs (Value, Index)
such that
Q[i].Value = P[i].
Q[i].Index = i
Now sort that array Q, considering only Q[i].Value for comparison.
We get a new sorted array Q’ such that Q’[i].Value Q’[i].Index
Time complexity o( nlogn)
and my O(n) which i posted earlier is giving incorrect result in some
case..so ignore that..
so does there exist O(n) solution for it also.. i had tried a lot but
could
not figure out. but i think it should exist as there is for the other
variation..
On Tue, Feb 1, 2011 at 8:24 PM, sankalp srivastava
richi.sankalp1...@gmail.com wrote:
You should not post homework problems .
1)For divide and conquer :-
Read about interval trees , binary indexed trees , segments
trees .
Solve this using interval tree (By the time you solve a few
basic problems of interval tree , you would be able to figure out a
solution)
the function to calculate the parent will be
1) first check if the two are +ve
2) if yes , join both of them and also iterate on the sides left by
both , to see if you can include them also (You only need to see the
positive elements , no negative elements )
T(n)=2T(n/2)+O(n)
I gan explain in detail , please correct me if im wrong
Logic :- Basically in the subproblem , we would have founded the
maximum subarray in that well , subarray (short of words ) .So , if we
want to ,we can only increase the solution in the next subarray (the
second subproblem )
So , there will be three cases
Either the subarray , the most minimum sum in one of the subproblems
will be the answer
The answer will be from between the gap of the indices between the
solutions of the two subproblems
The answer will be any combination of the two
All these three can be checked in O(n) itself .
2)Using DP(I don't know how many dp (pure dp i mean) algorithms are in
O(nlog n) .Never heard of any with the pure dp approach and an n log n
solution )
DP(classical for maximum positive sum array ) can be done by going
through two loops
dp[i]= minimum positive sum for an array with index (last index =i )
p[i]= start index corresponding to this dp[i]
dp[i]= minimum sum condition ( for each ij )
update p[i] accordingly .Then
Re: [algogeeks] Re: Invitation for CodeCracker'11 , Online Coding Competition
Dude! There must be something wrong with your compilers!! It isn't even accepting a hello world program. it's giving a compilation error on that as well :-/ On Wed, Feb 2, 2011 at 9:49 PM, Umer Farooq the.um...@gmail.com wrote: How am I suppose to provide inputs? Input file names?? On Wed, Feb 2, 2011 at 1:25 PM, Nikhil Agarwal nikhil.bhoja...@gmail.comwrote: On Tue, Feb 1, 2011 at 7:42 PM, Umer Farooq the.um...@gmail.com wrote: Hello, it's really nice to see such a world wide online programming competition being organized after Google CJ. I have got a three questions 1- Can we use Dev C++ (which we have been using on windows platform). If we are allowed to use dev C++, then do we have to submit .cpp files only or .cpp and .dev files (both)? 2- Can we use java? Java is also a platform independent? 3- How many rounds are there? Will there be any on sight rounds? Check http://codecracker.in/faq.php?t=1296635105 .I hope this will solve all your confusions. On Tue, Feb 1, 2011 at 6:55 PM, Navin Agarwal navin0...@gmail.comwrote: @veenus : The contest is open to everyone, but only students are eligible for prizes. -- Navin Agarwal -- 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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Umer -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Invitation for CodeCracker'11 , Online Coding Competition
How am I suppose to provide inputs? Input file names?? On Wed, Feb 2, 2011 at 1:25 PM, Nikhil Agarwal nikhil.bhoja...@gmail.comwrote: On Tue, Feb 1, 2011 at 7:42 PM, Umer Farooq the.um...@gmail.com wrote: Hello, it's really nice to see such a world wide online programming competition being organized after Google CJ. I have got a three questions 1- Can we use Dev C++ (which we have been using on windows platform). If we are allowed to use dev C++, then do we have to submit .cpp files only or .cpp and .dev files (both)? 2- Can we use java? Java is also a platform independent? 3- How many rounds are there? Will there be any on sight rounds? Check http://codecracker.in/faq.php?t=1296635105 .I hope this will solve all your confusions. On Tue, Feb 1, 2011 at 6:55 PM, Navin Agarwal navin0...@gmail.comwrote: @veenus : The contest is open to everyone, but only students are eligible for prizes. -- Navin Agarwal -- 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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Invitation for CodeCracker'11 , Online Coding Competition
@Umer : can you send your code here? -- Navin Agarwal -- 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: top search queries
@algoose I see what you are saying. what do you propose? checking out your link now... On Thu, Feb 3, 2011 at 11:44 AM, Algoose chase harishp...@gmail.com wrote: @Srikar In your first approach you cant simply ignore the queries that are not present in the heap because you have a stream of queries and you never know if the query that you are about to ignore is going be received frequently or not in future. Your approach is like find the top 100 queries from the stream and keep updating the frequencies of only those queries using heap and hash table. If you have to process some 1,00,000 , with a space for only 100 elements you cant find the frequencies correctly. this is a nice article related to this : http://www.americanscientist.org/issues/pub/the-britney-spears-problem On Tue, Feb 1, 2011 at 8:09 PM, sankalp srivastava richi.sankalp1...@gmail.com wrote: @guy above juver++ The solution , i don't think can get better than this , because you need to store the querries anyway (at least for the output ) -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to 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: Minimum positive-sum subarray
@ above and the answer to your test case is not 7 its 4 only.. as we have to
find min sum...i think u r confusing between max sum and min sum..
On Thu, Feb 3, 2011 at 10:15 PM, snehal jain learner@gmail.com wrote:
oh sorry.. i saved the complete ans in my draft and posted half ( as i got
interrupted when i ws typing) and so sent incomplete reply,..
here is my complete solution. hope it works.. let me know..if it fails
somewhere.. though i have tried it... on some test cases
Given Input Array A
form the prefix sum array P of A.
i.e P[i] = A[1] + A[2] + ... + A[i]
Now create another array Q of pairs (Value, Index)
such that
Q[i].Value = P[i].
Q[i].Index = i
Now sort that array Q, considering only Q[i].Value for comparison.
We get a new sorted array Q' such that Q'[i].Value = Q'[i+1].Value
Now walk the array Q' and find the minimum positive value of Q'[i+1].Value
- Q'[i].Value, considering only those i for which Q'[i+1].Index
Q'[i].Index
Time complexity o( nlogn)
On Thu, Feb 3, 2011 at 6:58 PM, sankalp srivastava
richi.sankalp1...@gmail.com wrote:
@above guy with cheers and all and snehal
the best way to prove wrong is by a test case , so ,
-1 -2 3 4
Ricky's solution will give the answer as 4 , while the answer is 7
@snehal .
[quote]if indices starting at 1
bothers you then take
P[i]= A[0] + A[1] + + A[i]
its one and the same thing.. [\Quote]
I'm really not that stupid to bother about an off-by-one error :-)
Your algo rephrased :-
P[i] = A[1] + A[2] + … + A[i]
so ,
P[1]=-1
P[2]=-3
P[3]=0
P[4]=4
Q[i].Value = P[i].
Q[i].Index = i
So ,
Q[1]=-1 , 1
Q[2]=-3 , 2
Q[3]=0 , 3
Q[4]=4 , 4
Now , as u said , let's sort it
new Q={{4 , 4} ,{0 , 3} ,{-1 , 1} ,{-3 , 3}}
You din mention anything after this , so I dunnoe what you plan up
from here . How are we going to get the answer {3 , 4 } from here ?
Now ,
On Feb 2, 10:06 pm, Ricky rajeevpo...@gmail.com wrote:
Hi you can try the following code snippet:
int array[] = {11, -12, 15, -3, 8, -9, 1, 8, 10, -2};
int length = 10;
int max = 0;
int current = 0;
for (int i = 0; i length; i++)
{
current += array[i];
max = max current ? max : current;
}
std::coutMax is : max;
Cheers!!
On Feb 2, 9:04 pm, snehal jain learner@gmail.com wrote:
@ above
didnt get you? why is the solution wrong? and if indices starting at 1
bothers you then take
P[i]= A[0] + A[1] + + A[i]
its one and the same thing..
On Wed, Feb 2, 2011 at 6:02 PM, sankalp srivastava
richi.sankalp1...@gmail.com wrote:
This solution is wrong , never has it been said that the indices
will
occur from 1.i (if that is the case , you don't need to sort ,
just return the maximum /minimum sum obtained as a result)
The indices were b/w i..j such that 1=i=j=n
O(n) solution does not exist .The state space tree will have n! leaf
nodes(because there is some ordering on the input data , otherwise
it
would have 2^n leaf nodes) .Traversing the tree will take O(log n!)
steps , or O(n log n)
In fact a slight modification to this , the subset sum problem id
NP-
complete .
But with the Q[i] array , you can get the answer with simple
recursion
( or bfs or state space search or dp ) .
On Feb 2, 1:33 pm, snehal jain learner@gmail.com wrote:
@ above
its nt any homework question.. i found it a good question... aftr
spending a
lot of time i came up with following solution
Given Input Array A
form the prefix sum array P of A.
i.e P[i] = A[1] + A[2] + … + A[i]
Now create another array Q of pairs (Value, Index)
such that
Q[i].Value = P[i].
Q[i].Index = i
Now sort that array Q, considering only Q[i].Value for comparison.
We get a new sorted array Q’ such that Q’[i].Value Q’[i].Index
Time complexity o( nlogn)
and my O(n) which i posted earlier is giving incorrect result in
some
case..so ignore that..
so does there exist O(n) solution for it also.. i had tried a lot
but
could
not figure out. but i think it should exist as there is for the
other
variation..
On Tue, Feb 1, 2011 at 8:24 PM, sankalp srivastava
richi.sankalp1...@gmail.com wrote:
You should not post homework problems .
1)For divide and conquer :-
Read about interval trees , binary indexed trees ,
segments
trees .
Solve this using interval tree (By the time you solve a
few
basic problems of interval tree , you would be able to figure
out a
solution)
the function to calculate the parent will be
1) first check if the two are +ve
2) if yes , join both of them and also iterate on the sides left
by
both , to see if you can include
Re: [algogeeks] Re: Minimum positive-sum subarray
Hi Richi,
Thanks for finding the problem. I forgot to add one condition:
Please have a look on the following code. I hope this will solve the
problem.
int array[] = {-1,-2,3,4};
int length = 4;
int max = 0;
int current = 0;
for (int i = 0; i length; i++)
{
current += array[i];
if (current 0 )
{
current = 0;
}
max = max current ? max : current;
}
std::coutMax is : max;
Thanks Regards,
Ricky
On Thu, Feb 3, 2011 at 6:58 PM, sankalp srivastava
richi.sankalp1...@gmail.com wrote:
@above guy with cheers and all and snehal
the best way to prove wrong is by a test case , so ,
-1 -2 3 4
Ricky's solution will give the answer as 4 , while the answer is 7
@snehal .
[quote]if indices starting at 1
bothers you then take
P[i]= A[0] + A[1] + + A[i]
its one and the same thing.. [\Quote]
I'm really not that stupid to bother about an off-by-one error :-)
Your algo rephrased :-
P[i] = A[1] + A[2] + … + A[i]
so ,
P[1]=-1
P[2]=-3
P[3]=0
P[4]=4
Q[i].Value = P[i].
Q[i].Index = i
So ,
Q[1]=-1 , 1
Q[2]=-3 , 2
Q[3]=0 , 3
Q[4]=4 , 4
Now , as u said , let's sort it
new Q={{4 , 4} ,{0 , 3} ,{-1 , 1} ,{-3 , 3}}
You din mention anything after this , so I dunnoe what you plan up
from here . How are we going to get the answer {3 , 4 } from here ?
Now ,
On Feb 2, 10:06 pm, Ricky rajeevpo...@gmail.com wrote:
Hi you can try the following code snippet:
int array[] = {11, -12, 15, -3, 8, -9, 1, 8, 10, -2};
int length = 10;
int max = 0;
int current = 0;
for (int i = 0; i length; i++)
{
current += array[i];
max = max current ? max : current;
}
std::coutMax is : max;
Cheers!!
On Feb 2, 9:04 pm, snehal jain learner@gmail.com wrote:
@ above
didnt get you? why is the solution wrong? and if indices starting at 1
bothers you then take
P[i]= A[0] + A[1] + + A[i]
its one and the same thing..
On Wed, Feb 2, 2011 at 6:02 PM, sankalp srivastava
richi.sankalp1...@gmail.com wrote:
This solution is wrong , never has it been said that the indices will
occur from 1.i (if that is the case , you don't need to sort ,
just return the maximum /minimum sum obtained as a result)
The indices were b/w i..j such that 1=i=j=n
O(n) solution does not exist .The state space tree will have n! leaf
nodes(because there is some ordering on the input data , otherwise it
would have 2^n leaf nodes) .Traversing the tree will take O(log n!)
steps , or O(n log n)
In fact a slight modification to this , the subset sum problem id NP-
complete .
But with the Q[i] array , you can get the answer with simple
recursion
( or bfs or state space search or dp ) .
On Feb 2, 1:33 pm, snehal jain learner@gmail.com wrote:
@ above
its nt any homework question.. i found it a good question... aftr
spending a
lot of time i came up with following solution
Given Input Array A
form the prefix sum array P of A.
i.e P[i] = A[1] + A[2] + … + A[i]
Now create another array Q of pairs (Value, Index)
such that
Q[i].Value = P[i].
Q[i].Index = i
Now sort that array Q, considering only Q[i].Value for comparison.
We get a new sorted array Q’ such that Q’[i].Value Q’[i].Index
Time complexity o( nlogn)
and my O(n) which i posted earlier is giving incorrect result in
some
case..so ignore that..
so does there exist O(n) solution for it also.. i had tried a lot
but
could
not figure out. but i think it should exist as there is for the
other
variation..
On Tue, Feb 1, 2011 at 8:24 PM, sankalp srivastava
richi.sankalp1...@gmail.com wrote:
You should not post homework problems .
1)For divide and conquer :-
Read about interval trees , binary indexed trees ,
segments
trees .
Solve this using interval tree (By the time you solve a few
basic problems of interval tree , you would be able to figure out
a
solution)
the function to calculate the parent will be
1) first check if the two are +ve
2) if yes , join both of them and also iterate on the sides left
by
both , to see if you can include them also (You only need to see
the
positive elements , no negative elements )
T(n)=2T(n/2)+O(n)
I gan explain in detail , please correct me if im wrong
Logic :- Basically in the subproblem , we would have founded the
maximum subarray in that well , subarray (short of words ) .So ,
if we
want to ,we can only increase the solution in the next subarray
(the
second subproblem )
So , there will be three cases
Either the subarray , the most minimum sum in one of the
subproblems
will be the answer
The answer will be from between the gap
Re: [algogeeks] Re: SPOJ PROBLEM
@juver++
Is the sign you printed anywhere on keyboard ?
how can u use it ??
i got AC althoughis there any *ALTERNATIVE SOLUTION *
On Thu, Feb 3, 2011 at 8:26 PM, rahul rai raikra...@gmail.com wrote:
does this has to do with floating point representation of numbers {IEE 754}
{single precision }
then the number would be
like
like for 32 bit field
put 0 in the sign field
all 1 in biased exponent field{8}
and all zeros in the mantissa field{23}
http://en.wikipedia.org/wiki/Single_precision_floating-point_format
also infinity is not equal to {1/machine tolerance=(2^-23)} for some
machines
one thing for sure is that
you can never come up with something bigger by adding one to {infinity}
and never subtract 1 from machine tolerance
correct me if i am wrong please
--
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.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to 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: Minimum positive-sum subarray
@ Snehal,
Yes you are right, I wrote function for finding max sub array. It can be
converted to find min sub array by just switching the comparison operator :)
On Fri, Feb 4, 2011 at 12:14 AM, snehal jain learner@gmail.com wrote:
@ Above
u r finding maximum sum subarray
whereas question is asking for minimum
On Thu, Feb 3, 2011 at 11:34 PM, Rajiv Podar rajeevpo...@gmail.comwrote:
Hi Richi,
Thanks for finding the problem. I forgot to add one condition:
Please have a look on the following code. I hope this will solve the
problem.
int array[] = {-1,-2,3,4};
int length = 4;
int max = 0;
int current = 0;
for (int i = 0; i length; i++)
{
current += array[i];
if (current 0 )
{
current = 0;
}
max = max current ? max : current;
}
std::coutMax is : max;
Thanks Regards,
Ricky
On Thu, Feb 3, 2011 at 6:58 PM, sankalp srivastava
richi.sankalp1...@gmail.com wrote:
@above guy with cheers and all and snehal
the best way to prove wrong is by a test case , so ,
-1 -2 3 4
Ricky's solution will give the answer as 4 , while the answer is 7
@snehal .
[quote]if indices starting at 1
bothers you then take
P[i]= A[0] + A[1] + + A[i]
its one and the same thing.. [\Quote]
I'm really not that stupid to bother about an off-by-one error :-)
Your algo rephrased :-
P[i] = A[1] + A[2] + … + A[i]
so ,
P[1]=-1
P[2]=-3
P[3]=0
P[4]=4
Q[i].Value = P[i].
Q[i].Index = i
So ,
Q[1]=-1 , 1
Q[2]=-3 , 2
Q[3]=0 , 3
Q[4]=4 , 4
Now , as u said , let's sort it
new Q={{4 , 4} ,{0 , 3} ,{-1 , 1} ,{-3 , 3}}
You din mention anything after this , so I dunnoe what you plan up
from here . How are we going to get the answer {3 , 4 } from here ?
Now ,
On Feb 2, 10:06 pm, Ricky rajeevpo...@gmail.com wrote:
Hi you can try the following code snippet:
int array[] = {11, -12, 15, -3, 8, -9, 1, 8, 10, -2};
int length = 10;
int max = 0;
int current = 0;
for (int i = 0; i length; i++)
{
current += array[i];
max = max current ? max : current;
}
std::coutMax is : max;
Cheers!!
On Feb 2, 9:04 pm, snehal jain learner@gmail.com wrote:
@ above
didnt get you? why is the solution wrong? and if indices starting at
1
bothers you then take
P[i]= A[0] + A[1] + + A[i]
its one and the same thing..
On Wed, Feb 2, 2011 at 6:02 PM, sankalp srivastava
richi.sankalp1...@gmail.com wrote:
This solution is wrong , never has it been said that the indices
will
occur from 1.i (if that is the case , you don't need to sort ,
just return the maximum /minimum sum obtained as a result)
The indices were b/w i..j such that 1=i=j=n
O(n) solution does not exist .The state space tree will have n!
leaf
nodes(because there is some ordering on the input data , otherwise
it
would have 2^n leaf nodes) .Traversing the tree will take O(log n!)
steps , or O(n log n)
In fact a slight modification to this , the subset sum problem id
NP-
complete .
But with the Q[i] array , you can get the answer with simple
recursion
( or bfs or state space search or dp ) .
On Feb 2, 1:33 pm, snehal jain learner@gmail.com wrote:
@ above
its nt any homework question.. i found it a good question... aftr
spending a
lot of time i came up with following solution
Given Input Array A
form the prefix sum array P of A.
i.e P[i] = A[1] + A[2] + … + A[i]
Now create another array Q of pairs (Value, Index)
such that
Q[i].Value = P[i].
Q[i].Index = i
Now sort that array Q, considering only Q[i].Value for
comparison.
We get a new sorted array Q’ such that Q’[i].Value Q’[i].Index
Time complexity o( nlogn)
and my O(n) which i posted earlier is giving incorrect result in
some
case..so ignore that..
so does there exist O(n) solution for it also.. i had tried a lot
but
could
not figure out. but i think it should exist as there is for the
other
variation..
On Tue, Feb 1, 2011 at 8:24 PM, sankalp srivastava
richi.sankalp1...@gmail.com wrote:
You should not post homework problems .
1)For divide and conquer :-
Read about interval trees , binary indexed trees ,
segments
trees .
Solve this using interval tree (By the time you solve a
few
basic problems of interval tree , you would be able to figure
out a
solution)
the function to calculate the parent will be
1) first check if the two are +ve
2) if yes , join both of them and also iterate on the sides
left by
both , to see if you can include them also (You only need to
see the
positive elements , no negative elements )
T(n)=2T(n/2)+O(n)
I gan explain in detail , please correct me if im wrong
Re: [algogeeks] Re: Minimum positive-sum subarray
@ rajiv
but there are conditions that sum should be positive and greater than
zero... so just reversing sign wont work..
On Fri, Feb 4, 2011 at 12:22 AM, Rajiv Podar rajeevpo...@gmail.com wrote:
@ Snehal,
Yes you are right, I wrote function for finding max sub array. It can be
converted to find min sub array by just switching the comparison operator :)
On Fri, Feb 4, 2011 at 12:14 AM, snehal jain learner@gmail.comwrote:
@ Above
u r finding maximum sum subarray
whereas question is asking for minimum
On Thu, Feb 3, 2011 at 11:34 PM, Rajiv Podar rajeevpo...@gmail.comwrote:
Hi Richi,
Thanks for finding the problem. I forgot to add one condition:
Please have a look on the following code. I hope this will solve the
problem.
int array[] = {-1,-2,3,4};
int length = 4;
int max = 0;
int current = 0;
for (int i = 0; i length; i++)
{
current += array[i];
if (current 0 )
{
current = 0;
}
max = max current ? max : current;
}
std::coutMax is : max;
Thanks Regards,
Ricky
On Thu, Feb 3, 2011 at 6:58 PM, sankalp srivastava
richi.sankalp1...@gmail.com wrote:
@above guy with cheers and all and snehal
the best way to prove wrong is by a test case , so ,
-1 -2 3 4
Ricky's solution will give the answer as 4 , while the answer is 7
@snehal .
[quote]if indices starting at 1
bothers you then take
P[i]= A[0] + A[1] + + A[i]
its one and the same thing.. [\Quote]
I'm really not that stupid to bother about an off-by-one error :-)
Your algo rephrased :-
P[i] = A[1] + A[2] + … + A[i]
so ,
P[1]=-1
P[2]=-3
P[3]=0
P[4]=4
Q[i].Value = P[i].
Q[i].Index = i
So ,
Q[1]=-1 , 1
Q[2]=-3 , 2
Q[3]=0 , 3
Q[4]=4 , 4
Now , as u said , let's sort it
new Q={{4 , 4} ,{0 , 3} ,{-1 , 1} ,{-3 , 3}}
You din mention anything after this , so I dunnoe what you plan up
from here . How are we going to get the answer {3 , 4 } from here ?
Now ,
On Feb 2, 10:06 pm, Ricky rajeevpo...@gmail.com wrote:
Hi you can try the following code snippet:
int array[] = {11, -12, 15, -3, 8, -9, 1, 8, 10, -2};
int length = 10;
int max = 0;
int current = 0;
for (int i = 0; i length; i++)
{
current += array[i];
max = max current ? max : current;
}
std::coutMax is : max;
Cheers!!
On Feb 2, 9:04 pm, snehal jain learner@gmail.com wrote:
@ above
didnt get you? why is the solution wrong? and if indices starting at
1
bothers you then take
P[i]= A[0] + A[1] + + A[i]
its one and the same thing..
On Wed, Feb 2, 2011 at 6:02 PM, sankalp srivastava
richi.sankalp1...@gmail.com wrote:
This solution is wrong , never has it been said that the indices
will
occur from 1.i (if that is the case , you don't need to sort ,
just return the maximum /minimum sum obtained as a result)
The indices were b/w i..j such that 1=i=j=n
O(n) solution does not exist .The state space tree will have n!
leaf
nodes(because there is some ordering on the input data , otherwise
it
would have 2^n leaf nodes) .Traversing the tree will take O(log
n!)
steps , or O(n log n)
In fact a slight modification to this , the subset sum problem id
NP-
complete .
But with the Q[i] array , you can get the answer with simple
recursion
( or bfs or state space search or dp ) .
On Feb 2, 1:33 pm, snehal jain learner@gmail.com wrote:
@ above
its nt any homework question.. i found it a good question...
aftr
spending a
lot of time i came up with following solution
Given Input Array A
form the prefix sum array P of A.
i.e P[i] = A[1] + A[2] + … + A[i]
Now create another array Q of pairs (Value, Index)
such that
Q[i].Value = P[i].
Q[i].Index = i
Now sort that array Q, considering only Q[i].Value for
comparison.
We get a new sorted array Q’ such that Q’[i].Value Q’[i].Index
Time complexity o( nlogn)
and my O(n) which i posted earlier is giving incorrect result in
some
case..so ignore that..
so does there exist O(n) solution for it also.. i had tried a
lot but
could
not figure out. but i think it should exist as there is for the
other
variation..
On Tue, Feb 1, 2011 at 8:24 PM, sankalp srivastava
richi.sankalp1...@gmail.com wrote:
You should not post homework problems .
1)For divide and conquer :-
Read about interval trees , binary indexed trees ,
segments
trees .
Solve this using interval tree (By the time you solve a
few
basic problems of interval tree , you would be able to figure
out a
solution)
the function to calculate the parent will be
1) first check if the two are +ve
2) if yes , join both of them and also iterate on the sides
left by
both , to see if
[algogeeks] Re: minimum no. of clicks
Hi, My approach:- 3 1 2 1 4 1 2 1 4 3 2 1) Find matching element from start and end. here it willl be 3 2) Perfrom (#1) for sub array 1 2 1 4 1 2 1 4 here it will be 2 1 4 1 2 4 left out 3) Perfrom (#1) on 2 1 4 1 2 here it will be 1 4 1 4) Perform (#1) on 1 4 1 here it will be 4 5) 4 is single element. discard it. @1 Now going to discard earlier found pairs..FROM INSIDE GOING OUT 6) 11 - discard @ 2 7) 22 - discard @ 3 8) 11 - discard @ 4 9) 4 - discard @5 10) 33 - discard @ 6 11) 2 - discard @ 7 Special coding.. :- 1) Consider 1 2 1 3 1 11 - subarrray 2 1 3 sent match not found. remember... last matching element.. which is 1. delete remainging single elements. in this case...from 2 1 3 ... 2 and 3 will be deleted.. 1 1 1 will be deleted.. 3 clicks for 5 elements... On Feb 3, 1:42 am, sourabh jakhar sourabhjak...@gmail.com wrote: this solution is wrong On Wed, Feb 2, 2011 at 12:41 AM, bittu shashank7andr...@gmail.com wrote: @ its again the question related to the frequency..of number My Approach would be we have to count the no. of time the a particular number occurring in the array then first took the number which has lowest frequency in case of Tie FCFS used up. then proceed to higher frequency number that represents the continuous chunks so that how much elements this chunks it has we can remove this in a single click so on so for this 3 1 2 1 4 3 1 2 1 4 3 2 here array of 4 elements Elements 1 2 3 4 ///also lets say we are initializing the array index as 1 Index 1 2 3 4 Frequency 4 3 3 2 we first process the 4 Click Required 1 then 2 Click Required 1 then 3 Click Required 1 then 1 Click Required 1 Total Click Required =4 so It Can be done in O(n) while space O(n) is penalty we have to pay for it...more better approach will be appreciated Correct me if you Find Approach is wrongs Thanks Regrads Shashank Mani The best way to escape from a problem is to solve it. -- 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.comalgogeeks%2Bunsubscribe@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- SOURABH JAKHAR,(CSE)(3 year) ROOM NO 167 , TILAK,HOSTEL 'MNNIT ALLAHABAD The Law of Win says, Let's not do it your way or my way; let's do it the best way. -- 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: SPOJ PROBLEM
It is unicode I think. -- 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.
