Tuesday, January 25, 2011

How to find topmost frequent items from a data stream?

0 comments
I've been asked this question in a interview a long time back: if you have a huge amount of data and don't have memory to keep all of them, how do you get the top items, even if you have some error. Answering this precisely is not simple and requiring the interviewee to provide a 100% correct may be too much, but the goal is more about the discussion - and luckily it seems I did well at that time. Anyway, below you can find two good references on the topic, in case you are interested in learning more:

Manku, Motwani - "Approximate Frequency Counts over Data Streams" [pdf]

Data Streams: Algorithms and Applications

Sunday, January 23, 2011

First program in Scala: porting binary search add/remove from Java

0 comments
Today I worked on my first program in Scala, after reading most of Programming Scala. This is the first time in a very long time that I try to learn a new programming language and I took the approach of first reading the book. After starting writing the code, though, I noticed how important it is to actually code something in the language, as without coding, you can't remember much.

So, what I did first was to port the code to delete nodes from a binary tree available here in Java to Scala. The outcome was almost identical, except for some Scala-specific things, like trying to use Option.

Second, I tried to make is more Scala ("scalafy my code") and, since it's been a couple of weeks since I last read the "Programming Scala", I thought that there wasn't a whole lot I could do for this kind of program. However, after trying to implement pattern matching in some sections, I realized that I could get rid of my if statements (which were long, with a bunch of elses) only with pattern matching. Also, some of the "get" calls on the Options objects ended up being unnecessary with the pattern matching. I thought the result was quite elegant compared to the Java version. Open the Java version in a different tab and compare the code, and let me know what you think. Also, if you know Scala, please let me know what suggestions you would have to make use of more Scala features.

case class Node(value: Int, var right: Option[Node], var left: Option[Node])

object TreeUtils {
 def printInOrder(node: Option[Node]) {
  node match {
   case Some(node) => {
    printInOrder(node.left);
    Console.print(" " + node.value);
    printInOrder(node.right);    
   }
   case _ => ;
  }
 }
 
 def addNode(node: Option[Node], valueToAdd: Int): Option[Node] = {
  node match {
   case None => 
    Option(new Node(valueToAdd, None, None));
   case Some(currentNode) => {
    currentNode.value match {
     case v if v < valueToAdd =>
      currentNode.right = addNode(currentNode.right, valueToAdd);
      node;
     case v if v > valueToAdd =>
      currentNode.left = addNode(currentNode.left , valueToAdd);
      node;
     case _ => node;
    }
   }
  }
 }
 
 def deleteNode(node: Option[Node], valueToDelete: Int): Option[Node] = {
  node match {
   case None => 
    None;
   case Some(currentNode) => {
    currentNode.value match {
     case v if v < valueToDelete =>
      currentNode.right  = deleteNode(currentNode.right, valueToDelete);
      node;
     case v if v > valueToDelete =>
      currentNode.left  = deleteNode(currentNode.left , valueToDelete);
      node;
     case _ => {
      (currentNode.left, currentNode.right) match {
       case (None, None) => None
       case (None, _) => currentNode.right 
       case (_, None) => currentNode.left
       case (Some(leftNode), Some(rightNode)) if rightNode.left == None => {
        rightNode.left = currentNode.left;
        currentNode.right;
       }
       case (Some(leftNode), Some(rightNode)) => {
        var q = rightNode;
        var p = rightNode;
        
        while (p.left.get.left != None)
         p = p.left.get;
        
        q = p.left.get;
        p.left = q.right;
        q.left  = currentNode.left;
        q.right = currentNode.right;
        Some(q);
       }
      }
     }
    }
   }
  }
 }
}

object BinaryTree {
 def main(args: Array[String]) = {
  var root : Option[Node] = None;
  val numbers: Array[Int] = Array(56,86,71,97,82,99,65,36,16,10,28,52,46);
  for (i <- numbers) {
   Console.println("Inserting " + i);
   root = TreeUtils.addNode(root, i);
  }
  Console.print("Tree: ");
  TreeUtils.printInOrder(root);
  Console.println();
  for (i <- numbers) {
   Console.println("Removing " + i);
   root = TreeUtils.deleteNode(root, i);
   Console.print("Tree: ");
   root match {
    case None => Console.println("  ");
    case _ => 
     TreeUtils.printInOrder(root);
     Console.println();
   }
  }
  Console.println("Done");
 }
}

Friday, January 07, 2011

DO NOT BUY on Frys.com

0 comments
It's been a while that I don't post, but this deserves a post in capital letter: DO NOT BUY on Frys.com. I placed an order on 11/25/2010, and their system recorded two orders, charged twice, and shipped two packages. When I called them, they told me to refuse the package when it was delivered by USPS. That is what I did on 12/07/2010. It's been a month since I refused the package, and several calls to their customer service number, one email sent through their web site (without response after a week), and I haven't received any refund. Except for the last associate I talked to, they did not seem to care a bit about the problem. Most of them say that I should keep waiting, because it can TAKE MONTHS. One of them said that he would talk to the manager and call me back: HE'S NEVER DONE THAT. Now, after a month of following their directions, they will investigate further without any guarantee whatsoever - yes, it's possible that they will never refund.

I think I've been really spoiled by Amazon.com and other companies that care about their customers and forgot about companies like Frys. Frys clearly doesn't care about their customers, provide a horrible experience, and I will definitely recommend all my friends against buying anything from this company.

After a quick search on Google, this is the first link I get about customers reviews of Frys.com - 950 reviews, 1 star out of 5. It seems I am not the only one:
http://www.resellerratings.com/store/Fry_s_Electronics_Outpost