Assuming that a company does not look for candidates who are naturally good at ICPC-type of questions or geniuses who can come up with amazing algorithms in a matter of minutes, there is actually a different way to do coding interview: just give a high-level description of a sophisticated enough algorithm to a candidate and ask the candidate to turn that into code. I think it strikes a good balance between depth in CS and the coding abilities. This type of interview is similar to what engineers do at work too. We rarely invent new algorithms, but we do read white papers or blog entries or books to pick an algorithm to implement.
There are many variations in questions too: search a tree or graph with some customized criteria, using a double buffer to implement a tree-style prefix scan, implementing an integer multiplication with unlimited digits, some streaming algorithm, tree-walking to transform one tree to another, a simplified skip list, the options are unlimited. A good candidate tends to grasp the high-level concepts quickly (and they can ask questions), and is quick to convert intuition into working code. I find that there is a strong positive correlation between the performance in work and the performance in such coding interviews.
There are many variations in questions too: search a tree or graph with some customized criteria, using a double buffer to implement a tree-style prefix scan, implementing an integer multiplication with unlimited digits, some streaming algorithm, tree-walking to transform one tree to another, a simplified skip list, the options are unlimited. A good candidate tends to grasp the high-level concepts quickly (and they can ask questions), and is quick to convert intuition into working code. I find that there is a strong positive correlation between the performance in work and the performance in such coding interviews.