September 19, 2013

Interview Question - Determine if a Tree is a Binary Search Tree

Well it's interview season.  That basically means it's the time of year I spend way more time studying for interviews than I do for actual class work.  Which doesn't bode well for my next week of midterms but I guess getting a summer internship is more important in the long run than acing one midterm.

Here's a question I remember I attempted a year ago, gave up, tried again recently, and got a working solution:

Determine if a binary tree is a binary search tree.
Solution in C#.  I defined previous and current as ints above because I didn't want to distract from the logic of the code.

const int previous = 1;
const int current = 0;

static bool IsBSTHelper(BSTNode node, int[] a)
{
    if (node == null) return true;

    var isValidBST = IsBSTHelper(node.left,
a);

   
a[previous] = a[current];
   
a[current] = node.data;

    if (
a[current] < a[previous])
    {
        return false;
    }

    return isValidBST && IsBSTHelper(node.right,
a);
}

static bool IsBST(BSTNode root)
{
    return IsBSTHelper(root, new int[] {int.MinValue, int.MinValue});
}

I started out with the classic pre-order tree traversal.  Since it prints out the elements in the right order, I figured I would save the last printed element in the recursive call and compare it with the next printed element.  I was running into problems with that until I decided to use an array of two ints to store the values instead.  And now.. it works for all of my test cases.

Here I assume the tree is nice.  This wouldn't return false if a tree has more than two children per node, or if the tree has a loop.

July 06, 2013

Implementing IEnumerable

I've found myself needing to implement IEnumerable time and time again, so I'm just putting up a fun reference for myself to follow in the future.

My data:
public class IceCream {
  string _flavor;
  public string Flavor {
    get { return _flavor; }
    set {
      _flavor = value;
    }
  }

  public IceCream(string flavor) {
    _flavor = flavor;
  }

  public override string ToString() {
    return _flavor;
  }
}

The class that implements IEnumerable:
public class Menu<T> : IEnumerable<T> {
  List<T> rep = new List<T>();

  public Menu() { }

  public void Add(T item) {
    rep.Add(item);
  }

  public Menu(IEnumerable<T> collection) {
    foreach (T item in collection)
      rep.Add(item);
  }

  public IEnumerator<T> GetEnumerator() {
    foreach (T item in collection)
      yield return item;

    // return rep.GetEnumerator() works as well
  }

  IEnumerator IEnumerable.GetEnumerator() {
    return GetEnumerator();
  }
}

And now for the fun:
static void Main() {
  var Vanilla = new IceCream("vanilla");
  var Chocolate = new IceCream("chocolate");
  var CookieDough = new IceCream("cookie dough");
  var SaltyCaramel = new IceCream("salty caramel");

  var menu = new Menu<IceCream>() { Vanilla, Chocolate, CookieDough, SaltyCaramel };

  foreach (var i in menu)
    Console.WriteLine(i.ToString());
}

With the awesome output:
vanilla
chocolate
cookie dough
salty caramel

yay

June 30, 2013

Lessons from work

In light of my first work experience, I've been grappling with the question - what makes a good programmer?  I know there have been so many articles written on this subject, by people much more knowledgeable than I am, but I'm still trying to figure out the answer.

Of course being smart helps.  Having good knowledge of algorithms, being able to optimize your code for time and space.  That's what most interviews test.

But, at least at my internship, I've rarely had to code optimized solutions for space or time, so maybe I'm not qualified yet to conclude anything.  But I have noticed traits of my co-workers that I admire and would like to emulate.

One of the interns I'm working with is one of those people who has a host of time-saving programs and techniques at his fingertips - I've never heard of Auto Hot Key before this internship, but it's a program that almost makes your mouse obsolete.  You can type in any customized shortcut and open any program you want.  Think of all the productivity gains!  It's just one example of the many techniques he uses to save time and make navigating around a computer easier.  I think that's one of the traits of a great programmer - constantly looking for ways to reduce tedious manual work, and generally making things easier.

Good people skills are much more important for programmers than most would think.  More than almost any other profession, programmers get the rep for being introverted to the core and socially inept.  But I honestly have not met this person yet.  Ultimately, the job of a programmer is to produce good code - and maybe that's where the stereotypical programmer excels.  But in the real world, people must work in a team and therefore must be tolerable at minimum to work with.  My co-workers are more than tolerable - they are delightful, and it makes coming into work every day that much easier.  They are always happy to help me, willing to point out my mistakes, and quick to give praise.  You just want to work with people you like.  You're happier when you work with people you like.  And you don't want to let them down, so you really try your hardest.

And I guess - self-sacrifice?  I've been doing a bit of that.  Interns are specifically told to work 40 hours a week and go home after that.  I know I put in more than 40 hours a week - I was the last intern put on my project so I've had a lot of catch-up to do - I came to work earlier than most and left later than most for the past two weeks.  There's another intern I know - she stayed til 9 a couple nights last week to finish all of her work.  I heard of another developer who once put in 120 hours a week during project development.  That's 17 hours a day, including weekends!  I heard that the project he was responsible for had only two bugs in production.  While I feel like putting in 120 hours a week is extreme, and not a sustainable way to live, I admire that programmer's determination to pursue quality.

There's another developer I've heard of that everybody says is one of the best ones.  He's very introverted, but on the few occasions I've had to talk to him he was very nice.  Everyone says he's very nice.  I want to know what makes him such a good developer, and if I'm missing any of those characteristics on my list I'll add them.  I feel like, as a developer, I'm at the most malleable stage of my career and most receptive to new ideas - I'm still at the point where I'm in awe of how much everyone around me knows.  I hope I never lose that.

edit // I feel like this will be a continuously growing list, and will update whenever I see fit.  Seems like these edits are more geared towards being a good employee in general, but it relates to the theme of this post

7/1/2013 - I forgot to add "following directions" to my list earlier.  I had an instance a couple weeks ago where I was downloading material for tutorials and I spent a day working with the wrong version and wondering why NOTHING was working.  Although it was confusing because I was required to download an outdated version of the software, I was still told which version to download and I somehow missed it.  I forced myself to stay later at the office and come in earlier all week - it wasn't overtime, it was making up for a mistake that I couldn't blame on anyone but myself.  Just reading the directions would have saved me so much time and trouble.  I've always had a hard time following tutorials because I always think I've got the idea and go off on my own - I often regret this impulsiveness and I'm learning to be patient and read every line thoroughly, as someone out there thought it was important enough to include.

7/2/2013 - I also forgot to add a technique that I use multiple times, every day.  When asking a question or a favor, I've learned to always start it with, "Hey, when you get a free moment ... " instead of "Hey, help me right now".  Of course the bluntness of the second is exaggerated but it illustrates my point - approaching someone directly for help often forces them to drop everything they are doing because they feel bad saying no, most times.  I learned this at my previous part-time job at school - I noticed that when I phrased my questions differently my team lead was much more receptive to helping me.  Indicating that you understand the other person's priorities - that your request for help comes AFTER the current task they are working on - seems much more respectful.

7/6/2013 - Self-commenting code and good variable names!  I enjoyed this article - especially this sentence: "[Write-Only-Code (as opposed to Really Obvious Code)] is, effectively, a love letter between the coder and the computer - full of inside jokes and pet phrases that are meaningless to those not part of the relationship."  I can say that when foraging through millions of files (not really but that's what it feels like), good variable names can make deciphering the madness a lot easier.

June 29, 2013

expense tracker - part 9

Hitting some snags trying to implement the edit functionality.  The MessageBox control is very limited, and I'm sure it was intended that way, but there is no way to create fields to allow for user input.  I actually had to use Xna's MessageBox in order to create buttons with custom text - I needed a "remove" button, and possibly later on, an "edit" button.  There's a problem with that - although I'll need three buttons in the future - "edit", "remove", "cancel", the MessageBox only allows for a maximum of 2 buttons.

So right now the user is allowed to remove single fields from clicking on a name in the display list, but they can't edit it.  I could direct the user to a separate edit page but that seems clunky.  I like the consistency and look of the MessageBox, but it looks like I'll have to implement my own to get the functionality I want.

And actually, deleting a single field was difficult enough.  I couldn't get the Binding Command to work on a single field in my ItemsControl so I had to go with Click event handlers in the code-behind.  Unlike Binding Commands, I can't pass on a parameter so that was tricky - I had to do some shenanigans to get it to work.

Anyway, say you want to remove a field from your list - you just click it and a MessageBox pops up, allowing you to remove it or cancel.  A second MessageBox pops up confirming that you did, in fact, remove it.  That might get annoying if you use it a lot so I'm thinking about taking it out.


And now no more lunch.  Although it bothers me that Other still shows up even when it's 0, I'm going to change that.  Also, if you look carefully, you can see that the "Lunch" button and its text is brighter than the rest of the fields, due to it being focused.  I didn't implement that, it comes with the Button, but I like how it looks.

I had to play around with Focus stuff in order to get it to work, as Click events can't pass parameters and I couldn't bind to a specific item that is contained in an ItemsControl.  Ideally I would use a Binding Command, where you can pass on a parameter, but I was having a lot of trouble implementing that.  Anyhow, here is the click event in my code:
private void List_Button_Click(object sender, RoutedEventArgs e) {
  string name = "";
  decimal cost = 0;
  GetFocusedNameCost(out name, out cost);
  vm.MouseClick(name, cost); // where vm is an instance of my ViewModel
}

private static void GetFocusedNameCost(out string name, out decimal cost) {
  var focusedElement = FocusManager.GetFocusedElement();
  StackPanel s = (StackPanel)(((Button)focusedElement).Content);
  name = ((TextBlock)(s.Children[0])).Text;
  Decimal.TryParse(((TextBlock)s.Children[2]).Text, out cost);
}

And in my ViewModel for this page:
public void MouseClick(string name, decimal cost) {
  string title = String.Format("{0}: ${1}", name, cost.ToString());
  var result = Guide.BeginShowMessageBox(title, " ", new string[] { "remove", "cancel" }, 0, MessageBoxIcon.None, null, null);

  int? user_choice = Guide.EndShowMessageBox(result);
  if (user_choise == 0) {
    theyclickedremove(name, cost);
  }
}

Where theyclickedremove(name, cost) just goes and removes the appropriate items from storage and the display list.  Right now the variable names are confusing and I need to do some minor refactoring so I'll just leave it out for now.

So now my app is mainly functional, if not totally intuitive.  Right now, if the user wants to subtract, say, $5 from a field, they'll have to remove it from the list and re-enter the field with the new value.  At least it's better than clearing the entire list, but I want to make that process easier.  Also I want to implement an option that clears the list at the beginning of every month.  Shouldn't be too hard.

June 24, 2013

expense tracker - part 8

Here is my app now.  No more ugly huge add button!

I finally decided to go with the pivot app.  It makes it a lot easier to navigate around, and it's a lot clearer now how to toggle between views.  I wasn't able to implement this using pure MVVM because the app bar is being annoying but it's close enough.

The running tally is semi-bold.  I didn't know that existed!  It kind of looked weird the way it was, but turning it bold made the text really aggressive.  Semi-bold was a nice compromise.

Now what I am working on:
Yes I legit did spend $11 on cupcakes
last week.  The rest is made up

Each row is actually a button, with a child element StackPanel.  The StackPanel contains three TextBoxes - one for the name, one for the dollar sign, one for the amount.  I did it this way so the user can just click on the button to edit the fields.  I haven't implemented the edit functionality yet, but when using this app I've already found myself needing one.  Now I have to clear all values and enter everything again if I want to remove from a single field, which gets annoying.  Plus having them all be buttons is cool because clicking on each row turns the text white.  And you'll notice the Running Tally row is grayed out, I couldn't think of any uses why the user would want to edit the Running Tally field as it depends on the values of every other field so I disabled the IsEnabled property.  I rather like the way it looks - it's kind of telling you "Go away don't touch me" so you know it'll just ignore you if you try to bother it.

I know the two columns kind of look odd.  I wanted to dynamically bind the widths so that each field is on its respective extreme end but my app resisted very much and I decided to move on to other things.  Maybe I'll understand Silverlight enough later on to implement that, I think right now the number field will take up to six digits (allows for up to the thousands place, accounting for cents).  Any more than that and it'll wrap around to the next line.  It looks horrendous, but that's what the user gets for spending too much money.

After I add the edit functionality this app should be pretty much done.  My friend suggested adding dates, and with my pseudo-MVVM pattern it shouldn't be too hard to add a date field.  I was also thinking that it might be convenient to let the user choose whether the app should be cleared the first of each month, or if they want to manually clear the values themselves.  That shouldn't be too hard either - it's a nice little extra feature.

Good design

I don't think I realized til recently how important good user interface design is.  Apple is a famous example.. have you noticed how in movies, if anyone is ever using a laptop it's ALWAYS a mac?  I asked my brother and he said it's because they just look better.. and it's true.  I prefer Windows and I'm a big fan of Unix/Linux but I do appreciate the simplicity and elegance of Apple products.

For a while, as I browsed through various programming blogs, I wondered why some blogs just seemed more legit than others.  Some of the material in those blogs I dismissed was probably very good, very thorough, and the authors were probably very knowledgeable.  So it's an unfortunate fact for them that I, and probably many other people judge the quality of a blog (or app, program, etc, anything really) by its design.  I generally don't like pages that are too busy, I don't like clashing/weird color schemes, I don't like the look of default html tables, I don't like gratuitous pictures/icons that pop up everywhere.  Yes I am picky but the look of an application is much more important than many programmers are willing to admit.

I know I'm one to talk.  My blog isn't very professional looking and sometimes my thoughts aren't coherent.  And, from browsing other sites, I can see it's common to format code a different way, to maybe wrap it in a table, to highlight and bold certain keywords, to have good spacing, and most of these things I don't follow well.  But as this is a blog mainly for my own learning purposes, I'm fine with what I have.  I like how the orange goes with the blue.

Just some thoughts.. I'm interning with a company that produces some very beautifully designed products.  I've been to a few lectures presented by our creative team and their Powerpoints are always very well put together, make full use of color harmonies, and have perfect font sizes and spacing.  Before this internship, I never thought I could describe a Powerpoint as "pretty".  And whenever tech makes powerpoints, they just throw everything together.  It's really kind of amusing to see the differences.

I should note that good design and beautiful design aren't necessarily the same things, and a product that incorporates both is commendable.

June 23, 2013

expense tracker - part 7

Gosh, when I started this project I had no idea it would be this complicated.  The concept seems so simple, doesn't it?  A working prototype took maybe a day, and that's with me barely knowing XAML or WPF or Silverlight at all.  But doing it RIGHT, and doing it so it's USABLE, can get complicated so fast.

I completed reorganized my code again.  I'm a huge fan of folders.. I made a folder for all of my converter classes, for variables, even a folder for little helper functions.  I tried segmenting my code even more.  And I separated the two Default fields in my app - the Other field and the Running tally field, as they operate a little differently than every other <name, value> pair the user types in so they might as well be separated into yet another class.  I'm still playing around with how all of the data and its corresponding logic should be organized.

I kind of hated the huge "Add" button in my previous implementation, even though it enables Command binding and so implements MVVM.  I looked up BindableApplicationBar and was excited to use it, but I don't think it works with Windows 8.  Sad face.  I think in this instance I'm willing to give up pure MVVM implementation in return for a better user interface, as I don't like using my app with the huge "Add" button, but I do like looking at it with everything neatly contained in the app bar.  As I've tried to be careful to use good coding practices in the rest of my app, I don't think it'll hurt too much to break MVVM here.

I'd only learned about singleton design patterns in school, this is actually the first time I've ever used one (well, knowingly).  My dilemma was - how do you implement INotifyPropertyChanged for a static class?  Sometimes you want to access a field that is used across multiple files in your application.  So this field must be static - but now you can't make it implement INotifyPropertyChanged.  Ahh, but here is where you can use the singleton pattern to implement that functionality.  I can't fully explain the details - but INotifyPropertyChanged only works for an instance of a class.  So you just create one instance of that class, and it can implement all of the INotifyPropertyChanged functionality you need.  As I said earlier, I decided to separate out the variables into separate classes - so I have a class for all of the text fields called Changing (since I have another class called Default that holds all of the variables that don't change).  Here is the implementation for that class:

public sealed class Changing : INotifyPropertyChanged {

  #region Singleton stuff

  private static readonly Changing _Instance = new Changing();
  private Changing() { }
  public static Changing Instance {
    get { return _Instance; }
  }

  #endregion

  #region Text Information

  private string _CurrentTxt = Default.DEFAULT_TXT;
  public string CurrentTxt {
    get { return _CurrentTxt; }
    set {
      _CurrentTxt = value;
      OnPropertyChanged("CurrentTxt");
    }
  }

  private bool _IsTxtDefault = Default.DEFAULT_SETTINGS;
  public bool IsTxtDefault {
    get { return _IsTxtDefault; }
    set {
      _IsTxtDefault = value;
      OnPropertyChanged("IsTxtDefault");
    }
  }

  #endregion

  #region Num Information

  private decimal _CurrentNum = Default.DEFAULT_NUM;
  public decimal CurrentNum {
    get { return _CurrentNum; }
    set {
      _CurrentNum = value;
      OnPropertyChanged("CurrentNum");
    }
  }

  private bool _IsNumDefault = Default.DEFAULT_SETTINGS;
  public bool IsNumDefault {
    get { return _IsNumDefault; }
    set {
      _IsNumDefault = value;
      OnPropertyChanged("IsNumDefault");
    }
  }

  #endregion

  #region INotifyPropertyChanged Implementation

  private void OnPropertyChanged(string p) {
    if (PropertyChanged != null) {
      PropertyChanged(this, new PropertyChangedEventArgs(p));
    }
  }

  public event PropertyChangedEventHandler PropertyChanged;

  #endregion
 
}

Yay and now I have static variables that can work with data binding.

Another small change is that I changed the numbers from being int to double to decimal.  Int was a bad choice because not everything you buy falls perfectly into an int value.  I wouldn't mind adding only int values to my phone but if you go through the trouble of adding a number with a decimal point, the TryParse just silently fails and drops the user's input.  Double seemed like overkill, I think decimal is more appropriate for this purpose.

Another thing I noticed was that I previously was loading all of the data in a ViewModel for my Display Expenses user control, but I don't think that was the place for it.  A lot of my debugging efforts were stymied by this code dependency.  So I just loaded the data in a separate class and called it in the constructor for my MainPage, I don't know if that's good practice or not but I know that separating those two different functionalities makes my life a lot easier when trying to debug code, and a lot less confusing when trying to navigate around.

Yeah.. a lot of changes.. My next problem to tackle is that fact that TextBoxes don't lose focus when you tap on an appbar item.  With my previous implementation, with the huge "Add" button, the TextBoxes would lose focus and the corresponding fields were correctly updated.  But appbars are annoying to work with and they keep the focus on the TextBoxes, which means my app has a bug now and I have to do some fanagling to make it right again.