Some Coding Puzzle Exercises For Fun - Part 1

Sat, 02/10/2018 - 17:50

So,..I'm just following some of those YouTube videos describing various Google job interview tech questions and decided to see if I could reproduce them myself.

Fro my own experience I know that these questions are generally less about actually getting the question correct as much as how a developer approaches a problem...What they know about coding in order to approach the problem and how to ask questions to approach the problem.

Regardless, it's always fun and a good exercise to work things out. Keeps the mind fresh and gives it new insight into problems yet to be solved in ones career. 

(Note: I didn't skip forward to the end and cheat. These are my solutions...what would be the fun in that).

The first exercise was finding the first recurring letter in a  set. 

Example: ABCA

This was pretty easy. Build a function with a single parameter. Within the function initialize an array. I could use a string as well but I'll get into that in a bit. I suppose the set could be placed into an array as well but, I opted to place it into a string. It seems that in a real-world scenario the content would be in string format (like looping over text looking for..."something"). Not sure where this might be used however. ... Not important :-}

// init an array 
$f = [];

Next use strlen() to get the length of the string to iterate over. Assign it to a variable $l. It's possible to do this within the for loop but, calling the function that way asks the interpreter to call strlen() with each letter..."slower".

Use a basic for loop using $l for the second parameter and use $i for the key variable.

// get the length of the test set
    $l = strlen($s);
    for($i=0; $i<$l; $i++) {

Next assign the letter at the location $i to a variable $c using substr() .

// get the letter in this location
$c = substr($s,$i,1);

The next part could be done one of two ways. Either way we are going to be checking if we have seen this value before.

One method would be to append the current letter to an array and in the next iteration check if the letter was in the array in_array()

if(in_array($c,$f))
   return $c; // this is our guy
   // add what we have seen before to the test set
   $f[] = $c;

A second method appends the letter to a string and in the next iteration checks if the string is in the array with strpos().

// if we have seen it before
if(strpos($f,$c) === false)
   return $c; // this is our guy
   // add what we have seen before to the test set
   $f .= $c;

The array is there to search for a duplicate letter and there are only 26 letters in the alphabet...so in this case at least, performance is not an issue and so its simply a matter of choice.

If the program doesn't find any duplicates it returns false. Of course in PHP we have the luxury or returning a variant and dealing with the result as we see fit on the other side of the function. As long as the boolean is handled a bit more strongly there shouldn't be any issue with typecasting.

Here's is the final code with a more challenging string to test against.

 

<?php
// find the first recurance of a letter in a set

$s = 'bersgsdbfgjkdfhsdbfkghjg';
$result = first_recurring($s);

if(false === $result) {
    echo "No results found";
}else{
    echo $result;
}
echo "\n";

/**
 * first_recurring
 * 
 * @param string
 *
 * @return variant
 * */
function first_recurring($s) {
    // init an array
    $f = [];
    
    // get the length of the test set
    $l = strlen($s);
    for($i=0; $i<$l; $i++) {
        // get the letter in this location
        $c = substr($s,$i,1);
        // if we have seen it before
        if(in_array($c,$f))
            return $c; // this is our guy
        // add what we have seen before to the test set
        $f[] = $c;
    }
    // nothing found return false
    return false;
}

 

Categories