Re: [algogeeks] LINKED LIST
@ashish : please provide link for that page
On Sun, Dec 25, 2011 at 10:36 PM, Ashish Goel wrote:
> refer stanford page
> 1,2,3,4,5,6
>
> will become
>
> 5,3,1
> 6,4,2
>
> void MoveNode(struct node** destRef, struct node** sourceRef) {
> struct node* newNode = *sourceRef; // the front source node
> assert(newNode != NULL);
> *sourceRef = newNode->next; // Advance the source pointer
> newNode->next = *destRef; // Link the old dest off the new node
> *destRef = newNode; // Move dest to point to the new node
> }
>
> void AlternatingSplit(struct node* source,
> struct node** aRef, struct node** bRef) {
> struct node* a = NULL; // Split the nodes to these 'a' and 'b' lists
> struct node* b = NULL;
> struct node* current = source;
> while (current != NULL) {
> MoveNode(&a, ¤t); // Move a node to 'a'
> if (current != NULL) {
> MoveNode(&b, ¤t); // Move a node to 'b'
> }
> }
> *aRef = a;
> *bRef = b;
> }
>
>
> Best Regards
> Ashish Goel
> "Think positive and find fuel in failure"
> +919985813081
> +919966006652
>
>
>
> On Sat, Dec 24, 2011 at 11:37 PM, atul anand wrote:
>
>> because you are doing odd=odd->next; and even=even->next;
>> you will lose head pointers for the two linked list formed once you come
>> out of the loop.
>>
>>
>>
>> void segregate(node* head)
>> {
>> node *temp,*odd,*even;
>> toggle=1;
>> if(head==NULL)
>> {
>> return;
>> }
>> odd=head;
>>
>> if(head->next==NULL)
>> {
>>
>> return;
>> }
>> even=head->next;
>>
>> if(even->next==NULL)
>> {
>> return;
>> }
>> else
>> {
>> temp=even->next;
>> }
>> node *otemp,*etemp;
>> otemp=odd;
>> etemp=even;
>>
>> while(temp!=NULL)
>> {
>>
>> if( toggle == 1)
>> {
>>
>> otemp->next=temp;
>> otemp=otemp->next;
>>
>> temp=temp->next;
>> otemp->next=NULL;
>>
>> toggle=0;
>> }
>> else
>> {
>> etemp->next=temp;
>> etemp=etemp->next;
>>
>> temp=temp->next;
>> etemp->next=NULL;
>>
>> toggle=1;
>>
>> }
>>
>>
>>
>> }
>>
>>
>> }
>>
>> On Sat, Dec 24, 2011 at 10:56 PM, Karthikeyan V.B wrote:
>>
>>> Segregate even and odd psoitioned nodes in a linked list
>>>
>>> Eg:
>>> 2->3->1->9->7->5
>>> The output should be two separate lists
>>> 2->1->7
>>> 3->9->5
>>>
>>> *My code is:*
>>> void segregate(node* head)
>>> {
>>> int i=1;
>>> node* sec=head->next;
>>> node *odd=head,*even=head->next;
>>> while(even)
>>> {
>>> if(i%2)
>>> {
>>> odd->next=even->next;
>>> even->next=NULL;
>>> odd=odd->next;
>>> if(!odd->next) break;
>>> }
>>> else
>>> {
>>> even->next=odd->next;
>>> odd->next=NULL;
>>> even=even->next;
>>> if(!even->next) break;
>>> }
>>> i++;
>>> }
>>> }
>>>
>>> Pls correct me if i'm wrong or suggest me a better approach
>>>
>>> Regards,
>>> KARTHIKEYAN.V.B
>>> PSGTECH
>>> CBE
>>>
>>> --
>>> 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.
>
--
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] LINKED LIST
@ashish : acc to Karthikeyan question ...output should not be in reverse
order.
there is not much difference b/w both implementation.
it will become little interesting if you try to solve using recursion .
On Sun, Dec 25, 2011 at 10:36 PM, Ashish Goel wrote:
> refer stanford page
> 1,2,3,4,5,6
>
> will become
>
> 5,3,1
> 6,4,2
>
> void MoveNode(struct node** destRef, struct node** sourceRef) {
> struct node* newNode = *sourceRef; // the front source node
> assert(newNode != NULL);
> *sourceRef = newNode->next; // Advance the source pointer
> newNode->next = *destRef; // Link the old dest off the new node
> *destRef = newNode; // Move dest to point to the new node
> }
>
> void AlternatingSplit(struct node* source,
> struct node** aRef, struct node** bRef) {
> struct node* a = NULL; // Split the nodes to these 'a' and 'b' lists
> struct node* b = NULL;
> struct node* current = source;
> while (current != NULL) {
> MoveNode(&a, ¤t); // Move a node to 'a'
> if (current != NULL) {
> MoveNode(&b, ¤t); // Move a node to 'b'
> }
> }
> *aRef = a;
> *bRef = b;
> }
>
>
> Best Regards
> Ashish Goel
> "Think positive and find fuel in failure"
> +919985813081
> +919966006652
>
>
>
> On Sat, Dec 24, 2011 at 11:37 PM, atul anand wrote:
>
>> because you are doing odd=odd->next; and even=even->next;
>> you will lose head pointers for the two linked list formed once you come
>> out of the loop.
>>
>>
>>
>> void segregate(node* head)
>> {
>> node *temp,*odd,*even;
>> toggle=1;
>> if(head==NULL)
>> {
>> return;
>> }
>> odd=head;
>>
>> if(head->next==NULL)
>> {
>>
>> return;
>> }
>> even=head->next;
>>
>> if(even->next==NULL)
>> {
>> return;
>> }
>> else
>> {
>> temp=even->next;
>> }
>> node *otemp,*etemp;
>> otemp=odd;
>> etemp=even;
>>
>> while(temp!=NULL)
>> {
>>
>> if( toggle == 1)
>> {
>>
>> otemp->next=temp;
>> otemp=otemp->next;
>>
>> temp=temp->next;
>> otemp->next=NULL;
>>
>> toggle=0;
>> }
>> else
>> {
>> etemp->next=temp;
>> etemp=etemp->next;
>>
>> temp=temp->next;
>> etemp->next=NULL;
>>
>> toggle=1;
>>
>> }
>>
>>
>>
>> }
>>
>>
>> }
>>
>> On Sat, Dec 24, 2011 at 10:56 PM, Karthikeyan V.B wrote:
>>
>>> Segregate even and odd psoitioned nodes in a linked list
>>>
>>> Eg:
>>> 2->3->1->9->7->5
>>> The output should be two separate lists
>>> 2->1->7
>>> 3->9->5
>>>
>>> *My code is:*
>>> void segregate(node* head)
>>> {
>>> int i=1;
>>> node* sec=head->next;
>>> node *odd=head,*even=head->next;
>>> while(even)
>>> {
>>> if(i%2)
>>> {
>>> odd->next=even->next;
>>> even->next=NULL;
>>> odd=odd->next;
>>> if(!odd->next) break;
>>> }
>>> else
>>> {
>>> even->next=odd->next;
>>> odd->next=NULL;
>>> even=even->next;
>>> if(!even->next) break;
>>> }
>>> i++;
>>> }
>>> }
>>>
>>> Pls correct me if i'm wrong or suggest me a better approach
>>>
>>> Regards,
>>> KARTHIKEYAN.V.B
>>> PSGTECH
>>> CBE
>>>
>>> --
>>> 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.
>
--
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: Frequency Sort Algo
LSD Radix sort can be used: - First, it will sort the no. This will take O(k.n) (k: max no of digits in a number; n: no of integers) - Second, since the no are now sorted, scan all the integers and get their frequency count. O(n) - Use radix sort again to sort the frequency count in decreasing order. O(k'.n) (k' < k) Overall, O(k.n). Whether it can be better depends on following: 1. Are all of the numbers single digit, if yes, then k=1 and thus first step will take O(n). Overall it will be O(k'.n). Value of k' will depend on how huge is the original list of numbers 2. Even if the numbers are not single digit and if k < logn, then O(k.n) < (n.logn) So, basically giving presenting both the solutions in the interview can be good along with the analysis that which algo can perform better in which scenario. On Sun, Dec 25, 2011 at 12:17 PM, atul anand wrote: > @ankur : if i am able to figure out a better solution , i will post.but i > guess nlogn is the best we can get. > > > On Sun, Dec 25, 2011 at 4:50 PM, Ankur Garg wrote: > >> @Atul..your solution is correct and would do the job but its complexity >> wud be nlogn . >> >> Any better way of solving it ? >> >> Regards >> Ankur >> >> >> On Sun, Dec 25, 2011 at 2:10 AM, sravanreddy001 > > wrote: >> >>> any better approach than O(N log N) time? >>> >>> maintain a heap of nodes >>> for each element, if already present increase the count. Else add the >>> elements. >>> >>> Max-Heap --> fetch the node, print it count number of times, (time to >>> search in heap -- log N) >>> doing this for N elements. >>> >>> >>> -- >>> 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/-/rJMBHTFmv8IJ. >>> >>> 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, Piyush Kansal -- 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: which is the right data structure to use for a given problem ?
@atul: I dont think you should make this assumption entering "at" should list down all the phone numbers starting with "at". It should be rather taken as "at" can occur anywhere in the name (beginning, mid or end). This is how it works in Android(I have android based phone and I checked it personally). In this case, Trie wont help. Instead suffix trees can be a good option. On Sat, Dec 24, 2011 at 11:21 AM, atul anand wrote: > @dave : > > using only one hastable will cause problem , if 2 person have same name > ...right?? > > using 2 hashtable then:- > if say two person has same name , they will collide at same point on 2nd > hashtable. > so second hashtable must contain linked list implementation to contain > phone number of both.. right?? > > now if we care of finding contact number by taking input string(name of > the person ) then for this case Trie is a better option . but what will > happen if 2 person have same name?? > > i am more interested in knowing like in are mobile phone when i give input > as -> *at* then it gives me list of names which starts with alphabets *at* , > which can be possible if use data structure like Trie.but as i have > mentioned above , my only concern is what will happen if two person have > same name. > > i guess they use both Trie and hastable to achieve this. > > what is your take on this?? > > On Sat, Dec 24, 2011 at 8:09 PM, Dave wrote: > >> @Atul007: Use a hash table. Enter the name and the number into the >> table, or use separate hash tables for names and numbers. The data >> associated with each is a pointer to the other. >> >> Dave >> >> On Dec 24, 1:50 am, atul007 wrote: >> > If you want to instant search a contact number of person from a phone >> > book. >> > >> > one must be able to use any one of them to search(person name or >> > contact number). >> > >> > for eg : given phone number as input it should return name of the >> > person >> > >> > or >> > >> > given name of the person as input it should return phone number of the >> > person. >> > >> > we can use TRIE , but for that we have to maintain 2 different Trie >> > >> > or >> > >> > we can use hastable. >> > >> > which one you guys think will be good approach for this??? >> >> -- >> 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, Piyush Kansal -- 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: Frequency Sort Algo
@ankur : if i am able to figure out a better solution , i will post.but i guess nlogn is the best we can get. On Sun, Dec 25, 2011 at 4:50 PM, Ankur Garg wrote: > @Atul..your solution is correct and would do the job but its complexity > wud be nlogn . > > Any better way of solving it ? > > Regards > Ankur > > > On Sun, Dec 25, 2011 at 2:10 AM, sravanreddy001 > wrote: > >> any better approach than O(N log N) time? >> >> maintain a heap of nodes >> for each element, if already present increase the count. Else add the >> elements. >> >> Max-Heap --> fetch the node, print it count number of times, (time to >> search in heap -- log N) >> doing this for N elements. >> >> >> -- >> 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/-/rJMBHTFmv8IJ. >> >> 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.
Re: [algogeeks] LINKED LIST
refer stanford page
1,2,3,4,5,6
will become
5,3,1
6,4,2
void MoveNode(struct node** destRef, struct node** sourceRef) {
struct node* newNode = *sourceRef; // the front source node
assert(newNode != NULL);
*sourceRef = newNode->next; // Advance the source pointer
newNode->next = *destRef; // Link the old dest off the new node
*destRef = newNode; // Move dest to point to the new node
}
void AlternatingSplit(struct node* source,
struct node** aRef, struct node** bRef) {
struct node* a = NULL; // Split the nodes to these 'a' and 'b' lists
struct node* b = NULL;
struct node* current = source;
while (current != NULL) {
MoveNode(&a, ¤t); // Move a node to 'a'
if (current != NULL) {
MoveNode(&b, ¤t); // Move a node to 'b'
}
}
*aRef = a;
*bRef = b;
}
Best Regards
Ashish Goel
"Think positive and find fuel in failure"
+919985813081
+919966006652
On Sat, Dec 24, 2011 at 11:37 PM, atul anand wrote:
> because you are doing odd=odd->next; and even=even->next;
> you will lose head pointers for the two linked list formed once you come
> out of the loop.
>
>
>
> void segregate(node* head)
> {
> node *temp,*odd,*even;
> toggle=1;
> if(head==NULL)
> {
> return;
> }
> odd=head;
>
> if(head->next==NULL)
> {
>
> return;
> }
> even=head->next;
>
> if(even->next==NULL)
> {
> return;
> }
> else
> {
> temp=even->next;
> }
> node *otemp,*etemp;
> otemp=odd;
> etemp=even;
>
> while(temp!=NULL)
> {
>
> if( toggle == 1)
> {
>
> otemp->next=temp;
> otemp=otemp->next;
>
> temp=temp->next;
> otemp->next=NULL;
>
> toggle=0;
> }
> else
> {
> etemp->next=temp;
> etemp=etemp->next;
>
> temp=temp->next;
> etemp->next=NULL;
>
> toggle=1;
>
> }
>
>
>
> }
>
>
> }
>
> On Sat, Dec 24, 2011 at 10:56 PM, Karthikeyan V.B wrote:
>
>> Segregate even and odd psoitioned nodes in a linked list
>>
>> Eg:
>> 2->3->1->9->7->5
>> The output should be two separate lists
>> 2->1->7
>> 3->9->5
>>
>> *My code is:*
>> void segregate(node* head)
>> {
>> int i=1;
>> node* sec=head->next;
>> node *odd=head,*even=head->next;
>> while(even)
>> {
>> if(i%2)
>> {
>> odd->next=even->next;
>> even->next=NULL;
>> odd=odd->next;
>> if(!odd->next) break;
>> }
>> else
>> {
>> even->next=odd->next;
>> odd->next=NULL;
>> even=even->next;
>> if(!even->next) break;
>> }
>> i++;
>> }
>> }
>>
>> Pls correct me if i'm wrong or suggest me a better approach
>>
>> Regards,
>> KARTHIKEYAN.V.B
>> PSGTECH
>> CBE
>>
>> --
>> 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.
Re: [algogeeks] Re: Facebook Question
@Gene,
The algorithm which you have given below is O(n^2). I tried too and could
not figure out anything better than this unless we go for data structures
like kd-trees, as you already suggested.
Is it really the case that w/o using kd-tree, there is no better algorithm?
On Fri, Dec 23, 2011 at 5:50 PM, Carol Smith wrote:
> @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.
>
--
Regards,
Piyush Kansal
--
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: which is the right data structure to use for a given problem ?
When two persons have same name and we use one hashtable(HT), what happens inside HT is entirely depends on HT implementation. In this case, HT may chain the values when keys match. When querying the HT for this key, HT returns all the values chained under this key and developer has to iterate and get the interested values. And for the case where the phonebook pulls all possible lexicographic matches, trie would be used to get the whole name and then the HT to get the number ( even duplicates, as the case may be). -Carol On Sat, Dec 24, 2011 at 11:21 AM, atul anand wrote: > @dave : > > using only one hastable will cause problem , if 2 person have same name > ...right?? > > using 2 hashtable then:- > if say two person has same name , they will collide at same point on 2nd > hashtable. > so second hashtable must contain linked list implementation to contain > phone number of both.. right?? > > now if we care of finding contact number by taking input string(name of > the person ) then for this case Trie is a better option . but what will > happen if 2 person have same name?? > > i am more interested in knowing like in are mobile phone when i give input > as -> *at* then it gives me list of names which starts with alphabets *at* , > which can be possible if use data structure like Trie.but as i have > mentioned above , my only concern is what will happen if two person have > same name. > > i guess they use both Trie and hastable to achieve this. > > what is your take on this?? > > On Sat, Dec 24, 2011 at 8:09 PM, Dave wrote: > >> @Atul007: Use a hash table. Enter the name and the number into the >> table, or use separate hash tables for names and numbers. The data >> associated with each is a pointer to the other. >> >> Dave >> >> On Dec 24, 1:50 am, atul007 wrote: >> > If you want to instant search a contact number of person from a phone >> > book. >> > >> > one must be able to use any one of them to search(person name or >> > contact number). >> > >> > for eg : given phone number as input it should return name of the >> > person >> > >> > or >> > >> > given name of the person as input it should return phone number of the >> > person. >> > >> > we can use TRIE , but for that we have to maintain 2 different Trie >> > >> > or >> > >> > we can use hastable. >> > >> > which one you guys think will be good approach for this??? >> >> -- >> 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.
Re: [algogeeks] Re: Frequency Sort Algo
fpr the nos with same frequency , the one having lower value shud come first For ex 3,1,1,3,1,3,2 Here 1 should come first so 2,1,1,1,3,3,3 On Sun, Dec 25, 2011 at 11:18 AM, top coder wrote: > What about the case of the numbers having same frequency? > Which one should come first? > > On Dec 24, 11:18 pm, atul anand wrote: > > first sort the given array , you will get > > > > 1,1,1,1,2,2,2,3,3,3,3,3,4,4,5 > > > > now count frequency of each number and insert it into min heap. > > each node contain 2 variable. > > 1) frequency > > 2) number > > > > now do extract min operation. > > > > and expand , for eg:- > > for node 5 > > frequency = 0 > > number =5; > > write 5 to the given array > > > > for node 4 > > frequency = 2 > > number =4 > > write 4,4 to array. > > > > for node 2 > > frequency = 3 > > number =2 > > > > write 2,2,2 to the given array... > > > > > > > > On Sat, Dec 24, 2011 at 10:57 PM, Ankur Garg > wrote: > > > how can one do frequency sort . > > > > > Suppose we have an integer array like > > > > > 1,2,3,1,2,3,1,1,2,3,4,4,3,5,3 > > > > > Then 1 is appearing 4 times > > > 2 - 3 > > > 3- 5 > > > 4-2 > > > 5-1 > > > > > Then if we sort by frequency we shud have this as result > > > > > 5,4,4,2,2,2,1,1,1,1,3,3,3,3,3 > > > > > How to do 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.- Hide quoted text - > > > > - Show quoted text - > > -- > 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: Facebook Question
AND, for two points to be close, they need not be on the same quadrant On Dec 21, 10:55 pm, atul anand wrote: > to find all points which lies on the same quadrant for a specific node(say > 1) , we have to check all nodes...rite?? > we have to find difference b/w 2 node(frome origin ) is less or greater > than distance b/w 2 nodes...rite?? > > so if i am not getting it wrong it wil be O(n^2) anyhow. > > > > > > > > On Thu, Dec 22, 2011 at 8:14 AM, rahul wrote: > > @harish What if all the points are in the same quadrant and and are > > equidistant from 0,0. > > > -- > > 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/-/NjysUthIqgYJ. > > 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.
Re: [algogeeks] Re: Frequency Sort Algo
@Atul..your solution is correct and would do the job but its complexity wud be nlogn . Any better way of solving it ? Regards Ankur On Sun, Dec 25, 2011 at 2:10 AM, sravanreddy001 wrote: > any better approach than O(N log N) time? > > maintain a heap of nodes > for each element, if already present increase the count. Else add the > elements. > > Max-Heap --> fetch the node, print it count number of times, (time to > search in heap -- log N) > doing this for N elements. > > > -- > 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/-/rJMBHTFmv8IJ. > > 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: Frequency Sort Algo
What about the case of the numbers having same frequency? Which one should come first? On Dec 24, 11:18 pm, atul anand wrote: > first sort the given array , you will get > > 1,1,1,1,2,2,2,3,3,3,3,3,4,4,5 > > now count frequency of each number and insert it into min heap. > each node contain 2 variable. > 1) frequency > 2) number > > now do extract min operation. > > and expand , for eg:- > for node 5 > frequency = 0 > number =5; > write 5 to the given array > > for node 4 > frequency = 2 > number =4 > write 4,4 to array. > > for node 2 > frequency = 3 > number =2 > > write 2,2,2 to the given array... > > > > On Sat, Dec 24, 2011 at 10:57 PM, Ankur Garg wrote: > > how can one do frequency sort . > > > Suppose we have an integer array like > > > 1,2,3,1,2,3,1,1,2,3,4,4,3,5,3 > > > Then 1 is appearing 4 times > > 2 - 3 > > 3- 5 > > 4-2 > > 5-1 > > > Then if we sort by frequency we shud have this as result > > > 5,4,4,2,2,2,1,1,1,1,3,3,3,3,3 > > > How to do 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.- Hide quoted text - > > - Show quoted text - -- 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: Frequency Sort Algo
Hashmapping O(n) On 25-Dec-2011 2:15 AM, "sravanreddy001" wrote: > any better approach than O(N log N) time? > > maintain a heap of nodes > for each element, if already present increase the count. Else add the > elements. > > Max-Heap --> fetch the node, print it count number of times, (time to > search in heap -- log N) > doing this for N elements. > > -- > 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/-/rJMBHTFmv8IJ. > 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.
