A nice way to generate all subsets within python.

Disclaimer: this post has some lousy code and a serious factual error. Throughout, I am speaking about a method of generating all permutations of a set, while saying that I’m speaking about generating all subsets of a set! I have written a newer post which integrates content from a comment by Owen Jacobson, along with a short response explaining just what the heck I was thinking. This post has been left intact aside from this disclaimer for the sake of posterity!

Recently on hackernews, I saw this amazing bunch of vimfu (learned some nifty tricks from it too!), and so I went to check out Jim Dennis’ other answers. Nothing quite so popular, but some worthy reads about “what qualifies a person as a kernel developer” and “can I run a .so compiled in red hat under ubuntu?” – the one that inspired this post though, is the classic “how to generate all subsets of a set?”

Jim suggests using python’s itertools module (in addition to bitmasking on the subset-representation), and I’ve never had cause to look at itertools before. Boy, how I wish I had! I quickly whipped up the following (after reading about argument packing/unpacking:

There’s probably reasons why it’s ugly, and certainly ways to do it better. What I like about this though is that it handles pretty much anything you throw at it, aside from a single non-iterable object I suppose! So calling “all_subsets(1,2,3,4)”, or “all_subsets(‘funny’)”, or “all_subsets([1,2,3,4])” or “all_subsets({‘a’:1,’b’:2})”, or even all_subsets(1) all work and spit out a list of tuples of the permutations.

A possible extension would be to convert back into the form originally provided – but I think that a standard form of return may be more useful. Regardless, this is a neat tool that I will keep in my box.

Edit: I made a modification to the above, so that it can work with any iterable or non-iterable object:

Wyatt is an Intern: Part 2

I am one month into my internship, and I’ve realized that I’m enjoying it.

Alright, I’ve known all along that I’m enjoying this. But it feels like a qualified decision now. This isn’t the awe of new things like, “wow I enjoy working”, or “ooh pretty city”, it’s a genuine appreciation of having a good thing going on.

I work on Webkit. That’s pretty cool. If you already know all about how webkit works, you can go find out what stuff I’ve patched by looking around in the bugzilla. If you don’t know how that stuff works, then I don’t expect you to care – it’s not very important anyway. I’ve only done test conversions so far, and a few other small things. I’m taking some bigger steps now, as I try to make a few actual code changes in the editing section – a cool 33 thousand lines of code among 60 files. Ramping up to speed on that is what this post is about.

My approach to this is holistic, which might be stupid of me. My fundamental assumption is that the better a programmer understands the system they are working within, the better a job they are able to do. I suppose that for an ideally modular system in a perfect world that might not hold, but I think it does here. I invite debate on the topic, but ask that you bring a) evidence which suggests I am wrong or b) viable alternatives to what I’ve said. If we simply disagree, we won’t be productive 😛

So, the “holistic approach”. I’ll define that as something akin to top-down, or biggest items first. Within the editing code, there’s a class ‘Editor’. It’s a pretty sizeable class – between its headers and implementation, it’s 3-4 thousand lines long. There’s a lot of other smaller classes, too. What my approach means is that I’ll read Editor’s high level definitions, then all of its methods, and as I find things which I don’t understand, branch into them and do similar. This search is a sort of optimised depth-first — only when something seems vital, common, and confusing will I break my task and go investigate it.

In this way, you can get a large chunk of understanding in a go. I spent 10 hours or so at the end of last week reading Editor.h/Editor.cpp and branching into some other important seeming code like Page, Frame, Node, EditorClient, and others. It seems to have gone pretty well. What seemed at first like a very confusing and scary bunch of code is now beginning to fit to a mental model: the Editor has a Page and a Frame and manipulates Nodes, and has all of the “policy information” about editing actions. The editing itself is done by the EditorClient, which is implemented separately by each of the different platforms that have ported Webkit. This large-scale picture makes the task feel much less daunting. I’ll draw an analogy.

Imagine you have a large puzzle with small pieces. The biggest clue for solving it is lookng at the picture on the box. With that frame of reference, you can identify the large objects you have to work with. That’s the first step in the recursion: you broke 1 big problem down into a group of smaller problems. Now the work is to treat each of these smaller problems in the same way: find a key feature or element, and identify subelements in relation to one another. Eventually, you’ll be working at the granularity of single puzzle pieces. Stepping back to code — you’ll eventually reach the granularity of single lines.

I’d like to hear people’s strategies for understanding large, complex, and at times roughly defined systems. I’m very interested in education, and at a certain level of abstraction, I think that all attempts to learn things are attempts to construct mental models which help us navigate complex systems. So I implore you – share your insights 🙂

Re: The story of George — ayttm’s most prolific non-developing contributor

A week or so ago, I watched a short series of youtube videos featuring Ira Glass speaking about being creative, telling stories, and so on.  A few key takeaways from those (for me) were:

1) Your good taste is not only what drives you to create, but what shows you that you suck. A lot of what you make will suck for a very, very long time. The people who don’t suck are the ones who manage to outlast this, which is hard.

2) A story can be thought of as an anecdote and a message. A bad story could have a lame anecdote and a lousy message, or an awful anecdote leading up to something surprisingly profound, or even a fantastic anecdote with nothing interesting to say at the end. A really good story is not just compelling to listen to, it also teaches you something neat when you’re done.

Reading this post on the other side of the moon, there’s a fantastic anecdote, and (I encourage you to go read it before you move on – it isn’t long!) a very worthy message. As someone coming onboard to an open source project, it seems to me to be chock-full of useful advice.

The ultimate message is copied here below, because I hadn’t seen it stated succinctly before. As the TED slogan puts it:

TED: Ideas Worth Spreading

 

 

 

I believe that this is an idea worth spreading:

When it comes to hacking on opensource software, none of age, gender, race, country of origin, or how you look matters. All that matters is a pleasant attitude to your fellow developers, a willingness to keep at it and learn as you go, the drive to not give up when things don’t go your way, and the ability to tell the difference between an idea and the one who has it.

Thank you for your insight, bluesmoon.

Wyatt is an Intern Part 1: Getting an Internship

This is the first post of several about being an intern. At some later point, I may not be able to talk about everything I’d like to (we’ll see), but I will do my best to maintain an open record of the experience. This post discusses the bits of the process I saw at each company I applied to, sorted by the time I found out my result.

Between late 2010 and early 2011, I submitted this resume to Hulu, Facebook, Google, Microsoft, MRX, and Pixar. Responses came (or did not) across a variety of timescales, and the results were mixed. Hulu did not ever respond. Facebook put me through four levels of phone interviews before rejection. I had one phone interview with Pixar before rejection. Microsoft flew me to Seattle (I’m a past intern, which allowed me to skip the first phone screening), then rejected me. I travelled to MRX in Hamilton for one interview, and received an offer, and I had five phone interviews with Google, and received an offer.

Rather than speak about mistakes I (or interviewers) made, or the exact problems encountered, this post will focus on processes. I apologise for the factual, step-by-step presentation!

Facebook

I submitted my resume via the submission form in the careers section of facebook.com in October of 2010. Within a week, a recruiter contacted me by email and arranged the first level of phone interview. This was essentially a pulse test, asking things such as “what is the ‘new’ keyword used for in C++?” and “Explain what inheritance means.” After this phone call, a second phone interview was arranged, where I was given some high level design problems and some low level code problems. The same was true for the third and fourth phone interviews – each occurring about a week or two apart. Each interview was about one hour long, and given by a developer. Generally, they had worked at Facebook about a year, and the people I spoke to were friendly and helpful. For sharing code, we used a cool (but slightly flaky) tool known as collabedit. I heard back fairly promptly about the decision each time, and have a fair understanding of why I did not progress beyond the fourth phone interview. High point: hearing about cool projects people work on at facebook. Low point: interviewers completely forgetting they were supposed to phone, which was a fair waste of time.

Pixar

I noticed Pixar’s internship posting through InternMatch, and submitted my resume in early February. They got back to me within about 10 days to set up a phone interview, which had to be rescheduled once. The interview was half an hour long, and was between myself and two development leads at Pixar. I spoke to them in the midst of the third day of the Guelph Seven, and everything went great. They told me a bit about development at Pixar, then asked some interesting questions (pretty high level) that I’d never thought about before, and seemed very pleased with my responses. We got along well, but I heard back about a week later that they decided to move forward with a different candidate. I’m not certain what I could have done to improve, but I still feel positive about the process.

Microsoft

I submitted my resume online to Microsoft in October of 2010, and didn’t hear anything back from them. In February of 2011, a snow storm cancelled a seasonal job fair, and I was motivated to find and contact the Microsoft recruiter for my region. About two weeks later, she got back to me and had me respond to some questions by email, mostly about my interests and past experiences. From here, I was brought forward to the flight to Redmond, which was scheduled for sometime during March (it was 48 hours after the end of the Guelph Seven).

I had three in-person interviews, each consisting of a brief introduction and coding on a whiteboard, and one of them involved lunch, which is really awkward, because you’re supposed to eat and talk at the same time. The interviewers were mostly senior engineers, and they were all friendly and helpful. Two interviews focused on code, and one on design (with some code thrown in). I have heard that 4 interviews is an indicator of success, while 3 or fewer indicates failure. Among my 3 separate times interviewing as an intern in Redmond, I was successful with 4 interviews, rejected with 4, and rejected with 3 – add that to your data as you wish. I received my rejection within a week each time, and my first time there, received my acceptance the day of my interviews.

One day, I would like to write about my past experience as an intern at Microsoft. I had a surprisingly complex task assigned without significant guidance, and fell through a lot of the internship process’ cracks. Particularly, I did not receive my final internship review until 9:00 PM on my final day of employment, despite the intention that it be completed at least a week prior to an employee’s last day, and a meeting between recruiter, employee, and supervisor is supposed to be held to discuss it and future steps, which never occurred. I learned many lessons while I was there – few of them were related to code, and most were about things not to do in my future. I also met some amazing people, but could have been more social.

MRX

I submitted my resume to MRX in mid-March and worked out a time to travel to the office. I met with the development lead and two senior members of the development team for about an hour, and had a mix of non-technical questions and questions about my experience. I felt like I would get along with these people and fit with the team really well, and I received an offer from them approximately two weeks later.

Google

Short version: I did 5 interviews with Google and received, then accepted an offer.

Long version (much better story): I submitted my resume to Google in October of 2010 (at the same time I submitted to Facebook, Microsoft, and Hulu), and aside from an acknowledgement email (and a form), I did not hear back from them until the middle of February. They requested two full months of availability for interviews, and we had a bit of a rough start.

My first two interviews were back to back 45 minute technical interviews, using Google Docs to share code. It used to suck a lot for this, and while still not perfect, it manages. The first interview went well, and the second interviewer forgot to call. My questions were algorithmic coding problems, and I was allowed to answer in whatever language was comfortable (I chose Ruby). The wait for the second interviewer gave me an awesome opportunity to properly finish and polish up the code I’d written, which was really fun. I did this in my own vim window, and copied back to the Google Doc every time I’d fixed a major issue or added an interesting feature, and the code ended up looking nice. I’m not quite sure why, but the interviewer was present in the doc for several hours afterward, so I think they saw my polished result later. The second interview was rescheduled, had similar content, and also went well. The interviewers were helpful and pleasant. Again, I enjoyed thinking about the problem enough that I polished up my code until it worked really well after the interview, and I believe the interviewer saw it (but have no confirmation of that).

My third interview was scheduled for the day after I returned from Microsoft, and on that day, I asked for it to be rescheduled (I’d been awake for 40 hours or so on airplanes and coding in McDonald’s). I rescheduled it for the following week, and then ended up being very, very sick the day of my interview, in a way that robbed me of sleep, tore my focus in half, and made moving my arms feel like fire was consuming them. I emailed a request to reschedule. My recruiter phoned me not long after to inform me that rescheduling at this point would severely limit my chances of finding a placement, but after I described my situation, she understood, and we decided to try another day. I hung up, relieved and delirious, and the phone rang again. It was my interviewer.

The problems were technical and began with code, then progressed into some more mathy stuff. I was sluggish and could barely type, and didn’t feel like I had much clue what was going on. The interviewer was forgiving of my condition, but assured me that he could (and would) not take into account my claimed state of mind while assessing my results. I did not find the answer to the final question, and even after I hung up, despite a lot of pacing to keep pain at bay, and discussing the problem with my likeminded friends, no solution arrived. Our shared stumpedness made me feel better, and I managed to go to sleep.

The next morning, my second thought was “I feel excellent!”, and my first thought was the fully formed mathematical answer to the problem from the day before. I quickly googled my interviewer’s name and found his email in a google groups discussion, and sent him a message outlining the correct solution, with some possible optimizations. I briefly considered coding it and putting the code onto github, but decided that would be too elabourate and time consuming. He responded favourably, and I heard back positive news within a few days. I’d made it ‘in’ – such redemption! Now I had only to find and interview with a host.

Next, I sat in the candidate pool for a few weeks.

I eventually emailed my recruiter, asking whether I could assist in finding a suitable project, and she responded very soon after, to let me know I’d been set up for a non-technical interview to determine my fit with a potential host, and they might make an offer over the phone if things went well. I was thrilled!

My non-technical interview ended up being a regular technical interview, only with less time than usual (just 30 minutes). My interviewer seemed like a nice guy, but I didn’t feel like our thoughts were quite lining up. After my interview, I contacted my recruiter inquiring about possible next steps.

One week later, I received both an offer from MRX and also word from Google that my previous host had moved forward with a different candidate. I’d fought so hard for the Google position at this point that I wanted to see the process out, but I did not want to keep the people at MRX waiting, because I knew I’d love to work with them.

Through an amazing effort of the recruiter assigned to me, an interview was arranged for the morning of the 18th (monday) with the Chrome team. I checked out the Chromium source tree, built it and ran some tests, and hung out in the #chrome IRC channel, and then waited for several hours by the phone. My host had fallen ill and couldn’t call that day – so we pushed the interview to the next day. My host was still sick, and not able to interview.

Again, through the amazing effort of my recruiters, things came together, and a different interviewer contacted me for the team. He explained some information about the position, what sort of tasks might be involved, what the team was like, and I asked him a few questions. Then we thanked each other and that was that. Not a surprise technical call, just a discussion of what work gets done by the team and what things they’re going to do. It also turned out I’d read a blog post by my interviewer the day before! I spoke to my recruiter again, and late that evening (post midnight for me, post 9pm in the pacific), a verbal offer was made. I can’t thank the people involved enough for being so prompt and diligent; they’re amazing through and through.

Conclusion

A common theme throughout this year’s internship hunt was that I had to be the first to act. Generally, things seem to sit still until you poke them. I have been fortunate to not poke someone and get an angry response, but I guess it’s often up to you to stoke your own fire.

Another takeaway is that the interview process, while fun, sucks in so many ways. Everyone I did phone interviews with had at least one scheduling change or issue, and everyone I did >1 phone interview with had someone completely miss a call for no obvious reason. If this kind of thing happens to you, the best you can do is maintain professionalism, accept that mistakes happen, and push forward in a constructive way. Contact your recruiter to let them know what happened, and try to work as a team to bring the process back under control.

The robots *want* to be like us.

X11R5 is a markov chain bot, and Dumont is (to my knowledge) a stock infobot.

04:31 < X11R5> Someday maybe i’ll come back speaking more intelligently.
04:31 < fuzzie> Unlikely.
04:31 * Dumont flips through the manual, looking puzzled.
05:01 < X11R5> Well it seems like the kind of pie? I was under the previous opengl 3 but later disappeared from his note, but it looks like i said, zombie apocalypse.
05:31 < X11R5> Ahh, software development.