Ryan Byrd's Tech Ramblings

so, the question goes a-like-a this: write a function that, given an array of strings, will return the number of those strings that contain the letters c,h,e,v,r,o and n in that order. there may or may not be other letters around and in between. Here’s was my first attempt:

$strings = array(
                 "i like cheetos, but everyone knows cheez-its are better",
                 "che guevara was born in argentina",
                 "i own a chevrolet",
                 "hello world"
                 );
 
echo(chevronMatch($strings));
 
function chevronMatch($strings)
{
  $chevron="chevron";
  $chevronCount=0;
  foreach($strings as $testString)
  {
    $hitCount=0;
    for($y=0;$y<strlen($testString);$y++)
    {
      if ($testString[$y]==$chevron[$hitCount])
      {
        if ($hitCount<strlen($chevron)-1)
        {
          $hitCount++;
        }
        else
        {
          $chevronCount++;
          break;
        }
      }
    }
  }
  return $chevronCount;
}

Obviously, iterative code like that would make a regex guru like bj upset. here’s my second attempt, this time with ereg

function chevronMatch($strings)
{
  $chevronsMatched=0;
  foreach($strings as $string)
    {
      $chevron=array('c','h','e','v','r','o','n');
      $regex="[a-z,\-\ ]*";
      $regexString=$regex.implode($regex,$chevron).$regex;
      if (ereg($regexString,$string)) $chevronsMatched++;
    }
return $chevronsMatched;
}

I had a friend send me a list of these questions today. some are repeats from previous posts but there are several new ones. Enjoy!

Logic Problems

a) 8 Steel balls, 1 heavier than all the rest. Use a Balance Scale to determine the heaviest ball in the shortest number of tries.

b) Find how many trailing zeroes are in the product of 100! (100 Factorial).

c) Replace each letter below with a corresponding number from 0 to 8. Each Letter can only be matched to one number (ie, all of the E’s would be a 3, and that would mean that no other Letter could be a 3). The following addition problem should work after you replace the letters.

   S  E  V  E  N
   S  E  V  E  N
+         S   I   X
-----------------------
 T W E N  T   Y

Programming Problems

a) Write a function that takes an array of integers from 1 to 1 million, with one number being duplicated. Determine which integer is a duplicate, accounting for speed and efficiency.

b) Write a function that takes an array of integers from 1 to 1 million, with one number being missing from the range. Determine the missing integer, account for speed and efficiency.

c) Write a function that takes an array of an number of integers. Determine the largest contiguous sum, meaning given any two integers in the array, what is the highest sum? Given an array such as Array(1, -5, 3, -3, -9, 2) the highest contiguous sum would be 5.

d) Write a function that takes a string as a parameter and determine the first unique character in the string. In other words, given the string “sissy” the answer would be “i”. Afterwards, how would you optimize the function.

e) Pseudo-code the Ball Clock problem, determining how many cycles it takes for the balls to end up in the same position in the queue tray. Afterwards, how would you optimize the process if it were to be hit thousands of times on a given interface by thousands of users. If you have come up with a pure brute-force method, how could you optimize it further to shorten the processing time?

it’s not as difficult as it first looks:

Given two water faucets, one hot and one cold, and one bucket. The hot water fills the empty bucket in eight minutes. The cold water fills the bucket in seven minutes. Then I make a hole in the bucket such that the full bucket drains in four minutes. Now take the empty bucket, with the hole, and place under both faucets together. Turn on the hot and cold water at the same time. How long does it take to fill the bucket halfway?

The puzzle “You have two hard eggs. But the question is ‘how hard are they?’ You have a 100 story building and only the two eggs, how would you find out which is the highest floor of the building you can drop the eggs from, before they break? It could be the 1st floor but it could also be the 99th floor—you must try dropping the eggs from different floors and see what happens. Your goal is to find the answer with the least number of egg drops.”

50th floor, worst case: egg 1: floor 50, 100 (break), then Egg 2: 51-99 : 2 + 49
25th floor, worst case: egg 1: floor 25, 50, 75, 100 (break), then Egg 2: 76-99: 4 + 24
10th floor: Egg 1: floor 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 (break), Egg 2: floor 91, 92, 93, 94, 95, 96, 97, 98, 99: 10 + 9 drops

a function which models this is:

f(x) = 100/x + (x-1), where x is a positive integer less than or equal to 100

to find the local minima of function f(x), take the derivative of f(x) and set it equal to zero

f’(x) = -100/x^2 + 1 = 0

x = 10

So f(x) has a minimum at 10, which is the optimal solution

reference