My software development journey
Given an array which contains some duplicate entries, How do we find the element which appears first and is also repeated.For example let us consider the array [10, 78, 45, 39, 22, 45, 78, 61].The element 78 is repeated and it appears before all such repetitive elements. Note that, though two entries of 45 is…
In this post we discuss how to efficiently implement a stack data structure with one additional operation getMin() along with push() and pop(). getMin() returns the minimum value in the stack. The trick here is to use another stack which stores the minimum values of the original stack. The top of Min-stack always contains the…
Given an array numbers, how do we write a function checkDuplicates() which returns true if the array has at least one element repeated; returns false if all the elements are unique. We discuss three different implementations of this function with various time and space complexities. Method-1: Naive approach This approach checks every possible pair in…
How do you implement a stack using Queue? This is the exact reverse of the problem discussed in my earlier post. We have to use only Queue operations like enqueue(), dequeue() and size() operations to implement push() and pop() operations of the stack. This can be done using two queues. One queue acts as the…
How to implement a Queue data structure using Stack? We have to use only the operations that are supported by Stack ADT*. The methods supported by stack are push(), pop(), and isEmpty(). We have to use only these three operations to implement a Queue. The Queue data structure should primarily support enqueue() and dequeue() operations.…
Given a single linked list, how do you find the middle of the list?One simple method is to traverse through the list twice once to find it’s length, and second to navigate to the middle of the list by traversing length/2 nodes. Even though this method runs in O(n) time, there is still a chance…
In this post we will see an algorithm to find the length of the linked list. Here singly linked list is implemented in Object Oriented Programming (OOP) paradigm in C++. The algorithm is very simple. Just start at the beginning of the linked list, move to next until you reach the end of the list,…