@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 wrote:
@Moheed: 0 is not a three-digit number. By convention, we do not print
leading zeros except in the units position. Thus, there are only 9
three digit numbers with absdiff={0,0}.
Dave
On Dec 13, 12:58 pm, Moheed Moheed Ahmad wrote:
> Thanks Don for pointing it out. It will not work [the second an
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 wrote:
> 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 wrote:
>
>> @atul:
>> Suppose the inpu
@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 wrote:
> Why can't we keep removing the minimum element each time and compare it
> with x? This should take O(k) time
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 en
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 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
>
> On Tue, D
Trying the combinations is not necessary. See my solution above.
Don
On Dec 13, 3:59 pm, Gaurav Kumar 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 try these combin
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 wrote:
>
>
> On Tue, Dec 1
On Tue, Dec 13, 2011 at 12:40 PM, Don 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 particular value
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 for
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 wrote:
> O(k) in the worst-case , then i guess it w
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 holds
@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 wrote:
> 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 shou
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 wrote:
> Moheed,
> If n=3 and absdiff = {0,0}, your program says that there are 100
> possible numbers. Can you show
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 wrote:
> To get a abs difference of 0 there are 10 ways
> similarly getting abs difference of 1 there are 9x2 ways(w1)
> for
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 i
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 l
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);
}
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 wro
There should be 39 combinations with that input. You are missing
numbers which include the digit zero, such as 14610, 30278, and 52056.
Don
On Dec 13, 11:37 am, tech coder wrote:
> I tried the problem and written the code for it . it is in java. it is
> printing all the possible numbers
> I am
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 absolu
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
int main(int argc, char* argv[])
{
int
http://groups.google.com/group/interview-street
On Tue, Dec 13, 2011 at 10:19 PM, tech coder wrote:
> 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 wrote:
>
>> @aayush
>> Lots of member are here but that doesn't
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 g
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
int main(int argc, char* argv[])
{
int
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 wrote:
> Given an array-based heap on n elements and a real number x, efficiently
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 wrote:
> @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
@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
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 st
1 is not a prime number!
On Mon, Oct 31, 2011 at 4:07 PM, mc2 . wrote:
> Hey guys ,
> I am trying to solve this DP problem :
> http://community.topcoder.com/stat?c=problem_statement&pm=10033&rd=13513
> SRM 422, DIV 2 ,level 2.
>
> Here is my DP solution. But it is not working. Can someone pl
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 a
@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 wrote:
>
>
> On Tue, Dec 13, 2011 at 3:2
On Tue, Dec 13, 2011 at 3:21 PM, hary rathor 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 algogeeks@googlegroups.com.
>
Graph
take up, right and bottom as nodes connected to current and do find
max path.
On Dec 13, 3:44 pm, Azhar Hussain 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 move either dow
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 o
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, d
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 rece
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
algogeeks+unsubscr
Thanks Dave, Don and all others for this clarification.
On Mon, Dec 12, 2011 at 11:23 PM, Prakash D wrote:
> only the number of comparisons is log(n)
>
>
> On Mon, Dec 12, 2011 at 11:04 PM, Ankur Garg wrote:
>
>> Agree with dave..Its still O(n)
>>
>>
>> On Mon, Dec 12, 2011 at 10:57 PM, Dave w
41 matches
Mail list logo
