Find common numbers in arrays: Part 2

Reminder: out problems are

1. How to find the first common integer in two pre-sorted array
2. How to find the first common integer in two unsorted array
3. How to find all the common numbers in two pre-sorted array
4. How to find all the common numbers in two unsorted array
5. How to find all the common numbers in three pre-sorted array
6. How to find all the common numbers in three unsorted array
7. Finally, here is the problem that this series of posts are gonna discuss: How to find all the common numbers in n unsorted arrays

Read the rest of this entry »

Find common numbers in arrays: Part 1

There is a very common problem often asked by interviewers which is How to find the first common number in two arrays. Nevertheless, there are a lot of variations of it. I can easily think a few of them:

1. How to find the first common integer in two pre-sorted array
2. How to find the first common integer in two unsorted array
3. How to find all the common numbers in two pre-sorted array
4. How to find all the common numbers in two unsorted array
5. How to find all the common numbers in three pre-sorted array
6. How to find all the common numbers in three unsorted array
7. Finally, here is the problem that this series of posts are gonna discuss: How to find all the common numbers in n unsorted arrays

Read the rest of this entry »

QuickSort in Java

Quick Sort is an optimal comparison sorting algorithm which provides an average O(n lg n) running time and worst case in O(n^2). It is an in-place, adaptive but not stable sorting algorithm. Although its worst running time is up to O(n^2), we can practically achieve the average time by cleverly choosing the pivot. In the following implementation, the pivot is chosen at the middle of the lowest position and the highest one.

Noted that this implementation referenced Introduction to Algorithms, Data Structures & Problem Solving Using Java and Bragaadeesh’s blog.

Read the rest of this entry »

[LinkedList]An implementation of Singly LinkedList in Java

LinkedList is a well-known data structure which possesses several interesting characteristics. In this post, I provide a basic implementation of SinglyLinkedList, there are a bunch of algorithms inside it and I will discuss them in later posts(Hopefully I have time to do that). I did not make this class to extend any existing class or abstract class like List or AbstractList or AbstractSequentialList because the purpose that I wrote this class is to practice and I don’t want to be restricted by those interfaces.

So, here comes the code. Almost all of the methods have sufficient comments on or inside them, so it should be understandable.

Read the rest of this entry »

An implementation of Disjoint Set(Union Find)

Disjoint sets is a useful data structure, but I am not going to discuss the details of it in this post. This post is to provide a simple implementation of disjoint set which provides the basic operations union() and find(). Some of the codes written reference Introduction to Algorithms.

Read the rest of this entry »