Immutable/persistent data structures are almost always some sort of tree, even if on the outside they look different. Knowing that all your operations that were constant (for the mutable case) are now logarithmic (for the immutable case) is a must.
Modern HAMTs are faster than your run of the mill hash table, the "constant" vs. "logarithmic" is misleading here.
The HAMT will be log32 or log16 N and will have runs of values that play very nicely with the caching behavior of the processor if you find yourself traversing more than one value.
I've made plenty of hiring decisions over the course of my career.
It depends on your field. Understanding arrays and hashes covers a lot of ground, especially in web development. I like it when candidates mention binary trees (in their many variations), graph theory, linked lists, Huet zippered lists/trees, and all sorts of other structures/algorithms. That said, array and hash are the big ones, the rest are for bonus points.
More than that, I like to see developers demonstrate a grasp of higher order functions. If you write a for-loop in JavaScript then you'll lose points. Write one in Ruby and I'll show you the door. Understanding the common higher order functions (map, reduce, filter, group_by, etc.) is a big plus.
This will differ by field. If I'm looking for a C developer then I expect a damn-solid understanding of not only how these data structures can be used, but how to implement them, their performance characteristics, and why one should be chosen over the other. That's mostly because implementing circular linked lists is something you'll likely have to do in a C app, but is almost never necessary in JavaScript, Ruby, Python, etc.
More than anything, I just want to see how you think things through.
Did you solve the problem elegantly? White-boarding is going to result in somewhat messy code, but that's no excuse for using global variables or creating giant deeply-nested if statements.
Did you solve the problem in a reasonable amount of time? Even if you've got a great idea, I want to see you solve a simple problem quickly. Taking 45 to create the most beautiful version of fizz-buzz known to humankind makes me worry that you'll agonize too much when trying to write real code.
How did you handle pressure? Most good interview problems have a twist; a spot where everyone misses a detail that causes a bug. How did you react when I pointed out the bug? Did you get flustered and fail to figure out what was wrong, or did you quickly spot the error and correct it?
Ultimately I want to know that I can depend on you. I want you to know how to quickly build stuff that works, because we've got a lot of work to do. I want to see that you can creatively solve problems, because I'm going to depend on your input when I run into a difficult problem. I'd also like it if I could imagine working next to you on a daily basis. If you come across as antagonistic or egotistical then I'm probably not going to want to work with you.
Many of Ruby's standard higher order functions came from Smalltalk, such as collect, detect, inject, select, and so on. I expect to see fewer for-loops than in JavaScript, but I'd be more forgiving than with Ruby due to having less familiarity with the language.
For-loops and if-statements have their place, but too many of them (especially after a couple levels of nesting) makes code hard to read. Different languages have their own answers for this. In Ruby you'd use polymorphism and higher order functions, while C++ would use polymorphism and iterators.
Mind you, all of this is based on your self-professed experience with a language. If you tell me you're an expert in Ruby and proceed to write for-loops all over the place then I'll be severely unimpressed. If you tell me you're mostly a Java developer, but you're going to do the interview questions in Ruby because it's easier to whiteboard with (and more applicable to the work you'd be doing at my company) then I'd be a lot more forgiving.
Come to think of it, I think this may explain the perception that older developers have a hard time finding work. I get very excited when I see 20+ years of experience on someone's résumé. I assume they're going to know all sorts of programming paradigms, algorithms, data structures, languages, techniques, and so on. The problem is that the human brain discards information if it goes unused for too long. As a result, a lot of older devs have a fantastic grasp of the fundamentals because they use them every day, a solid understanding of the one or two languages they use now, and a hazy remembering of a bunch of things they used 5+ years ago. In other words, they're a lot like a developer with 5-10 years of experience, except they're marginally more well-rounded and have better war stories. That would normally be someone I'd really want to hire, but it falls so far short of the unrealistic demigods I'd imagined them to be.
Sorry, that was a trick question: in Smalltalk, the for-loop is just a block/higher order function applied to a collection, except that the collection is an Interval defined by its start, end and optional step that only generates its contents on-demand, for example when iterating:
(1 to: 10) do: [ :i | ... ].
So (1 to: 10) creates an Interval, and then `do:` iterates that Interval. There's a shortcut convenience `to:do:` in Number that allows you to avoid the brackets.
The point being that the dichotomy "for-loop vs. higher order functions" is a false one. And usefully so, for example you can adjust methods in Interval to iterate in parallel (or you use a different kind of Interval) without having to touch the language or most iteration code.
