For the most part, I avoid the data structures-style questions. We have a limited time as interviewers and while these show off a candidates knowledge in areas we may need very rarely, I'd rather have someone who is productive at using what the framework we write code in provides. I stick with "when is it appropriate to use 'X' vs 'Y'" style questions but usually don't have to ask them; the candidate reveals that knowledge (or lack thereof) through other questions and I hate whiteboard interviews. I don't penalize the candidate for lacking knowledge they're never going to use on the job, but I like to know what areas they have deep understanding of. Before I ask these questions, I'm careful to point out "I don't care if you know the answer to this or not -- you might encounter that once in 10 years, here -- but if we do encounter it, it's helpful to know if you have a deeper understanding than others on the team." For the most part, though, it's a waste of time and I'd rather spend that time on the next two points.
My preference is to ask the candidate (very carefully) to provide a link to anything they've written that they can legally[0] share openly. My explanation includes all of the following: I am not interested in judging them on the code they send me -- in fact, I want their worst. I want the code that they don't care about, that they wrote in a hurry to solve some random problem that they had and that "just needed to work and do that one thing". I'll use that code as a starting point to discuss refactoring -- i.e. "What if you wanted to take this code and make it worthy of a product you'd sell". If there's absolutely nothing that they are comfortable[1] sharing, I ask them to take a few minutes and find a project in the framework we're interviewing for on GitHub that we can use for that purpose.
As for the "give them the actual work", we have a single-sheet project we give to every candidate, Junior, Mid or Senior. It's a "to do" app with basic requirements: Must use a database of some kind for storing/retrieving data (Sqlite is called out as an option, but anything relational is allowed), it must allow adding, marking complete, unmarking complete and deleting. We additional coach Senior/Mid developers to include things that would be important for a completely released application with examples (none of which are required), such as documentation, instructions for starting/setting it up, installers (with advice not to take this too far as that's one hell of a rabbit hole). Depending on the outcome of the "actual work", we might follow-up in a similar manner to ask them questions about their choices.
I've seen everything from a To Do app that used SignalR to perform its operations, allowing multiple users to watch the check-list get updated in real-time (complete with a WiX installer, OWIN hosted web service running as a Windows Service with everything wired up and a doc generation project[2]) to a simple HTML-template based solution that is done in four files. Of course, we check the usual sources for obvious evidence of whole-sale copying, but we're not terribly strict here, either (this point is made on the spec sheet -- it's such a simple app, it shouldn't require a lot of research/copy-pasta to build).
[0] The first time I did this, I left off that "legally" part and the candidate shared code that -- while not representing anything their employer would care about (basic library code that probably every programmer as written from time to time) and certainly not representing anything the company I worked for was interested in "stealing", it carried a copyright that they did not own. Unfortunately, it disqualified the candidate (not my choice in this case, but the company I was working for at the time had concerns that the employee might introduce liability we didn't want). And I don't want any candidate to think I'm asking them to break their contractual obligations in order to get a job -- we operate ethically and don't want to imply otherwise.
[1] I'm always careful to say "comfortable" so as to allow them to not have to feel bad about not having any code written "outside of work". I have met many software developers (albiet often in the Junior/mid-level skill levels) who simply don't care to write software outside of work. At the senior level, I've met several software developers who haven't written anything publicly shared in a while -- they're working too much at their current job, have families, and might not have the time to devote to things outside of that. Interviewing sucks and anything I can do to disarm the person and get them talking/excited will help me to evaluate them better.
[2] The dude really wanted the job. OK, I lied, the dude was me, but it was rare that I wouldn't include these things in an app I was writing for my current employer, so those parts were automatic (and easy at that point) for me -- it felt wrong not to include them. I used the documentation to explain my choices, mostly, which avoided a second technical interview.