Learn how to answer common technical interview questions with Haskell. Cameron Gera and Taylor Fausak discuss Chris Penner’s blog post.
Episode 27 was published on 2020-10-19.
Hello and welcome to the Haskell Weekly podcast. I'm your host, Taylor Fausak. I'm the lead engineer at ITProTV, which is an e-learning platform for IT professionals with me today is one of the engineers on my team. Cameron Gera. Welcome Cam. Hey, man, how's it going? It's going good. Thanks for being on the show today. Of course, man.
>> Well, you know, it's still October. We've been doing this podcast again for three weeks, and we're still in October. Which means we are still in Hacktoberfest, which is an awesome opportunity for us to contribute to the open source world and really just make a difference in these projects that may not have as much dev time going into them. So for us, it gives us a chance to learn as well as contribute to these projects. Um, so one awesome project is learn for Haskell, which is put on by Kowainik. And it's an opportunity for people to be a part of Hacktoberfest and also learn haskell at the same time. So if you're interested, go check it out at learn for Haskell. I think you can Google that, um you can also check it out on Kowainik's site. I believe they have some links as well, but it's a good opportunity for us to, you know, contribute learn for Haskell and get a free T shirt. So, you know, we all love free T shirts around here.
>> Sure do. I'm wearing a free T shirt right now, and it feels great.
>> Yeah, I guess I am. I'm wearing work t shirt, which is free to me. So that's always nice. Yeah, awesome. Well, Taylor, what are we talking about today?
>> Today we are talking about a blog post by Chris Penner called Silly Job interview Questions in Haskell If you haven't heard of him before. Chris Penner is the author of a book called Optics by example where he does a deep dive on optics and lenses and Haskell how to use them. How to get familiar with them.
>> Yeah, so, you know, he kind of talks about, you know, the interview questions that are part of the interview process and in the interview process. If you're looking for any kind of job, um, you know, and a tech job in particular, you're gonna generally have kind of, ah, general interview kind of understanding who you are. You'll have a culture fit interview with kind of the team you're gonna be a part of. And then you'll also have a technical interview where you can kind of get asked and challenged in various ways in the various programming language you may be in contact with in that job role. Um, and so for a lot of Haskell jobs, you're gonna come across some of these Haskell problems and be able to solve them quickly If you kind of reviewed this blog post. And, you know, I think he does a great job here of, you know, kind of giving us the general idea behind why he made the decisions he made. And as well as like a good variety of the questions that you could be asked and yeah, just just to jump in the first one was the palindrome, which, in Haskell I mean, can't get any easier than that, right Taylor?
>> you sure can't. This is this is so easy because all the functions you need are in the prelude, and you don't have to string too many of them together to get an answer. But I was gonna ask you, Cam, what's your favorite palindrome?
>> Probably race car, which is, you know, kind of the only one I can think of at the moment. But it's in the also in the blog post, so you know, it's a little bit a cop out, but I would say race car's a good one for me. What about you?
>> I like Taco Cat. It's also short to the point. I know there are some extremely long palindromes, but yeah, that's that's besides the point. Um, so Chris shows a solution for the palindrome question here, which I guess if you're not familiar with the Palindrome, it's something that has the same order of letters, forwards and backwards. So like racecar as an example r a c e c a r. That goes the same forwards and backwards. So the way that he, uh, solves this problem is by comparing the original string with the reversed version of the string. And if they're equal, then it's the same forwards and backwards Super easy.
>> Yep. Yep. I think that was Ah. Ah, great solution. Very straight to the point. Um, and you know, it's not bad when you could get one line of code solve, you know, quote unquote. The technical interview,
>> Yeah, especially if you're answering this on like a white board. You know, if your handwriting's really bad, this one's an easy one to knock out.
>> Yeah, and I think it does provide for a good ability to explain it to right. Uh, that's kind of the point of these technical interviews that you'll be coming across, and for those who have come across it, you already know it's just about kind of getting your verbal processing out and allowing you know, the team that you're gonna be joining to kind of hear and understand and see how you solve a problem. So he kind of talks and starts with, you know, the easy one of the palindrome on, and then it kind of takes another step forward, right? What's the next one that he talks about?
>> The next question is fizz buzz, and I'm sure a lot of people are already nodding along because they're familiar with this one. But if you haven't haven't heard of it before, the question is where the problem is to print out the first 100 numbers, so one through 100. But if the number is divisible by three, you print out the string fizz, and if it's divisible by five, you print out buzz. And if it's divisible by both you print out fizz buzz. So pretty simple problem. But a surprising number of candidates can't answer this one. So it's good to see a Haskell solution here.
>> Yeah, it definitely like when you hear the explanation. It kind of can make you squirm a little bit. But if you really listen to the problem, what it's asking, it's not too bad. And you just gotta, I think with every big problem you got to solve or any problem you have to solve, you know, you just gotta take one step at a time, you know, figure out all right, what do I need to do first? And then you can build on that, And I think Haskell kind of allows you to do that pretty well for his solution. He actually takes some time to use guards, which, if you aren't familiar with guards, you know, they're kind of a, you know, in line pattern matching per se, um, and that allow you to, you know, do some comparison check. And, you know, if it equals true, then you you go proceed to that line of code. Um, and so here he kind of, you know, goes one step at a time with, you know, some sort of secondary function that he's gonna iterate over. You know, this list of 1 to 100 with that? He does, you know, a check of, you know, the number of mod three. And number five. If those both equals zero, then he prints out fizz buzz. If not, you know, he goes the next case, which the next case, he's doing the mod three check. So if mod three of that number equals zero, then it's gonna print out fizz. Same with five when he's gonna print out buzz. So you know, he's got these cases that if they evaluated, true that, that's what is returned. If not, none of those cases returned. True, he's just gonna print out that number. And so it's pretty straightforward. Um, one interesting thing, though Taylor is that he decided to use for underscore from data dot foldable. Where? For me? I would have probably used just map out of Prelude. Um, that doesn't you know, it's pretty much the same as for underscore, but with reversed arguments, right?
>> Yeah, In fact, for is defined as flip map. So the fact that he reached for for here suggests to me that he's trying to reach out to an audience that may not be familiar with Haskell to write code that looks a little more imperative, even though, really, behind the scenes. It's still that functional goodness that we we all know and love, Um, and a quick note on what you were talking about with the guards. One of things that's really great about them is they match top to bottom. So, like you were saying, you can process these and you add the cases as you go by and you can think, Okay, I'll start with mod three and then mod five oh wait. I forgot about mod three and five, So I'll go put that one at the top. So it's just like an if else chain in a regular imperative programming language.
>> Yep. And I think a lot of these functions, you know, as we continue to talk about them, you know, would be good for people to kind of go and reason about yourself and try to solve it. Uh, maybe even before reading this blog post to just kind of see if you can solve it. Obviously, we're talking about it here. So you have a general idea of maybe what? To do, But it could be good to kind of just put that into practice, Um, and just kind of create that quick little solution, um, that you can kind of just have in your back pocket. So he then moves on, obviously to, um, something else, Something else. Even more complicated. And he it's called sum up to N numbers, which when I first passed over it, I was like, Okay, like, I get that. I wasn't sure how he reasoned about, You know, obviously, I have to read the full question. That's part of solving these problems. You know, you have to read the full question. Um, after my second pass, I realized, you know, it's always just a combination of three letters or no letters. Numbers. I mean, numbers, right. And that is I was like, OK, cool. I'm gonna be taking a list of numbers and trying to find combinations of three numbers that equal some total, some specific total. Um, And so you know, if I'm gonna kind of attack this problem before we move on to the solution like I'm gonna think. Okay, I've got a list of numbers and I need to find all the combinations of all combinations of these numbers that include three, right. So I need to chunk them into groups of three and every combination of that. And so that's kind of what I would attack first, Which I think he actually ended up tackling as Well, on, then I would have come back and, you know, tried to iterate over that new list of lists and find, you know, find the sum of each list and see if it equals the total which actually ends up being what he he does. So it sounds like I'm just copping out here and, you know, using his solution. But when I first read the problem, I didn't look at the solution, and that's kind of my process, uh, that I was would have proceeded with, but obviously he has a solution right there. So I just kept reading. And there it was.
>> Yeah, that's a good solution to this problem because you're breaking it down into components, and I think that's starting with the more complicated component. Namely, coming up with the combinations of the elements of the input list is a good way to go because the second part of figuring out if a list sums to some particular number and then including or excluding it based on that is pretty easy. So, you know, once you've got that nice head of steam built up from doing this hard combination stuff, then you finish it off with a nice and easy dessert of just figuring out if these add up to the right thing.
>> Yeah, an interesting thing. And, you know, Haskell is there is something called permutations, um, a function called permutations that will take a list and give you all of its permutations. But that's not quite the combinations. And, you know, if you look in Hackage or Hoogle for combinations, you're probably not gonna find one in, you know, a standard library. You may find one in some specialized package, but you know there's not going to generally be an easy combinations function you could reach for. And so he takes the time here and kind of explains and how he would have created a combinations function. Uh, you know, obviously, recursion is a big thing, you know, functions calling themselves until they find the solution and then returning that solution. It was nice to see all these. You know, this solution. He has very good comments and stuff like that. Uh, but could you kind of explain a little bit more on, like, what's happening in this combinations function?
>> Sure. So this whole problem is quite a bit more complicated than the fizz buzz one and the combinations. Part of it, like I mentioned earlier, is definitely the more complicated sub problem. But when you break it down into the three kind of base cases you have to cover, it turns out to be surprisingly simple. So the combinations function as he's given it gives you, or it takes a number as of like, how many things to include per group. And then it takes your input list with all of the things in it, and you output a list of lists. So a list of combinations of things. And, as is typical with implementing recursive functions, you start with the base case. So the base cases you're asking for zero things. There's exactly one way to give you zero things. So you return a list with the empty list as it's only element, and then we'll gloss over the recursive call for right now. But the other base case is where you're asking for a combination of some number of things. But your input list is empty, and in that case you cannot provide any combinations. So you return the empty list. So with those two base cases under our belt it's pretty easy then, to go on to the, um, recursive step where what you're doing is grabbing one element off the front of that list and consing it. So like making it the first element of, uh, the recursive call onto the rest of the list for one less element. So let's say you're looking at two a list of two elements, and you grab the first one and then for every other element, in the list you or every other combination of the list. Rather, you add that element onto the front, um, and then in addition to that, you do another recursive call. So this combinations function every step. It calls itself twice. So it's very recursive. Um, yeah, it's It's a little difficult to just explain without looking at the code. But again, with recursive functions, it's important to focus on those base cases. And then, uh, the recursive step will hopefully be clearer because you want to get to those base cases.
>> Nice. Awesome. Well, I appreciate you taking that time. Yeah. Like like you said, it's a little hard to explain code that's written because, you know, it's a little easier just to see it and kind of process that way. But, you know, a classic thing that happens in these technical interviews is they say Okay, well, now this part's gonna change and, you know, say, for this function, we want all combinations of any length which sum to the target number, you know? What are you going to do there? What? What's gonna have to change in our current implementation to make this work right? I mean, we're in Haskell. So is there something fun and easy and quick we can do to make this work?
>> I don't know. If it were me, I would probably be scrambling in the interview. And I would just say, Take the length of the input list and call combinations for each zero up to that length. And then, boom, you've got all the combinations. Did you have something else in mind? No, that's perfect, because that's the answer. Alright. I passed
>> nice threw that one threw that one at you, man. You weren't quite ready for it. But, you know, I think you figured you could handle it. You're pretty. light on your feet.
>> I think we've got a good handle on that question. Should we move on to the next one?
>> I'd say so. Yeah. Why not? So we've got check if two strings are anagrams. Aww, anagrams.
>> And what is an anagram? I
>> don't know. What's an anagram? Actually, I believe it's two words that have the same letters. Am I right. Or am I right?
>> I think you're right. But there's additional wrinkle there where they have to have the same number of the same letters. So, like, you know, if it has two 'S's in it, you gotta have two 'S's you can't just have an 'S'
>> see Okay. Yeah, that that definitely is a little bit of a wrinkle. But yet again, Haskell comes to the rescue. In my opinion, I think it's, ah, quite a pleasant solution. They're here. They're here that he created that actually ended up only being two lines of code A type signature and a function definition.
>> Yeah, it's very short. And it's similar to the palindrome question. You know, the first one. Because everything we need Well, we could solve this using just the prelude, but he actually reaches for this nice higher order function that's available from the data dot function module. And the function is called on, and it lets you take a binary function in this case equals and apply it by first applying another function to both arguments and then applying that operator. So in this case, we're calling equals. But before we do that, we wanna call sort on both of our arguments. And why is it that we wanna call sort Cam?
>> Well, because obviously we want to get those letters to be in the same order and then do a comparison of those lists, right? And if those lists are equal we return true. If not, we bail out. And the awesome thing about Haskell, too, is that because it's lazy, as soon as it finds a case where it's no longer equal, these two lists are no longer equal. It bails out, so that saves you a little bit on. You know, the performance issue um and you know this isn't necessarily the most performant code anyone's ever written, but it definitely will solve the problem in a pinch. Um, you know, because obviously, sorting a list isn't the most effective way to well. It's a very effective way to do comparisons of something, something that can be considered a list. But it also has a bigger notation of N log N which it's a little longer than you know some people want to deal with.
>> This is something people often point to as a upside of laziness by default, where you can have a sort function that lazily produces its output and some other function that lazily consumes its input, and the sort function is only going to do as much work as is required to give enough stuff to that other function to use. So in this case, equals is the function that's consuming the output of sort. So if on the very first letter equals says, well, these aren't the same, then we're not an anagram. So I'm just going to stop there. Sort isn't gonna bother sorting the entire rest of the list. Uh, it might, depending on the shape of the input list and everything, but in general, it probably won't. So that that's super nice. You don't have to do any fancy, like early return type stuff or anything like that. It just It just does it.
>> So nice. So nice. Um, well, yeah. Cool. Well, the solution that he kind of links to that was the inspiration for this question. Yeah, some java solution. That was a lot of lines of code. Um, you know, and and, you know, he mentions here. He doesn't know which one's faster. Um, you know, he imagines the Java one's probably faster because of some of the considerations they did, but he didn't benchmark them, so he doesn't really know. Um, so I mean, could be curious to see if lazy Haskell evaluation, you know, allows for the same benchmarks. Um, that he you know, he that would come from this java solution that is mentioned. Um well, cool. Yeah, I think that kind of wraps up anagram problem pretty, pretty cleanly and allows us to, you know, know how to do some quick comparisons. Um, you know, obviously the reverse. You know, the palindrome is another kind of string comparison, and then that these anagram wants to string comparison. So, you know, these things in Haskell aren't too difficult to deal with because of, you know, the built in functionality, the laziness, the, uh, just general ease of composition, even, you know, allows us not to have to have too much boilerplate and, uh, too much code, but yeah, so I think that's cool. Then they have one more that we're gonna quickly talk on. No, we have two more that we were quickly talking. Apologize. Um, we're gonna touch quickly on them. So just not too long. Because I would love for us to kind of get a little work, you know, chat about our experience and maybe some other things you could do to practice, um, Haskell and be able to be prepared for an interview like this. But there's a Min max problem. And then he also talks about the word frequency problem. So, Taylor, would you give us a quick synopsis of one or both of these?
>> I'd be happy to. So the Min and Max problem is given a list of things that can be compared. Return me a tuple with the greatest element in them and the least element in them, or the minimum and the maximum. The immediate solution that comes to mind is the one he goes for first year, which is make a tuple call minimum on one of them and maximum sorry minimum on the input list and maximum on the input list. And that works great, has some downsides. In particular, it will walk over the list twice, once to look for the min and wants to look for the max. And if your input list is empty, it's gonna explode. So he spends some time fixing up some of those issues, which I think is great, and it's worth pointing out that he's able to use fold map here in some of the interim solutions because there's actually monoids for expressing the minimum or maximum element. And so, if you wrap everything up in those you can fold map everything together. If you want to learn more about monoids, go listen to our previous podcast, where we get drunk on monoids. Hmm. And then the other final problem is about word frequency, and this one, like the sum up to N Problem is a little more complicated. There's more moving pieces involved, but fortunately again, Haskell kind of saves us here. It's not in the prelude. It's not in the base library, but it isn't a boot library called containers. And in there there's a data structure for maps. And that's what he reaches for here to take an input list and then build a map where the key is a word in there, and the value is how often it shows up. And this is something that we do so often in, you know, interview code in real code. I'm kind of surprised there's not a function in containers already to do this, not specifically for strings, but just for anything to count up the frequencies. So maybe I'll open a PR. And get some credit toward Hacktoberfest for doing that. Hmm. That could be cool. Yeah, and then, really the only other thing to point out about this word frequency things since we're blazing through it right now. Is that last week we talked about how maps When they union together, they're left biased. So it will just drop the value from the right one. And that's why here he has to use this union with function to say no. Don't just drop one of those values. In fact, combine them together and use addition to combine them together. So we're counting how often this shows up.
>> Yeah, And I looked at this code and I was like, I feel like I've written this for, you know, at some point whether it be in our actual code or, you know, when I personally been practicing my Haskell knowledge, which, you know, um, I think, actually, the great segue into our next kind of topic, which is, you know, some other tools to practice with for us and me personally, I've used, you know, code wars and exercism and advent of code to kind of, you know, solve various problems in Haskell. Uh, the cool thing about these platforms is that you can, you know, choose a language maybe you're more familiar with. There's a lot of languages and these and even advent of code. You can pick whatever language you want. You could do it and then Excel spreadsheet. If you could figure out the logic for that. And you know, I think that's really nice to have because then you know you can reason a reason in a in a way you already understand. And then you can, you know, go to the language you're learning and apply it the knowledge you know there and see how they compare. And, you know, there all the questions there's wide range code wars is what we're using more recently where you know, there's, you know, one to eight kyu with one being the most difficult and eight being, you know, relatively simple. But it allows you to kind of get your feet wet and reason about problems kind of quickly. And then once you've kind of created a solution, even if it might be a may not be perfect. You can submit it and see other people's solutions, and you can kind of see like Okay, yeah, that makes sense. I see where they did this a little bit better and then. You can, you know, edit it, or you can comment on other people's You can up both. There's, you know, say, Oh, yeah, That was really clever. And. People can give you feedback on yours as well. So I think for us, that's been a really good one. Um, but I think Taylor, I would love for you to talk a little bit more about advent of code because I know you've done that for quite a few years now, I get through, like, five days, and I'm like, I can't spend four hours on solving this problem.
>> Advent of code is a ton of fun for those that haven't heard of it before. It is a yearly programming challenge leading up to Christmas, where you get a new problem every day and I forget when exactly they drop. It's something, uh, not very convenient for us here on the east coast of the US It's like midnight UTC or something. So I'm not waking up at 4 a.m. To go to a programming puzzle because they have a leader board where you can compete against everyone else in the world to see who does it the quickest. I'm not really in it for the competition side of it, but it's a good, interesting mix of problems that build on each other so often, even if it's not actually like you use part of the solution for the next solution. They're thematically related, where they use similar concepts for solutions. But there's a very big community around it. And for all of the problems, the solution that you submit is some simple text value, so you can solve it with anything that you want. Like you mentioned Cam. You could do an Excel spreadsheet or with pencil and paper. And this is really nice because it gives you the flexibility to say, Well, maybe I don't know how to solve this in Haskell yet, but I do know how I would solve it in Java or Python or whatever language I used before. So I'm going to do it there and then show that I can come up with the right solution and then figure out how to convert it over or just go look at other people's solutions and try to understand them and see what they're doing. Because maybe I wouldn't have been able to get there myself. Um, but yeah. Advent of code, super fun.
>> You know, I was gonna say, I think I'm gonna start submitting some, uh, Excel spreadsheets as PR's into our code base. So I mean, it solves the problem, right?
>> It does. You can submit those, but be ready for them to be rejected.
>> Okay, that's understandable, but yeah, I think I think those are other tools that we can use to prepare for, you know, thinking quick on our feet because that's kind of what the interview process is all about is alright. I'm thrown an issue. How do I create some resemblance of a solution in a five minute window. And the more you expose yourself to difficult problems and have to reason about difficult things, the quicker you are to find that solution or find a solution that at least solves a problem. Um, I think this week we were talking to one of our other engineer friends, Cody, and he was kind of talking and brought up. This proposition of, like, better is better or worse, is better in the programming world. And, you know, we could spend a lot of time and architect the perfect solution and, you know, be better is better. But if we're not able to get a solution out there and and get something in front of a customer or in front of whoever the stakeholder is like, what are we doing? So kind of worse is sometimes better because it's there, it's usable. They know how to deal with it um and so. Like getting that practice with these, you know, coding challenges and things is gonna help you for different interviews as you progress in your career on move from place to place. Uh, but yeah, you know. And the funny thing is, like, Taylor, you and I have very different work experience. Mine is an intern turned engineer still working for the same place for, you know, almost going on five years now. So that's my experience. I have done some of these interview questions and stuff before, but it was right out of college, which for me, that was really hard to reason about. Like I had data structures. I had, you know, all these courses. But I hadn't had any practice. So for me, it was really difficult to like put those words into actions. Um, but luckily, you know, had opportunities here at ITPro and had actually a couple of other opportunities. And they really value just the ability to verbalize what you're trying to dio. And so I would maybe even suggest that you do various challenges, maybe verbalize and say I'm doing this solution because even if it's just you in your room, I still think that's valuable for you. Moving forward. Yeah,
>> I think that's a good way to get comfortable in that type of scenario, because clearly an interview coding challenge isn't exactly the same as your day job. Normally, you're not in front of a white board or explaining your problem solution as you're working through it. But one interesting way to work on these that I think has become more realistic recently is to stream your solution or maybe not stream it, but pretend like you are where Okay, if I was sitting here and I had my window open and there was a camera on me and I was streaming on YouTube, how would I explain to the people watching what it is that I'm doing and why I'm doing it? Because as someone who has conducted a fair amount of technical interviews. That's ultimately what I'm more interested in rather than can they solve this problem? So if I ask someone, can you solve the fizz buzz problem? And they say, yes, they quickly write it on the on the board. That's good. But I would prefer to hear you know, how they're working through how they're thinking how they like to approach problems.
>> Yeah, I think uh to point back to the article, I think he does a good job explaining of why he did what he did and some kind of as you read through the blog post, you have the ability to kind of see how he reasoned about the problem. Um, you know, and obviously you hear how how we would reason and verbalize it, you know, through the podcast. But yeah, overall, I think this is a great blog blog post, and I really think we had a great time today on this On the on the podcast.
>> Yeah, I sure did. I hope you all had a good time listening uh. I think that will do it for us today. This has been the Haskell Weekly podcast. I'm your host, Taylor Fausak. And with me today was Cameron Gera. If you'd like to learn more about the podcast or our newsletter, please visit our website Haskell weekly dot News Or you can catch us on social Media. Our Twitter handle is Haskell Weekly. We're on Reddit as Haskell Weekly were on Git Hub as Haskell weekly pretty much everywhere we're Haskell weekly. Also, if you could take a minute to go rate and review us on apple podcasts. We currently have a five star rating with 16 ratings. So that's 80 stars that people have given us. And if you want to give us some more, that's great. If you think we suck, let us know and we'll try to get better. You
>> know, Haskell Weekly podcast is brought to you by ITProTV, an e-learning platform for IT professionals and also our employer. But, you know, we would love toe extend an offer if you're interested in an IT content, um, to you with a promo code of Haskell weekly 30. That is Haskell weekly 30 All one word. Um and if you want to check it out. You know? Obviously we have a free membership as well, so come over. ITProTV. You know, it's I t pro dot tv. Easy to find. Easy to see. Um, come check out our great content and keep hanging out. We really love doing this. And we really are thankful that ITPro lets us do this. So it's been a good day, man.
>> Sure has. I'll see you all next week Peace Bye.