Cool interview questions

Q – What 3 Unix utilities would you take to a desert island, and why?

A: Find, Grep, hmm, gnuplot. Find and Grep are very capable, deep, and reliable. It would be easier not to have to re-do them myself, whereas sort, ls, df, even ps aren’t nearly as difficult to re-write myself.

Q: You have two strings, needle and haystack. Both are very long- haystack is at least as long as needle, could be longer. Potentially, millions of characters.

Q1: What’s the fastest way to determine whether all the characters in needle are found in haystack? Order doesn’t have to be the same, but if there are 27 ‘A’ characters in needle, we want to know whether there are at least 27 in haystack. And on through the rest of the, say, 8 bit character set.

A: Obviously, the trick here is to NOT do an N * N solution where each character in needle results in a read (or even a partial read) of haystack. Yet, one can’t avoid reading needle at least once. So: make an array with 256 elements, coresponding to character values 0 to 255. Initialize all array members to 0. Read through needle, incrementing the count for each character value when that character is encountered. For example: needle is “needle”. Character counts are:

d: 1
e: 3
l: 1
n: 1

Once needle has been completely read and counted, start reading haystack, and *decrement* the count (but stop at 0)  for each character value whenever one of those characters appears. The read through haystack ends when either all the character counters are “0”, which is success, or when haystack is exhausted AND at least one character counter is greater than zero.

This solution is on the order of 2N + some constant, much better than the N * N obvious technique.

Q2: The A1 technique requires 256 counters of 20+ bits – most likely 32 bit integers. So it requires 1K bytes. How can the job be done with the very least amount of memory, but as long a run time as it takes?

A2: 2, 32 bit integers, and a character, are enough. One integer is an index (indice) into needle or haystack, one is a counter. The character is incremented through all possible character values. For each character value, the count is zeroed, then needle is stepped through, adding one to the counter for every instance of the target character code. After needle is completely counted, the same index is used to step through the locations in haystack, and the integer in the counter is decremented (provided it started off positive) any time the target character is found. But not below 0. If any trial gets to the end of haystack with a non-zero counter value, return a fail and give up. If the counter gets to zero while decrementing, look no further, increment the character, start on the next character.

3 responses to “Cool interview questions

  1. find and grep were my first two choices, too. Just before reading this, I learned that a domain name that was never supposed to change just did, and I’d have to track down all the unfortunately hard-coded references to it.

    But if you were on a desert island with a working, and presumably networked, UNIX box, wouldn’t ping, traceroute, and sendmail be the most useful things, so you could send instructions to be rescued? 🙂

  2. Hi Eric,
    YES, ping, traceroute and sendmail would be the most useful things to get you rescued from the putative desert island. That’s a real step-back and answer the big question first approach. Wonderful! I’m going to point that out to Sam Stafford, who asked me the question when I was interviewing at Perforce.

    I was pretty sure find and grep were 2 out of 3 of Sam’s answers, but I stand corrected:

    Sam Stafford wrote:
    ” Going by what I use most often, I’d say “grep”, “sed”, and “wc”.

    If I thought I’d get away with it, I think my new tech interview question would be this game:

    I apologize in advance for ruining your productivity for the rest of the day. 🙂 ”

    So do I!

  3. My pal Gary wrote me with his answers:

    “As far as answering the 3 utility question:
    mv so I could get off the f*****g island
    cp so I could clone myself and have someone to talk to
    netstat so I could find a way to connect to the outside world.”


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s