Binary search algorithm is a widely used algorithm for sorted sequences. It can be utilized not only for searching, but also for sorting and proving hypotheses on ranges.
The idea of the algorithm is quite simple:
divide the range equally into 2 parts
only the potential part of the range will be used for further processing.
For example, if we want to find some value in a sorted array: – we divide the array into 2 equal parts – we continue searching in potential parts that may contain the searchable value, and skip the other part.
Binary search algorithm is quite fast. Is time complexity is O(log n).
The BFS algorithm in Graphs implies the following:
predefine a list of visited nodes
create a queue instance, put the starting node in the queue
while a queue is not empty: – poll the queue, take the head element – if the head element has already been visited, continue the loop – analyze the value of the retrieved node and mark it as visited – put to the queue all child nodes
time complexity: O(n)
space complexity: O(m), where m is the maximum graph width.
Graph DFS algorithm is so similar to DFS in Trees. Two differences: – a graph node can have more than 2 children – a node can be visited multiple times, hence we must mark the visited node to prevent repeated processing.
Text description of the algorithm: – predefine a list to store all visited nodes – start DFS from the root node, pass the list of visited nodes as an argument – if the current node has been already visited, return from the recursive function – run a DFS on all child nodes
Time complexity: O(n).
Space complexity: O(m), where m – maximal depth of the graph.
There are 2 approaches to traversing a binary tree: use Depth-First search (DFS) and Breadth-First search (BFS). In case of BFS, we process the tree as follows:
Iterative processing:
start from the root node
push current node into queue
while the queue is not empty: – poll the queue to retrieve node to process – analize the value of the retireved node – put to the queue both childs of the retireved node.
Recursive processing:
start from the root node
push current node into queue
if the queue is not empty: – poll the queue to retrieve node to process – analize the value of the retireved node – put to the queue both childs of the retireved node.
make a recursive call to itself
Time complexity: O(n)
Space complexity: O(l), where l – max width of the tree
There are 2 approaches to traversing a binary tree: use Depth-First search (DFS) and Breadth-First search (BFS). In case of DFS, we process the tree as follows:
In-Order processing:
make a recursive call on the left child (1)
analyze node value (2)
make a recursive call on the right child (3)
Pre-Order processing:
analyze a node value (1)
make a recursive call on the left child (2)
make a recursive call on the right child (3)
Post-Order processing:
make a recursive call on the left child (1)
make a recursive call on the right child (2)
analyze a node value (3)
Time complexity: O(n)
Space complexity: O(m), where m – max depth of the tree
To implement a simple binary tree, firstly we have to create a traverse function.
Traverse function
Node<T>[] traverseDFS(Node<T> root, T value, Node<T> parent)
is used to find node with a required value or to find an appropriate insertion position for a value. For example, if this function returns the node with the exact value, it means that the tree contains that value. And if the function returns a node with a different value, it means the returned node might be a good parent for the new node.
The algorithm of traverse function: – if the required value is less than the current value and a left child exists, re-run the traverse function on the left child – if the required value is greater than the current value and a right child exists, re-run the traverse function on the right child – otherwise return the current node.
And only then we will able to build the following methods:
Node insert(T value). – run a traverse function on the root node, use the return value as the parent for the new node
Node lookup(T value) – run a traverse function on the root node. If the return value is equal to the search value, hence the tree contains a searchable value.
Node remove(T value) – run a lookup by value. If returned value is not equal to the search value, then return null. Let’s consider 4 possible cases: – the node to be deleted doesn’t have children: remove the node link from the parent. – the node be deleted has only a left or right child (successor): connect the parent node to the successor. – the node to be deleted has both childs: find in the right subtree the closest greater value to the value to be deleted, put the found value in the place of the node to be deleted, remove the found node (use a recursive call).
Time complexity: – insert, lookup, delete – in worst case O(n)
Space complexity: – insert, lookup, delete – in worst case O(n), because we need to store a stack for recursive calls.
Implementation of the Queue is so similar to a Stack. We operate with the queue using a FIFO-approach: add elements to the end (tail) of the queue and retrieve (poll) from the head.
General points of the algorithm:
Store the head and tail in the class fields.
Implement the add(…) method to extend the queue and poll() methods to retrieve the first (head) element.
add(…) appends the queue and assigns the tail to the previous node.
poll() method retrieves the head element and reassigns the new head to the previous element.
Time complexity: O(1) for the add(..) and poll() methods.
Space complexity: O(1) for the add(…) and poll() methods.
Stack is also a type of LinkedList, but without the ability to retrieve i-th element. We can only retrieve (pop) the last added element and add (push) a new element to the top of the stack (LIFO approach).
General points of the algorithm:
Implement the push() method to add an element to the top of the stack. Store the last previous element (tail) in the “prev” property of the new tail.
Implement the pop() method: retrieve the tail node and reassign the tail to the previous element.
Time complexity: O(1) for the push() and pop() methods.
Space complexity: O(1) for the push() and pop() methods.
The task of implementing LinkedList can also be encountered during interviews with newcomers. The solution depends on the type of list you require: unidirectional (singly linked) or bidirectional. The following implementation uses a unidirectional (singly linked) LinkedList.
General points of the algorithm:
Store head and tail in the class fields.
Create the following methods: – void add(T value) – void remove(int i) – T get(int i)
Method add(…) is used for add a new node to the list: set the new node as a next node of the tail and reassign the tail.
Method remove(int i) is used to remove i node in order. Iterate through the list, incrementing the counter to position on the correct node. Reassign the tail of the previous node to the next one after the removed node.
Method get(int i) is used accordingly own name to get i node in order the list. To do this, iterate through the list, incrementing the counter to position on the desired node, similar to the remove method.
Time complexity: – add(…): O(1) – remove(int i): O(n) in worst case – get(int i): O(n) in worst case
The task to implement a HashTable is the most popular one in interviews.
General points of this algorithm:
Use an array of buckets to store “key-value” pairs .
The number of current bucket is a reminder of the hashed key value divided by the number of buckets.
Usually it’s enough to implement the following methods: – void set(String key, T value) – T get(String key) – List keys()
Method set(…) includes the following logic: – calculate the number of bucket to store the “key-value” pair – if the bucket is empty, store the “key-value” pair – if the bucket is not empty, find the last pair in the stored linked list and add a new pair
Method get(…) implies similar logic to the set method: – calculate the number of bucket to store the “key-value” pair – find a matching pair in a stored linked list by comparing the keys
Method keys(…) does the following: it iterates through the bucket array and retrieves all the keys of each pair in the stored linked list.
Time complexity: – set: O(n) in worst case – get: O(n) in worst case – keys: O(n)