# A System Design interview with a Google engineer

#### Watch someone solve the file parsing problem in an interview with a Google engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

### Interview Summary

**Problem type**  
File parsing

**Interview question**  
1) Given an inefficient file structure, how would you store data to efficiently look up the query?  
2) How would you alter this if you had many computers available?

### Interview Feedback

**Feedback about The Incredible Hawk (the interviewee)**  
Advance this person to the next round?  
Yes  
How were their technical skills?  
3/4  
How was their problem solving ability?  
1/4  
What about their communication ability?  
4/4  
> He was very good at explaining his logic and letting me know what he was thinking when working through the problem. Well done.

**Feedback about Intergalactic Avenger (the interviewer)**  
Would you want to work with this person?  
Yes  
How excited would you be to work with them?  
1/4  
How good were the questions?  
4/4  
How helpful was your interviewer in guiding you to the solution(s)?  
4/4

### Interview Transcript

**Intergalactic Avenger:** Hi.  
**The Incredible Hawk:** Hey.  
**Intergalactic Avenger:** How's it going?  
**The Incredible Hawk:** Good, how are you?  
**Intergalactic Avenger:** Doing good. Alright, you ready to jump on in?  
**The Incredible Hawk:** Yeah, let's do this.  
**Intergalactic Avenger:** Okay. Just a really quick question, what's your background, like what... this isn't really too much... the question I have isn't too heavy in programming, but just what kind of programming languages are you comfortable with so I have an idea.  
**The Incredible Hawk:** Python would be my favorite, a little bit of JavaScript.

**Intergalactic Avenger:** Okay, perfect. Alright, so today I'm going to ask you a question about data munging and... well, let's just stick with that. Last quick question, do you understand the fundamentals of baseball? Like the mechanics of innings and batters and pitchers and stuff like that?  
**The Incredible Hawk:** I'm gonna go with no.

> **Intergalactic Avenger:** So basically what happened to set the tone... so you've just started to work at a new startup that's called Internet Baseball Database and their customers have started to complain that the features aren't very good and that the site is really slow, so you've been told to come on in and kind of help clean everything up. So the idea is that this company gets a regular data feed from major league baseball that has data that they're going to want to display on their site.

**Intergalactic Avenger:** So when someone comes to the site, right now the only thing they can do is they can look up a certain date and look at all of the information for the games played on that day. But he started to get some comments that wouldn't it be nice to look up other things, so for example, wouldn't it be great if you could just look up a particular player and see some of the stats for that player, and as you might imagine, using this technique of storing the data, that's a bit inefficient.

**The Incredible Hawk:** Okay, quick question. If you were to reorganize them as datasets like... something like this... would that directory probably have more than a thousand entries at some point?

**Intergalactic Avenger:** It would, because this is all of baseball for the hundred years that they've been playing. So it's definitely too many.

**The Incredible Hawk:** Alright.

**Intergalactic Avenger:** And specifically just to... so that's just the overall thing, and then the the specific sort of feature that we'd like to do is we'd like to be able to calculate or show on the site their batting average, so the batting average is the number of times that they got a hit divided by the total times that they went up to bat.

**The Incredible Hawk:** What about the second letter in their name?

**Intergalactic Avenger:** Could you do like a two or three letter directory?

**The Incredible Hawk:** Yes, that would be a reasonable way to sort until you had less than a thousand and I mean reasonably so like you have the first two letters or maybe three letters, whatever it is, seems to work pretty.

**Intergalactic Avenger:** Let's say that you know this guy who wrote his own file system, he did it terribly inefficiently and even just doing a search over all of the directories, like getting a list of all the subdirectories inside directory is really slow. So we wanted to still optimize that so that you are doing as few possible sort of linear scans of the of these directories.

**The Incredible Hawk:** So you know back up here I had... it was just a single player name dot txt. If that was an issue then you have to do something like A1 and A2 and you're going to search through all these files, which is kind of annoying to find a player that you're looking for.

**Intergalactic Avenger:** So technically a binary search would be going from A1 to A4 and then looking at A4 and then you would decide if you want to go back to A3 or forward to A5 kind of thing.

**The Incredible Hawk:** I want to say sorted by name, then that doesn't work when you're inserting... you don't maintain the sort, so that's not good. I mean then you have to change everything potentially.

**Intergalactic Avenger:** Well do you though?

**The Incredible Hawk:** So we want to try and do this in with a parallelized... okay.

**Intergalactic Avenger:** This sort of general like I don't know if you're familiar with any of these like Hadoop or MapReduce kinds of things or just if you can think of some generic kind of way of parallelizing this across sort of many machines.

**The Incredible Hawk:** Would that directory probably have more than a thousand entries at some point?

**Intergalactic Avenger:** But also like think about the UI, so in the UI we're just looking up the player name, we don't know what team they are necessarily.

**The Incredible Hawk:** Got it. So other things that I can think of, like other attributes on the player I mean, it's their batting average that we're looking for. But I'm a little ambiguous of why that would be a good bidding structure.

**Intergalactic Avenger:** So if we have hundreds of thousands of players, then once you get down to these individual ones, probably not going to make a difference.

**The Incredible Hawk:** Got it yep, I see that.

**Intergalactic Avenger:** Right. So if you think about it, I mean you're really on the right path with the the A B C thing, so where did you get that and in general what is that technique sort of called when you have some kind of value and you're putting them into buckets according to some kind of attributes that they have? So in this case you have the players names, you have a bunch of different players names, and then you're sorting them into the buckets like A B C based on the first letter of their name.

**The Incredible Hawk:** Is that the only thing we'd like to find about these people?

**Intergalactic Avenger:** Well, if you were going to create that file, it would have one row for every player, right?

**The Incredible Hawk:** Yes.

**Intergalactic Avenger:** So then how long would it take to look up a player in that dictionary?

**The Incredible Hawk:** The size of the file, like where if n is the size of the file, it would take O(n).

**Intergalactic Avenger:** Right, so if you had hundreds of thousands of players, then maybe it's not a very efficient file system, maybe that's also going to be a little bit slow because you got to read in the entire file and then do a search on it and then... But yeah, that's a good start.