Does this run in linear time? A case for algorithmics

Speaker 1: So I'm Yulia. Sorry. First timer. I might get awkward. And I'm here to tell you about algorithms. So just a disclaimer, I'm not a very big genius. I'm not going to tell you how to solve a certain algorithm. I'm just going to let you know why I find them fun and what's been my experience with it. So a little bit about me. I'm a software developer. I work uh with Python. I'm a Python fangirl. I'm trying to make my switch to full stack. I work in London, so basic I think that's why I say sorry so often. I have

Speaker 1: a casual relationship with mathematics, meaning that I really love it, but I'm not very committed to it. And I am a daydreamer, which means that I need to be very passionate about the things that I'm doing. So let me tell you a little story about myself. I was born on a Thursday. No, I'm kidding. The year is uh 2014 and I was just starting my second university Um I was coming from a background of biology and physics and humanities, so I did not know a lot of stuff about computer science. So I just entered whatever group I could find and here I am in an algorithmic support group.

Speaker 1: It just piqued my interest, mostly because it was about math, but also because it had statements like this. You are a king and you have 100 barrels of wine and wine is poisonous. How do you find which one is the poisoned one? Well cool. I mean a detective show. So um I continue with it. I starting entering contests. My first one were not good. This is one of my first contests on code forces. Can you see that drop? Basically everyone started uh 1400 and then you just go low if you're not very good at it. Um but I really really liked it and I found people who were s also passionate about it I did notice something.

Speaker 1: Whenever I asked my work colleagues to join me, they would say, um, what do you want me to join you for? Well, you see it's an algorithmic contest. Oh, algorithmics. Do you mean bubble sort? So I just realized that uh also while looking at the websites that was following, that most of the audience were uh either students or people trying to get a job. And the adults, I mean past students, uh the ones who already got the job did not pursue it. And I could understand them. I mean I'm an avid reader, but if I have a book assignment, I might probably not get that book.

Speaker 1: So I find algorithms fun and I'm not going to tell you why I find them fun because whatever floats my boat might not float your boat. But I am going to tell you how I found them useful and how it I think changed the way I write code. So the why? First of all, they're really good mental exercise. You need to keep that skill sharp. And you could do that by learning a new language. or you can solve a problem. It it's um very very interesting also while studying uh for

Speaker 1: a problem like for example I really, really don't understand dynamic programming yet. And you start to read about that thing and you increase your knowledge base and you become better and better at what you do Also, I, as I said, I am a Python lover, so I sort of refuse to write algorithms in C, even though they are so much faster. So um basically this made me become a little more creative when writing code because in order to Get a a Python uh an algorithm to work in Python really really fast, you have to be creative about how you write

Speaker 1: that certain piece of code. Also, it breaks routine because Every day we write uh webs websites or uh I don't know functionalities, uh we connect to databases. We do stuff that is important for the people out there, but we sort of do it every day and the most interesting thing we might come across is getting a new job and learning that new project But doing algorithms from time to time just breaks that routine and makes you realize why you fell in love with programming in the first place. Also, it helps sorry, it helps you understand logic better and um

Speaker 1: it helps you see how certain things were implemented. I mean I'm perfectly uh honest about the fact that not all of us need to um know the stuff that the big guys out there who invented uh Google or machine learning need to do no but At the same time it's really nice to know how something so how a library that you're using. For example, when we're doing sorting, we're not actually writing the sorting algorithms ourselves. We just use dot sort. It's fun. But it's nice to see how it's implemented and why it's slow or fast. Let me give you an example. So let's say that one operation is done in one microsecond.

Speaker 1: And you have something that takes N iterations and that N is on a hundred. If you do it in logarithmic time or uh linear time or Even uh square time. It's still less than a second, so it's pretty great. But look at what happens when you do it at n to the power of six. It's three minutes. Oh three minutes I can go make a coffee in that time. But hot what happens if you do it in two to the power of n or to n factorial? I ain't got anybody time for that. My bones will not be exist by that time. And Also, it helps you improve the way you write code.

Speaker 1: I'm going to give you two examples. One of them is this thing the dreaded time litig team time limit exceeded in on cold forces. It usually happens either because I'm using too many iterations or because I'm very stubborn with using Python. So in order to get past that, I'm going to have to look a bit uh at how I'm visualizing and solving the problem. Am I using too many sorts? because those count. Am I uh using some sort of um inner library that I don't know how it works because that one counts Am I using um

Speaker 1: am I accessing something in a list or am I accessing something in a dictionary? Because those things count. It helps you see these things. And also it helped me write much prettier code. This is a really really bad threesome that it's still not working and I have no idea why. Because I can't I can't even remember what I wanted to do here. Those Ys and V's and Nums and D I D I know it stands for dictionary, but everything else, like my God So um since then I've managed to solve this problem, but I can't fix this one implementation. Also Um it helps you see patterns, you read a problem, and in the back of your head

Speaker 1: you feel like, oh, this sounds like binary search. I've done binary search. Or um I don't know at one time when I was solving many, many, many problems, I realized that I I've I managed to actually find the best solution for the best kind of problem almost instantly based just on the fact that I was having exposure to it. So, oh, and one more thing, almost forgot about this one. We can think of learning algorithms as a social duty When we say algorithm, we as programmers and computer scientists, we think about maths, steps, input goes to output. But when the general public thinks of algorithms, they

Speaker 1: think about um recommendation algorithms, they think about how that time Facebook influenced elections or um how they are matching you on Tinder with strangers. I don't know. But the basic thing is that in the recent years, like since 2017 onwards There is starting to be a pretty much lack of trust towards algorithms, and this lack of trust is based on a lack of understanding. I read a really funny story the other day while preparing for this talk. There is a guy who goes to the doctor. And the doctor is

Speaker 1: telling him, oh, everything is nice with you. You just have a really rare disease called um nervous festivitis because I'm nervous. And he's saying like what? Um and Yeah, well you don't actually really have it, but you have a really high risk for this disease and it's one hundred percent fatal. So you need to take this vaccine in order to help yourself. So y the the patient must will probably not go and take the vaccine because he's like, uh a machine is telling me to do this. But if the doctor would tell him, well, in fact, you have a high risk for the disease because you took blood tests and those blood tests have shown to have a correlation with

Speaker 1: um other people who got the disease and because taking other factors in constituid reason yada yada yada but because um the people using the products that are based on algorithms to not understand them and if we have as developers don't understand them we're just creating this environment where Um it it it could lead to a higher distrust in um I don't know technology in the future, and I think it's really, really bad. So um I'm going to tell you a little bit about how I'm doing it. It's not the best way. It's just a scheme and suggestion. So

Speaker 1: you start by finding your sources. These sources could be anything. You could think about Do you want to study or do you want to practice? Do you want to have a community? Do you have want to uh have someone teach you or do you want to do it on your own? And based on that you find those sources. Usually I use this website. My first favorite are the first three. The first one mainly because I started with it. Hackerang has a really really cool interface. Litcode is Trying to focus on helping you get through the interviews, but you have really cool paths. And the last one, the daily coding problem, sends you a problem each day for you to solve and it helps you get consistent.

Speaker 1: And um oh I have something nice to say about the Sphere Online Judge. They don't show you the test, so you don't know why you got them wrong, and that help makes you think about what you need to do Also, do you remember these books? Because I do remember them from university days. The second one used to give me nightmares at some point. Um The first one is actually very nicely explained, but it gets tedious after a while because you read the title describing the coding interview. It's not saying anything for you as a hobbyist But if you pair the two together and there are many, many, many, many books out there that could help you study, then you go to the next level.

Speaker 1: Up solving is a concept that I've been introduced to by my partner in crimes in algorithmics. It basically means solving your way up. And it goes in one or two directions. First is the point system. This is a website where um which takes problems from a couple of other websites such as Cold Forces. and puts them into lists and it has this concept of a ladder. Um basically um As you see, they are based on ratings, and in each step of the letter there are 100 problems. Some of those problems might um might repeat themselves, but Basically if you just take them one at a time

Speaker 1: and if you encounter duplicate you try to redo it because the second time you might have a better idea. Um you should Find it easier to nail those contests. Also, uh most of the websites have a difficulty system. Code force is now introduced a system based on points But all the others have uh put them into categories like easy, medium, and hard. Yeah, I think I might be rushing a bit along with my presentation. Sorry. Um and Um so yeah that's it. Next is the topic system. Um all the websites are trying to add tags to their problems so you know that you're solving something concerning

Speaker 1: arrays or greedy or dynamic programming. Basically in this approach what you do is you take all the problems that are about arrays and you try to solve all of them. Um the advantage of this is that you get a more um focused approach. Uh the disadvantage of the first one is that you might rush through them and you might get under the impression that you're doing it right because you're going up the ladder, but actually uh you're just Repeating a pattern because you've seen those problems and you got used to them. And then you take a longer break as it happens, like three months or more. Then you come back to it and you realize you didn't really understand them as well.

Speaker 1: Whereas this approach Helps you get into the middle of the problem and sort of I don't know become an array guru Um most of the websites also have paths like top problems about arrays or something like that. And that then it's really important that you keep track of your progress. This is something each might just personalize it. At some point, I was trying to keep the numbers of problems that I was solving, also to take a look at the ratings that I was having. Um the ratings are a bit bad because you might have bad days or you might be a nervous

Speaker 1: person, just as I am. And um If I have a time ticking near me saying you have one and a half hours to solve all these problems, I will do badly. And I will have a bad score, I will get discouraged, and I will not continue. So sometimes ratings are not very telling because I might be able to solve those, I don't know, C or D problems. That means medium or higher. uh if I were in a more calmer environment, but it's still something. Um also the number of problems is not really Telling a lot, but it's telling you something. At some point I was having a race uh with the said partner in crimes

Speaker 1: about which one of us solved the most problems and Uh we just realized after a while that we just tried to outdo the other instead of focusing on the problems themselves, which is not really particularly good. But The point is you need a metric. So whatever you choose, choose something that suits you. For me , racing someone or competing with someone is good But taking part in competitions is stressful, so I don't take ratings into consideration. Then don't forget to compete I am a really bad gamer. Um I mostly play just for the fun, so I do the same with um

Speaker 1: competitive programming. I don't really aim to be the best But I just aim to have the fun in it. And this is what kept my algorithmic slove in check over the time. There are many, many, many uh competitions out there. Um Code Forces, Hackerank, and the others have um weekly or monthly competitions. But what I love the most are these ones The ones that happen once, maybe twice a year, my favorite one is the hash code. Um the Google hash code have many MP complete uh well have only MP complete problems And what I really like about it is that they don't have a good answer. You just try to

Speaker 1: get as many points to um serve as many orders or to send uh a call through as many servers as possible or whatever the statement of to that year is. Instead of just having a number of problems and trying to get the right answer which is fixed like all the others. But Cold Catalyst had contest a couple of years back about astronomy and that really really grinded my oh no grind my gears I think it's it's a bad thing. I really loved it because Because um I love the subject and um so that made me solve the problems more ardently.

Speaker 1: Um then it's really important that you gamify everything. Um I love badges. Uh not a lot of not a lot of a lot of websites have uh badges added to them. These are from Hackerank. Oh uh regarding algorithmics only the first one is important because it uh relies to problem solving. Um but You could try to make your own game out of it. Like I said, I race. That one is me on a Code Forces contest. Last year I gained a lot of points and talking about Schadenfreude, my friend, got downgraded.

Speaker 1: And um We come back to finding your sources. So basically this whole scheme is not a cycle. It looks something like this. Because finding your sources is related to competing and competing is related to um gameif gamifying and keeping progress and Absolving and all of them are tightly coupled together and um you can't have one without the other, I think. So um This is pretty much it. Algorithmics is fun.

Speaker 1: I think we should all try to keep on going with it. Albeit not at a really proficient level. No one asks us to reinvent the wheel. And That's it. I think I rushed a bit. Please ask questions if you have any. Don't ask me to explain algorithms, please. Okay.

Speaker 1: Um, how

Speaker 2: did you start?

Speaker 1: Um so as I said I went to that uh university group, but what really kept me going was competing with friends. We would just um order pizza and stay in late at the office and um brag about who got the most points, which was actually really, really cool

Speaker 2: That's quite inspiring talk, thank you.

Speaker 3: Thanks Julia. Um you mentioned that one of the advantages of doing this is that you start to see patterns from your experience solving these puzzles and problems. But I wondered if you could give some examples of real life problems that you've been able to solve better or faster or or maybe at all as a result of having exposure to the problems through the i in the problem solving exercises

Speaker 1: with it because what I've been working until now is not very high class but I do have one instance Uh when uh a couple of years back at the previous job I managed to make some requests go a little bit faster just because I was I was looking at how the code was implemented and I was thinking about time complexity and I was like, oh, this is done in O add of n to the power of three. No wonder it's working like that. So um I think Seeing the time complexity you are bringing to the product when writing the code is of really, really great help.

Speaker 4: Yeah, I had a question. Thanks for uh taking this up. Um what do you do when you uh you know uh fail the five uh fifth time or sixth time? Because uh it is really intimidating Uh uh you have thoughts to give up on the programming, so uh what do you do then?

Speaker 1: Well I do take breaks from time to time. But uh no. What I realized helped me during those times is just take a step back. Usually I take pen and paper because it sometimes it works best than just having my laptop in front of me and try to to solve it as a math problem instead of a computer problem.

Speaker 4: There is another question as well. What do you do when you face memory out of bounds error? Because I face them a lot. I uh write the program uh like It is uh everything seems correct and the Ryan part, but uh when it comes to uh the programming part, uh it becomes a memory out-of-bounds error. So what do you do then?

Speaker 1: I only had that once during a contest and it was very weird because I've never seen it before. Uh but I usually try to use the to to try to find the best data structure such I don't have to keep a lot of uh different states when solving a problem. So if you choose the right data structure, then You can apply all kinds of uh operations on it without having to get uh from a dictionary to a list to a set to whatever else.

Speaker 4: Thank you so much. One more question.