algomaster, Author at Algo Tutor

0

Print singly linked list in reverse order

Posted on June 16, 2015 by algomaster

Problem:

Printing singly linked list is a little tricky problem because singly linked list only stores address to of the next node, no previous node address is stored in any node.

Logic:

This problem can be solved easily using recursion. Recursively call PrintReverse function till root is not null and start print.

For last node his next is null, so for that null function will return and executing line below recursive call will start execution which will start printing node values. As print line execution starts from last node, linked list will be printed in reverse order.

Implementation:

public void PrintReverse(Node head)
{
  if (head!= null)
  {
    PrintReverse(head.next);
    Console.Write(" " + head.val);
  }
}

1

2

3

4

5

6

7

8

public void PrintReverse(Node head)

{

if (head!= null)

{

PrintReverse(head.next);

Console.Write(" " + head.val);

}

0

Reverse singly linked list

Posted on June 16, 2015 by algomaster

Problem:

In singly linked list, each node contains reference to next node. Address of previous node is not stored in any node, so reverse a singly linked list is a tricky question.

Logic:

For start we will assign previous node as null and currentNode as head of linked list.Till we reach to the last node of list, first store next node in a temporary node and make current node’s next as previous node. Then for next iteration, current node become previous node and nextNode becomes CurrentNode.

Implementation:

public Node ReverseLinkedList(Node head)
{
  if (head.next == null)
  {
    Console.WriteLine(" " + head.val);
    return head;
  }
  Node preNode = null;
  Node currentNode = head;
  while (currentNode != null)
  {
    Node nextNode = currentNode.next;
    currentNode.next = preNode;
    preNode = currentNode;
    currentNode = nextNode;
  }
  head = preNode;
  return head;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

public Node ReverseLinkedList(Node head)

{

if (head.next == null)

{

Console.WriteLine(" " + head.val);

return head;

}

Node preNode = null;

Node currentNode = head;

while (currentNode != null)

{

Node nextNode = currentNode.next;

currentNode.next = preNode;

preNode = currentNode;

currentNode = nextNode;

}

head = preNode;

return head;

}

0

Heap Sort

Posted on June 15, 2015 by algomaster

What is a heap?

Heap data structure is an array that can be viewed as a complete binary tree. Which means each node of a tree corresponds to a element in array. Remember complete binary tree? Complete binary tree is a type of binary tree in which all levels are completely filled except last level which is filled from left to right.

Consider array [4,2,8,3,6,5,1] So first element of array forms a root of a tree.

If we consider array index staring from 1 instead of 0. We can consider how we decide left , right children and parent node of a tree. i is index of array.

Parent : i / 2

Left child: 2 * i

Right child: (2 * i) + 1

If we consider element at index 1 is parent its children will be left child (2*1=2) element at index 2 (2) and right child will be ((2*1)+1 = 3) (8).

If you want to find parent of 6 then you don’t need o picture a tree, using formula one can know that. 6’s index is 5. 5/2=2 so element at index 2 , which 2 is going to be 6’s parent.

If you consider his example, you can see a binary tree can have parent nodes till n/2, if ‘n’ is total number of elements. As each parent will have at the max 2 children, (n/2) + 1 to n will be leaf nodes.

Heap data structure is of 2 types, Max heap and Min heap.

Max heap: Value of parent node is always greater than value of its children.

Min heap: Value of parent node is always minimum than value of its children.

So how heap sort uses min heap or max heap property of heap data structure to sort elements?

Logic:

1. Build a max heap (or min heap depending on the order in which need o sort elements).

2. Place root key in back in array and replace root with leftmost leaf node. Form max heap again and repeat this step again.

Example:

Consider input array as: [4,2,,8,3,6,5]

Implementations:

private void HeapSort(int[] input)
{
   int length = input.Length;
   for (int i = length - 1; i >= 0; i--)
   {
     MaxHeapify(input, i);
     Swap<int>(ref input[0], ref input[i]);
   }
}

private void MaxHeapify(int[] input, int length)
{
  for (int i = length / 2; i >=0; i--)
   {
     int largestIndex = i;
     int max = input[i];
     int left = (2 * i) + 1;
     int right = (2 * i) + 2;
     if (left <= length && input[left] < input[i])
      {
        max = input[left];
        largestIndex = left;
      }
     if (right <= length && input[right] < max)
      {
        max = input[right];
        largestIndex = right;
      }
     if (largestIndex != i)
     {
       Swap<int>(ref input[largestIndex], ref input[i]);
     }
   }
}

public void Swap<T>(ref T a, ref T b)
{
  T temp = a;
  a = b;
  b = temp;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

private void HeapSort(int[] input)

{

int length = input.Length;

for (int i = length - 1; i >= 0; i--)

{

MaxHeapify(input, i);

Swap<int>(ref input[0], ref input[i]);

}

private void MaxHeapify(int[] input, int length)

{

for (int i = length / 2; i >=0; i--)

{

int largestIndex = i;

int max = input[i];

int left = (2 * i) + 1;

int right = (2 * i) + 2;

if (left <= length && input[left] < input[i])

{

max = input[left];

largestIndex = left;

}

if (right <= length && input[right] < max)

{

max = input[right];

largestIndex = right;

}

if (largestIndex != i)

{

Swap<int>(ref input[largestIndex], ref input[i]);

}

public void Swap<T>(ref T a, ref T b)

{

T temp = a;

a = b;

b = temp;

}

Explanation:

1. In each call we are going to do heap by calling heapify function and then swap first element of array(which is root of a tree) with last element of array ( which is leaf node of tree). Now after swapping new root may violate a max heap property, but children are max heaps.

2. In Heapsort call , for loop is from [length-1 to 1] because we will decrease heap size by 1 in each call.

3. In Heapify function call, for loop is from [length/2 to 1] because we know that in array all elements from [length/2+1 to length-1] going to be leaf nodes.

Analysis:

Each call to Heapify function costs O(lg n) time, and HeapSort makes O(n) such calls. So running time for HeapSort is O(n lg n).

Heap sort is in place and stable sorting algorithm.

0

Merge Sort

Posted on June 12, 2015 by algomaster

If you are given 4 red sticks of different heights placed from lower to higher height order and 4 green sticks of different heights placed from lower to higher height order. Task is to arrange red and green sticks together from lower to higher height..

A basic way to do this is to pick smallest by comparing smaller sticks of red and green and place it. Next pick 2^ndhighest stick. Continue this till all sticks are placed in correct order. In Merge sort this basic technique of merging to sorted array is used.

Logic:

Merge sort uses a concept of ‘divide and conquer‘ to sort elements.

a. Divide given elements in half, continue dividing elements unless there is only one element present to sort. As one element is always a sorted element, return and start next step.

b. Merge two elements together in a sorted order. continue merging two sorted sub arrays till all input elements are in sorted order.

Example:

Consider input elements as 4,2,8,1,6,3

Dividing action is performed by calling MergeSort function recursively, in each call mid of array is calculated and two subarrays are formed like input[start to mid] and input[mid+1 to end] and sorting and merging two subarrays is performed by calling Merge function recursively.

Implementation:

private void MergeSort(int[] input, int start, int end)
{
  if (start < end)
  {
    int e = (start + end) / 2;
    MergeSort(input, start, e);
    MergeSort(input, e + 1, end);
    Merge(input, start, e, end);
  }
}
        
private void Merge(int[] input, int start, int middle, int end)
{
 int[] output = new int[end - start + 1];
 int p = start;
 int q = middle + 1;
 int r = 0;
 while (p <= middle && q <= end)
  {
    if (input[p] < input[q])
     {
       output[r++] = input[p++];
     }
    else
     {
       output[r++] = input[q++];
     }
  }
 while (p <= (middle))
 {
   output[r++] = input[p++];
 }
 while (q <= end)
 {
   output[r++] = input[q++];
 }
 int k = 0;
 int i = start;
 while (k < output.Length && i <= end)
 {
   input[i++] = output[k++];
 }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

private void MergeSort(int[] input, int start, int end)

{

if (start < end)

{

int e = (start + end) / 2;

MergeSort(input, start, e);

MergeSort(input, e + 1, end);

Merge(input, start, e, end);

}

private void Merge(int[] input, int start, int middle, int end)

{

int[] output = new int[end - start + 1];

int p = start;

int q = middle + 1;

int r = 0;

while (p <= middle && q <= end)

{

if (input[p] < input[q])

{

output[r++] = input[p++];

}

else

{

output[r++] = input[q++];

}

while (p <= (middle))

{

output[r++] = input[p++];

}

while (q <= end)

{

output[r++] = input[q++];

}

int k = 0;

int i = start;

while (k < output.Length && i <= end)

{

input[i++] = output[k++];

}

Analysis:

Calculating mid of array takes constant time regardless of size of the array . So time complexity of this operation is O(1).

When we combine two sorted array , each element is checked so time complexity for this operation is O(n)

In each step array is divided in half and sort two subarrays of size n/2. So the total time complexity of sorting n elements can be expressed as following :

T(n) = T(n/2) + T(n/2) + O(n) :: T(n)=2T(n/2) + O(n)

By using Master theorem, Time complexity is O(nlog n)

Merge sort uses an extra space to hold two halves so his sort is not a in place sort and space complexity is O(n).

0

Linked List

Posted on June 6, 2015 by algomaster

Linked list is a data structure used to store data in linear order.

We know array , data structure which is used to store data in linear order, then why we need another data structure for same??

Answer to this question highlights main difference between array and linked list. For an array, data always stored in a continuous memory locations. so if I declare array of size 10, depending on size of data type * 10 memory block is reserved for array elements.

However for linked list, no continuous memory allocation is required. In linked list each element stores a data and pointer to (address of) the next element. So no continuous memory allocation require to store data. Each of this structure containing data and address is referred as ‘Node’.

The first element of linked list always referred as ‘Head’ and last node has address as ‘null’.

So what are the advantages and disadvantages of linked list compared to array?

Advantages:

1. Linked list is a dynamic data structure means the number of nodes in a list is not fixed and can grow and shrink on demand. Memory allocation is done when program is running.

2. Insertion and deletion operation is easy to implement compared to array.

3. They can reduce access time and may expand in real time without memory overhead.

Disadvantages:

1. Linked list requires more memory space to store reference of next node.

2. Linked list provides sequential access which means linked list accessed from head. So it is not possible to get element at specific location directly.

3. Time require to access individual element is more.

4. It is difficult to reverse traverse linked list as compared to arrays.

There are three variations in linked list as follows:

1. Singly linked list: This is a basic linked list which is described above. Each node contains pointer to the next element is list.

2. Doubly Linked List: In this list each element store pointer to the next element and a previous element. So for head node previous pointer value is Null and for last node pointer to next element is stored as Null.

3. Circular Linked List: This linked list is like a singly linked list only difference is last node of linked list store pointer of head.

We will discuss basic operations like insert, delete, traverse on each type of linked list in next session..

0

Sum of leaf nodes in binary tree

Posted on June 3, 2015 by algomaster

Problem:

Calculate sum of all the leaf nodes in binary tree.

Logic:

In this implementation we are passing 0 as initial result. When node is a leaf node(left child and right child is null) we are assigning node value to result. At the end of calls we are calculating addition of leaf nodes (that is result returned by each left and right sub-tree’s function call).

int SumOfLeafNodes(Node rt, int result)
{
  if (rt == null)
   return 0;
  if (rt.left == null && rt.right == null)
   {
     result = rt.value;
   }
  return result + SumOfLeafNodes(rt.left, result) + SumOfLeafNodes(rt.right, result);

}

1

2

3

4

5

6

7

8

9

10

11

int SumOfLeafNodes(Node rt, int result)

{

if (rt == null)

return 0;

if (rt.left == null && rt.right == null)

{

result = rt.value;

}

return result + SumOfLeafNodes(rt.left, result) + SumOfLeafNodes(rt.right, result);

}

If you want to understand recursive call and how we will get correct output as result, you can refer this and try to trace this function in same way.

To calculate sum of leaf nodes , all nodes of tree are visited, so complexity of function will be O( n)

Author: algomaster

Print singly linked list in reverse order

Reverse singly linked list

Heap Sort

Merge Sort

Linked List

Sum of leaf nodes in binary tree

Recent Posts

Algotutor