Merge K sorted linked lists/arrays revisited

K sorted arrays

I got a comment on my previous post Merge K sorted arrays, and I realized that there are much easier (and shorter) solutions to solve this problem. Here is the code snippet in both Java and Python.

Java:

public static List<Integer> merged (List<int[]> arrays){
  List<Integer> mergedArrays = new ArrayList<Integer> ();
  if (arrays == null || arrays.size() == 0){
   return mergedArrays;
  }
  for (int[] array : arrays){
   for (int i : array)
    mergedArrays.add(i);
  }
  Collections.sort(mergedArrays);
  return mergedArrays;
 }

Python:

def merged(lists):
    if lists is None or len(lists) == 0:
        return None
    mergedArray = [n for array in lists for n in array]
    return sorted(mergedArray)

Yeah, you can't disagree that the Pythonic way sometimes make things too easy to believe.

Why does this work:
Since in any case, we have to traverse the whole every element in the list of arrays, the complexity is O (mn), where m is the length of the list and n is the average length of each array.  Collections.sort() implements Timsort (see here, here and here) which on average has complexity O(nlogn). The time complexity is the same as using a priority queue, but with much shorter code.


K sorted lists

This gives me a reason to rethink the merge K sorted linked lists problem.
Unfortunately, since we need to return a linked list, we cannot use any built-in sorting methods.
I rewrite the code using Python. In Python, the built-in heapq only provides sorting based on natural order. Since the queue can sort tuples based on its first element, one solution could be wrapping the elements to be sorted to tuples (priority, element). See the code for detail[1].

import heapq
from mergeAndSort.ListNode import ListNode

class PriorityQueue(object):
    def __init__(self, initial = None, key=lambda x:x):
        self.key = key
        if initial:
            self._data = [(key(item), item) for item in initial]
            heapq.heapify(self._data)
        else:
            self._data = []

    def push(self, item):
        heapq.heappush(self._data, (self.key(item), item))

    def pop(self):
        return heapq.heappop(self._data)[1]

    def __len__(self):
        return len(self._data)

    def empty(self):
        return len(self._data) == 0

class ListNode(object):
    def __init__(self, val):
        self.val = val
        self.next = None

def mergeKLists(lists):
    if lists is None or len(lists) == 0:
            return None
    pq = PriorityQueue(key=lambda x:x.val)
    for n in lists:
        if n is not None:
            pq.push(n)
    head = ListNode(-1)
    h = head
    while not pq.empty():
        n = pq.pop()
        head.next = n
        head = head.next
        if n.next is not None:
            pq.push(n.next)
    return h.next

Comparison
Based on Leetcode's compiler, this Python implementation is not faster than the Java one. I'm sure there should be better solutions, please let me know.

Reference:
[1] http://stackoverflow.com/questions/8875706/python-heapq-with-custom-compare-predicate

Graph again (Python and Java, adjacency matrix representation)

I decided to start reviewing data structures and algorithms again, and the first thing I chose is my favorite graph.

There are quite a few ways to represent a graph, the most common two are adjacency matrix and adjacency list. In this post, I use adjacency matrix representation. 

Graph and Adjacency Matrix Representation

A graph (see here for formal definition) contains vertices and edges. Edges are used to connect vertices. Directed graphs have directions (of course!), e.g., edge(a, b) != edge (b, a). Undirected graphs, on the contrary, have no directions, e.g., edge(a, b) = edge(b, a). 

So the question is, how to represent graph in program?

Adjacency matrix representation refers to using a matrix of size (number of vertices * number of vertices) to represent the connectivity, i.e., edges. 

Consider the following graph:

The adjacency matrix representation is as follows:

Each row and column represents a vertex, the cell represents the weight of the edge between them. If there is no edge between two vertices, the weight is 0. In this example, all weights are set to 1, it is possible to personalize the weight, e.g., weight(1, 3) = 2, weight(2, 4) = 0.5. 

Since the graph is undirected, if there is an edge between v1 and  v2, then there is an edge between v2 and v1, so the matrix is symmetric. In case of a directed graph, an edge direct from 1 to 3 leads to a value in matrix[1][3], but that does not indicates there is a value in matrix[3][1], unless there is an edge that directs 3 to 1. 

Traverse the graph

There are two ways to traverse a graph, depth-first search (DFS) and breadth-first search (BFS). DFS goes as deep (yeah...) as it can until all the vertices rooted from one vertex are visited then visit a neighbor vertex. BFS goes as broad as it can until all the neighbors of a given vertex are visited then go to the next level. The following two graphs illustrate the path of DFS and BFS if we start by traversing vertex 3. 

Java code

public class Graph {
 protected int adjacencyMatrix[][];
 protected int size; //number of vertices
 
 public Graph(int size) {
  this.size = size;
  adjacencyMatrix = new int[size][size];
 }
 
 public void addEdge(int v1, int v2) {
  if (validity(v1) == false || validity(v2) == false)
   return;
  if (v1 == v2){
   System.out.printf("Same vertex %d and %d\n", v1, v2);
   return;
  }
  adjacencyMatrix[v1][v2] += 1;
  adjacencyMatrix[v2][v1] += 1;
 }
 
 public void removeEdge(int v1, int v2){
  if (validity(v1) == false || validity(v2) == false)
   return;
  if (adjacencyMatrix[v1][v2] == 0){
   System.out.printf("No edge between %d and %d\n", v1, v2);
  }
  adjacencyMatrix[v1][v2] -= 1;
  adjacencyMatrix[v2][v1] -= 1;
 }
 
 public boolean containsEdge(int v1, int v2){
  if (validity(v1) == false || validity(v2) == false)
   return false;
  return adjacencyMatrix[v1][v2] > 0 ? true : false;
 }
 
 public int getSize(){
  return size;
 }
 
 protected boolean validity(int v){
  if (v >= size || v < 0) {
   System.out.printf("Invalid vertex index %d\n", v);
   return false;
  }
  else
   return true; 
 }
 public void dfs(int startVertex){
  boolean[] visited= new boolean[this.size];
  List<integer> path = new ArrayList<integer> ();
  dfs(path, startVertex, visited);
  System.out.println(getPath(path));
 }
 private void dfs(List<integer> pathList, int v, boolean[] visited){
  if (pathList.size() == this.size)
   return;
  if (!validity(v)|| visited[v]) 
   return;
  visited[v] = true;
  pathList.add(v);
  for (int i = 0; i < this.size; i++){
   if (containsEdge(v, i)){
    dfs(pathList, i, visited);
   }
  }
 }
 public void bfs(int v){
  if (!validity(v)) 
   return;
  boolean[] visited = new boolean[this.size];
  List<integer> path = new ArrayList<integer> (this.size);
  Queue<integer> neighbors = new LinkedList<integer> ();
  neighbors.offer(v);
  while(!neighbors.isEmpty() && (path.size() < this.size)){
   int vertex = neighbors.poll();
   path.add(vertex);
   visited[vertex] = true;
   for (int i = 0; i < this.size; i++){
    if(containsEdge(vertex, i) && !visited[i]) {
     neighbors.offer(i);
    }
   }
  }
  System.out.println(getPath(path));
 }
 public String getPath(List<integer> path){
  String p = "";
  for (int v : path)
   p += String.format("%d -> ", v);
  return p.substring(0, p.length() - 3);
 }
}

Python code:
The easiest way to write a graph using Python is:
To use the SparseGraph class provided by APGL library.

from apgl.graph import SparseGraph
import time
def main():
    graph = SparseGraph(5)
    graph.addEdge(0, 3)
    graph.addEdge(1, 4)
    graph.addEdge(2, 3)
    graph.addEdge(2, 4)
    graph.addEdge(1, 3)

    print(graph.depthFirstSearch(3))
    print(graph.breadthFirstSearch(3))

if __name__ == '__main__':
    start_time = time.time()
    main()
    print("Running time: %f microseconds" % ((time.time() - start_time)*1000))

Where is the fun of writing code?!

Using the same structure as I do in Java:

from collections import deque

class Graph(object):
    def __init__(self, size):
        self.adjacencyMatrix = []
        for i in range(size):
            self.adjacencyMatrix.append([0 for i in range(size)])
        self.size = size

    def addEdge(self, v1, v2):
        if not self.validity(v1) and not self.validity(v2):
            return
        if v1 == v2:
            print("Same vertex %d and %d" % (v1, v2))
        self.adjacencyMatrix[v1][v2] += 1
        self.adjacencyMatrix[v2][v1] += 1

    def removeEdge(self, v1, v2):
        if not self.validity(v1) and not self.validity(v2):
            return
        if self.adjacencyMatrix[v1][v2] == 0:
            print("No edge between %d and %d" % (v1, v2))
            return
        self.adjacencyMatrix[v1][v2] -= 1
        self.adjacencyMatrix[v2][v1] -= 1

    def containsEdge(self, v1, v2):
        if not self.validity(v1) and not self.validity(v2):
            return False
        return True if self.adjacencyMatrix[v1][v2] > 0 else False

    def __len__(self):
        return self.size

    def validity(self, v):
        if v >= self.size or v < 0:
            print("Invalid vertex index %d" % v)
            return False
        else:
            return True

    def dfs(self, startVertex):
        if not self.validity(startVertex):
            return;
        visited = []
        for i in range(self.size):
            visited.append(False)
        path = []
        self._dfsR(path, startVertex, visited)
        print(self.getPath(path))

    def _dfsR(self, path, v, visited):
        if(len(path) == self.size):
            return;
        if visited[v]:
            return;
        visited[v] = True;
        path.append(v);
        for i in range(self.size):
            if self.containsEdge(v, i):
                self._dfsR(path, i, visited)

    def bfs(self, v):
        if v >= self.size or v < 0:
            return
        visited = []
        for i in range(self.size):
            visited.append(False)
        path = []
        neighbors = deque()
        neighbors.append(v)
        while neighbors and len(path) < self.size:
            vertex = neighbors.popleft()
            path.append(vertex)
            visited[vertex] = True
            for i in range(self.size):
                if self.containsEdge(vertex, i) and not visited[i]:
                    neighbors.append(i)
        print(self.getPath(path))

    def getPath(self, path):
        p = ""
        for v in path:
            p += "%d -> " % v
        return p[:len(p) - 3]

Performance
This is always my favorite part. Using the following pieces of test code for Java and Python:

public class GraphTester {
 public static void main(String[] args) {
  final long startTime = System.nanoTime();
  Graph g = new Graph(5);
  g.addEdge(0, 3);
  g.addEdge(1, 4);
  g.addEdge(2, 3);
  g.addEdge(2, 4);
  g.addEdge(1, 3);
  //g.addEdge(1, 5);
  
  g.dfs(3);
  g.bfs(3);
  System.out.println("Running time: " + ((System.nanoTime() - startTime)/1000) + "ms");
 }
}

from graph.Graph import Graph
import time
def main():
    g = Graph(5)
    g.addEdge(0, 3)
    g.addEdge(1, 4)
    g.addEdge(2, 3)
    g.addEdge(2, 4)
    g.addEdge(1, 3)

    g.dfs(3)
    g.bfs(3)

if __name__ == '__main__':
    start_time = time.time()
    main()
    print("Running time: %f microseconds" % ((time.time() - start_time)*1000))

And the result:
Python 0.157 ms vs. Java 4495 ms.
And guess what, using SparseGraph class takes 0.118 ms (feeling good ).

Silicon Valley S2E1: What does Erlich Bachman's binary T-shirt mean?

I saw this Quora question today. It's interesting. Of course as shown in the answer, we can use a binaryToText converter, but what's the fun part if I don't write my own. I am learning Python, so here is the Python and Java version:

Python:

import math
def binaryToText(binary):
 l = len(binary)
 c = 0
 i = 0
 for ch in binary:
  c += math.pow(2, l - i - 1) * (ord(ch) - ord('0'))
  i += 1
 return chr(int(c))

def main():
 Tshirt = ['01000010','01101001','01110100','01100011','01101111','01101001','01101110']
 for t in Tshirt:
  print(binaryToText(t), end = '')
 print('\n')

main()

Java:

public class BinaryToText {
 public static char binaryToText(String binary){
  int c = 0;
  int l = binary.length();
  for(int i = 0; i < l; i++)
   c += (int)Math.pow(2, l - i - 1) * (int)(binary.charAt(i) - '0');
  System.out.println(c);
  return (char)c;
 }

 public static void main(String[] args) {
  String[] Tshirt = {"01000010",
       "01101001",
       "01110100",
       "01100011",
       "01101111",
       "01101001",
       "01101110"
  };
  for(String t : Tshirt)
   System.out.print(binaryToText(t));
  System.out.println();
 }
}

Probably I still haven't got rid of the whole Java class concept, I don't find many advantages of using Python. But, just for fun.

Data Structures in Python compared with Java: Sets

A set is an unordered collection with no duplicate elements. Set models the mathematical set abstraction. Both Python and Java use hashtable as the underlying data structure of set.

Creating a set
Also allows different types of element

#empty set
basket = set()
basket = {'shirley',2014}

Python also allows for creating a character set using the following method:

basket = set('abaabab')

Duplicate elements will be removed.

In Java:

Set basket = new HashSet ()

Of course only one type is allowed.
Java also provide constructor to create a hash set from another collection, if created from a collection that contains duplicate elements, duplicate ones will be removed.

List listA = new ArrayList ();
  listA.add(1);
  listA.add(2);
  listA.add(1);
  Set t = new HashSet (listA);

Union
In Python, it is the same way as you do binary operation:

>>> a = {'shirley',2015}
>>> b = {'dora', 2014}
>>> a | b
{'shirley', 'dora', 2014, 2015}

In Java, we use addAll(Collection<? extends E> c) method:

a.addAll(b);

Complements
Python:

>>> a = set('aabbccabc')
>>> b = set('abdd')
>>> a - b
{'c'}

It will return the elements in a that is not in b.

In Java, we use removeAll(Collection<? extends E> c) method:

a.remveAll(b);

Intersection
Python:

>>> a
{'a', 'b', 'c'}
>>> b
{'a', 'b', 'd'}
>>> a&b
{'a', 'b'}
>>> 

Java: retainAll(Collection<? extends E> c) method:

a.retainAll(b);

XOR (?)
Actually, it is elements in a or b but not both

>>> a
{'a', 'b', 'c'}
>>> b
{'a', 'b', 'd'}
>>> a^b
{'d', 'c'}

I couldn't find any built in methods to do this in Java, however, we can always do a little bit coding to acquire the desired result:

Set a = new HashSet ();
  a.add(1);
  a.add(2);
  Set b = new HashSet ();
  b.add(2);
  b.add(6);
  Set c = new HashSet(a);
  c.removeAll(b);
  Set d = new HashSet(b);
  d.removeAll(a);
  c.addAll(d);

Sorted sets:
Java provides TreeSet data structure. It is based on red - black tree implementation (See here for implementations). In Python, I think this needs to be acquired by using lambda function(?). I am not quite familiar with the lambda function, but I will take a look later.



References:
[1]. Not-very-familiar Python doc
[2]. www.grepcode.com
[3]. Beloved Java doc
[4]. www.codatlas.com

Data Structures in Python compared with Java: Array, List, and ArrayList

At the hardware level, most computer architectures provide a mechanism for creating and using 1-D arrays. A one-dimensional array, is composed of multiple sequential elements stored in contiguous bytes of memory. The entire contents of an array are identified by a single name. It holds a fixed number of values of a single type. The length of an array is established and fixed and the array is created.

Python doesn't have a native array data structure. but it has a more general list structure. The list can grow and shrink during execution as elements are added or removed while the size of an array cannot be changed. However, the tradeoff here is that it needs more space, which allows for quick and easy expansion as new items are added to the list.

Another difference is that while the array only allows single type, the list in Python allows multiple types:

list1 = ['shirley','2014']
list2 = ['dora','shine']
list3 = [2011, 2015]

Note that the list is also implemented using an array structure to store the items. When the list() constructor is called, an array structure is created. The array is initially created bigger than needed, leaving the capacity for future expansion. If the number of elements added to the list exceeds the capacity (which is larger than the initial size) of the list, a new array with a larger capacity is created and an array copy is followed.

In Java, the best analogy should be ArrayList. A slight difference is that the ArrayList in Java only allows single type and initialize an array with very small capacity (10) if not predefined.

Creating an empty list:

list = []
#create a list of None with size 256
list = [None]*256
list = list()

In Java, everything is instantiated with the new operator:

int[] array = new int[10];
List arraylist = new ArrayList();

Extending a list:
Python provides built in method to append one list to another:

list2.extend(list3)

In ArrayList in Java, that is:

arraylist.addAll(arraylistB);

Inserting items:
In Java, neither Array or ArrayList allows this operation:

list1.insert(2, "Jesse")

However, since the list is still array based, this operation requires shift the elements from index 2 to the right then insert "Jesse" to index 2.

Slicing:
Slicing is an operation that creates a new list consisting a contiguous subset of elements from the original list. References to the corresponding elements are copied and stored in the new list:

list4 = list1[startIndex(inclusive) : endIndex(exclusive)]

JDK 8 provides a similar method subList(int fromIndex(inclusive), int toIndex(exclusive)) (here for src):

List sublist = arrayList(1, 3);

Creating 2-D array/list:
In Python, this involves creating a list containing m lists initialized to 0:

matrix = [[] for x in range(rows of the matrix)]

Similarly, you have to at least initialize 1 dimension when creating a 2-D array.

Alternatively, you can use library numpy:

import numpy
numpy.zeros((m, n))

Well, in Java, this is much easier:

int[][] matrix = new int[m][n];

References:
[1]. Data structures and algorithms using Python. Wiley Publishing, 2010.
[2]. www.grepcode.com
[3]. Beloved Java doc
[4]. www.codatlas.com