[algogeeks] Re: How to solve this
Hey Ankur, What is the order of time complexity we are looking for in this case. The option which Dave suggested can give us random node by traversing that many number of nodes from the head. That will be O(n). This can be further reduced to n/2 if we use two pointers, both of which will traverse two nodes at a time: 1. one pointing to first node (lets call it odd pointer) 2. other pointing to second node (lets call it even pointer) So, depending on the value returned by random number generator(even or odd), we can decide which pointer to pick. -- 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/-/N-5i9YH4AkYJ. 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: Facebook Question
@Gene -
Cool algorithm! I tried before in java and messed a little to get exact
output format.
Just wondering how you came up with simple yet working code?
-Carol
On Thu, Dec 22, 2011 at 6:08 PM, Gene wrote:
> The simplest algorithm is probably to check each point against all
> others while maintaining a list of the top 3. Since 3 is a small
> number, you can just maintain the top 3 in sorted order by insertion.
> For a bigger K top-K you'd use a max heap.
>
> This can also be done in O(n log n) time by building the right data
> structure. A kd-tree would be O(n log n) on random data, for example.
>
> The simple algorithm would code this way:
>
> #include
>
> #define N_PTS 1000
> #define N_TOP 3
>
> struct pt_s { int id; double x, y; } pts[N_PTS];
>
> struct top_s { struct pt_s pt; double d2; } tops[N_TOP];
>
> int n_top = 0;
>
> void clear() { n_top = 0; }
>
> void check_and_add(struct pt_s *hub, struct pt_s *sat)
> {
> double dx = hub->x - sat->x;
> double dy = hub->y - sat->y;
> double d2 = dx * dx + dy * dy;
> struct top_s top = { *sat, d2 };
> if (n_top < 3) { // must insert somewhere
>int i = n_top++;
>while (i > 0 && d2 < tops[i - 1].d2) {
> tops[i] = tops[i - 1];
> i--;
>}
>tops[i] = top;
> }
> else if (d2 < tops[N_TOP - 1].d2) { // may insert
>int i = N_TOP - 1;
>while (i > 0 && d2 < tops[i - 1].d2) {
> tops[i] = tops[i - 1];
> --i;
>}
>tops[i] = top;
> }
> }
>
> void print(struct pt_s *hub)
> {
> int i;
> printf("%d %d", hub->id, tops[0].pt.id);
> for (i = 1; i < n_top; i++)
>printf(",%d", tops[i].pt.id);
> printf("\n");
> }
>
> int main(void)
> {
> int n = 0, id, i, j;
> double x, y;
>
> while (n < N_PTS && scanf("%d%lf%lf", &id, &x, &y) == 3) {
>struct pt_s pt = { id, x, y };
>pts[n++] = pt;
> }
> for (i = 0; i < n; i++) {
>clear();
>for (j = 0; j < n; j++)
> if (j != i)
>check_and_add(pts + i, pts + j);
>print(pts + i);
> }
> return 0;
> }
>
>
> On Dec 21, 1:00 am, SAMMM wrote:
> > You are given a list of points in the plane, write a program that
> > outputs each point along with the three other points that are closest
> > to it. These three points ordered by distance.
> > The order is less then O(n^2) .
> >
> > For example, given a set of points where each line is of the form: ID
> > x-coordinate y-coordinate
> >
> > 1 0.0 0.0
> > 2 10.1 -10.1
> > 3 -12.212.2
> > 4 38.3 38.3
> > 5 79.99 179.99
> >
> > Your program should output:
> >
> > 1 2,3,4
> > 2 1,3,4
> > 3 1,2,4
> > 4 1,2,3
> > 5 4,3,1
>
> --
> 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.
[algogeeks] Re: How to solve this
@Ankur: The linked list is isomorphic to the non-negative integers, so selecting a random integer is equivalent to selecting a random node. There is no uniform distribution on the integers, so we can't find a uniform distribution on the nodes. One way to find a non-uniform distribution is by taking the n-th node of the list, where n = int(- log(random())), where random() generates uniform (0,1) random numbers. I presume that there are many more ways to do this. Dave On Dec 23, 1:54 pm, Ankur Garg wrote: > Suggest an algo with which u can find a random node in an infinitely long > linked list -- 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] How to solve this
Suggest an algo with which u can find a random node in an infinitely long linked list -- 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: correctness of "point inside polygon: algorithm ?
The description is fine. It is tricky to get implementation exactly right for the cases where the ray pierces a vertex or coincides exactly with an edge, especially with floating point rather than rational arithmetic. Franklin's code (link is given on the page) works well. I'd never code it myself when his is available, and it's only 6 lines. On Dec 18, 1:30 pm, WgpShashank wrote: > Would anyone will interested to discuss ? Algo is simple but i am > wondering about correctness > ofhttp://en.wikipedia.org/wiki/Point_in_polygonalgorithm ? > > 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.
Re: [algogeeks] correctness of "point inside polygon: algorithm ?
Ray casting algorithmn seems fine to mechecked some cases its working good. nice and simple algo. check this link:- http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html#The%20Method On Sun, Dec 18, 2011 at 6:00 PM, WgpShashank wrote: > Would anyone will interested to discuss ? Algo is simple but i am > wondering about correctness of > http://en.wikipedia.org/wiki/Point_in_polygon algorithm ? > > > Thanks > Shashank > CSE, BIT Mesra > > -- > 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/-/5QEG2iRLVLUJ. > 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.
