Thread: C++ Challenge

  1. #1
    Registered User
    Join Date
    Nov 2019
    Posts
    135

    C++ Challenge

    Hellp everyone.

    Maybe someone can guide me how I can solve this exercise in an efficient way?

    Thanks in advance.


    http://www.up2me.co.il/thumbs/35229922.bmp

  2. #2
    Registered User
    Join Date
    Aug 2019
    Location
    inside a singularity
    Posts
    308
    I know that Floyd's algorithm is an O(N) solution to finding a loop in a linked list. You might wanna read about it on Wiki or something. I learnt a version of it recently while solving an ICPC problem from their live archives.

    EDIT: You'll soon be taught about trees and graphs in your course if you haven't been taught that already. This video was very useful to me, alongside the tonne of tutorials I viewed at GeeksforGeeks, freecodecamp.org, medium.com, etc...

    YouTube
    Last edited by Zeus_; 01-09-2020 at 10:26 AM.
    "Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the Universe trying to produce bigger and better idiots. So far, the Universe is winning." - Rick Cook, The Wizardry Compiled

  3. #3
    Registered User
    Join Date
    Nov 2019
    Posts
    135
    This is my solution:

    Code:
    int findLoop(struct Node* head) 
    {
        if (head == nullptr)
        {
            return 0;
        }
        int countIndex = 0;
        map<struct Node*, int> mapping;
        
        struct Node* curr = head;
        mapping[curr] = countIndex++;
        
        struct Node* beforeLast = curr;
        struct Node* goThrough = curr->next;
        
        while (goThrough != nullptr && mapping.count(goThrough) == 0)
        {
            mapping[goThrough] = countIndex++;
            beforeLast = goThrough;
            goThrough = goThrough->next;
        }
        
        if (goThrough != nullptr) 
        {
            return mapping[beforeLast] - mapping[goThrough] + 1;
        }
           
        return 0;
    }

  4. #4
    Registered User
    Join Date
    May 2012
    Location
    Arizona, USA
    Posts
    945
    Quote Originally Posted by HelpMeC View Post
    This is my solution:

    Code:
    int findLoop(struct Node* head) 
    {
        if (head == nullptr)
        {
            return 0;
        }
        int countIndex = 0;
        map<struct Node*, int> mapping;
        
        struct Node* curr = head;
        mapping[curr] = countIndex++;
        
        struct Node* beforeLast = curr;
        struct Node* goThrough = curr->next;
        
        while (goThrough != nullptr && mapping.count(goThrough) == 0)
        {
            mapping[goThrough] = countIndex++;
            beforeLast = goThrough;
            goThrough = goThrough->next;
        }
        
        if (goThrough != nullptr) 
        {
            return mapping[beforeLast] - mapping[goThrough] + 1;
        }
           
        return 0;
    }
    Yikes! That has O(N) space requirement. In other words, the memory it requires is directly proportional to the length of the list. For example, if your list is 1000000 nodes long and has a loop at the 1000000th node, this function will need to fill up the map with 1000000 numbers. It's even worse for BIG lists.

    Take a look at Floyd's cycle-finding algorithm (or others on that page) which uses a constant (and small) amount of memory.

  5. #5
    Guest
    Guest
    Btw, the struct keyword is superfluous in type declarations. Any struct Node* in your function can just be Node*.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C challenge
    By me77 in forum C Programming
    Replies: 3
    Last Post: 04-18-2008, 05:06 PM
  2. AI Challenge
    By unknown_111 in forum General AI Programming
    Replies: 0
    Last Post: 10-02-2007, 12:18 AM
  3. A Challenge in C++
    By Brad0407 in forum C++ Programming
    Replies: 38
    Last Post: 07-18-2007, 12:56 PM
  4. Take it as a challenge rather
    By shoeb_hi in forum C Programming
    Replies: 1
    Last Post: 01-14-2006, 03:40 PM
  5. Take the challenge...
    By correlcj in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 11-15-2002, 09:33 PM

Tags for this Thread