DEV Community: Daniel Leskosky

Industrial Engineer to Software Engineer

Daniel Leskosky — Fri, 30 Jul 2021 18:38:25 +0000

If you are thinking of switching careers to become a software engineer, then this post is for you. There are a lot of great resources available on the internet to become a job-ready software engineer, but it can be a challenge to separate the signal from the noise. It was for me anyways. My hope is to offer some insight that I gained from my own coding journey to make your journey a bit easier. Just a reminder, these are just my opinions.

Undergrad

For my undergrad I attended Penn State University and earned a BS in Petroleum and Natural Gas Engineering. I think what initially appealed to me the most about the program was the high job placement rate and the potential to travel to different parts of the world. Petroleum engineers also have pretty decent salaries, so that was certainly a factor too.

By my senior year though, I wasn’t as enthusiastic about working as a petroleum engineer anymore. Mainly because I realized that while it was true that I would have the opportunity to travel a lot, I would likely be travelling to remote areas and working long hours. I decided that after I finished the program, I would try to get a job in another engineering field instead.

I had kind of a hard time with that. There were a couple of reasons. My undergrad GPA wasn’t the best — 2.72. I also wasn’t very good at interviewing (but I did get better. these books helped: Presence by Amy Cuddy and How to Win Friends & Influence People by Dale Carnegie). Also it was kind of tough in general to get interviews for non-petroleum engineering roles because I had such a specialized degree (although some of my friends were able to do it, so maybe it was just mostly my interviewing skills to blame).

During this time I was fortunate enough to have parents that allowed me to live at home. This was a tremendous help to me. While not ideal, I am certainly glad that it was an option.

I also worked a few different part-time jobs to pay off some of my student loans during this time. Additionally, in an attempt to improve my resume I took two courses at a local community college. Then I went on to pass the Fundamentals of Engineering (FE) Exam.

It was no use though. After two years of unsuccessful searching, I made the hard choice to go back to school.

Back to School

While searching for work I had seen quite a few postings for industrial engineering roles. After doing some research I decided that I could see myself working as an industrial engineer. I enrolled in the Industrial and Systems Engineering (ISE) graduate program at Lehigh University.

Now to be completely honest, I did consider studying Computer Science. At the time though, I wasn’t very computer-savvy. I had also taken a C++ course in my undergrad and didn’t do so well, so I opted to study industrial engineering instead.

I remember one day when I was working a shift at the library help desk, I was having a conversation with a fellow co-worker who just so happened to also be in my program. He was talking about Big Data and he was selling it pretty well. He said that I should seriously consider taking ISE courses that could lead to me getting a career as a data scientist. He was convincing, but I wasn’t yet completely convinced.

That next semester I did an internship at Mack Trucks. While working at Mack, I started to realize just how much data gets passed around for a company of that size. I decided that I should email my friend from the library help desk and ask him more about Big Data.

The following semester, I took courses that would allow me to learn more about the data sciences. I was willing and determined to overcome my fear of programming languages. I took a Python Data Mining course, a Business Analytics course using R, and a linear algebra course that used AMPL (which is sort of a programming language).

During this semester, I had also been reading Barron’s magazine and listening to different tech podcasts (favorite being CodeNewbie). From reading Barron’s I was able to learn that there were a lot of opportunities in the technology industry, especially for software engineers. Then by listening to the CodeNewbie podcast, I was able to learn that it was very possible to get a role as a software engineer without having a Computer Science degree.

When I graduated, my mind was made up. I was determined to become a software engineer. Now I just needed to figure out how I was going to do it.

Decisions Decisions

I graduated in December 2019 (side brag: I graduated with a 3.52 so I definitely redeemed myself from my undergrad years 🙂 ) and after job searching a bit I took a job as an industrial engineer at Westport Axle in March 2020. Although I just really wanted to get hired as a software engineer right after graduating, I knew that I didn’t possess the skills needed for that to be realistic.

By the way, Westport is a partner company of Mack. They assemble the axles that are used on Mack’s trucks. Just in case you were wondering.

Just want to also mention that Lehigh, Mack, and Westport were all within driving distance of my parents’ house, so I was still living at home. Not too glamorous, but a great way to save money.

At this time, I still wasn’t sure what my next steps should be. The big question for me at that point was whether I should attend a bootcamp or go the self-taught route. Or maybe even just continue with the industrial engineering career (glad I didn’t consider this as an option for too long).

The bootcamp route was tempting. In fact I had been emailing a few bootcamps and was seriously considering enrolling. A bootcamp would give me structure, a peer network, and connect me with potential employers, but it would also cost a lot of money. I already had student debt and wasn’t too enthusiastic about taking on more.

The self-taught route seemed tough though. I would be missing out on everything a bootcamp had to offer, but I would be saving money.

This article helped shape my decision a bit. I also looked up the curriculum for some bootcamps. After some googling I realized that there were courses for those topics online. I realized that I could use the bootcamps’ curriculums and create my own curriculum. It seemed like it would take some extra work, but I was willing to do that to avoid taking on more loans. I ultimately decided to go the self-taught route.

Here to Learn

So my plan was that I was going to continue working at Westport, and would code on weekday evenings and weekends. I figured that if I saved my money for six months, it would be enough to allow me to quit, so that I wouldn’t have a 50 hour work week getting in the way of my goal of becoming a software engineer.

That’s pretty much what I did. I worked at Westport from March 2020 to August 2020 and then lived off of my savings from August 2020 to July 2021, which is when I formally accepted an offer for a software engineering position.

Here are the topics that I studied during that time.

General

Here are two excellent resources that cover a wide range of programming topics:

Saving Money

Living on a budget was necessary in order for this career switch of mine to be possible. While working at Westport I spent very little. It was also during the middle of the pandemic, so that made going out less frequently a bit more convenient.

Didn’t eat out. Didn’t go out. Saved all of my money, so I could have something to live off of when I quit. I did take a trip to California after I quit, but I guess you have to live a little bit, right?

There was one time that I almost lived beyond my means though. I almost bought a new laptop.

There seems to be a misconception that in order to be a real developer you need a fancy new laptop. At least this is something that I believed. Even while getting my masters degree I felt very self-conscious about my ten-year-old laptop. I certainly do remember some strange looks when I would pull it out of my backpack.

I honestly kind of thought that the work that software engineers do would require an incredible amount of computing power. I thought that my laptop would not be able to handle it. So I bought a new laptop for around $2k. I remember not sleeping well at all that night, and then cancelling the order the very next day. I figured I would take my chances and push my old clunker to its limits. It was also a whole lot more important for me to put that money towards my quit-my-job fund instead.

However, I did switch the OS and this helped a lot. Here is another tweet from when I switched to Ubuntu.

The work I did on my laptop while becoming a software engineer mainly consisted of working in Visual Studio Code, NetBeans, or doing problems on LeetCode. It turned out that my laptop was able to handle all of these tasks just fine.

Networking

When I first started working at Westport, I had about forty connections on LinkedIn. I also didn’t have a Twitter account. All of the podcasts I was listening to stressed the importance of having a strong online presence, so I definitely needed to work on this a bit. I started engaging with aspiring developers on Twitter and on LinkedIn I focused on trying to connect with engineers who were already working in the tech industry.

I will admit that at first I felt intimidated trying to connect with people I didn’t know. It wasn’t so bad once I got started though.

I would typically send a connection request along with a few sentences that explained my situation. I would be sure to ask for their advice. For the most part, the people that did connect with me were incredibly helpful. Some would even talk to me on the phone or video chat. I learned a lot through these conversations. Lots of great advice.

But to sum up all of those great conversations in two points:

Do projects to get interviews
Know data structures and algorithms to pass interviews

I would say about 80% of the engineers that I spoke with recommended using LeetCode to prep for interviews. I have only used LeetCode and have really enjoyed the platform. However, there are many other algorithm practice websites out there. Do some research and pick the one that seems right for you.

An additional benefit from this that I then didn’t realize, was that these connections would later be willing to refer me for positions at the companies where they worked. Good deal.

So build your network. It’s important.

#100DaysOfCode

I started doing #100DaysOfCode right around this time. Really helpful and I can’t recommend it enough. Did two or three rounds just on Twitter, then I started doing it on LinkedIn as well. It’s a great way to hold yourself accountable, and it also allows you to take a look at what other people are working on. Also allows you to feel a sense of community.

Blog

From podcasts, blogs, reddit, …etc, I heard it mentioned frequently that it was important for a developer to have their own blog, so I decided that I should have a blog. It took me about a month of weekends to get it set up. I describe how I built it here. There are plenty of different ways to launch a blog though. If you do launch one, do some research and choose whichever way you think is best.

However, if I could have a do-over, I am not sure I would create a self hosted blog again. I post on DEV and Medium as well and I think that posting on sites like these is probably enough.

Although on the other hand, during interviews, many interviewers had some pretty nice things to say about my blog. I don’t think they would have said these nice things if I had just been using DEV or Medium. Another plus was that my blog also allowed me to become familiar with the AWS ecosystem. I used Amazon Lightsail, Route 53, and S3 to build it.

My blog was built with WordPress. While this option is not as ideal as coding it myself, I did not know how to code well enough at the time to build one. Building a WordPress blog allowed me to build a blogging platform without having to first become proficient with web development. Pretty good deal in my opinion.

Java

Next I started learning Java. At the time here was my thinking for learning Java:

Used by many large software companies
Language used in Cracking the Coding Interview
Language frequently used in LeetCode solution articles

Also I heard that this Java course was a great way to learn an object-oriented programming language. After completing this course, I agree.

Now don’t get me wrong, Java is now my favorite language, but if I could go back in time I don’t think I would have focused on learning Java. At least not if my goal was to get a job as a software engineer as quickly as possible.

It would have been much more efficient to become proficient with just JavaScript.

Here is what I have come to realize:

JavaScript is used by many large software companies too
While Java is the language used in the physical book, Cracking the Coding Interview also has the code in JavaScript online
While not as frequent as Java, there are still LeetCode solutions in JavaScript. Just google “JavaScript LeetCode solutions” and you will find some.

Coming out of Lehigh University, I had some misconceptions about JavaScript. The general attitude that I had picked up was that it was a weird (for lack of a better word) language and not really used professionally. This turned out to be kind of wrong (although truthfully JavaScript is kind of weird).

From all of the job board surfing I have done, it seemed like 3–4 out of 5 of the postings were for JavaScript roles. Also in technical interview rounds, there was probably about six instances where I was required to use just JavaScript, two instances where I was required to use Python, and no interviews were I was required to use only Java.

You can’t go wrong with learning an object-oriented language like Java, Python, or C++ (although I would probably not pick C++ as a first language). These are great and widely-used languages. However, if you are looking for a quick transition into the tech industry then JavaScript is your best bet. . . in my opinion.

Not Java

Ok, so if I could go back in time and not do that wonderful Java course that I mentioned above (just want to restress that it is a great course and I learned a lot) I would instead just focus on JavaScript right from the start.

I would recommend starting with either of these two courses:

I have worked through about half of both of these courses and you can’t go wrong with either. Each one also has a Slack/Discord community as well, which are a great way to network and see what other people are working on.

React

In this section I am going to talk about React. You might be wondering why I don’t have a HTML/CSS section and a JavaScript section. I wonder the same thing. For some reason I thought I could cut corners a bit and skip the foundations of web development and go right to the JavaScript libraries/frameworks part.

This was certainly doable, but not ideal. If I could go back in time I would definitely focus on becoming proficient with using HTML/CSS and JavaScript without using a library/framework. Then I would move on to learning the library/framework part. Those two courses I mentioned above would have been great places for me to start.

Instead I used this course to learn about React, and more specifically the MERN stack. It is a great course. I highly recommend it. Don’t be like me though. Learn HTML, CSS, and JavaScript first. At this point I still don’t know CSS very well and honestly it is kind of embarrassing.

The creators of the two courses mentioned above also have courses about React that have good reviews. I haven’t tried them though.

I am also mentioning React a lot, but haven’t mentioned Angular or Vue yet. That is because React is in much higher demand right now. My suggestion would be to learn React instead of Angular or Vue. Of course this can always change.

University of Helsinki

You might have noticed the both the Java course and the MERN course that I mentioned are both offered through the University of Helsinki’s MOOC. I really enjoyed both of these courses. I have only taken these two courses from the University of Helsinki, so I can’t speak about the others, but the two that I have taken were really well thought-out.

The main thing that I liked about the University of Helsinki’s courses was that there was lots of exercises. I have yet to find another online course that is as exercise-dense as the courses that I have taken from the University of Helsinki.

The problem with a lot of programming tutorials on the internet is that there is too much video watching, but not enough actual doing. This can lead to tutorial hell.

So when choosing courses, make sure that there are plenty of exercises and then be sure to build projects with what you have learned.

MySQL

I also took a course on MySQL. Good course, but not really not needed to get that first developer job. I think I had two interviews that asked about SQL queries.

LeetCode

I didn’t start doing problems on LeetCode until I had finished the Full Stack Open and made it about 80% through the Java course. I would do one or two LeetCode problems a day while continuing the Java course. Once I finished the Java course, doing problems on LeetCode became a full-time effort.

LeetCode problems were very tough for me when I first got started. Much more difficult than the courses that I had worked on.

The most important thing you can do is not to become discouraged. From what I have read on LeetCode’s forums, nearly everyone is bad when they first start. You just have to keep going.

Here are some resources that were helpful to me when learning data structures and algorithms:

Cracking the Coding Interview — Great resource. Really gets you in the right mindset for interviews. You can find it here.
Elements of Programming Interviews — Another great book. Personally, I like this one more than CTCI, but YMMV. You can find it here.
Grokking the Coding Interview — Can’t emphasize this one enough. Haven’t seen it mentioned it too often. Explains patterns that occur in different coding challenge problems. Great at providing a big-picture of all the different algorithm problems you might encounter. Check it out here.
Grokking Dynamic Programming — Dynamic programming is tough. This course has definitely helped me get a better understanding.
Tushar Roy — Tushar really knows his stuff. His dynamic programming playlist is especially good. Check out his awesome YouTube channel.
Back To Back SWE — Great YouTube Channel. Highly recommend.
Kevin Naughton Jr. — Another awesome YouTube channel. Great at going over problems and gives helpful advice.
Base CS — Vaidehi Joshi does a great job of laying out the fundamentals of algorithms and data structures. Check out the blog series here. She also has a podcast that I give two thumbs up.
Pramp — Do mock interviews! The sooner the better! Pramp has been a huge help to me. Pramp does free peer mock interviews. Doing peer mock interviews has its drawbacks, but it’s free! If it’s free, then it’s for me!
Interviewing.io — Will cost some money, but it is worth it. Get excellent practice by doing mock interviews with actual software engineers. Check out Interviewing.io.
JavaScript Algorithms and Data Structures Masterclass — Great course if JavaScript is your main language. Thank you Colt Steele for this wonderful course!

For me when I was first starting out, Kevin Naughton Jr’s YouTube channel was the most helpful. I started from his earliest videos and went in chronological order. Being able to watch him grow his knowledge over the years gave me hope for myself.

I was advised to do 300 LeetCode problems before starting to send out applications. From my experience, I don’t think that is necessary. I would have probably been fine doing significantly less. I would probably say about 100. Of course a lot of this depends on the companies that you plan to interview with and the difficulty of the questions that they will be asking.

System Design

The two best resources I found for system design are Grokking the System Design Interview and the system design playlist from Gaurav Sen’s Youtube channel.

I wasn’t asked too many questions about system design though. I never had a interview round that was dedicated entirely to answering a question like, “How would you design X?”.

The most frequent question I got that was related to system design was, “What is the difference between a relational and non-relational database?”, so I know how to answer that one pretty well by now.

If I could go back in time, I wouldn’t have spent as much time as I did on studying system design.

Object-Oriented Design

In my very first technical interview I was asked to design a chess game. I hadn’t prepped for object-oriented design questions, as I thought they more typically asked in interviews for senior engineering positions. Needless to say, I didn’t do very well in that interview.

After that though I did spend a decent amount of time learning how to answer those sort of questions. Cracking the Coding Interview has a great section on it and this course is really good too.

After that interview though, I was never asked an object-oriented design question again, so no need to spend too much time prepping for these questions in my opinion.

Behavioral

Prepping for behavioral questions was actually a lot more important than I initially thought it would be. I’ll admit before I started interviewing, I kind of thought that interviews would mainly be coding-focused apart from the typical “tell me about yourself” types of questions. I certainly had some interviews with some tough behavioral rounds.

I found Dan Croiter’s YouTube channel quite helpful. I recommend writing out about twenty stories using the STAR method. That’s what I did and it helped me quite a bit.

Interview Time

I started sending out applications right at the beginning of 2021. It took me until July to formally accept an offer, so about six months, give or take. I have heard of people getting offers after their first interview and have heard others taking over a year. It is probably best to plan for the worst, but hope for the best.

There was three different sort of distinct phases throughout the period of time that I was interviewing, so that’s how I will break it up.

Phase 1: January — March

During this time, even though I had done a decent amount of LeetCode problems, I was still not where I wanted to be. I actually didn’t send out too many applications during this period. I instead relied on LoopCV. Pretty good service in my opinion. I would let it send out applications for me, while I continued to practice LeetCode problems. I actually got a couple decent interviews while using it throughout my job search. I recommend to use it to supplement manually sending out applications, though. You will get much less interviews with LoopCV, compared to if you apply manually.

As I was using it as my primary means of sending out applications, I didn’t have too many interviews during this time period. I was mainly working on improving my whiteboarding skills. Pramp and Interviewing.io are great resources for that. In the first mock interview I took on Interviewing.io, my interviewer had lots of great advice. He introduced me to two great resources that really allowed me to improve my technical interviewing skills.

REACTO
Tech Interview Handbook more specifically this section

He also showed me this LeetCode list which I thought was pretty good too.

I did have a couple of interviews during this period, but none of them panned out. However, by the end of this period I was starting to feel more confident in technical interviews, so I started spending more time sending out applications and not as much time doing LeetCode.

Phase 2: April — May

Towards the end of March, I started to reach out to my connections and ask for referrals. There are plenty of resources on the internet that say that the best way to get an interview is through a referral. I think this is generally good advice, but in my case it wasn’t working so well. I was getting referrals, but still getting rejected.

Another approach that I tried was to send follow-up emails to people at the companies that I applied to. Sort of how it is described in this article. However, this wasn’t working for me either. I wasn’t getting enough results to justify the amount of time it took to reach out to each person individually.

Eventually I just started manually searching job boards and sending out as many applications as I could. I actually had the best results doing this.

In order for this method to be successful, though, volume was key. I would spend most of my day sending out applications. Probably got rejected by about 95%, but I eventually started to get interviews.

When mass applying like this, it is also important to do it consistently from day to day. Once I started to get busy with interviews, I eventually ran out of time to continue submitting applications. That is why it is important to send out as many applications as you can before you start getting interviews.

I should mention that I was applying all over the country. Being open to relocation allows you to be able to cast a much wider net. Here is a good list of tech cities by the way.

Also there are also quite a few job boards out there, but the ones that I had the most success with were LinkedIn, Indeed, and this one.

First Offers

Towards the end of May I was interviewing with a couple different companies and ended up receiving two offers. They didn’t work out though and largely this was because I had tried negotiating. Now I know that there are plenty of resources on the internet that do a great job of discussing the merits of negotiating. Take this one for example. I am not saying there is anything wrong with negotiating an offer, especially if you have multiple offers and have leverage. I am just saying that for perhaps your first software engineering role, maybe don’t negotiate. Instead, hold off until you are presented with more senior opportunities down the road. However, if you have three or more offers on hand than I would say that you should definitely negotiate.

Anyways, here is what happened.

I had two offers and I started to negotiate some of the details with both companies. Now Company A knew that I had an offer from Company B, so Company A made an offer to beat Company B’s offer. When I tried to negotiate with Company B they took back their offer. Now I was just left with Company A, so I accepted that offer (only verbally). Eventually Company A was able to piece together that Company B was no longer in the picture, so then they substantially reduced their offer. At that point I decided to continue looking for another opportunity.

I later spoke to a senior engineer who had been offering me mentorship. He said that he had actually seen similar situations happen several times with aspiring software engineers, such as myself. He said that he actually advises entry-level developers especially from non-traditional backgrounds not to negotiate.

After that I decided that the next good offer I got, I was going to accept. No negotiating next time.

YMMV

Phase 3: June — July

I will admit that I was a bit bummed that the last two offers didn’t work out, but I was determined to make it happen again.

During this period I more or less did the same as last time. Lots and lots of applications. Which lead to lots and lots of interviews.

I remember speaking with a software engineer I had met on LinkedIn, while I was still working at Westport. He told me that I should expect to have lots of days with multiple interviews. That sounded ridiculous back then, but his prediction turned out to be right.

Hello State Farm

Eventually I received an offer from State Farm and I was pretty happy about that. I was able to finish up the interviews that I was having with other companies and even ended up receiving another offer. No negotiating this time though.

I made the decision to go with State Farm and I am more than confident that I made the right decision. It was a great interview process and the engineering team seemed like they would be great to work with. Definitely looking forward to moving to Atlanta and getting started soon!

Good Luck

Thanks for sticking with me for this whole post. I hope that one or two of the things that I shared will allow you to reach your goals as well. I know how helpful it was for me to read blog posts like this throughout my coding journey, so I hope that this post was able to help you similarly. Good luck and don’t give up!

If I can do it, then you can too.

The k-th Lexicographical String of All Happy Strings of Length n

Daniel Leskosky — Tue, 02 Mar 2021 16:41:10 +0000

It is important to always strive for the best time complexity when solving algorithm problems. I recently solved for the brute force solution to this problem and was ready to move on. Then, a fellow programmer on the world-wide-web reached out to me and encouraged me to do better! He showed me a solution that was much better than mine. The only problem was that I didn’t understand it at all. Well, now I do understand it. AND I want you to understand it too!

The Problem

A happy string is a string that:

consists only of letters of the set [‘a’, ‘b’, ‘c’].
s[i] != s[i + 1] for all values of i from 1 to s.length — 1 (string is 1-indexed).

For example, strings “abc”, “ac”, “b” and “abcbabcbcb” are all happy strings and strings “aa”, “baa” and “ababbc” are not happy strings.

Given two integers n and k, consider a list of all happy strings of length n sorted in lexicographical order.

Return the kth string of this list or return an empty string if there are less than k happy strings of length n.

Example

We will be using example 3. To see more examples, check out the problem on LeetCode. Also read about Lexicographical Order.

Example 3:

Input: n = 3, k = 9
Output: “cab”
Explanation: There are 12 different happy string of length 3 [“aba”, “abc”, “aca”, “acb”, “bab”, “bac”, “bca”, “bcb”, “cab”, “cac”, “cba”, “cbc”]. You will find the 9th string = “cab”.

Brute Force

First, I should mention that the purpose of this post is to compare the efficiency of the different solutions and then to really dive into the most optimal solution.

If you are just starting out with backtracking and recursion, check out these three great problems to get started:

This brute force solution uses recursion to create all of the happy strings from letters ‘a’, ‘b’, and ‘c’ and store them in a list. Notice that when “dfs” is called, the for loop that iterates through “abc” starts at the first possible letter, ‘a’. This is what allows repeat letters to appear in the happy strings. Also note that the happy strings will be generated in lexicographical order.

That is a lot of extra work though! As you can see up in example 3, twelve strings were created and stored in a list. We are only interested in one string, so there is probably some room for improvement.

Also, here is a way to calculate the number of total happy strings from n.

Time Complexity

The first character in one of our happy strings can be three possible different letters. The rest of the letters in the string (n-1) though can only be two possible letters. The total number of permutations is 3 * 2^(n-1). Three options for the first letter, two options for the rest of the letters. 3 is a constant and is dropped. The time complexity is O(2^(n-1)).

Space Complexity

The space complexity is O(n) for the height of the recursion stack and O(3*2^(n-1)) for the strings stored in the list. This gives O(n + 3*2^(n-1)). This is asymptotically equivalent to O(2^(n-1)).

Learn more about Big-O.

A Bit Less Brute

This approach uses backtracking and is certainly more efficient than the last approach. For each “backtrack” call there is a parameter “remain” This keeps track of the length of “sb”. When “remain” is 0, there is a global counter that is incremented. Each “sb” is generated in lexicographical order, so when count = k, we know that the current string is the k-th string.

What is nice about this approach is that all of the the possible happy strings aren’t generated. Only up until the k-th string are generated. Also, none of them are stored in a list. This saves time and space.

Time Complexity

We evaluate k strings of n length. The time complexity is O(k * n).

Space Complexity

The space complexity is O(n) for the recursion stack.

Optimal Solution

When I first solved this problem, I was only able to come up with the brute force solution. I then saw the second solution on the discussion board and saw how it was a nice optimization to the brute force solution. Keeping a global counter and getting rid of the storage list are two really good improvements.

I had also seen another solution. This solution was able to do it in linear time. The only problem was that I could not understand the solution at all. I took a glance at it, scratched my head, and put it in my “come-back-to” list. Here is the post that has the solution that I am talking about.

Not to get too far off topic, but I want to mention that I have been doing the #100DaysOfCode Challenge. One day I posted about solving the brute force solution. A week or two later someone who had read my post, emailed me some Python code that was very similar to the Java solution that I had put in my “come-back-to” list. His code could do linear time as well.

The code I posted for the #100DaysOfCode challenge only did O(2^(n-1)). I decided that I needed to do better!

First let’s take a look at the code that was generously donated by Sahand. We won’t spend time going into it, but the logic used is very similar to the Java linear time solution that we will be going over.

Thanks again Sahand!

Now let’s take a look at the Java solution that I will do my best to explain.

This solution was posted by LeetCode user @vortrubac. Here is the original post again.

Let’s go through this code line by line. Remember how I mentioned that the first letter in the string can be three possible characters and then the rest of the letters (n-1) can be two possible characters? Well, that is what is going on in lines 3–4.

Line 3 is just a fancy way of writing this: Math.pow(2, (n-1)). Using the left shift operator is just another way to do it. But, really what you are doing is taking 1 and shifting the bits left n-1 places and filling 0’s in the void. So for n = 3, prem = 1 0 0 = 4.

“prem” also corresponds to the total number of happy strings. Well, sort of. You have to multiply “prem” by 3 to get the total number of happy strings. 3 represents the first letter. Lines 4–5 are making sure that the k-th value does not exceed the total number of happy strings.

While on the topic of bitwise operators, in line 10 that is a signed right shift. It does the opposite of left shift. It basically divides a number by two. Read more about bitwise operators. Check out this great video too.

Also, here are two problems that I think are good bit problems:

Ok, now that we have the bit stuff out of the way, let’s move on to the tricky parts. When I was first trying to figure out this solution, I worked through lines 6–14 and sure enough it worked. The StringBuilder creates “cab” which is the 9th lexicographically-sorted happy string. However, I could not figure out why it worked.

Someone in the comments mentioned that this problem follows a similar method. Something about using the Factorial Number System. Still couldn’t figure it out.

We know that line 6 is used to find the first character in the k-th happy string. In line 6 “ch” is starting with a base ‘a’. We know that the first letter in our happy string can be either ‘a’, ‘b’, or ‘c’. That means that (k-1)/prem has to equal either 0, 1, or 2. This creates three groups. In group 1, four strings start with ‘a’. In group 2, four strings start with ‘b’. In group 3, four strings start with ‘c’.

k = 9, so (9–1)/4 = 2. ch = 099, (char)ch = ‘c’. Check this ASCII Table to be sure.

But how do we decide whether (k-1)/prem is 0, 1, or 2? Check the list in example 3. Happy strings 1–4 start with ‘a’. Happy strings 5–8 start with ‘b’. Happy strings 9–12 start with ‘c’.

Ok now I know this is going to sound ridiculous, but this is the part that really hung me up: Why do we subtract 1 from k? I came this close to calling it quits on this post, because I could not find a proper way to explain why 1 was being subtracted from k.

Then I got it! I put together some tables that I think will allow you to get it too. In Table 1, you can see our three groups.

Table 1 — line 6

And Table 2 shows why 1 is subtracted from k.

Table 2 — line 6

k-1 is just a nice trick that allow there to be an equal distribution of 0, 1, and 2. It also guarantees that there isn’t a 3. 3 would mean ‘d’ and ‘d’ makes our strings unhappy.

Table 3 — line 9

Table 4 — line 9

As you can see in Table 3, k can possibly be 1–12, but (k-1) % prem + 1 will reassign k so that it can instead only be 1–4. Go look at the list for example 3. Look at the second letters for each happy string.

Let’s take the happy strings that have a first letter of ‘c’ for example. “cab”, “cac”, “cba”, “cbc”. The second letter is ‘a’ for the first two happy strings and then ‘b’ for the last two happy strings. This is where our new values of k come in handy. After we reduce “prem” by an order of 2, it is quite handy to divide (k-1) by “prem”.

Table 5 — line 9

Now look! Because “prem” was reduced by a factor of two, (k-1)/prem at the beginning of the ternary operator can only either be 0 or 1 as seen in Table 5. If it is 0 then the conditional is truthy and “ch” will either be ‘a’ or ‘b’ depending on what “ch” currently is. If (k-1)/prem is 1 then the conditional is falsy and “ch” will either be ‘b’ or ‘c’ depending on what “ch” currently is.

Table 6 — line 9

Now back to line 9 for Table 6. k ranges from 1–4 and (k-1) % prem + 1 will “index” the k values like it did in Table 3.

Table 7 — line 11

Table 7 shows that prem = 1 which means that the while loop will terminate after the last “ch” is appended to “sb”.

result = "cab"

Time Complexity

The time complexity for this algorithm is O(n). There is one string of size n that is built.

Space Complexity

The space complexity for this algorithm is O(1).

Get Better at Algorithms!

Algorithms and data structures are pretty tough. They are definitely taking a while for me to get the hang of them. However, there are some great resources out there, and I feel obligated to share some that have been most helpful to me. If I missed any that have been helpful to you, be sure to mention them in the comments.

Cracking the Coding Interview — Great resource. Really gets you in the right mindset for interviews. You can find it here.
Elements of Programming Interviews — Another great book. Personally, I like this one more than CTCI, but YMMV. You can find it here.
Grokking the Coding Interview — Can’t emphasize this one enough. Haven’t seen it mentioned it too often. Explains patterns that occur in different coding challenge problems. Great at providing a big-picture of all the different algorithm problems you might encounter. Check it out here.
Grokking Dynamic Programming — Dynamic programming is tough. This course has definitely helped me get a better understanding.
Tushar Roy — Tushar really knows his stuff. His dynamic programming playlist is especially good. Check out his awesome YouTube channel.
Back To Back SWE — Great YouTube Channel. Highly recommend.
Kevin Naughton Jr. — Another awesome YouTube channel. Great at going over problems and gives helpful advice.
Base CS — Vaidehi Joshi does a great job of laying out the fundamentals of algorithms and data structures. Check out the blog series here. She also has a podcast that I give two thumbs up.
Coding Challenge Website — There are plenty of different ones to choose from. HackerRank, CodeWars, and Edabit all seem to be pretty popular. I personally use LeetCode. Find the one that works for you!
Pramp — Do mock interviews! The sooner the better! Pramp has been a huge help to me. Pramp does free peer mock interviews. Doing peer mock interviews has its drawbacks, but it’s free! If it’s free, then it’s for me!
Interviewing.io — Will cost some money, but it is worth it. Get excellent practice by doing mock interviews with actual software engineers. Check out Interviewing.io.

Well, I hope that was useful. Thanks for reading my post and best of luck with your learning about data structures and algorithms!

Dedication

This post is dedicated to Sahand. I wouldn’t have taken the time to figure out the optimal solution, if you didn’t send me that Python code, so thanks!

Path in ZigZag Labelled Binary Tree

Daniel Leskosky — Tue, 16 Feb 2021 01:22:46 +0000

Every so often when I am practicing algorithm problems, I run into a problem that requires a bit of math to solve. For this “Path in ZigZag Labelled Binary Tree” problem, my initial impression was that I would have to do a breadth-first search on a tree. As I quickly found out, I was not dealing with a typical tree problem. This problem requires a bit of math to solve. I don’t know about you, but my math is a bit rusty.

The Problem

In an infinite binary tree where every node has two children, the nodes are labelled in row order.

In the odd numbered rows (ie., the first, third, fifth,…), the labelling is left to right, while in the even numbered rows (second, fourth, sixth,…), the labelling is right to left.

Given the label of a node in this tree, return the labels in the path from the root of the tree to the node with that label.

Example

Example 1:
Input: label = 14
Output: [1, 3, 4, 14]

Example 2:
Input: label = 26
Output: [1, 2, 6, 10, 26]

Link to Problem

ZigZag Tree

Normal Tree

Some Math

As promised there is going to be some math. I just want to go over some concepts to make sure that we are on the same page.

First off, here is a post about tree basics. In this problem we are dealing with a full and complete binary tree. This is also known as a perfect binary tree. For a perfect binary tree, each level has exactly twice as many nodes as the previous level.

Let’s refresh our memories on logarithms a bit. I found two great resources to help us do that. Here is one by VC that is pretty good and here is one by Vaidehi Joshi that is pretty good as well. I like some things that VC says:

“Log of a number is the number of times you need to divide that number by the ‘base’ to get an output equal to 1.”

I like how VC explains it in terms that us simple folk can understand. Let’s look at some examples.

log2(8) = 3. Divide 8 by 2 (the base). Do it 3 times and you get 1.
Log10(10000) = 4. Divide 10000 by 10 (the base). Do it 4 times and you get 1.

Ok, so that’s not so bad. Now let’s see how this can be applied to the perfect binary tree in the problem. First take a look at the figure below to see how we are going to refer to the depths of of the levels for the binary tree in this problem.

For starters, let’s see how we can find both the fist and last node in a level for a particular depth.

Let’s see how this can be applied to depth = 3.

Here is a neat trick. Let’s see if we can find how many nodes are contained up until a certain depth.

Now let’s see how for a particular node number, we are able to find the depth that the node is located.

The example for finding the depth from a node number uses numbers that have 2 as a root. Let’s look at when this isn’t the case.

log2(10) = 3.32 ~ 3
log2(13) = 3.70 ~ 3

As you can see, although node 10 and node 13 come out to decimal, they still have a depth of 3. So, when we are finding depth based off a node number, we will floor the result.

Well, I think we have just about the covered the basics. Let’s start figuring out how to solve the problem.

Brute Force

This problem is essentially asking us to return a list that has the path from a node to the root.

Node to Root

When I tried to solve the problem, I first built a tree that contained nodes for all the values up until the “label” that is given as input. I didn’t actually build a tree though. I instead used nested lists to represent each level of the tree. The lists followed the zigzag pattern.

What I realized is that if you take the node that corresponds to the label given as input then you can can assign an index value to that node. Then take that index value and divide by two. This will give the index value of the parent node. In the example below, I used label = 10 to make it more interesting.

Something to note is that if the tree was not in a zigzag pattern and was a “normal tree”, then the node values could be divided by two to get the value of the parent node. Go up to the “Normal Tree” picture above and try it. Just make sure to floor the result.

Here is the code for the brute force approach that I took:

Pretty good approach in my opinion. Just not quite fast enough for the big leagues. The time complexity of this algorithm is O(n + logn) with n = label. The space complexity is O(n + logn) as well.

Optimal Solution

Here is some real top-notch code submitted by LeetCode user @alok5. You can find the original post here.

The basic idea behind the algorithm is fairly straightforward.

Add the node to the back of the result list.
Find the depth of the node.
Find the parent of the node.
Repeat steps with the parent as the new node.

When using Math.log() in Java, it defaults to base 10. In the algorithm Math.log(parent) / Math.log(2) is how to change the base to two. Read more about that here.

Some Illustrations

Let’s take a look at some illustrations to really give us a crystal clear mental picture of what is happening with this algorithm.

parent = 14

Ok, so I know what you are thinking. This tree does not follow the zigzag pattern that is described in the problem. In fact it is a pretty normal-looking full and complete binary tree with the exception of the last level. The last level is reversed.

That’s right. Only the last level is reversed. This is the level that contains the “label”. Label or the “parent” is shaded red. The other nodes in this level are shaded blue. This blue-shaded level is the only level that is reversed.

Why is only this level reversed?

Go back up to the “Normal Tree” picture. The parent of the node 14 is 7. However, in the zigzag tree the parent of node 14 is 4. To find the parent in the zigzag tree, think of it like this.

Pretend we are actually dealing with a normal tree. To find the “zigzag” parent in a normal tree we can do one of two things:

We can reverse the current level. Now the parent of the node in the reversed level is the desired “zigzag parent”.
We can reverse the level above. Now the parent of the label node is the desired “zigzag parent”.

That is what offset is doing. If you remember from above, 2^(depth + 1) — 1 is the last node for a particular level. Last node — parent = distance that parent is from end of the level = offset.

Remember that the first node = 2^(depth). So then take the offset value (1) and add it to the first node in the level (8) and divide this value by 2.
(8 + 1) / 2 = 9 / 2 = 4. In a normal tree, the parent of node 9 is 4.

So really we are finding the parent of node 9 in a normal tree. Node 9 is like the mirror node for 14. Offset is like finding the mirror value for a node.

parent = 4

The same thing happens when parent = 4. The offset is 3. So 7 is like the mirror value for 4. So, when this level gets reversed, 4 goes in the place where 7 was. 3 is the “zigzag parent” of 4.

parent = 3

Same thing happens again, but there is only the root node left, so it doesn’t matter so much. Also notice that parent = 1. This terminates the while loop and the result is returned

result = [1, 3, 4, 14]

Time Complexity

The time complexity for this algorithm is O(logn) with n = label.

Space Complexity

The space complexity of this algorithm is O(logn) as well.

Learn some more Big-O tips and tricks.

Get Better at Algorithms!

Cracking the Coding Interview — Great resource. Really gets you in the right mindset for interviews. You can find it here.
Elements of Programming Interviews — Another great book. Personally, I like this one more than CTCI, but YMMV. You can find it here.
Grokking the Coding Interview — Can’t emphasize this one enough. Haven’t seen it mentioned it too often. Explains patterns that occur in different coding challenge problems. Great at providing a big-picture of all the different algorithm problems you might encounter. Check it out here.
Grokking Dynamic Programming — Dynamic programming is tough. This course has definitely helped me get a better understanding.
Tushar Roy — Tushar really knows his stuff. His dynamic programming playlist is especially good. Check out his awesome YouTube channel.
Back To Back SWE — Great YouTube Channel. Highly recommend.
Kevin Naughton Jr. — Another awesome YouTube channel. Great at going over problems and gives helpful advice.
Base CS — Vaidehi Joshi does a great job of laying out the fundamentals of algorithms and data structures. Check out the blog series here. She also has a podcast that I give two thumbs up.
Coding Challenge Website — There are plenty of different ones to choose from. HackerRank, CodeWars, and Edabit all seem to be pretty popular. I personally use LeetCode. Find the one that works for you!
Pramp — Do mock interviews! The sooner the better! Pramp has been a huge help to me.

Well, I hope that was useful. Thanks for reading my post and best of luck with your learning about data structures and algorithms!

Largest Rectangle in Histogram

Daniel Leskosky — Tue, 02 Feb 2021 04:41:33 +0000

I was working on a LeetCode problem a few days ago. I was able to come up with a brute force solution, but wasn’t able to get any further past that. On the discussion board a user gave a solution that utilized histograms. The user also referenced another problem for more histogram practice. I don’t know about you, but I could use some more histogram practice. Let’s figure out how to solve “Largest Rectangle in Histogram”.

The Problem

Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Example

Example 1:
Input: heights = [2, 1, 5, 6, 2, 3]
Output: 10

Example 2:
Input: heights = [2, 4]
Output: 4

Link to Problem

Brute Force

Understand what we are trying to find? We want to find the largest possible rectangular area that can exist within the histogram that is pictured above. The rectangle can span across multiple columns, but it has to be only one rectangle.

The best way to get some ideas on how to go about optimally solving the problem is to first look at the brute force solution.

Here is the code for the brute force solution:

The time complexity of this algorithm is O(n²) with n = heights.length. The space complexity is O(1); no extra space is used.

Let’s take a look at some illustrations that show what one full iteration of i looks like.

What did you notice in the illustrations? A lot of unnecessary work right? At first when both i and j = 0, the minimum height is 2. After that though, the minimum height is 1 for the rest of the time. It seems rather unnecessary to have to calculate a new area every single time that j increments. Wouldn’t it be much better to only ONCE have to find the maximum area that exists for each of the different column heights?

Still not sure what I mean? Ok let me try to explain it a bit more. The column height of 1 is the absolute minimum of the column heights. Every column in this histogram has a height of at least 1. Thus, the maximum width that corresponds to the column height of 1 is 6. 6 is the total width of the histogram.

On a side note, I have found that it is good practice to start sentences with words like “Thus”, “Conclusively”, and “Unequivocally”. It is a good way to let people know that you are wicked smaht and an even better way to lose friends quickly.

Ok back to business. Let’s look at some more maximum areas that correspond to a specific column height.

The picture above corresponds to the column height of 2. What do you notice about it? It stops when it hits the column height of 1. The column with the height of 1 creates a bound for our rectangle. 1 is less than 2 and because 1 is less than 2, it creates a boundary.

One more illustration.

This area corresponds to a column height of 5. 6 is greater than 5, so we are able to extend our rectangle into this column. However, 2 is less than 5, so it creates a boundary. Likewise, 1 is less than 5, so it too creates a boundary.

Do you get it now? For every individual column there exists ONE maximum rectangular area that corresponds to that current column’s height. That rectangle is able to extend into the neighboring columns as long as that column has equal to or greater height than the current column’s height.

This is what the optimal algorithm needs to do. It needs to iterate through each of the columns and ONLY calculate the area if it is going to be the maximum area that corresponds to that particular column’s height. It then needs to return the absolute maximum area from all of these local maximum areas.

How do we do this?

How to Solve

When I was trying to solve this problem, I kept thinking to myself that I needed to use a stack. I had a very strong hunch that it could be solved with an approach similar to the one used in this problem.

The only problem was that I just couldn’t figure out how to get it started. Sure enough, when I went to check on the discussion board, there was the solution that I was trying to get to. That solution uses a stack.

Here is how it works:

Look at the height for a column.
If the height is greater than or equal to the first height at the top of the stack or if the stack is empty, push the height onto the stack.
Otherwise pop from the stack. The maximum rectangular area that exists for this popped height is then calculated.
Continue to pop until the top stack height is less than the column height from step 1.

Some really important things to note about this algorithm. I mentioned earlier that the rectangle is able to extend into the neighboring columns only if they are equal to or greater than in height. This is what our stack is going to facilitate for us. As soon as a column is reached that is shorter than the column at the top of the stack, the column at the top of the stack is popped and its maximum area is calculated. The stack creates that boundary for us.

Think about it. Let’s say column B in the stack is positioned right below column A in the stack, but there is also column C that is right below column B. The means that the rectangular area for column B can extend into column A, but it cannot extend into column C. The stack is sorted by height. The lesser heights will always be at the bottom and the greater heights will always be at the top.

The Code

Here is some real top-notch code submitted by LeetCode user @legendaryengineer. You can find the original post here.

Some Illustrations

Let’s take a look at some illustrations to really give us a crystal clear mental picture of what is happening with this algorithm.

Figure A shows the initial setup. The stack is empty, so push i = 0 on to the stack.

Figure A

In Figure B, h = 1 and 1 < 2. The column that has a height of 2 is popped from the stack and its max value (2 x 1) is calculated. The stack is empty.

Figure B

In Figure C, i still equals 1 and the stack is empty. Push i onto the stack.

Figure C

In Figure D, i = 2. The height associated at i = 2 is greater than the height associated with i = 1. Push i = 2 onto the stack.

Figure D

In Figure E, the height associated with i = 3 is greater than the height associated with i = 2. Push i = 3 onto the stack.

Spoiler alert, there is going to be a pop in the next step. Let’s take a look at our stack really quick. If you notice, it is sorted by height. 1 is the minimum height. 6 is the maximum height.

This is what is going to happen in the next step: i = 3 will be popped, and because the stack is sorted, we know that it will not be possible for a rectangle that has a height of 6 to extend into the column that has a height of 5. Also because i = 3 is being popped in the first place, we know that it is not possible for a height of 6 to extend into the neighboring column to the right, either. The maximum area for i = 3 will be 6 x 1 = 6.

Figure E

In Figure F, the height that corresponds to i = 4 is less than the height at the top of the stack. Pop the top, find the maximum area (6 x 1) that corresponds to the popped height, and stay at i = 4 until the height at the top of the stack is less than the height that corresponds to i = 4.

Figure F

In Figure G, the height that corresponds to i = 4 is less than the height at the top of the stack. Pop the top, find the maximum area (5 x 2) that corresponds to the popped height, and stay at i = 4 until the height at the top of the stack is less than the height that corresponds to i = 4.

Figure G

In Figure H, the height at the top of the stack is less than the height that corresponds to i = 4, so i = 4 can finally be pushed to the top of the stack. i is incremented.

Figure H

In Figure I, the height at the top of the stack is less than the height that corresponds to i = 5, so i = 5 can be pushed to the top of the stack. i is incremented.

Figure I

Figure J shows that i = len. This is going to cause everything in the stack to be popped off and each of the maximum areas to be calculated. The maximum area here is 3 x 1 = 3.

Figure J

Figure K shows the maximum area being calculated for i = 4. It is 2 x 4 = 8. Now the stack is empty.

Figure K

Figure L shows the maximum area (1 x 6) being calculated for i = 1. When the stack is empty the width that is multiplied by the height is i. Just a reminder that i = 6 right now.

The width can be i at this point, because if the stack is empty there cannot exist a neighboring column to the left of i = 1 that has a greater height than the height at i = 1.

Figure L

Figure M shows that the stack is empty. Push i = 6 on to the stack. This value of i exceeds the conditions of the for loop. The algorithm is finished.

Figure M

maxArea = 10

Time Complexity

If n is the number of elements in the heights array then n + 1 is iterated through in the for loop. This gives O(n + 1). A total of n elements are popped from the stack, so now it's O(2n + 1). The constant is dropped and only the dominant term is considered. The time complexity is asymptotically equivalent to O(n).

Space Complexity

The space complexity will be O(n) as well. The height of the stack will never exceed the length of heights array.

Learn some more Big-O tips and tricks.

Get Better at Algorithms!

Cracking the Coding Interview — Great resource. Really gets you in the right mindset for interviews. You can find it here.
Elements of Programming Interviews — Another great book. Personally, I like this one more than CTCI, but YMMV. You can find it here.
Grokking the Coding Interview — Can’t emphasize this one enough. Haven’t seen it mentioned it too often. Explains patterns that occur in different coding challenge problems. Great at providing a big-picture of all the different algorithm problems you might encounter. Check it out here.
Grokking Dynamic Programming — Dynamic programming is tough. This course has definitely helped me get a better understanding.
Tushar Roy — Tushar really knows his stuff. His dynamic programming playlist is especially good. Check out his awesome YouTube channel.
Back To Back SWE — Great YouTube Channel. Highly recommend.
Kevin Naughton Jr. — Another awesome YouTube channel. Great at going over problems and gives helpful advice.
Base CS — Vaidehi Joshi does a great job of laying out the fundamentals of algorithms and data structures. Check out the blog series here. She also has a podcast that I give two thumbs up.
Coding Challenge Website — There are plenty of different ones to choose from. HackerRank, CodeWars, and Edabit all seem to be pretty popular. I personally use LeetCode. Find the one that works for you!
Pramp — Do mock interviews! The sooner the better! Pramp has been a huge help to me.

Well, I hope that was useful. Thanks for reading my post and best of luck with your learning about data structures and algorithms!

Dutch National Flag Problem

Daniel Leskosky — Sun, 17 Jan 2021 22:56:56 +0000

I was going through LeetCode problems that I have solved, looking for one that would be good to write a post about. I came across the Dutch National Flag Problem and knew right away that it would be a good one.

LeetCode says that I solved this one on December 12, 2020 at 18:04. I remember this one because I was able to solve it all on my own. Being able to solve a problem all by yourself, certainly is powerful positive reinforcement. I certainly can use a bit of a pick-me-up after last night’s LeetCode Contest. I was only able to answer one question! Oh well, there is always next week.

Before we get into the problem, I just wanted to give some background on it. It was actually first created by Edsger W. Dijkstra. Pretty neat if you ask me. Read more about it here.

The Problem

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

Examples

Example 1:
Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

Example 2:
Input: nums = [2,0,1]
Output: [0,1,2]

Example 3:
Input: nums = [0]
Output: [0]

Example 4:
Input: nums = [1]
Output: [1]

Link to Problem

How to Solve

A good way to think about this problem is to realize that there are three different possible numbers (or colors) that can be in the array. As the array is iterated through, a different action needs to occur for each of the different numbers.

The twos need to all be at the right end of the output array, the zeros need to be all at the left end of the output array, and the ones need to be in the middle.

One of my initial thoughts for this problem was that there would have to be multiple pointers. One pointer to keep track of the lower bound, one for the upper bound, and then one that iterates. The pointers for the bounds will only increment or decrement, when the position that corresponds to that pointer is sorted properly.

Here are the steps:

If the current number is zero, then swap the current number with the number at the lower bound. Increase the lower bound and current index by one.
If the current number is one, increase only the current index by one.
If the current number is two, swap the current number with the number at the upper bound. Decrease the upper bound by one.
Repeat that process until the index for current passes the upper bound index value.

The Code

Here is the code that I came up with. Might not be a one-liner, but I still am pretty proud of it. If you want to see some other solutions, here is a top-rated one and here is another top-rated one too.

Some Illustrations

I find illustrations pretty helpful to better understand the steps involved in an algorithm. Let’s look at some illustrations to help us be able to see this algorithm in action.

Input: [2, 1, 0, 0, 1, 2]

Figure A shows the initial setup. The left is 0, current is 0, and right is 5. nums[current] = 2 and nums[right] = 2, so just right is decremented by one.

Figure A

In Figure B, once again nums[current] = 2, but this time nums[right] = 1. These two values will be swapped. right is decreased by one.

Figure B

In Figure C, nums[current] = 1, so only current is increased by one.

Figure C

In Figure D, nums[current] = 1, so current is again increased by one.

Figure D

In Figure E, nums[current] = 0, so nums[current] is swapped with nums[left] and then both left and current are increased by one.

Figure E

In Figure F, nums[current] = 0, so nums[current] is swapped with nums[left]. left and current are increased by one. currrent is no longer less than or equal to right, so the while loop terminates and nums is returned as output.

Figure F

result: [0, 0, 1, 1, 2, 2]

Time Complexity

If ’n’ is the number of elements in the input array, then the time complexity of this algorithm is O(n), as the algorithm only requires one pass.

Space Complexity

The space complexity of the algorithm is O(1). The algorithm runs in constant space.

Get Better at Algorithms!

Cracking the Coding Interview — Great resource. Really gets you in the right mindset for interviews. You can find it here.
Elements of Programming Interviews — Another great book. Personally, I like this one more than CTCI, but YMMV. You can find it here.
Grokking the Coding Interview — Can’t emphasize this one enough. Haven’t seen it mentioned it too often. Explains patterns that occur in different coding challenge problems. Great at providing a big-picture of all the different algorithm problems you might encounter. Check it out here.
Grokking Dynamic Programming — Dynamic programming is tough. This course has definitely helped me get a better understanding.
Tushar Roy — Tushar really knows his stuff. His dynamic programming playlist is especially good. Check out his awesome YouTube channel.
Back To Back SWE — Great YouTube Channel. Highly recommend.
Kevin Naughton Jr. — Another awesome YouTube channel. Great at going over problems and gives helpful advice.
Base CS — Vaidehi Joshi does a great job of laying out the fundamentals of algorithms and data structures. Check out the blog series here. She also has a podcast that I give two thumbs up.
Coding Challenge Website — There are plenty of different ones to choose from. HackerRank, CodeWars, and Edabit all seem to be pretty popular. I personally use LeetCode. Find the one that works for you!
Pramp — Do mock interviews! The sooner the better! Pramp has been a huge help to me.

Well, I hope that was useful. Thanks for reading my post and best of luck with your learning about data structures and algorithms!

Reveal Cards in Increasing Order

Daniel Leskosky — Sun, 03 Jan 2021 23:19:40 +0000

Although I continue my practice of algorithms, I am still having trouble identifying when to use the appropriate data structure. I recently attempted to solve a problem on LeetCode and completely missed the obvious hints that a queue would be a good data structure to use for the algorithm. This post will provide a detailed solution with illustrations for that problem. While the main purpose of this post is to help others get a clear mental picture of what is happening with the algorithm, I also write this post with the hope that I can work to strengthen my intuition of when to leverage the correct data structure.

The Problem

In a deck of cards, every card has a unique integer. You can order the deck in any order you want.

Initially, all the cards start face down (unrevealed) in one deck.

Now, you do the following steps repeatedly, until all cards are revealed:

Take the top card of the deck, reveal it, and take it out of the deck.
If there are still cards in the deck, put the next top card of the deck at the bottom of the deck.
If there are still unrevealed cards, go back to step 1. Otherwise, stop.

Return an ordering of the deck that would reveal the cards in increasing order.

The first entry in the answer is considered to be the top of the deck.

Example

Input: [17, 13, 11, 2, 3, 5, 7]
Output: [2, 13, 3, 11, 5, 17, 7]
Explanation:

We get the deck in the order 17,13,11,2,3,5,7, and reorder it.
After reordering, the deck starts as [2,13,3,11,5,17,7], where 2 is the top of the deck.
We reveal 2, and move 13 to the bottom. The deck is now [3,11,5,17,7,13].
We reveal 3, and move 11 to the bottom. The deck is now [5,17,7,13,11].
We reveal 5, and move 17 to the bottom. The deck is now [7,13,11,17].
We reveal 7, and move 13 to the bottom. The deck is now [11,17,13].
We reveal 11, and move 17 to the bottom. The deck is now [13,17].
We reveal 13, and move 17 to the bottom. The deck is now [17].
We reveal 17. Since all the cards revealed are in increasing order, the answer is correct.

Link to Problem

Some Thoughts

Before we get to the optimal solution, I wanted to briefly talk about my attempted solution.

My solution only works for the example test case. I was too focused on trying to transform the provided input into the target output. I did not take enough time to consider all possible test cases, or at the very minimum at least test cases of different lengths.

I think it would have helped if I had slowed down a bit. I should have thought more about the problem and asked myself which data structures would be good candidates. A stack or a queue should have been an obvious choice for a problem that is about a deck of cards.

The optimal solution for this problem uses a queue. If you need a refresher on queues then check out this post about queues. The solution will also be storing index values inside of the queue. This is a great technique and I definitely want to get better at recognizing when it is appropriate to use. Here is an algorithm that uses that technique except with a stack.

How to Solve

The solution that will be covered was submitted by LeetCode user @caraxin. Here is the submission. Here are the steps:

Sort the deck, it is actually the “final sequence” we want to get according to the question.
Then put it back to the result array, we just need to deal with the index now!
Simulate the process with a queue (initialized with 0,1,2…(n-1)), now how do we pick the card?
We first pick the index at the top: res[q.poll()] = deck[i]
Then we put the next index to the bottom: q.add(q.poll())
Repeat it n times, and you will have the result array!

The Code

Here is the code for the @caraxin approach. As you can see, the solution is quite succinct and does an amazing job of utilizing a queue. Super smart!

Some Illustrations

This is a perfect problem to use some illustrations to get a clear mental picture of what is going on.

Figure A just shows the initial setup. The queue is filled with index values 0–6, result is initialized, and i = 0. deck has been sorted.

Figure A

q.poll() gives a value of 0. This 0 corresponds to the index for result. result[q.poll()] = deck[i] == result[0] = deck[0]. q is polled again and that polled value is added to the queue. This is shown in Figure B.

Figure B

q.poll() gives a value of 2. This 2 corresponds to the index for result. result[q.poll()] = deck[i] == result[2] = deck[1]. q is polled again and that polled value is added to the queue. This is shown in Figure C.

Figure C

q.poll() gives a value of 4. This 4 corresponds to the index for result. result[q.poll()] = deck[i] == result[4] = deck[2]. q is polled again and that polled value is added to the queue. This is shown in Figure D.

Figure D

q.poll() gives a value of 6. This 6 corresponds to the index for result. result[q.poll()] = deck[i] == result[6] = deck[3]. q is polled again and that polled value is added to the queue. This is shown in Figure E.

Figure E

q.poll() gives a value of 3. This 3 corresponds to the index for result. result[q.poll()] = deck[i] == result[3] = deck[4]. q is polled again and that polled value is added to the queue. This is shown in Figure F.

Figure F

q.poll() gives a value of 1. This 1 corresponds to the index for result. result[q.poll()] = deck[i] == result[1] = deck[5]. q is polled again and that polled value is added to the queue. This is shown in Figure G.

Figure G

q.poll() gives a value of 5. This 5 corresponds to the index for result. result[q.poll()] = deck[i] == result[5] = deck[6]. There are no additional values to poll from the queue. This is shown in Figure H.

Figure H

result: [2, 13, 3, 11, 5, 17, 7]

Time Complexity

The time complexity of this algorithm is O(n * log(n)), where ’n’ is the number of cards in the deck. Let’s go over this a bit.

The array is sorted. Now I think that it depends on the version of Java, but either Timsort, or Dual-Pivot QuickSort is used for Arrays.sort(). This is O(n * log(n)). This might help explain it better too.

Then we need to iterate the length of n to add the index values to the queue. This is O(n). This gives O(2n * log(n)). Then the length of n needs to be iterated for adding the values to result. This is O(n). This gives O(3n * log(n)). The constant is dropped giving O(n * log(n)).

Space Complexity

The space complexity will be O(n). Let’s break it down like we did for the time complexity.

O(n) is required for the result array. O(n) is required for the queue. O(n) is required for the sorting. This totals to O(3n). The constant is then dropped giving O(n).

If you are looking for more tips and tricks for Big-O then you might find this post helpful.

Get Better at Algorithms!

Cracking the Coding Interview — Great resource. Really gets you in the right mindset for interviews. You can find it here.
Elements of Programming Interviews — Another great book. Personally, I like this one more than CTCI, but YMMV. You can find it here.
Grokking the Coding Interview — Can’t emphasize this one enough. Haven’t seen it mentioned it too often. Explains patterns that occur in different coding challenge problems. Great at providing a big-picture of all the different algorithm problems you might encounter. Check it out here.
Grokking Dynamic Programming — Dynamic programming is tough. This course has definitely helped me get a better understanding.
Tushar Roy — Tushar really knows his stuff. His dynamic programming playlist is especially good. Check out his awesome YouTube channel.
Back To Back SWE — Great YouTube Channel. Highly recommend.
Kevin Naughton Jr. — Another awesome YouTube channel. Great at going over problems and gives helpful advice.
Base CS — Vaidehi Joshi does a great job of laying out the fundamentals of algorithms and data structures. Check out the blog series here. She also has a podcast that I give two thumbs up.
Coding Challenge Website — There are plenty of different ones to choose from. HackerRank, CodeWars, and Edabit all seem to be pretty popular. I personally use LeetCode. Find the one that works for you!
Pramp — Do mock interviews! The sooner the better! Pramp has been a huge help to me.

Well, I hope that was useful. Thanks for reading my post and best of luck with your learning about data structures and algorithms!

Odd Even Linked List

Daniel Leskosky — Sun, 20 Dec 2020 21:09:29 +0000

Linked list problems can seem tricky at first, but they aren’t so bad once you get the hang of them. Or so they say. I have yet to get to that point, which is why I am here blogging about it! If you are brand new to linked lists then check out this post. While, reversing linked lists and finding cycles are great problems to start on, this odd even linked list problem is a pretty good one for us beginners as well. Let’s get started!

The Problem

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

Link to Problem

Check out Figure A for an example input and result.

Figure A

How to Solve

For this problem, we are going to create two linked lists. One of the linked lists will contain all of the odd nodes from the original list and the other list will contain all of the even nodes from the original list. Once we have these two lists, the even list will get added on to the end of the odd list.

In this example the list nodes just happen to have values that correspond to their placement in the list. Just a reminder that the problem states that “we are talking about the node number and not the value in the nodes”.

The Code

Let’s take a look at the code to solve this problem. Read through the code and make as much sense of it as possible. Then we can go through it step-by-step and make sure that we understand it completely.

Here are the steps that the algorithm takes:

Create 5 new nodes: oddHead, evenHead, oddNode, evenNode, and current.
oddHead and evenHead do not move during this algorithm. They will keep track of the beginning of the odd and even lists.
Current iterates through the nodes of the list until it reaches null. At each iteration of current, the node that current points to will either be connected to the end of the odd list or the even list.
Once current reaches null, the even list will get connected to the end of the odd list.

Some Illustrations

I know what might be helpful! How about we use some illustrations to help us better understand what is going on in the algorithm.

Take a look at Figure B. It shows what happens in lines 15–21 of the code. This can be thought of as a preparatory step. It is common for linked list problems to have a preparatory step like this. I also want to mention that head is still pointing to the first node. It just isn’t shown to make things a bit clearer.

Figure B

Figure C shows what happens in lines 23–25 of the code. oddNode.next is set to current, current points to the next node, and oddNode now points to where current just was. Also notice that oddHead stays in the same spot.

Figure C

Figure D show what happens in lines 27–29 of the code. evenNode.next is set to current, current points to the next node, and evenNode now points to where current just was. Once again, notice that evenHead stays in the same spot.

Figure D

In Figure E we are back to lines 23–25 of the code. oddNode.next is set to current, current points to the next node, and oddNode now points to where current just was. Take note that current now points to NULL.

Figure E

In Figure F only lines 27–28 of the code are applied because current = NULL. evenNode.next is set to current and evenNode points to where current is. current = NULL and the while loop terminates.

Figure F

Now on to line 32 of the code. oddNode.next is set to evenHead, which results in the even list being added to the end of the odd list. The original head has been brought back just in case you forgot it was still there.

Figure G

Output:

result: [1, 3, 5, 2, 4]

Time Complexity

This algorithm will have a time complexity of O(n) with n being the number of nodes in the linked list.

Space Complexity

The algorithm runs in constant space O(1).

Want to know more about Big-O? I know of a great place to start.

Get Better at Algorithms!

Cracking the Coding Interview — Great resource. Really gets you in the right mindset for interviews. You can find it here.
Elements of Programming Interviews — Another great book. Personally, I like this one more than CTCI, but YMMV. You can find it here.
Grokking the Coding Interview — Can’t emphasize this one enough. Haven’t seen it mentioned it too often. Explains patterns that occur in different coding challenge problems. Great at providing a big-picture of all the different algorithm problems you might encounter. Check it out here.
Back To Back SWE — Great YouTube Channel. Highly recommend.
Kevin Naughton Jr. — Another awesome YouTube channel. Great at going over problems and gives helpful advice.
Base CS — Vaidehi Joshi does a great job of laying out the fundamentals of algorithms and data structures. Check out the blog series here. She also has a podcast that I give two thumbs up.
Coding Challenge Website — There are plenty of different ones to choose from. HackerRank, CodeWars, and Edabit all seem to be pretty popular. I personally use LeetCode. Find the one that works for you!
Pramp — Do mock interviews! The sooner the better! Pramp has been a huge help to me.

Well, I hope that was useful. Thanks for reading my post and best of luck with your learning about data structures and algorithms!

Daily Temperatures

Daniel Leskosky — Mon, 07 Dec 2020 00:15:48 +0000

As I practice more algorithm problems, I sometimes find it challenging to identify the right time to use the appropriate data structure. While, doing lots of problems is a sure bet to develop this perception, I have found that it is also important to have a thorough understanding of what is going on under the hood. I realized this, while making my last blog post. My last post was about trees, queues, and BFS. This one will be about stacks.

The Problem

Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

For example, given the list of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

Link to Problem

How to Solve

Basically, we need to iterate through the list of temperatures. If T[i] < T[i+1] we can enter a 1 in our result array. Otherwise, we need to check T[i+2], T[i+3], … etc against T[i] until we find a value that is greater than T[i]. The appropriate value would then be entered into the result array. It should also be noted that the last value in the result array will always be 0. The last temperature in T has no proceeding temperatures to compare to.

I will be honest. I was not able to solve this problem optimally. My original brute-force solution used a nested for loop to check every temperature against every other temperature. Using nested for loops is not ideal and it resulted in a Big-O of O(n²).

When I looked at solutions submitted by other people, I saw lots of people using stacks to achieve a time complexity of O(n). Being a beginner to all this algorithm stuff, it took me a while to understand how the stack was being used. I think I understand it now. Here is a post on stacks if you need a refresher.

Instead of having to compare each temperature to ever other temperature, a stack will allow us to “archive” index values for the temperature array if a warmer temperature has not been found yet. We can then continue to iterate through the temperature array and if we find a warmer temperature, we simply subtract the “archived stack index” from the index of the warmer temperature.

Hopefully this high-level description will make more sense as we look at the code and then some illustrations of the algorithm in action.

The Code

Here are the steps that the algorithm takes:

Create an array that is the same length as the temperature array.
Create an Integer stack.
The for loop iterates for the length of the temperature array.
There is a while loop that runs for every iteration of the for loop. The while loop will continue to run as long the stack isn’t empty and if the temperature that corresponds to the top value of the stack (which is an archived index value) is less than the current temperature value that the for loop is on.
If those two conditions just mentioned are true then the top value is popped from the stack and a new value is added to the result array.
If one of the conditions is false then the index for the current iteration of the for loop will get pushed onto the stack and the for loop will iterate to its next value.

Some Illustrations

I know what might be helpful! How about we use some illustrations to help us better understand what is going on in the algorithm.

Take a look at Figure A. It corresponds to when i = 0 in the for loop. The stack is empty, so 0 gets pushed onto the stack. i = 0 changes to i = 1.

Figure A

In Figure B, our stack is not empty and the temperature value that corresponds to the top of the stack is less than the temperature value that corresponds to the index of the for loop. A value is added to result and 0 is popped from the stack. The stack then becomes empty which breaks the while loop. 1 is pushed onto the stack. i = 1 changes to i = 2.

Figure B

In Figure C, the stack is not empty and the temperature value that corresponds to the top of the stack is less than the temperature value that corresponds to the index of the for loop. A value is added to result and 1 is popped from the stack. The stack then becomes empty which breaks the while loop. 2 is pushed onto the stack. i = 2 changes to i = 3.

Figure C

In Figure D, the stack is not empty, but the temperature value that corresponds to the top of the stack is not less than the temperature value that corresponds to the index of the for loop. The while loop doesn’t run. 3 gets pushed onto the stack. i = 3 changes to i = 4.

Figure D

Figure E is quite similar to what just happened in Figure D. The stack is not empty, but the temperature value that corresponds to the top of the stack is not less than the temperature value that corresponds to the index of the for loop. The while loop doesn’t run. 4 gets pushed onto the stack. i = 4 changes to i = 5.

Figure E

In Figure F, the stack is not empty and the temperature value that corresponds to the top of the stack is less than the temperature value that corresponds to the index of the for loop. A value is added to result and 4 is popped from the stack. The stack is not yet empty though, so the while loop will continue to run. i = 5 will remain the same as the while loop runs again.

Figure F

In Figure G, the while loop continues with another iteration and i = 5 still. The temperature value that corresponds to the top of the stack is less than the temperature value that corresponds to the index of the for loop.

Here is where it gets interesting. Up until now only values of 1 have been added to result. Now, 5–3 = 2 is being added to result. This is where the stack comes in handy. If the i + 1 of a temperature is not greater than it, then a stack allows us to store the index until we find a temperature that is greater. Then the difference between the two indexes can be added to result.

Ok, let’s get back to Figure G. A value of 2 is added to result and 3 is popped from the stack.

Figure G

The temperature value that corresponds to the top of the stack is not less than the temperature value that corresponds to the index of the for loop. 5 gets pushed to the stack. i = 5 changes to i = 6.

Figure H

In Figure I, the stack is not empty and the temperature value that corresponds to the top of the stack is less than the temperature value that corresponds to the index of the for loop. A value is added to result and 5 is popped from the stack. 2 is now at the top of the stack.

Figure I

In Figure J, the while loop runs again while i = 6. The temperature value that corresponds to the top of the stack is less than the temperature value that corresponds to the index of the for loop. A value is added to result and 2 is popped from the stack. The stack is empty, breaking the while loop. 6 is then pushed onto the stack. i = 6 changes to i = 7.

Figure J

In Figure K, the temperature value that corresponds to the top of the stack is not less than the temperature value that corresponds to the index of the for loop. 7 is pushed onto the stack. i = 7 changes to . . .

Figure K

That’s it! i = 7 is the last index of the temperature array. When an array is initiated it has all zeros by default, so the last two values in the result array will be 0, which is what they should be. As mentioned before, the last value of the result array will always be 0. The temperature at i = 6, which is 76 has no proceeding warmer temperatures, so it gets a 0 as well.

Output:

result: [1, 1, 4, 2, 1, 1, 0, 0]

Time Complexity

As mentioned earlier the time complexity for this algorithm is O(n) with n being the number of elements in the temperature array.

Space Complexity

The space complexity is O(n) as well. The result array will be the same length as the temperature array. Also, the height of the stack will never exceed the length of the temperature array.

If you want some more Big-O tips and tricks then I know of a great place to start.

Get Better at Algorithms!

Cracking the Coding Interview — Great resource. Really gets you in the right mindset for interviews. You can find it here.
Elements of Programming Interviews — Another great book. Personally, I like this one more than CTCI, but YMMV. You can find it here.
Grokking the Coding Interview — Can’t emphasize this one enough. Haven’t seen it mentioned it too often. Explains patterns that occur in different coding challenge problems. Great at providing a big-picture of all the different algorithm problems you might encounter. Check it out here.
Back To Back SWE — Great YouTube Channel. Highly recommend.
Kevin Naughton Jr. — Another awesome YouTube channel. Great at going over problems and gives helpful advice.
Base CS— Vaidehi Joshi does a great job of laying out the fundamentals of algorithms and data structures. Check out the blog series here. She also has a podcast that I give two thumbs up.
Coding Challenge Website — There are plenty of different ones to choose from. HackerRank, CodeWars, and Edabit all seem to be pretty popular. I personally use LeetCode. Find the one that works for you!
Pramp — Do mock interviews! The sooner the better! Pramp has been a huge help to me.

Well, I hope that was useful. Thanks for reading my post and best of luck with your learning about data structures and algorithms!

Make BFS Your BFF

Daniel Leskosky — Sun, 22 Nov 2020 23:15:32 +0000

As I am continuing to learn more about algorithms and data structures, I have found one particular kind of problem that has been giving me trouble: Breadth First Search. Because I was having a hard time grasping this concept, I figured that the best thing for me to do would be to blog about it. So, time to put our differences aside, BFS, because by the time this is over, you and I will be BFFs.

What is this blog post about?

I understand what BFS is on a high level. That is not the problem. The problem is being able to use BFS when solving coding challenge problems. This blog post is going to go over a coding challenge problem that uses BFS. The problem will focus on the level order traversal of a binary tree and break down the problem step-by-step.

However, if you are completely new to BFS, then fear not! Vaidehi Joshi has written a wonderful blog post about BFS. In fact, you might as well check out another post of hers where she has written about Depth First Search (DFS) as well. IN FACT, check out all of her work from her Base CS blog series. I can’t emphasize just how much she has helped me learn about algorithms and data structures. Thanks Vaidehi!

Binary Tree Level Order Traversal

Problem: Given a binary tree, populate an array to represent its level-by-level traversal. You should populate the values of all nodes of each level from left to right in separate sub-arrays.

This problem like most BFS problems will use a queue to perform its search. On the other end of the spectrum, DFS alogrithms typically utilize a stack along with recursion to perform its search. If you are rusty on stacks and queues then use this useful resource to get up to speed. Similarly, if you are rusty on trees then use this other useful resource to get up to speed.

The desired result of the problem seems simple enough to obtain. It is just a nested array with each sub-array representing a different level of the tree. The elements of the sub-arrays contain the values of each of the nodes for each level.

But how do we get to the result? We use a queue. Vaidehi discusses in her BFS post that even though the nodes across a level are not connected, we can still push all of the tree nodes for a level onto the queue and then add the values for those elements to a sub-array which will then get added to the main array.

The Code

Here are the steps that the algorithm takes:

Push the root node onto the queue.
Iterate until the queue is empty. This will be when there are no more tree nodes left.
At each iteration, the number of elements in the queue needs to be counted. This will allow the sub-array for that level to be set to the correct length and also allow for the correct number of iterations.
Then remove the nodes for that level from the queue and add their values to the sub-array.
As the nodes are being removed from the queue insert each of their children nodes into the queue.
Keep doing this until the queue is empty.

Some Illustrations

I know what might be helpful! How about we use some illustrations to help us better understand what is going on in the algorithm.

Take a look at Figure A. The root node gets pushed onto the queue. This happens on line 20 of the code. If you are not familiar with the Java implementation for a queue then check out the docs. Also in line 22 a variable levelSize is created that keeps track of the number of nodes in the queue.

Figure A

The next step is to move the number of nodes that is equal to levelSize out of the queue (line 25). Currently levelSize = 1. So the node that has a value of 1 is removed from the queue and added to a sub-array (line 27). But as that node is leaving, IF it has any children they will get added to the queue (lines 29–32). This is illustrated in Figure B. Finally, the sub-array gets added to the result list (line 34).

Figure B

The node with a value of 1 is no longer part of the queue. Now its children are the only nodes in the queue. These elements are now counted. Notice in Figure C how levelSize now equals 2.

Figure C

Now with a levelSize = 2 the for loop on line 24 allows us to iterate through the two elements of the queue. It should also be noted that a sub-array that is the length of levelSize is created on line 23. The node that contains the value 2 and the node that contains the value 3 are removed from the queue and added to the result list. BUT, as they are leaving, 2’s children and 3’s children are being added to the queue. This is shown in Figure D.

Figure D

Nodes 2 and 3 are no longer in the queue. Nodes 4, 5, 6, and 7 are in the queue. They are counted and levelSize = 4. This is shown in Figure E. Remember lines 29–32? These nodes have no children. They are going to be removed from the queue, but because they have no children, no additional nodes will be added to the queue.

Figure E

I want to mention again that no nodes were added to the queue as nodes 4, 5, 6, and 7 were being removed and added to the result list. The queue is now empty. This terminates the while loop on line 21. Look at Figure F. We now have a traversed tree, an empty queue, and a filled list with the results that we wanted. Neat!

Figure F

Output:

    Level order traversal: [[1], [2, 3], [4, 5, 6, 7]]

Time Complexity

The time complexity for this algorithm is O(N). “N” is the total number of number of nodes in the tree. This is because each node gets traversed once.

Space Complexity

The space complexity for this algorithm is O(N). The result list that is returned contains the total number of nodes (N) that were initially contained in the tree. Also don’t forget that O(N) space is required for the queue. Although the queue at most will contain N / 2 nodes remember that constants are disregarded with Big-O. So O(N/2) is actually just O(N) Similarly, the space complexity of the result list and the space complexity of the queue do not get added together. The final space complexity is O(N).

If you want some more Big-O tips and tricks, then I know of a great place to start.

Get Better at Algorithms!

Cracking the Coding Interview — Great resource. Really gets you in the right mindset for interviews. Sometimes though, I feel that the style of the coding can be confusing. This repo does a great job of filling in the blanks.
Grokking the Coding Interview — Can’t emphasize this one enough. Haven’t seen it mentioned it too often. Explains patterns that occur in different coding challenge problems. Great at providing a big-picture of all the different algorithm problems you might encounter. Check it out here.
Kevin Naughton Jr. — Awesome YouTube channel. Great at going over problems and gives helpful advice.
Base CS— Vaidehi Joshi does a great job of laying out the fundamentals of algorithms and data structures. Check out the blog series here. She also has a podcast that I give two thumbs up.
Coding Challenge Website — There are plenty of different ones to choose from. HackerRank, CodeWars, and Edabit all seem to be pretty popular. I personally use LeetCode. Find the one that works for you!
Pramp — Do mock interviews! The sooner the better! Pramp has been a huge help to me.

Well, I hope that was useful. Thanks for reading my post and best of luck with your learning about data structures and algorithms!

Big-O

Daniel Leskosky — Mon, 09 Nov 2020 00:24:32 +0000

Big-O is pretty important. It is the metric that is used to describe the efficiency of algorithms. Having a thorough understanding of Big-O is crucial for ensuring that algorithms are as efficient as possible. Let’s learn more about this fundamental computer science topic.

What is Big-O?

Imagine that there is a ship builder. Her name is Andrea. She makes big ships and small ships for a port city. She can make the small ships pretty quickly, but the bigger ships take longer. The amount of time that it takes her to build a ship is proportional to the size of the ship.

Andrea is also a pirate. She is known to steal other peoples’ ships. She usually does her pirating in a port town that is 10 days worth of travel by land and 5 days of travel back with the stolen ship, so 15 days round trip. The port town that she pirates from always has the ship size that she is looking for.

If a customer asks Andrea to build a ship, she has two options. She can either build the ship or she could put on her pirate hat and go steal a ship.

So if someone wants Andrea to build a ship for them, which option should Andrea choose? That’s right! It depends.

Build the Ship: O(s): where s is the size of the ship. This is linear time. The time that it takes to build the ship increases linearly depending on the size of the ship.
Steal the Ship: O(1): this is constant time. It doesn’t matter how big or small the ship is. It will always take Andrea 15 days to get the ship back to the customer.

So Andrea should build the ship if she can get it done in less than 15 days. If the ship is big enough that it would take longer than 15 days to build, then Andrea should go steal the ship.

On a side note, this blog does not condone stealing and Andrea should really rethink her life of crime.

Here is a graph that represents the relationship between linear O(s) and constant O(1) time:

There are many more possible runtimes that can occur besides linear and constant. Here is a graph that shows some of the more commonly-used runtimes:

The above complexity chart comes from the Big-O Cheatsheet website. Definitely a useful resource!

The Three Cases

Let’s use quick sort as an example. Quick sort picks a random element as a pivot and then swaps the values so that the elements less than the pivot appear before the elements that are greater than the pivot. Then it uses recursion to further sort the left and right sides. Learn more about quick sort here.

Best Case: The best case means that the algorithm is given the most ideal data. If all elements are equal in the array then quick sort will just have to traverse the array once. Traversing an array of N elements will give a runtime of O(N).
Worst Case: The worst case means that the algorithm is given the least ideal data. With quick sort, it could happen that the pivot is repeatedly the biggest element in the array. If this were to happen then instead of the subarray being recursively divided in half each time, the subbarray would only be reduced by one element. This would give a runtime of O(N²).
Expected Case: Typically instead of having a worst case or a best case you are more likely to have an expected case. Sometimes the pivot will be high and sometimes the pivot will be low, but over time they will average each other out. This will give a runtime more close to O(N log N).

The best case runtime usually isn’t of too much interest when analyzing an algorithm. The worst and expected cases are the ones that need to be considered.

Space Complexity

Space complexity is used to describe the total amount of memory that an algorithm uses in respect to the input size of the algorithm.

If an algorithm requires an array of size n, this will require O(n) space. If there is a two dimensional array of size n by n, then O(n²) space is required.

Some Useful Big-O Tips

There are a couple of tips that you should keep in the back of your mind when you are working on finding the Big-O. Here they are:

No constants
No non-dominant terms
Consider multiple runtimes

No Constants

With Big-O time the constants are not taken into consideration.

“Big-O notation doesn’t care about constants because Big-O notation only describes the long-term growth rate of functions, rather than their absolute magnitudes.”

An algorithm that might seem to be O(2N) is actually only O(N). Here is a Stack Overflow post that does a pretty good job of describing it.

Take a look at some code:

int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int x : array) {
    if (x < min) {
        min = x;
    }
    if (x > max) {
        max = x;
    }
}

The runtime is O(array.length) or O(N).

Let’s take look at some more code:

int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int x : array) {
    if (x < min) {
        min = x;
    }
} 
for (int x : array) {
    if (x > max) {
        max = x;
    }
}

Your first intuition might to be assume that because there are two for loops that iterate the length of the array that the runtime must be O(2N). Don’t fall into this trap! The runtime is O(N). Remember to drop the constant!

No Non-Dominant Terms

What if you get a runtime like O(N² + N)? What should we do then? Well, if you were able to deduce that we should drop the non-dominant term, then congratulations!

Consider the runtime O(N² + N²). This is the same as O(2N²). We know that we should not include constants in our runtimes. So if one of the N² terms is ignored then we can ignore the N in O(N² + N) as well.

O(N² + N) becomes O(N²).
O(N + logN) becomes O(N).
O(5*2^N + 1000N¹⁰⁰) becomes O(2^N).

Consider Multiple Runtimes

If we had to iterate through two arrays of the same length N then we could say that the runtime was O(N) (remember to drop constants!). However what happens if the arrays are of different lengths?

Take a look at some code:

for (int a : arrA) {
    print(a);
} 
for (int b : arrB) {
    print(b);
}

We are iterating through two arrays of different lengths. The runtime is O(A + B). Both runtime lengths must be considered!

Let’s take a look at some more code:

for (int a : arrA) {
    for (int b : arrB) {
        print(a + "," + b);
    }
}

If the arrays were of equal length we could say that the runtime was O(N²). However, the arrays are different lengths. This means that for every element of A, arrB will be iterated through. This results in a runtime of
O(A * B).

Thanks!

Thanks for reading my post. I hope that you found it useful. Once you understand the material presented here, be sure to continue your learning about Big-O.

Here are some topics that you should explore next:

Thanks again!

Stacks & Queues

Daniel Leskosky — Sun, 25 Oct 2020 20:32:53 +0000

Stacks and queues are some pretty neat data structures in my opinion. In some ways they are similar. They are both linear data structures after all. But, there are certainly some key differences. Let’s learn a bit more about stacks and queues, shall we?

What is a Stack?

Let me show you what a stack is. Actually, you probably already know what it is. You just don’t know it yet. Let me describe a common scene in my life that I think that you might be able to relate to.

Hello internet! How are you doing today? Time to get some work done. First let me check my email. Hmm, ok, here is one from that Nigerian prince that I’ve been chatting with, let’s see how he is doing. (opens email) (reads email) Ah, ok, looks like the money that I loaned him is really helping him out. Good. Now let me get back to my other emails. (hits back button)

Ah, here is one about I how I can get my hair line back to where it used to be. (opens email) (reads email) (orders special cream) Ah, good, glad I found this email. My dating life hasn’t been so good lately. This should help. (hits back button)

Ok, here is another one. Learn these 5 easy workouts that Ryan Reynolds does to get shredded. (opens email) Hmm what is this link at the bottom? (clicks link) Smart scientists prove that moon is made of cheese! (clicks another link) (clicks another link) (clicks another link) (clicks another link) Holy smokes! Where am I?! (hits back button) (hits back button) (hits back button) (hits back button) (hits back button) (hits back button) Phew, all right, let’s keep going. Learn these 5 hacks that doctors don’t . . .

In the above scenario we have just witnessed the concept of a stack being used. Can you guess where? That’s right: the back button! Your browser keeps a history of the websites that you visit. As you go from website to website you are also able to go “back” as well. However, you are only able to go back to the immediately previous website. In a nutshell, this is what a stack is. Let me explain.

Think of a stack as several books that are placed one on top of the other. The book that is on top is the only one that can be immediately accessed. If you want to get to a book at the bottom then you have to remove every book that is on top to get there. If you add another book to the stack then that book is now on top and is the one that can be immediately accessed.

The very first book that is put into the stack is the one that has to be taken out last. Similarly, a book that is put in last will have to be taken out first. This is called: Last In First Out (LIFO).

The following figure shows a stack with arbitrary numbers stored as data:

Some Key Terms

Let us become familiar with some key terms for stacks that are used in Java:

push: Inserts an element at the top
pop: Removes an element from the top and returns it
isFull: Returns true if stack is full and false otherwise
isEmpty: Returns true if stack is empty and false otherwise
top: Returns the element at the top

Let us look at some illustrations to help show the push and pop functionalities of a stack. Some arbitrary numbers have been stored into each element of the stack.

The following figure illustrates the push functionality:

The following figure illustrates the pop functionality:

Stack Overflow

You are probably still wondering what a stack overflow is though. Well to put it simply as possible, it is when one too many elements are added to the stack. This happens when the data that is being pushed onto the stack exceeds the memory that has been allocated for the stack.

If you recall in my post about linked lists and arrays I talked about some key differences between the two data structures. The main difference is that an array has a set size while a linked list does not. Both linked lists and arrays can be used when constructing a stack. Although, there really hasn’t yet been a general consensus on which implementation is more efficient. If an array is used as a stack then there is always the possibility of the array size being exceed. While linked lists do not have a fixed size they do require some extra memory to store their pointers.

With an array as the stack, if the stack ends up reaching the capacity of the array then the data can be copied into a bigger array that can hold more data. Although, it should be noted that ultimately it is the use case of the stack that decides whether a linked list or array should be used. Check out this Stack Overflow post for reference.

What is a Queue?

To be honest, I think that the easiest way to understand a queue is to envision a line (or queue) of people. Let’s say that they are at the movies. If someone enters the line then they must enter at the back. That is, of course, assuming that they are a civilized human being and understand how lines work. Additionally, let’s say that it is time for the folks at the very front of the line to get their tickets. Then they would leave the line and go get their tickets. In a nutshell, this is how a queue data structure works.

Queues implement the FIFO method, which is short for First In First Out. According to FIFO, the first element inserted is the one that comes out first.

The following figure shows a queue with arbitrary numbers stored as data:

Some Key Terms

Let us become familiar with some key terms for queues that are used in Java:

enqueue: Inserts elements at the end of the queue
dequeue: Removes an element from the start of the queue
top: Returns the first element of the queue
isEmpty: Checks if the queue is empty
isFull: Checks if the queue is full

Let us look at an illustration to help show the queue and dequeue functionalities of a queue. Some arbitrary numbers have been stored into each element of the queue.

Much like stacks, whether an array or linked list is chosen when implementing a queue ultimately depends on the use case. The same trade-offs that were discussed for stacks apply to queues as well.

It should be noted that there are three different types of queues. The type of queue that has been discussed so far is the linear queue. There is also the circular queue and the priority queue as well.

Summary

After reading this blog post, if you were to remember only two things then it should be this:

Stacks: LIFO
Queues: FIFO

Try to remember the other stuff too though!

I Speak for the Trees

Daniel Leskosky — Tue, 13 Oct 2020 04:17:00 +0000

Trees are similar to linked lists in that they are made up of nodes and links. There are certainly some differences between the two though. Let’s find out what makes a tree a tree.

What is a Tree?

In my previous post I discussed arrays and linked lists. Arrays and linked lists are linear data structures. They are only able to be traversed sequentially. Trees are a bit different. They are non-linear data structures. Non-linear data structures are not organized sequentially like linear data structures are, so it only makes sense that they have to be traversed non-sequentially.

Don’t worry though. This post will not focus on the traversal of trees. Instead, let us make sure that we know what a tree is.

Some Key Terms

Let us start by becoming familiar with some key terms.

Nodes: Hold data
Root: Uppermost node of tree
Link/Edge: The connection between a Parent Node and a Child Node
Parent Node: A node which is connected to one or more nodes on the lower level (Child Nodes)
Child Node: A node which is linked to an upper node (Parent Node)
Sibling Node: Nodes that have the same Parent Node
Leaf Node: A node that doesn’t have any Child Node

Using the above figure, let’s go over some of these terms that we have just learned. A is the root node. A is also the parent node to child nodes B, C, and D. Node C is a parent node to child nodes E and F. Nodes B, C, and D share the same parent node A. This makes them sibling nodes. The same is true for nodes E and F. They are sibling nodes because they both have node C as a parent. Finally, nodes B, D, E, and F are leaf nodes as they do not have any child nodes.

Some More Key Terms

Here are a few more key terms that are helpful for when talking about trees.

Sub-tree: A sub-tree is a section of the main tree. Pick a node from a tree. That node and all of the nodes below it is a sub-tree.
Depth: The distance that a node is from the root node. The easiest way to find the depth is to start at the root node and then count the number of edges that exist between a certain node and the root.
Height: Start at a node. Count the number of edges that exist between the node and its furthest removed leaf node. This is the height.

The figure above shows the depths and heights for the different nodes. Each circled section represents a different sub-tree. There are a total of six different sub-trees.

Types of Trees

This post isn’t going to go into too much detail about the different types of trees. However, it is still a good idea to at least become familiar with some different types of trees that are commonly used.

Ok, let’s at least talk about N-ary Trees for a bit. Think of N simply as the number that describes the parent node with the most children. For example, look at the first figure. Node A has the most children. It has 3. N is 3. That makes it a 3-ary tree. Let’s go the next figure. There isn’t any one node in particular that has the most children. BUT, the most children that any one node has is 2. N is 2. This makes it a 2-ary tree. Or more commonly known as a Binary Tree.

Where are Trees Used?

At this point, you are probably wondering where trees are actually used. Here is a tree structure for you: folders. That’s right, kind of mind blowing right?! When you navigate up and down through directories you are in some respects traversing a tree structure. So, next time you are at a party, be sure to tell your friends that you traverse tree structures on the regular. They will think you are wicked smart.

Or how about this one. I have recently been learning about React, so you can be sure that I was pretty surprised when I learned that the DOM is, in fact, a tree structure.

“The Document Object Model (DOM) is a cross-platform and language-independent interface that treats an XML or HTML document as a tree-structure wherein each node is an object representing a part of the document.”

Do some digging yourself (I had to do at least one pun, sorry). I think you will find that trees are all around us in the great big world of programming!