Home



2019/04 - DS&A #1: Basics and Intro

Hey folks,

Last year I began to learn Data Structures and Algorithms through Pluralsight, Lynda (Now called LinkedIn Learning) and a few books. I realised after having some conversations with colleagues that my college didn't really equip me with what I needed to know in this field (Not that you should really blame someone/thing else for your own ignorance mind you).

So I began going through a bunch of resources to teach myself (The Github repo of my results is here). If you don't know your Linked Lists from your Balanced Binary trees, you're in the right place! I'll be going through pretty much everything in the github project linked above, but thought I'd also add a few points below, of preparatory information:

1. If a list is unsorted, it is almost a certainty that no algorithm is going to be more efficient than a basic linear search. This changes if you can search the list multiple times though.

2. A linear search is a super bad method of searching, and is probably what you used when you first started programming as your default form of searching (If you didn't know that already).

(Just for the sake of clarity, this is pseudo-Javacode represents a linear search):

boolean foundNumber = false;

int numberImLookingFor = 3;

for(int i = 0; i < 10; i++){

    if(listImSearching[i] == numberImLookingFor ){

        foundNumber = true;

        return;

    }

}

It just looks through the list from the beginning until either the end or until it finds the number. Not very efficient!

3. You'll pretty much never have to write this kind of code yourself outside of interviews and college classes, as most modern lanuages come stock with their own solutions that you can avail of. You're also not going to come up with a more efficient solution for a Queue (For example) than your languages stock version, except in edge cases, so should just be using that one. The chances of you coming into these kinds of questions in an interview depends on whether the company is international and your experience level. The less experience you have, the more likely you'll be asked them. International companies also love these questions too, especially the big four (Google, Facebook, Amazon, Apple, Netflix and Microsoft. If you're wondering why they're still  called the "Big Four", you're not alone and can count). In Ireland, if you're outside of Dublin, and maybe Cork/Galway, I'd highly doubt that you'll be asked these kinds of questions in an interview.

4. Big Omega Notation is a kind of bastardised term that Computer Science stole from Math to explain the different time/space complexities between algorithms (Because no single algorithm rules them all!). Your solution might be faster than another algorithm in one use case, but slower in another. "Big O" notation provides terms that you can used to express this idea, so that you have an effective way of saying "This algorithm is acceptable on a smaller data set, but will scale very badly with larger data sets". Instead you can just say that it's "Big O(n²)" because the time to complete multiplies over time (Is squared by itself). The algorithm in point 2 is "Big O(n)" because it only increases with the size of the list we are searching. 

5. You aren't going to be using existing data structures/algorithms in your solution. You pretty much get arrays, data types and flow control syntax to work with when developing Data Structures and Algorithms. It makes sense, but you might find yourself thinking "Oh, I know the X library offers a handy solutions for... Ah. I see." when you realise just how much more complex this can make your solution become. In some cases you might go ahead and use an arrayList because it beats having to make your own , but ONLY IF the specific problem you're solving is unrelated to how you're storing your data. It's a way to not have to deal with Amortisation (How a list grows, by how much, when, etc) if you aren't being tasked with such a problem.

So that's it for now, the next post will be on binary trees.

Good luck!
Marc