This problem has been discussed before @
http://groups.google.co.in/group/algogeeks/browse_thread/thread/9c1e1aa8cf1ed437/d451cd9468d985f7
I believe, the problem can't be solved in O(n) but only in O(nlog n).
@Divya: Are you sure the interviewer explicitly asked for an O(n) time
algorithm?
On
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Shishir Mittal
Ph: +91 9936 180 121
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com
On Mon, Oct 12, 2009 at 1:29 PM, ankur aggarwal ankur.mast@gmail.comwrote:
@shishir
can u give the ds
data structure used is a binary tree, with each node key being the maximum
of its two children's key values.
Space complexity of implementation of tournament principle is O(n).
how would
anyone give me algorithm for finding the second largest element in
array using tournament method requiring n+logn-2 compariso
--
Shishir Mittal
Ph: +91 9936 180 121
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
doesn't provide correct results. Try to dry run
the code for some more test cases like ( 4 3 2 1) , ( 3 1 3 2).
Refer Introduction to Algorithms, II Ed. (Cormen) Exercise 9.1-1 and the
preceding discussion for more info regarding tournament principle.
--
Shishir Mittal
Ph: +91 9936 180 121
and then highest among the
number which get defeated during tournament.
(details in corment).
Can anyone do code implemenation for this one.
Thanks
Nagendra
--
Shishir Mittal
Ph: +91 9936 180 121
--~--~-~--~~~---~--~~
You received this message because
the highest number and then highest among the
number which get defeated during tournament.
(details in corment).
Can anyone do code implemenation for this one.
Thanks
Nagendra
--
Shishir Mittal
Ph: +91 9936 180 121
--~--~-~--~~~---~--~~
You received
;
int ar[n];
for(i=0;in;i++)
cinar[i];
res=sec_largest(ar,n);
coutsecond largest number=resendl;
}
--
Shishir Mittal
Ph: +91 9936 180 121
--~--~-~--~~~---~--~~
You received this message because you
.
What algorithm can be used to decide how to break up the entered
amount?
--
Shishir Mittal
Ph: +91 9936 180 121
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send
]+1.
In the proposed algorithm, searching for minimum element is done using min
heap.
--
Shishir Mittal
Ph: +91 9936 180 121
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post
A correction in the proposed algorithm.
On Tue, Sep 15, 2009 at 1:08 PM, Shishir Mittal 1987.shis...@gmail.comwrote:
*Algorithm.*
1) Corresponding to each element in X, create a node with 2 values, to be
compared indexed of Y, and the corresponding sum.
NODE[i] = {yIndex, sum = X[i
smallest
no of Z in O(n) time.
Space complexity : No bound on it. But try to optimize it if possible.
--
Shishir Mittal
Ph: +91 9936 180 121
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group
0
--
hence 43 + 14 = 111001 = 57
--
Shishir Mittal
Ph: +91 9936 180 121
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks
is
minimum.
--
Shishir Mittal
Ph: +91 9936 180 121
--~--~-~--~~~---~--~~
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
) for O(n) space case.
the first 5 elements is the required answer.
Overall worst case time complexity : O(n), space complexity : O(1).
O(n) space simplifies the coding and understanding of the problem.
On Tue, Sep 1, 2009 at 6:04 PM, ankur aggarwal ankur.mast@gmail.comwrote:
@shishir
i could
of.
--
Shishir Mittal
Ph: +91 9936 180 121
--~--~-~--~~~---~--~~
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
wrote:
Given a set S of n distinct numbers and a positive integer k = n.
Determine the k numbers in S that are closest to the median of S.
Find an O(n) algorithm
--
Shishir Mittal
Ph: +91 9936 180 121
--~--~-~--~~~---~--~~
You received this message
--
Shishir Mittal
Ph: +91 9936 180 121
--~--~-~--~~~---~--~~
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
There were some errors in my solution.
On Thu, Aug 27, 2009 at 6:10 PM, Shishir Mittal 1987.shis...@gmail.comwrote:
Its a bit similar to finding the rank of the word COMPUTER in the
dictionary among the words formed from C,O,M,P,U,T,E,R.
Find maximum r such that (k+r)C(r) n
det(A) ! = 0 , for inverse to exist.
--~--~-~--~~~---~--~~
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
@Kapil
How do you intend to do a BFS in a linked list (its not a Bin Tree i
suppose or a graph)
@Pramod
Can you please detail as to what does your program do?
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
. I guess you already are aware of the
changes required in there.
~Shishir
--~--~-~--~~~---~--~~
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
Thanks Narvi, for the idea. A simple counter at the start of the tree
insertion keeping track of the strength of the tree, would be all that
is required.
~Shishir
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
/ \
27 54
/ \ / \
23 42
For eg in the above case the next node should be inserted as the left
most child of 54.
Let me know if there's any doubt regarding the question.
~Shishir
--~--~-~--~~~---~--~~
You received
Well, I was aware of BFS solution , but am looking for something more
elegant than this. Does, any other method exist to do this.
Thanks for your reply anyways
~Shishir
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google
@Karas
Can you please take some time to brief us about the algo of your
program.
Thanks,
~Shishir
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email
void sort(int arr[])
{
for(int i = 0, j = 0; iarr.length ;j++)
if(arr[j])
{
arr[i]=1;
arr[j]=0;
i++;
}
}
This should work, the only think I doubt is whether it qualifies as a
single pass or not, coz i have two variables i,j in the for loop.
Errata: Should be j in place of i in the condition statement of the for
loop.
and arr[j]=0 should come before arr[i]=0;
Here's the correct code.
void sort(int arr[])
{
for(int i = 0, j = 0; jarr.length ;j++)
if(arr[j])
{
arr[j]=0;
arr[i]=1;
i++;
}
}
I think the best possible thing is to do an insertion sort(using
another stack)/bubble sort.
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
sorry ! didn't get 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 [EMAIL
HI,
how do you intend to use hash ( as in which hash function) to check if
the hash keys generated for both A and B are equal.
Thanks,
Shishir
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group
Given an array of integers and a number N, find if there exists a
consecutive series of numbers in this array which sum up to N.
Regards,
Shishir
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks
There's a small error in my formula. The formula holds for a NxM grid
(N horizontal and M vertical lines) where N= n+1 and M = m+1, which
essentially boils down to
C(N+M-2, N-1) = C(N+M-2,M-1).
This should work fine.
-Shishir
--~--~-~--~~~---~--~~
You received
Well the formula works only for the corner end points as starting and
ending node and that too on the diagonal ends.
Its not a general formula for any set of starting/ending nodes.
@Dhyanesh
I think the problem clearly states that the nodes can only be traversed
once i.e. no repetition.
Hi,
This is a standard MS interview question.
Give an O(n) algorithm to find the subset of an array A[n] with largest
sum.
Anticipating a healthy and useful discussion on this.
Thanks,
Shishir
--~--~-~--~~~---~--~~
You received this message because you
Yes, am sorry, its infact the continous sub-sequence which I missed
in the question.
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
36 matches
Mail list logo
