Thanks Dave, Don and all others for this clarification.
On Mon, Dec 12, 2011 at 11:23 PM, Prakash D cegprak...@gmail.com wrote:
only the number of comparisons is log(n)
On Mon, Dec 12, 2011 at 11:04 PM, Ankur Garg ankurga...@gmail.com wrote:
Agree with dave..Its still O(n)
On Mon, Dec
aal puzzle from techinterview. more then 50 % came from there .
--
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
Given an array-based heap on n elements and a real number x, efficiently
determine whether the kth smallest element in the heap is greater than or
equal to x. Your algorithm should be O(k) in the worst-case, independent of
the size of the heap.
This question was also asked in Amazon
--
You
We have apples arranged in a mxn matrix. We start from the upper left
corner and have to reach bottom right corner with maximum apples. We can
only move either down or right.
Now if we can start any where in the matrix and have to reach anywhere on
the right(reach n column). We can either up,
i thnk it can be done using dynamic programming..
let the array b
25 3
25 1
10 2 5
now at at every point in the matrix..there can be two ways..to reach that
point..either from left..or from right..
for example to reach at the center of the above matrix..we can come from
2-5-5 or
Graph
take up, right and bottom as nodes connected to current and do find
max path.
On Dec 13, 3:44 pm, Azhar Hussain azhar...@gmail.com wrote:
We have apples arranged in a mxn matrix. We start from the upper left
corner and have to reach bottom right corner with maximum apples. We can
only
On Tue, Dec 13, 2011 at 3:21 PM, hary rathor harry.rat...@gmail.com wrote:
aal puzzle from techinterview. more then 50 % came from there .
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
@aayush
Lots of member are here but that doesn't mean that you should start posting
the things which are strictly banned on this group. I hope you will take
care next time while posting anything in this group.
On Tue, Dec 13, 2011 at 7:40 PM, rahul sharma rahul23111...@gmail.comwrote:
On
actually there are infinite number of sequences that match it
for example if the absolute differences are 3 2 5 1
one possible sequence is 6 3 5 0 1 one other is 7 4 6 1 2 or 8 5 7 2 3
and you can add any integer value to all elements and the result will still
be valid
actually you can start with
1 is not a prime number!
On Mon, Oct 31, 2011 at 4:07 PM, mc2 . qlearn...@gmail.com wrote:
Hey guys ,
I am trying to solve this DP problem :
http://community.topcoder.com/stat?c=problem_statementpm=10033rd=13513
SRM 422, DIV 2 ,level 2.
Here is my DP solution. But it is not working.
After first iteration, adjacent similar characters are converted to
get a single character
After second iteration, similar adjacent strings of length 2 in the
remaining string are replaced with single string of length 2
After third iteration, similar adjacent strings of length 3 in the
remaining
@Amir: Presumably, since these are digits in a number, they are
bounded on the bottom by 0 and on the top by radix-1. So in decimal,
if a digit is 7 and the absolute difference between it and the next
digit is 3, there is only one possibility for the next digit, 7-3 = 4,
since 7+3 is too large. So
which other group u people are talking about, i would like to join that
group.
On Tue, Dec 13, 2011 at 9:21 PM, sunny agrawal sunny816.i...@gmail.comwrote:
@aayush
Lots of member are here but that doesn't mean that you should start
posting the things which are strictly banned on this group. I
O(k) in the worst-case , then i guess it would better to use
median-of median algo to find element at rank k. and comparing with x.
or
we can us hashtable to solve this.
On Tue, Dec 13, 2011 at 3:23 PM, Ankur Garg ankurga...@gmail.com wrote:
Given an array-based heap on n elements and a real
The following is a dynamic programming solution to this problem.
It builds up an array num[i][j] such that num[i][j] is the number of
combinations of digits starting with digit j at position i.
The answer is the sum of num[1][1]..num[9][1].
#include stdio.h
int main(int argc, char* argv[])
{
If pairwise sums of 'n' numbers are given in non-decreasing order
identify the individual numbers. If the sum is corrupted print -1
Example:
i/p:
4
4 5 7 10 12 13
o/p:
1 3 4 9
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this
http://groups.google.com/group/interview-street
On Tue, Dec 13, 2011 at 10:19 PM, tech coder techcoderonw...@gmail.comwrote:
which other group u people are talking about, i would like to join that
group.
On Tue, Dec 13, 2011 at 9:21 PM, sunny agrawal sunny816.i...@gmail.comwrote:
@aayush
The following is a dynamic programming solution to this problem.
It builds up an array num[i][j] such that num[i][j] is the number of
combinations of digits starting with digit j at position i.
The answer is the sum of num[1][1]..num[9][1].
#include stdio.h
int main(int argc, char* argv[])
{
I tried the problem and written the code for it . it is in java. it is
printing all the possible numbers
I am treating the differences ans an array of integers.
here is the code
public class Main {
public static void main(String[] args)
{
int digit[]={3,2,5,1};// array of
One other observation: if any of the absolute differences was zero, it
would print the same number more than once.
Your algorithm is fine for n=5, but as n gets larger, the execution
time increases exponentially. The dynamic programming algorithm is
O(n).
Don
On Dec 13, 11:37 am, tech coder
thanks don , i got it , it was due the condition in if expression .
modified code
i have highlighted the change
public class Main {
public static void main(String[] args)
{
int digit[]={3,2,5,1};
for(int num=1;num=9;num++)
findNumber(digit,4,num,0,num);
}
To get a abs difference of 0 there are 10 ways
similarly getting abs difference of 1 there are 9x2 ways(w1)
for 2 its 8x2 (say w(2)
for 3 its 7x2
.
for 9 its 1x2(w9)
let w(i) represents the number of ways to get abs diff of i.
So total numbers that are possible from the given abs diff i j k
i am not sure , but this came to me when i first read it
here is the idea:-
given : 4 5 7 10 12 13
4 should be there boz it is the least.
next is 5 , 5-4 =1 which is less that 4 , so 1 should be there
next is 7 , 7-4 = 3 which is less than 4 , so 3 should be there
next is 10 , 10-4 = 6 which
Moheed,
If n=3 and absdiff = {0,0}, your program says that there are 100
possible numbers. Can you show me at least 10 of them?
Don
On Dec 13, 12:24 pm, Moheed Moheed Ahmad mohe...@gmail.com wrote:
To get a abs difference of 0 there are 10 ways
similarly getting abs difference of 1 there are
When the difference is 0, the numbers will be repeated:
000, 111, 222, 333, 444, 555, 666, 777, 888, 999 but only these are
possible.
Gaurav
On Tue, Dec 13, 2011 at 10:47 AM, Don dondod...@gmail.com wrote:
Moheed,
If n=3 and absdiff = {0,0}, your program says that there are 100
possible
@atul:
Suppose the input is :(7,8,9)
So output should be (3,4,5)
then ur approach is not giving the answers..
Regards,
Sayan
On Tue, Dec 13, 2011 at 11:51 PM, atul anand atul.87fri...@gmail.comwrote:
i am not sure , but this came to me when i first read it
here is the idea:-
given : 4 5 7
I am just trying to understand the number of ways we can form this number,
lets say d is the absolute difference between the numbers and the length of
the numbers is n. Lets say we are considering base 10 numbers, so lets say
radix r = 10.
if you try to see all the comparisons, here is what
Why can't we keep removing the minimum element each time and compare it
with x? This should take O(k) time since in a Min heap, the minimum element
can be removed in O(1) time? Am I missing something?
On Tue, Dec 13, 2011 at 8:43 AM, atul anand atul.87fri...@gmail.com wrote:
O(k) in the
That gives an answer of 40,320, but the correct answer is 39. You
can't multiply all of those values together and expect to get the
right answer. There are not 14 possible values for the first digit,
and if there were, for any particular value of the first digit there
are not 16 possible values
On Tue, Dec 13, 2011 at 12:40 PM, Don dondod...@gmail.com wrote:
That gives an answer of 40,320, but the correct answer is 39. You
can't multiply all of those values together and expect to get the
right answer. There are not 14 possible values for the first digit,
and if there were, for any
Thanks for pointing out the issue with my logic. What I am wondering is
what is the general solution to finding the number of possible numbers? Is
the only way is to try these combinations? Please share if you know.
Gaurav
On Tue, Dec 13, 2011 at 1:56 PM, Gaurav Kumar gkuma...@gmail.com wrote:
Trying the combinations is not necessary. See my solution above.
Don
On Dec 13, 3:59 pm, Gaurav Kumar gkuma...@gmail.com wrote:
Thanks for pointing out the issue with my logic. What I am wondering is
what is the general solution to finding the number of possible numbers? Is
the only way is to
hmmm i guess i screwed by taking least element as a part of the output set
directly.
On Wed, Dec 14, 2011 at 12:57 AM, sayan nayak sayanna...@gmail.com wrote:
@atul:
Suppose the input is :(7,8,9)
So output should be (3,4,5)
then ur approach is not giving the answers..
Regards,
Sayan
in above case we need to do some checking like in case when next element is
10;
next elements is 10
10-4 = 6 , 6 4
add(1,3,4 ) = 8
8 10(required_element) , so add 1 to 8 = 9 and do same as mentioned
but if sum( number_found_so_far ) required_num then add 1 to difference
of required_num -
@Gene : considering m-of-m algo , one thing that worries me is that using
m-of-m for huge data is not good bcoz when practically implementing it
constant would be very large so as to make it work for O(N)
here is the reason why is not a good approach for huge data :-
reccurence eqn for m-of-m is
Thanks Don for pointing it out. It will not work [the second and
consecutive abs-diffs are not mutually exclusive].
However, here are the 10 possible numbers that will work for n=3 and
absdiff={0,0}:
0 0 0
1 1 1
2 2 2
--
8 8 8
9 9 9
-Moheed
'If a man neglects education, he walks lame to the
@gaurav : you need to first build heap and then maintain heap property ever
time you remove element.so this would take O(n logn ).
On Wed, Dec 14, 2011 at 1:38 AM, Gaurav Kumar gkuma...@gmail.com wrote:
Why can't we keep removing the minimum element each time and compare it
with x? This
how is the case taken of when 2 pairs add to the same sum?...
On Tue, Dec 13, 2011 at 11:35 AM, atul anand atul.87fri...@gmail.comwrote:
hmmm i guess i screwed by taking least element as a part of the output set
directly.
On Wed, Dec 14, 2011 at 12:57 AM, sayan nayak
@Atul: The initial heap is given. You have to maintain the heap
property as k elements are removed, which is O(k log n). This does not
satisfy the original request for an algorithm that is O(k) in the
worst-case, independent of the size of the heap.
Dave
On Dec 13, 10:31 pm, atul anand
39 matches
Mail list logo
