3 Geeky Questions

I had a technical conversation recently that reminded me of what it really means to get back to basics in software development. Frankly, I have been managing people and drawing pictures for so long I was initially stumped by some of these. I am ashamed of myself for not having these answers on the tip of my tongue. After some thought, I can deal with it better the next time someone wants to grill me on these pieces of minutia.

When FunctionA hands control to FunctionB at runtime, how does FunctionA resume control when FunctionB is done processing?

I really fumbled this one when it was posed to me. Upon further reflection my answer is: FunctionA inserts into the stack the address of the point of execution to be resumed, and then inserts the address for FunctionB such that as the stack is processed FunctionB is called, followed by FunctionA. Did that make sense?

What is the difference between a thread and a process?

I defy you to answer this question without using the words “process” or “thread” as part of the definition. Here’s my attempt:

A process is managed directly by the OS while threads are managed within a process and not directly available to the OS . Further, threads share resources within a shared memory space and processes do not. Duh, right?

Given a list of all words in the English language, and the ability to pre-process this list before using it, write a function that finds all anagrams of an input word.

My original approach lamely tried to use a sorted tree. For shame.

This a 2 part problem. Firstly, create a lookup table (maybe in a DB or something) with 2 columns, hashcode and word. Like so:

Hashcode (Key)	Word
########	cat
########	act
########	park

The trick is in how we calculate the hashcode value. Good hashcode algorithms factor in a dynamic component such that the hash will contain a degree of randomness. A typical way to do this is to use the address location of the object being hashed as a component of the algorithm. For our purposes, we want to actually calculate the hash in an ineffective way that produces a non-unique key we can use to equate anagrams. Like this:

int hashCode = 1; 
for (int i=0; i<s.length(); i++) hashCode *= s.charAt(i); 

This simply produces a hash, or a key if you prefer, for each word and has the side effect of creating the same key for each word with the same length and letters.

hashMyWord(“CAT”) == hashMyWord(“ACT”)
because:
hashMyWord() == multiply the letter codes together
therefore:
C*A*T == A*C*T

Now that we have our effective lookup table, we can simple use a numeric lookup when we define our FindAnagrams(string word) function. Now we simply hash our input word and search our list of words using the hash so we are using number comparisons. This creates an efficient, single-pass lookup algorithm. We can speed our lookup even more by sorting our lookup list by key value.