Tuesday, July 11, 2017

Sort the odd numbers in array

Given an array of numbers, it is required to sort ascending odd numbers but even numbers must be on their places.

ex:
{ 5, 3, 2, 8, 1, 4 } should give { 1, 3, 2, 8, 5, 4 }
{ 5, 3, 1, 8, 0 } should give { 1, 3, 5, 8, 0 }

Algorithm:
define sorted list
define another list to save the odd number indexes
Iterate through the array for each item
     if item is even skip it
     if item is odd:
           add it to the sorted list
           add the item index to indexes list
loop through the indexes list, for each index
     save the item from the sorted list into the the numbers array at the that index

Note: the sorted list should support duplicate items

Example implementations

Using a list

using System;
using System.Collections.Generic;
using System.Linq;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace sortOdd
{
    public class Program
    {
        static void Main(string[] args)
        {
            CollectionAssert.AreEqual(new int[] { 1, 3, 2, 8, 5, 4 }, Program.SortArray(new int[] { 5, 3, 2, 8, 1, 4 }));
            CollectionAssert.AreEqual(new int[] { 1, 3, 5, 8, 0 }, Program.SortArray(new int[] { 5, 3, 1, 8, 0 }));
            CollectionAssert.AreEqual(new int[] { }, Program.SortArray(new int[] { }));
        }

        public static int[] SortArray(int[] array)
        {
            var result = new int[array.Length];
            List<int> sortedOdd = new List<int>();
            var indexes = new List<int>();
            for (int i = 0; i < array.Length; i++)
            {
                if (array[i]%2 == 0)
                    result[i] = array[i];
                else
                {
                    int index = sortedOdd.BinarySearch(array[i]);
                    if (index < 0)
                        sortedOdd.Insert(~index, array[i]);
                    else
                        sortedOdd.Insert(index, array[i]);
                    indexes.Add(i);
                }
            }
            for (int i = 0; i < indexes.Count; i++)
            {
                result[indexes.ElementAt(i)] = sortedOdd.ElementAt(i);
            }
            return result;
        }
    }
}

Using sorted list 

using System;
using System.Collections.Generic;
using System.Linq;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace sortOdd
{

    public class Program
    {
        static void Main(string[] args)
        {
            CollectionAssert.AreEqual(new int[] { 1, 3, 2, 8, 5, 4 }, Program.SortArray(new int[] { 5, 3, 2, 8, 1, 4 }));
            CollectionAssert.AreEqual(new int[] { 1, 3, 5, 8, 0 }, Program.SortArray(new int[] { 5, 3, 1, 8, 0 }));
            CollectionAssert.AreEqual(new int[] { }, Program.SortArray(new int[] { }));
        }

        public static int[] SortArray(int[] array)
        {
            var result = new int[array.Length];
            var sortedOdd = new SortedSet<int>(new DuplicateKeyComparer<int>());
            var indexes = new List<int>();
            for (int i = 0; i < array.Length; i++)
            {
                if (array[i]%2 == 0)
                    result[i] = array[i];
                else
                {
                    sortedOdd.Add(array[i]);
                    indexes.Add(i);
                }
            }
            for (int i = 0; i < indexes.Count; i++)
            {
                result[indexes.ElementAt(i)] = sortedOdd.ElementAt(i);
            }
            return result;
        }
    }

    public class DuplicateKeyComparer<TKey>:IComparer<TKey> where TKey : IComparable
    {
        public int Compare(TKey x, TKey y)
        {
            int result = x.CompareTo(y);

            if (result == 0)
                return 1;  
            return result;
        }
    }
}

Monday, July 10, 2017

Level order traversal in spiral form

Printing tree in spiral form, or a zigzag form

would print 1 2 3 4 5 6 7
Algorithm

printSpiral(tree)
  set level = tree root
  while level contains nodes
     printLevel(level, ltr)
     set level = getNextLevel(level)
     ltr == !ltr 
Function to get next level
getNextLevel(level)
set nextLevel as empty list
foreach node in level
     if(node.left!=null) nextLevel.add(node.left)
     if(node.right!=null) nextLevel.add(node.right)
Function to print all nodes at a given level
printLevel(level, ltr)
if(!ltr)
    reverse level
foreach node in level
    print node.data

Example code in Java

package com.algorithms.treespiral;

import
java.util.ArrayList;
import
java.util.Collections;

public class
Main {
   
/* Driver program to test the above functions */
   
public static void main(String[] args)
    {
        BinaryTree tree =
new BinaryTree();
       
tree.root = new Node(1);
       
tree.root.left = new Node(2);
       
tree.root.right = new Node(3);
       
tree.root.left.left = new Node(7);
       
tree.root.left.right = new Node(6);
       
tree.root.right.left = new Node(5);
       
tree.root.right.right = new Node(4);
       
System.out.println("Spiral order traversal of Binary Tree is ");
       
tree.printSpiral(tree.root);
   
}
}

class Node
{
   
int data;
   
Node left, right;

    public
Node(int d)
    {
       
data = d;
       
left = right = null;
   
}
}

class BinaryTree
{
    Node
root;

   
/* print spiral order traversal of a tree  */
   
void printSpiral(Node node)
    {
       
boolean ltr = false;
       
ArrayList<Node> layer = new ArrayList<>();
       
layer.add(node);
        while
(layer.size() != 0)
        {
            printLevel(layer
,ltr);
           
layer = getNextLevel(layer);
           
ltr = !ltr;
       
}
    }

   
/* gets the next layer in the tree */
   
ArrayList<Node> getNextLevel(ArrayList<Node> node) {
        ArrayList<Node> nextLayer =
new ArrayList<>();
        for
(Node n:node) {
           
if(n.left != null)
                nextLayer.add(n.
left);
            if
(n.right != null) {
                nextLayer.add(n.
right);
            
}
        }
       
return nextLayer;
   
}

   
/* prints tree level taking direction into account */
   
void printLevel(ArrayList<Node> node, boolean ltr) {
       
if (ltr != true) {
            Collections.reverse(node)
;
       
}
       
for (Node n:node) {
            System.
out.print(n.data + " ");
       
}
    }
}