Algos and Puzzles

Problem Reduction

Problem Reduction is what I call when a given problem can be expressed in terms of or solved using a solution to an alternate problem. Take for instance, the word distance problem: Find the shortest distance between two words in a given set of words.

Selective Combinations

You have a list of strings with which you have generate ordered selective combinations of strings starting with the first string in the list. Let us say the list of strings is abc, def and ghi. I have to generate ordered combinations of the above list restricted to the ones starting with abc.

Linked List Quiz – Part II !!!

In the previous post, we saw the academic (not general purpose) version of a linked list used to solve the puzzles, and solved the following puzzles on linked list.

• Reverse the list recursively
• Reverse the list iteratively
• Find if a list is cyclic

In this part, I will be solving the remaining two puzzles that I listed in the last part.

Finding the cyclic node in a cyclic linked list

1. According to my solution, the node which is actually supposed to be the end of the linked list is the cyclic node. Let us call Cn. Taking node Cn as the cyclic one has an advantage wherein you can break the cycle; assign Cn->next = nullptr;
2. But some people take the node after Cn as the cyclic node. The node after Cn is the node somewhere back in the list. This way it is not possible to break the cycle as we would traversed past Cn.

LinkedList::Node* LinkedList::FindCyclicNode() const
{
   int iterCount = 0;

   auto jmpBy1Ptr = root;
   auto jmpBy2Ptr = root;

   while (jmpBy1Ptr != nullptr && jmpBy2Ptr != nullptr && jmpBy2Ptr->Next() != nullptr)
   {
      jmpBy1Ptr = jmpBy1Ptr->Next();
      jmpBy2Ptr = jmpBy2Ptr->Next()->Next();

      if (jmpBy1Ptr == jmpBy2Ptr)
      {
         const int noOfNodesInLoop = CountNoOfNodesInLoop(jmpBy1Ptr);

         cout << "No of nodes in loop: " << noOfNodesInLoop << std::endl;

         auto p1= root;
         auto p2 = GetNthNode(noOfNodesInLoop - 1); // zero based index

         cout << "Node at index " << noOfNodesInLoop << ": " << p2->Item() << std::endl;

         // Pointers meet at eye of the loop (this node is as per point #2 above)

         while (p1 != p2)
         {
            p1 = p1->Next();
            p2 = p2->Next();
         }

         // This piece of code takes you to the loop starting node (this node is as per #1 above)
         p2 = p2->Next();

         while(p2->Next() != p1)
         {
            p2 = p2->Next();
         }

         return p2;
      }

      ++iterCount;
   }

   return nullptr;
}

int LinkedList::CountNoOfNodesInLoop(Node* stopNode) const
{
   int count = 1;
   auto p1 = stopNode;
   auto p2 = stopNode;

   while (p1->Next() != p2)
   {
      p1 = p1->Next();
      ++count;
   }

   return count;
}

The code above is the result of several iterations of discussions with Azhagu. It wasn’t written that way the first time. The first version was much complex and naive. I think it looks better now. What do you say?

Linked List Quiz – Part I !!!

A short while back, Sammy quizzed me on linked list based problems; singly linked list.

I am recording those problems, solutions and my experience as a two part series. In the first part, I am introducing the linked list class, which I wrote for packaging the implementation of the solutions. This class pertains to the context of the problem(s) and cannot be used as a general purpose linked list. A std::list might more pertinent in the context of the general purpose implementation of a list.

Unique Id Generation !!!

A short while I was engaged in a little project where I had to interact with a third party service provider who required a (30 length) unique id as part of the transaction. I am little dumb and am used to GUIDs for a long time when it comes to unique ids. But GUIDs are more than 30 in length. I was trying out some stupid ways like stripping out the trail part of the GUID to make 30 length unique but my intuition wasn’t convinced about the tricks I was working out. More ...

Quiz - Beauty of Numbers - Solution

One hint that should be helpful in building our solution is that we got to get retained after every wave of removal (until nobody else remains). That means it got to be really some special number or special kind of number. We could do what functional programmers would do. Write down the steps of removal for every queue size N, and it is not worth trying for very large N; in our case, even 20 or 30 could be large. But the point is we could iterate the steps manually and find a position K for every queue size N, where K is the position that remains after all the waves of removal. Once we are done with that, we should stare intensely 😂 on every K to derive a pattern, which would tell us something about those Ks, and with that we should be able to solve the problem. More ...

Quiz - Beauty of Numbers

Sriram quizzed:

Imagine there is a queue of people for getting a ticket for a movie or somehing. Where should be standing in the queue to last until the manager or some guy keeps removing people at odd indices. For instance, if the queue has 5 people given a token A to E, first we remove the first set of odd numbered positions in the queue, so A, C and E are gone. Now B and D remain. Again we remove the odd numbered positions. This time B alone is gone, and D is the winner. So in a queue like that, what is the lucky position you should hold so that you survive the wave of removals?

More ...