Python Coding Exercise: Nested Dictionaries

23:54 Fri 08 Jan 2010. Updated: 15:26 18 Jan 2011
[, ]

I’ve been looking at a bunch of coding exercises recently, including the demo for Codility, and recalled an exercise that I came up with as an interview question. It’s not incredibly difficult, but strikes me as a good “real-world” exercise—it’s based on a task I had to perform while working on the discuss functionality for freebase.com.

You have a list of objects (the objects can be dictionaries). In addition to other, irrelevant, properties, they all have id and parent keys (or properties). The parent key contains the id of the object’s parent. There are no recursive parent relationships (two objects cannot be each other’s parents), and there’s only one parent per object.

The goal is to go from this flat list of objects to a list of nested objects, where each object has a child key (or property), and that contains not a list of ids but the child objects themselves, each of which also has a child property containing its child objects, and so on. Each dict should still show up only once in the entire structure (each only shows up once in the original list).

I think it gets slightly more difficult if you start with the objects having their parent relationships laid out at the start instead of the child relationships, but it’s still a similar problem.

I might post an answer to this over the next couple of weeks, and might also dig up my old solution to the problem to compare against how I’d do it now (if there’s much difference).

Leave a Reply