Skip to main content

Interview Questions: What is the Big O notation of X?

What the interviewer is really asking:
Can you figure out the computational complexity of a situation, algorithm, or process?

How to answer:
It might seem like a great idea to just memorize the Big O notation of every algorithm or process you've ever heard of, but this is going to be a lot of memorization and isn't going to be as impressive as reasoning your way through a problem.

Big O notation is simply a way to quickly describe how efficient some computing code is.  O(n) means that the process runs in time proportional to the amount of information processed; O(n2) means that the process runs in time proportional to the amount of information processed, squared.  So, for instance, if a O(n) process is processing 10,000 pieces of data, this process might take 10,000 milliseconds (or 10 seconds) assuming that each datum requires 1 millisecond of processing; a comparable O(n2) process would take over a day to process the same set of information.

An algorithm that runs a single for loop on a set of data would be O(n), because it only processes one iteration for each item (hence, n1); an algorithm that runs a for loop on a set of data, then has another for loop processing the entire set within each iteration of the first for loop, processes the entire set once for EACH item in the set (hence, n2).

A great explanation of Big O notation is available here: http://www.cforcoding.com/2009/07/plain-english-explanation-of-big-o.html

I've seen this question come up in about half of the jobs I've interviewed for, so it's good to be able to understand it and explain it.

Labels

Labels:

Comments

Post a Comment

Popular posts from this blog

The Gobbler from Arby's

Stop.  Stop what you're doing and go to Arby's. Right. Now.  Have them make you a Gobbler .  This is not something you'll regret. Go. Eat this thing. Look at that bacon. Go. Arby's has a new sandwich.  It's called "The Gobbler" and as far as I can tell it's two things: a vehicle for their new deep fried turkey, and an attempt at a Thanksgiving themed sandwich.  It's also a third thing: magically delicious. move over Lucky, there's a new holiday mascot on the block Unwrapping: this actually looks like a sandwich.  It looks appetizing.  It looks like something I want to eat.  It doesn't look like the promo photo above, but it doesn't look like someone was flailing around and accidentally smashed up a sandwich, either. sexy Instagram caption goes here First bite: Wow.  I mean, "WOW."  Holy h*ck this is good.  The turkey has a really bold, meaty flavor.  It tastes a lot like turkey sliced fresh from your...
Post a Comment
Read more

Sheetz Sandwich Standoff: El Gringo vs Twisted Swiss

My wife left me alone for dinner tonight so I decided to check out the latest GetGo offerings... but to my great chagrin, they have no promotional subs. My travels led me to the local Sheetz, where I'd be able to keep eating the best gas station sandwiches around. To keep tradition alive, I picked the two most outrageous "Burgerz" on the menu: El Gringo and Twisted Swiss. The ingredient list is promising: Twisted Swiss is the burger with topped with swiss cheese, cole slaw, pickles, bacon, and whatever "Boom Boom Sauce" is on a pretzel bun.  El Gringo is the burger topped with pepper jack cheese, chili, Doritos, and BBQ sauce on a regular old bun. I unwrapped them both and stood back to admire the majesty before me. They're not pretty, but they do look a lot better out of the wrapper than many fast food burgers I've eaten. Twisted Swiss I expected this sandwich to be an awful mess.  It just seemed like a bunch ...
Post a Comment
Read more

Interviewing: Tell Stories

Softball questions  are questions the interviewer asks to try to find out about your personality, your history, your level of enthusiasm, and your experience.  While technical questions evaluate your skills or your knowledge, softball questions are meant to have you talk about less quantifiable abilities.  An interviewer might ask a dozen or more softball questions to determine what you're like outside of an interview room. The word to remember for interviews, especially the softball questions, is: STORIES .  People who are good storytellers tend to be good interviewees. Technical questions are important - you need the skills to be able to do the job.  However, often interviewers are convinced by your answers to softball questions - then they spend the rest of the interview trying to convince themselves why they should hire you, instead of spending the rest of the interview trying to convince themselves why they shouldn't. A great strategy for prepa...
Post a Comment
Read more