Algorithm Season

23 06 2010

I applied for a Senior Web Developer position recently which had a job description that appeared to match well with my experience and skillset. Then I got a response from the prospective employer in which I was asked to solve 4 technical problems, one of which involved developing an algorithm rather than writing code and to optionally use something called Big O notation. I admit my knowledge of Big O notation is nil. What I possess is expertise in knowing how to exploit the features of PHP to accomplish a task efficiently. So, I’m going to share with you the technical question, a resource I consulted and the I code wrote.

The Question:
Write an algorithm that detects if any character in a string occurs more than once. Describe the algorithm as you would verbally, not in code or pseudo-code. Assume we are competent programmers and will use your description to implement the algorithm in a mainstream programming language of your choice. Describe the performance of your algorithm in one sentence or using “big O” notation.

What inspired my approach:
http://stackoverflow.com/questions/190544/most-efficient-character-counting-algorithm

My Answer:
I’m going to create an array out of the string such that each index of the array corresponds to each letter of the string. Then I will use that array to keep a tally of each letter’s frequency in the string. To keep such a tally, I will inspect each letter and see if it occurs in one of four strings that together comprise the English alphabet. When the letter occurs in one of the four strings, I will then increment that value of element whose index matches that letter. Lastly, after I am done examining the string, I will sort the array so that the array tally appears in ascending order according to the indices. See code below for how I originally implemented this approach:

The PHP Code:

$string = strtolower('Shoshanah');
$ABCag = 'abcdefg';
$ABChm = 'hijklm';
$ABCnt = 'nopqrst';
$ABCuz = 'uvwxyz';
$totals = array();
$letter = '';
for ($i=0, $max = strlen($string); $i <= $max; $i++)
{
$letter = substr($string,$i,1);
if (strstr($ABCag,$letter)) {
$totals[$letter] = 0;
}
else
if (strstr($ABChm,$letter)) {
$totals[$letter] = 0;
}
else
if (strstr($ABCnt,$letter)) {
$totals[$letter] = 0;
}
else
if (strstr($ABCuz,$letter)) {
$totals[$letter] = 0;
}
}
for ($i=0, $max = strlen($string); $i <= $max - 1; $i++)
{
$letter = substr($string,$i,1);
if (strstr($ABCag,$letter)) {
$totals[$letter]++;
}
else
if (strstr($ABChm,$letter)) {
$totals[$letter]++;
}
else
if (strstr($ABCnt,$letter)) {
$totals[$letter]++;
}
else
if (strstr($ABCuz,$letter)) {
$totals[$letter]++;
}
}
ksort($totals);
var_dump($totals);

But even I had to admit the above code is not very elegant and it could be faster, too. So, here’s the improved version of the PHP code:


$string = strtolower('Shoshanah');
$ag = 'abcdefg';
$hm = 'hijklm';
$nt = 'nopqrst';
$uz = 'uvwxyz';
$totals = array();
$letter = '';
$arrABC = array($ag, $hm, $nt, $uz);
// build totals array
for ($i=0, $max = strlen($string); $i <= $max; $i++)
{
$letter = substr($string,$i,1);
foreach ($arrABC as $ABC) {
if (strstr($ABC,$letter)) {
$totals[$letter] = 0;
}
}
}
// find each letter's frequency
for ($i=0, $max = strlen($string); $i <= $max - 1; $i++)
{
$letter = substr($string,$i,1);
foreach ($arrABC as $ABC) {
if (strstr($ABC, $letter)) {
$totals[$letter]++;
}
}
}
ksort($totals);
var_dump($totals);

I picked the name of ‘Shoshanah’ the name of one of the alters on the US of Tara to test my code. The approach I took with PHP was to first create an array $totals where each element’s index corresponded to one of the letters in that name. PHP won’t permit duplicate indexes so when there is such a case the previously created one gets wiped out.

Next step is I then take each letter of the name and compare it with a section of the alphabet which I break into 4 strings of more or less equal length. That way each test is smaller than comparing each letter in the name with the entire alphabet.

What is interesting is that PHP was designed so that one needn’t be concerned with algorithms per se but instead be cognizant about which is the most appropriate function or class to use to solve a problem. So, why are algorithmic tests popping up for PHP-related positions? GOK (G-d only knows!)

This work is licensed under a Creative Commons License
.

Advertisements

Actions

Information

3 responses

23 06 2010
Bill Gates

Great Work!

23 06 2010
Sharon Lee Levy

Thank you, Mr. Gates.

27 07 2010
Comments on Algorithm Season « Sharon Lee Levy's Blog

[…] sent me recently not one but two lengthy comments on Algorithm Season which unfortunately lacked a valid email address. However, I think it is worthy to raise some of […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s




%d bloggers like this: