Time and again, we see the self-recursive list of Fibonacci numbers:

fibs = 1 : 1 : [ a + b | a <- fibs | b <- tail fibs ]

This list allows us make a space-for-time tradeoff that’s appealing in many applications. A similar technique can be used with maps, for example:

module Fibonacci where

import Prelude hiding (lookup)
import Data.Word
import Data.Maybe
import Control.Monad

import Data.EnumMap




integers                     =  fromList [ (n,n) | n <- nums ]
 where
  nums                      ::  [Word32]
  nums                       =  [0..9]


fibonnacify mapping          =  fibonacci'
 where
  fibonacci'                 =  mapWithKey fib' mapping
   where
    fib' 0 _                 =  1
    fib' 1 _                 =  1
    fib' k _                 =  1 `fromMaybe` do
      a                     <-  lookup (k-1) fibonacci'
      b                     <-  lookup (k-2) fibonacci'
      return (a+b)


m                           ::  EnumMap Word32 Word32
m                            =  fibonnacify integers

Loading this in GHCi, we get what we expect:

Prelude> :load Fibonacci.hs 
[1 of 1] Compiling Fibonacci        ( Fibonacci.hs, interpreted )
Ok, modules loaded: Fibonacci.
*Fibonacci> lookup 1 m
Just 1
it :: Maybe Word32
*Fibonacci> lookup 2 m
Just 2
it :: Maybe Word32
*Fibonacci> lookup 3 m
Just 3
it :: Maybe Word32
*Fibonacci> lookup 4 m
Just 5
it :: Maybe Word32
*Fibonacci>

I’m doing a Haskell class at Noisebridge and I want to introduce unit testing early on. There’s so many testing packages on Hackage! It looks like Torch is the smallest and most versatile of the bunch — it can handle testing in IO and it’s certainly simple (and devoid of the operator madness that afflicts HUnit).

There is a constant space, linear time solution to the problem of finding a cycle in a linked list, dubbed “the tortoise & the hare”. We start with two pointers at the front of the list; one steps by two while the other steps by one; eventually they end up on the same node if there is a cycle in the list.

What is the actual time complexity of this operation? For a non-cyclic list, we naturally terminate as soon as the hare reaches end. In the cyclic case, we have a “preamble” and “cycle” for the list:

x ━╋ x ━╋ x ━╋ x ━╋ 0 ━╋ 1 ━╋ 2 ━╋ 3 ━┓
                       ┗━━━━━━━━━━━━━━┛

We count the elements of the cycle with numbers 0,1... while we just assign x’s to the elements in the preamble. Call the length of the preamble p and the length of the cycle x.

When the tortoise gets to 0, where is the hare? It has stepped over 2p nodes, p of them in the cycle; it is thus sitting on p % c (using % for the modulus). The hare is thus x - (p % x) steps from the tortoise.

The hare covers this distance at a relative velocity of 1; so we need

p + x - (p % x)

steps in total for the hare to reach the tortoise. It seems possible that the hare can skip over the tortoise, perhaps; but consider that in the time it takes the tortoise to travel x - (p % x) nodes, the hare has covered exactly twice that distance.

Using modular arithmetic a little differently, we count the number of steps the algorithm has run for it (call it i) and then set the position of the tortoise and hair at and after the point where the tortoise hits 0 as:

t =ₓ i - p
h =ₓ 2i - p

where we use =ₓ to mean “congruent modulo x”. At the point of solution, the tortoise and the hare must be sitting on the same element; t =c h. Now at i = p + x - (p % x) we have:

p + x - (p % x) - p =ₓ 2p + 2x - 2(p % x) - p
-(p % x) =ₓ p - 2(p % x)
p % x =ₓ p

which is correct by the definition of modular congruence.

After much toiling in the mines of IE 7, I’ve unearthed a strange monstrosity: it seems there are lazy DOM operations. Or jQuery is only so strict in its execution of DOM operations. It’s hard to say which.

I ran into this trouble where I explicitly hide an element before unveiling it parent but it shows up anyways. I fixed it by, strange to say, printing whether it is visible or not. In fact, it’s enough to just evaluate whether it is visible or not:

function surface(jquery_filter) {
  var show = $(jquery_filter);
  var hide = show.siblings().not(jquery_filter);
  show.show();
  hide.hide();
  var why_do_i_have_to_force_in_a_strict_language = $("#source:visible");
}

This code is drawn from a beta version of CrossLister; the problem affects the HTML preview section specifically (hence the #html at the end of the URL).

If you comment out the why_do_i_have_to_force_in_a_strict_language line and load the page, you’ll get the red and green #source section showing over the #preview. (I would like to put together a reduced test case when time allows).

I don’t have any explanation for this behaviour. Does evaluating the visibility state force queued up DOM operations? It would stand to reason that there is a bug in IE, given the broad approval my code enjoys among the other browsers; however, this may be a case where jQuery relies on undefined behaviour. It’d be nice to know what the real story is here.

Most of the time Haskell’s Lazy IO works as we would like. It can be tough to know what to do when it doesn’t. Here’s a simple console application that demoes file handle exhaustion in the absence of hClose, as well as the need to force file contents and derived values when using hClose.

import System.IO
import System.Environment


main                         =  do
  args                      <-  getArgs
  case args of
    [ "--help" ]            ->  help stdout
    [   "-h"   ]            ->  help stdout
    [  string  ]            ->  maybe (help stderr) perform (sel string)
    [          ]            ->  perform fast
    ____________            ->  help stderr
 where
  perform op                 =  do
    files                   <-  lines `fmap` getContents
    counts                  <-  mapM op files
    print counts
  help h                     =  do
    hPutStrLn h "Feed this program a list of files on standard input."
    hPutStrLn h "Options:\n  --lazy\n  --strict\n  --fast\n  --slow"
  sel "--lazy"               =  Just lazy
  sel "--strict"             =  Just strict
  sel "--slow"               =  Just slow
  sel "--fast"               =  Just fast
  sel _                      =  Nothing



 -- Results in file handle exhaustion with many filenames.
lazy fname                   =  do
  h                         <-  openFile fname ReadMode
  length `fmap` hGetContents h


 -- Ditto.
strict fname                 =  do
  h                         <-  openFile fname ReadMode
  len                       <-  length `fmap` hGetContents h
  return $ len `seq` len


 -- Just forces the length.     
fast fname                   =  do
  h                         <-  openFile fname ReadMode
  len                       <-  length `fmap` hGetContents h
  len `seq` hClose h
  return len


 -- Forces the file contents. Noticeably slower on large files.
slow fname                   =  do
  h                         <-  openFile fname ReadMode
  s                         <-  hGetContents h
  force s `seq` hClose h
  return $ length s
 where
  force []                   =  []
  force (h:t)                =  force t `seq` (h:t)

I received a curious email today in response to my resume. It says nothing about the position; the author wants me to answer a long sequence of questions about Java before we talk again:

---------- Forwarded message ----------  
From: amanda rocap <amandarocap@gmail.com>
Date: 2009/04/09
Subject: Java requirement
To: amandarocap@gmail.com


** CRAIGSLIST ADVISORY --- AVOID SCAMS BY DEALING LOCALLY
** Avoid:  wiring money, cross-border deals, work-at-home
** Beware: cashier checks, money orders, escrow, shipping
** More Info:  http://www.craigslist.org/about/scams.html

Hi,
Please answer the following questions and send it across,We have a
Java requirement.I will give a call once I receive a reply.

The Position Summary is as follows.
The sr. java developer will play a key role in developing new
technology initiatives for a very high growth organization. These new
initiatives will include content and contact management systems,
reporting systems, and other mission-critical applications as
appropriate. As a member of the dynamic and highly motivated
application development team, the systems and software developer plays
a key role in all aspects of the system development life cycle.
Depending upon the scope of each project, the systems and software
developer will work directly with business owners or through project
managers, but will always communicate closely with the rest of the
application development team. The sr. java developer reports to the
managing director, application development – architecture.
.......................................................................................
they need you to answer the test.do well.best of luck.

Java Fundamentals
1) Assume the Person class is defined and responds to
“updateAccessTime()” and “getName()”.  You have a populated map,
“aMap”, that maps person name strings to Person instances.  Identify
the problem in this code.  How could the problem be fixed?
    Person person = (Person) aMap.get("bob");
    if (person != null) {
    person.updateAccessTime();
    }
    String name = person.getName();
    System.out.println(“name is ” + name);
Answer:






2)  What does this code snippet print?  Describe why it does so.
    String b = "bob";
 b.replace('b', 'p');
    if (b.equals("pop")) {
    System.out.println(“pop”);
    } else {
    System.out.println(“bob”);
    }
Answer:





3)  Somebody calls “new Thing("start stop")” to create a new Thing
object, but an error occurs.  Identify the problem in the code below.
What change would you make to fix the problem?
    public class Thing {
    private List actions;
    public Thing(String startingActions) {
    StringTokenizer tokenizer = new StringTokenizer(startingActions);
    while (tokenizer.hasMoreTokens()) {
    actions.add(tokenizer.nextToken());
    }
    }
}
Answer:

SQL Knowledge
4)  Based on the following table DDL, write a SQL query to select all
products and SKUs where the username was “google” and the date ordered
was between January 1, 2009 and March 15, 2009. Date format is
YYYY-MM-DD.
CREATE TABLE ‘product_order’ (
 ‘id’ int(10) unsigned NOT NULL auto_increment,
 ‘product’ varchar(45) NOT NULL,
 ‘sku’ varchar(45) NOT NULL,
 ‘desc’ varchar(45) NOT NULL,
 ‘username’ varchar(45) NOT NULL,
 ‘user_order_num’ varchar(45) NOT NULL,
 ‘date_ordered’ date NOT NULL,
 ‘creation_timestamp’ date NOT NULL,
 PRIMARY KEY  (‘id’)
);
Answer:

Identifying Bugs / Spring & Servlets Knowledge
5)  Examine the following poorly-written servlet and Spring context
file.  Assume correct web deployment descriptors, assume everything
compiles, etc.
MyServlet.java
package com.clearwire.stuff;
import javax.servlet.*;
import javax.servlet.http.*;
import java.io.*;
import org.springframework.*;
public class MyServlet extends HttpServlet {
    private static Happy happy ;
    private static Sad sad;
    public void init(ServletConfig config) throws ServletException {
    super.init(config);
    happy = (Happy) SpringApplicationContext.getBean("happy");
    sad = (Sad) SpringApplicationContext.getBean("sad");
    }
    public void doGet(HttpServletRequest request,
HttpServletResponse response)
        throws ServletException, IOException {
    response.setContentType("text/plain");
    PrintWriter out = response.getWriter();
    if (request.getParameter("param").equalsIgnoreCase("happy")) {
           happy = new Happy();
    System.out.println(happy.message.toUpperCase());
    }
    else if (request.getParameter("param").equalsIgnoreCase("sad")) {
                   System.err.println(sad.message.toLowerCase());
    }
    else {
                    out.println("Panic!");
    }
    }
    public static class Happy {
           public String message;
    }
    public static class Sad {
           public String sadMessage;
    }
}
ApplicationContext.xml
<?xml version="1.0" encoding="UTF-8"?>
<beans>
    <bean id="happy" class="com.clearwire.stuff.MyServlet$Happy">
        <property name=”message” value=“I’m very happy!”/>
    </bean>
    <bean id="sad" class="com.clearwire.stuff.MyServlet$Sad"/>
</beans>

5a)  Explain what would happen if someone passed
‘http://localhost/myapp/MyServlet?param=happy’ to a machine running
this servlet within an appropriate servlet container.
Answer:




5b)  What about ‘http://localhost/myapp/MyServlet?param=sad’?  Why?
Answer:




5c) What about ‘http://localhost/myapp/MyServlet?param=foo’?  Why?
Answer:




5d)  What changes would you make to this code so that it functions as intended?
Answer:

Hibernate Knowledge
6)  What is the purpose of the following annotation on an object?
    @Entity
Answer:




7) What is the purpose of the following annotation on an object?  Is
the “@Table” annotation always required for entities?  If not, what is
the default table name?
    @Table(name=”my_table”)
Answer:




8)  What is the purpose of the following annotation on an object?  Why
would you use this type of annotation?
    @org.hibernate.annotations.Cache(usage =
org.hibernate.annotations.CacheConcurrencyStrategy.READ_WRITE)
Answer:




9) What is the purpose of the following annotations on an object?
    @Id
    @GeneratedValue(strategy = GenerationType.AUTO)
 private Long id;
Answer:


Programming Challenge
10)  You are standing at a point located at 50, 50 on a Cartesian X-Y
coordinate grid. The grid is shown in this elegant ASCII art:    :)
100
  ^
  |y
  |
  |      x
 0 +-------> 100
  0
The grid's X values are in the range:
    0 (x origin) to 100
The grid's Y values are in the range:
    0 (y origin) to 100
You are given the following ten random points on the grid:
    12, 34
    95, 12
    82, 6
     7, 89
    24, 57
    53, 19
    91, 5
    32, 36
    14, 68
    23, 41
Write the code to print the 3 closest points to where you are
standing.  You may write the code in Java or in detailed pseudocode.
HINT
The equation to find the distance D between any two points A and B is:
    D = square root ( (By - Ay)^2 + (Bx - Ax)^2 )
<Answer question in the space below and on the next page>
Answer:

regards
amanda


------------------------------------------------------------------
this message was remailed to you via: res-jgana-1115071475@craigslist.org
------------------------------------------------------------------

The jQuery history plugin that I’m using causes animations to skip and jump if its loadHistory operation runs at the same time as an animation.

When are we going to animate at the same time we are altering the browser history? During an animated transition to an error screen, for example. The remedy is to place the history operation in between the animations, using the delay operation provided by one of a few jQuery delay plugins. For example:

function message_fade_in() { ... }

function message_fade_out() { ... }

var step_time = 250;
function fade_transition(id) {
  return function() {
    $("")
      .delay(1 * step_time, message_fade_out)
      .delay(2.5 * step_time, function() {
        $.historyLoad(id.slice(1));
      })
      .delay(3 * step_time, function () {
        message_fade_in();
      })
    return false; // Disable native link action.
  }
}

(A longer example of fade_transition can be found in a CrossLister beta.)