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.

How to set up work space (directories) for software development:

How to lay out a work space for software development:

Q: Why not use
/Users/yourNameHere/blah.blah – everything in the login directory?

A:Its messy, impractical hard to export.

Requirements for a software development workspace:

1. Makes it easiest to do things the ‘right’ (you choose ‘right’) way.
2. Source files and support stuff can easily be version-controlled: using a third party tool (Perforce, etc) or informal methods (numbered revisions in a “History” or “Rathole” or per-file subdirectory below the working directory, etc.
3. Environment neutral: Easily exported to someone else’s environment (Some people don’t value this- I like to send out examples that arrive workable and sometimes I ask others for help. If you don’t need that, by all means have a big alias file and a bunch of stuff in /bash_profile… But do consider packaging all of that stuff so you, yourself, can move from system to system, OS to OS…)
4. Scalability: One file, 100 files, 100,000 files (i.e, no bottom)

I’ve seen a bunch of somewhat thoughtlessly assembled setups at a variety of work environments. Back in the mists of time, at Lomac, in 1979, we didn’t have password protection on our 8 inch floppy environments (RT-11 for PDP-11/03, and CP/M for S-100 Z-80s). Easy stuff. Boot up and, on a build disk, there it all was. (WERE there subdirectories in RT-11 and CP/M?, Google knows…)

At Perforce, the Performance Lab used a nice organization of:

/Users/yourNameHere/- anything and everything, but no production stuff here.

Installed stuff, supported by two additions to PATH

export PATH=$PATH:/Release/namedRelease_*:/Work/yourNameHere/namedRelease_*:.

This then became:
/Releases/namedRelease_1/usualTopLevel
/Releases/namedRelease_1/usualTopLevel/bin
/Releases/namedRelease_1/usualTopLevel/etc
/Releases/namedRelease_1/bin
/Releases/namedRelease_2/usualTopLevel
/Releases/namedRelease_2/usualTopLevel/bin
/Releases/namedRelease_2/usualTopLevel/etc
/Releases/namedRelease_2/bin

Database location:
/db/namedRelease_1/
/db/namedRelease_2/

Leading with a named release allows Path to mix and match generically named 3rd party tools. Like Source Control Management…

Project work:
/Work/yourNameHere/namedRelease_1/
/Work/yourNameHere/namedRelease_2/

and if you absolutely, positively, have to work in /Users…
/Users/yourNameHere/namedRelease_1a
/Users/yourNameHere/namedRelease_3b

What NOT to do:

The “namedRelease_*” paths looks unnecessary, up to the time you need to maintain two parallel developments. You can keep one in /Releases/usualTopLevel/… and one in /Users/yourNameHere/usualTopLevel but its all too easy to get to:
/Releases/usualTopLevel/…
/Releases_1/usualTopLevel/…
/Releases/usualTopLevel_2/…
/Users/yourNameHere/usualTopLevel/…
/Users/yourNameHere/usualTopLevel_A/…
/Users/yourNameHere_2/usualTopLevel/…

and having to hand edit these irregular paths here, there and everywhere. Ask me how I know. 🙂

And what I plan to do here at home:

/Work/Bill4/rel_1/
to start with. Its pretty light weight. just took a few minutes to set up.

Fun with string comparisons in BASH/Bourne Shell. Unix/Linux/Mac OS X/Cygwin

Short form:
Compare two strings, in BASH shell script. “$?” is 0 (true) if they are equivalent:
$ t3=a; o3=a; test “$t3” = “$o3” ; echo $?
0

Capture the true/false (0/non-zero) result in a variable:
$ t3=a; o3=; test “$t3” != “$o3” ; z=`echo “$?”`; echo $z
0

Remember $? is updated after every operation, so capture its value DIRECTLY after the test!

Long form::
As used as I’m getting to the generally low quality of software help/tutorial/manuals, this one is really a new low.
Here on page 133, in chapter 5 of the Fourth Edition of Unix Shell Programming by Lowell Jay Arthur & Ted Burns, in table 5.7, states:

s1 = s2 True if strings s1 and s2 are identical

BALONEY!

babbott$ tF3=a; oF3=b; test tF3 = oF3 ; echo $?
1
babbott$ tF3=a; oF3=a; test tF3 = oF3 ; echo $?
1

What this “1” means is that “tF3” and “oF3” are DIFFERENT strings. The comparison fails, and the 1 indicates “false”. “true” is 0.

But I’m getting wise to this stuff, So I put dollar signs ahead of them to mark them for substitution and double quotes around them specifying only $, \ and ` (back quote or back tick or graves have special meanings, AND allowing the reference to be processed even if the variable doesn’t exist and has never bveen assigned a value: Anyway:

babbott$ tF3=a; oF3=a; test “$tF3” = “$oF3” ; echo $?
0
babbott$ tF3=a; oF3=b; test “$tF3” = “$oF3” ; echo $?
1

NICE! FINALLY. I’ve been trying for 2 1/2 working days to figure out how to do a string variable to string variable comparison.

The really slick thing, which is their justification, is that the double quotes protect the code from uninitialized variables:

babbott$ tF3=a; oF3=; test “$tF3” = “$oF3” ; echo $?
1
babbott$ tF3=a; oF3=a; test “$tF3” = “$oF3” ; echo $?
0
babbott$ tF3=a; oF3=a; test “$tF3” != “$oF3” ; echo $?
1
babbott$ tF3=a; oF3=; test “$tF3” != “$oF3” ; echo $?
0

Gee. Well at least I know what to expect for a while.

Oh yes, if you want that pass/fail value to use for something further, here’s the only way I”ve come up with so far- I HAVE to believe this is sillier than it needs to be, and I’ll improve it when I get smarter about this stuff. But it works, its bullet-proof and I don’t have to think about it for the moment:

babbott$ tF3=a; oF3=; test “$tF3” != “$oF3” ; z=`echo “$?”`; echo $z
0
babbott$ tF3=a; oF3=a; test “$tF3” != “$oF3” ; z=`echo “$?”`; echo $z
1

And if you wonder why I just don’t use a compound statement with -a and -o switches for AND and OR logic, its because I’m comparing four pairs of strings. If all the pairs match, then do “A” else “B” Pardon me if I don’t really want to present an 8 argument test with two levels of parenthesis, 4 equals operators for the string pairs and 3 -a operators for the booleans, to future maintainers.

Bill

Underscore “_” is *sometimes* a metacharacter in the Bourne shell, and \ doesn’t protect it, but ” does!

Hahaha. Jokes on me.
Read ’em and weep:
———————————————————–
$!sh
export FOO=2
export BAR=5
touch java.hprof.txt

cp java.hprof.txt “a$FOO_$BAR.txt” produces: a5.txt
cp java.hprof.txt “a$BAR_$FOO.txt” produces: a2 .txt
cp java.hprof.txt “aBackSlash\_$FOO\_$BAR.txt” produces: aBackSlash\_2\_5.txt
cp java.hprof.txt “a_$BAR_$FOO.txt” produces: a_2.txt
cp java.hprof.txt aIndiQuoted”_”$FOO”_”$BAR.txt produces: aIndiQuoted_2_5.txt
cp java.hprof.txt “aNoDash$FOO$BAR.txt” produces: aNoDash25.txt
cp java.hprof.txt “adot.$FOO.$BAR.txt” produces: adot.2.5.txt
cp java.hprof.txt “aquoted_$FOO_$BAR.txt” produces: aquoted_5.txt

Oh for crying out loud!

Well, ok, you have to quote the underbars to get them through, at least its possible, but what can possibly justify:
export FOO=2
export BAR=5
cp java.hprof.txt “a_$BAR_$FOO.txt” produces: a_2.txt
cp java.hprof.txt “a$BAR_$FOO.txt” produces: a2 .txt

its $FOO that’s getting through, but the underbar BEFORE it doesn’t!!! Its the underbar before $BAR that gets through. That’s messed up, IHMO.

Dykstra probably has a foot note explaning why this is what I should expect. Bleh.

RIght, then.

Bill

Even better than NetBeans, HProf comes with the JVM in 1.5 and 1.6…

Bingo! NetBeans’ profiler is very nice, thank you, and WAY easier to get started with than Eclipse, but its a GUI and you run it interactivly- good for some things, not for automated performance testing, which is what I’m trying to set up. Well, turns out HProf (Heap Profile) is a tool built into the Java Virtual Machine and available as a launch-time option whenever you run a Java program. The example on Sun’s web page profiles “javac”- pretty confident there. So I tried it on Mac OS-X and Win XP and it works just fine on both. You get percentages, not absolute times, but it gives you the total time and you can multiply out the absolute time if that’s what you really want. I must say I’m enjoying this again. Trying to get JMeter and TPTP running under Mac OS wasn’t any actual fun, since they didn’t work. In fact, having put TPTP into Ecipse, I can’t use Eclipse anymore… that’s a useful definition of software that’s not quite ready for prime time- it installs successfully, then tells you it doesn’t support your platform when you try to run with it, and it prevents your IDE from working until you figure out how to remove it. Joke’s on me, eh?

Anyone have expereince running NetBeans’ Profiler from command line?

Just found the following about running the NetBeans Profiler with Eclipse…  not command line but headed that way, maybe…

http://www.jroller.com/ortegon/entry/on_profiling_eclipse_rcp_applications

I left the following comment for Mario and I wouldn’t mind answere from anyone who reads this plea anywhere!
I’m trying to find a platform neutral profiling tool for Java- I need to support *nux, Windows and Mac OSX (yeah, BSD, but…) and I need to run from a command line so I can automate it. The Java library I’m testing is a thin client that talks TCP/IP to a server, all I care about is the client library performance, but I care on all three major platforms.

I tried to get JMeter going and realized it wasn’t aimed at what I was doing. I installed TPTP and was really hoping it would do the job but then discovered it has NO agent for Mac OSX and hasn’t for years. Phoey!  So I got NetBeans, imported my code (trivial, why can’t Eclipse be this easy?) and happily profiled on my Mac. Good so far.

Does anyone have experience running the NetBeans Profiler from Solaris, Linux, Mac OSX and/or Windows command lines?

Other all-platform Java profilers?

Many thanks for any help!!!

Bill

50 books every geek should read- from Monster.com

Ok, lets see: I’ve read 16 of these, gave up on another and have 2 in-progress.

I think there are a few good books missing:

1) “The C Programming Language” – Kernighan and Ritche. Not only a great book about programming, especially for beginners, it also shows how clear a programming text can be, how little needs to be said, and how to spiral around the same problems with increasingly capable and complicated programs.

2) “The C++ Programming Language” – Stroustrup. By comparison to C, a much thicker book, containing K&R’s language and a whole lot more, for practical coding and for object oriented techniques.

3) “The Codebreakers” – Herman Kahn A huge book and one that ends in the era where crypto was still a government issue, mostly. But a great history, and clear proof that no cypher system, or code book, is 100% unbreakable.

4) “Seizing the Enigma” – most complete discussion of BREAKING Enigma I’ve seen so far. There are any number of good lessons here, starting with, a small, motivated, team can accomplish what is considered impossible. Never treat the opposition with contempt. Define your requirements as well as you can, do what you can to satisfy them, pay attention to what actually happens.

The actual analytic technique to break Enigma was cooked up by two Polish intelligence officers who could see how the wind was blowing in the late 1930s. When the Germans invaded, they escaped with their method and presented it to the French. The French passed it on to the British before they collapsed. The technique wouldn’t do for rapid recovery of plain text from a well operated system but it could break in by brute force, with some time, and it could also rapidly exploit any laxness in technique by the cypher users. Whereas the Germans believed that Enigma was essentially unbreakable and never seriously looked for its weaknesses, or their own in using it.

Code and cipher trade-craft was good in the Kriegsmarine, so-so in the Wehrmacht and lousy in the Luftwaffe, oddly echoing Hitler’s complaint that he had a Christian Navy, a Reactionary Army and only one National Socialist (Nazi) armed force, the Luftwaffe. The Brits mounted a frontal assault on Luftwaffe Enigma traffic and got what they needed because of bad practices by the users. With the Wehrmacht they got enough to combine with conventional intelligence, what the Soviets gave them from “Lucy”, from the Italians sending cables to each other, etc., to get the job done. The Kriegsmarine used Enigma intelligently, so that frontal assaults hit a blank wall. Fortune gave the Brits the keys, the initial rotor position for each message, occasionally, and they knew what they were missing, so they made it their business to GET the keys, through espionage, Soviet salvage of a sunken German ship, the capture of a shipboard weather station in the North Atlantic, the US Navy’s capture of U-505. Every six months when the key changed, they had to get the new one and did, EACH TIME. And tight security at the Allied end allowed the Germans, all of them, to ignore any suspicion that their cyphers and codes were less than 100% secure. They had no “Red Team”s, or even someone looking at the pattern of Allied luck in finding lone U boats, bombing the right place at the right time, etc. Convinced of their own superiority, like the Japanese, they caught “victory disease” and when the tide turned, retained a confidence that events did NOT justify. Lucky for us.

“Snow Crash,” Neal Stephenson
“Neuromancer,” William Gibson
“I, Robot,” Isaac Asimov  <———- 1
“Hitchhiker’s Guide to the Galaxy,” Douglas Adams  <———– 2
“Do Androids Dream of Electric Sheep?” Philip K. Dick  <————– 3
“Ender’s Game,” Orson Scott Card
“The Time Machine,” H.G. Wells  <————– 4
“Microserfs,” Doug Coupland  <————— 5
“Flatland,” Edwin A. Abbott  <——- tried, couldn’t get into it. Should try again I suppose
“1984,” George Orwell  <—————- 6
“Brave New World,” Aldous Huxley  <————— 7
“iCon,” Jeffrey S. Young and William L. Simon
“iWoz,” Steve Wozniak and Gina Smith
“Hard Drive: Bill Gates and the Making of the Microsoft Empire,” Jim Erickson
“The Visual Display of Quantitative Information,” Edward Tufte  <——————- 8
“Don’t Make Me Think: A Common Sense Approach to Web Usability,” Steve Krug
“The Non-Designer’s Design Book,” Robin Williams
“Tog on Interface,” Bruce Tognazzini  <—————– 9
“User Interface Design for Programmers,” Joel Spolsky
“Revolution in The Valley: The Insanely Great Story of How the Mac Was Made,” Andy Hertzfeld
“The Soul of a New Machine,” Tracy Kidder  <——————- 10
“Where Wizards Stay Up Late,” Hafner and Lyon
“Dealers of Lightning: Xerox PARC and the Dawn of the Computer Age,” Michael A. Hiltzik
“The Cuckoo’s Egg,” Cliff Stoll  <—————- 11
“The Perfect Thing: How the iPod Shuffles Commerce, Culture, and Coolness,” Steven Levy
“Longitude: The True Story of a Lone Genius Who Solved the Greatest Scientific Problem of His Time,” Dava Sobel  <– 12
“The Code Book,” Simon Singh
“Cryptonomicon,” Neal Stephenson
“Crypto,” Steven Levy
“The Pragmatic Programmer: From Journeyman to Master,” Andrew Hunt, David Thomas
“Code Complete: A Practical Handbook of Software Construction,” Steve McConnell  <—— working on it
“Design Patterns: Elements of Reusable Object-Oriented Software,” Erich Gamma, Richard Helm, Ralph Johnson, John M. Vlissides  <— working on it
“Dreaming in Code,” Scott Rosenberg
“The Mythical Man-Month: Essays on Software Engineering,” Frederick P. Brooks  <———- 13
“Beautiful Code: Leading Programmers Explain How They Think,” Andy Oram
“Cathedral and the Bazaar,” Eric S. Raymond
“The Long Tail,” Chris Anderson
“The Future of Ideas,” Lawrence Lessig
“On Intelligence,” Jeff Hawkins
“In the Beginning was the Command Line,” Neal Stephenson
“Code: Version 2.0,” Lawrence Lessig
“The Wisdom of Crowds,” James Surowiecki
“The Singularity Is Near: When Humans Transcend Biology,” Ray Kurzweil
“Gödel, Escher, Bach,” Douglas Hofstadter  <——— 14
“Gut Feelings,” Gerd Gigerenzer
“A Brief History of Time,” Stephen Hawking  <————- 15
“Hackers and Painters: Big Ideas from the Computer Age,” Paul Graham
“The Evolution of Useful Things,” Henry Petroski  <————– 16
“Getting Things Done,” David Allen
“Upgrade Your Life: The Lifehacker Guide to Working Smarter, Faster, Better,” Gina Trapani

“Gut Feelings,” Gerd Gigerenzer

SPOILER ALERT! More about the NetBeans Anagram game

If you want to read about the NetBeans Anagram.java program but do NOT want a hint, just scroll down past this post to the one below.

So you’ve guessed by main force or cheated any number of ways and answered one or two of the anagrams that the Anagram program that comes with NetBeans has. You’ve worked out the plain text for

maibuguos

for sure.

You only need one answer to work out the rule to use, but with the first answer and the answer to this question, you can easily work out how the scramble works- you aren’t s’pozed to just sit there and cheat, there’s an algorithm. Find it and you can just type back the answers, one after another. Makes the program far more entertaining to use than having to look stuff up.

Bill

Java run-time Profiling. NetBeans seems to run, Eclipse TPTP won’t, (!) on a Mac…

Here’s some hard-won wisdom that I’ll gladly share with others

1) If you’ve got a Java library that forms an API to some other thing, and you want to test it, JMeter may not be the best vehicle. This is because JMeter wants to get between the client and server… at which point, how you test the client becomes a bit of a mystery to me! I’ll revisit this when I’ve got a bit more experience, but I have a running program, no UI but works creat from a command line or inside Eclipse. JMeter wants me to add stuff  before it will profile it. Hmm. Next.

2) TPTP sure looked good when I was reading the description and I got to be a bit more mindful in downloading and adding it- copied its jars, etc, from where it unzipped its …/features and ../plugins directories. (NOTE: cp -rp : you need this to be recursive !) into …/eclipse/features and …/eclipse.plugins. I did NOT copy any file with the same name and time stamp as was already present. All looked good, there was the test and profile icon in the menu bar and everything. But there’s no Agent for Mac OS X, just Windows and *nix. There’s an open bug with 70+ responses to it in the Eclipse bug tool, nobody has come forward with a complete, working, version and the project management (this is open source freeware…) says they’d like to deliver the Mac OS X version but hasn’t got the resources… I can’t figure whether to laugh or cry! Maybe I should put my old shoulder to this wheel, when I am competent enough. Crazy making. Its like flying into 1995 and being told that professional programmers don’t use Macs. Malarkey, but there were planty of people saying it. If doing Java development, compile once, run on all platforms, blah blah, can’t be made to work on a Mac at this point in history, there’s something very odd. How the heck to developers using Eclipse work on their shiny new Macs? Without profiling or testing? Hard to believe.

3) SO, now I’m running NetBeans and I have to say it downloads and installs pretty quick, and appears to have a testing tool-kit built in, not a secondary download, which is nice. Here’s what I’ve learned about it:

NetBeans has an Anagram example program. Of course, you have to build it, and when you bring up the sources, you are offered a panel layout tool where you could pick additional events or add stuff or mess up the demo 100 different ways in 5 minutes or less. Don’t! Don’t add anything.  Just save and build. It runs and now you’ve got a NEW problem- you’ve created an anagram game with complex words and you aren’t thinking anagrams and haven’t got a clue what the plain text for

“batsartcoin”,
“maibuguos”,
“ratimhteci”,

should be.  Or maybe you do. Think about Java the language and the conceptual space it exists in.  I won’t spoil it by giving the plain text here or any complete solution. You can exercise your creativity, just like you should, do a search for “batsartcoin” and follow the hints you find.

Of Course you should learn how to find things like constant strings with the NetBeans IDE, and you should probably learn how to do it from a command prompt (or cygwin on Windows) too. And you can exercise your clever muscles looking on the web, where you can find the plain text, as a literal, or as a result from the anagram breaking tool(s) that exist out there.

BUT let me just say, after you’ve cheated for an answer or two, or racked your brain and gotten an answer or two just take a look at the anagrams and plain texts.

Bill

Now that’s odd… Java really IS different

My friend Harrison sent me a  Java file that was giving him trouble. He wanted to read in an Integer from in a command-line program. He found the method readInt() in the class Console. But it wouldn’t compile:

for ( i = 0; i < 5; i++)
System.out.println(“Array[“+ i +”] = “+ array[i]);
String name = null;
int age = 0;
age = Console.readInt(“Enter Age:”);
}
}

PersonTest.java:74: cannot find symbol
symbol  : method readInt(java.lang.String)
location: class java.io.Console
age = console.readInt(“Int Enter Age:”);
^
1 errors

I did a little searching and found suggestions that he was going in the right direction:

   char letter = Console.readChar("Enter a letter: ");
   double d = Console.readDouble("Enter a real number: ");
   int i = Console.readInt("Enter an integer: ");
   String name = Console.readLine("Enter your full name: ");

http://faculty.cs.wwu.edu/martin/Software%20Packages/BreezyGUI/breezyguijavadoc/breezygui/console.html

hahaha! Turns out breezygui.console isn’t the same as console… the base language doesn’t actually have the readInt method, or readChar or readDouble. But apparently C# and or J++ and/or some dialect/library for C++ DO have a Console class with a readInt, readChar and readDouble members…

SO… you have to be VERY careful what the on-line document you’re counting on really says. It might have the method you want but only in a library you don’t have, or in another language completely. Ooof! is this fun or what???

Of course I showed Harrison how to get integer, double and char values he wanted. That’s what friends are for.

So be careful what you read and believe. Including this!