A prime-finding snippet for Java using a 'sieve' method for calculating primes.

find_primes.java

/**
 * This will iterate up-to the sqrt of num 
 * in order to check if it can be written as 'nxn=axb'
 **/
public boolean isPrime(int num) {
  // check for even nums
  if (num % 2 == 0) return false;

  // http://stackoverflow.com/a/5813926
  for (int i = 3; i*i <= num ; i+=2) {
    if (i%num == 0) return false;
  }

  return true;
}

/**
 * Use this as your main function. Looks for primes up-to `ceiling`.
 **/
public List<int> findPrimes(int ceiling) {
  // TODO: null check here!

  List<int> primes = new ArrayList<int>();

  if (ceiling >= 2) {
    primes.add(2);
  }

  for (int i=3; i<=ceiling; i++) {
    if (isPrime(i)) {
      primes.add(i);
    }
  }

  // optional: sysout(primes);

  return primes;
}

notes.md

NOTES

OS

Thread vs Process

Both are independent sequences of execution. Threads are interdependent.

Process

• Is an executing instance.
• Process can have multiple threads.
• Can talk bw each other via IPC (very expensive).
• Starts with a main thread.

IPC

The Linux kernel provides the following IPC mechanisms:

• Named Pipes or FIFOs
• UNIX Domain Sockets
• Signals
• Anonymous Pipes
• SysV Message Queues
• POSIX Message Queues
• SysV Shared memory
• POSIX Shared memory
• SysV semaphores
• POSIX semaphores
• FUTEX locks
• File-backed and anonymous shared memory using mmap
• Netlink Sockets
• Network Sockets
• Inotify mechanisms
• FUSE subsystem
• D-Bus subsystem

For Most of my needs I use sockets.

Thread

• Are paths of execution within a process.
• Threads share same address space within a process.
• Shared space must be synced.
• Less resource-heavy.
• Can perform the same tasks as a process.
• Easier to create (less resource allocation)

Deadlock

Two or more threads wait on other two or more threads for resource control.

Conditions:

• mutual exclusion
• resource holding
• no sys-level preemption mechanism
• circular wait

Thrashing

A thread makes little to no-progress due to excessive context switching.

Livelock

A deadlock, but threads are constantly switching states.

Starvation

A more resource-hungry thread holds onto a given resource, making other threads with less priority wait indefinitely. Often a signal of poor semaphore technique.

Multithreading

Use a thread pool, create new threads (runnable) add them to the pool. When the time comes, run will be called on them.

AES vs MD5

Gorilla vs Shark: one is an encryption algorithm (reversible) whereas the other is a hashing algorithm (one-way encrypt).

Java

Access modifiers

Private => class only

Protected => class, subclasses (diff package), package

No-mod => class, package

Public => world, class, package, subclasses.

Method modifiers

Private

• Method: only available to the class.

Protected

• Method: only available to class & subclasses.

Final

Final method can't be overridden nor hidden.

Final class can't be subclassed.

Final var cannot be reassigned. Blank finals, can only be assigned once, but objects pointed at are still mutable. Careful!

Finalize

Called after an object is eligible for GC. JVM does not guarantee GC. JVM can stop, EOL of proc. etc.

Finally

• A finally block always executes when the try block exits, even if an unexpected exception occurs.
• Useful for cleanup code, ensures it won't be bypassed by a return, continue, or break, even when no exceptions are anticipated.
• Finally won't be called is if you call System.exit() or if the JVM crashes.

Array vs Linkedlist

Array:

• random access (read/writes).
• Expensive operations O(n) if not at the end.
• If out of bounds, needs to be resized O(n)
• Get O(1)
• More memory, regardless of items.
• iterates faster (random access)

Linked list

• Each item has more overhead (previous/next pointer allocation)
• Insertion/Removal is O(1)
• Traverse is O(n) -- sequential access.
• Requires iterators. If used properly, O(1) for add/remove.

Synchronized

Sync works by acquiring a locks on the object and releasing it after a successful return or uncaught exception.

Synchronized Class Method:

class class_name {
    static synchronized type method_name() {
        statement block
    }
}

All the statements in the method become the synchronized block, and the class object is the lock.

Synchronized Instance Method:

class class_name {
    synchronized type method_name() {
        statement block
    }
}

All the statements in the method become the synchronized block, and the instance object is the lock.

Synchronized Statement:

class class_name {
    type method_name() {
        synchronized (object) {
            statement block
        }
    }
}

All the statements specified in the parentheses of the synchronized statement become the synchronized block, and the object specified in the statement is the lock.

Method

• can only lock on this.
• Cleaner API/interface/intent.
• anyone can sync on this :(
• methods need to be splitted.
• Blocks access on the current object.
• On method exit, establishes a happens-before relationship on all subsequent sync calls on the object.
• Guarantees that changes to the state are visible to all threads.

Constructors cannot be synced.

• Final fields are safe to read.
• Static fields use a different lock from the rest of the object.
• Re-entrant sync: a thread can acquire a lock it already owns.

Block

• Can use private/local-only objects to sync.
• Can use different objects (multiple locks) for interleaved sync.
• WARN: when calling methods from other objects.

Web

AJAX

Set of techniques in order to execute code asynchronously on the client. Allows client-server data exchange via XML/JSON.

• JavaScript triggers execution.
• XML/JSON for data transfer.

Mind web crawlers and slow connections/lack of JS.

Improve webapp perf

• Minify CSS/JS
• Cache CSS/JS
• Load order
• Group together scripts/resources
• CSS sprites
• Set max-life/s-max-life
• Avoid inline CSS/JS
• Gif ALL the things! JPG elsewhere.

HTTP

Application-layer and stateless protocol. Communications use a Request/Response pair. Client can create custom headers (are treated as entity headers by the protocol).

Response: URL + Verb:

• GET: Fetch a resource. Analog to READ operations on the DB. Forward when using this.
• POST [DELETE/PUT]: Contains payload data for creating a resource. Analog to CUD operations on the DB. Redirect when using these.

Response: STATUS + MSG body

• 1XX - info messages
• 2XX - success
• 3XX - redirect
• 4XX - client error
• 5XX - server error

A request/response also contains HEAD, TRACE and OPTIONS data.

OPTIONS: server info.

TRACE: server roundtrip info.

HEAD: check resource validity.

HEAD

Use cache-headers to allow storing resources along the way to the client.

CACHE-CONTROL:

• private | public : should only be stored on the client. Declares intent. Use SSL instead.
• no-cache: this resource should be keep up-to date with the source (cookies/dynamic content).
• no-store: sensitive info. Request shouldn't be stored either.
• max-age: sets the cache expiry-date for any resource. Overrides the expires header.
• s-max-age: shared max age, sets the above property on any proxies along the way. Overrides above.
• must-revalidate: do not serve stale content. Warn client if so.
• proxy-revalidate: same as above, applies to proxies (shared content).
• no-transform: skip proxy optimization-transformations.

DB

Transaction unit of work performed by a DBMS on a DB that guarantees a consistent state. Follows ACID:

• Atomic
• Consistent
• Isolated
• Durable

Transactions are "all-or-nothing": either completes successfully or doesn't do anything.

Enqueue: locking mechanism for controlling simultaneous access to a common resource. Uses a mutual exclusion policy for enforcing limits.

Coding

Primes

public boolean isPrime(int num) {
    if (num%2==0) return false;
    
    for(int i=3; i*i<num; i+=2) {
        if (num%i==0) {
            return false;
        }
    }
    return true;
}

public void findPrimes(int ceiling) {
    // TODO: null check
    
    List<int> primes = new ArrayList<int>();
    primes.add(2);
    
    for(int i=3; i<=ceiling; i++) {
        if (isPrime(i)) {
            primes.add(i);
        }
    }
    
    sysout(primes);
}

public boolean[] fillSieve(int ceiling) {
    // TODO: null check for ceiling
    boolean[] primes = new boolean[ceiling];
    
    Arrays.fill(primes, true); // assume all nums are primes.
    primes[0]=primes[1]=false; // except for 0 & 1, of course.
    
    for(int i=2; i<primes.length; i++) {
        if(primes[i]) {
            for(int j=2; i*j<primes.length; j++) {
                primes[i*j] = false;
            }
        }
    }
}

Capicua

public boolean isCapicua(String word) {
    /* All these calls should be separate methods */
    word = word.replaceAll("\\s",""); // trims whitespace
    word = word.replaceAll("\\W",""); // trims non-word chars
    word = word.toLowerCase(); // eases up comparison

    int len = word.length() -1;
    int middle = len/2;

    for(int i=0; i<=middle; i++) {
        if(word.charAt(i) != word.charAt(len-i)) {
            return false;
        }
    }
    
    return true;
}

SQL

Join

SELECT c.name, o.product
FROM customer c
INNER JOIN order o 
ON c.id = o.cust_id
WHERE o.value = 150;

Join

SELECT Customers.CustomerName, Orders.OrderID
FROM Customers
INNER JOIN Orders
ON Customers.CustomerID=Orders.CustomerID
ORDER BY Customers.CustomerName;

AVG

SELECT ProductName, Price FROM Products
WHERE Price>(SELECT AVG(Price) FROM Products);

Having

SELECT Employees.LastName, COUNT(Orders.OrderID) AS NumberOfOrders FROM Orders
INNER JOIN Employees
ON Orders.EmployeeID=Employees.EmployeeID
WHERE LastName='Davolio' OR LastName='Fuller'
GROUP BY LastName, NumberOfOrders
HAVING COUNT(Orders.OrderID) > 25;

Written with StackEdit.

prime_sieve.java

private boolean[] primes;

private void init(int ceiling) {
  primes = new boolean[ceiling];
  
  // remember to import java.util.arrays;
  Arrays.fill(primes, true); // assume everything is a prime.
  primes[0] = primes[1] = false; // save for 0 and 1
}

/**
 * If we're dealing with a prime, discard all its multiples
 **/ 
public void fillSieve() {
  init();
  for(int i = 2; i < primes.length; i++) {
    if(primes[i]) {
      for(int j = 2; i*j < primes.length; j++) {
        primes[i*j] = false;
      }
    }
  }
}

public boolean isPrime(int num) {
  // TODO: null check here
  return primes[num];
}

private void swap(int i, int j) {
  int tmp = arry[i];
  arry[i] = arry[j];
  arry[j] = tmp;
}

quicksort_ruby.rb

# A quick and dirty quicksort in Ruby

def qsort(list)
  return [] if list.nil? || list.size == 0
  x, *xl = *list
  less, more = xl.partition { |n| n < x }
  qsort(less) + [x] + qsort(more)
end

# ramblings...
items = [8,4,9,12,155,5,9,678,2,6]

sorted = qsort(items)

# Pretty format
puts "Sorted (asc): #{sorted.join(', ')}"
puts "Sorted (dsc): #{sorted.reverse.join(', ')}"

puts "Lowest number is: #{sorted[0]}"
puts "Highest number is: #{sorted[-1]}"