Kselftest is an effort to enable a developer-focused unit test
framework in the kernel to ensure the quality of new kernel
releases.
- Shua Khan
Install and run Linux kernel selftests on Ubuntu 16.04
A Fenwick tree is a data structure that holds an ordered collection and supports
the operations sum and update, both in O(log n) time.
… understand just how astonishingly commonplace (and important) graph problems are
they should be part of every working programmer’s toolkit.
- Stevey
The graph data structure is of high utility across the field of computer science. Graph problems come in many shapes and sizes but once modeled can typically be represented by a limited number of graph data type variants.
To appreciate programming as an intellectual activity in its own right … you must read and write computer programs - many of them.[ASS96]
For the past nine weeks I have been working on programming questions at HackerRank completing questions in the ‘practice area’ i.e I have not competed in any competitive programming competitions offered by the site. Today I reached the first milestone I had set, namely, to get a top 1000 ranking (96th percentile) in the algorithms sub domain.
A heap is a data structure that supports the operations insert and extract. Heaps typically come in two varieties, min heap (for extracting the minimum value) and max heap. A heap is built using a binary tree where each node is said to dominate the nodes below it. The meaning of dominate depends on the type of heap being implemented, for a min heap the key of each node is less than the keys of both of child nodes.
A deque is type of queue which enables adding and removing items from both ends. Deque ends have such names as left/right, front/rear or, as we will use here, front and back. The add/remove operations on a deque are typically called enqueue and dequeue. For ease of explanation but without loss of generality, we limit discussion to a deque of integers.
A binary search tree (BST) is a binary tree where each node has a comparable key. As with any tree, nodes may optionally contain satellite data.
A BST can support many dynamic container operations, including search, minimum, maximum, predecessor, successor, insert and delete. The defining feature of a BST is that keys are maintained in an ordered fashion. This makes a BST a useful data structure for implementing such things as ordered sets and bags.
A bag is a container of non-unique items. Bags are defined by the following operations Length, Add, Delete and Find. Bags often also need to support FindAll.
Bags can be ordered or un-ordered. This post will be discussing un-ordered bags.
A queue is a container that supports retrieval by first-in, first-out (FIFO) order. The get and put operations for a queue are usually called enqueue and dequeue, other operations may include isEmpty. A full description of queues can be found online here.
Queue’s minimise the maximum time spent waiting, however the average wait time will be the same whether a LIFO or a FIFO is used.
A stack is a container that supports retrieval by last-in, first-out (LIFO) order. The get and put operations for stacks are usually called push and pop, other operations may include peek and isEmpty. A full description of stacks can be found online here.