Duplicate Values in Binary Trees

Every once in a while I get an email from a reader pointing out a possible error in the book. There are definitely some errors in there. But sometimes they aren’t errors, but I treat them as such because there’s obviously something that needs to be clarified.

Here’s a recent email from a reader (hi Mark!) that warrants extra discussion:

Another possible error I spotted is that binary search trees usually do not contain duplicate nodes, so the sentences at the top of page 64 should say that the nodes to the left are all less than the nodes own value and the nodes to the right are all greater than the nodes own value. But, if duplicate nodes were allowed, then either the left or the right would have the “or equal to” but not both (the current wording has both sides having “or equal to.”.

It’s definitely true that most binary search trees (BSTs) you see in examples don’t contain nodes with duplicate keys. However, that doesn’t mean it isn’t possible. If you can only store one value in a node and you have multiple values that map to the same key then you’ll need multiple nodes with duplicate keys to represent all those values. (In real life, a BST will have a value associated with it, say a pointer to a structure. BST examples in books and interviews won’t add the extra complexity of value management, but it’s there in practice.)

What Mark is objecting to is the “less than or equal to” and “greater than or equal to” wording when describing how the nodes of a BST relate to their parents. He’s asserting that either:

  1. The left child must be less than or equal to the parent and the right child must be greater than the parent; or
  2. The left child must be less than the parent and the right child is greater than or equal to the parent.

Enforcing either statement will still give you a BST. But it will make it impossible to create a balanced tree. (Recall that in a balanced tree the difference in heights of the left and right subtrees of a node is either 0 or 1.)

Let’s say you have a small tree of 7 nodes, each with value “5”. Create a tree from them using either of Mark’s rules and what do you end up with? A tree with nothing but left or right children — effectively a linked list. The tree has a height of 7.

If you relax the rules to allow for “less than or equal to” and “great than or equal to” then you can create a balanced tree of height 3. Balanced trees are great because you can search them in O(log n) time.

Of course, all of this hinges on allowing duplicate keys in a BST. If you don’t allow duplicate keys then the point is moot since “less than or equal to” and “greater than or equal to” devolve to “less than” and “greater than”. This is the likeliest case, in fact, since most tree implementations I’ve seen treat the keys as a set, not just a collection.

Anyhow, obviously something that could use some clarification in the book. Thanks Mark!

Feel free to send questions and comments about anything you’ve read in the book to eric@piexposed.com. Sometimes I’m slow with my mail, so if you don’t get a response after a couple of days, resend it to remind me to reply…

The 40-Year-Old Loser

Are you sure you want to work for Google? Or Facebook or Twitter or some other biggish company? If you’re in your early twenties, you might want to stop and think about it. Or you could end up a 40-year-old loser like me!

Let me explain.

I get to interact with a lot of young programmers, both as part of my recruiting efforts at Google and as a side effect of Programming Interviews Exposed. The other day I was reflecting on the differences in the tech industry when I graduated (1990 — pre-Java, early C++, i.e. ancient history) compared to today. Today there are so many opportunities for good software engineers to do things that I’m actually quite envious. These opportunities were not around when I graduated. Instead, my classmates and I were busy interviewing with big companies. I turned down an offer from Microsoft, for example (which in some ways I regret because I’d probably be rich by now because of stock options!). Friends were interviewing with Sun, SCO, Bell-Northern Research, Northern Telecom, big banks, etc. — all big companies for the most part. I don’t remember anyone starting their own company.

Today, though, I see many graduating students thinking about starting or joining a startup where the pay is lowish and the work is all-consuming. And that’s great, because the possible upside — i.e., going public or being acquired — is almost limitless compared to working a 9-to-5 job for an established firm. If you love autonomy, if you want to work on something that could be the Next Big Thing, if you want to change the world, a startup is the place to be. And if you were wise enough to stay unattached through your college/university years and are willing to travel to where startups thrive (and you’re OK with continuing to live like a pauper) then I recommend you go the startup route. It’s much, much easier to create or join a startup when you’re young and have no responsibilities.

The truth is that most startups fail. So at some point you’ll probably end up working for an established company. You’ll have lots of hands-on coding experience and you’ll be a prime catch — please do apply to Google, it’s a great place to work. You won’t get rich or change the world working for an established firm, but you will enjoy the work if you choose the right company and get paid pretty well.

Looking back, I guess I regret taking the easy route with my career. I played it very safe. I didn’t even take the Microsoft offer, which would have required a move to the United States. I didn’t join RIM in its salad days — it’s ending badly now, but I’d at least have some serious money to console me. Switching to Google was the riskiest thing I’ve done career-wise, which really wasn’t much of a risk!

Don’t get me wrong, I enjoy my work and Google’s a great company to work for. But part of me thinks I’m a 40-year-old loser for not taking career risks when I had the chance. If you’re young, now is the time to take those risks. Go interview for that hot startup — what do you have to lose? You can work for a big company anytime — trust me, we’ll be happy to have you! Don’t discount the tiny companies with lofty goals and aspirations. Give a startup a chance. Or better yet, find a buddy and start your own!

The T-Shirt Signal

Occasionally I’m asked what’s the biggest difference between working at Google and working for my previous employer. There are some obvious answers like better compensation, better perks, more opportunity, smarter colleagues, impact-based promotion system, etc. But really it all boils down to the additions to my wardrobe. I’m talking t-shirts, folks!

It seems silly, but the number and variety of t-shirts you get as a software engineer is a strong signal as to what kind of company you’re working for. New t-shirts can mean:

  • The company has money to spare. (When it doesn’t, “frivolous” expenditures on things like t-shirts are the first to get chopped.)
  • The company values your team. (You get t-shirts designed specifically for your project and/or the members of your team.)
  • The company values its products. (You get t-shirts when a major new product or product update launches.)
  • The company supports its employees. (You get t-shirts for initiatives around women in computing, LGBT issues, diversity, etc.)
  • The company is a fun place to work. (You get silly t-shirts for silly reasons.)

It’s quite amazing how excited software engineers get about t-shirts. T-shirt distribution at our office is often a frenzied affair. It’s a simple and inexpensive perk that makes those software engineers feel just a little bit better about the work they do and the company they work for.

Dud Coder Elimination: Why Technical Interviews Matter

This post was originally published on Amazon’s tech.book(store) as a promotional post for Programming Interviews Exposed. I retained the rights to it and am reposting it here.

By Eric Giguere

To non-programmers, the technical interview process seems cruel and heartless. After screening by a recruiter, the candidate is subjected to a series of personal interviews that test both their programming skills and their problem-solving abilities. Armed with nothing but a marker and a whiteboard, the candidate must convince each interviewer that he or she has the chops to make a meaningful contribution as a software engineer at their company. No chops, no job—it’s that simple.

Programming interviews are a way to optimize the hiring process, much the way a compiler optimizes code. One of the simplest compiler optimizations is dead code elimination, which removes code that will never execute. Dead code elimination yields smaller executables and speeds the remaining optimization steps. Not to be harsh, but technical interviews are a form of dud coder elimination—a way to weed out the people who can code from those who can’t.

The sad truth is that many job applicants with computer science or software engineering degrees don’t actually know how to code. They may understand the technical and theoretical aspects of programming. They may know how to manage projects and teams. They may be able to give great presentations. But they can’t write good code.

Writing good code is a skill you develop mostly by writing a lot of bad code. Like any craft, it takes time and effort to develop good coding skills. The more you write, the more you learn.

The dud coders haven’t written enough code to develop those skills. A typical computer science or software engineering program doesn’t involve a whole lot of in-depth, hands-on individual programming in real-world scenarios. Dud coders can thrive in these programs by doing well on the academic side and choosing the right teammates for class projects.

Hiring a dud coder can be problematic. At best, they’ll distract the other coders by requiring extensive mentoring and in-depth code reviews and rewrites. At worst, they’ll affect the group’s morale and make negative contributions to the codebase. Dud coders eventually get fired or transferred, but they can really set a project back.

Every coder, dud or not, also has a learning curve. It takes weeks to learn a new codebase and the related development tools. Companies may not realize they’ve hired a dud until months have passed.

Unfortunately, recruiters can’t always tell the duds from the non-duds, especially when they have the right accreditations and experience. The only way to ferret out the good coders from the bad or inexperienced ones is to get them to program something.

Companies could hire software engineers on a probationary basis in order to properly assess their programming skills. In fact, internships and co-op work terms are a great way for firms to find raw talent without any long-term commitment. But short-term probationary contracts don’t appeal to most programmers, especially the skilled ones.

Enter the programming interview. While it’s not a perfect process by any means, it’s a great way to get some good signals on how well a candidate can program. Several detailed interviews by experienced interviewers—software engineers who went through the same hiring process and have been trained to ask good questions—is usually enough to discern the dud coders from the good coders. And if there’s any doubt, the hiring committee will err on the side of not hiring the candidate—that’s the price most companies are willing to pay to not hire dud coders.

That’s why technical interviews matter. And why you don’t want to interview like a dud coder. Preparation and practice are the keys to landing that great programming job. Don’t be a victim of dud coder elimination!

Eric Giguere is the co-author of Programming Interviews Exposed and several other programming books. He has bachelor’s and master’s degrees in computer science and is not a dud coder. Join the mailing list for more technical interview advice.

Rejected by Google: Now What?

You’ve interviewed at Google (or Facebook, or Amazon, or the hottest new startup) and been rejected. I know what it’s like. My first interviews at Google went well, but I turned down their offer because I didn’t want to move to Mountain View. Later, when the Waterloo Region office was well-established, I re-applied and had to be re-interviewed. The interviews didn’t go as well — I didn’t take them seriously enough — and this time I didn’t get an offer. Oops!

So what do you do after you’ve been rejected? Here are my tips:

  • Don’t take it personally. I know, it’s hard, because in many ways job interviews are personal. Read Steve Yegge’s description of the ‘anti-interview’ to see why the rejection may not have anything to do with you at all. Generally speaking, I think it’s important not to place too much emphasis on where you work or what kind of title you have. If you’re a good programmer, have confidence in your own abilities. (Bonus tip: being confident will also help you do well in those interviews…)
  • Be honest with yourself. You usually know when you’re blowing an interview. It’s not a good feeling. But the lack of an offer probably won’t be that much of a surprise.
  • Don’t rant about the company. It’s never a good idea to diss potential employers. It’ll hurt your chances if you re-apply, and it makes you look bad to other employers.
  • Learn from the experience. Hopefully you read a good programming interviews book before the interviews, but reading and doing are different things. Write down the questions that you were asked and how you thought the interview went. Were you asked about algorithm complexity and you didn’t get the right answer? Go re-read the relevant book chapter and then work on some complexity problems. Don’t be afraid to explore other books, too.
  • Prepare for more interviews. Don’t stop preparing! You have to keep reading, keep working on problems, and keep programming. You should also be updating your LinkedIn profile and building an online reputation.
  • Re-apply when you’re ready. If six months have passed and you’re still interested in working for the company, re-apply for the job. Most companies will give you a second chance. You’ll be in a much better position this time because you know what to expect from the interviews and you’ll be much better prepared.

Don’t forget that hundreds or even thousands of people apply for jobs at high-profile companies like Google and Facebook. Most people don’t even make it past the screening stage. These companies spend a lot of time, effort and money to find talented employees. Making it to the interview stage is a big deal. You just have to make it a little further!

And as for my story…. I applied to Google again after about a year, took the interview process much more seriously, did proper preparation…. and this time I got in. I’m very happy working in the Google Waterloo Region office and glad it worked out in the end. I hope it works out for you, too!

Don’t Diss Your Previous Employers

I’m always surprised to see people dissing their previous employers in public, and it’s not something I recommend you do. I think it paints you in a more negative light than your previous employer.

People leave jobs for all kinds of reasons. Some people leave for better opportunities — that’s what I did last year. Some people leave because of personal issues not related to work. Some people leave because the job just doesn’t fit them anymore or because there’s nowhere else for them to advance career-wise within the company. Some people leave because of poor performance. And a very few people leave because of harassment and abuse.

But recruiters looking to determine if you’re a fit for their company don’t want to see you badmouthing your previous or (even worse) current employers. It’s not professional and it makes them wonder if you’ll be doing the same thing with their company.

Of course, you’ll never be completely happy with everything your employer does. There will be policies and decisions you disagree with. But don’t rant about them in public. Try to work internally to fix them, if you can — and I know this can be very hard in many companies. If you can’t fix them and you can’t live with those policies/decisions, maybe it’s time to look for another job.

There’s very little to be gained by complaining about an employer in public. Remember what Thumper said: If you can’t say something nice, don’t say nothin’ at all.

What’s New In Programming Interviews Exposed, 2nd Edition

Even classics like Programming Interviews Exposed need revision. Here’s a brief list of what’s new in the second edition of PIE:

  • Updated code samples. Code samples in the first edition were mostly in C. The second edition places more emphasis on Java and C#.
  • Corrections. There were a few errors in the first edition that have been corrected in the second edition.
  • Additional interview material. The second edition includes more coverage of important areas like concurrency as well as entirely new topics of discussion.
  • Clarifications to existing problems. Answers to many of the programming problems have been clarified.
  • Inclusive language. While men still dominate, more and more women are finding their way into the field, and the second edition reflects that reality.

Just as important, though, is what hasn’t changed: the comprehensive, let’s-talk-it-through approach to answering the problems that made the first edition so readable and useful is still the same. Grab your copy today!

Programming Interviews Exposed is available from Amazon and other bookstores.

The New Edition of Programming Interviews Exposed

Cover of Programming Interviews Exposed, second edition, now available for saleWe are pleased to announce that the second edition of Programming Interviews Exposed (PIE) is now available for sale from fine bookstores everywhere, including of course Amazon.com. We’ve also created a mailing list offering free interviewing tips and more information about the book, so be sure to join today!

Stay tuned for more! You can leave us comments here on this blog or use the contact form to drop us a note.