Tag Archives: html

Computer Algorithms: Finding the Lowest Common Ancestor

algorithms, data structures, , , , , , , , , , , , ,

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.

Finding the Lowest Common Ancestor
Finding the Lowest Common Ancestor

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

algorithms, PHP, , , , , , , , , , , , , ,

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"
output:	"2 su@2ce@2sfu@2ly a@2complished tasks"

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, micro tutorial, PHP, , , , , , , , , , , , , , ,

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.

jQuery.unbind()

javascript, micro tutorial, , , , , , , , , , , , , , , , , ,

Binding Problems

jQuery JavaScript Library
jQuery JavaScript Library

Typically in jQuery when you bind an HTML element with some event this event is fired every time the user (client) triggers it. Thus when you’ve a click event attached on a button you can click it as many times as you want. In some rare cases this can be tricky. Let’s imagine the following scenario.

  1. The user clicks on a “vote” button.
  2. Some AJAX calls are performed.
  3. After a successful AJAX call you setup a cookie to deny further votes from this machine.

This seems to be pretty well known scenario, but as the click event is attached to the button there is enough time to click several times on the “vote” button and to vote several times. In this case before the cookie is set the user can vote more than once. Continue reading jQuery.unbind() →

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

micro tutorial, PHP, web development, , , , , , , , , , , , , , , , , ,

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.

Facebook Attach a Link Prompt Screen
fig. 1 - Facebook Attach a Link Prompt Screen

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 Attached Link Screen
fig. 2 - Facebook Attached Link Screen

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).

Vimeo Thumb
fig. 3 - Vimeo Thumb

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 →