Author Archives: Admin

Google Technical Inteview Hangout

Two software engineers from Google’s Pittsburgh office deliver a presentation on how to prepare for technical interviews in this Hangout on Air from October 9, 2012. The rundown menu is at the bottom. Head over to http://goo.gl/xSD7jo to learn more about how we hire and to find your role with us.

0:00 – Introductions
0:59 – How we hire Software Engineers
2:49 – Interview preparation
11:38 – Working through sample interview question
26:10 – Example solution
32:59 – Answering user questions

MALE SPEAKER: Hi, everyone. Welcome to another Hangout on Air that we’re doing on the Life at Google channel. Today we’re doing a candidate coaching session talking about technical interviews. And joining me today is Kevin and Vicky from our Pittsburgh office. So I’m going to let them introduce themselves, and then they’re going to take over from here. KEVIN SERAFINI: Hello. My name is Kevin Serafini, and I’m a software engineer here in the Pittsburgh office.

And I’ll be walking you through the presentation. VICKY THEODORELI: Hi. My name is Vicky. I’m also a software engineer here in the wonderful Pittsburgh office. I’m going to be making sure that Kevin doesn’t leave out any useful information from the presentation. KEVIN SERAFINI: Good. Because that could be a big deal. OK. So let’s start. So first off, how do we hire software engineers?

Software engineers are really the biggest hire here at Google. They comprise the largest group of people that work here. When we do that, we’ll generally have multiple interviews and multiple steps along the way. First off, we’ll have one to two phone interviews.

Basically, they’re phone screens. They give us an idea of your skill level and kind of what you’d be appropriate for. Assuming you pass those, then we’ll have on-site interviews. And the on-site interviews, we’ll have up to five of these.

Note that if you’re located in a place that has a Google office, you can actually do all of these at once. We’ll bring you in for the phone interviews as well as the on-site interviews. So the phone interviews will actually be local. VICKY THEODORELI: Even if you’re not actually applying for this office, you could just still get introduced on– KEVIN SERAFINI: Correct. So if you’re at one of the local schools here in Pittsburgh, we’ll often bring you here to do the phone screen and the on-site interview even if you were going to end up working in Mountain View or something like that. Once you pass the main interview, then it actually goes to a local hiring committee. The local hiring committees, each office has one. They basically go over all the candidates that came through and then select the candidates that we want to extend an offer. They’ll put together a hiring packet and then pass it to a regional and company headquarter review. Those are really higher level things. They’re basically adjusting head counts and kind of strategic decisions. Once you’ve reached that level, though, you should be in pretty good shape barring some great change. After that, then the HR person will put together an offer and contact you and let you know basically the details of here’s your offer, here’s what it entails, here’s the office you’re going to work at, and all those kind of things. So let’s talk a little bit about preparation and what to expect. A standard Google interview lasts roughly 45 minutes give or take, depending on how things work out.

There will be a short introduction. Usually when I interview, I’ll give a quick spiel on me, on the office, maybe something a little more about Google. But it’s usually a short, five-minute kind of just to get to know you.

Then we’ll do the meat, which is the actual technical assessment. So that’s where you’ll have a series of coding questions and problems that you’ll walk through. And then at the end, usually the last 5 to 10 minutes depending on how things go, we’ll have an opportunity to kind of review what we’ve done and then give you the opportunity to ask questions. A lot of people would like to know either more about the office or more about working at Google in general, and that’s when we’ll cover those things.

And usually, by the end of the day, most of your questions are answered. So that part can usually be pretty short. VICKY THEODORELI: You usually get a nice, big lunch with one of the engineers that’s not part of the interview itself so you get to ask as many questions as you want. That’s usually the nice part of the day. The relaxed one. KEVIN SERAFINI: Yes, exactly. So that’ll be a break like in the middle of your day. So the skills assessment is all about writing code.

We want to see that you can write good code. It depends on your skill level. So if you’re a new grad, we might have different expectations than if you’re been around an industry for years. The coding questions involve both code

and algorithms and data structures. So we want to see that you understand the basic data structures, and how to use them, and how to apply them to different problems. We’ll keep track of your analytic skills. So you’ll get questions that have maybe interesting bits,

and we want to see how you approach those bits. A lot of them will be something that you might not have studied in school or might not have had before. And we kind of want to see how you adapt to that. And we want to make sure that you have sound design in your code.

We want to make sure that you understand limitations or the corner cases and things like that, error checking. It’s something that we want to make sure that you’re doing when you’re writing your code. VICKY THEODORELI: I was going [INAUDIBLE] say testing, but you [INAUDIBLE].

KEVIN SERAFINI: [LAUGHS] Right, right. And that’s an important thing. Like feel free to say, hey, this could be null or this could be zero, and make a note of it. But we want you to make sure that you’re at least making a note, preferably writing the code

that says to doing these checks. So just to make sure that you’re doing clean kind of production grade eventually, but like production-grade code. VICKY THEODORELI: It’s a difference from school where you can tolerate something’s not working or, ah, kind of like not account for that situation.

When you’re writing production code, you need to understand exactly what could go wrong, and you need to show that you can account for that. KEVIN SERAFINI: Yeah. VICKY THEODORELI: Even if it’s just a simple interview question, that’s still part of the process.

KEVIN SERAFINI: Right. Exactly. So how to prepare for your interview. Basically, the basic idea is review basic algorithms and data structures. It’s hard to emphasize that enough.

You need to understand what things are, what a linked list is, what a heap is, what a hash table is. Understand how they work and why you use them, why you use one over the other. A lot of questions will involve some kind of data structure or be made easier if you use a data structure.

And your interview, you’ll go through the question, and your interviewer will look favorably upon you if you have the right data structure. Or even if you have a sub-optimal one, if you can explain why you’re using it, and then if the interviewer says, oh, you know, a set would be better here than whatever you’re using. Understand why they said that and why they do it, and it’s good. Like, that’s really important stuff. So where were we? Right.

So review algorithms and data structures. Understand how to use them and use them in your code. Like, we’re probably not going to ask you to implement a hash table, but you should understand how it works. VICKY THEODORELI: And by how it works, we’re probably talking O notation, Big O notation about all those things. How long does it take to find things? How long does it take to short things? You don’t have to prove anything, like do mathematical analysis, but you still

need to be able to understand how they work and say that. KEVIN SERAFINI: Right. And the other part of practicing is write a lot of code. Like go to one of these sites, find the problems there, write the code, solve them. There’s no better way of practicing

than actually writing these algorithms. Especially if you’ve been in industry for a while, you probably haven’t used basic data structures, you’re using whatever custom data structures you have on your job. So you might be a little rusty.

It’s definitely worth practicing. Also, practice on a whiteboard or just on a notebook or something. VICKY THEODORELI: On a whiteboard. KEVIN SERAFINI: Yeah. It is actually better to be on the whiteboard,

because you’re used to writing with an editor. You won’t have an editor, it won’t color-code your comments, it won’t highlight anything, it won’t auto-correct things, it won’t insert parentheses, it doesn’t do any of that. And it’s a very different thing if you’re used to just typing in an editor,

writing on a whiteboard. VICKY THEODORELI: And no one’s going to penalize you if you forget a semicolon somewhere, but we do like to see code that’s pretty and that it’s functional. So being able to produce that without the help of an editor

is really important for an interview, because it’s actually going to speed up how you write the code if you have done this before. KEVIN SERAFINI: Exactly. Exactly. And we don’t want to use pseudocode.

You shouldn’t be writing in pseudocode. You should be writing in code. Whichever language you choose, that’s fine. We’ll work through that. VICKY THEODORELI: Whichever mainstream language you choose. VICKY THEODORELI: Right.

Generally, we do our interviews here in C++ or Java. Some other roles might allow Python. VICKY THEODORELI: Or C. KEVIN SERAFINI: Or C. Yeah. C’s fine, C’s fine. VICKY THEODORELI: UI roles might have JavaScript.

That’s also acceptable. KEVIN SERAFINI: That’s true. That’s true. But it will be one of those major languages. It’s not going to be these kind of random– I shouldn’t say random.

But a lot of non-major– VICKY THEODORELI: Specialized. KEVIN SERAFINI: Specialized languages. That’s a good way of saying it. We don’t do interviews in those. So during the actual interview, so you’re here, you have your question, you’re starting to solve it. We’re really interested in how you approach the problem. It’s just like in school. Show your work. You’re going to be graded as much on your work as you are on the final answer.

I always emphasize interviewees when I’m interviewing to think out loud, to tell me what you’re thinking, what are you going, brainstorm, however you want to call it. If you’re standing at the board and you’re not saying anything, I have no idea whether you understand the problem.

Because that’s not an issue, right? We want to see how you think through these things. And by kind of working through the problem, then I can understand and either guide you or understand, like, oh, yeah, they’re on the right track, this is all good. VICKY THEODORELI: Yeah, because the interviewer wants to help you if you have an issue, but they also don’t want to give you a hint if you don’t need it. Because then they’re not doing you any good. So making sure that the interviewer has a clear idea of what step in the process you’re at and what you’re thinking is super important. We could not read your mind. KEVIN SERAFINI: Exactly. And the questions are in-depth, so these are questions that generally don’t have a simple solution. They might have kind of a– or let me rephrase.

They won’t have an easy solution, they might have a simple solution. VICKY THEODORELI: Which is fine. KEVIN SERAFINI: Which is fine. There’s a difference there. And a lot of them are set up so that there is a simple, inefficient solution, and then there’s one that’s better. Or they don’t have a simple solution, and then we’ll expand it to cover other situations. And showing your work there and showing how you approach– like, given the first solution, how

you approach and expand it to these other roles is super important. That’s kind of what we’re really interested in seeing, how you kind of think, how you think on your feet about these different things. The right answer is nice but not necessary.

And the right answer is kind of relative. Personally, I won’t criticize you if there’s some slight error in the code or there’s a semicolon out of the way or something. That’s not important. The important thing is you took the problem, you understood it, you broke it down, you solved it. That’s what we want to see. So here’s a sample interview question. This is a question you will not be asked. I can guarantee that.

But it gives you an idea of what kind of question you’ll be asked in an interview. This is a question that has kind of a simple solution. I wouldn’t say a sub-optimal, but kind of a simple solution that you can start with, given basic assumptions. And then we can change the assumptions and make it more complicated. We can change the solution to make it better, and the better solution is more complicated. And it’s one of these questions that can actually expand to fill as much time as necessary, and don’t be surprised if that’s the kind of question you’re asked. And don’t be surprised if you don’t reach the end of the question. VICKY THEODORELI: The best questions do not have an end. They can go on for as long as you want. KEVIN SERAFINI: Exactly.

And that’s all part of we really just want to see how well you handle these different questions and what you know. And if we asked a question that was super simple and you answered, we wouldn’t know anything other than you know a simple question.

So our sample question here is write a program that breaks up a string of words with no spaces into a string with the appropriate spaces. So if you had, for example, one word, peanutbutter, this method will split it into a sentence, peanut, space, butter.

If you have multiple words, it might not do that. If you have no words, it won’t do anything. VICKY THEODORELI: I guess what Kevin is trying to say is that you’ll probably get asked a question that fits in a sentence, but you can’t answer it unless you start asking questions of your own. KEVIN SERAFINI: That’s a very good point. That’s a very good point. Most of these questions are underspecified. VICKY THEODORELI: Exactly. For a reason.

Because we want to see what questions you need to ask in order to answer it. KEVIN SERAFINI: Exactly. Oh, and that’s actually a great segue. VICKY THEODORELI: We’re ahead of ourselves. KEVIN SERAFINI: Awesome.

So basically, the first thing you should do is clarify the problem. Exactly like Vicky said, these questions are underspecified for a reason. And so the first thing you should do is ask questions. Like, oh, this is fine.

What if we have more words? What if we have an empty string? What if we have a null string? Things like that. You need to talk to your interviewer. And actually, this is all part of the yeah,

I know what I’m doing analysis, because you can be given a problem that is underspecified and help figure out what some of these constraints are. And it shows that you understand how to solve this problem. Oh, go ahead. VICKY THEODORELI: I was just going

to say that if a candidate saw this question and then just immediately started writing code on the board, that would be a red flag. Because there’s so many questions to answer like how do I do– where do– where– I don’t even know where to start with the question.

So getting on board and writing code is not the right thing to do here. KEVIN SERAFINI: Exactly. That’s exactly right. And that’s– like, she can’t stress it enough. VICKY THEODORELI: Oh, yeah.

KEVIN SERAFINI: It is very important to understand the problem and show that you understand the problem. VICKY THEODORELI: Because one of the other things is that you may be thinking you’re solving problem A, and your interviewer is thinking you have to solve Problem B.

And that’s where the whole problem is going to collapse. Because he’s expecting different things that you think you should be doing, and there’s a communication problem there. KEVIN SERAFINI: Right. Right. And you know, it’s just not going

to– you won’t get as high up a review as if you were on the right track. And it’s really, I don’t want to say through no fault of your own, but basically because there was just a communication mismatch. And we want to avoid that.

So for this problem, clarify the problem. Consider an example that’s rich enough but not tedious. So fast man, peanut butter, the same thing. Disambiguate the result. So that’s where I was saying, you know, you will ask, well, what if you have more than one word?

What if you have– or more than two words, multiple words? What if you have an empty string? What if you have a null string? What if you have all numbers? Like these are things that usually if someone would ask me a question like that, I would say either it will guaranteed not be null, or you should verify that it’s not null and build the right thing. One or the other, depending on the question. But that’s a question that you should ask, that you need to ask. So the next bullet.

State and clarify key assumptions. And so in a question like this, the question we have in the slide is where do we get the words? In this case, use a dictionary. Your interviewer might not say use a dictionary. Or what exactly does a dictionary mean?

It could mean that you have a big set of words, it could mean that you have a function call of words. And your interviewer will clarify that. Usually they’ll say, OK, assume you have a dictionary. Here’s the API for the dictionary. Dictionary.asp, dictionary.get, whatever.

Some kind of API. And you’ll use that in your solution. And then the last step, clarify the function’s signature. So make sure that you understand what’s coming in, what’s going out, basically.

So the next thing that you should do is start with the first solution that comes to mind. VICKY THEODORELI: It doesn’t matter if you think it’s dumb. KEVIN SERAFINI: Right. It’s much better to have a dumb, slow solution. VICKY THEODORELI: Nothing is dumb.

If it solves the problem, it’s fine. It could be slow, it could take five terabytes of memory, it’s still something that solves the problem. It’s better than nothing. KEVIN SERAFINI: Right. And then you could iterate on that solution.

So you say, you know what, I know this isn’t the best thing, but we’ll start here and go from there. And in fact, in a sense, a lot of questions that I ask are exactly that. They usually have some, I wouldn’t say obvious, but like a fairly straightforward, inefficient

solution. And you’d do yourself a great– it’s very good for you to implement that straightforward, not optimal solution. And then we can work on it from there. VICKY THEODORELI: Because then no matter what happens later,

we still get a coding sample from you. KEVIN SERAFINI: Exactly. Exactly. And usually you get a lot of interesting conversation out of it as well. VICKY THEODORELI: Exactly.

You see the problem points. KEVIN SERAFINI: Exactly. Exactly. And so as the slide says, there will usually be a brute force solution. And I often joke and say every problem that we have has the brute force n squared solution. Like it’s something that’s not great, but it solves the problem VICKY THEODORELI: And I bet you there are pieces of code in Google right now that do use a very simple, brute force solution, because that works. KEVIN SERAFINI: Right. Right. Exactly. It says, run through at least one or two examples to check. That’s very important.

You have your initial solution. And I will always say, OK, given these examples, let’s see what your code produces. VICKY THEODORELI: One tip here. When you do that, do not assume your code works. Because a lot of people do, oh, I know, I just wrote this,

it works. And they just blindly run through an example, and they don’t actually check that did what I say actually work? Sometimes you have a less than that should’ve been a greater than, for example.

You think the less than is right, you read it, you don’t actually do the math, and you miss the point, you miss the bug. So just assume someone else wrote the code and actually do step it through line by line. KEVIN SERAFINI: Yeah, exactly.

Pretend you’re a debugger. VICKY THEODORELI: Yeah, exactly. KEVIN SERAFINI: And a lot of times when I ask the question, I will actually specify examples. So for this question, I would say, well, what happens if the string is– if I give you peanut butter,

it should show peanut, space, butter. If I give you blah, it should come back with blah. And it’s very helpful if your interviewer asks that as the– when they ask the question, if they actually give you examples, run through those examples.

There might be a reason why they asked it that way. Check for edge cases. That’s very important. There’s a lot of these solutions that look really good, but in the edge cases they break down. And that’s something that you need to address.

VICKY THEODORELI: Make sure your recursion terminates, for example. KEVIN SERAFINI: Exactly. Exactly. Make sure there’s no off by one errors, make sure that things like that don’t plague your code,

because that’s certainly going to be a mark against you. Try to use reasonable variable names and clean up the code. We realize that you’re writing on a whiteboard, not an editor. So it’s not going to be as easy. You don’t have Eclipse to refactor things. And it’s perfectly fine to have variables named x and i and n and what not. So that’s fine. It’ll make things much easier. A lot of people sometimes, they try to be very– in production code, sure, you’ll use more descriptive names than this.

They don’t have to be perfect, because it makes writing it much easier later. And then before you actually refine it, ask the interviewer if they have any questions. The interviewer might point out something that you left out, might point out an edge case that you

didn’t remember, or might actually ask you about the solution. Like the solution might be perfectly correct, and they might want to say, well, so what’s the run time of this, what’s the memory usage? Things like that.

So leave some time or make sure– give your interviewer the opportunity to ask those questions. It goes a long way. So then Part Three is refine the solution. So in this case, this is where you might end up

either A, doing better, so you end up with a faster solution than before, or B, you might start exploring different parts of the question. So for our question, the initial assumption was we’re going to have two words. Well, now maybe we’ll assume it has multiple words, three

words, or whatever, more than two. VICKY THEODORELI: Or [INAUDIBLE] there’s different ways you could split the string. KEVIN SERAFINI: Right. VICKY THEODORELI: For example, peanut is– KEVIN SERAFINI: Is also can be split.

VICKY THEODORELI: Is pea and nut, yeah. KEVIN SERAFINI: Exactly. VICKY THEODORELI: [INAUDIBLE]. KEVIN SERAFINI: Right. VICKY THEODORELI: [INAUDIBLE]. KEVIN SERAFINI: So that’s an issue, right?

And that’s something that, again, by going over these things and working through them with your interviewer, your interviewer will have a better understanding of your understanding. VICKY THEODORELI: And the interviewer will probably guide you.

He will point out, for example, the peanut butter case. Like, what happens here since this can be split two ways? And then you’ll just say, oh, that was not part of my original assumptions, but I can change my algorithm this, this, this, and that. And now it can also handle this case.

KEVIN SERAFINI: Exactly. There might be a faster way to do it. You had an O n squared, and now we’re going to come up with the O log n or n log n or something like that. And working through those different solutions is a way to provide input on, like, yeah, I really know what I’m doing, this is how I solved the problem, and so forth. One question that a lot of people ask and I always say a lot of people will ask about do I need to know specific library calls or anything like that? And for me, the answer is no. Like, as long as you understand that yeah, there’s some way to get the length of a string, or there’s some way to get the size of an array or a size of a set or something, that’s fine.

Like feel free to say, I know there’s a way in Java to do blah, I don’t remember what it is. And I will give you the answer. Or we’ll make something up if I don’t know the answer. Or I’ll make something up and won’t say that I’m making something up.

VICKY THEODORELI: You mean there’s candidates that can do .length instead of .size? KEVIN SERAFINI: Right. VICKY THEODORELI: Oh my god, that’s such a terrible mistake. KEVIN SERAFINI: Exactly. VICKY THEODORELI: I get them wrong half the time.

KEVIN SERAFINI: Yeah, exactly. And that’s why. And in general, we’re not– again, you don’t have your APIs next to you, you don’t have– so don’t feel bad if you can’t remember something like that.

We’ll just– it’s not a big deal. So the next slide here talks about these problems kind of– the first one, how do we handle these multiple word situations. And you could end up with a very complex solution, and that’s why you want to talk through your interviewer.

The next couple bullets start going down themes that you might see. This next one in particular. What if the dictionary cannot fit in memory? That’s a common theme in Google questions, and I know I’m not giving anything away by saying that.

Like, Google operates at a scale that’s pretty big. And you will often see a solution for a problem in kind of an isolated– I’m doing a homework problem answer is great. If you expand that problem to scale, that solution often will not work.

And even if you don’t necessarily code the solution for this big, crazy problem, like the big, crazy scale problem, we’ll talk about it. As long as you have some idea of how to approach that, that’s what we’re looking for. Because we don’t expect you to have done some big, crazy multi-processor solution. But as long as you have an idea of how you would approach the problem, that’s important. VICKY THEODORELI: That’s also why it’s important to get a coding sample early, because if you go down a path that leads to a very technical and hard-to-solve problem, then you will probably not be able to code it. And that’s fine, because that’s not what the interviewer wants you to do. They want to see how you think about different problems. But having had that coding sample in the beginning, they are also confident that had you had the time, you would have been able to come up with a coding example. KEVIN SERAFINI: Exactly. And then the last two bullets here are also more refinements. How do you print the most likely multiple choices, like the peanut butter thing?

And it could be you might have to make some decision. Is it going to be peanut butter or pea, nut, butter, two words or three? Work through with your interviewer. They’ll come up with something pretty sane. What if the words aren’t spelled correctly?

So this is a super advanced problem where however you tokenize the string, then you would do a spell check, some kind of spell check algorithm on the string. I mean, if you get to that point, you’re probably doing pretty well.

I’ll be honest with you. But like in general, it just shows you that there might be twists in these problems that are just more taking the base problem and then extending it into these different regions. And it provides a lot of interesting information.

VICKY THEODORELI: And makes the interview fun. KEVIN SERAFINI: Yeah, exactly. And the interview should be fun. I know it doesn’t sound– it’s not going to feel like that. But a good interview is really just a conversation between two engineers.

You have a problem, you kind of work through the problem, you talk about different solutions. We understand that you’re nervous, we understand all that stuff. But when all is said and done, as you

work through the problem, this is really just a discussion of here’s the problem, I understand how you solve it, this is kind of what I want to do, does it sound sane? Yes, it sounds sane. How can you make it better?

And it’s really just almost like a conversation that you’d have every day at work. VICKY THEODORELI: And ideally, you should enjoy that, right? KEVIN SERAFINI: Right. VICKY THEODORELI: If you like your job, that’s exactly what your everyday work is.

KEVIN SERAFINI: Exactly. So here we have an example solution. This is the example for the super simple, semi-brute force– VICKY THEODORELI: Semi-brute force? KEVIN SERAFINI: Well, semi-brute force.

VICKY THEODORELI: OK. KEVIN SERAFINI: I don’t– I don’t even short circuit. Anyway. VICKY THEODORELI: Nope. Pretty brute force. KEVIN SERAFINI: So this is the pretty brute force solution.

But it gives you an idea of here’s step one. Like I have the problem, I want to put something on the board. That gives us a starting point, and then we can refine from there. This is in Java. I called it “Break Into Spaces.”

It takes a single string argument. And basically, all this solution does is loops through the string, splits the screen in two by where the current index is, and sees if both words are in the dictionary. And in this case, I used a set to see if the words are in it, but like I said, you would work through with your– you would ask your interviewer and say, how do you want to do this? Your interviewer will pick something. They might say, yup, you have a big set called Dictionary, or we have a class called Dictionary. You can use it to look it up. Here’s the API. And then at the end, this return source. Note that this solution is pretty basic and actually does not satisfy some of the other criteria.

Like the multiple words it would fail, although it should be easy enough to extend it to multiple words. Brute force, but multiple words. Making it not brute force would be another refinement that would be pretty easy to do.

The spell checking is probably a little extra here, but that’s OK. But anyway, it gives you an idea of yeah, this is actually a pretty simple solution. It’s not easy. It requires some thought to make sure,

but it’s pretty straightforward once you solve the problem. And then we’re going to take that simple solution and make it into the more complex, more interesting solutions that we can talk about afterwards. OK.

Some tips. So optimizing. It’s always a mistake in an interview and in engineering in general to optimize too early. VICKY THEODORELI: Especially if you don’t know what your constraints are.

KEVIN SERAFINI: Exactly. I’ve seen a lot of people make that mistake. And then you end up kind of going down the rat hole or wasting a lot of time on a solution that won’t work, because there’s some mistake there or some misunderstanding. And that’s bad.

You don’t want to waste your time on things like that. You want to actually be making progress toward solving the problem. Now, that said, if you understand that there’s a log n solution versus an n solution, then you can do the first– the former– do that.

If using a hash map is good, using efficient algorithms in a binary search, that’s all good. VICKY THEODORELI: You don’t have to come up with a brute force. KEVIN SERAFINI: Right. Even though I always did.

But that’s OK. It worked for me, right? I’m here. So it’s all good. Time-space trade-offs. This is another interesting one that a lot of people won’t think of off the top of your head. But understand that those can be made. If you’re going to optimize, you often can optimize by trading time for space or pre-computing things. Maybe that’s a valid thing. It’s at least worth talking through your interviewer.

Like, oh, we can actually do the first n number of these and keep them in memory. Is that a reasonable idea? And a lot of times, they’ll be like, yeah, that is, let’s do that. And then the final bullet is assumptions.

This is the big or small. In some cases, say, if you’re comparing two parts or whatever, the optimal solution changes if the number of things is large or small. And that’s something that you will go over whenever– a lot of times when they refine

the question, a common refinement is, well, what happens if your input is significantly bigger? Like in the previous example, what happens if it doesn’t fit in memory? VICKY THEODORELI: Or for example, the string you have to split on all those.

Let’s say, for example, you know that the maximum dictionary word you have is 16 characters and you have a string that’s 59, do you actually have to check in the dictionary if it’s a word? You don’t have to. KEVIN SERAFINI: Exactly.

VICKY THEODORELI: Because you know it’s not going to be there. KEVIN SERAFINI: Right. Exactly. Exactly. VICKY THEODORELI: Little tidbits like that.

KEVIN SERAFINI: Yup. Little things like that that help you when you’re making more efficient in answering the question, which is good, because then you can actually be doing more meat, kind of more interesting problem solving, and kind of less side calculations, API.

If you can’t remember the name of the method or how it behaves, ask. I said it before. I’m never going to hold it against you. Just ask. VICKY THEODORELI: In general, just ask.

KEVIN SERAFINI: Just ask. I’ll either give you the answer or make something up. Or we’ll make something up and move on, because it’s not interesting to know whether you know all the methods for a set class to Java. I don’t care.

That’s what the internet’s for. VICKY THEODORELI: Google? KEVIN SERAFINI: Right. Testing. Say what cases you’re going to test. Walk through your code, make sure that it does what you think it does. And like I said, a lot of times your interviewer will give you examples specifically, like the peanut butter one is actually one. Like there’s a reason why they might give you some of these examples, because they illustrate different parts of the problem. VICKY THEODORELI: But you should also give yourself a hard time by picking test cases that you would expect to fail. KEVIN SERAFINI: Exactly. VICKY THEODORELI: Under different circumstances.

KEVIN SERAFINI: Exactly. Off by one, things like that. And then try to reserve some time to work a small case, which is basically the testing. Like all the time when I give an interview, there will be these small things that either pass whatever we’re doing or fail whatever we’re doing. And also keep in mind there might be some degenerate cases that completely break your problem. So those are things to keep in mind when you’re testing that. Awesome. So that’s the meat of our presentation.

We have a few questions that we’d like to go over. VICKY THEODORELI: Yes, we do. OK. Are you ready for this? KEVIN SERAFINI: All right. Let’s do it.

VICKY THEODORELI: OK. Let’s hope they’re not going to give us too hard of a time. OK. First question. Does Google account for cultural differences and language barriers during the interview?

Yes. As you can tell, not everyone was born in the US. KEVIN SERAFINI: Exactly. VICKY THEODORELI: So that’s something that every Googler has learned to work with. And I think we’re pretty good at it.

KEVIN SERAFINI: Yeah. I think we’re pretty good at it. It’s generally not an issue. VICKY THEODORELI: No. KEVIN SERAFINI: At all. VICKY THEODORELI: I mean, speaking English

is probably a plus. KEVIN SERAFINI: Speaking English is a plus. Right. Speaking the same language as your interviewer, certainly a plus. VICKY THEODORELI: OK.

Does Google train their interviewers? How does it make sure that the interviewers are not showing off more than trying to learn about the interviewee’s skills and abilities? Because we’re nice people. KEVIN SERAFINI: Exactly.

VICKY THEODORELI: OK? I just went through my training, actually. Yeah, we do get trained. They don’t just throw us into a room with a poor interviewee to test our skills.

No, we get formal training. We have very strict rules about what we’re supposed to do, how we’re supposed to do it, what the scoring is, what we’re looking for in a candidate. We don’t all show up and ask the same question. We’re trying to coordinate.

And the interesting part is that your first couple of interviews you don’t do alone, you do with someone else. Initially, you observe them, and then they observe you. And for those initial interviews, I think your feedback is actually not accounted. KEVIN SERAFINI: Right.

Right. VICKY THEODORELI: It’s actually the senior person that has the final say. You’re just learning how to do this, and you’re calibrating yourself. KEVIN SERAFINI: Exactly.

And so that’s the only time that there will be two people in the interview with you. So if you are in an interview and two people show up, that’s why. Basically, someone is observing, someone is doing the interviewing.

And it’s all part of the interview training. It’s natural. They’re not going to shotgun questions to you or anything weird like that. VICKY THEODORELI: No, they try to make it as friendly as possible.

KEVIN SERAFINI: Exactly. VICKY THEODORELI: One’s going to be quiet in the corner. KEVIN SERAFINI: Exactly. VICKY THEODORELI: Awesome. OK. Oh, there you go.

Does Google take into account that a combination of general interview fear and specific Google [INAUDIBLE] can make candidates under-perform? I thought we were nice people. We covered that already. KEVIN SERAFINI: Exactly.

VICKY THEODORELI: How does Google make sure the final decision doesn’t exclude shy/insecure but smart people? What do you think? KEVIN SERAFINI: I think a lot of this goes to the ask questions part.

If I see a candidate at the board– you kind of break the ice with the initial, you know, here’s what I am, here’s what we do here in Pittsburgh, blah, blah, blah. VICKY THEODORELI: You try to smile. KEVIN SERAFINI: Exactly, exactly.

Right. You try to make them a little bit more relaxed. And then you go into the question, and that’s where it becomes a conversation. If I see a candidate kind of stuck or not saying anything, I’ll try to help them out.

I’ll be like, oh, so what are you thinking? What angle are you looking at here? Or something like that. And try to kind of, like I said, break the ice, try to get them more engaged, really. And as long as you’re talking about technical things, I think that, for the most part, that works itself out. The initial nervousness goes away, and then you just start talking about the problem. VICKY THEODORELI: And there’s also a lot of interviews over the day, so you should be feeling more and more comfortable with the whole process. KEVIN SERAFINI: Right, right. VICKY THEODORELI: That being said, it is important to be able to communicate your ideas. So having someone that doesn’t say a single word is past shyness, I think.

KEVIN SERAFINI: Yeah, it’s tough. Yeah, exactly. And that’s why we say make sure you just talk out loud, think out loud. VICKY THEODORELI: But we understand that sometimes it can be intimidating.

But on the other hand, I was more scared than the candidate on my interview for sure. I was like, oh my god, what am I going to do now? I don’t want to do this. KEVIN SERAFINI: Exactly. VICKY THEODORELI: They had to push me into the room.

It worked out fine, by the way. I think, at least. KEVIN SERAFINI: Yeah. VICKY THEODORELI: OK. Which path can an individual follow to get into Google? The lobby’s on the second floor.

Please mention what languages, certifications, or any other important factors maximize the chances of selection of the pressure? OK. Languages. Any mainstream.

I thought we already covered that. KEVIN SERAFINI: Yup. C++. VICKY THEODORELI: C++, Java. That’s it. You don’t have to–

KEVIN SERAFINI: JavaScript for UI maybe. VICKY THEODORELI: Yeah. KEVIN SERAFINI: Python maybe. VICKY THEODORELI: Python is tricky. But I don’t think you’re going to be turned down if you say, like, I’m really awesome at Python,

in your interview. KEVIN SERAFINI: Right. VICKY THEODORELI: Just buck your [INAUDIBLE]. KEVIN SERAFINI: Right. VICKY THEODORELI: I don’t know about certifications. KEVIN SERAFINI: Yeah.

For the software engineer roles, it doesn’t really matter. VICKY THEODORELI: I don’t know if in the security teams they care. But I really– KEVIN SERAFINI: Right. I don’t–

VICKY THEODORELI: Yeah, that would be surprising if there’s like an oh my god, this guy has no certifications, we’re not going to interview him. No. KEVIN SERAFINI: Right. No.

That’s not the case. VICKY THEODORELI: Yeah. Just good coding skills. Practice algorithms. That’s all you need. And be able to showcase that in five interviews.

KEVIN SERAFINI: Right. Exactly. Throughout the day. VICKY THEODORELI: OK, yeah. This is relevant. In the tech interviews, is the way the interviewee approaching the problem more important than skills and experiences? Yes, yes, yes, yes, yes, yes, yes. KEVIN SERAFINI: Exactly. We want to see you working through the problem. The code is the tool that you have.

That’s your hammer or nail or saw or whatever cheesy analogy you want to use. VICKY THEODORELI: Exactly. KEVIN SERAFINI: Right. We want to see how you solve these problems. VICKY THEODORELI: How you think.

KEVIN SERAFINI: Exactly. How you think. VICKY THEODORELI: And even if you have the most awesome skill set in the world, you are going to come in at Google, and then the first few months you’re going to be, oh my god, I have no idea what’s happening around

me. So you’ll have to relearn everything you know anyways. So it’s kind of like subjective what skills are. KEVIN SERAFINI: Exactly. VICKY THEODORELI: Because everything is– KEVIN SERAFINI: Exactly.

In everything here there’s a ramp-up period. Everyone expects it, everyone understands it. And that’s just part of the deal. VICKY THEODORELI: And we’re not talking a week, we’re talking months. KEVIN SERAFINI: Right.

Exactly. And that’s just part of the deal, so don’t let it bother you. VICKY THEODORELI: Everybody’s been there before, everybody’s done it. And we have survived.

KEVIN SERAFINI: Yes. Exactly. VICKY THEODORELI: OK. How does the interviewer choose questions? Does he have his own set of questions, or do you have a pool of questions?

We Google interview questions. KEVIN SERAFINI: Right. And then pick the top [INAUDIBLE]. VICKY THEODORELI: No, we don’t do that. No. We’re encouraged to pick our own questions.

That being said, it’s probably wise when you do that to run the question with your class senior engineers that have some experience. KEVIN SERAFINI: Yeah. When you come up with a question, it’s very common for you to come up with a question and talk with other engineers. I’ve often done mock interviews and basically said, OK, here’s this new question I want to use. I’m going to try it out on you, and let me know what you think. And we try to keep– I’ll have a set of questions that I use. I try to use kind of a consistent set of questions, because it helps me help you. How’s that sound? VICKY THEODORELI: Cheesy. KEVIN SERAFINI: Actually. But it does, right? It is cheesy, but it’s true, because I understand the question and understand like the problem space. If someone’s kind of going off the rails, I can bring them back and say, well, you know what, that solution, I understand what you’re trying to do, it’s cool, but we’re not going to do that today. Or that’s not an optimal solution, and here’s why. Let’s talk about something else. And it’s really just to kind of guide you. It helps you analyze and understand what the interviewee is doing.

VICKY THEODORELI: And that’s why interviewers generally try to have their couple questions and use them often, because then they have seen a lot of solutions. They have seen what works, they have seen what candidates struggle with.

So they are able to identify where this is going fast and try to fix it before it goes haywire. KEVIN SERAFINI: Exactly. And that’s all good. Like, that’s actually OK. VICKY THEODORELI: That’s the responsibility

of the interviewer to make sure you don’t go down a rabbit hole that you cannot get yourself out of. KEVIN SERAFINI: Exactly, because we don’t want to do that. VICKY THEODORELI: No, it’s wasting everybody’s time, and we don’t want to do that. KEVIN SERAFINI: Exactly.

VICKY THEODORELI: Yup. KEVIN SERAFINI: Cool. VICKY THEODORELI: Awesome. Is having a degree mandatory? KEVIN SERAFINI: So the answer is no. If you have no technical degrees and you

wanted to become a software engineer, it’s probably going to be challenging. But it’s not a requirement. Like as long as you have the skill set that it takes and you can understand the problems and write the code– VICKY THEODORELI: And there’s also

people with substantial field experience that might not have a degree. KEVIN SERAFINI: Right. And the Computer Science degree is also not necessary. VICKY THEODORELI: Nope. We have a–

KEVIN SERAFINI: Because neither I. VICKY THEODORELI: Well, sort of. KEVIN SERAFINI: Sort of. VICKY THEODORELI: But we have mathematicians. KEVIN SERAFINI: Right. We have mathematicians.

I’m a mechanical engineer. VICKY THEODORELI: I’m an electrical engineer. Statisticians, physicists, you name it. KEVIN SERAFINI: You name it. Astronomy. VICKY THEODORELI: Astronomy, yeah.

Generally, everything that deals with math and large data sets, that works for Google. KEVIN SERAFINI: Exactly. VICKY THEODORELI: [INAUDIBLE]. KEVIN SERAFINI: Yeah, I know. VICKY THEODORELI: Yeah, I know.

OK. So would you advise to prepare for the interview or do the interview as a natural as possible without reviewing? Well, if we didn’t want you to prepare, we wouldn’t be here right now. KEVIN SERAFINI: Exactly.

VICKY THEODORELI: So you get the hint. KEVIN SERAFINI: Yeah, preparation is a big deal. VICKY THEODORELI: A whiteboard. Write on the whiteboard. KEVIN SERAFINI: Yeah. Exactly.

It’s a big deal. You know, preparing is the whiteboard part, it’s the accepting the fact that this is multiple interviews in a day. You know, it’s a little tiring. Make sure you get a good night’s sleep.

Make sure that you understand these different algorithms and different data structures, because those are the kind of questions that are going to be asked. VICKY THEODORELI: And we’re not talking crazy, PhD-level questions here. KEVIN SERAFINI: Right.

VICKY THEODORELI: No one’s going to tell you about this data structure that you’ve never heard before, but they will expect you to know what a binary tree is, right? KEVIN SERAFINI: Exactly. VICKY THEODORELI: So if you don’t remember, you need to go back to your algorithms and data structures book and freshen your memory a little bit. KEVIN SERAFINI: Right. And it’ll be very helpful on the day of the interview, because again, you can have just the conversation. It’s a conversation between peers and not anything uncomfortable.

And that’s what we want. We want that conversation between peers. VICKY THEODORELI: Exactly. And last but not least, oh boy, I do not want to answer this one. What is the delay of reply between each interview?

KEVIN SERAFINI: Yeah. VICKY THEODORELI: That depends. KEVIN SERAFINI: That depends, right? It depends really on the interview load. Some times of the year are really bad. VICKY THEODORELI: Like now.

KEVIN SERAFINI: Like now. Exactly. VICKY THEODORELI: College right now. Oh my god. KEVIN SERAFINI: Exactly. And as interviewers, we interview everyone from college grads to industry experience. And so if there’s a lot of interviews going on like there is now, it will probably take some time. Exactly how much, that is hard to say. Your recruiter will give you an idea of what the turnaround is. So feel free to ask them.

They’ll let you know like hey, we’re really busy, there’s a lot going on, so it might take some extra time. They’ll at least set your expectations as to what that’s going to be. VICKY THEODORELI: That’s the only thing we didn’t specifically mention. It doesn’t exactly tie in. I just thought of it that during the interview, the interviewer will actually be taking notes of what you’re saying, because he has to go back and write feedback.

And that has to go to the committee that Kevin mentioned in the beginning. So that’s a very natural process. Don’t freak out if someone has a notebook and starts scribbling down like crazy. But what that means is that then they have to take those notes,

type them up, polish them, explain what they feel about the interview. And all that takes time. Now, multiply that with 10 people per day, add your typical workload, and then you can see how this can go back if there’s

like a crazy interviewing time. KEVIN SERAFINI: Right. Like now. VICKY THEODORELI: Yes, like now. KEVIN SERAFINI: Exactly. VICKY THEODORELI: Woo, I guess we’re done with the questions.

KEVIN SERAFINI: Yeah, I think that wraps it up. VICKY THEODORELI: Yeah. MALE SPEAKER: OK, guys. Thanks so much. This was a lot of really good information. And yeah, I want to thank both Kevin and Vicky

for participating. And thank you all for watching. We hope to do more of these candidate coaching sessions in the future. So please follow us on the Life at Google page on Google+. And if you’re interested in applying for a role, you think you have what it takes now to go in and apply and do an interview, just browse our job site at www.google.com/jobs. All right. Thanks, everybody. KEVIN AND VICKY: Thanks.

paradox dragon

I met three dragons. One always tells the truth, other one always lies and the last one alternates between lie and truth.

Dragon 1: You may ask us one question, then you must guess which dragon is which

Dragon 2: He’s lying. You may get three questions

Dragon 3: Oh no. It’s definitely one question

Right Rotate an array by k elements

An array of elements is given arr
arr is of length n
Right rotate array by k elements
Time complexity O(n) and space complexity O(1)

Sample Input:
arr = {1,2 ,3,4,5}
n = 5
k = 2
Output :
arr = {4,5,1,2,3}

Building a Stack with a getMax() function

Suppose you had a Stack class. Write a new class MaxStack which, in addition to push() and pop(), has a method getMax() which returns the largest item in the stack. Use your existing Stack class to store the stack’s contents.

Don’t just use pop() to “dig” through your stack to find the max—do something that lets you return the max in constant time.

Solution

We could have an instance variable where we hold the max, but there’s a problem—when we pop that item from our stack it’s no longer the max. Now we have to “dig” through our stack to find the new max. Ideally we’d keep track of the current max as well as what the new max will be when that max is popped.

The trick is to have two instances of Stack inside our MaxStack. One holds the actual stack contents, while the other (call it maxesStack) holds the maxes. Whenever we push() an item, if it’s larger than the top item in maxesStack, we also push it to maxesStack. Whenever we pop() an item, if it’s the same as the top item in maxesStack(), we also pop() it from maxesStack.

So at any given point we can get the overall max in constant time be peeking at the top item in maxesStack.