Check their ability to reason about problems, by posing them kinds of problems they're unlikely to have solved in the past. Net of knowledge and experience, this probes a person's reasoning abilities (knowledge in the field, or experience at problem-solving, enhance such abilities, but we've posited that they're equal in those -- and if they weren't the correlation might still be a positive, esp. wrt problem-solving experience).
You can do it at very high architectural levels -- "We'd like to design a software system to let people play 'Boggles' ((many other games are also suitable! Just pick ones that you can describe briefly)) -- what functionality would we like in various components?" See if they separate user interfaces from underlying engines, allow for human-human as well as human-computer play, consider multi-user local and remove possibilities, think of optional helpers that might make the game more enjoyable without spoiling its main point [[such as timed play, challenging other players' moves, a computer arbiter to solve a challenge by checking in a large dictionary whether a sequence is indeed a valid word, and so forth]], consider the possibility of interfaces for people with disabilities, and so forth. Such open-ended, very high-level architecture problems tell you a lot about how people go about solving vague problems (are they making a lot of assumptions, or rather generating ideas and checking them with you, for example).
At the other extreme, you can do it at extremely detailed levels -- "In a factory, we keep getting large batches (a few hundreds at a time) of brass rings that are one component in a machinery the factory builds. All rings in the batch are supposed to be exactly the same weight, but unfortunately that's generally not the case -- a typical batch will have N rings all of one weight and M others that are all of a different weight. It's important to the machinery we're building that the three brass rings used in each machine are exactly the same weight as each other, so we need to sort the N+M rings in an incoming batch into the N and M groups. The brass-ring-inspection robot has a set of scales which can only tell it whether the set of rings on the left plate is heavier, lighter, or equal to the set on the right plate. Each weighing takes a fixed amount of time and we want to do our sorting ASAP. Please consider what algorithm the robot should be using to minimize the number of weighings it needs."
This kind of low-level algorithmic problem tells you a lot about a person's facility for algorithmic thinking (assuming they do have "high school algebra" enough to be fully comfortable with manipulating symbolic expressions). There are many other problems of this kind, and some can be expressed more briefly (you might consider having a printed sheet with the problem statement to ensure you avoid ambiguity &c). In some of these problems it's actually fruitful to be slightly ambiguous in the problem expression, again to distinguish candidates who just make assumptions (worst of all, those who make assumptions without even realizing they do so;-) from those who will ask for clarification of the ambiguities (which means they've spotted the ambiguity and have the right attitude -- that it's much better to take a little time but solve the true problem, rather than rapidly solve a problem that's not actually the one you need to solve!-)