# Computer Algorithms: Finding the Lowest Common Ancestor

## Introduction

Here’s one task related to the tree data structure. Given two nodes, can you find their lowest common ancestor?

In a matter of fact this task always has a proper solution, because at least the root node is a common ancestor of all pairs of nodes. However here the task is to find the lowest one, which can be quite far from the root.

We don’t care what kind of trees we have. However the solution, as we will see, can be very different depending on the tree type. Indeed finding the lowest common ancestor can have linear complexity for binary search trees, which isn’t true for ordinary trees. Continue reading Computer Algorithms: Finding the Lowest Common Ancestor

# Computer Algorithms: Data Compression with Diagram Encoding and Pattern Substitution

## Overview

Two variants of run-length encoding are the diagram encoding and the pattern substitution algorithms. The diagram encoding is actually a very simple algorithm. Unlike run-length encoding, where the input stream must consists of many repeating elements, as “aaaaaaaa” for instance, which are very rare in a natural language, there are many so called “diagrams” in almost any natural language. In plain English there are some diagrams as “the”, “and”, “ing” (in the word “waiting” for example), “ a”, “ t”, “ e” and many doubled letters. Actually we can extend those diagrams by adding surrounding spaces. Thus we can encode not only “the”, but “ the “, which are 5 characters (2 spaces and 3 letters) with something shorter. In the other hand, as I said, in plain English there are two many doubled letters, which unfortunately aren’t something special for run-length encoding and the compression ratio will be small. Even worse the encoded text may happen to be longer than the input message. Let’s see some examples.

Let’s say we’ve to encode the message “successfully accomplished”, which consists of four doubled letters. However to compress it with run-length encoding we’ll need at least 8 characters, which doesn’t help us a lot.

```// 8 chars replaced by 8 chars!?
input: 	"successfully accomplished"
output:	"su2ce2sfu2ly a2complished"
```

The problem is that if the input text contains numbers, “2” in particular, we’ve to chose an escape symbol (“@” for example), which we’ll use to mark where the encoded run begins. Thus if the input message is “2 successfully accomplished tasks”, it will be encoded as “2 su@2ce@2sfu@2ly a@2complished tasks”. Now the output message is longer!!! than the input string.

```// the compressed message is longer!!!
input:	"2 successfully accomplished"
```

Again if the input stream contains the escape symbol, we have to find another one, and the problem is that it is often too difficult to find short escape symbol that doesn’t appear in the input text, without a full scan of the text. Continue reading Computer Algorithms: Data Compression with Diagram Encoding and Pattern Substitution

# A JavaScript Trick You Should Know

## JavaScript Strings

You should know that in JavaScript you cannot simply write a multilined code chunk, i.e. something like this:

```var str = 'hello world';```

This will result in an error, which can be a problem when you deal with large strings. Imagine a string containing some HTML that should be injected via innerHTML. Now one possible solution is to concatenate two or more strings, by splitting the initial string.

```var str = 'hello' + 'world';```

Howerver this solution result in some additional operations like concatenation. It can be very nice if there was something like the PHP multiline string format.

## The PHP Example

In PHP you have the same use case with strings. You can have a string concatenated over multiple lines, but you cannot split lines like so:

```// the following line is wrong \$str = 'hello world';   // a possible solution to the line above is \$str = 'hello' . 'world'; // which is very similar to the js solution in the second example   // ... but in PHP there is the so called HEREDOC \$str = <<<EOD hello world EOD;```

The heredoc gives us the power to write multiline strings.

## The JavaScript Trick

Actually in JavaScript there is something that’s exactly what Heredoc is meant to be for PHP. Take a look at the last example:

```var text = <> this <br /> is my multi-line text </>.toString();   document.body.innerHTML = text;```

Thus you can write multiline strings in the JavaScript code.

# How to Collect the Images and Meta Tags from a Webpage with PHP

## Meta Tags and the Facebook Example

You’ve definitely seen the “share a link” screen in Facebook. When you paste a link into the box (fig. 1) and press the “Attach” button you’ll get the prompted cite parsed with a title, description and possibly thumb (fig. 2). This functionality is well known in Facebook, but it appears to be well known also in various social services. In fact Linkedin, Reddit, Dzone‘s bookmarklet use it.

Fist thing to notice is that this information, prompted by Facebook, is the same as the meta tag information. However there is a slight difference.

Facebook prefers for the thumb the image set into the <meta property=”og:image” … />. In the case above this tag appears to be:

`<meta property="og:image" content="http://b.vimeocdn.com/ts/572/975/57297584_200.jpg" />`

And the image pointed in the SRC attribute is exactly the same as the one prompted by Facebook (fig. 3).

First thing to note is that the real thumb is bigger than the thumb shown in Facebook, so Facebook resizes it and the second thing to note is that there are more meta tags of the og:… format. Continue reading How to Collect the Images and Meta Tags from a Webpage with PHP