Who’s up for a challenge?

15Sep/068

Who’s up for a challenge?

Before starting this blog up, I spent a bit of time thinking about the kind of things I would like to talk about which other people might find interesting. I also wanted to find some areas of discussion where people would be interested in giving me feedback and comments containing their thoughts and opinions so that I can learn something and possibly benefit from other people's experience. While this is all very enlightening, it can be fun and it can be, shall we say, political.

So as well as having lots of industry-specific rants, posts on what's considered good and bad, and large chunks of text relating to experiences while out on site working for clients, I thought it'd be a good thing to post some other bits and pieces that are a bit more light hearted, and dare I say it... FUN!

Way back before I went to the U.K. I used to have a site up and running that had a small community of people interested in programming - specifically game development. While this site is long gone, never to be remembered, there were a few things that we used to do there which I thought were really good. One of which was listing programming challenges. Every now and then I'd come up with (or rip off) a programming challenge that I thought would be a good exercise for members of the community to undertake. It was surprising how many people were interested, and we ended up with many responses and submissions containing solutions to the problems.

The beauty of it was that people learned a lot from the exercise - especially from each other's varied approaches. They would come up with a solution and be eager to post it. After noticing that someone else had created a "better" solution than them, members would go away and try and improve what they had. It was great, as it bred a mindset of iteration and improvement, and over time most of the community members ended up being comfortable with the idea that their first solution generally isn't perfect and they immediately look to make it better.

I'm of the view that the first solution that you write to solve a given problem is designed to give you a better understanding of the problem space. Sure, it's not always the case that you can throw away the code you've written (depending on what you're working on, and what timelines you have to adhere to), but if you can it's a good idea to do it and start again fresh with the knowledge you've gained from your first attempt.

I would like to get this type of thing going again. I'm going to get some ideas together for problems and start posting them here for other people to have a stab at. I'll be giving some of them a go as well, and if people are interested in sharing their solutions and discussing them, they can post their solutions as comments. If the idea becomes popular and the number of submissions goes up, then I may think about setting up a basic Coding Challenges forum for the discussion and submission of the problems and solutions. If people don't like it, I'll probably continue to post them anyway just in case someone at some stage finds them as interesting as I do If anyone's interested in seeing my solution, then I'd be happy to post it.

The problems themselves will most likely be small. I won't be suggesting that people should go away and write a 3D rendering engine just to see the frames-per-second they can achieve on a 386! The problems will have a very small scope - meaning that solutions can be built quickly, and people won't feel that they need to put a massive amount of time in to get the results required. Hopefully they'll be quite challenging despite being small in stature.

One thing I will attempt to do when writing these problems up is make sure that the specification forces the programmer to do as much of the work as possible - without relying on the supporting framework or library set that comes with the language. In general the problems will not have a target language (or language set), but there may be cases where I state that the problem is intended to be solved using C++ or Miranda!

I hope that you'll find the challenges interesting, and that you'll perhaps find the time to give a few of them a go to exercise the mind. I think some of them will be more useful to beginners learning the ropes of development, but I can't see why experienced programmers shouldn't give them a shot. There's always the possibility that we'll learn something.

So let's begin with the first one that's popped into my head. It's a bit of a classic problem, but there's still a chance that people out there might not have heard it before - or more importantly attempted to solve it themselves in code. I first heard about this problem through a friend of a friend of a friend of a ... you get the idea

Challenge #1 - Linked List Loops

"What do you think is the most efficient and resource-friendly way to determine if a singly-linked-list contains a loop?"

When you have an instance of a linked list, it is usually NULL-terminated, that is, the last reference is a NULL reference which tells you that the end of the list has been found. The question asks how you determine if the list is not NULL-terminated, instead the "last" item in the list points back to another item in the list (thus creating a loop in the list).

To solve this problem you will need to have an understanding of Singly-linked lists. You don't need to write code, I'm just interested in the algorithm you'd use.

Sounds easy, and there are quite a few ways of doing it. So give it a shot! I'm interested to see what you guys come up with.

Happy problem solving!

Filed under: Challenges, Software Development Leave a comment

OJ

One more thing that I'd like to say: Keef's solution is commonly known as the "two-walker" method (apparently), though I can't seem to find a link that backs that up :)
OJ

I've just had a nose through the RubyQuiz link that you posted and there does seem to be some good puzzles on there to solve. I think that for the most part they are a little larger than what I intend to post on here, which is a good thing! At least if people become bored with small questions and are looking to get their teeth into something bigger then they can head over there solve until their heart's content. I'll do my best (but that doesn't mean I'll nail it all the time ;)) to post questions that focus on a very small blob of code or a particular algorithm.

Thanks again.
OJ

I hadn't seen the RubyQuiz link before today, thanks for posting it. It does look like it could be a bit of fun! I'll probably keep tabs on that one while I continue to play with Ruby, as it's a language that I'm yet to delve into in depth.

I see the challenge did get you thinking :) Of course, there are usually a bunch of other issues that come along with a problem like this, and I think you may well have covered most, if not all, of them.

I tried to write the definition of the problem in a very compact way in an attempt to focus people on the algorithm rather than the code. This of course forced me (and you guys) to make some assumptions about the code where this might occur.

In an ideal world, there would of course be some form of list management structure/object that ensures that a "loop" such as this would never occur. My assumption here is that, even if there is a list management structure, there is a bug in the code which results in the list incorrectly becoming a circular list - at an unknown point.

That's probably the key piece of information that I left out of the problem spec, but I did that for a reason also - to see what solutions come through which attempt to cater for any loop scenario.

I have actually seen this sort of issue happen in the real world. The most common place you see things like this (in my experience) is where code is attempting to manage one or more "free lists" where the nodes can switch between the lists.

Example: You're writing a little memory manager that is responsible for allocating a block of memory which can be used by a collection of objects, let's say of type T. On start-up, the memory manager allocates a chunk of memory to allow for the use of up to N lots of T at any given time, and it manages that chunk of memory using two separate free lists. At the start, the "allocated" list is empty, and the "unallocated" list has all the nodes in it. As the program continues to execute, and calling objects request allocation of memory for type T, the memory allocator simply removes a node from the "unallocated" list to the "allocated" list (by switching a few pointers around), and returns a reference to the newly "allocated" instance of T for the caller to use. Depending on how good (or bad :)) the author of this memory manager was, issues such as loops in the list can unfortunately become a reality. In this scenario, it is possible, through incorrect ordering of steps or bad management of pointers across the two structures, that the loop can occur almost anywhere in either of the free lists.

So while this may be unlikely when, for the most part, there are already a bunch of implementations of lists that people use day in day out it can actually appear in the wild. The purpose of the question was to attempt to come up with a way of determining if a list contains such a loop. I see it more as a debugging utility than anything else.

You're entitled to get pedantic :) That's what this is about! I think your posts are interesting, and in the case where an official "singly linked-list" (or is it "singularly"?) becomes an official "circular linked-list", your solution would indeed be fastest. Of course, in the case where we don't exactly know where the loop in the list occurs, this wouldn't give us the result we're looking for, and this is where Keith's solution shines.

Thanks for the posts guys :)
Pete Wright

Now this is really bugging me.

So, let's assuming we don't have a list managing structure; we simply have items in memory that point to their successor and have no choice but to traverse the list to examine whether or not it is null terminated.

The solution posted by Keef in that respect then is horribly inefficient since you can't actually traverse the list at different speeds at all; each node only knows about its successor. So, the 'faster' mover actually has to read a node and check the successor twice for each one check made by the slower mover. It's late here and I don't want to do the math but you will end up traversing the entire list at least 1.5 times I think.

So, the simplest solution is (since you know the first element of the list - you've got to start somewhere) is to simply sequentially move through the list until a successor is null (it's a singly linked list) or you get back at the start. The most you would traverse then, assuming you start at the very first node, is once, and you'd check each node just once, rather than 3 times (the slow mover checking each node, and the fast mover checking each node and the successor node in order to leap ahead).
Pete Wright

Looking at the problem you posted though, I'm tempted to get pedantic. Knuth documented linked and circular lists in volume 1 of The Art of Programming. They are different structures. Thus, if you had a situation where you were concerned that a linked list may have become circular the obvious concern would be whether or not the implementation of the list itself is correct.

A classic singly linked list (one which tracks only the first entry in the list, with each node knowing only the node that follows) is limited in usefulness in terms of adding new items; unless you want to walk sequentially through the entire list to find the last and update its 'next' pointer, you are limited to only adding items to the front of the list. The class or construct managing the list would then be responsible for updating the 'next' pointer of this new item to point to that which was previously first. In that respect, if the class implementing the linked list is properly implemented, it woudl be impossible to have the list become circular surely? (consumers of the list rely on the list to manage itself). The list is merely an organisational representation of data, and thus the consumer or producer of the data would not ever be concerned with the semantics of the list's own pointers.

Similarly, a circular singly linked list would be implemented in such a way that two pointers are updated on the addition of a new entry; the next pointer of the last item, and the next pointer of the new item. Such a construct would by nature of its design have to manage the circular link (but as Knuth points out there are problems to be aware of when managing a circular singly linked list that could be empty - pg274).

So, the upshot from a design standpoint is that if there is a risk that your singly linked list has in fact become circular, giving rise to the need to write code to determine if that's the case, then surely refactoring driven by tests to implement an effective list-structure-manager construct would be the best way forward to not only address the potential bug, but also shore up the architecture of the solution at hand.
Pete Wright

Ever seen RubyQuiz? Sure it's aimed at the Ruby folks, but there's some complex problems there that could be a challenge to solve in any language.

www.rubyquiz.com
OJ

By jove I think he's got it ;) Nice one Keef!

Yer mum!
Keef

I've been asked this one in interviews a couple of times. The cleanest solution I know of is to have two pointers traversing the list at different speeds (one just increments, the other increments twice). You check them for equality at each stage. If the two pointers ever end up the same, you've got a loop.

When I say "cleanest" above, I mean that it's the best solution I know that doesn't involve extra memory and doesn't modify the list.

Also, I'm talking from a C/C++ perspective there where pointers exist. I'd need to think a bit more about doing this in a language where you don't know where something is in memory (because having two list entries the same doesn't imply a loop).

blog comments powered by Disqus

« Server change imminent Are you any good? »

Me on the Web

Recent Thoughts

Nicely put. RT @rickasaurus: "Coders do two things: Thinking and Typing.. the more you do of one, the less you do of the other" 8 hrs ago
Current status http://twitpic.com/29o8y9 19 hrs ago
More wpf for me today.. Filling holes in the ui. What would I give to be writing pixel shaders or solving tough problems with an FP lang?! 1 day ago
Some days I really miss the creative and exciting vibe of the games industry. Other days I'm grateful for a decent paycheck! 1 day ago
Disappointing. @osfoora for iPhone now crashes on startup since the last update. Does it assume iOS 4? #fail 1 day ago
More updates...

OJ’s rants What would OJ do?