Re: [algogeeks] Search an element in an Infinite array
@Saurabh There is no biggest number in an infinite array [?]
On 25 October 2011 09:07, saurabh singh saurab...@gmail.com wrote:
suppose the element doesn't lies in the array and is bigger than the
biggest number:D
everything will fail...
On Mon, Oct 24, 2011 at 9:43 PM, ravindra patel
ravindra.it...@gmail.comwrote:
using power of 2 approach doubles the scope of search each time.
How about using approximation. Say I have lower bound lb and upper bound
ub. Now -
initially lb = 0, ub = 1;
while (a[ub] k)
{
lb = ub;
ub = (ub*k) / a[ub];
}
after end of this loop we'll have a lower bound and upper which should
provide a narrow scope.
Feedback welcome :-),
- Ravindra
On Mon, Oct 24, 2011 at 7:09 PM, Bittu Sarkar bittu...@gmail.com wrote:
@Ankur Don't think there's any major reason for using powers of 2 except
the fact that computing the powers of 2 can be done very efficiently than
computing the powers of any other number. Complexity in any case remains the
same.
On 24 October 2011 10:29, rahul sharma rahul23111...@gmail.com wrote:
+1 ankur
On Mon, Oct 24, 2011 at 1:26 AM, Ankur Garg ankurga...@gmail.comwrote:
Use Binary Search
start = 2^n-1 high =2^n where n=0,1
On Mon, Oct 24, 2011 at 12:28 AM, sunny agrawal
sunny816.i...@gmail.com wrote:
hint 1: try to find 2 indexes i, j such that a[i] = K = a[j]
On Sun, Oct 23, 2011 at 11:23 PM, Ankuj Gupta ankuj2...@gmail.comwrote:
Given a sorted array of Infinite size, find an element ‘K’ in the
array without using extra memory in O (lgn) time
--
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.
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
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.
--
Bittu Sarkar
5th Year Dual Degree Student
Department of Computer Science Engineering
Indian Institute of Technology Kharagpur
--
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.
--
Saurabh Singh
B.Tech (Computer Science)
MNNIT ALLAHABAD
--
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.
--
Bittu Sarkar
5th Year Dual Degree Student
Department of Computer Science Engineering
Indian Institute of Technology Kharagpur
--
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.
329.gif
Re: [algogeeks] adobe question help
N = (N | ((1(j-i+1)-1)i) (Mi); On 12 October 2011 01:22, prasad jondhale jondhale.pra...@gmail.com wrote: grt -- 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. -- Bittu Sarkar 5th Year Dual Degree Student Department of Computer Science Engineering Indian Institute of Technology Kharagpur -- 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] Search an element in an Infinite array
@Saurabh I think you did not get the question clearly. It's
a theoretical question because in practice you cannot have an infinite
length array of non-decreasing numbers anyways. Yes the sequence 1,1,1,...
is infinite and the algorithm cannot just know all by itself what the
largest number is, just because it has processed millions of 1s. In this
case no algorithm can find the required number (1) in which case the
algorithm does not terminate.
On 25 October 2011 13:46, saurabh singh saurab...@gmail.com wrote:
Really?
the array is infinite length..
what if the sequence is 1,1,1,1,1,1,1,1...infinity?
We need to know the max in order the algorithm is terminating..
On Tue, Oct 25, 2011 at 11:32 AM, Bittu Sarkar bittu...@gmail.com wrote:
@Saurabh There is no biggest number in an infinite array [?]
On 25 October 2011 09:07, saurabh singh saurab...@gmail.com wrote:
suppose the element doesn't lies in the array and is bigger than the
biggest number:D
everything will fail...
On Mon, Oct 24, 2011 at 9:43 PM, ravindra patel
ravindra.it...@gmail.com wrote:
using power of 2 approach doubles the scope of search each time.
How about using approximation. Say I have lower bound lb and upper bound
ub. Now -
initially lb = 0, ub = 1;
while (a[ub] k)
{
lb = ub;
ub = (ub*k) / a[ub];
}
after end of this loop we'll have a lower bound and upper which should
provide a narrow scope.
Feedback welcome :-),
- Ravindra
On Mon, Oct 24, 2011 at 7:09 PM, Bittu Sarkar bittu...@gmail.comwrote:
@Ankur Don't think there's any major reason for using powers of 2
except the fact that computing the powers of 2 can be done very
efficiently
than computing the powers of any other number. Complexity in any case
remains the same.
On 24 October 2011 10:29, rahul sharma rahul23111...@gmail.comwrote:
+1 ankur
On Mon, Oct 24, 2011 at 1:26 AM, Ankur Garg ankurga...@gmail.comwrote:
Use Binary Search
start = 2^n-1 high =2^n where n=0,1
On Mon, Oct 24, 2011 at 12:28 AM, sunny agrawal
sunny816.i...@gmail.com wrote:
hint 1: try to find 2 indexes i, j such that a[i] = K = a[j]
On Sun, Oct 23, 2011 at 11:23 PM, Ankuj Gupta
ankuj2...@gmail.comwrote:
Given a sorted array of Infinite size, find an element ‘K’ in the
array without using extra memory in O (lgn) time
--
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.
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
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.
--
Bittu Sarkar
5th Year Dual Degree Student
Department of Computer Science Engineering
Indian Institute of Technology Kharagpur
--
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.
--
Saurabh Singh
B.Tech (Computer Science)
MNNIT ALLAHABAD
--
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
Re: [algogeeks] Search an element in an Infinite array
@Ankur Don't think there's any major reason for using powers of 2 except the fact that computing the powers of 2 can be done very efficiently than computing the powers of any other number. Complexity in any case remains the same. On 24 October 2011 10:29, rahul sharma rahul23111...@gmail.com wrote: +1 ankur On Mon, Oct 24, 2011 at 1:26 AM, Ankur Garg ankurga...@gmail.com wrote: Use Binary Search start = 2^n-1 high =2^n where n=0,1 On Mon, Oct 24, 2011 at 12:28 AM, sunny agrawal sunny816.i...@gmail.comwrote: hint 1: try to find 2 indexes i, j such that a[i] = K = a[j] On Sun, Oct 23, 2011 at 11:23 PM, Ankuj Gupta ankuj2...@gmail.comwrote: Given a sorted array of Infinite size, find an element ‘K’ in the array without using extra memory in O (lgn) time -- 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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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. -- Bittu Sarkar 5th Year Dual Degree Student Department of Computer Science Engineering Indian Institute of Technology Kharagpur -- 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] Search an element in an Infinite array
@Ankur I know that the complexity reduces from linear time (constant length
range checks) to logarithmic time (exponential length range checks). I was
just explaining the reason for not choosing any other number like say 3 to
compute the exponential ranges [3^(k-1)...3^k] in which case the complexity
still remains logarithmic.
On 24 October 2011 21:43, ravindra patel ravindra.it...@gmail.com wrote:
using power of 2 approach doubles the scope of search each time.
How about using approximation. Say I have lower bound lb and upper bound
ub. Now -
initially lb = 0, ub = 1;
while (a[ub] k)
{
lb = ub;
ub = (ub*k) / a[ub];
}
after end of this loop we'll have a lower bound and upper which should
provide a narrow scope.
Feedback welcome :-),
- Ravindra
On Mon, Oct 24, 2011 at 7:09 PM, Bittu Sarkar bittu...@gmail.com wrote:
@Ankur Don't think there's any major reason for using powers of 2 except
the fact that computing the powers of 2 can be done very efficiently than
computing the powers of any other number. Complexity in any case remains the
same.
On 24 October 2011 10:29, rahul sharma rahul23111...@gmail.com wrote:
+1 ankur
On Mon, Oct 24, 2011 at 1:26 AM, Ankur Garg ankurga...@gmail.comwrote:
Use Binary Search
start = 2^n-1 high =2^n where n=0,1
On Mon, Oct 24, 2011 at 12:28 AM, sunny agrawal
sunny816.i...@gmail.com wrote:
hint 1: try to find 2 indexes i, j such that a[i] = K = a[j]
On Sun, Oct 23, 2011 at 11:23 PM, Ankuj Gupta ankuj2...@gmail.comwrote:
Given a sorted array of Infinite size, find an element ‘K’ in the
array without using extra memory in O (lgn) time
--
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.
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
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.
--
Bittu Sarkar
5th Year Dual Degree Student
Department of Computer Science Engineering
Indian Institute of Technology Kharagpur
--
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.
--
Bittu Sarkar
5th Year Dual Degree Student
Department of Computer Science Engineering
Indian Institute of Technology Kharagpur
--
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: Directi Questions - needed answers
Q7. Correct answer is 12km west and 12km south for sure!!
On 21 September 2011 13:28, Nitin Garg nitin.garg.i...@gmail.com wrote:
Ohh i totally missed that line.
Thanx a lot :)
On Wed, Sep 21, 2011 at 10:46 AM, pankaj agarwal
agarwal.pankaj.1...@gmail.com wrote:
@Nitin Garg
Question 6 -
i agree that greater the sum is and greater the probability to getting it.
but in given question if sum100 then rolling is stopped
so for
P(106)=P(100)*1/6
P(105)=P(100)*1/6+P(99)*1/6
.
.
.
P(101)=P(100)*1/6+P(99)*(1/6)+P(98)*(1/6)+P(97)*(1/6)+..+P(95)*(1/6)
now P(101) is more
cleare me if something is wrong.
On Mon, Sep 19, 2011 at 1:35 PM, Nitin Garg nitin.garg.i...@gmail.comwrote:
Question 6 -
Intuitively you can see that the greater the sum is, the greater the
favorable events in sample space.
e.g. - sum = 1 .. cases {(1)} Pr = 1/6
sum = 2 cases {(2),(1,1)} Pr = 1/6 + 1/36
sum = 3cases {(3),(2,1)(1,2)(1,1,1)} Pr = 1/6 + 1/36 +1/36 +
1/216
for a more formal proof, look at the recursion -
P(k) = (P(k-6) + P(k-5) + P(k-4)... P(k-1)))/6
where P(0) = 1, P(i) = 0 for i0
Base case -
P(2) P(1)
Hypothesis -
P(i) P(i-1) for all i = k
To prove
P(k+1) P(k)
Proof
P(k+1) - P(k) = (P(k) - P(k-6))/6 0
--
Pankaj Agarwal
Communication and Computer Engineering
LNMIIT,jaipur
--
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.
--
Nitin Garg
Personality can open doors, but only Character can keep them open
--
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.
--
Bittu Sarkar
5th Year Dual Degree Student
Department of Computer Science Engineering
Indian Institute of Technology Kharagpur
--
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] Amazon Question - Find Pythagorean triplet in an unsorted array
@rahul It still will be O(n^2) time complexity On 14 October 2011 15:14, Ankur Garg ankurga...@gmail.com wrote: @Rahul Pls elaborate with an example ... On Fri, Oct 14, 2011 at 2:35 PM, rahul patil rahul.deshmukhpa...@gmail.com wrote: You can take advantage of a basic property of triagle that sum of largest side of triangle sum of other two sides, After sorting you could easily deside the range in which possible solution could be found for a chosen hypotenuse On Fri, Oct 14, 2011 at 11:10 AM, ravindra patel ravindra.it...@gmail.com wrote: @Wladimir, yeah I have heard about that. Another way of populating primitive pythagoreans is, for any natural number m 1 (m^2 - 1, 2m, m^2 + 1) forms a pythagorean triplet. This is useful in populating pythagorean tiplets but here the problem is to search such triplets from a given int array. @ rahul, Hash of z^2 - x^2 for each pair of z,x itself will of the size n*(n-1). I am not sure how it will work in O(n) time then. Thanks, - Ravindra On Fri, Oct 14, 2011 at 12:25 AM, Ankur Garg ankurga...@gmail.comwrote: @rahul...How do u choose z and x for computing z^2 -x^2 ? On Thu, Oct 13, 2011 at 11:34 PM, rahul rahul...@gmail.com wrote: You can create a hash with sqrt(z2-x2). This will make it o(n). The interviewer just made it lil tricky. That's all -- 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/-/2Ge2pjt4N-4J. 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. -- Regards, Rahul Patil -- 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. -- Bittu Sarkar 5th Year Dual Degree Student Department of Computer Science Engineering Indian Institute of Technology Kharagpur -- 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: plz explain if the solution is possible with less than 2n-3 comparisons??
@shiv here we go
to find 2nd best player in array
Tournament tree is a form of min (max) heap which is a complete binary
tree. Every external node represents a player and internal node
represents winner. In a tournament tree every internal node contains
winner and every leaf node contains one player.maxheap is winner tree
min heap is looser tree.
There will be N – 1 internal nodes in a binary tree with N leaf
(external) nodes.
It is obvious that to select the best player among N players, (N – 1)
players to be eliminated, i.e. we need minimum of (N – 1) games
(comparisons). Mathematically we can prove it. In a binary tree I = E
– 1, where I is number of internal nodes and E is number of external
nodes. It means to find maximum or minimum element of an array, we
need N – 1 (internal nodes) comparison. its simple fact of
mathematics.
The method is tournament algorithm. The idea is to conduct a knockout
minimal round tournament to decide the ranks. It first organises the
games (comparisons) between adjacent pairs and moves the winners to
next round until championship (the first best) is decided. It also
constructs the tournament tree along the way. Now the second best
element must be among the direct losers to winner and these losers can
be found out by walking in the binary tree in O(log n) time. It
organises another tournament to decide the second best among these
potential elements. The third best must be one among the losers of the
second best in either of the two tournament trees. The approach
continues until we find k elements. This algorithm takes O(n + k log
n) complexity, which for any fixed k independent of n is O(n).
for example check it let say we have array a={5,3,8,7} we have build
given tournament tree using above algo
8(Winner)
/ \
5 8 to find 2nd best we have to choose the
path by winner in 2nd last step ??
/ \ / \
5 3 8 7
its clear that 1st max or min element can't be done in less then O(N)
in an unsorted array isn't it ?
now to find the 2nd best choose the pat of direct looser to winner
then go through this path until we reach to leaf , as leaf nodes
always be player compare them maximum will be 2nd maximum here try
out it for different example so what the total number of comparisons
to find 1xt maximum its n-1 = O(N)
to find 2nd maximum logn-1=O(logn) as we start comparing after root
tottal number of comparisons is n-1+logn-1=n+logn-2
let me know if i missed something ??
Thanks
Shashank Mani
Computer Science Engg.
Birla Institute of Technology Mesra
--
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: Adding w/o +
Check the last post of this http://groups.google.com/group/algogeeks/browse_thread/thread/95a593375c62c31d/bf5fab1c88f4b491?lnk=raot#bf5fab1c88f4b491 Thanks Shashank Mani Computer Science Birla Institute of Technology Mesra -- 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: Improve upon O(m^2)
@dumanshu check it
Algo is simply start putting elemnt in bigger array by comparing then
from last logic is same as merge part of merg sort :)
void merge(int[] a, int[] b, int n, int m)
{
int k = m + n - 1; // Index of last location of array b
int i = n - 1; // Index of last element in array b
int j = m - 1; // Index of last element in array a
// Start comparing from the last element and merge a and b
while (i = 0 j = 0)
{
if (a[i] b[j])
{
a[k--] = a[i--];
}
else
{
a[k--] = b[j--];
}
}
while (j = 0)
{
a[k--] = b[j--];
}
//no need to do for a array as its alraedy filled in B array :)
}
Time O(N)
Thanks
Shashank Mani Narayan
Computer Science Engg.
Birla Institute of Technlogy Mesra
--
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: Search node in a binary tree
whats the problem with this
bool search(root,node)
{
if(root==node)
return 1;
else
return search(root-left,node)||search(root-right,node);
}
TC O(N)
notify me via mail if anything wrong.?
Thanks
Shashank
CSE,BIT Mesra
--
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: Image based Problem (Google)
too store this whole image we need 2^70==10^21 bytes size of disk. assuming each pixel take 1 byte . always go metadata for large entities .here metadata includes type(e.g jpeg,bmp,gif etc),size,name,pointer to log file entry etc. Shashank CSE,BIT Mesra -- 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: sbtration
Lets Try For Decimal Integer Number how we add them
1 Add 759 + 674, but “forget” to carry I then get 323
2 Add 759 + 674 but only do the carrying, rather than the addition of
each digit I then
get 1110
3 Add the result of the first two operations (recursively, using the
same process de-
scribed in step 1 and 2): 1110 + 323 = 1433
we have done for decimal numbers
Now, how would we do this in binary?
1 If I add two binary numbers together but forget to carry, bit[i]
will be 0 if bit[i] in a and
b are both 0 or both 1 This is an XOR
2 If I add two numbers together but only carry, I will have a 1 in
bit[i] if bit[i-1] in a and b
are both 1’s This is an AND, shifted
3 Now, recurse until there’s nothing to carry
int add_no_arithm(int a, int b)
{
if (b == 0) return a;
int sum = a ^ b; // add without carrying
int carry = (a b) 1; // carry, but don’t add return
add_no_arithm(sum, carry); // recurse
}
Subtraction uses add function internally as well as we have adder !!!
int sub(int x, int y)
{
return(add(x,add(~y,1));
}
Thanks
Shashank Mani
Computer Science
Birla Institute of Technology Mesra
--
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: remove duplicate chars in a string without using extra memory
whats the problem ? if no extra memory allowed then can't be done in better then O(nlogn)sorting time O(1) space else it will take O(N) time O(N) Space sorting will change the order but using bitmap or bitarray order will be preserved Thanks Shashank CSE,BIT Mesra -- 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: linked list doubt
now try how u will remove the loop from linked list Shashank CSE BIT Mesra -- 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: How to store largest N values efficiently
John You Can Use MinHeap here is the algo 1) Build a Min Heap MH of the first k elements (arr[0] to arr[k-1]) of the given array. O(k) 2) For each element, after the kth element (arr[k] to arr[n-1]), compare it with root of MH. a) If the element is greater than the root then make it root and call heapify for MH b) Else ignore it. O((n-k)*logk) 3) Finally, MH has k largest elements and root of the MH is the kth largest element. Time Complexity: O(k + (n-k)Logk) without sorted output. If sorted output is needed then O(k + (n-k)Logk + kLogk) Thanks Shashank Computer Science Birla Institute of Technology Mesra -- 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: Bipartite Matching?
@nishit whats the problem with Bipartite Matching ist perfect example of Bipartite Graph isn't it ?? as have to just divide the set of vertex in to two disjoint set such that no two people who are friends will be in same team that what Bipartite Matching says ?? although graph coloring will also work here as u said in last we have to return all the nodes in even level odd leve by combining into two disjoints set ..it will be automatically disjoints .. Shashank Mani CSE, BIT Mesra -- 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: Amazon - Longest palindrome in a string in O(n)
i have posted some time back but that is O(N) , need to code suffix tree will do that asap i get the time. Thanks Shashank CSE BIT Mesra -- 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: Amazon - Longest palindrome in a string in O(n)
sorry for typo that is O(N^2) 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: given a bst and a value x.find pair of nodes in the tree that sum upto x
@Dave I Think So We Can Construct In the same we construct singly linked list ton BST . 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: MS
lets take the example {1,2, 10, 2, 3, 5, 1, 1,2,3,5,2} clearly min
distance is 1 between a=2 b=5
take variables current=-1 min=INT_Max
so we start from last element say its index is last which is array
size -1 check it with a b if its equal to any of these then check
current !=- a[current]!=a[last] if its true then compare min with
min current-last update the min e.g min=minimum(min,current-last)
set current=n; repeat until we run out of loop
so function looks like
minDistance (int a[], int n, int b, int c)
{
int ret = INT_MAX, cur rent= -1;
while(n--)
{
if(a[n] == b || a[n] == c) {
if(cur rent!= -1 a[current] != a[n]) {
min = minimum(min, current - n);
}
current = n//upodate current
}
Thanks
Shashank Mani
CSE, BIT Mesra
--
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: Amazon - max substring
use suffix array time will be O(N) e.g. in case of banana answer will be ana you can find more info here http://shashank7s.blogspot.com/2011/06/longest-repeated-substring-eg-maximum.html Thanks Shashank I Don't Do Code to Code But I Do Code to Build Product Computer Science Engineering Birla Institute of Technology,Mesra -- 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: Yahoo Question
1.Use Haddop Map Reduce Framework .Obviously We Need Distributed Algo we will make one computer as master assign the job to all slave computer to do the crawling the web depending upon the geographic area ( m thinking real time problem).to crawled the maximum pages in least time we need above framework or any other distributed framework like google map reduce or GFS. computers are given for maximizing the crawling function minimizing the the crawling time time.. Algorithmically you ca think of its like a graph which has 100 connected components in it we will bfs to traverse each computer to find out the number of pages it has been crawled till now. i have given some overview hope it will help Thanks Shashank I Don't Do Code to Code But I Do Code to Build Product Computer Science Engineering Birla Institute of Technology,Mesra -- 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: Amazon telephonic question
@juver++ correct @ankit you can see here 1st Approach . You can implement this by having each node in the stack keep track of the minimum beneath itself. Then, to find the min, you just look at what the top element thinks is the min.When you push an element onto the stack, the element is given the current minimum. It sets its “local min” to be the min. The disadvantage of above algo is that if we have a large stack, we waste a lot of space by keeping track of the min for every single element. 2nd Approach(Use Two Stack) so We can (maybe) do a bit better than this by using an additional stack which keeps track of the mins. it is also good If many elements have the same local min, then we’re keeping a lot of duplicate data. so when we will push the value then we will push in 2nd stack as well. while popping if value is equal to min then we will remove it from 2nd stack. Hope It Will Help.:) Thanks Shashank I Don't Do Code to Code But I Do Code to Build Product Computer Science Engineering Birla Institute of Technology,Mesra -- 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: Queue using a stack
@ashish Dude you can Have a Look http://shashank7s.blogspot.com/2011/04/wap-to-implement-queue-using-stack.html do notify me if we can optimize the solution..:) Thanks Shashank I Don't Do Code to Code But I Do Code to Build Product Computer Science Engineering Birla Institute of Technology,Mesra -- 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: MS Q
@harshal every thing seems to be correct m not sure if things will mess up but can we do it in 1 pass ..?? Shashank CSE,BIT Mesra Cracking The Code shashank7s.blogspot.com -- 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: MS Q
@ross i think u mean s[i]==g[b[i]] or s[i]==g[i] then hit++ isn't it u r not using guess at all as u r comparing character with digit correct me if m wrong Shashank CSE,BIT Mesra -- 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: Sorting an array - using the foll functions
@ ross yes its pancake sorting,although i have code using insertion sort O(N^2) , we can use quick sort to achieve O(nlogn) click here http://shashank7s.blogspot.com/2011/03/pancake-sorting.html Feel Free to Comment Thanks Shashank CSE,BIT Mesra -- 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: Finding shortest path in 4-ary tree
I think BFS will do That isn't it.?? lets say we have starting node v wants to find shortest path e.g leaf at lowest height say this node u so when you will do BFS each level will represent the shortest path between two nodes. shortest path=min dist(V,U) DS Used Queue Time Complexity O(N) Correct me if anything wrong Shashank Computer Science CSE,BIT Mesra -- 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] Find shortest substring that is only occurring once. in Given String
I found one interesting question Given a string s , return the shortest substring that is only occurring once. Examples: s=aabbabbaab gives either bab or baa s= gives My Approaches Generate All Possible SubStrings O(N^2) puts all substrings into hashtable keep incrementing counter for each substring , return substring with counter 1 memory O(N) Not efficient Create Suffix Tree Seems to be Efficient Solution Only You Need to do Create Tree then we can find the shortest substring that is only occurring once. in O(n) time PS: let me other approaches,suggestion Thanks Shashank CSE,BIT Mesra -- 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: solve the series
@sunny. ..lol..dude..20 June is My Bro's B'day 18th Nov is of My mom ...:P Shashank Computer Science Engg. Birla Institute of Technology, Mesra -- 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 Question
@Nate...Both TinyUrl Bit.ly Fails in case of our web address is less then length of their(tinyurl/bit.ly) names.. example if u will try http://www.a.com/a (num of chars 18) in tinyurl.com it will convert http://tinyurl.com/cl3nc4 which 25 chars long surly greater then original url length so these service are not good for small length of urls..its my observation so their purpose to make large url into tiny they are surely either using hash function of base 36(26chars=10 digits) or base 62 chars (26+26+10) in case of case sensitive as A is differ from a or they are using random number generation by converting between 0 to 10. if we need all possible shortest url possible then we can count ascii chars of base 256 or unicode characters. as we know each url is unique in world of internet. every long URL is associated with a unique key, which is the part after http://top-level domain name/mypage.html , for example http://tinyurl.com/m3q2xt has a key of m3q2xt. so basically we have to generate the unique key as shown in example from string after top level domain so hash function obvious choice as urls are unique key will be unique for example www.google.com/abc www.google.com/bac will generate different key thus unique any other approach 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Google Question
well i can speak much on these question.as these algorithms are part of web crawler ..but do u mean we have to detect the duplicate files, by file having same size are duplicates..?? also same question raised by me few days back Detecting Duplicate Documents but no one seems to interested u can search previous threads.. 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Google Question
i also thought its relative to database but ultimately it also depends on the data structure Algorithms used by database to implement the particularly query. The simpler implementation of this service is to store, in a database table, a data pair (id, url) where your id has the autoincrement option, e.g. 1 - www.facebook.com 2 - www.otherurl.com/path/complete/to/the/page.php 3 - ... so on So when a user ask for http://tinyurlservice.com/1 you simply do a select into your table (select url from urlstable where id = '1') and then you do a redirect to that url. You could refine this, looking before if a certain url was already 'tinyurled' (so you prevent multiple insertions of the same url), you could add a date field in your table and delete the older entries with a stored procedure or with a cronjob or with an admin panel... and so on. 1 have another approach using temp. array of all chars that a url can contains will explorer later.. Hope this will be useful for you., Correct me if anything wrong Thanks Shashank CSE,BIT Mesra -- 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: Facebook
First of all i would like to describe the what an event it is.. so In computing an event is an action that is usually initiated outside the scope of a program and that is handled by a piece of code inside the program. I Would Like to Add Some Points modify the above algo so that it can be coded in multi-threaded environment.because once any one see this algo he will definitely ask whether your code is able to run in multi- threaded environment or not..?? because it might be possible in single minute several threads may initiates the event in parallel because there is no condition that is stopping thread to execute the common piece of program that can be shared b/w them as thread share common part of process. .so there is more chances to loss of integrity of data . hope you know race condition.Also a global variable can also create linking (external reference resolution ) problem in addition to global variable can be modified by any thread.at any time. so basically what i am talking about some kind of synchronization is needed above can can be re-implemented in multi-threaded environment to resolve above problem so that 1) we can Record all Events (For the sake of simplicity, treat the Event as an integer code) generated by threads 2) Return the number of Events recorded in the last one minute by all threads 3) Return the number of Events recorded in the last one hour by all threads. so these are the few points on which we can further discuss with interviewer to show him awareness about multi thread environment.the basic approach given by ankit is fine from my points of view with only overhead of shifting ?? for open ended question if we don't have enough space to store an event then we can divided the space required by event in multiples of memory available isn't it..?? Correct me if anything i explained seems to be wrong or if you wants to add something more. Thanks Shashank CSE BIT Mesra -- 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: Array Merge Problem
@sravanreddy...logical bugs if A is size of n B is size m from your example assuming nm so if you want smallest m elements in A then u only capacity of n elements didn't allocate memory so these elements initialized by INT_MIN for m-n nodes so that array A can hold m smallest elements then what r u swapping u dude..isn't garbage value ?? you will get at 1st step only just run it ?? in you algo A_End=m-1(which 4th position in Array that DNE)..?? also you have to free memory for m-n in array B as it contains n largest elements . take A= 1,2,3 n=3 B= 0,1,4,5,9 m=5 after allocating memory to Array A for m-n elements A will looks likes 1 2 3 INT_Max INT_Max now what you wants A should contains m smallest elements B have n largest elements so O/P should be A=1,2,3,1,0 B=INT_Max,INT_Max,4,5,9 now free memory used by 1st elements in array B so that A will represent M smallest elements B will have n Largest elements so that above will work. Hope I am Correct let me know if any issue with explanation Thanks ShashankThe Best Way To Escape From The problem is To Solve It CSE,BIT Mesra -- 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: Odd Even Sort array
@subramania jeeva ..can we have example with explanation as algorithmic approach is fine..!!! 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: suitable data structure
@himnashu..Obvious Trie(Data Structure) is best in this case i will suggest you to study Trie deeply try it.. if you need more clarification, let me know 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Palindrome
you its similar kind of problems Already Solve few days back please check Previous threads. Small Modification needed in previous solution .except cost not calculated but all possible palindrome have been generated so hope you can try that that will help .(Although its slightly Different Question) string s=radarradarradarradar here is link http://shashank7s.blogspot.com/2011/03/wap-to-find-all-possible-palindromes-in.html ( m not sure it will give exact thinking but it will give you approach Run Here https://ideone.com/7tihB 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: spoj--two squares problem
@ashish you forget one condition that c=x^2+y^2 iff c= 1 mod(4) e.g. c %4==1 also x!=y see above link its great simple. Thanks to Fermat Euler 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Find closest point
Hi don ..We can Approach Like this this..See we can assume earth as a Sphere there n points lies on that sphere so if any points lie on that it must satisfy equation of sphere. okk.. then find the distance of all the points from the center of sphere find the distance of location form center . the find minimum of all the distance with location ...see its mathematically approach..m hope we can solve these equation can get desired answer...i appreciate if u can throw some example ..that can make more clear PS: i am talking about relative minimum distance as i have calculated wrt center of sphere . i assume there is bug in my approach, will appreciate your suggestion ?? 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: AMAZON Q
@all geeks
I have already posted it 2-3 forums..here let me post it again its
O(n) but the basic idea is clear if got the problem stmt correct then
we have to find out the largest Fibonacci number that is small then
given number n so say if n=10 then should be 8
for n=13 i=8
n=14 i=13 similarly for all n13 n 21 i will 13 so on i don't why
so confusion ?? It Will Cover All Test Cases
#includestdio.h
int fib(int n)
{
int final=0,i,c,a=0,b=1;
for(i=2;in;i++)
{
c=a+b;
a=b;
b=c;
if(cn)
final=c;
}
return final;
}
int main()
{
int n=14;
printf( %d , fib(n));
}
TC O(n)
SC O(1)
Run Here https://ideone.com/aCli7
Optimization: To get the answer in O(logn) we can use matrix
representation of Fibonacci number check wiki.. if you wants O(logn)
then i can also post that..I hope m clear ..There are already 6 Way
Known to me to find nth Fibonacci Number
only thing necessary is that optmization .. Correct me if anything
wrong ???
Thanks
Shashank the Best Way To Escape From The problem is To Solve It
CSE,BIT Mesra
Reach Me +91-9739002481
--
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: AMAZON Q
@aakash...so above algo is fine working fine i forget to put else stmt after if otherwise unnecessary comparison so you can add if(finalc)then final=c else break; in above program will post O(logn) program soon 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: AMAZON Q
@piyuesh..i posted the naive because geeks are so confused about this quest. i have seen some geeks saying terrible time complexity of it. so above approach will make 1st of all every1clear optimization 2ndary step... As i have told earlier its similar to find nth Fibonacci number can be done in O(logn) using Matrix Representation that i also know will post later..its little modification of nth Fibonacci number. Thanks Shashank Reach Me +99-9739002481 -- 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 Q
Study Trie Then Apply It..It Will Work PS: We already have dictionary congaing all the possible words if its not given then we can make the dictionary then we can find out the all possible anagram of word in constant time O(K) where K is length of each anagram of word W. Hope i m correct Thanks Shashank The Best Way to Escape From The Problem is to Solve It CSE,BIT Mesra -- 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: Divide 2 nos. without DIVISON
I don't know u will be happy with this or not but let me explain in
simplest way
PS: i haven't used division operator anywhere but i also i haven't
done using Bit Logic which is efficient then this one but below code
work simplest way to understand
This One is the Simply Logical. This will work all kind of Inputs. The
concept behind this is We need to Perform the Reverse Operation
performed on the Mutiplication Without '*' Opreator. Here we need to
Subtract the Second Number From the First Number Until First Number =
Second Number. That’s All.
For example, Assume that a=10, b=3. Here we need to do is Subtract the
Number 3 from the number 10 itself, until a=b. And we should make a
count for how many times we are doing like this, It is the Quotient
Value.
So, finally We get the Answer as 3 Times we subtract 3 from the Number
10. Because we are checking the Condition a=b everytime. So the is
the Quotient as 3. The Remainder will be stored itself in 'a' as 1.
#include
#include
void main()
{
int a,b,c;
clrscr();
printf(Enter 2 No.s :\n);
scanf(%d%d,a,b); // Read 2 Numbers
if(b==0) // Here we are Checking for the Divide By Zero Error
{
printf(\nDivide By Zero Error);
}
else
{
c=0; // Here c as Count, and we should initialize the Count value to
0.
while(a=b) // We Repeatedly Checking for the Condition a=b
{
a = a - b; // Subtract b from a, and the new result stored in 'a'
itself
c++; // Incrementing the Count
}
printf(\nQuotient = %d \n Remainder = %d,c,a); // Print Quotient and
Remainder
}
getch();
}
Thanks
ShashankThe Best Way To Escape From The Problem is to Solve It
CSE,BIT Mesra
--
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: Application of Data Structure In Moview]
I think Hash-map With Separate Chaining Will be Best Where Key Will be Name of country value will be pointer to linked list that will hold all the scene Shooted in that country so hope it pretty clear that as we shooting scene randomly so whenever new scene Shooted put into bucket of Hash-map if starting pointer of linked is null else if scene from same country repeats again then add it to last or first its can be done O(1) repeat the same for remaining scene so when particular scene will be displayed just display it increment the corresponding pointer of bucket ..It just an approach we have to take care of out system requirement complexity Issue (time space) so in this case whenever collision occur string an item can be done in O(1) but retrying the item may take the time of length of linked list in particular bucket O(n) See There are several DS several way we can do insertion , searching, deletion operation in O(1) but not all of the same time but here is problem is that of associativity i mean every scene is associated with particular country Correct me if anything Wrong or Optimization or Suggest Any DS.that can perform both operation very fast ?? Thanks ShashankThe Best Way to Escape From The Problem is to Solve It CSE,BIT Mesra Reach Me:+91- 9739002481 -- 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: PUZZLE
@all you can find the better explanation here , hope it will help http://ashutosh7s.blogspot.com/2011/02/camel-and-banana.html feel free to comment if anything wrong Thanks Shashank Mani Best Way to Escape From Problem is to Solve It CSE,BIT Mesra -- 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] Application of Data Structure In Moview]
Which data structure is the most efficient to store and access movie shots. Say, when a movie song is shot, it may include 5 scenes from Switzerland,8 from malaysia, 6 from india etc. and these various scenes shot will be sequenced in the movie song in a random order. Example: When the movie song is to be played after compilation and editing, it will be in such an order: 1. 3rd scene of Malaysia 2. 1st scene of Switzerland 3. 6th scene of India 4. 7th scene of malaysia 5. 6th scene of Vienna 6. 1st scene of India etc. Such sequence will be huge in case of full movie. So, which data structure will be the most efficient to store such type of data and at the same time easily accessible? -- 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: Inversion Count
@all i have posted the solution of same problem few times back , search in group thread i used BST using that inversion count can be calculated in O(nlogn) if you found any error on that then let me know Thanks Shashank CSE,BIT Mesra -- 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: Run for a google years
@Dave... I think 1 Googol Year is =10^100 not 10^116.5 ?? why u have
used
so then we have to write the single line program that googol years of
time ?? we have processor that can execute the instruction in 10^9
per second so the time required by googol year in second
which is equals to time t=pow(10,109)*365*86400 sec.
so program is like
#include stdio.h
#include math.h
int main() {
double n = pow(10, 109) * 365 * 86400;
while(n--);
}
Correct me if anything wrong???
Thanks Regards
Shashank ManiThe Best Way To Escape From The problem is Solve It
Computer Science Engg.
BIT Mesra
--
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 INTERVIEW QUESTION
@all geeks ..check out the algo solution with detailed explanation here http://shashank7s.blogspot.com/2011/03/wap-to-find-all-possible-palindromes-in.html let me know if it will fail for any test cases Thanks Regards Shashank Mani The Best Way To Escape From The problem is Solve It Computer Science Engg. BIT Mesra -- 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: Amazon Interview Question
see here let me know if anything wrong..?? http://shashank7s.blogspot.com/2011/05/wap-to-find-minimum-difference-between.html Thanks Regrads Shashank the Best Way to Escape From The problem is to Solve it Computer Science Engg. BIT Mesra -- 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: Need the algorithm or idea
in hurryi will suggest you to study TRIE in Detail as Much as you can..Then you will not only get the idea but also you will able to implement see practical uses of Trie in computer Science Thanks Regards Shashank Mani -- 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] Efficient Way to Detect Duplicate Document
suppose You have a billion urls, where each is a huge page. How do you detect the duplicate documents? on what criteria you will detect it, what algorithm , approach , whats will be the complexity of each approach as it has many application in computer science ...i would like to have some good discussion on this topic Lets Explorer All The Approach ??? Thanks Regrads Shashank CSE, BIT Mesra -- 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: Do you Think Allocating memory to 2D Array is easy ???
although its right . basic , funny way to allocate the memory , but i was looking fro sum better way to do the same .. 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Problem regarding MySql server Installation
i forget to say that every tool has its own site for documentation help check it it out http://dev.mysql.com/doc/refman/5.5/en/default-privileges.html 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Problem regarding MySql server Installation
As i remeber you can do this on command prompt type i am assuming u have installed configured mysql mysql -u username -p password i think u shoud have google it Thanks Regards Shashank Mani The Best Way to escape Fromm problem is Solve It CSE,BIT Mesra -- 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] Do you Think Allocating memory to 2D Array is easy ???
Basically we have to implement function which allocates memory to a two dimensional array. we have to Minimize the number of calls to malloc and make sure that the memory is accessible by the notation arr[i][j]. .important part of the question is we have to implement the it using single call to MALLOC..its strictly means only 1 time ?? so make sure your not calling malloc more then 1 so lets make our hand dirty..?? Please Read Question Carefully... Thanks Regrads 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] JigSaw Puzzle
1 .Design The JizSaw Puzzle Object Oriented Design(OOD) 2 Design the data structures and explain an algorithm to solve the puzzle. No Code Needed, A Good Discussion Algorithmic, Complexity Discussion is Sufficient 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: number of inversions
HI i found that it Can Be Done Using BST in O(nlogn) see the
explaination then code , let me know if m wrong or anything mising
also tryvto dry run yourself
/*
Explanation
we are constructing BST from the array elements and maintaining a
count on each node. The idea here is every parent node must maintain
the number of nodes that branched on to it's right side (right count).
The above code fails if there are equal element which cause the count
to be incremented. Equal nodes won't participate in inversions. The
count (rc) will be used to track the number of inversions.each rc say
we have these no of inversion of this number.
However, when the array is reverse sorted, the tree will be fully
right skewed. While inserting i-th node, we need to visit previous
(i-1) nodes, so the worst case complexity is no better than O(n^2).
Where as merge sort procedure doesn't depend on data to be sorted.
What ever may be the permutation of input data, merge sort will sort
the array in O(NlogN) time, so the inversion count.
*/
#includeiostream
using namespace std;
struct node{
int data;
node *left;
node *right;
int rc;
};
node *root = NULL;
int get_inv(int val)
{
node *newnode = new node;
newnode - data = val;
newnode - left = NULL;
newnode - right = NULL;
newnode - rc = 0;
int inv = 0;
if(!root)
{
root = newnode;
return 0;
}
node *ptr = root;
node *pptr = root;
while(ptr)
{
pptr = ptr;
if(val ptr-data)
{
inv += ptr-rc +1;
ptr = ptr-left;
}
else
{
ptr-rc++;
ptr = ptr-right;
}
}
if(val pptr-data)
{
pptr-left = newnode;
}
else
{
pptr-right = newnode;
}
return inv;
}
int count_inv(int *array,int n)
{
int inv = 0;
for(int i=0;in;i++)
{
inv += get_inv(array[i]);
}
return inv;
}
int main()
{
int array[] = {3,6,1,2,4,5};
coutcount_inv(array,6)endl;
return 0;
}
Thanks Regards
Shashank Mani Narayan
Birla Institute of Technology,Mesra
Computer Science Engineering
--
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] Interesting...For Geeks ...Dictionary Question
Given a dictionary of millions of words, give an algorithm to find the largest possible rectangle of letters such that every row forms a word (reading left to right) and every column forms a word (reading top to bottom). Thanks Regards Shashank Mani CSE,BIT mesra -- 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: Facebook Interview Question....Heavy Number
@all , Nikhi Jindal ,.as i already told that O(n^2) Solution is Obvious ..but .it wont work for 1Biillion as a time limit exceeds , memory Error occur, so its not a good solution ..I think There is DP Solution Exist For Thats We Need to Figure it Out to resolve this problem @anand what r u trying to do bro...elaborate something more let me know if still have confusion ?? Thanks Regards Shashank Mani -- 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: Algo to identify loose ends of each cable in minimum time.
its the The Graham-Knowlton Problem in their paper this proble4ms i published is published goole it you will get answer explanation Thanks Regards Shashank Mani CSE, BIT Mesra -- 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] HI object oriented designing ebook with case study Needed
If Any1 has OOD ebook case study put the link here any good resources across the web or send directly to shashank7andr...@gmail.com if you can Thanks Regards Shashank Mani Computer Science Engineering BIT Mesra -- 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] Facebook Interview Question....Heavy Number
Hi Geeks, One of The My Friend had This Question in His Technical Round of Facebook, I m going to share with you.lest see how geek approach this...Plz don't make this post spam..by discussing whats ur friend name, wich colge, etc etc..just share your approach, think solve the question, even Google search wont give you correct efficient approach ,answer for this question..so think your self.. O(n^2) Solution is Obvious ..but .it wont work for 10 million as a limit so not a good solution we have to solve it using best approach algo..as we have so here is the question...From Facebook... /* A non-negative integer is called heavy if the average value of its digits in decimal representation exceeds 7. Assume that 0 has average value of its digits equal to 0. For example the number 8698 is heavy, because the average value of its digits equal to (8+6+9+8)/4 = 7.75. The number 53141 has the average value of its digits equal to (5+3+1+4+1)/5 = 2.6, so it is not heavy. Write a function int heavy_decimal_count(int a,int b); that given two non-negative integers A and B returns the number of heavy integers in the interval [A..B] (both ends included). Assume that 0 =A = B = 200,000,000 Range Given ..It Really Matters Your Program should not give time out memory error For example, given A=8,675 and B=8,689 the function should return 5, because there are 5 heavy integers in range [8,675..8,689]: 8675 avg=6.5 8676 avg=6.75 8677 avg=7 8678 avg=7.25HEAVY 8679 avg=7.5 HEAVY 8680 avg=5.5 8681 avg=5.75 8682 avg=6 8683 avg=6.25 8684 avg=6.5 8685 avg=6.75 8686 avg=7 8687 avg=7.25HEAVY 8688 avg=7.5 HEAVY 8689 avg=7.75HEAVY you have to keep in mind for given range e.g given B=2 Billion Its Man Thing so what happen when A=1 Billion B=2 Billion */ Go Ahead Thanks Regards Shashank Mani Cell 9740852296 -- 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: Microcontroller LED project
In Hurray but after seeing ur post,i can tell you, you make code in Assembly Lang. , u can use 8085 Microprocessor 51 micro-controller its very simple to code to display using assembly80 using 8085 ,i have done may programs in collage using 8085 assembly don't remember now,,hope it will help u..u have do some practice of 8085 assembly Thanks Regards Shashank Mani CSE,BIT Mesra -- 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: finds a pair of close numbers
Hi , Use Hashing for That , for sum =12 arr[]={2,4,3,6,5,8,7}; store
in to hashtable for each index=0 in loop find sum-arr[index] so
fro sum =12 if we do index=1 a[1]=4 sum-a[1]=8 so stop it we have
done..hope make d perfect code.
time Complxity o(n) space size of hashtable
Let me me if anything wrong ??
Thanks Regrads
Shashank The Best Way to Escape From The Problem is 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.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Application of Data Structure System Design
Pretend you work for a phone company. At your company, you have a satellite that routes phone calls. We want to bill customers by the maximum number of simultaneous phone calls they make in a single day. (After asking clarifying questions I received the following information: assume no calls last more than 24 hours and that at midnight each night all the calls are automatically dropped. In the event that one call ends as soon as another starts, answer part 2 of this question in such a way as to maximize revenue). What information should the satellite store for each phone call? Define a data structure for this (e.g. write a struct). Write a function that finds the maximum number of simultaneous phone calls from a given customer. (Hint: typical solution is O(nlogn), but if you use an absurd amount of memory like I did, it can be done in O(n)). 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Application of Data Structure System Design
Pretend you work for a phone company. At your company, you have a satellite that routes phone calls. We want to bill customers by the maximum number of simultaneous phone calls they make in a single day. ( clarifying questions with the following information: assume no calls last more than 24 hours and that at midnight each night all the calls are automatically dropped. In the event that one call ends as soon as another starts). What information should the satellite store for each phone call? Define a data structure for this (e.g. write a struct). Write a function that finds the maximum number of simultaneous phone calls from a given customer. (Hint: typical solution is O(nlogn), but if you use an absurd amount of memory it can be done in O(n)). Best Designing DS, Approach Will b highly Appreciated 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Ties The Rope With Minimum Cost ..Interesting For Geeks
@utkarsh i was just about to put Huffman algo ..yes it is optimized answer to solve the problem @all basicaly we have to minimize the cost of intermediate path ,final o/p will obvious be the same Try Huffman algo 1st read what it is..dan u will able to figure out soln of this problem Hope i am clear , if missing something , correct me Thanks Reagrds Shashank Mani CSE,BIT Mesra -- 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] Ties The Rope With Minimum Cost ..Interesting For Geeks
you are given n ropes,maybe of different length. the cost of tying two ropes is the sum of their lengths.Find a way to tie these ropes together so that the cost is minimum. 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Median of Binary Tree
@all try to understand the question as usual we have to do it in min. time space complexity ..in mean Time O(n) space o(1) At-most just tell em after doing in-order traversal where u will store the elements either in array or in set isn'tit it will take O(n) extra space why not looks fro O(1) SPACE..IF M NOT CORRECT otherwise problem just become finding median in array which O(1) ..correct me if m wrong @Anurag wher u will store inorder of tree 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Check out One More Interesting Challenging Question...Longest Consecutive Elements Sequence.
Given an unsorted array, find the longest consecutive elements sequence. Challenge ...Time Complexity O(n) Space o(1) Ex: 5 7 3 4 9 10 1 15 12 Ans: will be 3 4 5 (longest with 3 elements) another Example 5,12,3,13,10,9,4,6,23,8,7. The answer should be 3,4,5,6,7,8,9,10. 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Check out One More Interesting Challenging Question...Longest Consecutive Elements Sequence.
its (not aplicable). sorting nlogn i said time O(n) O(1) space i think we can use BST , put all elements in BST O(n) then do inorder to find longest sub sequence still O(n) ..no no no its Ol(ogn) suggest another way to solve it 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Median of Dynamic Stream
Numbers are randomly generated and passed to a method. Write a program to find and maintain the median value as new values are generated. 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Median of Binary Tree
@all wake up geeks 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Median of Binary Tree
HI Geeks You Have Given Binary Tree , We need to Find The Median of Binary Tree it BT not BST I have some approach with BST ..lest discuss with you as how you can figure out exactness of the solution for this question 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Merge K Sorted Array In to Single Array
Given k sorted arrays each of length n, construct a single merged and sorted array.focus on running time and space complexity my soln. 1st basic soln..simple merge sort all whet we does in merging 2 sorted array it too complex for big K 2nd i have approach using min-heap as well but not able to figure the working code ..dono why? lets c what others think Approach Exactness of The Solution matters here 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: generate ques set
i think its like the generating the the number with equal probability
in given range thats it.if i understood the question correctly
so a shuffle algorithm will do that in o(n) like Knuth Shuffle will do
it so its like shuffling deck of card with equal probability
public static void shuffle(int[] cards)
{
int temp, index;
for (int i = 0; i cards.length; i++){
index = (int) (Math.random() * (cards.length - i)) + i;
temp = cards[i];
cards[i] = cards[index];
cards[index] = temp;
}
}
Please Let me know if m missing something here
Thanks Regards
Shashank Mani
CSE, BIT Mesra
--
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: compress memory
we have to use shuffling algo here i means compaction is technique used for this. google it you will find lot info on this topic hit: os use diff. algo.like best fit, worst fit, next fit,first fit for this , its the part of dynamic partition let me know if you have any difficulty i can post gud information here too. 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Application of OOD(Object Oriented Design) System Design -Design Clock Room..??
Design a system to manage clock room ( used at railway station). Like what data structure, how ? U need to give O(1) time solution + small space complexity. Thanks Shashank Mani -- 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] An Interesting Question Calculate nth Power of Integer
How you will print the 100th power of a single digit( which is of type int). How do you maintain that big number in memory? Lets C The Approach Thank Regards 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Application of OOD(Object Oriented Design) System Design -Design Clock Room..??
i have only this, one of the my friend asked from me., i post the q here so that we can look different approach 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Application of Prime Number . An Interesting For Geeks
yesterday one of the my friends asked this Q to me prove with correctness that Every even integer greater than 2 can be expressed as the sum of two primes e.g 4 = 2 + 2 6 = 3 + 3 10 = 7 + 3 or 5 + 5 14 = 3 + 11 or 7 + 7 Explain Derive The Time ,Space Complexity of Algorithm it seems to be that we have to find all possible prime factor of number prints it its not big task , so by checking that number we have to generate the all prime factor of it seems O(n) ..Hope i m clear corrcet me if i am wrong here.?? But problem come when even number become bigger say 1 billion 10^9 so for this choosing the a number as a prime factor has probability of 1/ln(n) so say if for 1 billion number out of 21 only 1 is prime. .y question is we have to prove the time complexity for two choosing a number nearby such big number is 1/ln(n)..?? with Heuristic justification it can be explained ro induction might help but guarantee here but i need some mathematical proof for this Thank Regards Shashank Mani CSE,BIT Mesra -- 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: friend's finder
in Hurry but giving approach 1st find the machine suing distributed algorithms from 1000s of server of such big sites i mean we have to 1st find the machine acco. to geographic location of user it gives us machine index say m_index; 2nd then in particular machine apply lookup function i mean then we database optimization needs to done as our user data stores in database we can't store such millions of user info in flat-files so i don't think we have to think about any string searching algo like KMP or Rabin-Karp (Hope I am clear)..so then we have to write most efficient optimize query to retrieve the user info from database. May b I Missed or Mixed Something Will Get Back to You.(In Hurry)! 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: power of 2
hope it will do that
unsigned int Log2n(unsigned int n)
{
return (n 1)? 1 + Log2n(n/2): 0;
}
Thank Regards
Shashank Mani
--
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: prime number using Sieve of Eratosthenes
@allWhy Not Try Carziest Thing in This Question Q.1st Prrove Timpe Complexity of Sieve of Eratosthenes is O(Log(Log(n))) ..isn't Making U Stuck..?? Q.2nd We Need to Drease the same Number of element sieved more then one time e.g 6,12 all the multiples of 2,3 ..then again all the multiples of 2,4,6,...many are sieving so many times..as the number of multiples increases ..isn;t it important modification in Sieve of Eratosthenes Prime Algo.. 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Compositions of a number
@Ganesha it has been several times here i m re-posting again here have
look at it , You can also find it several places by goggling it
basically we have to Print all combination of points that can compose
a given number
Examples:
For n = 1, the program should print following:
1
For n = 2, the program should print following:
1 1
2
For n = 3, the program should print following:
1 1 1
1 2
2 1
3
For n = 4, the program should print following:
1 1 1 1
1 1 2
1 2 1
1 3
2 1 1
2 2
3 1
and so on …
Algorithm:
At first position we can have three numbers 1 or 2 or 3.
First put 1 at first position and recursively call for n-1.
Then put 2 at first position and recursively call for n-2.
Then put 3 at first position and recursively call for n-3.
If n becomes 0 then we have formed a combination that compose n, so
print the current combination
/* The function prints all combinations of numbers 1, 2, ...MAX_POINT
that sum up to n.
i is used in recursion keep track of index in arr[] where next
element is to be added. Initital value of i must be passed as 0 */
void printCompositions(int n, int i)
{
/* array must be static as we want to keep track
of values stored in arr[] using current calls of
printCompositions() in function call stack*/
static int arr[ARR_SIZE];
if (n == 0)
{
printArray(arr, i);
}
else if(n 0)
{
int k;
for (k = 1; k = MAX_POINT; k++)
{
arr[i]= k;
printCompositions(n-k, i+1);
}
}
}
Let Me Know if You facing Any problem
Thanks Regards
Shashank Mani
CSE,BIT Mesra
--
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: Robot Moving on The Maze..Need All possible Path
@karans..dude..dude..dude.. 1st thing dat..a s/w engg. can't live without copy paste..every1 does the samething so nothing new in this. . 2nd is that..whatever one is doing it should help others understood- able.. okkk..karan..:lol well i don't like spamming but m just repling ans of ur quest tc 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Google puzzles
Hi here is the basic approach as we know in a week atmost 7 days ..so start with hit and trial Total 36 medals were awarded and the contest was for 6 days. On day 1: Medals awarded = (1 + 35/7) = 6 : Remaining 30 medals On day 2: Medals awarded = (2 + 28/7) = 6 : Remaining 24 medals On day 3: Medals awarded = (3 + 21/7) = 6 : Remaining 18 medals On day 4: Medals awarded = (4 + 14/7) = 6 : Remaining 12 medals On day 5: Medals awarded = (5 +7/7) = 6 : Remaining 6 medals On day 6: Medals awarded 6 Clear and Simple Thanks Sahshank -- 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] A Puzzling Puzzle
There is a lake, of square shape. There are four temples on each corner. There is a flower tree next to, say temple no 1. The pond has this magic power, if a flower is dip into the water it doubles the quantity. There is a warning note from the priest, saying No flower should be wasted. So the puzzle is, how many flowers should be plucked from the tree and should be offered in the temple and after offering at each temple, no flower should be left. Each temple has to be offered the same number of flower. Before offering, flowers has to be dipped in to the pond to get it double, as he can pluck the flowers from the tree only once, so he has to be carefull in choosing, the total number of flowers 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] A Billion Number Question
Given an input file with four billion integers, provide an algorithm to generate an integer which is not contained in the file. Assume you have 1 GB of memory. 2nd Part What if you have only 10 MB of memory? Thank 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Given an integer n , you have to print all the ways in which n can be represented as sum of positive integers
if m getting question correct then
the our task is to Given a total score n, print out all the
combination to compose n.
Examples:
For n = 1, the program should print following:
1
For n = 2, the program should print following:
1 1
2
For n = 3, the program should print following:
1 1 1
1 2
2 1
3
For n = 4, the program should print following:
1 1 1 1
1 1 2
1 2 1
1 3
2 1 1
2 2
3 1
and so on …
Algorithm:
At first position we can have three numbers 1 or 2 or 3.
First put 1 at first position and recursively call for n-1.
Then put 2 at first position and recursively call for n-2.
Then put 3 at first position and recursively call for n-3.
If n becomes 0 then we have formed a combination that compose n, so
print the current combination
so function looks like
void printCompositions(int n, int i)
{
/ int arr[ARR_SIZE];
if (n == 0)
{
printArray(arr, i);
}
else if(n 0)
{
int k;
for (k = 1; k = MAX_POINT; k++)
{
arr[i]= k;
printCompositions(n-k, i+1);
}
}
}
Please Correct me if i am wrong or you found for any test case it
failing
Thanks Regards
Shashank The Bets Way To Escape From The Problem is to Solve It
CSE, BIT Mesra
--
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] Crazy Question, Wants Creative Answer
U r watching an i cricket match.Suddenly the tv goes blank. Write the steps u ll take to find the fault purpose of this question is not to spamming but to taste how creative , innovative crazy one can think well what i found 1) See if some remote button is pressed by someone 2) Check the cable connectors 3) whats about amplifier if installed by operator in house 4) Check with your neighbors if there connection is also not working 5) Else notify the the operator i wants to see from all algogeeks what they think about this Q.. Thanks Regards 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: 10 digit problem
i don't think another answer 50 is best answer according to your constraints may sum1 else can think but i found its correct 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Interesting Text Editor , Word Question
We have a text editor application where we can choose 1)between 100s of different fonts like arial, calibri, etc.. 2)different text sizes 3) different formatting such as bold, Italics, regular, etc.. Imagine that the application is similar to word(there we will have these options). Now give different test cases to test this application. 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Interesting Toughest Problem On Telephone PC ..
Hy Guys I want to do . for any phone number .. the program should print out all the possible strings it represents. For eg.) 2 in the number can be replaced by 'a' or 'b' or 'c', 3 by 'd' 'e' 'f' etc. In this way how many possible permutations can be formed from a given phone number. I don't want anyone to write code for it ... a good algorithm or psuedocode would be great. I am talking about old small phone where a single digit corresponds to 3charcter from digit 2 to 8 and digit 9 has 4 character w x y z ..Hope everyone got my points what i wants well i tried my solution but thats become so complex so now even i am facing to understand that so will anybody try this interesting question . more clearly for digit o/p is AD AE AF BD BE BF CD CE CF Now You Can Imegin what will be o/p for 9740852296 or any 10 digit number Think as much as you can but finally solution matters .. Thanks Regards Shashank Mani -- 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: Combination Puzzle
@dave right.. its 40*40=1600 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Combination Puzzle
@all wake...up.. -- 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.
