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
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→
Do you know that objects in PHP5 are passed by reference, while arrays and other scalar variables are passed by value? Yes, you know it, but it’s not exactly true. Let’s see some example and let’s try to answer few questions.
// depending on the machine but both lines return// expectedly equal values: 331208// 331208echomemory_get_usage();echomemory_get_usage();
// depending on the machine but both lines return
// expectedly equal values: 331208
// 331208
echo memory_get_usage();
echo memory_get_usage();
These two lines of code, expectedly return the same value (in my case 331208), which shows us that because nothing happened in between them the memory usage isn’t growing. Let’s now put some code in between them.
Heapsort is one of the general sorting algorithms that performs in O(n.log(n)) in the worst-case, just like merge sort and quicksort, but sorts in place – as quicksort. Although quicksort’s worst-case sorting time is O(n2) it’s often considered that it beats other sorting algorithms in practice. Thus in practice quicksort is “faster” than heapsort. In the same time developers tend to consider heapsort as more difficult to implement than other n.log(n) sorting algorithms.
In the other hand heapsort uses a special data structure, called heap, in order to sort items in place and this data structure is quite useful in some specific cases. Thus to understand heapsort we first need to understand what is a heap.
So first let’s take a look at what is a heap.
Overview
A heap is a complete binary tree, where all the parents are greater than their children (max heap). If all the children are greater than their parents it is considered to call the heap a min-heap. But first what is a complete binary tree? Well, this is a binary tree, where all the levels are full, except the last one, where all the items are placed on the left (just like on the image below).
If we talk about arrays and linked lists we know the pros and cons about both of them. No matter which programming language we use arrays benefit from direct access to its items, while linked lists are more memory efficient for particular tasks.
Array & Linked List
The items of a linked list keep a reference to their successor, so we can easily walk through the entire list. However we don’t have direct access to its elements. Thus we can’t go directly to its middle element! Even more – in particular implementations of a linked list we don’t know its length. But in some cases linked lists are far more effective than arrays. For instance reversing an array of non-numeric values require constant additional memory, but also requires n/2 exchanges. The same taks using linked lists is not only performed in linear time, but doesn’t require any additional memory. The only thing we need to do is to reverse the links – no movement of values and the items remain at the same place in the memory.
Merging of two arrays often require more space (proportional of the space of the two arrays) or many exchanges in case we try to do it in place. The same task on linked lists is far more effective with only changing pointers and without moving the values. Continue reading PHP: Arrays or Linked Lists?→
Linked lists are one very common and handy data structure that can be used in many cases of the practical programming. In this post we’ll assume that we’re talking about singly linked list. This means that each item is pointed by it’s previous item and it points to it’s next item. In this scenario the first item of the list, its head, doesn’t have an ancestor and the last item doesn’t have a successor.
Sometimes, due to bugs or bad architecture or complexity of the applications we can have problems with lists. One very typical problem is having a loop, which in breve means that some of the items of the list is pointed twice, as shown on the image below.
So in first place we need to be sure that there is a loop and then: how can we break it!
