edible insect

Imagine a bat flying through a cave towards a stalactite hanging from the cave ceiling (not a stalagmite poking up from the cave floor, although that variant of speleothem would really work just fine in my story too) and on the way to the stalactite, for every step along the journey the bat must make it pings ahead, across all the positions in space it must yet cross that it will eventually pass through, in an attempt to find a juicy insect to eat along the way. While the bat is making only one trip there are many pings making trips, one for each of the increments in the bat's flight. If you write code this should sound like a loop within a loop to you. I've encountered in my history some interview questions with puzzles that have answers that fit this shape of things for finding an edible insect. One example: Here is a list of stock prices during a stretch of time and I want you to tell me what is the most amount of money I could have made by buying at the optimal time and selling at the optimal time. Another: What is the longest palindrome in a sentence? Imagine having to whiteboard static methods for these scenarios which could successfully be tested like so:

using System.Collections.Generic;
using Algorithms.Utilities;
using Microsoft.VisualStudio.TestTools.UnitTesting;
namespace Algorithms.Tests.Utilities
{
   [TestClass]
   public class CrawlerTests
   {
      [TestMethod]
      public void FindLargestPossibleGain_happy_pass_test()
      {
         List<double> stockPricesOverTime = new List<double>()
         {
            15.67,
            18.88,
            40.22,
            41.88,
            32.19,
            11.88,
            22.17,
            39.42,
            27.17,
            27.86,
            11.11,
            22.28
         };
         double largestPossibleGain =
               Crawler.FindLargestPossibleGain(stockPricesOverTime);
         Assert.AreEqual(largestPossibleGain,27.54);
      }
      
      [TestMethod]
      public void FindTheLargestPalindrome_happy_pass_test()
      {
         string sentence = "Otto drove the racecar to the madam he had the eye for.";
         string largestPalindrome = Crawler.FindTheLargestPalindrome(sentence);
         Assert.AreEqual(largestPalindrome, "racecar");
      }
   }
}

 
 

I've heard that the first puzzle may be solved in one loop, although I cannot imagine how. In an interview however, and beyond esoteric heroics, when these puzzles come up, you are being tested to see if you can come up with an algorithm that could be considered O(n²) in Big O notation and you should craft a solution with a loop inside of a loop like these:

using System;
using System.Collections.Generic;
using System.Linq;
namespace Algorithms.Utilities
{
   public static class Crawler
   {
      public static double FindLargestPossibleGain(List<double> stockPrices)
      {
         double largestPossibleGain = 0;
         int outerCounter = 0;
         while (outerCounter < stockPrices.Count)
         {
            int innerCounter = outerCounter + 1;
            while (innerCounter < stockPrices.Count)
            {
               double immediateGain = stockPrices[innerCounter] -
                     stockPrices[outerCounter];
               if (immediateGain > largestPossibleGain)
               {
                  largestPossibleGain = immediateGain;
               }
               innerCounter++;
            }
            outerCounter++;
         }
         return largestPossibleGain;
      }
      
      public static string FindTheLargestPalindrome(string sentence)
      {
         List<char> characters = sentence.ToLower().Replace(" ","").ToCharArray().ToList();
         string largestPalindrome = "";
         int outerCounter = 0;
         while (outerCounter < characters.Count)
         {
            int innerCounter = outerCounter + 1;
            string potentialPalindrome = characters[outerCounter].ToString();
            while (innerCounter < characters.Count)
            {
               potentialPalindrome = potentialPalindrome + characters[innerCounter];
               string potentialPalindromeBackwards = "";
               char[] potentialPalindromeCharacters = potentialPalindrome.ToCharArray();
               Array.Reverse(potentialPalindromeCharacters);
               foreach (char character in potentialPalindromeCharacters)
               {
                  potentialPalindromeBackwards = potentialPalindromeBackwards + character;
               }
               if (potentialPalindrome == potentialPalindromeBackwards)
               {
                  if (potentialPalindrome.Length > largestPalindrome.Length)
                  {
                     largestPalindrome = potentialPalindromeBackwards;
                  }
               }
               innerCounter++;
            }
            outerCounter++;
         }
         return largestPalindrome;
      }
   }
}

 
 

The total number of steps in these challenges aren't really represented by n to the power of two as for in incrementing through the first loop the ground to cover in the second loop luckily decays. Instead it would be half of the value derived by multiplying n by one less than n, so instead of there being one hundred steps for a collection of ten sequential items there would be forty-five. Anyways, I hope you can see how these problems are solved. I found them mind-boggling at first and wanted to write a blog posting about them. The thing to keep in mind is that the window within the second loop progressively shrinks. As the bat flies it has less distance to ping across to the stalactite at any one point in time in contrast to any one previous point in time. Puzzles in which we are just comparing two points in a sequence in which one point does not have to precede the other can perhaps just be solved in one loop. The puzzles here are not such puzzles however. Our bat cannot just fly to the stalactite and find an insect along the way all by its own. An inner loop comes into play. Our bat needs to ping to find an insect.