Tech Thoughts

That O(n^2) algorithm you're writing in Collabedit is losing you any chance of getting that job you're interviewing for. Chances are you're comparing every element in an array to every other element in that array. Sure it's an easy solution to the problem, but that's the trick. The interviewers are looking for an efficient solution to the problem. I've read over a number of different publications for how to do well on a technical interview and I found that they just say things like "remember your data structures" and then throw you into doing problems. My goal here is to show you some of the tricks that I have discovered for solving a problem efficiently. 

So back to your O(n^2) algorithm. I have found that when you are dealing with an array you need to organize your data. If you are dealing with a problem like trying to combine overlapping numerical data structures (like the overlapping interval problem) it is best to sort your array. Then instead of comparing all items in the array to all other items, you just have to compare adjacent items. Remember that when you sort it will be O(n log n), which is better than your O(n^2). What if you aren't using numerical data types? Well then sorting doesn't really make sense and the problem probably isn't asking about overlapping intervals. What it probably is asking is to find duplicates. So how can we put the objects in some type of order? Use a hash table. I know the worst case for a hash table lookup is O(n), but every interviewer I have spoken with has been okay with using the average case of O(1). Now you can just iterate through your array and put items on the hash table if they aren't there already. If they are there, then you just found your duplicates. And hey now we're running in O(n) time. 

Oh hey, it's a problem with a binary tree I should use pre/in/post order traversal to solve this one. Hold on a second. Let's not get ahead of ourselves. Remember that any of those three traversal methods in the tree do a depth first traversal. If the question is asking about cousins in the tree, you'd better start thinking about doing a breadth first traversal. Doing a breadth first traversal is fairly straight forward. The basic idea is to take a linked list of nodes that are all on the same level in the tree and create a new linked list of nodes that are the children of the nodes in the original linked list. If you start with a linked list of only the root node, you will do a breadth first traversal of the tree. 

My Dad talks to his phone. Any time he wants to send a text, he opens up his speech to text app and begins talking like Microsoft Sam. It is actually a remarkably efficient way to input 160 characters of text, but I don't like the idea of everyone in the room hearing what I'm trying to text. I am a fanatic when it comes to different ways to enter text on a mobile device (or on a full sized keyboard for that matter. I have made the permanent switch from QWERTY to Dvorak). I've tried as many input methods on my RAZR MAXX HD as I can find. I started with the built-in AOSP keyboard then moved to Swype, but wasn't happy with either. Things got really interesting when I tried alternative swipe based keyboards like 8pen and Keymonk. It seems like my crab claw thumbs just make it impossible to type really fast and really accurately on my phone (I've tried using an iPhone keyboard and that just results in some horrific auto-corrects). 

When I came across SwiftKey, I realized the developers were on to something. While it is not perfect, it brings some new ideas to the table. Instead of trying to push directly on a key, I just mash the general area of a key with my thumb and SwiftKey knows what I mean. Even though SwiftKey can even sometimes predict the next word that I want to type, I think there are still some improvements to be made.

There is a huge market out there for the next generation of text input for mobile devices. Someone is going to make a tremendous amount of money from a simple idea for changing the way we interface with our tablets and smartphones. We need to get away from the QWERTY layout. U, I, and O are way too close together. If the vowels get spread out then predictions become easier. I do not know enough about double character frequencies to say what other letters need to be separated, but the separation is just one issue. Should Z, Q, and X really have their own button? Or could they be combined? By reducing the number of necessary buttons, the buttons can become larger and less accuracy is needed when typing. How much change can be made to the input method before people will reject it? 8pen is notorious for taking a long time to learn, but on the other hand SwiftKey takes no training at all and comes up short in the innovation category.