Friday, November 29, 2013

SXSW 2013: blending bendy materials and bendy life

A talk by Ping Fu at SXSW 2013 blended, in an odd way, self-help advice and 3D-printing technology. The only thing in common between the two may be her own personality, which, like those raw materials shaped into an infinite collection of shapes, succeeded by flexibility and adaptability.

Ping Fu at her SXSW 2013 speech 'Digital Reality: Life in Two Worlds'.

The title of her speech, "Digital Reality: Life in Two Worlds" ostensibly refers to the merge of physical and digital reality. She reviewed exciting things happening in three-dimensional scanning and printing technologies -- and her company, Geomagic, is among the players in the field. Standing on the stage in 3D-printed platform wedge shoes, she said you may be able to walk into a Nike store tomorrow, have their feet scanned, and pick up custom-made shoes tomorrow. You may also have custom-made prosthetics that would let artificial limbs look like real ones, "because currently they look like airplane landing gear". You just have to scan a soccer player's "good" leg, and print an artificial one based on that model. 3D-printing can produce filling for dental cavities, and repair tiles on NASA space shuttle -- two technologies that surprisingly (or not), are related. Preservation of historical artifacts is also a big application for 3D-scanning. Mount Rushmore took a hell of a long time to scan, but it was eventually done, and US Parks and Wildlife has a scan, said Ping Fu.

Ping Fu's 3D-printed shoes she wore at her SXSW 2013 speech 'Digital Reality: Life in Two Worlds'.
Ping Fu's 3D-printed shoes she wore at her SXSW 2013 speech 'Digital Reality: Life in Two Worlds'. More pictures from this speech and overall SXSW 2013 are in my photo gallery.

On the other hand, life in two worlds can be a metaphor for Ping Fu's own life, that has certainly spanned two vastly different worlds. As a young child she was taken from her loving family in Shanghai during the Cultural Revolution, and raised in a camp. She was put through communist brainwashing, being forced to go up on stage and scream "I am nobody!" So she has no stage fright, she jokes. If anything saved her, it was her father's advice to be like a bamboo, that bends but does not break in the wind. She even made it the title of her book, "Bend, not Break".

A soccer player's 3D-printed prostethic leg: a slide from Ping Fu SXSW 2013 speech 'Digital Reality: Life in Two Worlds'.
A soccer player's 3D-printed prostethic leg. More pictures from this speech and overall SXSW 2013 are in my photo gallery.

Looking up this book on, I saw that many reviewers accuse her of fabricating her life story. They claim her actual life was not nearly as horrible as described in the book, and that she might not have lived in a labor camp. I have no way to verify the claims of either side, though there is no doubt that the horrors of Chinese labor camps, where middle class children were sent for "re-education", actually existed. There is also no doubt that Ping Fu at some point immigrated into the US, and went from a person who knew just 3 English words, to a tech entrepreneur. And though she chose a technical field, she credits her love of language for her design skills. She may have known little of English, but she had a love of language all her life.

In China, she went to graduate school for journalism around the time when China's one-child policy started. It made not just subsequent-child births, but also pregnancies, illegal. When Ping Fu heard rumors that baby girls were being killed in the countryside, she went there as a journalist to investigate. There she witnessed "abortions" done via C-section in 8th or 9th month of pregnancy. For writing publicly about these atrocities she was put in jail, and was certain she would die there. Luckily, Cultural Revolution soon ended -- this was a few years before the Tiananmen Square -- and Ping Fu was released. (Again, I have no way of verifying how much of it is true.) Then the government gave her a choice: quietly leave the country, or be exiled to a remote corner of China. She chose to go to America, and took a crash course in English on the plane. By the time she landed in San Francisco, en route to the University of New Mexico, she already knew a few English words. Not enough to be accepted into comparative literature program, which was her first choice, but enough for computer science.

Mobile 3D-printer demonstrated during Ping Fu SXSW 2013 speech 'Digital Reality: Life in Two Worlds'.
Mobile 3D-printer. This guy and another one with a similar printer walked up and down the aisles to let the audience take a look at the printers. They, however, did not demonstrate how it works. More pictures from this speech and overall SXSW 2013 are in my photo gallery.

Myself, as someone who had a love for languages all my life, but didn't go into linguistics because I didn't think there were any jobs in it beyond school teacher, felt vindicated. There are not many people (or perhaps we're just not visible) who come into computer science not because of fascination with technology, but because we enjoy teasing out complex logical structures from the code as we do from human languages. And so when Ping Fu said that somebody back in the day suggested to her that she check out this new field, computer science, because it's a "language" that lets you make stuff, I thought that it was the same kind of thing that attracted me to the field of computing. Her life tale of a foreign student turned tech entrepreneur also has a special resonance to me because I, too, initially came to the US to go to graduate school. She, however, did not think she was a good programmer, because she lacked a science background, so she became a designer and project manager. Her secret to working with programmers is to ply them with Coke to keep their juices flowing. It must have worked, because at some point she hired Marc Andreesen, who developed Mosaic, and eventually licensed it to Microsoft to become Internet Explorer.

For a long time she didn't consider becoming entrepreneur, and when she finally started her company, Geomagic, people were still skeptical. Of the first seven employees all but her had PhDs, and 4 of them were mathematicians. People said you can't start a company with a bunch of mathematicians, as math doesn't make money. But Ping Fu replied that she liked to do impossible things, so she did it. A win for language nerds and foreign students everywhere!

Thursday, October 10, 2013

Some hackathons result in demos, some in questions

After finding out that the Devstack server we created during the walkthrough is not suitable for hosting web applications, I created a "plain" Rackspace server, installed Apache on it, and we proceeded to create a barebones web application. One of my goals was to get a clear idea how much progress a group of people could make on an application in a hackathon. The answer is, since we only got started after lunch (the first half of the day was taken up by the Devstack tutorial), and had until 4 pm to go: not much. But we got a little done.

Rackspace's Dana Bauer, Developer and Community Advocate at Rackspace
Dana Bauer, Developer and Community Advocate at Rackspace, one of the organizers of the hackathon. She and another Rackspace employee helped us greatly with the registration glitches. At the end she encouraged people to give demos, or, lacking a demo, to stand up and speak about what they did, accomplished, or learned during the hackathon. Though Dana gave people Legos for speaking, very few people (including two from our team) came up to speak. Only one person (Kesten, see below) gave a demo. More pictures from the 2013 OpenStack Hackathon are in my photo gallery.

I am no front-end developer, but nobody else in our team clamored for that role. In a strange coincidence, the other 4 women on our team came either from PyLadies (Python was their language of choice) or from scientific computing background, or the intersection of both. So I assigned the front-end developer role to myself, fully realizing that a web-page hand-coded by me would look rather... homemade. I needed some HTML and CSS templates that would make my creation look at least somewhat professional. Specifically, I needed a web form. I spent a good couple of hours looking for HTML/CSS templates for forms, and most sites were misleading: either they promised free templates, but every template you picked required you to sign up for a fee; some websites promised form templates, but instead of providing the HTML/CSS code they let you create and host a form in their domain, which wasn't what I wanted. After a long search I was able to find a form where I could tease out its HTML/CSS code. Interestingly, throughout my numerous Google searches, Bootstrap didn't show up even once. But when I mentioned my predicament to the people at the hackathon and on Facebook, two of them recommended Bootstrap. Indeed, Bootstrap has form templates. Face-to-face interaction can still be more useful than Google.

Kesten Broughton gives a demo of Picycles
The one and only product demo at the hackathon was given by Kesten Broughton, who created a 2D altitude chart as an addon for Google Maps "get directions" service using the Python beta API. His program was called Picycle, and was intended as a service for bicyclists who want to choose an optimal route, either minimizing or maximizing (if they want a good workout) the hills along the route. More pictures from the 2013 OpenStack Hackathon are in my photo gallery.

It took me 3 hours to put together a basic -- extremely basic -- front end to our application. There was no even a question of hooking it up to the backend. There was no time to write even a primitive web service that the front-end could call and display some results. One person in our group, more experienced with Python, finally got Twitter authentication to work in Python. This allowed her to query Twitter API programmatically by making requests from her Python code. Other of our members were just starting out with programming in general (in some cases switching from other professions), so I don't know what they did during that time. Perhaps they were going through Codecademy courses.

To our credit, other teams did not seem to fare better. Only one of the hackathon attendees had even a minimal product at the end to give a demo of, and he admitted he had been working on that product for 2 weeks already. His name was Kesten Broughton, and he created a 2D altitude chart as an addon for Google Maps "get directions" service using the Python beta API. His program was called picycle, and was intended as a service for bicyclists who want to choose an optimal route, either minimizing or maximizing (if they want a good workout) the hills along the route.

The lesson to be learned here is that to participate meaningfully in a hackathon requires quite a bit of preparation. If All Girl Hack Night is going to have a hackathon (I've been threatening to organize one, but always felt woefully unprepared), we would need to prepare in advance. For example, some us will have to be team leads who will have studied the API's of our choice (the APIs will also have to be decided ahead of time), and will be able to guide the teams so they could make tangible progress. That's the main lesson. Lots of advance decisions, planning what to implement, what programming languages and APIs to use, and a critical number of people who are familiar with those technologies and can guide others.

Sunday, June 30, 2013

Making sense of criteria for making sense of Javascript frameworks

How do you select the right parts from a talk about how to select the right technology? Especially if you haven't spent a whole lot of time working with any of the development tools that are being compared? Perhaps you just listen to what resonates. And so I did at the All Girl Hack Night presentation on how to select a Javascript framework that's right for you, by Justin Lowery from Cerebral Ideas. Justin compared Angular JS, his team's favorite, with two other popular Javascript frameworks, Backbone and Ember. So while an experienced web developer might be nodding their head sagely at the criteria Justin gave (which I put at the bottom of the page), I just pondered how web development today is still oddly plagued by the same problems as when I did it in 1999.

When you just can't separate presentation from business layer...

Justin Lowery (the presenter).
Justin Lowery (the presenter).

Back in 1999, when we wrote cutting edge web applications with (ahem) CGI and Perl, separating business logic from presentation seemed a distant dream, which my team at the time quickly gave up on. We wrote spagetti code where HTML was generated in a deeply nested tangle of Perl's ifs and fors. It's 2013, and it sounds like HTML still can't be made completely independent of business logic. And some people say you might as well embrace that, and pick a Javascript framework that lets you hook up Javascript to backend-generated HTML easily. According to Justin, that's one of big advantages of AngularJS.

Those Javascript-hating backend developers

This will let backend developers generate chunks HTML without ever touching Javascript. In Justin's observation, backend developers hate Javascript, but are much more friendly with HTML. Why they hate Javascript more than HTML is anyone's guess. Perhaps it's because backend developers are used to "proper" object-oriented languages, whereas Javascript kind of has objects without actually being object-oriented. It has this strange prototype inheritance, which is not like the "classical" inheritance that backend developers are used to. But I have been a backend developer for a long time, and I'm not averse to Javascript: I've been learning it eagerly in recent months, and I'm fascinated by some of its features like closures.

Freeform HTML versus generating the whole page from Javascript

Then again, there exist Javascript frameworks that not just let, but force you separate presentation from business logic; it's another question if those solutions cause bigger problems than they solve. I am talking specifically about ExtJS. ExtJS expects all the data from the backend to be returned as JSON objects via service calls. I'm not sure you could make it accept custom HTML even if you tried. At least that would be very hard, and it would violate another of framework selection commandments: "Choose a framework designed by someone who thinks like you, otherwise you'd be fighting it all the way". It would be hard to stick any custom HTML into an ExtJS application, because ExtJS does not "hook" into your existing HTML: it generates it all from scratch, from Javascript alone. Some pople don't like that. I suspect our presenter didn't either, because he considers it an advantage if a framework lets you write free-form HTML, like Angular does.

This ties into our next criterion.

Page load time: the "no blank page" criterion

Left to right: Annine, Yim, Angelina, Katie, and unidentified woman.
Left to right: All Girl Hack Night members Annine, Yim, Angelina, and Kate at the Angular JS presentation.

Allowing static HTML versus generating it all from Javascript is tied to another criterion: how fast the framework is. Mainly it means page loading time. Justin observed that a perception of loading time is not the same as the loading time itself. This criterion can also be summed up as "No blank page prior to JS parsing". If your application renders some HTML elements before it executes all the Javascript and populates fields with data, some HTML elements are already on the page even though some fields are initially blank. Even if loading the data into those fields takes 2 seconds, the user will still perceive this page as loading faster than a page that stays blank until it generates all the content, though that might take 1 second. In this case Angular obeys "no blank page" rule, whereas ExtJS -- you guessed it -- doesn't.

Opinionatedness: what does it mean?

The most mysterious criterion is probably "opinionatedness" of the framework. Perhaps you have to be an experienced front end developer to fully understand this concept, and I'm not. A Google search did not give me a crystal-clear understanding of what it means. Apparently, opinionated APIs are on the opposite end of a "scale" than REST APIs. Unlike REST, opinionated APIs don't treat URLs as resources. They are more like function calls that URLs: save(collection, key, value) versus http:///collection/{collection}/variable/{key} (this example is from an article Opinionated (RPC) APIs vs RESTful APIs). But from what I read, experts seemed to think that REST APIs are more intuitive than opinionated ones.

Clockwise from the left: Bridget, Patty, Ashley, Maryam, Simi, an IT guy from the company that hosts All Girl Hack Night; Justin Lowery (the presenter), Neelima, unidentified woman, Annine, and Yim.
Clockwise from the left: Bridget, Patty, Ashley, Maryam, Simi, an IT guy from the company that hosts All Girl Hack Night; Justin Lowery (the presenter), Neelima, unidentified woman, Annine, and Yim.

Opinionatedness of the framework figures into its learning curve. Justin said that Angular JS becomes harder to learn as the API becomes less opinionated. This seemed counterintuitive to me. Why would it be harder to program using RESTful API than one that consists of commands? Googling more about it, I found that AngularJS is called opinionated because it forces you to give your application a certain structure. If so, that can influence the learning curve in two ways.

Again, let's take ExtJS as an example. If you are writing an application that resembles the "Hello World" tutorial, it's easy to use this framework. You follow the steps, and the widgets on the page magically materialize and get populated by the data from the backend. So the learning curve does not seem too steep. But then you find out that a real-world application does not match the confines of the tutorial, and its logic often does not conform to the structure the framework imposes on you. That's when the learning curve becomes steep, as you have to find various backdoors and workarounds around the framework's assumptions. From that perspective, I'd say ExtJS is very opinionated, and this can make it hard to write real-world applications. This framework gives you prefabricated houses instead of individual bricks. But if it gave you just the bricks, a beginner wouldn't know how to stack them into an architecturally sound house.

A meta lesson is that it may be hard to know what concepts are and are not too vague for an overview talk (assuming that overview talks are introductory in nature). All Girl Hack Night has developers from all walks of life, from device driver writers to front-end, and I don't know that many non-front-end developers are familiar with the concept of opinionatedness. I will have to keep that in mind when creating my own presentations.

What kind of philosophy / methodology does the framework use to solve problems?
  • How is it architected?
  • Is the framework authoritarian or egalitarian?
  • Are all problems solved with Javascript?
  • Are problems solved with a bigger, more aggressive API?
How does the framework solve common problems of development?
  • Templating?
  • Data binding?
  • Routing?
  • Bootstrapping?
  • Data management?

How active are the creators in the community?

  • Do they have an active forum with many users?
  • Do they have stale pull requests or issues list?
  • Are they active in the community?
HTML-centric philosophy
  • HTML is intuitive for those that are non-Javascripters.
  • Strong separation of concerns.
  • Event binding is much easier.
  • Backend devs that hate JS have limited exposure to it.
  • Views are compatible with other frameworks, especially backend technologies.

Monday, May 20, 2013

Diversity hiding in plain view, or my thoughts from a SXSW 2013 panel

Conversations about diversity in technology are as interesting for who they include as who they leave out. Their goal should be to challenge the stereotype of a programmer as a young white male, unencumbered with anything that would keep him from coding 18 hours a day. The panelists who got together to discuss diversity in the Austin tech community were not in this category. But diversity is more than just being female or a person of color.

Those categories are, however, the most visible, and no wonder that the conversation revolved around them. There are companies who have been setting examples in how to bring under-represented groups into engineering. One of them is Etsy, the online craft marketplace, where one of the panelists, Garann Means, worked as a software engineer. Etsy noticed that while most of its customers were women, most of its engineers were men, and they set out to change that. Instead of poaching women developers from other companies, they started the Hacker School, and gave scholarships for women learning programming. Many of its women graduates found software engineering jobs. Moderator Mark Phillip noted that when Etsy committed to diversity, it also benefited male developers -- they became better team players.

Mark Phillip, Nicole Cofield, Garann Means, and Gerardo Treviño.
Mark Phillip (CEO/Founder Are You Watching This?!), Nicole Cofield (president/CEO of Capital City African American Chamber), Garann Means (software developer), and Gerardo Treviño (founder and CEO of Paybook). More pictures from SXSW 2013 are in my photo gallery.

Garann (who is also the founder of All Girl Hack Night, Austin women developers' group) says that diversity efforts are often criticized as "we shouldn't separate women from men, we want to keep them in the same group". But she says that this kind of separation is never an issue, at least in her own experience. Many white guys talked to her about how things that are "supposed" to offend women and people of color, actually offend them as well. It is sometimes said that a special effort to attract more people from underrepresented groups to software industry would bring a lot of underqualified people. But there are examples showing that that doesn't have to happen. Garannn says her friend Divya put together a conference in San Franscisco, with very diverse speakers, and it was technically excellent -- you didn't have to sacrifice the quality.

People categorize themselves in interesting ways that can be different from the categories we assign them to. I saw this play out in my own life as well, and I was reminded of it by what Natalie Cofield, president/CEO of Capital City African American Chamber, said. Many black engineers in tech are not Americans: they come from African countries. She has heard Nigerian programmers say "African American Chamber is not for me, because I'm not African-American. I'm Nigerian." So she saw a need for AAC to be more internationally inclusive. I can relate to this from my own experience. As an international graduate student in America, I felt I was more of a minority here than the officially recognized minorities. They were at home with this country's ways, and I was not. (I know it's a subjective feeling, and a white foreigner still benefits from the white privilege without realizing it, so I would not put my experience on the same footing as that of truly underprivileged minorities.) But when the Natalie Cofield mentioned a need to include foreign-born engineers in the tech community, it was the first time I felt that somebody was inclusive towards immigrants in this country. It was certainly the first time in my experience that somebody wanted to make them a part of the diversity discourse, as opposed to treating them as a job-stealing, wage-depressing nuisance, which is how high-tech immigrants are usually talked about in this country.

Then there is another dimension to diversity, hidden in plain view. It came to my mind when the fourth participant of the panel brought up something, and his story was considered a success story without anyone noticing the darker undertones. Gerardo Treviño was talking about Paybook, his recently launched startup. It lets people take pictures of their receipts, and Paybook will parse them for you. He and most of his developers are from Mexico. At first he wanted to base his company in Austin, but it was very difficult to get USA work visas for the whole development team. Abandoning that plan, they decided that the company's home will be Monterey, Mexico. They wanted a safe place with landscapes that help creativity. So they got the whole team of a dozen developers to live together in Playa de Carmen, an organic food paradise, in a utopian commune of sorts: for example, the whole team collectively decides what to eat for dinner that night.

Mark Phillip, Gerardo Treviño, Nicole Cofield, and Garann Means.
Mark Phillip (CEO/Founder Are You Watching This?!), Gerardo Treviño (founder and CEO of Paybook), Nicole Cofield (president/CEO of Capital City African American Chamber), and Garann Means (software developer). More pictures from SXSW 2013 are in my photo gallery.

No one in the audience indicated they viewed it as anything but a creative move, and perhaps it was; but such a move would only work for a team of people who have no other responsibilities outside of work. Clearly, someone who has children would hardly be able to leave their family and move somewhere for months at at time. This is especially true about people who have been traditionally responsible for childcare, namely, women. So I wouldn't say that it's really diversity when you pick employees who are free of family obligations. And since they tend to be in their 20s, you are clearly not aiming for age diversity either.

This goes against bringing more women into computing, because women would be the first to quit a company, or entire industry, that makes it hard to combine a job with a family. Even child-free women are less likely to stay in such a company, because they still want to have friends and personal lives. Encouraging your employees to relax on a beach or eat organic food is not a true support of work-life balance; the balance needs to be the kind that lets people fulfill their other responsibilities.

It reminds me of a story I read in our local newspaper, Austin American-Statesman, about tech startups that open offices downtown. They want to be in an attractive location, because their engineers like to to live music clubs or to the lake after work. Clearly, they are trying to attract only a certain kind of engineers, namely, those whose after-work hours are spent on leisure. They are not positioning themselves for another kind of employee who goes home to their family in the evening. It just so happens that the first kind is usually in their 20s, while the other kind is older and more likely to be female. So in the era when sex and age discrimination is illegal, this is a roundabout way to tell the non-20-something-male applicants that they are not particularly wanted here. And I think that as long as companies have implicit preferences for certain kinds of demographics -- expressed by supporting some lifestyles but not others -- I think that all the talk about bringing more diversity into tech won't yield much fruit.

Monday, March 04, 2013

Programming interviews: recommendations versus experience

Gayle McDowell gives a presentation 'Cracking the Coding Interview'.

Three years ago, when I was looking for a job after 10 years of working at one company, I really wished there were consultants to help software developers to improve their resumes and prepare for technical interviews. How enormously helpful it would be if someone who was a developer once to guide your preparation! Especially if such a person collected many years' and many companies' worth of technical interview questions.

Such a company now exists, and its founder, former Google engineer Gayle McDowell, visited Austin last year to promote her book "Cracking the Coding Interview". In her presentation, based on the book, she advised software developers what to expect at, and how to prepare for technical interviews. I found myself agreeing with Gayle half of the time, and scratching my head the other half. If my experience did not match her recommendations, the reason may have been that her advice was directed to (a) mostly beginner programmers, and (b) those who want to work at big companies. No wonder her presentation was paired with a hiring pitch by Amazon Web Services.

Let us see, then, how my experience of interviewing for software development jobs stacks up to Gayle McDowell's advice.

What happens when "they" pull your resume out of a giant pile

Gayle's version

  1. Pull resume out of giant stack;
  2. Spot-check: company names, positions, projects, schools;
  3. Skim bullets to see if you've written real code.

My experience

I haven't been on the recruiting side of things, but I was hoping that that's how it is -- that a real hiring manager (i.e. someone who knows what to look for in a developer), would look for that, as opposed to for buzzwords from an HR bingo.

Resume length

Gayle's recommendation:

Your resume should be 1 page only, unless you have more than 10 years of experience. In a 2-page resume, no one will read all the points; they might read 50% at most. The hiring manager will skim your resume and notice only some random job experience points. Some of them won't be your strongest. Wouldn't you want a hiring manager to notice only your strongest experience? If so, cull them and put them on a 1-page resume.

My experience:

I had many seasoned recruiters tell me that my resume needs to be 2 pages. But then, I have more than 10 years of work experience.

Technical questions

Gayle McDowell recomended her company's website,, for a good list of real interview questions. I checked it and the questions are really good -- they don't test your knowledge of a programming language syntax, but rather test your ability to design, as well as deep understanding of object-orienting programming.

"Don't memorize!"

Gayle's recommendation:

If an interviewer asked you a question you've already heard before in a different interview, don't just spit it out the answer -- tell them first that you've heard it. It's likely that the interviewer will still ask you to answer the question / solve the problem, but you won't come across as dishonest. Plus, they don't want just to hear you spit out the answer -- they want to know your thought process. Seeing that you've memorized some answer tells them nothing about you -- the question was wasted. It didn't give them any extra information about you.

My experience:

Perhaps this is reasonable for college students, but if I am an experienced programmer, I might have faced certain types of problems in my programming practice often enough that I know the answer off the top of my head. Such is the question mentioned later in this text, where the answer turns out to be binary search tree. What if at some of my previous jobs I searched for data in large lists? Then I could spit out the answer "BST" before I even heard the end of the question, and it's not because I heard it in another interview, or memorized the answer off of some online preparation site -- it's because I know it from practice.

Push yourself

Gayle's advice:

  • When studying a code problem, write the solution from the beginning to end. Don't just stop because you think you understand it. When faced with a whiteboard at an interview, you may discover you don't understand it nearly as well as you thought.
  • Write the code with pen on paper -- it's harder than in an IDE, where intellisense helps you. But you won't have IDE and intellisense on a whiteboard.
  • Using pseudocode is OK temporarily, as long as you tell the interviewer you will fill it out with actual code later, and actually do so.

My experience:

Agree completely. To make sure you completely understand a problem, you need to write it on a piece on paper from beginning to end. Otherwise it's easy to stumble when solving it on the whiteboard. You are used to the IDE doing so much for you, that when you are faced with a blank sheet of paper, you might start thinking, do you need a keyword "function" to declare a function in C#? Or was that PHP?

I use lots of pseudocode when writing code on a piece of paper, and I think if the pseudocode is detailed enough, most interviewers would be fine with that. No one necessarily expects you to remember all the 50+ methods of the generic List<> class when you're coding on the whiteboard.

Data structures

Gayle's recommendation:

You have to know how to implement, or when to use, the basic data structures: linked lists, stacks, queues, trees, tries, graphs, vectors, heaps, hashtables. Especially hashtables -- they come up often in interviews.

My experience:

I agree about the importance of hashtables. Many code problems I've been given in interviews required use of a hashtable for best solution. Linked lists were the second most popular data structure -- for example, I was asked to write code to reverse a linked list. There was a time when I was asked to write a program for searching a binary tree. But I was never asked about a stack, queue, trie (whatever that is?), graph, or heap. (As for vectors, they are essentially arrays, and they are used in every coding problem -- you can't write almost any code without it.)

Algorithm Questions

Gayle's advice:

Study the basics: complex algorithms usually unnecessary.

My experience:

I agree: I have never been given a problem that required more than a simple algorithm. Well, at one point I was shown the code for merge-sort, and asked what was the complexity of that code (it's O(n log n)), and the interviewer asked me which lines of the code contained the log n part. That was the most complex algorithm I had to deal with at an interview, and even then I didn't have to write code for it, only analyze it.

Decomposing algorithm problems

Gayle's advice:

To make the problem easier to solve, decompose it in 4 steps:
  • Pattern Matching
  • Simplicity and Generalization
  • Base Case and Build
  • Data Structure Brainstorm

My experience:

Overall I agree, however, I think we think about decomposition differently.

Example of decomposition

Design an algorithm to print subsets of a set: {a, b, c} -> {}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}

Gayle's decomposition:

You start with empty set:

S({}) -> {}

Find a solution for a one-element set

S({a}) -> {}, {a}

For a two-element set, the solution is still obvious:

S({a, b}) -> {}, {a}, {b}, {a, b}

S({a, b, c}) -> ?

You'll notice that there is a pattern: build S(n) -- a subset for an n-element set -- by cloning S(n-1) and adding n to the cloned sets.

My comment:

This is an example of a problem that can be solved inductively, but there are many problems where induction wouldn't help. Such is, for example, a problem that I was asked at a past interview -- determine if two words are anagrams of one another. It's easy, yes, it's just not inductive. Probably because we are not required to find all anagrams of each word (in which case it would be closely related to the subset problem), only to determine whether one word can be an anagram of the other, i.e. if both words have the exact same set of letters. You don't gain knowledge on how to do it for a 3-letter word if you know how to do it for a 2-letter word, because it's an exact same problem.

Pattern matching as a step decomposing algorithm questions

Reverse the order of words in a sentence

Write code to reverse the order of words in a sentence, e.g. "dogs are cute" to "cute are dogs".

Gayle's way:

This problem is similar to reversing the characters in a string: "dogs are cute" -> "etuc era sgod".

The answer: reverse full string, then reverse each word.

My comment:

This solution sounds straight from a joke about mathematicians. How does a mathematician make tea? He/She pours water into a kettle, puts the kettle on the stove, turns on the stove, waits until the water boils, then ours the boiling water over the tea leaves. Now suppose the kettle is already boiling. How do you make the tea then? Mathematicians's answer: turn off the stove, dump the water, and now you've reduced this problem to the one you already know how to solve.

I think a simpler way to reverse the word order in the string would be to split the string at spaces, put the resulting words in an array of strings, and reverse that array (many programming languages have built-in functions to reverse arrays. The ones that don't, like C, don't have functions to reverse strings either).

A ransom note from a magazine

Design algorithm to figure out if you can build a ransom note (array of strings) from a magazine (array of strings)

Gayle's way:

What if we used characters instead of strings, and built an array of character frequencies? And generalized to word frequencies?

My comment:

The suggested approach doesn't seem to simplify much. I don't think it's essentially simpler to do that than to build an array of word frequencies. The key to it in any case is hashtable. Familiarity with the hashtable data structure is pretty much the only thing you need to know to keep track of how many times each word occurs, and therefore if there are enough words to put together the note you want.

Unconventional, but intuitive advice

Gayle McDowell gives a presentation 'Cracking the Coding Interview'.

Some of Gayle's general interviewing advice was not what career advisors typically give, but consistent with my experience. Such as: there is no need to write thank-you cards, because no candidate for an engineering position was ever rejected for not writing a thank-you card. People make a decision whether to hire you pretty soon after the interview - perhaps within a day or so -- and that's much sooner than your thank-you card could reach them. From over a hundred of candidates that she had interviewed at Google, she got only 1 thank-you card, and it did not sway her decision towards that person in any way.

Finally, do not despair if you think you did poorly. Gayle says that you really, truly can't know how well or poorly you did. Seriously, you think you do, but you don't. Candidates are evaluated on the scale of comparison with other candidates, so sometimes you might think you did really poorly, but in the interviewer's eyes you were the best candidate interviewed for this position.