Crea sito

Algorithms and Data Structures Archive

Find the missing number in two Arrays

PROBLEM: Let A,B be two Arrays. Suppose B is a sub-array of A and there is one element that appears only in A. Find the element of A that is missing in B. Example: A = 1, 5, 6, 3, 4, 2 B = 6, 3, 5, 1, 4 Output: 2 IDEA: If you want

Find the Number which occurs odd number of times

I’m practicing again with Algorithms and I’ve found an interesting Algorithmic Challenge named “Find the Number which occurs odd number of times in an Array”, so I have decided to try it and fortunately I solved it, but not without any problem. I want to show you what the challenge exactly was and the code

How to find the maximal sum in Array in Java

INTRODUCTION TO THE ALGORITHMIC PROBLEM: Imagine that you receive a 50$ gift card which can be used in a famous shop of your town. You can use this gift card to buy only two items and the sum of their prices must be lower than 50$. This shop has a lot of products and you

Find the most frequent number in Array in Java

We will se how to find the most frequent number in an Array in Java, by sorting it and using only one for loop. Before watching the code, remember that this code runs, in worst case, in O(n^2). Because the for loop runs in O(n) but the static method sort() of the class use

Convert Binary Tree to Linked List in Java

We will see how to convert a Binary Tree (or Binary Search Tree in this case) to a Linked List. In the web I saw some examples on how to convert to a Doubly Linked List, but this is not the case. The idea of this conversion is to have 5 java classes: the main,

Implement a Queue as Linked List in Java

A Queue is an Abstract Data Type that can be implemented in various way, the two best ways are Arrays and Linked List. Below you will find the running Java code to implement a Queue using a Linked List, in particular a Head Tail Linked List, which worst case running time for insertion is O(1)

Print a Linked List in reverse order in Java

Printing a Linked List in a reverse order, in this example in ┬áJava, could be computed very easily using recursion. However this method requires a good knowledge about Recursion to be understood. In order to refresh you about Linked List, i’ll first repost the normal code to print a Linked List: public static void print(List

Create a Binary Search Tree (BST) from scratch

Today we will see how to create and implement a Binary Search Tree (BST) from scratch in Java. I think that if you’re here it means that you know what’s a BST and so it’s useless to write another time all the theory of this Data Structure. Let start, remember that we need three files

Head Tail List in Java from scratch

UPDATE SEPTEMBER 22, 2016: The method insert(Node x) of was not optimized, now I have fixed it and his running time becames O(1)! Creating a Head Tail LinkedList, this case in Java, it’s similar to the creation of a simple LinkedList, but with a pointer pointing to the tail. Obviously the worst case running

OrderedList from scratch (Java)

In order to create, in Java, an Ordered List (Data Structure) you need four files: I’m not going to explain you what an Ordered List is, ’cause if you want to create it from scratch I hope you know what are you going to do. So I rapidly post the four