(Intro music: Electro swing)

Hello, and welcome to BookBytes, a book club podcast for developers. We’re talking about Cracking the Coding Interview, 189 programming questions and solutions by Gayle McDowell. I’m Adam Garrett-Harris.

I’m Safia Abdalla.

I’m Jason Staten.

So, I read this book about two years ago when I was interviewing as well as about a year ago when I was interviewing and I always recommend it to anybody who’s interviewing or thinking about interviewing, especially if they’re interviewing at one of these big tech companies. And, you know, actually, I never thought I could get a job at one of these big tech companies but it’s actually a lot more attainable than I first thought.

You know, because they’re not recruiting out of these small colleges that I went to. So if you’re from one of these smaller colleges or self taught, you really just have to go and study and apply yourself.

So, anyway. This book is massive. It’s about 700 pages long, but most of it’s just solutions and so the overall structure is that there are eight chapters at the beginning which are about 80 pages and they cover some basics about the interview process. Then there’s the actual questions that are about 100 pages, but that’s kind of split into different chapters based on topic. So it will talk about arrays and strings to give you some hints and then it will have some questions about it, and then the questions, they have different hints that you can go and look up and then you can go and look at the actual solutions. And then after that there’s the solutions which is about 400 pages and then there’s some advanced topics, a code library because there’s certain types of things that come up over and over again and so that that code is just sort of in one spot at the back, and then there’s the hints.

How did you use the book when you were studying? Did you, like, just go straight to the problems and do those? Did you read, like the intro chapters at the beginning? Did you use the things at all? What was your process then?

Yeah, I had enough time that I went and read all of the eight chapters at the beginning, then I went through and started reading each section. I’d read a chapter before the problems and then I wouldn’t answer all the problems, you know, I would read about strings and then answer a couple of questions and then move onto the next section.

And there were certain chapters that I didn’t really feel applied to me, or I wasn’t as interested in. Like, I didn’t think I would get asked about object oriented design as much, or there’s a chapter on C and C++ and one on Java, so I, kind of, skipped some of those.

Got it. So you were, kind of, selective about the content.

Yeah. And then when I was being really good about this I would get an actual white board and then write out the code on the whiteboard. And then after it’s written out go to the computer and type it in and see if it works.

Oh, wow. So you actually went in and coded, like, a compiler, or /interpreter approved code?

Yeah.

Okay.

So that’s what it recommends. It recommends that you read the question, you try to solve it on paper or a whiteboard without looking at the hints or the solution, just try to do it on your own, and then test it on paper, and then go to the computer and type it in exactly as it is on paper and see if it works.

I see. That’s interesting.

Yeah.

Not the process I’ve used for things. So that’s interesting that it recommends that.

When you went through the problems, Adam, did you also try and talk through it aloud? Because I know that’s probably the most important thing of any whiteboard interview is letting people know and like, the interviewer knowing rather actually coding it 100%, or at least that’s always been my take on it.

I think I did that a little bit because I also watched a video from Google about how to interview at Google and so they talked about how to write it out, how to ask questions before you even start to make sure you understand the question fully because when they ask the question they’ll give you little hints, like, little, they’ll include, or not include certain information that’s relevant to solving it and so making sure you answer it really well. And then it talks about describing the naive or brute force approach. Maybe, not actually writing it on the board, just describe that to let them know that, yes, you can do a naive approach and then talk through maybe a better solution and then starting working on it.

Yeah, I agree with that approach. That’s the strategy that I always use whenever I’m interviewing is I, like, I ask questions, throw out a brute force answer and then spend the rest of the time optimizing.

Yeah, and if all you can think of is the brute force, then go ahead and put that on the board and then they’ll probably ask you how you could optimize it.

Mm-hmm (affirmative).

Or ask you what the Big-O is.

I’ve definitely been in that situation before of only being able to think of the brute force option, especially when coming up with it on the fly during an interview. And so, just getting it up on the board and having it as a point that you can discuss with the interviewer makes a lot more of a statement than sitting there quietly trying to churn out a linear, line, answer if you just don’t know.

Yeah. So chapter one kind of talks about the interview process in general and one of the things it says, especially with these big companies, is that they want to make sure they get really good people and so they are okay with there being false negatives Meaning, they’re okay with turning away really good people, what they don’t want is false positives where they let someone not so great into the company.

Hmm, interesting. Yeah, I guess that makes sense.

Yeah, even if you get rejected that’s not necessarily anything against you, it could just be you had a certain interviewer that was looking for a certain set of skills and if you’d gotten someone else then you would have gotten in. And the other thing is you’re not necessarily supposed to finish all of the questions. So you can’t tell how well you did because they’re comparing you with every other candidate and you don’t know how well the other candidates did.

So it, you know, it definitely said basic data structure and algorithm knowledge is useful. I went to this one interview one time where the job description said, “Hey, you don’t need to know any data structure algorithm stuff or weird logic puzzles.” And then I went in for the interview and that’s exactly the kind of questions they asked.

(laughs)

yeah, I think at smaller companies sometimes you don’t get these data structure questions but super useful to know and the big companies will definitely ask those.

And then Chapter Two talked about behind the scenes at Microsoft, Google, Apple, Facebook, and Planter? And just how their interview process is different from each other. You know, some of them you’re applying for the whole company in general and then after you get hired you pick what team you’re on. I think at Microsoftwaret you’re applying, usually, for two teams and then you talk to a hiring manager on an as needed, on an as needed basis. And so if you end up talking with a hiring manager that’s a really good sign. And like, I don’t know how up-to-date these company profiles are, but…

I can to Microsoft a little bit.

Okay.

Yeah, so I think, and I checked I can publicly share this, there’s actually a couple of blog posts and news articles out about it, and the “it” here is Microsoft’s new job interview format for software engineers and other roles, as well. As a caveat, I actually did not interview under the new format. I interviewed under the old format. The new format is unlike traditional software engineering interviews. It’s designed to be a little more focused on project-based problems. So, for example, like in the old interview format, similar to other tech companies, you would end up doing stuff similar to what is, like, in the Cracking the Coding Interview book where it’s like you’re solving different exercises and they’re all kind of, like, disconnected from each other and they test different things and there’s not really a cohesive story behind each of the questions.

With this new format, it's more like you get one kind of general theme or thing that you're going to be working through in each of your interviews and then there's also experimenting with different things. Should, I think one of them is you get some information about what you're going to be asked about before you come to the interview. So you like, have time to research-

Hmm.

And, like, prep and stuff like that. So yeah, this is the new format. I think I'm supposed to do a training on it at some point so I can learn how to do this interview format but I know a lot of people talk about how there's, kind of, problems with these traditional Tech interview formats and so this is, like, an example of a big tech company realizing that and starting to change the way that they do interview. You know, I interviewed with Microsoft in December of 2018 and I was doing it under the old format so I'm not sure what the timeline is for rolling it out for people-

Okay.

But I can speak to the old format because I think that's probably the one that's, like, most similar to how Google and Apple and all those big fancy companies do things.

(laughing)

And my interview process was in two phases which I think isn't the case for most people. There is a phone interview phase and then there was an in-person interview phase and on the phone interview I was speaking with two different engineers solving a technical problem and it was, like, on, like, an online code pad and I was required to produce code that would compile and run.

Oh, Okay.

Yeah. So this is saying, when we were like on the coder pad like the virtual online code editor where you can, like, collaborate with each other.

Yeah, that's interesting because I've heard that Google uses Google Documents.

Hmm.

Type it in there and it's not going to compile if you're writing in a Google Documents.

(laughs)

Oh,interesting.

Google Docs.

So, yeah. I guess that is something that can depend. I know in other companies that I've interviewed at that were also, like, bigger-type companies it was like a portion where I was on an online code editor and it did have to compile and run. And then-

Mm-hmm (affirmative).

Once I got past the phone interview, it was the on-site which was like 6? 5? 4? I blurred this all out of my memory because it was a terrifying experience.

Yeah I think the book says 4 to 5.

Yeah, it was 4 to 5 and it's basically like, back-to-back the whole day. So, like, you start at 9:00 and you end at, like, 4:00 and it's about an hour per interviewer and it's a whiteboard-style interview questions. So you get, like, they ask you the interview question and then you work through it on the whiteboard.

I mentioned earlier the principles I follow which were like, you know, ask questions to set the scenario. I usually like to do this by kind of making it a little bit test-driven. So what I'll do is they'll give me the problem statement like “write a function that prints out the number of letters in a word. And so what I'll do is I'll, like, write a couple of test cases for it so I’ll like, you know write the word cat and say my function is going to return three and then I'll start to, like-

Yeah.

Explore edge cases. I'll be like should my function handle nulls? Should my function handle empty strings? What if the word is so long that it's got like, you know, whatever the maximum integer is on your machine and like-

Right.

Like establishing those test cases and then I write the brute force.

And are you asking them what it should do in the case of null and empty string?

Yeah. I’ll, like, ask like, “Should I-”, I’ll be like, “Should I care about these kinds of edge cases just so it shows I'm thinking about it and then usually that'll, like, get into more scenarios. I remember distinctly the things that I got caught up on with my interview was when I didn't consider edge cases until I was, like, well into having written a solution and then I realized I forgot an edge case and I had to, like, keep rewriting.

Yeah and and speaking about rewriting. How do you manage your space on the whiteboard?

So I will, I think the way I did it was, like, I split up the far left of the whiteboard for my test cases and then I, kind of like, planned ahead of time what kind of functions I would need. So I started by creating, like, my main function, like, immediately next to my test cases and I then left room for, like, helper functions and things I needed to add on to the right of the white board.

Okay.

And to be honest, it definitely got a little bit messy. Like, I was like, you know drawing arrows and like, “Add this here because I forgot it” and all that kind of stuff.

(chuckles)

But yeah, I think it ended up looking fairly clean. I did do a lot of, like, erasing and rewriting and stuff like that and I I got the job. So I ob-,that obviously wasn't a bad thing that I was like erasing and rewriting my solution as I was going along

One good tip that the book gives is to bring your own whiteboard markers and bring the fine tip whiteboard markers.

Mmm.

markers. Oh, that's a good tip.

A good tip.

Yeah, because a lot of times they don't have good markers that have ink in them. Like, they can actually write on the whiteboard and if they do they're the fat ones and so it's hard to write a lot of code.

That is a really good tip.

I've done that before and they were, you know, I definitely needed them. It's good to have the fine tip and then they were impressed that I thought of that.

That’s true.

Anything that can make you stand out a bit, right? Like, stand out in a good way.

Yeah, it shows you're prepared.

Yeah.

Also, your example of walking through the edge cases is definitely one of those side qualities that you get is, or that I would think interviewers are looking for in you is not can you solve the problem immediately, but are you thinking through the problem case in general? Because I mean, that's what we do as developers. Like, every program that we work within has some sort of bounds associated with it and so knowing those constraints is really important to the decisions we make in the software we write.

Yeah, definitely. Anything you can do that, for example, like Adam was talking about that, like, bringing your own whiteboard markers or exploring edge cases that shows you’re, like, thoughtful, is really good.

On the topic of thoughtfulness, one thing that I think is really important, and I have not done this but I have shadowed interview sessions where I've seen other people do this, and it's, like, being kind of, like, rude or snipey when you get corrected or when someone points out something that you didn't consider. So, like, for me, I was talking about how, you know, there were, like, edge cases I didn't consider. When the interviewer pointed that out to me I was like, “Oh, thank you for letting me know that. Here's how I think I can rework it.”

And I was in a situation or I was a shadowing an interview once where someone, like, the main interviewer had pointed out that they had, like, missed something and the person was just like, I don't, maybe I'm reading into it but they were just like, “Oh, yeah, of course. Whatever.” You know? They were like a little dismissive of it.

Hmm.

And I thought that was kind of, you know, not the best quality for someone to howcase when they're interviewing. so, you know, like, be courteous and respectable to the interviewer, which is a basic thing, maybe but...

Yeah, ‘cause they're looking for a culture fit as well.

Yeah.

And you want to look at you want to look at what the company values.

Yeah, that is a great point.

And align to that.

So I do have a flip story on that note of a personal interview that I got in and it was with a company that I had gotten through a phone interview with them and they actually flew me out to them to go and do an in-person and while I was there I was put on a machine to code a specific problem for an hour to debug, like, why some Windows application wasn't working; and it turned out to be the reason it wasn't working was related to threading and after writing it and figuring out a solution, was interviewed by a person who reviewed my code and there was a case where, like, I chose not to use a lock when dealing with a specific spot in it in it and this interviewer questioned me as to, like, why I didn't use it and I explained to them that it, in that particular case, it didn't matter. That it was okay to alter that structure and that case and he pushed back on me to say no and we wound up, kind of, getting in a pretty heated debate about it like near argument.

And at that point I had had the thought that I tanked this interview and not too long after I had one interview between but somebody came in and they were like,” I don't know what you said to this guy but he loves you like he thinks you're great.”

(laughs)

And so I was, kind of, uh, kind of surprised at that point and maybe it's because I stood my ground a bit and he was just of that type but that was actually one case where I was pretty stern back with him and it worked out because they did wind up making an offer. So yeah.

Yeah, that is interesting. I guess you definitely kind of have to, like, suss out the situation and play it by ear. I think, definitely, if you do feel like the interviewer is, you know, bringing up a point that isn't completely valid I agree that you should definitely bring it up in, of course, in a way that's, like, courteous and, you know, it's a good way to show that you, like, have your own opinions and you're not just gonna like go with what the person in power is going to say if that makes any sense. So yeah, that's a good story to

Definitely, that that makes sense having been an interviewer of other people, too. That's that's one thing I will look for in somebody is for them to take an opinion on something. I mean,whether or not it's right, I mean, there are so many things in development that append but if you say you are really good at something or that, you know something well then, like, you should have some form of opinion on it, like, whether it's good or bad or something is better and not just being loose about about everything that's discussed.

Yeah, that's a good point.

So one of my favorite parts of this book is in Chapter Four talking about before the interview. It talks about getting the right experience, writing a resume, and then has a preparation map which is this two-page flowchart about how to prepare for an interview starting out a year or more in advance all the way up to the day of the interview and after the interview, and I say it's a flowchart but really it it's completely linear. And you don't have to start at the beginning.Yo u just start it, however far out the interview is, you start at that point.

It stresses me out that it's like a year before. (laughs)

What do you do a year before?

I mean, one plus years before, build projects outside of school and work.

Oh.

Learn multiple programming language, languages. Expand your network. Build a website, portfolio, take internships. Things like that.

You were nailing all those things, Safia.

What? I've done all those things?

Yeah, like between doing outside work, having public-facing stuff on a blog, like-

Starting your own startup.

Unknowingly, you were you were following the flow chart.

Yeah. I, well, although I guess not intentionally, but yeah, I can see how that is, like, I guess you're just, like, I guess in life in general and your career, you're just always pretend that you're going to be going for a big job interview and act like it. Like, now even though I have this job at Microsoft, not that that's like a big deal or whatever, but I mean, I guess it is a big deal. I shouldn't, like, downplay that achievement.

But I guess what I'm trying to say is even though I have the role, I'm still trying to, you know, keep blogging, keep still contributing to open source, still doing all of the stuff that I love and care about and then I also think it's, like, important that, like, the stuff that shows that I'm growing and developing as an engineer isn't just, like, within the walls of Microsoft, and that there is, like, evidence of my skill set and my abilities that is out in open source and blog posts, now in GitHub all over the place so that, you know, I have proof that I know what I'm doing for any other future opportunities I might have.

Yeah.

Even for your current company at Microsoft, I mean, I'm sure one of the influences on them making the hiring decision of you is the work that you had done in the past. And so I would assume that they wouldn't want that to stop because not only does it look good for you but it also does reflect well on them saying these are the types of brilliant people that were hiring here at

Yeah for sure.

Okay. Yeah, and one of the things that it says to do about four weeks out is to create an interview prep grid. So in Chapter Four it talks about the interview prep grid. Chapter Four is about behavioral questions rather than the technical questions. And so the prep grid is common question and then you… on the columns are three different projects you've worked on. So for each of those projects answer these questions: challenges you had, mistakes and failures, what you enjoyed, some sort of leadership, conflicts and what you would do differently.

That's a good list.

Yeah.

So yeah, I've done that. It's really good to have that in your back pocket. I mean not literally have a cheat sheet in your back pocket-

(laughs)

(laughs)

But to have those things in your mind and you can review that before you go in for your interview because they're going to ask you, “What's an example of a time you showed leadership?” Or, “What's an example of a time you overcame a challenge?” And you'll be able to answer those things.

Yep.

Especially things you as an individual did as well and not just, “My team did this”, but thinking-

Yes.

About your specific role.

Yeah, it does say to watch out for saying “we” too much because they want to know what you've done.

Huh. Interesting. Yeah. This is… yeah, this is kind of a tangent or footnote, but that's something-

(laughs)

That I definitely struggle with, just in general because I have a tendency to, like, maybe more so than others give credit to the support and, like, the, like, other people involved in something even if I did, like, a majority of the work, I'll still be all like, “We, the team, did this.” And I think that's, like, a good quality in many cases but sometimes I definitely do wonder if, you know, I'm interviewing or in situations where I have to showcase my particular skill set achievements if by like being too team-focused I'm kind of hurting myself-

Hmm.

By not, you know, being a little selfish about it in a good way.

Yeah, and then it kind of talks about how to answer these kinds of questions, like, a structured way to answer it. So first you give a little nugget and you say I'll tell you about a time where this happened. It was a little a little tldr and then you give the situation and then you give the action steps you took and then you give the result.

I like that roadmap.

Yeah, I think a lot of people tend to, kind of, their answers, kind of, meandering and you're trying to understand what the point of it, the story, is.

That is one thing that I've heard about storytelling in general is to start somewhere in the middle of it that, kind of, pull somebody in you put it in a situation that people can put themselves in, whether it's something they've experienced themselves, but it's not the whole ramp up of it but rather jump into the middle. Like, I was sitting in my car and it was really cold outside and as I walked up to the front door, you know, I go in and everybody looks at me, like, giving that without giving the other bit of it like pulls you in a little bit more than-

Mm-hmm (affirmative).

Like, giving, I don't know about the whole lead in and that maybe wasn't right [inaudible].

Yeah, that's a really boring story but I still want to know what happened.

Right. Like, what is going on because why did everybody look at me? Right?

Yeah. It gives the same advice for the question. So tell me about yourself.

Oh, I hate that question so much

Yeah, it says to start off with your current role, just a headline, and then briefly college and then post-college what your jobs were and then you get back to your current role again, and you can get some more details. And then you can talk about stuff outside of work if you want to. And then I think people miss this part, what you're planning to do now, what you're looking for now.

Mmm. That's a good way to pull in their company as a thing too, saying how you fit this role or this role fits what you're looking for.

And another thing too is not giving too many details but, like, not overwhelming them with too many details. If they ask you a question that's very, you know the answer is going to be very hard to explain and very detailed you can give them a high-level overview and then say, “I can go into more detail if you'd like.”

After that, it just talks about Big-O and that's a really long chapter and then it talks about how to answer technical questions and it's got a flowchart for walking through a problem and how to solve it. There's an acronym called BUD, uh, BUD optimization, which means when you're trying to optimize a problem, B is for bottlenecks, U is unnecessary work and D is duplicated work. So you can think through that.

Oh, I like that?

Hmm.

Where are the bottlenecks? Okay, where am I doing unnecessary work? Is there anything I'm doing twice, or multiple times, that I don't have to? Yeah.

I like that

And then finally it says “Don't give up and show excitement for solving hard problems.”

That's definitely a great thing to do, too. Like, I always try and say when I get the problem like, “Oh that's a really interesting problem.” Or, “Oh, I'm looking forward to solving this.” Just to, like, show that you're not someone who's necessarily like jaded or afraid to take on big problem. So I like that that tip is in there.

Yeah. Yeah, and this reminds me a lot of a technique I heard about overcoming anxiety and, ‘cause interviewing is be very anxiety-driven and a lot of people, when they're anxious, they try to calm down but that's very, like, low-energy and anxiety’s, like, high energy and so it's very hard to do that and instead you can just say, “I'm excited!” And so excitement is positive. It's not a negative one like anxiety. It's positive, but it's also high energy. So it's easier to move from anxiety to excitement.

Nice.

I like that perspective, too.

Yeah.

And I think that's a TED talk. I'll try to find a link to that and then Chapter Eight talks about the offer and beyond. It says to negotiate and ask for, like, a specific number instead of just more.

Yep. That's definitely a solid tip on negotiation.

And then if you can't get more salary, there's other things you can negotiate for, more stock options or different things. More time off, it really depends. And it also says keep interviewing at least once a year to keep your skills sharp.

Mmm. I had not considered that I guess that is a good thing, a good thing to do.

Yeah, if you wait several years until you're really burnt out and you're desperate to get a new job. You may not be in the best position as you would be if you kept interviewing.

Yeah.

(Typewriter Dings)

This episode of BookBytes is sponsored by Pluralsight. Pluralsight is the technology skills platform. You can see where your skills stand, master the latest technologies, and show off your expertise.

They’re currently hiring in Salt Lake City and Boston.

I work at Pluralsight and the engineering culture is amazing. We work in small cross-functional autonomous teams; each team has four to six engineers, a product manager, a ux designer, and a dev-ops engineer that all sit and work together on the same part of the product. And each team is autonomous so they own the discovery, design, development, delivery, and production support of their part of the overall system. We encourage test-driven development and pair programming so that at least two people who have looked at every piece of code that gets committed.

We have a culture of continuous learning. We have book clubs, discussion groups, and Pluralsight was just named the #9 Best Workplace and one of the Best Workplaces for Women by Great Place to Work.

If you want to work here visit Pluralsight.com/Careers/Engineering to learn. That's Pluralsight.com/Careers/Engineering.

And for those of you who would be interested in checking out the product you can direct message @Pluralsight on Twitter and they'll send you a free trial code so you can check it out for yourself.

And thanks to Pluralsight for sponsoring the show.

(Typewriter Dings)

Okay, and then there's the problems. So Jason and I have done some problems that we can talk about.

Yeah.

Jason, and I know you’ve done several so why don't you start with one?

Okay, I will start with one because I guess you sent me a number of them that were on the start of Chapter Seventeen and so I went ahead and did 17-1, 17-2, and 17-3 and I will talk about the first one. Gave me an excuse to go and write some more Rust. I've been slacking on that a little bit, so…

(laughs)

It's nice to bust it out and try out the Rust documentation, which is, like, the documentation generator is so nice.

Oh, really?

Yeah. I will… I will send a link because I went and actually and I documented my flow through this or, like, how it's supposed to work.

So the problem of 17-1 was to add without plus. So the instructions are:”Write a function that adds two numbers. You should not use plus or any other arithmetic operators.” And when that happened I had kind of a few thoughts that went through my mind. One of them was to go and, like, literally do but case matching with numbers because I was like, well, I mean you've only got 0-9, right? And so like the combinations of each one of those things you technically could go and, like, treat those things as strings or something or potentially modding them and to go and get just like one digit at a time from each number.

I don’t know. Modulus is probably an arithmetic operator.

That, that's what, like, I don't, yeah. I don't know if it's considered one or not. But either way.

You could ask your interviewer.

(chuckles)

Yeah. Yeah. That is a question. Like, what is an arithmetic operator? Because I mean even the route that I actually went with could be considered arithmetic and that depends on your perspective of things. So I decided that another approach to use was bitwise operators. And-

Mm-hmm (affirmative).

I don't know if bitwise operators are actually arithmetic or not but because you are combining digits together in base 2... so it may or may not be legal. I'm not sure but I did go and find that it has been recommended in other places, as it’s the approach to take.

So say you want wanted to go and add some numbers like 3 and 1 together. Then I guess you wind up getting the binary representation of each one. Uh, for 3 is 0011 for the number 3 because you've got the last two bits turned on; and then-

Yeah.

For 1, 0001. And there are two things that you need to know about those numbers, is first you need to add them together without carrying and so a way that you can do that is you need to find a case where two of them, like, when you “add” them, add inside of quotes, if both of them are 1 then you get 0 because you're going to carry to the next position if you think you're adding in base 2. And if two of them are 0 you also get 0 but if one of them is 1 and the other one is 0 then you, in that case, it should be 1. If that makes sense. And so that is actually what matches the truth table for the XOR operator. So, like, that carrot.

And so if you were to go and XOR both of those 0011 and 0001 then you wind up getting 0010 because the last bit gets flipped to a zero because they both end in one.

Okay.

Yeah. Yeah. So this is, like, whiteboard interview leveling up because I don't even have a whiteboard to share with you.

(laughs)

Right?

And so you have that and you've kind of added them but you haven't done any carrying and so if you want to do the carry, then what you need to find is the case where both bits in a given position are 1, and so in that case the & operator so single ampersand will get you what, that desired behavior.

And so if you “&” them together then what you wind up getting is 0001 because they both have their first bit turn on both have it as 1 and so you get 1 out of it, and then since you need to carry it you do a left shift by one position. So you you move that 1 one to the left getting you-

Oh, nice.

Yeah, getting you 0010 and then, in that case, now what you have is your uncarried adding which is 0010 and your carry which is 0010 and then you repeat the operation again, you add those things. And eventually you wind up in a case where you don't have any more carries and that ultimately gets you your end of 0100.

So did you repeat that iteratively or recursively?

I did it iteratively that was the way that it seemed clearest to me to approach. And I can go ahead and share the source code or pass over a link to you so you can see what it was.

Yeah, nice. So what I like about that is that you had to think about something that's on the surface simple, addition, and then think about how that actually works. So you talked a lot about carrying and you recognize that those are two separate steps and you made a truth table like a binary truth table. You're like, “What, what if we did this in binary and then made a truth table and then figure out what operation that was.”

Yeah, that was, I guess, binary operators are not something that I've had to, like, generally deal with that much but in that particular case, yeah, just thinking about the truth tables was the route that I went to go and figure out which operators. What took me probably a bit of time (laughs) was the the left shift, was thinking about that because that, even less so, is something that I've dealt with. I've done the binary operators to deal with, like, flags-type enumerations and something like C sharp to go and combine them together but doing shifts are not a common choice of mine like not something I generally reach for but-

Yeah.

In this case did just what I needed.

Nice. So I worked on 16-22. So 7-, Chapter Seventeen is the hard problems and Sixteen is the moderate problems and it's called Langton’s Ant. The problem is that you have an ant, I just picked this one because it sounded fun, you have, like, a little ant moving around. An ant is sitting in on an infinite grid of black and white squares. Initially the grid is all white and the ant faces to the right and then at each step it does the following: So if it's a white square you flip the color of the square it's currently on, the ant turns 90 degrees to the right, or clockwise, and it moves forward one unit. And a black square you flip it, you flip the colored square, it turns to the left instead of to the right and then it moves forward one.

So you have to write a program called print K moves that takes in the number of moves the ant goes and then you just print out the final board after that many moves. So first I started by drawing out what this looks like at each step because this is pretty deterministic. You know, given 0 the answer is it's all white, given 1 you've got a grid that just has one black square somewhere and so on so forth.

And so I started drawing it out and trying to see if I could recognize a pattern because it sounds like some sort of pattern is going to emerge where you can easily just not have to go through every single step to calculate this grid, but I realized I didn't really see one and probably the best way to do it is just to go through the steps, but then the problem becomes it's an infinite grid and so how do you store that? What data structure do you need to be able to hold an infinite grid and then be able to print that out at the end?

And, you know, one naive approach is just to have a two dimensional array that is, you know it's going to be big enough. And so I thought, “Well if the ant is moving K, it can move K in one direction, not actually because it's going to turn based on these rules, but at most it can move K in one direction so you could be K times 1 or it could be K divided by 2 in one direction and K divided by 2 in the other.”

And so that's actually the approach I went with is, “Hey, let's just initialize an array” and this may be huge if K is big so it's probably not the best approach but to, just to get some code down, I just started off with that grid and then just run through the steps. I just keep track of the entire grid and then I keep track of the position of the ant in which direction it's facing and then every time it moves just change the grid and then at the end, I just have a function that takes that 2D array and prints it out. And it just it just prints out a string that has like zeros and ones.

So I just looked at the solution and it talks about every time... so one of the problems is if you start off with a small array and then you need to expand it you're expanding in two directions, first of all, and one of the problems is if it goes in the negative direction. So I considered using some other data structures where negatives aren't a problem. Like, maybe just a hashmap, but then the problem is being able to print it out based on that.

Mm-hmm (affirmative).

So it says what you can do is just double the array if it goes off in one direction and if it goes in the negative direction double the array and then shift the entire grid towards the positive. So that's that's kind of one space-saving optimization that I didn't do. So I guess my solution is more it optimizes time, but not space. I don't know, what do y'all think?

I like the consideration of space concerns within it because that is actually something that we deal with in general in computers and we talked about, in the past, the Turing Machine which is theoretically designed for an infinite amount of tape and we obviously don't have infinite amount of memory on the machines that we use today; and so in order to deal with those bounds we work within a set of things that we’re likely to be able to handle and then if it goes outside of that then, I mean, we throw out of memory exceptions or do-

Yeah.

Other things and so I liked your approach of dealing with it by using K is as a way to determine how much memory to go in and pull.

Yeah, really what I wanted to do is create a hashmap where the key is, well not a hashmap just like a dictionary, where the key is the X like a string of X,Y and then that way you can go into the negative and it's not a problem and you just add it… you just add it into the dictionary when it turns black and when it turns white either remove it or change it to false. And then to print it out, you would have to iterate through there and generate all of the black squares onto the grid but you’d also need to know how big that grid is before you start trying to make it.

So I thought about you might have to keep track of Min x max X Min Y and Max y as you were going through and putting things in the dictionary and then that way when you go to generate the grid, you know how big it needs to be, iterate through the dictionary, and then just change some zeros to ones.

That is an interesting approach. It gets you an, by using a map like that then you get more of a sparse matrix would be what would be similar to. So if you think, like, a matrix, like, math matrix where you have, like, a grid of numbers, I mean, in your case like 0 and 1 then a sparse matrix is one where it's generally, like, most of the positions are 0 because, I mean, in this case, very likely most of your positions are going to be 0 or, like, they're going to be a white spot and so to hold something that doesn't have to represent all of those zeros is a definitely more memory efficient approach to it. And so-

Nice.

Yeah, I think, I think using the hashmap approach could be, like, sounds pretty reasonable to me for efficiently storing that and then tracking your bounds for a means of printing makes sense.

Yeah. So I know you have two more questions, but we're about out of time. I think what would be cool to do is talk about those remaining two questions in a bonus episode. If people are interested they can listen to it; otherwise, they can just skip it and we can talk about any wrap up thoughts, any closing thoughts right now.

I feel like I want to go and buy this book now.

Yeah, I mean, it's really useful. It's one that I keep going back to over and over. I mean 189 problems is a lot. I don't know if I'd ever go through all of them, but it's definitely a challenge.

Yeah, definitely something to go and get you in that mindset of practicing those types of problems that are pretty common in industry. And, I mean, also it made me kind of excited of the fact that you just gave me a couple of problems, Adam, because I will be honest, I have had a time, at least once, where I have moved forward in a coding interview not because I was excited about the company but just because they had a really cool coding problem and I wanted to see-

Yeah.

If I could solve it in the time frame.

Wait, so I just got a message from Safia here. Did you end up working on a problem?

Yeah, so I was terrible. I had chosen a problem to work on, like, a couple days ago and I’ve just been so busy with life that I didn't get a chance to do it. So while Adam and Jason were talking through their problems. I popped up a jupyter notebook and started working on my problem.

I thought you went a little quiet.

Yeah, I muted myself when I started-

(laughs)

Tinkering out a little bit because I felt bad that I didn't get it. I chance-

(laughs)

To work on it.

Like we said before we started recording, your homework was getting an actual job at Microsoft.

(laughs) Yeah. I was joking with them earlier. I think I'm all interviewed out for the next couple of months, so… But yeah, I can talk a little bit of mine. I know we're out of time so I don't have to cover it, but similar to, like, what I've been discussing, my problem was called the Count of 2s so you have to write a function that would return the number of the digit 2 that would appear from 0 to n inclusive. And so, like I said, similar to what I was saying before, I started by doing, like, just, like, the naive solution which was, for me, I wrote a for-loop that converted a number to a string and that I use the count function in Python to count the number of times that 2 appeared in that string and I summed that total up. Super naive, it did the job.

I tested it with something and it gave me what I expected and then from then on I didn’t get a chance to finish it, but where my head was going was starting to think a little bit about, like, extracting each of the digits within a number and then seeing what would happen if you were to divide that position by 2. So, like, if you have the number 25, pull out the 20 and pull out the 5, you can divide the 20 by 20 with no remainder. So that tells you that there's a count of 2 in the tens place and then you'd kind of do the same thing for each of the digits.

And I was starting to think that you could, like, do an iterative implementation to start but then maybe do a recursive implementation and that would reduce the amount of code that you had. But yeah, my head started off with like,”Oh, just, like, convert it to a string and use some native Python functions to do it.” Then I was like, “Alright, can you get away with not doing string conversion and kind of just use the positions of the numbers and then Macgyver it that way.”

Apparently this is what gets you a job at Microsoft. Is this kind of thinking so… (laughs)

Yeah, talking through you your approach to solving it, it makes a lot of sense to, I mean, build it once, like, proof your proof of concept sort of thing and iteratively improve it from there.

Yeah, you don't have to be perfect the first time around, for sure.

It almost seems like one that there could even be, like, a mathematical approach to it based on the number of digits that are in the number; or, like, to what power of ten that it’s at to get you something pretty close.

Oh, like, just some sort of, like, function that you could use that would approximate the number of 2s? Okay.

Right. Yeah, just by, like, the number of digits that are actually in the number, being able to use that. Like, I mean, if you are doing it like through 100, like, then you would wind up having a 2 in each of those places except for 22. So, I mean you'd wind up with 11 of them and then I guess that's also-

Yeah.

Taking in the twenties as well. So I'm thinking through it on the fly but something on that route where you could potentially do it in a, like, constant time.

All right. Yeah. I'm glad you were able to come up with a solution to a problem on the fly.

Yeah, sorry for going, going silent and just, just shuffling away.

Yeah, but I don't know, it makes me want to go and take a look at it

Awesome. Yeah.

So thank you so much for listening and please follow us on Twitter @BookBytesFMand you can follow each of us on Twitter as well. And if you haven't already, leave a review on iTunes. We love hearing what everyone thinks of the show, how we can improve, and if you want to suggest what books to read we've got our GitHub repo where you can put in an issue for the for a book and you can even give it a thumbs up and it will float to the top. I don't know have y'all seen that I don't know if I even told y'all

I don't think you have.

I will have to take a look at that.

Yeah, and I'll see you all next time.

All right. Bye everyone.

See ya!

Bye.

(Exit music: Electro swing)