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. Following is an unanimous solution, I suppose:

Continue reading Problem Reduction

Advertisements

Selective Combinations

Consider this scenario:

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.

So that would be as follows:

abc def ghi

abc def

abc ghi

abc

Continue reading Selective Combinations

Linked List Quiz – Part II !!!

In the last part, 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?

Reversing every K nodes in the list

This is an interesting puzzle. You should not reverse the whole list instead only every K nodes, where N >= K > 1 and N is the number of nodes in the list. For instance, if you reverse 2 nodes (K = 2) in the following list

1 -> 2 -> 3 -> 4 -> 5 -> 6

the resulting list would be

2 -> 1 -> 4 -> 3 -> 6 -> 5
void LinkedList::Reverse(int k)
{
   prevHead = nullptr;

   auto head = root;
   root = _Reverse(head, k);
   head = head->Next();

   while (head != nullptr)
   {
      _Reverse(head, k);
      head = head->Next();
   }

   prevHead = nullptr;
}

LinkedList::Node* LinkedList::_Reverse(Node* head, int k)
{
   int iter = k;

   Node* current = head;
   Node* prev = nullptr;
   Node* next = nullptr;

   while (current != nullptr && iter >= 1)
   {
      next = current->Next();
      current->Next() = prev;

      if (next == nullptr)
      {
         break;
      }

      prev = current;
      current = next;
      --iter;
   }

   if (prevHead != nullptr)
   {
      prevHead->Next() = next != nullptr ? prev : current;
   }

   prevHead = head;
   head->Next() = next;

   return prev;
}

I hope the code covers all the corner cases of the puzzle. Give it a try and let me know if it all works for you.

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.

Here are some of the problems that Sammy asked me to solve:-

  • Reverse the list recursively
  • Reverse the list iteratively
  • Find if the list is cyclic
  • Find the node that causes the cycle (and break the cycle)
  • Reverse every K nodes in the list

Continue reading Linked List Quiz – Part I !!!

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.

Finally, Sriram helped me with it. I am sharing his code for the benefit of others.

string GenerateUniqueId(int length)
{
   string asciiChars = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890";
   char[] chars = asciiChars.ToCharArray();
   byte[] randombytes = new byte[length];

   RNGCryptoServiceProvider crypto = new RNGCryptoServiceProvider();
   crypto.GetNonZeroBytes(randombytes);
   StringBuilder result = new StringBuilder(length);

   foreach (byte b in randombytes)
   {
      result.Append(chars[b % asciiChars.Length]);
   }

   return result.ToString();
}

Thanks Sriram.

Quiz: Beauty of Numbers !!!

Sriram asked:

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?

I could give you solve it right here in front of your eyes. But that would not give you time to think to solve it on your own. So solve it and\or read the solution here.