# Copy Paste Select-All Problem

In the Copy Paste Select-All problem, a user wants to replicate the most amount of ‘a’s with the least amount of keystrokes. I was asked how many keystrokes would be necessary to produce 50,000 ‘a’s.

There are 3 basic ways to create ‘a’s: Pressing ‘a’, Selecting-All -> Copying -> Pasting, and Pasting what is in the clip board. Pressing ‘a’ will cost 1 keystroke while selecting-all, copying, pasting will cost 2 each. So just pasting will cost 2 keystrokes, but selecting-all -> copying -> pasting will cost 6.

Now let’s create the recursive definition of our dynamic programming problem. $$L(x) = { \mbox{max}[ L(x-6)*2,L(x-2)+buffer,L(x-1)+1 ] }$$

# Another Interview Question

This is another problem that is bound to come up during an interview.

How would you tell if there is a loop in a linked list if there is an arbitrary length, using little to no memory?

The idea in solving this problem is having two iterators, one of which iterates faster through the linked list than the other. This way, the faster moving iterator catches up to - or laps - the slower iterator in the event of a loop. Otherwise the first iterator will find the end of the list.

In the following code example I made the one iterator move twice as fast as the other. At each step I check to see if the iterators point to the same object or the end of the linked list is found.

Compile with:

# An Interview Question

Here’s one of the (admittedly easy) questions I received during an interview at Palantir:

Write a function that will convert an integer into a list of single digits.

So, how do you separate individual digits out of an integer? Simply put, division.

Say we had the number 112095. If we divide this number by 10 we achieve 11209.5 or 11209 remainder 5. The remainder will allow us to isolate the least significant digit. The main idea lies within taking the modulus of the original number by 10.

This is a quick java program I wrote up that accomplishes this:

# A Brief Review: Regular Expressions (in Linux)

If you’re like me, you learned regular expressions in Theory of Computation and quickly forgot about them. Regular expressions are a powerful tool on the command line and can save you copious amounts of time when searching for patterns.

A quick side note about regular expressions - they were first implemented by Ken Thompson in his editor QED. Later, he took this same idea and put it the linux editor ed. From this editor is where the linux command ‘grep’ was born. ‘g/re/p’ meant Global search for Regular Expression and Print matching lines in ‘ed’.

There are two basic sets of regular expressions: basic and extended [these are both POSIX]. Most programs in linux use the basic regular expression type. Here’s a list of some of the programs that use the basic format and extended format (taken from http://www.grymoire.com/Unix/Regular.html)