[patio11]

A spiritually similar question at a previous employer resulted in many candidates attempting to iterate over the dictionary rather than iterating over the string. We hired them. At least they could iterate over a dictionary. That's a surprisingly rare skill in the hiring pool.

Maybe I'm just getting cynical in my old age, but sometimes I think the world is awash in incompetence. We see so much of it in tech because our incompetencies are (marginally) harder to hide.

[dxbydt]

>sometimes I think the world is awash in incompetence. We see so much of it in tech because our incompetencies are (marginally) harder to hide.

A very candid Philip Greenspun in Founders@Work( p341-2) : "In aviation, by the time someone's your employee, their perceived skill and actual skill are reasonably in line. JFK Jr is not working at a charter operation because he's dead. In IT,you have people who think 'I am a great programmer'. But where are the metrics that prove them wrong ? Traffic accidents are very infrequent, so they don't get the feedback that they are a terrible driver.

Programmers walk around with a huge overestimate of their capabilities. That's why a lot of them are very bitter. They sit around stewing at their desks. That's why I don't miss IT, because programmers are very unlikable people. They are not pleasant to manage."

[nasmorn]

I second that. For musicians it is hard to hide their incompetence, for programmers it is just a matter of picking the right succession of jobs.

[onemoreact]

I like that you accepted new approaches as valid even if a candidate did not finish them. Reading this I can’t help but think how this person falls into the java trap of trying to make a ridiculously generic solution which I would consider a danger sign but plenty of people love to see.

So, assuming a real world input and real world dictionary you can try plenty of things that break down for a dictionary that includes four hundred A’s but are actually valid solutions. Also, if you want a fast real world solution then sticking with a pure lookup dictionary would slow things down. Being able to toss 5 letters into a lookup table that says the longest and shortest words that start with those letters would save a lot of time. Basically, ‘xxyzy’ = null, null saves you from looking up x to the maximum word length in your dictionary. Secondly sanitizing inputs is going to be both safer and faster. And anything you are coding in 45 minutes is going to be a long way from production ready code.

PS: Even with backtracking you can code an O(n) solution for vary large input sets. Just keep track of the K best output sequences that are aka N, N-1,N-2,…N-K.

[arethuza]

Many years ago ('97) we had a Java programming test for new hires that included a question that involved iterating over a Hashtable containing String keys and values and printing them all out.

Nobody ever answered that question correctly and I used to joke that if anyone ever did we'd hire them immediately.

NB I've long since stopped using those kind of trivia questions in interviewing, but I didn't know any better at the time.

[StavrosK]

I'm sorry, my Java is rusty; is this the equivalent of the Python

    print("\n".join("%s: %s" % (key, value) for key, value in mydict.items()))

? If so, is it hard to do in Java?

[nitrogen]

In 1997, before for-each and generics, it would've been very verbose. I learned Java in 2006 and haven't written much in a while, so I maybe slightly off, but I think you'd either get an Iterator for the Hashtable's keys and repeatedly call Iterator.next() and Hashtable.get(), or get the length of Hashtable.keys() and use a traditional C-style for loop.

Okay, I couldn't resist looking up the old docs, so this looks about right (Enumeration instead of Iterator -- two interfaces that do basically the same thing):

  void printTable(Hashtable table)
  {
    Enumeration e = table.keys();
    while(e.hasMoreElements()) {
      String key = (String)e.nextElement();
      String value = (String)table.get(key);
      System.out.println(key + ": " + value);
    }
  }

[arethuza]

Yeah - that's pretty much it. Except that being lazy I'd have probably not bothered casting the keys and values to Strings and just called toString() on them directly....

[onemoreact]

Did you expect people to be able to do this by hand? I mean infront of an IDE I could do this in 5-10 minutes. But on a blackboard or pen and paper there is little chance I would get anywhere close to a correct answer.

[kragen]

I don't understand how that's possible. I mean, I'm going to assume that you're telling the truth, but I don't understand how it's possible for that knowledge to reside so entirely in your IDE rather than in your head. Do you mean you know that you would use an Enumeration, but not the names of the Enumeration and Hashtable methods that you would use? If you're trying to debug a piece of code and it's calling the wrong methods on an Enumeration or a Hashtable, how do you tell that they're the wrong methods? How does this work?

[arethuza]

This was the last question out of 15 or so that we used to give to people as part of an interview if they claimed they had done Java before - it was a written test. Some people had only done C or C++ before and had only had a quick look at Java and still did pretty well in it.

[StavrosK]

I see, thanks. It's more complicated than the Python version, which does the iteration implicitly, but I'm still surprised that nobody was able to do it.

[phillytom]

FYI - there's a potential defect there - keys are not required to be strings so you should lookup the value before you cast.

[free]

Ideally, whatever your key/value is would have the toString method over ridden to meaningfully represent it. Alternatively, I could write it as

for(Map.Entry<K, V> entry : map.entrySet()){

     System.out.println(entry.getKey());

     System.out.println(entry.getValue());

}

[nitrogen]

I was relying on the assumption from the original question that the keys and values were all Strings: "...a Hashtable containing String keys and values and printing them all out."

[SoftwareMaven]

Well, yours does iterate over the dictionary twice and generates a temporary list in the meantime. If you have a huge dictionary, this would explode. The equivalent Java code wouldn't do that (due to lack of list comprehensions).

[kragen]

At first glance, your statement is incorrect: there is no Python code to create a list here, and no list comprehensions. On further examination, though, string_join in stringobject.c invokes PySequence_Fast to convert its iterable argument into a sequence --- a temporary list, in this case --- so your statement that this code generates a temporary list is correct, although I suspect that this is more by accident than because you have a deep knowledge of the implementation of the Python standard library.

The temporary list of temporary strings probably will use less memory than the original dict did, though, so it's only a very mild sort of "explosion". It will, however, be several times bigger than the final output string, which also has to be huge if the dictionary is huge.

Python doesn't have anything like a StringBuffer. If it did, it would be reasonable for string_join to use it instead of generating a temporary list. The Python code above would look the same.

But hey, if you just want to print the values, you could say

    sys.stdout.printlines("%s: %s\n" % (k, v) for k, v in mydict.items())

but frankly I think I would write instead

    for k, v in mydict.items():
        print "%r: %r" % (k, v)

[nyellin]

Why doesn't StringIO count as a string buffer?

[kragen]

Sir or madam,

you may have an excellent point, there. But I haven't looked at how cStringIO is implemented: does it construct a list of strings and then join them when they are requested, thus keeping alive all the string objects passed to it? Or does it concatenate the bytes into a buffer?

I just realized that the Python 3 memoryview object also provides the wherewithal to construct a string buffer, even in pure Python.

[sur]

He is using parentheses instead of square brackets, so the code is actually using a generator expression which will produce each value lazily.

[eru]

Is mydict.items() also lazy?

[kragen]

In Python 3 yes, in Python 2 no. In Python 2 you'd say mydict.iteritems() if you were concerned about it.

[StavrosK]

Aside from the fact that I'm using a generator, where does it iterate twice? I don't see it.

[arethuza]

No, it's really not - even with the java.util.Hashtable class that was all that Java had at the time. I think it was something that people from a C,C++ background didn't really expect to be able to do.

[nopassrecover]

Iterating over a hashtable (at least in pseudocode if they didn't recall the API functions off-hand) hardly seems a trivia question...