Mutex vs Semaphore

Mutex: Mutual Exclusion Lock. Allows only 1 thread at a time to enter the protected area/controlled section. Once a thread has obtained a lock, other threads will wait until that thread exists the controlled section and releases the lock. The thread owns/obtains the lock, and only that thread can release it. Only one thread can own a lock a given point. Locking mechanism to control access to a resource.

Mutexs help prevent race conditions. The example usually given here is depositing money into a bank account.

A mutex is essentially a semaphore with value 1, except it differs in how threads "own" the lock.

Semaphore: Allows up to N threads to enter the protected area. Threads increment/decrement the semaphore when they enter the concurrent area and when they leave. So multiple threads can own the lock. More like a signaling mechanism with keeping track of count to access the shared resources.

Producer/Consumer example.

Object in Java

In Java, it's the root class. All objects implement the methods of this class.

clone(), creates and returns a copy of the object

equals(Object), tests whether the two objects are equal to each other.

finalize(), garbage collector calls this method when there are no more references to this object

getClass(), returns the runtime class of the Object

hashCode(), hash code value of the Object

toString(), string representation of the Object

Thread related functions:

notify(), notify/awaken a single thread waiting on this object

notifyAll(), notify/awaken all threads waiting on this object

wait(), causes the current thread to wait until another thread invokes notify

wait(timeout), causes the current thread to wait until another thread invokes notify or the timeout is up

Queue, Deque, Stack

Stack (LIFO, Last In First Out)

In Java, the Stack class extends Vector.

Deque (aka Double-Ended Queue), objects can only be added to or removed from the front or back. Doubly linked list is a good implementation structure for this.

In Java, the Deque class extends Queue.

Queue(FIFO, First In First Out)

In Java, the Queue class extends Collection.

LinkedList is a good data structure to implement all of these.

Methods on these classes

push(Object)

pop()

clear()

isEmtpy()

size()

List in Java

LinkedList, ArrayList, Vector, and Stack all implement this interface.

Important methods on this interface:

add(Object)

add(index, Object)

addAll(Collection)

addAll(index, Collection)

clear()

contains(Object)

containsAll(Collection)

equals(Object)

get(index) //return object

indexOf(Object)

isEmpty()

size()

iterator()

subList(index, index) //return List

toArray()

iterator()

set(index, element), replace specified postion with the passed in element

retainAll(Collection)

removeAll(Collection)

remove(Object)

remove(index)

lastIndexOf(Object) //return index of the last occurrence of this object

ArrayList:

clone()

toString()

removeRange(fromIndex, toIndex)

Vector:

clone()

toString()

elementAt(index)

setElementAt(Object, index)

firstElement()

ElementAtIndex(index)

removeAllElements()

removeRange(fromIndex, toIndex)

Stack, last-in-first-out (LIFO), extends vector

empty()

peek()

pop()

push()

search(object)

LinkedList //implements Deque Interface

descendingIterator - Returns an iterator over the elements in this deque in reverse sequential order.

removeFirst()

removeLast()

removeFirstOccurance(Object)

removeLastOccurance(Object)

peekFirst/Last() //retrieve and don't remove

offerFirst/Last() //insert

pollFirst/Last() //retrieves and removes

Data Binding

There are two types XML data binding and UI data binding. It's a technique that binds data with the backend/ability to access and retrieve that data...I guess you can call it logic. Any change in the data will be reflected in the element bound to that data.

Examples of UI binding: WPF, Cocoa with nibs and variables

UI elements are tied to a variable. Data changes to that variable will be reflected in the UI element immediately. This can be implemented using event triggers or notification/Observer pattern.

Example of XML binding: SOAP
An object is used to represent the XML data. One would access the object to see retrieve data about the XML.

Merge Sort

Merge sort is a divide and conquer algorithm that works by dividing a list continuously and then merging/sorting the smaller lists.

Average and Worst case running time: O(n logn)
n, because you visit all the elements to merge them. log n, because you're constantly split the array in 2, so n/2

Note: It is faster than quick sort because it has a lower constant.

Most implementations of quick sort require O(n) space. That's why some people prefer heap sort which is also O(nlogn) running time, but requires only constant space (O(1)).

An interesting note: Java uses a modified version of merge sort for their sort() algorithm

Implementation of merge sort that you can run:

import java.util.List;
import java.util.ArrayList;

class MergeSort {

   List <Integer> list;
  
   MergeSort() {
       list = new ArrayList<Integer>(6);
       System.out.println("size before we put anything in it: "+list.size());
       list.add(new Integer(1));
       list.add(new Integer(5));
       list.add(new Integer(3));
       list.add(new Integer(4));
       list.add(new Integer(20));
       list.add(new Integer(0));
       list.add(new Integer(6));
       list.add(new Integer(10));
   }

   public static void main (String args[]) {
       MergeSort ms = new MergeSort();
       ms.sort();
   }

   void sort() {
       if (list != null) {
           List<Integer> result = mergesorthelp(list);
          
           for (Integer i: result) {
               System.out.println(i);
           }
       }
   }
  
   List<Integer> mergesorthelp(List<Integer> list){

       if(list.isEmpty() || list.size() == 1) {
           return list;
       }
      
       List<Integer> a, b, result;

       a = mergesorthelp(list.subList(0, (list.size()/2)));
       b = mergesorthelp(list.subList((list.size()/2), list.size()));
      
       result = merge(a, b);
      
       return result;
   }
  
   List<Integer> merge (List<Integer> a, List<Integer> b) { 
       List<Integer> newList = new ArrayList<Integer>();
       int indexA = 0;
       int indexB = 0;
       int sizeA = a.size();
       int sizeB = b.size();
      
       while (indexA < sizeA || indexB < sizeB) {
           if (indexA < sizeA && indexB < sizeB) {
               if (a.get(indexA) > b.get(indexB)) {
                   newList.add(b.get(indexB));
                   indexB++;
               }
               else {
                   newList.add(a.get(indexA));
                   indexA++;
               }
           }
           else if (indexA < sizeA) {
               newList.add(a.get(indexA));
               indexA++;
           }
           else if (indexB < sizeB) {
               newList.add(b.get(indexB));
               indexB++;
           }
       }//end while
      
       return  newList;
   }
}

Simple Java program to test how much time an action takes

public class TimeTest {

public static void main(String[] args) {

int count = 0;

long startTime;

startTime = System.currentTimeMillis();

while (count < Integer.MAX_VALUE) {

count++;

if (count % 1000 == 0) {

System.out.println(count);

}

}

System.out.println("Time in ms: "+ (System.currentTimeMillis() - startTime));

}

}