Algorithms & DataStructures

Algorithms on Arrays

TIPS: Algorithms on arrays can be dealt with pointers. Taking pointers one at the beginning of the array and one at the end of the array (using length of the array) will be helpful in solving array algorithms.

algorithm to remove element from an array: 1. standard way when existing order is important: traverse through the elements, once element_to_be_deleted is found, shift remaining…

algorithm to merge two sorted arrays without additional array Algorithm to merge two sorted arrays: Here we use merge sort logic…

find all pairs in an array, that sum up to particular number with best complexity: Here we discuss two possible algorithms…

finding three elements in an array whose sum is equal to a given number Here, for every element(arr[i]) that we pick, trisum-arr[i] gives us the …

find intersection of elements in two arrayscase 1: Two arrays are unsorted; Case 2: Two arrays are sorted; case 3: Two arrays are unsorted;

find group of connected 1s in a matrix Consider a two-dimensional grid of cells, each of which may be empty or filled. The filled cells that are connected form a sector…

subsequence of array with maximum sum (Kadane’s Algorithm): This is given by Jay Kadane. Problem Statement: In a given array, find out subarray such that the sum of its elements is maximum… *note* Dynamic Programming

Algorithms on Strings

TIPS: Algorithms on Strings/Character_Arrays can be dealt with pointers. Taking pointers one at the beginning of the array and one at the end of the array (using length of the array) will be helpful in solving string algorithms.

algorithm to reverse a string in O(n/2) complexity: There are many ways of reversing a string but best possible case should be considered keeping space and time complexities in mind. Psuedocode for O(n/2) complexity…

algorithm to reverse words of a string: This is a bit tricky algorithm and most frequently asked question in interviews. I will now show how to do it in best time complexity [O(2n)]….

algorithm to find first unrepeated character in a string: We can do it in two different ways; Algorithm with O(2n) time complexity and O(1) space complexity; Algorithm with O(2n) time complexity and O(n) space complexity

algorithm to find substring in a string (KMP Algorithm): Knuth-Morris-Pratt Algorithm (KMP) detailed analysis – Understanding this would show us what a careful algorithmic thinker would code even for a small problem like this. This is one of the algorithms which is easy to implement but one needs lot of attention and hard work to understand the algorithm.

Algorithms on Binary Trees

TIP: To crack algorithms on binary search trees we need to be good at recursion, usage of queues and stacks. Imagining the traversal of BST is important and then decide whether to use queue or stack based on the traversals.

spiral traversal of binary tree: This can be done using two stacks in iterative manner. The below diagram depicts the spiral traversal of BST …

algorithm to find left view and right view of binary tree in java: This algorithm is an extension of breadth first search. In BFS we just print level wise nodes whereas here while printing level wise …

find depth of binary search tree We can find the depth of binary tree in three different recursive ways; 1. using instance variables to record current depth and total depth at every level….

print level wise nodes in the binary tree This can be achieved using breadth first traversal algorithm. 1. push level wise nodes into the queue at every iteration. 2. pop the node from queue at every iteration and print its value

how to print leaf nodes in a binary search tree The logic here is simple. Recursively go through left and then right elements, when it goes beyond these two recursive calls, ..

types of traversals in a binary tree There are three types of traversals in binary tree: pre-order, in-order and post-order …

Algorithms on Lists

TIP: Algorithms on lists can also be dealt with pointers. Taking pointers with different speeds can sometimes help us solve problems in linked lists.

algorithm to find if a linked list is cyclic: The best way of doing it is to take two pointers. For every step taken by one pointer, move another pointer two steps. In this manner if there is no cycle in the linked list(i.e, if …

algorithm to find if two linked lists are intersected: Two different lists will be intersected when one node of a list points to the other list’s node. The below diagram depicts the intersection of lists…

algorithm to remove element from single linked list: In this algorithm we were not given with the head node but instead given with the node that is to be deleted…

print single linked list in reverse orderThis is frequently asked question as we would be having only forward reference but not the backward reference to traverse the single linked list (SLL) in backward direction. We can do it recursively or by using LIFO data structure…

algorithm to find middle element of linked list @ O(n/2) order: Since every node in a linked list has the reference to its next node, we can achieve this solution by taking two pointers. For every increment in one pointer, increment the second pointer twice, in this way by the time second pointer…

algorithm to find nth last element of a single linked list: We can do this in two ways. 1. Recursive Approach; 2. Iterative Approach…

Searching Algorithms

best searching algorithm: Consider a data structure, say, array ‘a’ of size m: Linear Search with complexity O(n); Binary Search with complexity O(log n); Search using HASH value with complexity O(1)

Sorting Algorithms

Understanding quicksort algorithm: On an average Quicksort Algorithm has the complexity of O(nlogn) and in the worst case it has O(n^2) when the elements of the input array are..

Analogy between Binary Search Tree and Quicksort Algorithm: BST and Quicksort Algorithm are similar in nature in almost all the factors, like time complexities, and number of comparisons…

Other Algorithms

decimal to binary/octa/hexadecimal conversion: Here decimal to binary/octa/hexa decimal conversions are shown. Algorithm is simple provided we should make use of the stack (stack implementation) to put the coefficients.

Towers of Hanoi Recursive Ananlysis: Recursive program to towers of hanoi problem. For 2 discs we need 3 iterations, 3 discs we need 7 iterations, 4 discs we need 15 iterations, etc…

What is BIG(O) NOTATION: BIG O Notation is used to represent complexity of an algorithm in worst case scenario. Complexity in computer programming can be defined in terms of time and space….

order of hashmap/hashtable in BIG-O Notation: Order or complexity of any hash implemented data structure in java is O(1). O(1) means the time to retrieve…

Queue implementation in Java: Queues operate in FIFO model. Queues are also used in various other data structures, some of them are…

Stack implementation in Java: Stacks operate in LIFO model. Stack plays vital role in many data structures, some of them are: in parsing arithmetic expressions…

Mawazo

Mostly technology with occasional sprinkling of other random thoughts

amintabar

Amir Amintabar's personal page

101 Books

Reading my way through Time Magazine's 100 Greatest Novels since 1923 (plus Ulysses)

Seek, Plunnge and more...

My words, my world...

ARRM Foundation

Do not wait for leaders; do it alone, person to person - Mother Teresa

Executive Management

An unexamined life is not worth living – Socrates

Diabolical or Smart

Nitwit, Blubber, Oddment, Tweak !!

javaproffesionals

A topnotch WordPress.com site

thehandwritinganalyst

Just another WordPress.com site

coding algorithms

"An approximate answer to the right problem is worth a good deal more than an exact answer to an approximate problem." -- John Tukey