Hi
I hace a similar problem. The above algorithm works well, but how can we
determine which side it intersects ?
On 1 July 2010 21:30, sharad kumar sharad20073...@gmail.com wrote:
@jalaj ur method fail when it is lying on the corner
plzz consider case for that also
--
You received this
what is the website having collection of ms questions?
On Thu, Jul 1, 2010 at 6:48 PM, vicky mehta...@gmail.com wrote:
Actually i saw a forum of MS questions and same as i wrote was written
there. I too was confused but finally came to conclusion as u.
Anyways
On Jul 1, 5:51 pm,
@Anand:
Let me know your input we can modify it accordingly.
I have already mentioned it in previous posts.. for your sake I ll do it
again..
Input is a a map of a small area..(some college campus)..it can be in the
form of an image, osm format (www.openstreetmap.org) or in the kml format (
1. (1) Maintain a hash table and insert the elements in the table when
passing through the array. And if there is a collision then that
element is a duplicate element in the array.Time - O(n) and the space
is O(n).
(2) Duplicate is detected by the above process. Then it can be easily
removed. I
I think those two sensors should not be exactly opposite to each other
to make the decision meaningful.
On Fri, Jul 2, 2010 at 11:58 AM, Jitendra Kushwaha
jitendra.th...@gmail.com wrote:
I think two sensors beside one another is enough to find the direction of
rotation.
At some time both
Can you please elaborate on the solution you have with auxiliary array?
On Fri, Jul 2, 2010 at 3:53 AM, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote:
we are given with Numerator and Denominator. After division we might get a
recurring decimal points float as the answer.
For example
@dave
is 1/17 recurring...??
@abhirup
now convert float to string ..only part after decimal
now let the string be .346346346.
take an auxilarry array a[0--9]..initialize it to zero
as you encounter update inceremnt a[s[i]-48]
wheneva you element in tha array becomes 2
store i-1
now from 0 to
make a bst of all numbers (nlogn)
include a count in the structure..as soon as the count become n return the
data of that node
On Thu, Jul 1, 2010 at 10:13 PM, sharad sharad20073...@gmail.com wrote:
1.an array of 2n+1 elements is given .one element is repeated n
times
and rest all are
second question can be done in O(logn)
do a modified binary search to find the starting index of the rotated array
i.e the smallest element.
after that you have two sorted arrays..
for eg 789 1236 (your modified binary search should return index of 1)
now check if the elemnent you are searching
Yes. What if the recurring number is more than 20 digits?
On Fri, Jul 2, 2010 at 9:33 AM, Dave dave_and_da...@juno.com wrote:
Does it work for 1/17, 2/17, 3/17, etc.?
Dave
On Jul 1, 5:23 pm, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote:
we are given with Numerator and Denominator. After
why not block reversal?
On Fri, Jul 2, 2010 at 5:36 PM, Saurabh Ahuja nsit.saur...@gmail.comwrote:
a[0] = a[2]
a[1] = a[3]
a[2] = a[4]
a[0] and a[1] has been changed
a[3] = a[0]
a[4] = a[1]
so this solution would not work.
On Fri, Jul 2, 2010 at 5:14 PM, Akash Gangil
@ dave its not always that the number be adjacent as the array is not sorted
suppose array is 2 1 3 4 2
On Fri, Jul 2, 2010 at 6:04 PM, Dave dave_and_da...@juno.com wrote:
For problem 1, finding a number that is repeated just once is enough.
Scan the array to see if there are two adjacent
Disagree
a BST can have duplicate entries
the 'equal to' term in the definition allows that
I am surprised to see in the Wiki:
From the above properties it naturally follows that:
- Each node (item in the tree) has a distinct key.
The example in the question is definitely wrong in the
hmm. :-o
On Fri, Jul 2, 2010 at 5:57 PM, Dave dave_and_da...@juno.com wrote:
Yes. With a period of 16:
1/17 = 0.0588235294117647 0588235294117647 0588235294117647 ...
Dave
On Jul 2, 5:22 am, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote:
@dave
is 1/17 recurring...??
@abhirup
On Fri, Jul 2, 2010 at 3:41 PM, jalaj jaiswal jalaj.jaiswa...@gmail.comwrote:
make a bst of all numbers (nlogn)
include a count in the structure..as soon as the count become n return the
data of that node
Can you please tell me why you chose a bst, simply traversing the array and
how would u implement LRU cache
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more
i think this should work.
for(i=1;i=k;i++)
{
var=a[n-1]
for(j=n-1;j=1;j--)
a[i]=a[i-1]
a[0]=var
}
On Fri, Jul 2, 2010 at 5:36 PM, Saurabh Ahuja nsit.saur...@gmail.comwrote:
a[0] = a[2]
a[1] = a[3]
a[2] = a[4]
a[0] and a[1] has been changed
a[3] = a[0]
a[4] = a[1]
so this solution
place the sensors on the same color portion well apart to distinguish which
one indicated the change first
the sensor number to indicate a change first indicates the direction.
On Fri, Jul 2, 2010 at 3:37 PM, Abhirup Ghosh abhiru...@gmail.com wrote:
I think those two sensors should not be
Okay. Here is some code to determine the number of digits in the
period of repetition of the decimal expansion of 1/n, where n 0:
int period(int n);
{
int i=1,j=0;
while( n % 2 == 0 )
n /= 2;
while( n % 5 == 0 )
n /= 5;
do
{
i = (10 * i) % n;
@Jalaj. You apparently missed the sentence Otherwise, look for the
repeat in the first 5 numbers.
Dave
On Jul 2, 7:42 am, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote:
@ dave its not always that the number be adjacent as the array is not sorted
suppose array is 2 1 3 4 2
On Fri, Jul 2,
@Saurabh. Checking three adjacent numbers won't work, as the example
1,2,3,4,1 shows.
You apparently missed the sentence, Otherwise, look for the repeat in
the first 5 numbers. If you don't find two equal adjacent numbers,
then there will be a repeat within the first five numbers. How do you
know
we can do this in a much better time than divya's algorithm since he does
the shortest path algorithm E+1 times
here's my approach:
find the shortest path using dijkstra since in dijkstra we have the shortest
path to each vertex
now look at the edges that end at the destination if the shortest
keep n bits (depending on the usage level you want) to track for each
element (cell/page) etc in the cache.
Now whenever an element is loaded into cache set all the bits and on further
use increment by 1 if not max value. Decrement value by 1 for all the block
periodically.
Now whenever you
the rank of median in the merged list of the two lists is (N1+N2)/2
so if it's rank in list A is i and it's rank in list B is j
then i+j=(N1+N2)/2
(it's rank in the list that it does not belong is i when A[i]medianA[i+1]
)
we do an changed binary search as follows:
pick the middle element of A
both problems can be done in O(n)
pick the first two elements count the number of their appearances in the
array ( O(n) )
if they are not the result we now that there is an element that is repeated
n times in 2n-1 elements and we can do the moore's algorithm for finding it
here's a link to this
how to search a number in a 2d matrix which is sorted both row wise and
column wise in less then O(n)
--
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
IIIT ALLAHABAD
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this
for count suppose if there are very big numbers ..then space will nt be
efficient
On Fri, Jul 2, 2010 at 7:05 PM, saurabh gupta sgup...@gmail.com wrote:
@Dave,
for 2n+1 you can have a configuration where repeated nos may not be
adjacent
you need a block of 3 instead of 2.
On Fri, Jul 2,
reverse full array first
then, reverse last k elemnts and initial n-k elements seperately
this will do
On Fri, Jul 2, 2010 at 8:34 PM, Ratnesh Thakur ratneshthaku...@gmail.comwrote:
correction..
a[j]=a[j-1] instead of a[i]=a[i-1]
On Fri, Jul 2, 2010 at 7:30 PM, Ratnesh Thakur
given some positive numbers
output the numbers in decreasing oeder of frequency..in case of atie print
the number which occurd first
for eg: 1,3,3,1,2,3,5,2,3
the output should be 11225
--
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
IIIT ALLAHABAD
--
You received this message
number the elements in clockwise order from 1..n suppose n is 12
then start from a point here we start from the point 1 then we find the
farthest point from it in O(n) suppose that's point 5
now if we want to find the farthest point from point 2 since we moved
clockwise the farthest point must
i think this might work
Binsearch on matrix for the column in which the element may lie...
use last element of the coloumn for comparisons
\
then binsearch in the coloumn to find if the element is there or not
--
You received this message because you are subscribed to the Google Groups
@Jalaj. I don't understand how your comment contributes to the
discussion. Please explain.
Dave
On Jul 2, 10:56 am, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote:
for count suppose if there are very big numbers ..then space will nt be
efficient
On Fri, Jul 2, 2010 at 7:05 PM, saurabh
@Jalaj. The original poster said, P.S---do not give block reversal
method for array rotation
Dave
On Jul 2, 10:54 am, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote:
reverse full array first
then, reverse last k elemnts and initial n-k elements seperately
this will do
On Fri, Jul 2, 2010
Given an array of n elements and an integer k where kn. Elemnts
{a[0].a[k] and a[k+1].a[n] are already sorted. Give an
algorithm to sort in O(n) time and O(1) space.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this
This is an example of bitonic sequence if we reverse the bottom half of the
array.
Sequence is called Bitonics if the sequence of number first
increases(ascending order) and then decrease(descending order).
1. We need to reverse the bottom half the array to make it bitonic.
2. Appy Bitonic Merge
Consider the bottom half elment of the given 2 - D array. if it is less than
the number to be search, ignore the whole column and if less ignore the
whole row. if it equal note the array index. repeat the above procedure till
all rows and column are scanned. By doing with complexity less than
@Anand: good one
On Sat, Jul 3, 2010 at 2:02 AM, Anand anandut2...@gmail.com wrote:
This is an example of bitonic sequence if we reverse the bottom half of the
array.
Sequence is called Bitonics if the sequence of number first
increases(ascending order) and then decrease(descending order).
How to find all the possible trees with 3 nodes from a given tree
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
@Rahul: the worst case running time for your algo is O(nlogn)
but here's another approach:
suppose we're searching for x
binary search on the diameter of the matrix (note that the diameter is
sorted)
if x is not on the diameter
when you find i such that a[i][i]xa[i+1][i+1]
split the matrix to
@Dave:
ah, yeah, you are right
On Fri, Jul 2, 2010 at 11:13 PM, Dave dave_and_da...@juno.com wrote:
@Jalaj. I don't understand how your comment contributes to the
discussion. Please explain.
Dave
On Jul 2, 10:56 am, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote:
for count suppose if
i think that the best method would be a balanced binary search tree which
counts the number of appearances for each element
O(nlogn)
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
not clear yaar
suppose the matrix is 0 1 3 7
2 4 5 8
6 9 10 11
8 12 13 14
how wiill you search 9.. elaborate
On Fri, Jul 2, 2010 at 11:09 PM, Rahul Kushwaha rahul.kushw...@gmail.comwrote:
i
Something like merge sort should do.
On Sat, Jul 3, 2010 at 12:00 AM, ANKUR BHARDWAJ ankibha...@gmail.com wrote:
Given an array of n elements and an integer k where kn. Elemnts
{a[0].a[k] and a[k+1].a[n] are already sorted. Give an
algorithm to sort in O(n) time and O(1) space.
--
I think its similar to the merge operation which is used in merge sort...
correct me if I am wrong..
Regards,
Abhishek
On Sat, Jul 3, 2010 at 12:00 AM, ANKUR BHARDWAJ ankibha...@gmail.comwrote:
Given an array of n elements and an integer k where kn. Elemnts
{a[0].a[k] and a[k+1].a[n]
catalan numbers.(2n)Cn/(n+1)
On Sat, Jul 3, 2010 at 1:06 AM, Raj N rajn...@gmail.com wrote:
How to find all the possible trees with 3 nodes from a given tree
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group,
@anand: this code will not work when n is not power of 2.
check for this example:
{2, 4, 55, 25, 15}
Output was:
0 4
0 2
1 3
0 1
2 3
2 4 25 55 15 0 0 0
ascending order
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group,
46 matches
Mail list logo