Algorithms + Data Structures = Programs - Episode 53: Florida & LeetCode

Episode Date: November 26, 2021

In this episode, Bryce and Conor catch up about Florida before solving an algorithm LeetCode problem.Date Recorded: 2021-11-13 and 2021-11-23Date Released: 2021-11-26Raising Cane’s Chicken FingersChannel 5 News YouTube ChannelLeetCode ProblemC++ std::partitionClojure partitionRust partitionProgramming PearlsThe Art of Computer ProgrammingStructure and Interpretation of Computer ProgrammingQuicksort AlgorithmIntro Song InfoMiss You by Sarah Jansen https://soundcloud.com/sarahjansenmusicCreative Commons — Attribution 3.0 Unported — CC BY 3.0Free Download / Stream: http://bit.ly/l-miss-youMusic promoted by Audio Library https://youtu.be/iYYxnasvfx8

Oh, I should have worn my Hawaiian shirt. Oh, what was I thinking? That would have gotten a laugh out of you. Damn. Mistakes, mistakes, mistakes. I'll put that clip at the beginning of the episode, so, uh... I am wearing my pineapple swim trunks, though. Welcome to ADSP the podcast episode 53 recorded on both November 13th and 23rd 2021. My name is Connor and today with my co host Bryce we catch up and chat about Bryce being in Florida and then dive into solving an algorithm leak code problem. So I was I'm in Florida visiting my parents because they hate the cold weather. My mother went to Cornell for undergrad and University of Chicago for law school, which are two of the colder options for college in the continental United States. I'm sure you as a Canadian are like, yeah, yeah,

that's cute. But after that, she was like, I'm done. I'm going to like move to Florida and go become the first female lawyer and like the first like female lawyer, the first like Jewish lawyer, the first like Northern lawyer at this good old boys law firm, um, in, uh, in Florida. And then she had me down here. And then for some reason she was like, let's try New England again. Um, although she had never actually lived in New England growing up, she grew up in Long Island, but let's try the tri-state area again. So then we moved up to Connecticut. And then I grew up there. And then there was one year, and she married my stepdad,

who lived in Connecticut his whole life. And he's like, I'm never leaving Connecticut. And there was one year where there was this freak blizzard, although these days with climate change, those just happen all the time. But there was this freak blizzard and they lost power for like two weeks. And then my stepdad was like, all right, I am now ready to give Florida a try. And so now my parents live in Florida. And so I was packing to come down and visit them. And I thought I did a reasonable job of packing. Like I didn't bring any more stuff than I needed. I just had a carry-on bag, which is like a new thing for me.

Like a few years ago, I would almost always check luggage. But this time I was just like, I'll just fit it all in a carry-on bag. I don't need to bring every possible Bryce outfit. But then I get here and I'm unpacking and I realize I have two different headsets. The one that I use for recording in telecons and then my noise canceling ones, plus my ear pods, plus the microphone for recording the podcast and the boom filter and i'm like hmm i'm pretty sure that that like a fifth of my luggage was recording equipment what has happened to my life i blame connor i mean you should also blame covid. COVID created all these virtual meetings and whatnot. I should, but am I going to?

You're in Florida right now. Damn. Florida. I've heard about Florida. I would love to be outside and recording so that I could make you feel jealous about the cold city that you're in but uh in the interest of audio quality i am in the most the room that i determined was best um although i do think there's a bit of an echo because they have like very high ceilings but there's nothing really i can do about that and it is inevitable even though i i warned my parents about 10 times i'm recording this

podcast today i need you to not to not come in and disturb me it is inevitable that my mother is going to burst in at some point and see whether i need water or cookies or tea or some other thing this lady is always trying to feed me she's trying to fat to feed me. She's trying to fatten me up, man. She's trying to fatten me up. Isn't that what moms are for? It is. They got to make sure you're, you know. There's something about, yeah, moms.

And even if you're not hungry, you could be hungry shortly. And so we got to make sure that that doesn't happen. She's always planning her next meal, always planning her next meal. What are you doing for Thanksgiving? I'll be working. I mean, I'm in Canada, so the real Thanksgiving already took place in October. That is a pack of lies. I, of course, know that Connor is Canadian and was setting him up for some trolling there.

But that's cute that you think that you have the real Thanksgiving. Also, too, let's just rewind. So you're back in Florida or you're in Florida. Technically, back in Florida is accurate because it is a little known fact that I tend to try to keep hidden from the world, although I am now saying it on our podcast. Which I believe all 7 billion people in the world do listen to our podcast. So you've definitely been outed here. I was technically speaking born in Florida.

So I am technically speaking back home. And so I heard that a couple of years ago, was it a year ago, COVID no longer exists in Florida, hey? Oh, yeah, yeah, yeah. I mean, this is the free state of Florida. I was joking. I've never actually been to Miami. I've been to pretty much all the other major U.S. cities.

And they're opening. When I was in Louisiana, they had this chain. This is going to be a tangent, but we're going there. They had this chain of, um, fast food restaurants called Raising Cane's and they served one thing, um, chicken fingers and like fries, but like chicken fingers and fries. And that was it. Um, and they had this sauce that was like, I would, I would, Connor, I would sell you down the river for a thing of this sauce.

Like it is good. It is really, really good. But they're like only in like Louisiana and like they've been spreading out like other parts of the South. I lived near the first of the stores, which is right next to the lsu campus um the the founding store and the story is that the guy who founded this restaurant chain um he was a business major and this was his you know for their final project for one of his business classes you had to come up with a business model for, you know, something. And he came up with this business model for a restaurant.

And basically the premise was that, you know, it was a fast food restaurant that had one thing on the menu. And that because they had one thing on the menu, you know, they had fewer ingredients that they needed to source. They could source like higher quality ingredients, you know, that there were fewer things that their staff had to learn how to make. So like they could just do one thing really, really good. And apparently the professor was like, this is like a dumb idea, like, and gave the project to C. And the guy was like, well, I'm going to go start my, you know, my very successful business. Anyways, they're opening up Raising Cane's in Miami, which is like the closest to me or a relative that I get one right now. I'm waiting for them to open one in New York, but

that'll take a few decades. But so I keep telling my mom, I'm going to come down to visit her solely so we can go drive four hours to Miami to get these chicken fingers. And so I was joking the other day with her that we're going to have to go to get to Miami while Florida is still a part of the United States. I was trying to figure out how this is going to come back to Florida and, you know, Florida. And, you know, if we've got listeners in Florida, good on you. They know. They know. we've got listeners in Florida good on you they know they know if we have listeners in Florida they get it they get it because I'm Floridian I get

it I get it like I mean I'm not sure this is I'm not sure I mean we're not going to say anything so it's fine to mention but there's a YouTube channel that was previously called all gas no brakes and then there was like a lawsuit thing. Then they had to rebrand.

So now it's channel five news. Have you heard of either of these? No, I will send you a link. I'm not actually sure if I feel comfortable. I'll have to watch a couple of the videos and then we will link a video. Um, but it's this guy, his name's Andrew Callahan, and he records these five to like 10 minute videos where he just puts himself in the most, not awkward, but just like crazy situations and then ends up interviewing these folks that are just, let's just say, very unique and have interesting worldviews and a lot of conspiracy theory types. Like, you know, one of his most viral ones was when he got himself into like a flat earth conference and was interviewing a bunch of people. Anyways, he's got a bunch of them in Florida on Miami beach during sort of

spring break. He's got one in like Fort Lauderdale. I have, I have myself have never been to Florida. Really? I'm not sure if I should rectify that. Most of what I see on the internet says that I shouldn't. There are cool parts of Florida. Like Tampa's kind of cool. Miami's cool.

Key West is kind of cool. There's other parts of Florida that are probably cool. Yeah, maybe one of these days. There were two very famous C++ committee meetings held in Jacksonville. And all the stories I could tell you both about those meetings and about the venue and the city. Yeah, it was memorable. It was memorable. Those were two of my most memorable committee meetings.

Jacksonville squared. We'll have to do a episode on that later. All right, so. You got a topic for today? Are we doing what we missed out on last time? So at this point, we've been recording for 10 minutes. We have 10 to 15 minutes of recording of the start of the leak code problem. Yeah. Do we want to do that today?

All right. All right. So, yeah. So then let's do the leak code problem. And then we can start our redesigning thrust sequence series. I don't know why I said sequence. All right. So probably,

probably the way I'm going to cut this up is we'll do that little intro thing. Oh yeah. It's too bad too, because I'm flying, you're in Florida. I'm flying to Vancouver this weekend for a 10 K race where I hope to set a personal record, but folks aren't going to hear that.

If that happened for like a month, because we've got part one of this part two of this, then we're recording with Eric and his dad, Eric Kneebler. That's going to be exciting. So that's probably going to be one or two more episodes. It's going to be like four episodes, but anyways.

All right. So we'll cut the beginning of this Florida, Bryce in Florida plus his. Oh, I should have worn my Hawaiian shirt. Oh, I wasn't thinking. That would have gotten a laugh out of you. Damn. Don't worry.

Mistakes, mistakes, mistakes. I'll put that clip at the beginning of the episode. I am wearing my pineapple swim trunks, though. All righty. I'm also wearing shorts and a T-shirt, but I'm inside. I guess you're inside too. Yes, but I am in Florida. You are in

Toronto. Like the ice city. Yeah, it is supposed to snow today. Although I will say, I'm going to turn that down. Toronto is becoming more and more of an attractive city to live in because Vancouver is like the other top city in canada but they had forest fires in the summer and they got flooding right now i've i've been to vancouver and i'm into toronto i

love both cities but like i feel like toronto is like a city on a different level than vancouver really yeah interesting i mean most there's a there's a saying a lot of people from bc and vancouver call ontario on terrible because it doesn't have as it doesn't have mountains it's admittedly not as beautiful from a geography point of view so listener it's important to understand canadians very nice to non-canadians not at all nice to other canadians no we always are saying sorry it's that's like how you can tell a canadian one time here's a story one time i went down across the border because i was at a concert in windsor which is just across the border from Detroit. And so I drove through

Detroit to some like, I don't know, a couple outlet malls to do some shopping, which I don't even know why I did it because I don't really like shopping. But hey, I was told that's what you're supposed to do. Anyways, I stopped off at the subway and then ordered a subway sandwich. And at the end was just I just said, thank you. And she said, Oh, you must be from Canada. And I said, what? How did you know that? And she's like, oh, Americans don't say thank you just for making them a Subway sandwich. Oh, yeah, that's definitely true.

I would not do that. Anyways, all right. So this is the end of this episode. We are now going to – how did I do this last time? Wait, wait, wait. We're not going to do a whole episode just about me in Florida. You've got to give people some real content. Oh, no, no, no. So the end of the episode is that we're going to cut in the 10 to 15 minutes

that we still have left from last time recording, which was the introduction of the leak code problem. This page. All right. I just have a feeling that I'm going to be put on the spot. Oh, no, no, no. At some point. There'll be one question at the end of this, but I'm not going to expect you to know any APL.

So here. The question is, actually, let's bring up the LeetCode question. I'll try and hide the title. And then I'm going to share my screen. And then first I'll just ask you. Oh, I'm not going to put you on the spot. There'll be one question at the end. Oh, let me hide the title.

Then I'll ask you a question. A window. And we'll share this one. There we go. Here, we'll hide the bookmarks. Make it a little bit cleaner. All right. Can you read the question for the listener and answer it in C++ if you'd like?

Given an integer array nums, move all the even integers at the beginning of the array followed by all the odd integers. That's actually poorly written. It should say move all the even integers to the beginning of the array and all of the odd integers to the end. So what algorithm, you can play along, listener. What algorithm in C++ can you use to solve this? Woo-hoo!

I mean, I'm confused because it's pretty clearly partitioned. I mean, so here's the thing. Our C++ developers that are algorithm woke will be like yeah i mean that's you just explore you literally just explain what partition does i don't even need to think like about a fancy that's literally what partition does however partition doesn't exist in every language and i'm sure we have a few non-c++ devs. And even if we have like a Clojure listener right now, they're going partition. That's not what partition does. Partition and Clojure is an anamorphic algorithm

that like splits things up. So it's closer to like a chunk than it is the partition in C++. And partition is actually one of the most overloaded in terms of what it does across programming languages. So what other languages call what C++ calls partition? I think actually just C++.

Nobody else has partition? Or actually here, do you want to? Oh man, damn, I'll post this as well. Because partition is like a fairly important algorithm. I would be surprised if other languages don't have it. Wait, isn't it like your job to know what this would be in all the other languages? I mean, we're bringing up Google Translate. We're bringing it up. Wait, isn't it like your job to know what this would be in all the other languages? I mean, we're bringing up Google Translate.

We're bringing it up. We need to go to... For the listener who may have forgotten, Google Translate is Connor's thing that you tell it, hey, I want to know what this algorithm in this particular programming language is called in other programming languages. Yes, Connor has a thing for this. Of course he does. Why wouldn't he? Yeah, I mean, it's supposed to be a website at some point.

I just haven't had time to do that. My guess is that other languages call it some form of sort. Well, so I know that Haskell actually, they call it partition. But Haskell returns a pair of arrays, not just a single array. Do you know what other? It's actually a library. It's not a language. We could, but we don't. So here we are, Google Translate. So let's type in partition. So what this is here, this is color coded by implementation. And actually that's interesting. Why does oh, so yeah.

All of the blue ones, C++, CUDA, and D have partition doing exactly what we do. And the purple ones I believe return well actually, let's just go to... Should we go to the Rust docs? Let's see what partition does. Creating an iterator... Consumes an iterator, creating two collections from it. So, yeah, I think purple here means that all of these languages return a pair of lists. So it is sort of the same algorithm.

But then Clojure and APL, their partitions do completely different things. So if we go to the closure docs, returns a lazy sequence of lists of n items each. So yeah, it's basically chunks of. So if you give chunks of four, it'll take four elements at a time. Okay, that makes sense. And there's overloaded versions where you can also create, like,

where the chunk size is different than the step size, and then you got some padding and stuff. All right. So Bryce. But that, I mean, like that algorithm, the algorithm, the partition algorithm, like it must be, it must be like just a general algorithm in CS. Like there must be some term of art for it, right? Like it's some class of swarging algorithm i think it's actually talked about in uh programming pearls but i don't actually i don't remember

if it had a name on it hang on hang on hang on i don't know if you've heard this story but uh when i worked for uh for hartmut uh kaiser at lsu um he gave me four books. For the first birthday that I worked there for him, he gave me his copy of Elements of Programming. And then when we moved out of the building, he gave me a hard copy of SICP, the Structure and Interpretation of Computer Programmers, which when I told you that I had a hard copy of, you got very excited because they're incredibly hard to find. They're very expensive.

I mean, here, let's go. While you tell this story, I'm going to look up what the price of SICP is on Amazon. I guarantee you it's not less than 100 bucks. He gave me volumes two and three of Nef, The Art of Computer Programming, the book that Donald Newf wrote. And I was like, well, what about volume one and four? And he was like, yeah, I don't know what, I don't know how the set got broken up, but, you know, you only really need two and three. And so volume two is semi-numeric logarithms and volume three is sorting and searching.

And it's been a long time since I've opened this up. And so I'm going to take a look and see if I can find, if I can find partition in the index here. I'm going to give you 20 seconds to find that. And yes, you can get it in paperback for not that. I mean, $73 for a paperback text is still up there. Let's see. We got partition exchange sort, partitioning a file, partitions of a set, partitions of an integer.

None of those particularly sound promising but let's look at what partition exchange sort is i have i'm almost certain that's not what we're looking for and while bryce skips to that page the hardcover price used is 140 and if you want it new it's 1077 so i'm surprised you can even get it new yeah mine's a little a little uh a little beaten up um which we can look at I mean actually isn't this now that I think about it I mean I haven't really been thinking much I've just been waiting for you to find the answer. Partition is the single step within quicksort, is it not?

Right, right. And that's the section that I'm in in the book is the quicksort section. And it's talking about how you can use this to, you know. Yeah, so this is definitely documented in... Yeah, yeah, yeah. And so I think that the origin of the term partition for what C++ calls stood partition

is probably from this 1962 CS paper, which presumably is about, you know, how you write Quicksort. All right, well, we're coming up on the hour mark here. We're going to punt this to a different episode. And stay tuned for a future episode right quick sort all right well we're coming up on the hour mark here we're gonna we're gonna punt this to a different episode and uh stay tuned for a future episode where we look your audio cut out i can't hear you your audio cut out no still can't hear you and that concludes part one of this two-part episode due to the fact that

my audio cut out stay tuned for the second part next week thanks for listening we hope you enjoyed and have a great day