During the technical component of an interview for a software developer position I was posed the following problem:<\/p>\n\n\n\n
You are working for a company that is responsible for processing survey data for an Oil and Gas company. You are given data that summarizes whether oil was found at a certain grid reference. The assumption is that if oil is found in contiguous grid references (or grid elements), then they form a single oil reservoir. The objective is to write a program that will determine the number and locations of the reservoirs.<\/p><\/blockquote>\n\n\n\n
The Algorithm<\/h2>\n\n\n\n
The interview went pretty well, and I managed to write something within 10-15 minutes or so that I think did the job. The coding exercise was done with a shared Google Doc, so I never actually got the chance to run the code, but my interviews seemed happy with the solution. The algorithm I came up with looked something like this:<\/p>\n\n\n\n
- Create a new active
reservoir<\/code><\/li>- For each
element<\/code> ingrid<\/code>:
- If the
element<\/code> is in thechecked_locations<\/code> set, go to the nextelement<\/code><\/li>- Add the
element<\/code> tochecked_locations<\/code><\/li><\/ol>
- Add the
element<\/code> to the currently activereservoir<\/code><\/li>- Check if there are any neighbors to this
element<\/code>
- If yes: go to 2 (passing in the list of neighbors as the
grid<\/code>)<\/li><\/ol><\/li><\/ol>
- If we are not currently recursing:
- Add the
reservoir<\/code> to the result set<\/li>- Create a new active
reservoir<\/code><\/li><\/ol><\/li><\/ol><\/li><\/ol>\n\n\n\nThe Discussion<\/h2>\n\n\n\n
When I was asked to defend my code, I said I was initially hesitant about going down a recursive route, because Python is generally not a great language for writing functional-style recursive functions. However, a purely iterative approach would mean having to run an arbitrary number of times to see if there were any adjacent reservoirs that could be joined, which also isn’t ideal.<\/p>\n\n\n\n
As I said, my interviewers seemed happy with my solution, so I assume this was the solution they had in mind. However, I really wasn’t satisfied with the recursive approach, and I suggested a graph-based approach instead. The crux of the problem is taking a grid of data and understanding the connectivity, which is what graphs are intended to capture. I have a bit of experience with the iGraph and NetworkX Python libraries and knew that a graph-based solution would need probably half as many lines and probably be as performant as the recursive approach, if not more so.<\/p>\n\n\n\n
The discussion went along the lines of trading one form of complexity for another. I argued on the side of trying to shift the complexity into the standard library, even potentially at the expense of performance. Yes, a full graph library is maybe overkill for a relatively simple problem. However, I’m always in favor of writing (and maintaining!) as little code as possible.<\/p>\n\n\n\n
Outcome<\/h2>\n\n\n\n
I think the discussion was well-received, but alas I didn’t end up getting the job (probably more to do with COVID-19 than anything else). As a coding exercise, I decided to revisit the code to see firstly if my algorithm above would really work, and how much more\/less performant a graph-based approach would be. Expect articles in the near future that show the code I have written for each approach and an analysis of the pros and cons of each!<\/p>\n\n\n\n
<\/p>\n","protected":false},"excerpt":{"rendered":"
During the technical component of an interview for a software developer position I was posed the following problem: You are working for a company that is responsible for processing survey data for an Oil and Gas company. You are given data that summarizes whether oil was found at a certain grid reference. The assumption is […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[9],"tags":[7,3,6,4,5],"class_list":["post-36","post","type-post","status-publish","format-standard","hentry","category-discussion","tag-discussion","tag-graph","tag-interview","tag-network","tag-python"],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/andygrigg.com\/index.php?rest_route=\/wp\/v2\/posts\/36","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/andygrigg.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/andygrigg.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/andygrigg.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/andygrigg.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=36"}],"version-history":[{"count":10,"href":"https:\/\/andygrigg.com\/index.php?rest_route=\/wp\/v2\/posts\/36\/revisions"}],"predecessor-version":[{"id":114,"href":"https:\/\/andygrigg.com\/index.php?rest_route=\/wp\/v2\/posts\/36\/revisions\/114"}],"wp:attachment":[{"href":"https:\/\/andygrigg.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=36"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/andygrigg.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=36"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/andygrigg.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=36"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}