Computer

Interview Question – Tail

In my hiatus, I finished my last semester at Georgia Tech and began my job search. I had an offer starting the semester, so I wanted to explore my options before the deadline near the end of the year. As such, in the 3 months of school, I participated in over 20 interviews with several companies across the US. During those interviews, I was exposed to a new style of programming: Interview programming (sometimes called “whiteboard coding”). This style of development is so fundamentally different from my experiences in classes and work that I decided to dedicate this post (and possibly a few others to come) to a few of the more interesting question I encountered.

The Problem

Through my interviews, I was asked an assortment of odd questions. Some were complicated: “write an algorithm to determine the shortest sequence of words in order out of a paragraph” and others were downright absurd: “If you had to spend a day as a giraffe, what do you think would be your biggest problem?”. The problem at the center of this post was a seemingly tame one, and possibly my favorite of the many questions I was asked.  It is worth noting that one of the key secrets to most interview questions is to find a clever use for a data structure. While many questions seem to have a simple brute force answer, it is typically a good idea to examine the question for possible uses of data structures (often a hash map). This question was no different.

The problem posed was to implement the linux command “tail” in O(n) time. For those unfamiliar with the command, running tail on a file or stream displays the last n lines (which can be specified with an argument). This is useful for monitoring logs, as new records are often appended to the end. It seems a simple problem to print lines [length-n, length] but that first requires indexing every line of the file. It causes problems with files smaller than n, very very large files, or streams. So we need a way general enough to scale up or down without performance losses.

Hash Map?

Sadly, this time the answer is not a hash map. It is however, another common data structure which can be creatively implemented to solve our problem. A linked list is a very simple data  structure. It is made up of nodes, which are small wrapper objects containing data and a pointer to another node. The list is referenced by storing the node at the top of the chain. This is a convenient structure for our needs because you can keep a list in memory without concerning  yourself with  the contents of the whole list.

So we have start with a node class, containing a line of text and a pointer to another node. This still leaves us with the problem of finding the end of the file, plus we do not have an index. So we need a class to manage the list. This class will be responsible for iterating through the file and creating the nodes for each line. Since we have a controller, we no longer need to  make the entire file into a list. Instead, we can append to our list until the length (tracked by the control class) is equal to the provided n lines of text. From that point on, in addition to appending to the end of the list, we can move the head. Moving the head pointer effectively subtracts a node from the front of the list. Repeating this algorithm through a file or stream should return the expected results regardless of filesize. At the end of the process the list should start a maximum of n lines from the end of the file, ending on the last line. This list can be iterated to print the correct lines. If a file is smaller than the specified length, the whole file will be printed, and should the file be very very huge, only the last lines will be printed without filling memory with the entire file.

The Train Rolls On

This problem had an elegant solution. Think of it as a sliding window or rolling train. The train adds cars until it hits its maximum length, then rolls down the tracks. The contents of the train at the end of the tracks are the desired lines. Visualizations like this can help in an interview, where the questions tend to be more about the way you think, rather than the best solution. Even if you were unable to implement the solution, explaining your approach with imagery shows you understand the problem.

So take some time this week to brush up on your data structures and the everyday struggles of being a giraffe. As always, raise a glass and code on.

Advertisements

IT WORKS!!!!

All condensed in to 2 boxes

The pi bar circuitry

As of today, the pi bar circuitry is complete. Using a few protoboards, I was able to mock up a test signal and dispense liquid from multiple buckets! The next stage is to complete our laser sensor and build the frame. However, in the next few days, I have 3 projects due so I am a little swamped. Hopefully I can find time to keep you updated as I build, but it is likely the next update will be a completed project.

In other news, my birthday is this weekend so I will be a bit preoccupied and unable to make much progress. However, I swear to you it will be done by thursday (partially because it is due then…).  If you are in the Atlanta area and want to come see the more fun, less electronics side of the Drunken Developer, come out to little 5 on Saturday the 19th, where my friends and I will be bar-crawling, ending at the Brewpub Cafe. Come say hi and we can discuss robot bartenders and other such fun.

As always, raise a glass and code on.

Lasers!

Ever watched an old spy movie? I’m talking your classic heists: expensive loot, black tights, ski masks, and the inevitable laser security grid. What if you could own one of those for yourself? For my bartenderbot project (which I am now affectionately calling pi bar) I have been tasked with creating a novel sensor. Since the nature of the product leads to inebriated users, the system needs to be fairly idiot-proof. As such, I am creating a laser security grid for cups.

Bzzzzzzzzzzzzzzzzzzzzz

Beware the laser array

Cup Security

The cups used in this application have a fairly limited size range. The code hard-scales recipes to max out at 12  oz to prevent overflow on Solo cups and shakers, and the smallest drink that makes much sense is 1 oz. As such, we can make some assumptions regarding our cups volume from another property, like height.  This laser security array will read that height (approximately) and give us a best guess of cup size. It is in no way precise, but it will hopefully prevent drunken users from pouring a 12 oz Long Island Iced Tea in to a 1 oz shot glass.

So where do lasers come in to this? EVERYWHERE.  The new design for the cup platform will look like the museum floor around the priceless sculpture centerpiece.  One side of the platform now consists of a  small project box with 3 inconspicuous metal washers sticking out of the side at various heights. The other side looks identical, minus the washers. Instead there are small holes in the box, with no visible parts.

 

WHAT’S IN THE BOX?!

The super secret dark boxes contain 2 cardboard sheets, keeping the insides as dark as possible. This is important for the tiny light dependent resistors (LDRs) nestled in the back. The LDRs are wired to 5V, through a simple comparator to grab an amount of light from their resistance levels. These resistors supply 25 MegaOhms of resistance in relative darkness, and close to 0 Ohms in direct light. I think you can see where this is going. When there is no cup on the platform, all three lasers hit the LDRs head on, supplying our detector circuit with the information we need to determine a cup’s presence. When at least one is blocked, we know SOMETHING is in the way. Using this, we can tell approximately how tall our vessel is to be! 3 lasers allows us to detect a shot glass, low ball and highball.  We are ignoring specialty glasses like martini glasses and margarita glasses for now for simplicity. But this can’t solve all our problems. You see, glasses are often made of glass. Glass is used in many applications for its ability to NOT block light.  So how does the system handles glasses?

 

Thresholding

LDRs are not binary. They are analog (which is another whole problem which will probably get its own blog post once I solve it), meaning they have a large range of resistance, dependent on the AMOUNT of light, rather than the presence. So when a laser passes through a glass, as long as it is weakened, it will be OK. Since glasses are often made of glass >1 micron thick, the scattering of light due to the change in the speed of light is quite noticeable.  Pinholes on the sensor box will allow directed, uninterrupted laser to hit the LDRs head on, but scattered light will hit with much less intensity. A circuit can be used to measure the voltage drop from the increased resistance and “call it” at a certain point. That point is called a threshold. This threshold will need to be experimentally determined due to the near infinite variety of drinking vessels.

 

Project Progress

The laser array has eaten up a fair amount of my time, but this weekend should be a productive one for the pi bar. The design has been created, so a rudimentary parts list is ready for shopping. Once a large amount of PVC and lumber can be acquired, the machine should begin to take shape. I hope to be posting a blog entry with a frame soon, so keep tuned, and keep coding.

Spring Break Pokemon Games

Hey everybody, I’m back! The past few weeks have been a whirlwind of school work and emergencies which finally let up just in time for spring break. Because of my limited time, I was not able to work on my recipe manager or the BartenderBot (much) but I promise I come prepared.  I had mentioned before that I had a tradition of programming digital versions of my favorite drinking games over spring break. Last break I coded Horse Races, and the one before that I made Circle of Death, both of which have a post earlier. This time, I made….

The Pokemon Drinking Game

Most of you know that I love Pokemon, drinking, and programming, so this just made sense. The game itself was designed as a board game some time ago by a user named “raith”. The game has seen many modifications, eventually resulting in the Pokemon Drinking Game 2.0, a circular board based game with many drinks, complicated rules, and a guaranteed good time. The numerous rules to keep track of made this game quite difficult while intoxicated (which occurs about 1/4 of the way through). My version lets the computer worry about movement and turns and instead farms out only the drinking.

Watch the dots move....

The game in mid-play

Making it Work

This game has so many complex rules, movements, turn skips, and history checks that the vast majority of my planned architecture was useless. Unlike a project for school, or work, or fun, this project was for use within the week. As such, clean-code got thrown out in favor of making it work. That is not to say I will not revisit it and clean it up, but for the time being, it is pretty ugly.  Here’s where we sit. There are 3 java packages involved, and they should be clearly named.

Backend – This package contains the control class which controls (duh) everything about game logic, along with any necessary models.

Tiles – There were so many custom tiles needed for weird behaviors, I made a new package of just those custom Tile models.

UI – This houses the GameFrame, which displays the playable part of the game.

These packages do not necessary adhere to their strict responsibilities, but once again, speed and function were emphasized. The Control class is a rather monolithic class, keeping track of all turns, players, tiles, and UI text and screens. All other models are used to store relevant data and have a few important methods. The most important is the Tile class’s landed() function. This method takes a Player (provided by the control when a player lands on a tile) and operates on that player upon the call. This aids in skipped turns or forced moves, along with several more complicated consequences in the specialized tiles.

Help

Unlike any of my other posts, I am pleading to you for help. As I’ve described, the code is ugly, but the far bigger issue is that there are logic failures. The game “plays” and will track you to the end (though the victory image has not been added) but some of the tiles exhibit unwanted behaviors. I am aware of at least one tile where a re-roll results in a move, one which sets the next turn’s movement modifier incorrectly, and a couple other bugs, but they are rather hard to pin down where they occur.

So how you, the reader, the drinker, the good time guy can do to help is play. I have hosted the code in its usual spot on my github (here), and it is free to be grabbed and compiled. If you could play through the game and keep a list of bugs you find, I would love to finish off making this game work. Leave some bug reports in the comments, message me, or if you know me, come up and let me know where you saw problems.  Once the logic is working, I will chip away at the design and appearance until I am satisfied.

As always, code on, and thank you for your help.