# AVL tree

Published , updated
Tags:

The AVL tree, named after its inventors Georgy Adelson-Velsky and Evgenii Landis, is a type of self-balancing binary search tree. The tree re-organises itself after every insert and delete so that the tree height is approximately \log n nodes high, allowing search in O(\log n) time. The re-organising does not guarantee a perfectly balanced tree, it is however good enough to guarantee O(\log n) search.

# Fibonacci heap

Published , updated
Tags:

A Fibonacci heap is a heap data structure similar to the binomial heap, only with a few modifications and a looser structure. The Fibonacci heap was designed in order to improve Dijkstra’s shortest path algorithm from O(m \log n) to O(m + n \log n) by optimising the operations used most by the algorithm. Its name derives from the fact that the Fibonacci sequence is used in the complexity analysis of its operations.

# Binomial heap

Published , updated
Tags:

A binomial heap is a priority queue data structure similar to the binary heap only with a more strict structure, it supports quicker merging of two heaps in Θ(\log n) at the cost of a slower find minimum operation. A binomial heap is made up of a series of unique ‘binomial trees’ which are constructed from smaller binomial trees.

# Binary heap

Published , updated
Tags:

A binary heap is a binary tree data structure that typically uses an array or list as its underlying data structure. Heaps are one of the fundamental data structures that all software developers should have in their toolkit due to its fast extraction of either the minimum or the maximum element in a collection.

GitHub wikis are great for documentating projects due to their ease of use and high visibility. The problem is though that there are only two options for access; full access for everyone or restricted to collaborators only. Unfortunately it’s rarely the case you want the public to have full edit access to the wiki, and restricted prevents external contributions completely. This article describes how I recently got around this to enable contributions to the Visual Studio Code wiki via pull requests.

Sometimes it’s necessary to redirect a particular event on an element to another element, not just bubble it up through the element’s ancestors. Since an Event cannot be reused once it is thrown, that means it needs to be recreated before being dispatched.

# Find the median of two sorted arrays

Published , updated
Tags:

This article looks at the interview question - Find the median of two sorted arrays. For example an input of [1, 7, 8] and [2, 5, 6, 9] should result in the output 6.

# Bucket sort

Published , updated
Tags:

Bucket sort, also known as bin sort, is a distribution sort that works by arranging elements into several ‘buckets’ which are then sorted using another sort, typically insertion sort, and merged into a sorted list.

The backtick (also known as the grave accent or backquote) is used to start a code section in Markdown, because of this it’s a little tricky to include it without triggering the code formatting in a page. This snippet demonstrates the various ways of displaying a backtick.

Putting yourself out there and answering questions on Stack Overflow is a great way to grow as a software developer. Not only does it let you practice more at what you’re good at, it also let’s you dip your toes into areas where you’re less familiar or learning. There is a lot to providing great answers on Stack Overflow, here are some tips to help out.

This snippet is useful when applied to events that occur many times such as resize and scroll, particularly when the callback does heavy processing. It throttles the calls to the callback by only calling in to the callback if the event has not occurred again in the last 300ms. This technique is called ‘debouncing’.

# Sorting algorithms

Published , updated
Tags:

A sorting algorithm takes a list of items and sorts them in a particular order, most commonly alphabetically or numerical.

# Counting sort

Published , updated
Tags:

Counting sort is a distribution sort that achieves linear time complexity given some trade-offs and provided some requirements are met.

Stack Overflow is a brilliant resource for asking software development questions. There is a certain amount of etiquette you should follow though that isn’t immediately obvious to new users. This article tries to clear this up so you can get down to asking great questions and helping the site, the industry and the web grow.

CSS preprocessors like LESS, Sass and Stylus have come a long way in the short period of time they’ve been around, and they aren’t going anywhere. If you haven’t looked into them yet, now is as good time as any to get into them! Here’s why.

So Google+ dropped an update on us yesterday which allows full-sized image previews and descriptions for page shares! No longer will you have to share images and include a link to get more presence on Google+ feeds. This article will tell you how to get them up on your site!

East-Asian languages are a bit of a mess on the internet for a number of reasons, such as browser implementation, the presence of system fonts and web developers neglecting to address the issue on their side. This article dives deep into how languages work on the web and the problems that can occur.

# Given random5(), implement random7()

Published , updated
Tags:

This article looks at the interview question - Given the function random5 that generates and returns a uniformly distributed random integer from 1 to 5, implement random7 that returns a uniformly distributed random integer from 1 to 7.

Git is a source control (or version control) system designed and developed by Linus Torvalds back in 2005 for the development of the Linux kernel. Similar to other source control systems like TFS or Subversion, it manages your source code enabling a team to work on the same project while minimising conflicts.

There is a lot to cover when making a website. So much that it’s unreasonable to manually check a site for best practices in SEO, performance, accessibility, style and so on. Luckily the internet has you covered with these great tools to push your site to the next level!

# Bubble sort

Published , updated
Tags:

While studying efficient sorting algorithms is beneficial, studying slow ones, at least initially is as well since it teaches us why they’re bad. Bubble sort is one of those bad sorting algorithms. I recall as a young programmer, around 11 years old before I had any formal training, bubble sort is how I intuitively sorted a list.

# Flyweight design pattern

Published , updated
Tags:

The flyweight design pattern aims to minimise the memory usage of a collection of items by promoting re-use and deferring initialisation.

Sass provides us with a number of helpful tools to share code between CSS rules. This article dives in to the relatively new feature in Sass called placeholder selectors. Looking at how to use this feature correctly, cover some problems that may occur, and examine how it differs from other approaches.

# Visitor design pattern

Published , updated
Tags:

The visitor design pattern provides a method of separating an algorithm on an object and the object’s actual class implementation. This allows the programmer to easily follow the open/closed principle.

# Design patterns

Published
Tags:

Design patterns in software engineering are generic solutions to some commonly occurring problems encountered when creating software. They are incredibly useful tools for both communicating a solution to a problem to other developers and also for saving time solving problems that have already been solved in quite elegant ways. Learning the big design patterns is a also just a great way to improve your skills as a software developer.

# Selection sort

Published , updated
Tags:

Selection sort is an O(n^2) sorting algorithm that works by searching through a list to find the minimum element and swapping it for the first in the list. After every swap, selection sort is performed on the list with the head removed (ie. the minimum element). Due to the way that elements are swapped anywhere in the list, this is not a stable sort.

# output HTML element

Published
Tags:

The output HTML element was introduced in HTML5 and represents a calculated value belonging to a form. An example use case is client-side calculation on a shopping website’s checkout page.

# q HTML element

Published
Tags:

The q HTML element is used to represent an inline quote. Now regular quotes (“”) can represent this just fine, surrounding the quote in the q tag differs in that it explicitly indicates that the text is a quote, removing ambiguities that it could be emphasis, irony, etc.

The feature I’ve wanted for a very long time has finally arrived with Chromium v31; you can now inspect the ::before and ::after pseudo-elements within the Chrome DevTools! It is such a great quality of life change for anyone who spends a decent amount of time tinkering with CSS.

# Moving to the US for work

Published
Tags:

I eventually made it to the US in September and have started working at Amazon! It was a pretty intense period in the couple of months leading up to leaving Australia. I have compiled a list of things that that helped me and also what I wished I had known before starting the move.

The borders in CSS are weighted equally which means if their colours differ, the split between them will be diagonal. This is the reason that CSS triangles work the way they do. Say your design wanted a more rectangular border though, where the top and bottom extended all the way out and covered the bottom portion of the left and right borders.

The one thing I hated about maths in school and university was the fact that I had to show my working. Of course I knew that it helped the marker see that you understood the problem, but I just found it incredibly tedious. Particularly when I knew the answer right after reading the question.

# The Fibonacci sequence

Published , updated
Tags:

This article looks at the interview question - Implement a function that returns the Fibonnaci number for a given integer input.

# Coming to America

Published
Tags:

I’ll be moving to Seattle, Washington with my wife in a couple of weeks as I’ve accepted a position at Amazon! I will be joining the AWS team to work on the Kindle’s cloud-powered browser Silk. Needless to say I’m super excited to get into it :)

# Reverse a string

Published , updated
Tags:

This article looks at the interview question - Reverse a string in the most efficient way possible. For example an input of "abc123" will result in the output "321cba".

# Integer division without the division operator (/)

Published , updated
Tags:

This article looks at the interview question - Implement a function that performs integer division on two integers without the use of the division / operator. For example for the input of 10 and 4 should result in the output of 2.

# All permutations of a set

Published , updated
Tags:

This article looks at the interview question - Implement a function that gets all possible permutations (or orderings) of the characters in a string. For example for the input string "abc", the output will be "abc", "acb", "bac", "bca", "cab" and "cba".

# All combinations of a set

Published , updated
Tags:

This article looks at the interview question - Implement a function that gets all possible combinations (or subsets) of the characters in a string with length of at least one. For example for the input string "abc", the output will be "a", "b", "c", "ab", "ac", "bc" and "abc".

# Splay tree

Published , updated
Tags:

The splay tree is a type of self-adjusting binary search tree like the red-black tree. What makes the splay tree special is its ability to access recently accessed elements faster. Whenever an operation is performed, the tree performs an operation called splaying which pulls the element to the top of the tree.

It is not necessary to expose all methods being tested as public when using an external test project. By using the assembly attribute InternalsVisibleTo and specifying the namespace of the “friend” assembly, the visibility of the methods can then be reduced to internal, hiding them from all other assemblies.

Ever wanted to print a type name as text that the would be suitable for users? For example, converting the type name "SomeTypeName" to "Some type name". I’ve come up with a pretty nice method to convert type names in to nice strings.

A couple of weeks ago I jumped in to Dart with a little project to learn the language; to convert my canvas-astar.js project. I’m glad to say that what Google claims is true, since Dart borrows syntax from some common languages, it’s very easy for the seasoned developer to learn. It took me around an hour of studying and then an hour of porting to get it in the state that it is.

# One year

Published
Tags:

Just over a year has passed since I created my blog and I just wanted to reflect a little on how I feel everything has gone, the impact it’s had on my life and go over the most popular posts to date.

There are a lot of questions on Stack Overflow, probably a lot than you realise. This is understandable when you consider over 7,000 questions are being asked every day. No I’m not just talking about the 5 million odd that you can access via the questions tab (4,930,418 and counting at time of writing). There are also a ridiculous amount of deleted questions which only users with at least 10,000 reputation can see.

The CSS property background-size:cover is incredibly useful but due to the nature of it resizing in different directions, it’s difficult to pinpoint where a particular part of the image is on the background at any given time. Difficult but not impossible of course.

Published
Tags:

I wrote up a little JavaScript plugin over the weekend that has a <table>’s header scroll with the page. What sparked this little endeavour was a question asking for this functionality on Stack Overflow. Since it was fun answering the question, I thought I’d go ahead and make a more general plugin type solution that worked for multiple tables.

You may ask yourself why you would ever want to pass a reference type into a method using the ref keyword, or why the C# compiler even allows this. Using ref on a reference type is actually slightly different to not using it. The difference is that the ref keyword makes it a reference (pointer) to the variable, not just the object. This allows assigning to the source variable of the parameter from within the method.

Here’s a pretty good method of creating a header that has a vertically-centered, horizontal line on the right-hand side of the header. There are a couple of caveats though: it requires a little JavaScript to set an attribute on the headings; and it cannot be used on tiled backgrounds.

# Triangles in CSS

Published , updated
Tags:

Creating triangles with CSS is a pretty good way to reduce the number of images within an application. They’re a bit tricky to get your head around at first but once you understand them it’s really easy.

I stumbled upon this little gem, a search engine called Symbol Hound that unlike Google, doesn’t ignore symbols in fast it is actually optimised for searching with them. It only searches within Stack Overflow but that means it’s very focused on programming and really if you’re not finding your answer to a programming operator question on SO, it deserves to be asked.

This post will show you how to data-bind a hierarchical model that can go infinitely deep onto a page using Knockout.js. In this post, I will make a screen that will be used to build an organisation chart as an example, I chose this as it’s a really simple example to illustrate the technique that I’ll be using.

I’ve compiled some information about time complexity and underlying data structures of .NET simple collections and dictionaries. It was difficult to find some of this information on official sources like MSDN and non-official sources seemed to differ, so I used reflector and actually had a look at the .NET framework code to confirm these cases.

One of the new features in VS2012 is the ability to ‘preview’ a file instead of opening it fully which will open it in the ‘preview’ pane (docked to the right). To do this Left click on the file in the solution explorer. The great thing about it is that you can only have one preview open at a time. So when you’re searching for something looking through several files in the process, the ones that aren’t needed will close themselves.

Unfortunately when deleting items in entity framework the SQL commands are issued as single DELETE statements for each entity. This really becomes a bottleneck when there are a several thousand items. This handy set of extension methods allows convenient and efficient deletion of all entities for a particular type T. The GetTableName<T> used function even takes into account table mappings set up with the ModelBuilder.

.NET allows us to set the size of a List<T> in the constructor if we know the capacity ahead of time. This will save the List’s inner (dynamic) array from being reassigned (and copied) when items are added. While usually this will make a minuscule change to your program, if the list is large enough it saves quite a few operations.

If you haven’t experienced the power of the System.Threading.Tasks namespace new in .NET 4 you’re missing out. This post is about the Parallel class which takes all of the complexity out of the seemingly simple task of running multiple functions in parallel.

You can apply fonts based on unicode character codes using the unicode-range CSS3 rule. Fonts with a unicode-range rule will only target the specified range and fall back to other fonts with characters not in the range. Multiple ranges can be used by separating them with a comma.

# Merry Christmas!

Published
Tags:

Merry Christmas everyone! Here is a CodePen I whipped up to celebrate, fitting based on the recent posts. A binary Christmas tree :)

Make sure for code documentation you use the razor-style comments in your ASP.NET MVC views, not HTML-style comments. Regular HTML comments will be sent to the client which would increase the page size and expose unnecessary implementation details to the end-user, razor comments are kept server-side.

Published , updated
Tags:

The facade design pattern is a very simple pattern that provides a simplified interface to other code that may not be structured the same way.

# Red-black tree

Published , updated
Tags:

The red-black tree is a type of self-balancing binary search tree that assigns a colour of red or black to each node. On every insert or delete, the tree re-organises itself so that it is approximately \log n nodes high, allowing search in O(\log n) time. The re-organising does not guarantee a perfectly balanced tree, it is however good enough to guarantee O(\log n) search.

# Quicksort

Published , updated
Tags:

Quicksort is an O(n^2) sorting algorithm that runs in O(n \log n) time on average. It has a number of favourable qualities; it’s an in-place sort, requiring O(\log n) auxiliary space in the worst case; and is also a divide and conquer algorithm making it easy to parallelise. Unfortunately however it’s not a stable sort.

# Factory method design pattern

Published , updated
Tags:

The factory method design pattern attempts to implement the concept of real-world factories within your program. Instead of the object creating itself, the task of creation is given to a ‘factory’ object.

# Heapsort

Published , updated
Tags:

Heapsort is an O(n \log n) sorting algorithm that works by first constructing a heap out of the list and repeatedly pulling the root off the top of the heap and reconstructs it until there are no items left in the heap. The values that are pulled off of the top of the heap come out in sorted order. If the heap used was a min-heap, the resulting list will be in ascending order, and a max-heap will give them in descending order.

Have you ever started working on a giant project containing many JavaScript files and needed to find out what some random button is doing? A pretty easy way to find out is to enable the mouse click’s event listener breakpoint in the Chrome developer tools. This will break execution when you next click on the page allowing you to step into the code seeing exactly what is happening.

# Binary search

Published
Tags:

Binary search is a decrease and conquer search algorithm than can be used on a sorted array. It operates by determining whether the search value is less than or greater than the middle value and recursively calling itself on the lower or upper half of the list respectively until either the value is found or not found.

Published
Tags:

A continuation of my post CSS selectors you must know, this one is going to look at the more advanced selectors available to us. Each section will first describe what is selected and then provide an example first with the CSS and then the HTML if applicable, the selected elements will be marked.

# Insertion sort

Published , updated
Tags:

Insertion sort works by looking at each item in an array (starting with the second) and comparing it with the item before. If the item before is larger, they are swapped. This continues until the item is smaller at which point we do the same for the next item.

# Merge sort

Published , updated
Tags:

Merge sort is a sorting algorithm that runs in O(n \log n) time. It is a divide and conquer algorithm, so it can get the most out of today’s multi-cored systems. It works by continually splitting up the array until each item stands on its own. The items are then merged back with the items that they were split with in the correct order.

# Decorator design pattern

Published , updated
Tags:

The decorator pattern allows behaviour to be added to an existing object at runtime. This is achieved by wrapping the object (the component) in another class (the decorator).

# Big-O notation

Published
Tags:

This article looks at the definition of Big-O notation, how it works and provides some code examples of different Big-O time complexities.

Being a someone that is a little OCD about organisation, I was a little disappointed when I couldn’t immediately figure out how to name the Windows 8 app groups on my new start screen. You can do it, it just may not be immediately obvious for everyone.

A handy little trick that’s global to most of Google’s core services. Press Shift + / (?) or Ctrl + / to display an overlay containing the hotkeys for the application. To hide it you can repeat the hotkey, press Esc or click off the overlay.

# Binary search tree

Published , updated
Tags:

A binary search tree (BST) is a node-based tree data structure in which each node can have at most two children, it supports several operations common to any search tree such as search, insert and delete.

In response to Ron’s comment on the attr('id') vs [0].id post last week asking about the jQuery.fn.prop’s vs jQuery.fn.attr’s performance, I extended the program to include prop and enabled profiling across all browsers (thanks to time.js). The program also does the tests a little more thoroughly, running 1000000 operations 5 times per each operation and averages the result.

In version 12 of Chrome they added the ability to de-obfuscate (un-minify?) the JavaScript on the sources tab by right clicking the code area. Today that feature lives on in the “pretty print” feature located at the curly brace icon on the bottom of the debugger.

So I was wondering for a while exactly what the performance difference is between the jQuery function attr('id') and getting the native JavaScript object and grabbing the id that way was. Surely attr('id') was slower but how much slower… I decided to write a little HTML page that tested each method by doing 1 million operations of each. In interest of being complete I added the getAttribute and get(0).id methods also.

Here’s a cool little effect that can be applied to buttons/images/etc. on hover, it slides the button down using top/bottom margins and fades the button slightly into the background. Subtle effects like this really add to a web site in my opinion.

I put together a CodePen demonstrating a method for creating a ‘trail’ effect using canvas. The method involves drawing a slightly transparent rectangle over the canvas every time the program loops. This creates the fading gradient effect.

# Redesign #1

Published
Tags:

I decided to give the blog a major overhaul and redesign the template as previously it was just using a one of the built-in Blogger templates with a few minor alterations. I was originally quite hesitant in modifying the template directly as I didn’t really understand how it was put together, the blog has been in place for some time now so I thought it was about time to give it a go.

One of the things that made me fall in love with Sass was the ease of including large chunks of CSS very easily using mixins. This happens to also be one of the main criticisms of Sass due to the CSS it results in. Consider the following Sass which applies the IE6/7 hack to enable the use of the then unsupported inline-block to 3 selectors.

I thought it would be fun to try my hand at producing a similar effect as the Visual Studio 2012 installer working/busy animation using pure-CSS. I think it turned out pretty well, it works in Opera, Safari, Chrome and Firefox.

Here is a method for selecting a column in a table using the selector :nth-child(n). You could then do whatever you want to it, like hiding or highlighting it. An example use could be showing that a particular column has been sorted, instead of the more traditional method of showing some indicator on the header.

I had a problem a while back where an IIS 6 server was not serving .docx extension files even though they were definitely there on the server. I immediately thought that the .docx MIME type must not be included in IIS 6 by default and it turns out that was the cause of the problem.

The difference between pseudo-classes and pseudo-elements can be a little confusing until you have it spelt out for you. Basically a pseudo-class is a selector that assists in the selection of something that cannot be expressed by a simple selector, for example :hover. A pseudo-element however allows us to create items that do not normally exist in the document tree, for example ::after.

Here is a collection of CSS selectors that you really need to know if you work with CSS. Each section will first describe what is selected and then provide an example first with the CSS and then the HTML if applicable, the selected elements will be marked.

# Extension methods

Published
Tags:

Extension methods are a nice piece of syntactic sugar added to C# version 3.0 as part of .NET framework 3.5. They allow you to add methods to existing types, for example you can add a new method to the type System.String or System.IO.File.

If you’ve been coding in C# for a while you may have noticed the Func<> parameter type presented in several places, particularly LINQ which uses it extensively. You may know how to use it but have you ever thought about what it is exactly and how to go about using it in your own functions?

# Delegation design pattern

Published , updated
Tags:

The delegation design pattern allows an object to delegate one or more tasks to a helper object. Two classes are used to achieve this; the delegate and delegator, both which realise a common interface. A method (or methods) on the interface represent the functionality to be delegated. A call to the delegator calls the matching function on the delegate.

I was faced with a problem recently where a web page needed to create an email with the user’s email client. This is normally trivial, simply redirect the user to mailto:<emails>. The issues was that the maximum length of a URL across different platforms is approximately 2000 characters, and the amount of emails required far exceeded that in some cases. So a solution would need to make multiple mailto requests.

Sass is awesome, I first discovered it around 9 or so months ago now and have loved it ever since. Recently I implemented an unplanned theme system to a web app and because I was doing the styles in a modular/extendable way thanks to Sass, it was very easy. It took around around 30 minutes to have 8 distinct colour themed stylesheets.

A CSS reset is a chunk of CSS that attempts to “reset” all styles so that a web developer can start with a plain canvas that is consistent across browsers. Having all styles uniform including heading tags makes the web site much easier and nicer to style.

HTML elements such as div, span, img, etc. don’t normally accept input, but sometimes you’ll want them to. For example if you have an image that does something when you click on it. If you want your site to be accessible it also needs to happen when you tab to the element and press enter.

This is the easiest and best way to center text vertically, simply set the line-height to the same value as height. Remember that in order to modify the height of an element, it needs to be displayed as either a block or inline-block.

Something everyone who works with jQuery should know, how to pass parameters to a jQuery event handler. Pass a data object as the first argument on the event, the contents of the object will be transferred onto the data variable of event.

# A* pathfinding algorithm

Published , updated
Tags:

Game development introduced me to programming when I was around 10 years old, and I’ve loved it ever since. One of the first formal algorithms I learned before entering university was A* (pronounced “A star”), and I really had a great time learning about it. It’s one of the most widely used pathfinding algorithms and is one that you would likely be introduced to first when approaching the subject of pathfinding. A pathfinding algorithm takes a start point (also known as a node) and a goal and attempts to make the shortest path between the two given possible obstacles blocking the way.

I’ve become a big fan of the idea in user interfaces that images are faster than words, providing of course that the images do actually represent the idea they are trying to communicate. That latter point is incredibly important, if the icons are badly chosen then it just introduces confusion for the user.

# Touch != Click

Published
Tags:

I started programming for Android a few months ago, starting a few apps while playing around with the API, re-familiarising myself with Java and getting a feel for mobile development. Having spent the majority of my programming time during the last couple of years using WinForms, ASP.NET and other Microsoft technologies, I’ve really enjoyed breaking out and trying something new.

Sass stands for Syntactically Awesome Stylesheets, yes, I’m quite a fan of the name. It provides us with a much simpler and more elegant way of defining CSS, allowing the creation of more modular and manageable stylesheets. Sass has two flavours; Sass-style and SCSS-style, the basic difference being that Sass-style uses indentation to separate code-blocks instead of curly braces. The examples used in this post will be using the SCSS-style.