Category Archives: Uncategorized

Interview Questions

Given a two-dimensional array representing ascii art of an ocean with islands, count the number of land masses. Masses are connected by non-vertical continuous locations.

OLOOOO
OOLOOO
LOOLOL
LOO

 

Play game of plusses (?) and anticipate moves
——
++-++-

 

Count number of links given helper function that returns number of links on a page. Then optimize.

 

Write JSON parser

 

Create reader of python argument tree (useful to have compiler class which I didn’t take…)

Cool blub about Java sorting algorithms

We know that quick sort is the best sorting algorithm.

There isn’t a single “best” choice. As with many other things, it’s about tradeoffs.

As to the “why” question, only the original author can answer it with any certainty. However, the following is relevant:

The algorithm used by java.util.Arrays.sort and (indirectly) by java.util.Collections.sort to sort object references is a “modified mergesort (in which the merge is omitted if the highest element in the low sublist is less than the lowest element in the high sublist).” It is a reasonably fast stable sort that guarantees O(n log n) performance and requires O(n) extra space. In its day (it was written in 1997 by Joshua Bloch), it was a fine choice, but today but we can do much better.

Since 2003, Python’s list sort has used an algorithm known as timsort (after Tim Peters, who wrote it). It is a stable, adaptive, iterative mergesort that requires far fewer than n log(n) comparisons when running on partially sorted arrays, while offering performance comparable to a traditional mergesort when run on random arrays. Like all proper mergesorts timsort is stable and runs in O(n log n) time (worst case). In the worst case, timsort requires temporary storage space for n/2 object references; in the best case, it requires only a small constant amount of space. Contrast this with the current implementation, which always requires extra space for n object references, and beats n log n only on nearly sorted lists.

Timsort is described in detail here: http://svn.python.org/projects/python/trunk/Objects/listsort.txt.

Tim Peters’s original implementation is written in C. Joshua Bloch ported it from C to Java and end tested, benchmarked, and tuned the resulting code extensively. The resulting code is a drop-in replacement for java.util.Arrays.sort. On highly ordered data, this code can run up to 25 times as fast as the current implementation (on the HotSpot server VM). On random data, the speeds of the old and new implementations are comparable. For very short lists, the new implementation is substantially faster that the old even on random data (because it avoids unnecessary data copying).

Also, see Is Java 7 using Tim Sort for the Method Arrays.Sort?

I did write these methods, so I suppose I’m qualified to answer. It is true that there is no single best sorting algorithm. QuickSort has two major deficiencies when compared to mergesort (1) It’s not stable (as parsifal noted), and (2) It doesn’t guarantee n log n performance; it can degrade to quadratic performance on pathological inputs. Stability is a non-issue for primitive types, as there is no notion of identity as distinct from (value) equality. And the possibility of quadratic behavior was deemed not to be a problem in practice for Bentely and McIlroy’s implementation (or subsequently for Dual Pivot Quicksort), which is why these QuickSort variants were used for the primitive sorts.

Stability is a big deal when sorting arbitrary objects. For example, suppose you have objects representing email messages, and you sort them first by date, then by sender. You expect them to be sorted by date within each sender, but that will only be true if the sort is stable. That’s why we elected to provide a stable sort (Merge Sort) to sort object references. (Techincally speaking, multiple sequential stable sorts result in a lexicographic ordering on the keys in the reverse order of the sorts: the final sort determines the most significant subkey.)

It’s a nice side benefit that Merge Sort guarantees n log n (time) performance no matter what the input. Of course there is a down side: quick sort is an “in place” sort: it requies only log n external space (to maintain the call stack). Merge, sort, on the other hand, requires O(n) external space. The TimSort variant (introduced in Java SE 6) requires substantially less space (O(k)) if the input array is nearly sorted.

–Josh

source: http://stackoverflow.com/revisions/15154287/2

Softball Stats/Pro

I finally got the Eclipse ADT reinstalled and started digging through the code for Softball Stats and Softball Stats Pro. I’ve since discovered:

  • I’m a bunch of revisions behind of the AdMob API
  • All the ad calls are different in the new JAR
  • I have no idea how they work now
  • Most of the UI techniques I built to work with AndroidOS 2.0+ are also horrendously behind and mostly deprecated
  • Who still uses 2.1-3 anyway?

I was going to try modifying the old code to work on new platforms, AndroidOS 4.0+, but right now it seems like I’d be better off building it new from the ground-up with the modern design techniques. I’m dreading this though since it means I have to build the app again and it takes A LOT of time. Not that I don’t have it but damn that’s a lot of work to throw away. I’ll still keep up the old version and probably change the manifest so that it doesn’t show up in the market for devices running 4.0+. This does have some good points:

  • New refreshed UI using much improved 4.0+ naviation
  • Reconfigured databases that aren’t slow and overly complicated
    • But I’d have to include an “upgrade” option to read in the old database into the new one
  • Proper threading so as the database gets large it doesn’t hold up the UI from loading
  • Additional stats to make it more useful for baseball players (increase the userbase)
  • Include better export options to share the data with other people using CSV/spreadsheet files

This is going to take a while.

Problem of the Day: Tic-Tac-Toe (update)

Whew. TicTacToe is quite the time suck. I made a new TicTacToe class to handle creating a board, adding moves, checking for a winner, and printing the results. The board is still pretty dumb; each move attempt is started by getting a random integer [0-3), checking that it’s a legal move, then making the move and switching players. The entire board is always filled up but only prints out if there is a winner. Because “X” gets to go first every time it also wins a large percentage of the time, I check for “X” winning first to avoid a board having two win-conditions.

I did re-learn the ternary operation and figuring out how to teach a computer to play TicTacToe was a useful thought exercise. I might spend some time making the board smarter as far as choosing positions and checking for wins. Maybe.

Problem of the Day: Tic-Tac-Toe

Computers are great at repetitive tasks, and tic-tac-toe more often than not is very repetitive. Today’s problem is to make a Tic-Tac-Toe solver with or without an AI; to make things easy at first I’ll just make it play randomly.

  • in the case of a draw, print an empty board and “Draw”
  • in the case of a win, print out the completed board and who wins
  • run until either player has 10 wins

Finding win conditions is the hardest part so far as the program has to watch each move and check for three matching pieces on each horizontal, vertical, and diagonal axis. Initially I’ll do the check manually after each move; it’d be much cooler for each piece to check for a win on its own by analyzing each adjacent piece. Mark that down for the second iteration and the AI for the third.

Tic-Tac-Toe

HAPPY MONDAY!!!

Today’s Problem of the Day is to implement an automated version of our favorite childhood game, tic-tac-toe. Your program can assign random moves for X and O or you can implement some AI to favor one over the other. When someone wins print out the board and who won. If the game is going to be a draw print out the board and print out that it will be a draw.

Based on these conditions your program should never print out a full board unless the final move is a game winning move. If a game is going to end in a draw just print out the board. The program should run until X or O has won 10 games.

X

Play Store app updates!

I know I’ve been saying it for a while, but I swear eventually I’m going to un-tie the database query from the UI thread to stop the app from hanging on large imports. Honestly it’s on my To-Do List. Check it for yourself. See? Right there at number 4. When that day comes, hoo boy you’ll all love it. Also on that list is a UI refresh, turns out white letters on black background ISN’T the best for battery life. Heh, the more you know. Oh and a UI design for larger screens, which soon even phones are hitting (thanks Samsung and your fascination with phablets).

More importantly, I really need to get on that app that connects to the qBittorent web-UI so I don’t have to keep awkwardly using the Chrome browser to manipulate a screen that works best with a mouse. I’m sure a lot of other people could use it but really I tend to make apps that I want. So someday once I’m tired of the website on the mobile Chrome browser.

But in more important news, back to a new hardcore Minecraft world! So far I’ve gone through 12 of them, finding more and more stupid ways to die in each one. The worst was the 10th, where I was so desperate for diamonds I was digging up the world and didn’t notice the three creepers that were right behind me.

Problem of the Day: The Lone Survivor (update)

Double-linked-list worked but the link to move backwards, .prev, wasn’t necessary. I created a package of datatypes I’ve made then imported a Node object to create the list; since I had the option of including a link to the previous node I figured I’d use it. My 64-bit Java 1.8 install and Eclipse install can handle a total of about 3,500 servants; anything higher and it runs out of memory and starts losing nodes which causes null pointer issues.

The comments and I agree that given 1,500 servants the winner is the 953rd servant who kills the 1,456th servant. Most used some sort of data structure like I did, but a few pointed out that there’s a mathematical function, a circular left-shift, that does the same result. Probably can handle much larger groups of servants as well since it doesn’t actually have to create an object or instance of each one. LEARNDING!

So far doing the Problem of the Day has been entertaining and dare I say something I look forward to each day. I don’t try to finish first as I’m sure they’re put up while I’m still asleep and solved about an hour later. As far as giving something programming to do everyday I’m the real winner. /cue sappy “lesson learned” music from 80’s high school movie

Problem of the Day: The Lone Survivor

This is a bit morbid and could easily be more of a math problem but computers are just so good at maths it’s an easy fit. Recursive or repetitive function that continues to eliminate the even numbered entries until only one is left. It seems like the 1st servant would always be the one to start everything but the comments and I agree that it continues in a loop; not necessarily stopping then starting with the 1st servant again.

This moves to a circular pattern throughout the servants. I thought an array at first, I always go to arrays it seems, but a linked-list (or conveniently a double-linked-list that I already made a couple POTDs ago) would be best since the size is constantly being dropped by one. The modification will require the last entry to point to the first entry once the entire thing is set up, then it just keeps removing the next-next entry until there is only one entry left.

But how to track only one entry being left…

The Lone Survivor

There are 1,500 loyal servants sitting around the king’s table when they decide to play a little game. The 1st servant gets a sword and kills the 2nd servant. He then gives the sword to the 3rd servant, who then kills the 4th servant and then gives the sword to the 5th. This continues so that the 1,499th servant kills the 1,500th servant and gives the sword back to the 1st servant.

Now the 1st servant kills the 3rd and gives the sword to the 5th. This process continues until only one servant remains. Which number servant is the lone survivor?

X