Data Structures and Algorithms: Junior Software Developer nightmare or great oppotunity to have better chance of dreamed job?
This series will focus on really important thing. When I started my adventure with programming I started with creating simple application, without any standards or best practices. I was really proud when my app was able to handle simple button tap and perform some kind of action. After some time later I realized it is not enough to reach dreamed job. There is a lot of topics which every iOS Developer should to know and I think Data Structures and Algorithms is one of them.
Every data structure or algorithm will be covered at seperate story, check list below.
A BST (Binary Search Tree) is a special kind of binary tree which is always sorted. All kind of operations like adding or deleting nodes should not break down the sorted structure.
Before we start er have to talk about few crucial things. Binary Tree is a tree which nodes have not more than 2 children. Why that particullar kind of tree was named Binary Search? Cuz if we want to find some value at BST we are performing searching logic which is working like a Binary Search algorithm. …
There is a lot of searching algorithms for that purpose. Today we will talk about the Binary Search. It’s really nice (and fast! 🚀) way to find a required element.
You can ask, why I have to implement my own searching logic? Collection has
firstIndex(of:) method. That’s true but that method is using linear search and time complexity is O(n) (where n is the number of elements at collection). You can find that information at apple’s developer page (click):
Complexity: O(n), where n is the length of the collection.
Binary search has O(log n), so it is really fast. Of course when we want to find a value which is on the first or second place at collection, linear search will be faster, but when we don’t have any predicates where that value can be, binary search will be much better. The way of working is simple and use few steps, but before we take a look on that, we have to remember prerequisites: Collection must be sorted. …
Queue is the second structure at my list and it is very similar to Stack. Main difference is that, the Queue is using FIFO order (First in First out).
Queue can be build using array with some limited functionality and can handle few operations like adding new elements on the back of the Queue, removing first element from the Queue, and check the first element without removing it.
Stack, what it is?
Basically Stack is a kind of array with limited functionality. Stack is supporting three types of operations: push new element to the top of the Stack, pop the element to remove it from the top and check the element on the top without removing it.
Stack is using LIFO order (Last in First Out). The element which was pushed to the stack last, will be the first one which can be removed from Stack.