Day 14, nearly two weeks since I started. I started my first project in PHP since 7 years. I wouldn’t have expected that I started that fast. My initial plan was to start maybe after 6-8 weeks learning. So that’s pretty good.

I also want to write some more code and do less architecting. I decided to take at least one of those interview books and work through it!

*Three Beautiful Quicksorts*

By Jon Bentley! I said that before but I think quicksort is beautiful so I was intrigued by the title.

Jon Bentley presents different variants of Quicksort for different purposes. I really like his style.

One thing I remember well was about calculating the average number of comparisons. Instead of doing it mathematically or letting the algorithm run and count each comparison, he abstracted everything away.

This reminded me of the Tower of Bable and similar algorithms. I always tried to solve the problem ‘physically’ instead of abstracting everything away we don’t need.

I decided to start with *Coding Interviews* by Harry He.

**STAR pattern**

Is used to describe projects:

**S**ituation: Background, features, customers**T**ask**A**ction: What were the requirements/limitations/approaches for the tasks**R**esult

Questions:

- Most difficult issue?
- Lessons learned?
- Conflict with others?

*How would you convert a string into an integer?*

Interesting question. I like to start looking at the input and output.

**Output: Integer**

- How big? 32bit, 64bit, bignum?
- In which system (decimal, binary, …)?
- Which representation (just digits, scientific, etc)?

**Input: String**

- Which system?
- How big?
- Which representation?
- How should empty strings be handled?
- How should invalid strings be handled?
- What about the encoding (ISO-8859-1, UTF-8, etc)?

I assume, for the sake of simplicity, that it should be able to handle only ascii strings consisting of digits which fit into 32bit integers. If there’s a problem it should throw errors.

Here’s a short version of how you could solve the problem:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | public static function convert($string) { if (false === is_string($string)) { throw new \BadMethodCallException("The input has to be a string!"); } // Regexs matches a string of digits with an optional + or - sign at the start if (0 === preg_match("/^[-+]?[0-9]+$/", $string)) { throw new \BadMethodCallException("The input strings doesn't just consist of digits!"); } if (0 === strlen($string)) { throw new \BadMethodCallException("The input string is empty!"); } $result = 0; $sign = 1; $characters = str_split($string); foreach ($characters as $char) { if ($char === '-') { $sign = -1; } elseif ($char === '+') { $sign = 1; } else { $result = $result * 10 + intval($char); } } $result *= $sign; return $result; } |

There’s also a nice testing suite behind that. This is my final product though given those hard restrictions on the input. I first forget to check whether the input is actually a string. The ‘main’ algorithm however, is pretty simple. I also started to write tests first. It’s mainly because there wasn’t much exploration in this example. I knew what I expected the function to do so it’s easy to write tests for it.

Here are the tests:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 | class StringToIntegerTest extends PHPUnit_Framework_TestCase { /** * This function is used to simplify tests which should be successful * @param $string string A integer string to test * @param $integer int An integer to compare to the string */ protected function simplifySuccessfulTests($string, $integer) { $result = \CodingInterviews\chapter1\StringToInteger::convert($string); $expected = $integer; $this->assertEquals($expected, $result); } public function testPositiveStrings() { $this->simplifySuccessfulTests("1234567890", 1234567890); $this->simplifySuccessfulTests("0123", 123); $this->simplifySuccessfulTests("000123", 123); $this->simplifySuccessfulTests("0", 0); $this->simplifySuccessfulTests("5", 5); $this->simplifySuccessfulTests("+0123", 123); } public function testNegativeStrings() { $this->simplifySuccessfulTests("-1234567890", -1234567890); $this->simplifySuccessfulTests("-0123", -123); $this->simplifySuccessfulTests("-000123", -123); $this->simplifySuccessfulTests("-0", -0); $this->simplifySuccessfulTests("-5", -5); } /** * @expectedException \BadMethodCallException */ public function testMalformedStringCharacter() { \CodingInterviews\chapter1\StringToInteger::convert("1234F"); } /** * @expectedException \BadMethodCallException */ public function testMalformedStringSign() { \CodingInterviews\chapter1\StringToInteger::convert("&1234"); } /** * @expectedException \BadMethodCallException */ public function testMalformedStringHexadecimal() { \CodingInterviews\chapter1\StringToInteger::convert("0x1F"); } /** * @expectedException \BadMethodCallException */ public function testMalformedStringEmpty() { \CodingInterviews\chapter1\StringToInteger::convert(""); } /** * @expectedException \BadMethodCallException */ public function testMalformedInputBool() { \CodingInterviews\chapter1\StringToInteger::convert(false); } /** * @expectedException \BadMethodCallException */ public function testMalformedInputFloat() { \CodingInterviews\chapter1\StringToInteger::convert(123.456); } /** * @expectedException \BadMethodCallException */ public function testMalformedInputObject() { \CodingInterviews\chapter1\StringToInteger::convert((object)'foo'); } } |

*In a 2D matrix, every row is increasingly sorted from left to right, and the last number in each row is not greater than the first number of the next row. Please implement a function to check whether a number is in such a matrix or not.*

Never had to do something like that but I like it! There are several questions again, like how does the indexing work, etc.

But let’s think about it. We can use a kind of binary search. Or if we do some nifty indexing we can use the standard implementation of a binary search. I show you how:

Let’s take this matrix:

1 2 3 | 1 3 4 7 9 13 16 19 23 |

Let’s say that the first index is the row and the second the column. E.g. `array[0][2] = 4`

and `array[2][0] = 16`

. That is, our index runs like that:

1 2 3 4 5 6 7 | 0 0 = 0 0 1 = 1 0 2 = 2 1 0 = 3 1 1 = 4 1 2 = 5 2 0 = 6 |

…

I wrote the indexes of a 1D array on the right. We can now write a function to convert one representation to the other:

**From 2D to 1D:**

1 | $index = 3 * $row + $column |

or more general

1 | $index = $COLUMN_LENGTH * $row + $column |

**And 1D to 2D:**

1 2 | $row = floor($index / 3) $column = $index % 3 |

And then just do normal binary search!

*In a 2-D matrix, every row is increasingly sorted from left to right, and every column is increasingly sorted from top to bottom.*

Here’s an example:

1 2 3 4 | 1 3 7 9 3 4 7 10 6 7 9 13 10 14 19 23 |

The first thing I see is that we can get a good idea about whether a number is in this array from the rows. Let’s say we’re looking for the number 5. We know that it can only be in the first or second row because the third one starts with 6 > 5.

However, in the worst case our target number is bigger than the first element in the last row then we have to search everything.

We also can take a look at the last number in each row!

Let’s take a look at our example in this way:

1 2 3 4 | 1 to 9 3 to 10 6 to 13 10 to 23 |

That’s pretty good. Let’s say we’re looking for 12, we know that we just have to search in the third and forth row. The worst case becomes a lot less worse than it was before.

So, we could do the following: Do a search for the possible range at the start of the row, then for the end of the row. Now, we have all possible rows selected and for each row we could do a binary search.

The book takes an other approach which I quite like. It presents a diagonal binary search.

*Given two sorted arrays, denoted as array1 and array2, please merge them into array1 and keep the merged array sorted*

Trees immediately pop into my head. In C I would iterate through both with pointers backwards and then fill the array1 from behind. However in PHP that’s not very idiomatic or possible.

I think idiomatic solution would be to construct a new array on the fly by simply iterating through both. The construct would be a while which checks whether `index1`

and `index2`

is less than their length. That would be the replacement for the pointer.

*Please design a queue with two stacks and implement methods to enqueue and dequeue items.*

This is an interesting question. I started working it out with two items and then with three and four to finally find a working solution.

I thought about the tower of bable which is similar. In the tower we have 3 stacks. Here just two but we have to do less.

Here’s a simple solution. We just take one stack and push our elements on it. If we want to dequeue an item we put everything but the last element onto the other stack and pop the last out. Now, we would have a neatly sorted stack from which we can dequeue in O(1).

We can pop from that as long as there’s something on it! In the meantime we add to the other stack to build the queue up. If the sorted stack is empty, we just repeat our pushing operation and start again!

*Please implement the function double Power(double base, int exponent) to raise a number base to power of exponent.*

Ok, several things to consider:

- Valid input types
- Valid input
- The algorithm
- How to deal with overflow
- How to deal with undefined behavior

I start again writing test cases. One super problematic thing is negative exponents thanks to floating operations. E.g. `Power(3,-1) = 0.3333333`

; Because I don’t want to write all that comparisons logic for floats I limit my code to non-negative exponents.

Here’s my code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | public static function power($base, $exponent) { if(is_double($base) === false) { throw new \BadMethodCallException("Base has to be double!"); } if(is_int($exponent) === false) { throw new \BadMethodCallException("Exponent has to be an integer!"); } if($exponent < 0) { throw new \BadMethodCallException("Negative exponents aren't supported!"); } if($exponent === 0 && $base === 0.0) { throw new \BadMethodCallException("Power(0,0) is not defined!"); } $result = 1; for($iteration = $exponent; $iteration > 0; $iteration--) { $result = $result * $base; if(is_nan($result) === true) { throw new \DomainException("Result is too big or too small!"); } } return $result; } |

It’s a primitive algorithm but is good enough for that case. You can implement a faster one by considering the odd and even cases of exponents.

*How do you find the median from a stream of numbers?*

I remember that I read about a nifty algorithm for that but can’t remember how it worked. I just start with an example.

We have two cases:

- If the amount of numbers is odd, then the median is the middle element
- Otherwise, the median is the average of the left and right element in the middle

The important task to figure out is how to calculate the median. What information do we really need?

Maybe, 3 numbers are enough.

Let’s say we have calculated a median which is 4, the number was odd. We’re also saving the left and right element.

Stream: 3 4 6

Median: 4

Left: 3

Right: 6

Now we can take a look at the next number. There are several possibilities:

- Number is bigger than median
- Number is smaller than median
- Number is equal to median

Let’s look at each individual case:

**Bigger**

Stream: 3 4 6 7

Median: (4+6)/2 = 5

Left: 4

Right: 6

**Smaller**

Stream: 3 4 6 3, sorted: 3 3 4 6

Median: (3+4) / 2 = 3.5

Left: 3

Right: 4

**Equal**

Stream: 3 4 6 4, sorted: 3 4 4 6

Median: (4+4)/2 = 4

Left: 3

Right: 6

In this case we only needed left and right to calculate the median. However, there’s maybe a problem. Let’s see what happens if after the first bigger case, there’s an other one.

**Bigger (2x)**

Stream: 3 4 6 7 8

Median: 6

Left: 4

Right: ???

Here, we don’t have access to 7 without saving the whole stream which isn’t good. So that doesn’t work.

The thing is that we don’t need too many numbers because the median is either a number less, more, equal, or the average. But, we need access to the numbers surround it.

I thought about calculating the average on a stream which is quite easy. But why? Because the average has implicit knowledge. It remembers enough about its past to calculate its future.

Let’s think about the stream a bit. Example stream: 2 9 8 5 4 8 0 2 1 3

1 2 3 4 5 6 7 8 9 10 11 | Number Sorted Median 2 2 2 9 2 9 (2+9) / 2 8 2 8 9 8 5 2 5 8 9 (5+8) / 2 4 2 4 5 8 9 5 8 2 4 5 8 8 9 (5+8) / 2 0 0 2 4 5 8 8 9 5 2 0 2 2 4 5 8 8 9 (4+5) / 2 1 0 1 2 2 4 5 8 8 9 4 3 0 1 2 2 3 4 5 8 8 9 (3+4) / 2 |

I can’t come up with the ideal algorithm. The book took several approaches were they saved all the data in trees. That’s ok but I remember a better solution.

I think I found the solution, it’s called FAME which has complexity of O(N) but a storage of 2. It’s an heuristic algorithm though.

*Unbreakable Domain Models*

- Bounded context should be checked, e.g. if you have two different kinds of behaviour for one object, make two separated contexts
- Value objects: (e.g. Money, e-mail address, distances)
- Equality by Value
- Immutable
- Entity: (e.g. Customer)
- Equality by Identity
- Mutable
- Has a life cycle
- You can start modelling everything as value object first. And then introduce entities if you need identity

That was a great talk! Very practical and understandable.

I improved my project a bit more. Finally written a nice router. I’m actually pretty proud. It’s neat and simple. Also written some more tests and added XSS protection. Now I want to add some build script for the DB and then I can deploy it finally.

### Updates Goals:

- Get a bit more exposure to OOP and OOD
- Learn a bit more about MySQL
- Learn Symfony2
- Write at least one web app using Symfony2 and its core components (templating, testing, forms, validation, security, caching, i18n)
- Watch one video per day on average

### Progress status

#### In Progress

- Watch one video per day on average [40 of 75]