Adobe Interview question - heuristic solution

Here's an easy solution (solutions are easy if the problem is hard because you don't have to try too hard since it will be very difficult to prove your solution isn't worse than an alternate)

1. Choose some number k < N the number of points
2. Choose the k closest pairs and connect them.
3. for each of the rest of the points, find the closest one to one of the endpoints of the k groups and add it in. Also include the endpoints of the groups (this results in a merge)
4. Repeat until all points added in.
5. Find "closest" group pairs and merge them. The closest group pair is the pair that can be merged with the least increase to the distance (you can connect endpoints, or do variations where you cut the groups in half and glue the 2 halves to another group).
6. Repeat (5) until all groups merged.

7. Repeat 1-6 experimenting with different values of k.

8. Simmer well until done to taste :)

Adobe Interview question

Here's an interview question, apparently from Adobe, posted on the Joel On Software site.

Someone ("d" is his moniker) posted that this was NP-complete. I think in this case the problem is to come up with an imaginative heuristic solution that will sound good to the interviewer :)

Adobe Interview Question

You are given a plotter which can plot points provided to it in the form of 'x' and 'y' coordinates. The plotter hand can move horizontally or vertically only. Your program will be given a list of 'n' coordinates in the form of {(x1,y1), (x2,y2} ... (xn,yn)}. Your program must print a sorted list of all 'n' points that would represent the least cumulative distance for the plotter hand to plot all 'n' points in that sorted order.

Inheritance of forms in VB .NET

In an earlier post, I talked about form to form navigation. An earlier version of this attempt tried to use in the built-in Form inheritance, which didn't work very well.

The form to form navigation worked fine, but I still had a hankering for some form of inheritance as I found myself creating many variants of forms for entering e.g. a booking field, a container field, etc. (the application is designed to be on a touch screen, for unsophisticated users, so buttons are big and each form is used to enter just 1 field).

I seem to have come up with an alternate solution. The solution is to create a parallel hierarchy of classes of controllers, associated with a form, that do the control. These classes have none of the VB behind-code associated complexity, so inheritance works as expected without unexpected sideeffets.

So far I've created a FormController at the top of the hierarchy, with a TextFormController beneath that, and a specific BookingFormController. The VB Design class is associated with the TextFormController, and the BookingFormController overrides that class to instantiate the heading and to override the save/restore next/back button navigation.

This new idea seems to be working well, and I'll probably eviscerate the code and post the skeleton classes a bit later.

Larry Watanabe's Gearchart

Years ago I wrote a simple program for calculating the equivalent size wheel for a given set of gears. That piece of code worked it's way into a bicycle FAQ and will probably outlive anything I've ever written in terms of code or publications. You never know what you'll be known for :)

Here's the link (and the code). It took me about 5 minutes to write.

/*
The C Source for Larry Watanabe's gear chart program
Originally found at ftp://draco.acs.uci.edu/pub/rec.bicycles/gear.c

*/
/* gear.c - prints out a table of gear-inches.
*
* Example:
*
* Wheel outside diameter: 27
*
* Chainwheel teeth: 50 40 27
*
* Rear cog teeth: 13 15 17 19 21 27
*
*
* 50 40 27
* -------------------------------
* 13 103.85 83.08 56.08
* 15 90.00 72.00 48.60
* 17 79.41 63.53 42.88
* 19 71.05 56.84 38.37
* 21 64.29 51.43 34.71
* 27 50.00 40.00 27.00
*
* Larry Watanabe watanabe@cs.uiuc.edu 1994
*/

#include
#define MAXFRONT 3 /* max number of chainwheels */
#define MAXREAR 8 /* max number of rear cogs */
main()
{
int c;
int i, j;

double wheel_diameter; /* outside diameter of wheel */
int front[MAXFRONT]; /* number of teeth for front chainwheels */
int rear[MAXREAR]; /* number of teeth for rear cogs */
int frontn = 0; /* number of front sprockets */
int rearn = 0; /* number of rear sprockets */
double gear_inch; /* gear-inches of current combo */

printf("Wheel outside diameter: ");
scanf("%lf", &wheel_diameter);

printf("\nChainwheel teeth: ");

/* skip over junk to get to a digit */
for (c = getc(stdin); !isdigit(c); c = getc(stdin))
;
ungetc(c, stdin);

/* input chainwheel sizes */
for (;;) {
c = getc(stdin);
if (c == '\n')
break;
if (isdigit(c)) {
ungetc(c, stdin);
scanf("%d", &front[frontn++]);
}
}
/* input rear cog sizes */
printf("\nRear cog teeth: ");
for (;;) {
c = getc(stdin);
if (c == '\n')
break;
if (isdigit(c)) {
ungetc(c, stdin);
scanf("%d", &rear[rearn++]);
}
}
printf("\n\n ");
for (j = 0; j < frontn; j++)
printf("\t%4d", front[j]);
printf("\n-------------------------------\n");
for (i = 0; i < rearn; i++) {
printf("%5d", rear[i]);
for (j = 0; j < frontn; j++) {
gear_inch = wheel_diameter * front[j]/ rear[i];
printf("\t%3.1lf", gear_inch);
}
printf("\n");
}
}

code formatter for VB

Strangely, the simple left-justified code looks better in the blog than the properly indented code -- because the blog columns are so narrow (to allow space for google ads I suppose).

Maybe we need a code formatter for blogs?

I'm not going to waste the space on my 2 22" monitors by formatting for the web :) Anyone really interested can just cut and paste into Visual Studio if they need properly formatted code.

VB Form to Form Navigation

I'm creating a wizard type application in VB.NET. One form starts off, then the next button goes to the next form, and so on.

Amazingly (at least to me) there didn't seem to be an easy way to do this. I looked on the net and the solutions there seemed to use a lot of resources by basically keeping all forms that have ever been opened, and creating a new form as the navigation target without closing any old ones.

With people buying 4GB of RAM nowadays (probably we will be up to 100 GB as a standard configuration when you are reading this) it's probably no big deal. But my OC wants to close the no longer needed forms :)

Here's a way to do this - this is just 3 forms. Form1 can navigate to form2 by pushing the button, Form2 can navigate to Form3 by pushing the button, and Form3 closes the application when it's button is selected. I wanted to keep the code clear of distracting details, so I just used the default names etc. for the forms and buttons.

Option Strict On
Option Explicit On

Public Class Form1
    Public continuation As FormContinuation


    Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
        ' initialize the first continuation with Form2. 
        ' later forms in the sequence are responsible for setting the continuation
        ' on this form to whatever should follow before they close themselves.
        ' We will just keep on opening and displaying those forms until
        ' someone sets it to nothing, after which the application will just
        ' close itself.
        continuation = New Form2
        Me.Hide()
        While Not continuation Is Nothing
            continuation.mainForm = Me
            continuation.showFormDialog()
        End While
        ' no more continuations, so just close this (the startup form)
        Me.Close()
    End Sub

    Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load
        Dim pt As New Point With {.X = 0, .Y = 0}
        Dim sz As New Size With { _
            .Width = Screen.PrimaryScreen.Bounds.Width, _
            .Height = Screen.PrimaryScreen.Bounds.Height _
            }
        Me.Size = sz
        Me.Location = pt
    End Sub
End Class

Public Class Form2
    Implements FormContinuation

    Private m_mainForm As Form1

    Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button2.Click
        ' we want the application to continue with Form3,
        ' so just set that in the mainform and then close this form
        mainForm.continuation = New Form3
        Me.Close()
    End Sub

    Private Sub Form2_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load

    End Sub

    Public Property mainForm() As Form1 Implements FormContinuation.mainForm
        Get
            Return m_mainForm
        End Get
        Set(ByVal value As Form1)
            m_mainForm = value
        End Set
    End Property

    Public Sub showFormDialog() Implements FormContinuation.showFormDialog
        Dim pt As New Point With {.X = 0, .Y = 0}
        Dim sz As New Size With { _
            .Width = Screen.PrimaryScreen.Bounds.Width, _
            .Height = Screen.PrimaryScreen.Bounds.Height _
            }
        Me.Size = sz
        Me.Location = pt
        ShowDialog()
    End Sub
End Class

Public Class Form3
    Implements FormContinuation

    Private m_mainForm As Form1


    Private Sub Form3_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load

    End Sub

    Public Property mainForm() As Form1 Implements FormContinuation.mainForm
        Get
            Return m_mainForm
        End Get
        Set(ByVal value As Form1)
            m_mainForm = value
        End Set
    End Property

    Public Sub showFormDialog() Implements FormContinuation.showFormDialog
        Dim pt As New Point With {.X = 0, .Y = 0}
        Dim sz As New Size With { _
            .Width = Screen.PrimaryScreen.Bounds.Width, _
            .Height = Screen.PrimaryScreen.Bounds.Height _
            }
        Me.Size = sz
        Me.Location = pt
        ShowDialog()
    End Sub

    Private Sub Button3_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button3.Click
        ' This is the last form in the sequence, so set the continuation to
        ' Nothing before closing
        mainForm.continuation = Nothing
        Me.Close()
    End Sub
End Class

Option Strict On
Option Explicit On

Public Interface FormContinuation

    ''' <summary>
    ''' Get/set the mainForm of the series of forms
    ''' </summary>
    Property mainForm() As Form1

    ''' <summary>
    ''' Show the dialog. This allows initialization to be 
    ''' done before showing the dialog and to declare the
    ''' continuation as a FormContinuation yet still show the
    ''' dialog.
    ''' </summary>
    Sub showFormDialog()

End Interface

Code formatter for VB, C# to XML for blogging

Found a great code formatter for formatting VB/C# code in xml format so it can be published in a blog -- no more ugly left-justified code!

http://www.manoli.net/csharpformat

Design Tools

A useful feature of a design tool is the ability to communicate to the user how the product will function. Some might say that this should fall into the area of requirements, but often there are areas where the design will impact the interaction with the user.

That's a problem with UML and many of the design tools out there. They are too technical to present to a user. I find that simple flow diagrams can be used to communicate a lot of information to the user, and capture many requirements as well, so requirements can be debugged along with usability and design through user reviews.

But perhaps flowcharts should be updated to better capture the types of interactions that can happen with a user and the type of functionality a program can have. Currently, once you get past the basic flowchart notation (and what is that anyways?) there seems to be a gamut of possibilities .. probably similar to OO-design before the Rational Unified Process. And when I make a flowchart and follow the standard conventions, I feel like I'm designing a COBOL program that is connecting to a mainframe ... which is what they were designed to do, and probably do well.

This brings up a host of possibilties ... there could be language-specific or environment-specific flowchart conventions/notations that would facilitate lower-level design without descending to the code level ... yet provide some higher-level specification. And ideally there would be a hierarchy of notation, so that commonalities between languages/environments could be specified in a language/environment independent way, and refined to a more detailed specification only as required. Or better yet would be a flowchart language that captures the functionality of language-specific features (as currently implemented) in a language-independent way ... languages evolve, and we see convergence in the feature-set of various languages with each version (objects being added to perl, etc.).

Amazon interview question - divide a list of integers into 2 lists where the sum of each list is as "balanced" as possible - here's a greedy hill-climbing algorithm:


Option Strict On
Option Explicit On
Module Module1
Public Const N As Integer = 100
Public Const HalfN As Integer = CInt(N / 2)
Public Const maxval As Integer = 1000
Public Const maxTries As Integer = 10000000
Dim list1 As List(Of Integer) = Nothing
Dim list2 As List(Of Integer) = Nothing
Dim tries As Integer = 0
Dim genRand As New Random()
Class Swap
Public i As Integer
Public j As Integer
Sub New(ByVal iv As Integer, ByVal jv As Integer)
i = iv
j = jv
End Sub
End Class
Public Sub generateRandom()
list1 = New List(Of Integer)
list2 = New List(Of Integer)
tries = 0
For i As Integer = 0 To HalfN - 1
list1.Add(genRand.Next(0, maxval))
list2.Add(genRand.Next(0, maxval))
Next
End Sub
Public Function findFirstSwap() As Swap
Dim diff As Integer = list1.Sum - list2.Sum
If (diff = 0) Then
Return Nothing
End If
For i As Integer = HalfN - 1 To 1 Step -1
For j As Integer = 0 To i - 1
tries = tries + 1
Dim x = list1.Item(i)
Dim y = list2.Item(j)
Dim newDiff = abs(diff - 2 * x + 2 * y)
If (newDiff < abs(diff)) Then
Return New Swap(i, j)
End If
Next
Next
Return Nothing
End Function
' just use greedy hillclimbing algorithm
Public Sub trySwap()
Dim firstSwap As Swap = findFirstSwap()
While (Not firstSwap Is Nothing And tries < maxTries)
With firstSwap
Dim x = list1.Item(.i)
Dim y = list2.Item(.j)
list1.Item(.i) = y
list2.Item(.j) = x
End With
firstSwap = findFirstSwap()
End While
End Sub
Public Sub output()
Console.WriteLine("partitions - difference in size is : " _
& (list1.Sum - list2.Sum).ToString() & _
" ops = " & tries.ToString())
Console.Write(list1.Sum.ToString() & ": ")
For Each x In list1
Console.Write(x.ToString & " ")
Next
Console.WriteLine()
Console.WriteLine("--------------------------------------------------------------")
Console.Write(list2.Sum.ToString() & ": ")
For Each x In list2
Console.Write(x.ToString & " ")
Next
Console.WriteLine()
End Sub
Public Function abs(ByVal x As Integer) As Integer
If x < 0 Then
Return -x
Else
Return x
End If
End Function
Public Sub test()
generateRandom()
trySwap()
output()
End Sub
Sub Main()
For I As Integer = 0 To 10
test()
Console.WriteLine()
Next
Console.ReadLine()
End Sub
End Module

Amazon interview question

Someone posted this on http://discuss.techinterview.org/cursor.gif


You are given a threaded binary tree where each node of a tree points to some node to the right of it in in-order traversal. Given such tree, check whether each thread pointer of the node in a tree satisfies this condition( i.e check whether if thread pointer is pointing to node that is on the right side in in-order traversal). If not make that pointer NULL else leave it.Each node has only three pointers pointing to left, right nodes and other the thread pointer. Space and Time constraint has to be considered while designing it.
IvflyMay 5, 2009

.. this little snippet should do the trick ....

Option Strict On
Option Explicit On

Public Class TNode
Private left As TNode
Private right As TNode
Private rightInOrder As TNode
Private name As String

'''

''' Returns the next node to the right of this node in an in-order traversal
''' This will be the leftmost node of the subtree of the right child.
'''

Private Function nextRight() As TNode
If right Is Nothing Then
Return Nothing
End If
Return right.leftMost()
End Function
'''

''' Returns the leftmost child of this subtree
'''

Private Function leftMost() As TNode
If left Is Nothing Then
Return Me
End If
Return left.leftMost()
End Function

Function validateTree() As Boolean
If (nextRight() Is rightInOrder) Then
Console.WriteLine("Node {0} is correct", name)
Else
rightInOrder = Nothing
End If
If Not left Is Nothing Then
left.validateTree()
End If
If Not right Is Nothing Then
right.validateTree()
End If
End Function
End Class

Module Module1
Sub Main()
' call with root
End Sub
End Module