Personal Brand: Week 1
Welcome to my blog! I’m excited about today's blog since this post marks the beginning of a new phase in the academy program that I form part of, which is about preparation to pass a programming technical interview.
We all know that interviewing is a hard process that requires study hard and constant practice, this is exactly the purpose of this phase. During the last month I shared in my blogs the concepts that I studied to be prepared, I would like this month to share as well the things that I have been studying, but unlike the last month, I won’t be sharing just definitions but actual code!
My main stack is Python, therefore I’m going to be sharing exercises in this programming language. I will also write about the important aspects that from interviews and my experiences.
For this week, in terms of data structures, I implemented Nodes, Linked Lists, Doubly Linked Lists, Queues, and Stacks. I worked on exercises using these data structures and I also implemented 2 search algorithms, linear and binary search.
Nodes
As you may know, nodes are a basic data structure that contains data and one or more links to other nodes. Nodes can be used, for example, to represent a tree structure or linked lists. Depending on the data structure it might be possible to traverse from one node to another.
As I mentioned, nodes have typically 2 units of data stored. The first is a value and the second is an address that points to the next node. Therefore, if a node has a NULL value as the address for the next node, that implies that we have reached the end of the path we were following since there are no further nodes.
If we have a node A, deleting it means to change the address value of the node before A, to point to the address of the node that's placed after A. For example, if C->A->B, we change the pointer of C to point to B, C->B.
Linked Lists
A linked list is a linear data structure, and its elements are not stored in a contiguous location. In its place, elements are linked through pointers. Linked lists are formed by nodes. Singly-linked lists have nodes with values and a pointer with the address to the next node, doubly linked lists, on the other hand, have values and a pointer to the next and previous nodes.
Linked lists have a head node which is always the first node, if this head node is NULL we can say that the linked list is empty. In addition, if we find a node that has a value and points to NULL, we can say we have reached the end of the list.
If we have a node A (which is a node in the middle of the list), deleting it means to change the address value of the node before A, to point to the address of the node that’s placed after A. For example, if C->A->B, we change the pointer of C to point to B, C->B. The same thing happens when we add nodes.
If we add a node to the head of the list, it is necessary to maintain the list by giving the new head node a link to the current head node.
Check the code for the class Node and the class LinkedList here.
Doubly Linked List
The main difference against singly-linked lists is that we can traverse the list not only from head to tail but also from tail to head. We can add elements to the tail by updating the link of the last tail to point to the new tail.
We can also add to the head by doing the same thing we did with the singly-linked list. This also implies that we can remove elements directly from the tail and from the head.
Check the code for the class DoublyLinkedList and an updated Node class here.
Linked List Techniques
There are different forms of interacting with linked lists that can be useful to accomplish different tasks. These techniques can come in handy to have in your problem-solving repertoire.
Swapping Nodes in a Linked List
A technique where we search through the entire linked list (using while loops and changing our current node with a method like current_node.get_next_node()) until we find the position of the specified nodes to swap so we can arrange the correctly.
The worst-case for time complexity in swap_nodes() is if both while loops must iterate all the way through to the end (either if there are no matching nodes, or if the matching node is at the tail). This means that it has a linear big O runtime of O(n), since each while loop has an O(n) runtime, and constants are dropped. There are four new variables created in the function regardless of the input, which means that it has a constant space complexity of O(1).
Two-pointer Linked List Techniques
By moving pointers over the nodes of a linked list you can solve different problems, for example, you can move two pointers from the head of a linked list, with one pointer moving at a double rate so that when the faster pointer gets at the end of the list, the slower pointer will be located at the middle.
You might wonder why don’t we use lists. One thing that might first come to mind is to use a list to store a representation of the linked list, and then to obtain the nth to last element from this list. While this approach results in an easy-to-read implementation, it could also use up lots of memory maintaining a dual representation of the same data.
Instead, we use two-pointers. This solution has O(n) time complexity, and O(1) space complexity (we always use two variables no matter what size the linked list is: two-pointers).
You can move the pointers at different rates depending on your applications. Check how to find the middle element of a linked list in code here.
Searching Arrays
There are different ways of searching through arrays, depending on how the data is received, one algorithm can perform better than the other. Here I present the implementation of 2 important and very useful searching algorithms.
Linear Search
A searching algorithm that consists of going through each element of an array until the value matches the element that we are searching for, in the end, we will return the index of the element.
This algorithm implies that if the element we are searching for is at the end of the list or is not present in the list at all, we would search through all the elements of the dataset.
This indicates that the Big-O (worst case) runtime for this algorithm is O(N). This means that as the input size increases, the speed of the performance decreases linearly.
Here is the code for linear search.
Binary search
This searching algorithm can only be performed in sorted lists. It consists of the following steps:
- Go to the middle element of the list. If that’s the element we are searching for return its index.
- If the element we are searching for is greater than the value in the middle, do step 1 with the right half (since the left is less than the value in the middle).
- If the element we are searching for is less than the value in the middle, do step 1 with the left half.
Then we can say that a dataset of length n can be divided log n times until everything is completely divided. Therefore, the search time complexity of the binary search is O(log n).
This means that if we have a sorted dataset of 1000 elements linear search will require at most 1000 operations at most, while binary search would require log2(1000) = 10 operations at most. Hence binary search has a better performance. Nevertheless, binary search can only be implemented in sorted lists.
Binary search can be implemented using recursion, reducing the sorted input list by making a smaller copy of the list. This is wasteful since if we have a sorted list with N elements we would be copying N/2 at each iteration.
Instead, we can use pointers that would be indices stores in variables that mark the beginning and the end of the list.
The next implementation is precisely this, an implementation using pointers to use memory efficiently, and also instead of using recursion, we are using loops.
Here is the implementation for binary search.
Queues
Queues are data structures formed by nodes that, as in a line in a ticket stand, items are removed in the same order that they are added. Can be implemented using linked lists.
That is, it follows FIFO (first in — first out) protocol. The main functionalities are enqueue (add a node to the back), dequeue (remove the node at the front), peek (return the node at the front), and is_empty (true is the queue is empty).
Here is the implementation of a queue in python using Nodes. You will need the Node class from linked_list.py.
Stacks
Stacks are also very interesting data structures. They are made of nodes as well and can be implemented using lists. Literally means arranging objects one over the other, just like a bunch of plates.
This means that we can only do operations at the top of the stack. Follows the LIFO (last in — first out) protocol. The three main methods are push (add a node to the top), pop (removes a node from the top), peek (returns the node in the top), and is_empty (true if the queue is empty).
For this data structure, I would like to share a more interesting implementation, which was a project I did about creating a game of Towers of Hanoi using 3 stacks.
Here is the code for the stack. You will need the Node class from linked_list.py.
This is everything for this week's post, I hope you learned a lot! See you in the next post with a lot of new things to share.
