K Nearest Neighbors (Linear Implementation)

02 Oct 2012 | By Mihai Roman | Comments | Tags algorithms javascript adobe node

O(Nd) implementation of the K-nearest neighbor problem in JavaScript.

var Point = function(x, y, d) {
  this.x = x || 0;
  this.y = y || 0;
  this.d = d || Number.MAX_VALUE;
  
  // Square of the Euclidean distance.
  this.dist2 = function(point) {
    var dx = this.x - point.x;
    var dy = this.y - point.y;
    this.d = dx * dx + dy * dy;
    return this.d;
  }
  
  return this;
};

// Returns the array of the nearest d points from point p.
// points: array of points.
// p: origin point.
// d: number of points to extract.
var knearlin = function(points, p, d) {
  if (d >= points.length) {
    return points;
  }
  
  var result = [];

  // Initialize the result with far away points.
  for (var i = 0; i < d; i++) {
    result[i] = new Point();
  }
  
  for (var i = 0; i < points.length; i++) {
    // Calculate the distance from point p.
    points[i].dist2(p);
    
    var found = false;

    // Search for a spot to insert the current point
    // into the sorted result array.
    for (var k = 0; k < d && k <= i; k++) {
      if (result[k].d > points[i].d) {
        found = true;
        for (var j = d - 1; j > k; j--) {
          result[j] = result[j - 1]
        }
        result[k] = points[i];
      }
      
      // Point was inserted.
      if (found) {
        break;
      }
    }
  }
  
  return result;
};

// Some testing helper code
var circle = function(center, r) {
  var result = [];
  result[0] = new Point(center.x, center.y + r);
  result[1] = new Point(center.x + r, center.y);
  result[2] = new Point(center.x, center.y - r);
  result[3] = new Point(center.x - r, center.y);
  return result;
};


var p = new Point(10, 10);
var points = circle(p, 5).concat(circle(p, 10), circle(p, 2), circle(p, 6));

console.log(knearlin(points, p, 8));
console.log(knearlin(points, p, 6));
console.log(knearlin(points, p, 4));
console.log(knearlin(points, p, 20));
console.log(knearlin(points, p, 0));

Running with Node:

[ { x: 10, y: 12, d: 4, dist2: [Function] },
{ x: 12, y: 10, d: 4, dist2: [Function] },
{ x: 10, y: 8, d: 4, dist2: [Function] },
{ x: 8, y: 10, d: 4, dist2: [Function] },
{ x: 10, y: 15, d: 25, dist2: [Function] },
{ x: 15, y: 10, d: 25, dist2: [Function] },
{ x: 10, y: 5, d: 25, dist2: [Function] },
{ x: 5, y: 10, d: 25, dist2: [Function] } ]

[ { x: 10, y: 12, d: 4, dist2: [Function] },
{ x: 12, y: 10, d: 4, dist2: [Function] },
{ x: 10, y: 8, d: 4, dist2: [Function] },
{ x: 8, y: 10, d: 4, dist2: [Function] },
{ x: 10, y: 15, d: 25, dist2: [Function] },
{ x: 15, y: 10, d: 25, dist2: [Function] } ]

[ { x: 10, y: 12, d: 4, dist2: [Function] },
{ x: 12, y: 10, d: 4, dist2: [Function] },
{ x: 10, y: 8, d: 4, dist2: [Function] },
{ x: 8, y: 10, d: 4, dist2: [Function] } ]

[ { x: 10, y: 15, d: 25, dist2: [Function] },
{ x: 15, y: 10, d: 25, dist2: [Function] },
{ x: 10, y: 5, d: 25, dist2: [Function] },
{ x: 5, y: 10, d: 25, dist2: [Function] },
{ x: 10, y: 20, d: 100, dist2: [Function] },
{ x: 20, y: 10, d: 100, dist2: [Function] },
{ x: 10, y: 0, d: 100, dist2: [Function] },
{ x: 0, y: 10, d: 100, dist2: [Function] },
{ x: 10, y: 12, d: 4, dist2: [Function] },
{ x: 12, y: 10, d: 4, dist2: [Function] },
{ x: 10, y: 8, d: 4, dist2: [Function] },
{ x: 8, y: 10, d: 4, dist2: [Function] },
{ x: 10, y: 16, d: 36, dist2: [Function] },
{ x: 16, y: 10, d: 36, dist2: [Function] },
{ x: 10, y: 4, d: 36, dist2: [Function] },
{ x: 4, y: 10, d: 36, dist2: [Function] } ]

[]

Microsoft Linked Lists Interview Questions

09 Nov 2011 | By Mihai Roman | Comments | Tags algorithms C/C++ microsoft

MS30: Reverse a linked list.

List* reverse(List* list) {
  if (list == NULL || list->next == NULL) return list;
  List* p = list->next;
  list->next = NULL;
  while(p->next != NULL) {
   List* c = p->next;
   p->next = list;
   list = p;
   p = c;
  }
  p->next = list;
  return p;
}

MS115: Reverse a singly linked list recursively. The function prototype is node * reverse (node *).

List* reverse(List* list) {
  if (list != NULL && list->next != NULL) {
    List* next = list->next;
    list->next = NULL;
    List* r = reverse(next);
    next->next = list;
    return r;
  }
  return list;
}

MS39: Insert in a sorted list.

List* insertSorted(List* list, int data) {
  List* node = new List;
  node->data = data;
  if (list == NULL || list->data > data) {
    node->next = list;
    return node;
  }
  List* p = list;
  while (p != NULL) {
    if (p->next == NULL) {
      p->next = node;
      node->next = NULL;
      return list;
    }
    if (p->data <= data && p->next->data >data) {
      node->next = p->next;
      p->next = node;
      return list;
    }
    p = p->next;
  }
}
}

MS74: Write, efficient code for extracting unique elements from a sorted list of array. e.g. (1, 1, 3, 3, 3, 5, 5, 5, 9, 9, 9, 9) → (1, 3, 5, 9).

List* extractUniqueFromSorted(List* list) {
  if (list == NULL) return NULL;
  List* p = new List;
  p->data = list->data;
  p->next = NULL;
  List* l = list->next;
  List* a = p;
  while (l != NULL) {
    if (l->data != a->data) {
      List* node = new List;
      node->data = l->data;
      node->next = NULL;
      a->next = node;
      a = node;
    } 
    l = l->next;
  }
  return p;
}

MS116: Given a singly linked list, find the middle of the list.

List* middle(List* list) {
  if (list == NULL) return list;
  List* p = list->next;
  while(p != NULL && p->next != NULL) {
    p = p->next->next;
    list = list->next;
  }
  return list;
}

Java Interview Questions - Mutex and Semaphore

08 Nov 2011 | By Mihai Roman | Comments | Tags java concurrency
  1. What are the limitations of basic Java concurrency model based on synchronization blocks and methods?
    • cannot cancel an attempt to acquire a lock that is already held;
    • unable give up acquiring a lock after waiting a period of time;
    • there’s no support to interrupts in synchronized blocks;
    • cannot control lock reentry, read vs. write protection or fairness;
    • any method can synchronize on any object (no access control);
    • locking and releasing is restricted to the same method.
  2. What is a mutex?
    A mutex restricts access to a resource to one thread at a time. The thread that acquired the mutex must also release it. In Java, any object can function similarly to a mutex using the synchronized block.
  3. What is a semaphore?
    A semaphore restricts access to a resource to a set number of threads. Acquire call blocks until a new permit is available and release call adds a new permit.
  4. What is the difference between a mutex and a semaphore?
    Number of threads: the mutex implements mutual exclusion, only one thread can access the resource; the semaphore allows a set number of permits. Ownership: the mutex is tied to the thread currently holding the lock.
  5. Concurrency support in Java 1.4. What about 1.5+?
    Java 1.4 had only basic built-in concurrency: synchronized methods and blocks, Thread, ThreadLocal. Some frequently used classes are synchronized: StringBuilder, HashTable, Vector. Java 1.5 introduces the java.util.concurrent package that includes: the scheduling framework (thread pools and executors), concurrent collections (with higher performance than synchronized collections), synchronizers (semaphores, mutexes, barriers, latches, and exchangers), locks.
  6. What is the difference between a built in lock and a lock implementation from java.util.concurrent.locks?
    The built in lock has several limitations that the new concurrency package is fixing: specify a timeout when attempting to acquire a lock, multiple condition variables per lock, non-nested scoped locks, and support for interrupting threads that are waiting to acquire a lock.

Java Interview Questions - Coding

07 Nov 2011 | By Mihai Roman | Comments | Tags java coding

For each of the following code snippets, indicate the output.

Finally

public class Main {
  public static void g() throws Exception {
    try{
      throw new Exception();
    } finally {
      System.out.println("A");
    }
  }
  public static void f() {
    try {
      g();
    } catch (Exception ex) {
      System.out.println("B");
    }
  }
  public static void main(String[] args) {
    f();
  }
}

Answer: A B

Arrays

public class Main {
   public static void main(String[] args) {
    int[] numbers = new int[10];
    for (int i = 0; i < 10; i++) {
      numbers[i] = i;
    }
    String[] strings = {"one", "two", "three", "four", "five"};
    System.out.println(numbers.length);
    System.out.println(Arrays.toString(numbers));
    System.out.println(strings.length);
    System.out.println(Arrays.toString(strings));
  }
}

Answer: 10 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 5 [one, two, three, four, five]

Arraycopy

public final class DemoFour {
  public static class A {
    private int x;
    public A(int x) {this.x = x;}
    public String toString() {return (new Integer(x)).toString();}
    public void setX(int x) { this.x = x;}
  }
  public static void main(String[] args) { 
    int[] x = {1,2,3,4};
    int[] y = new int[4];
    System.arraycopy(x, 0, y, 0, 4);
    Integer[] X = {1, 2, 3, 4};
    Integer[] Y = new Integer[4];
    System.arraycopy(X,  0, Y, 0, 4);
    A[] Z = {new A(1), new A(2), new A(3), new A(4)};
    A[] T = new A[4];
    System.arraycopy(Z, 0, T, 0, 4);
    X[0] = 10;
    x[0] = 10;
    Z[0].setX(10);
    System.out.println(y[0]);
    System.out.println(Y[0]);
    System.out.println(T[0]);
  }
}

Answer: 1 1 10

Constant Storage

public class Main {
  public static void main(String[] args) {
    String a = new String("A string");
    String b =  new String("A string");
    String c = "A string";
    String d = "A string";
    System.out.println(a == b);
    System.out.println(a.equals(b));
    System.out.println(c == d);
    System.out.println(c.equals(d));
  }
}

Answer: false true true true
Hint: String is a reference type so any assignment made to a String variable stores a reference to an object. Constant values are stored without duplicates in the constants table.

Scope

public class Main {
  public static void main(String[] args) {
    String a = null;
    {
      String b = new String("Hello World!");
      a = b;
    }
    System.out.println(a);
    System.out.prinln(b); 
  }
}

Answer: Compile error, b cannot be resolved to a variable.
Hint: b is out of scope;

Overflow

public class Main {
  public static void main(String[] args) {
    byte b = (byte) 130;
    System.out.println(b);
  }
}

Answer: -126

Java Interview Questions - Exceptions

06 Nov 2011 | By Mihai Roman | Comments | Tags java exceptions
  1. What are Checked and UnChecked Exception?
    Checked: subclass of Exception except RuntimeException. Unchecked: Error, RuntimeException and their subclasses. For unchecked exceptions, the compiler does not force the programmer to either catch the exception or declare it in the throws clause.
  2. What is the difference between and error and an exception?
    Errors should be irrecoverable. However there’s nothing stopping you from catching any subclass of Throwable.
  3. How to create custom exceptions?
    Extend Throwable or any of its subclasses, like Error, RuntimeException or Exception.
  4. If I want an object of my class to be thrown as an exception object, what should I do?
    Either make your class extend Throwable or any of its subclasses or delegate throwing your object to a wrapper subclass of Throwable.
  5. If my class already extends from some other class what should I do if I want an instance of my class to be thrown as an exception object?
    Java doesn’t allow extending multiple classes (unlike C++). You should delegate throwing it to a wrapper class that extends Throwable.
  6. How does an exception permeate through the code?
    An unhandled exceptions moves up the call stack until it finds a matching catch block that will be executed. If the exception is not caught anywhere, the program exist with that error.
  7. What are the different ways to handle exceptions?
    try-catch blocks or declaration in throws clause.
  8. What is the basic difference between the 2 approaches to exception handling: 1) try catch finally block and 2) specifying the candidate exceptions in the throws clause? When should you use which approach?
    1) The method is responsible of dealing with it’s own exceptions. 2) Otherwise. Making the decision is subject to patterns and anti-patterns in exception handling, not a short and decisive answer.
  9. Is it necessary that each try block must be followed by a catch block?
    No. However, in this case, it must be followed by a finally block.
  10. If I write return at the end of the try block, will the finally block still execute?
    Yes. It can also change the return value.
  11. If I write System.exit (0); at the end of the try block, will the finally block still execute?
    No.
  12. How does a try statement determine which catch clause should be used to handle an exception?
    The first matching catch block, in order of declaration.
  13. Does it matter in what order catch statements for FileNotFoundException and IOException are written?
    Yes, because the FileNotFoundException is a subclass of IOException.
  14. What is the purpose of the finally clause of a try-catch-finally statement?
    Execute code no matter if an exception is thrown or caught. Order of execution: try-catch-finally or try-finally-throw forward.
1 2 3 4 5 6 7 8 9