So, keeping in mind that this is an interview question and not an actual real-life scenario, I believe the correct approach (and probably what the interviewer is looking for) is to ask a clarifying question, or to write "It can't be done" and move on. Here's why.
What the Interviewer Asks:
Write a function that is guaranteed to never return the same value twice. Assume that this function will be accessed by multiple machines concurrently.
What the Interviewer Needs:
Does this candidate effectively evaluate requirements and seek additional input when required?
When an engineer is handed a requirement (via a SOW or Specification or some other requirements document), some are self-evident, and others are totally unclear. This is a perfect example of the latter. As the previous answers have shown, there is no way to respond to this requirement without making several major assumptions either (a) as to the nature of the question or (b) as to the nature of the system, because the requirement cannot be met as-written (it is impossible).
Most of the answers make one attempt or another at solving the problem via a series of assumptions. One specifically recommends to just get it done quickly and let the customer worry about it if it's wrong.
This is really a bad approach. As a customer, if I give an unclear requirement, and the engineer goes off and builds me a solution that doesn't work, I am going to be upset that they went to work and spent my money without bothering to ask me first. That sort of cavalier decision-making demonstrates a lack of teamwork, inability to think critically, and poor judgement. It can lead to any manner of negative consequences, including loss-of-life in a safety critical system.
Why Ask the Question?
The point if this exercise is that it is expensive and time-consuming to build to ambiguous requirements. In the OP's case, you have been given an impossible task. Your first action should be to ask for clarification - what is it that is required? What degree of uniqueness is needed? What happens if a value is non-unique? The answer to these questions could be the difference between several weeks of time and a few minutes. In the real world, one of the biggest drivers of cost in complex systems (including many software systems) is unclear and poorly-understood requirements. This leads to expensive and time-consumig bugs, re-designs, customer and team frustration, and embarassing media coverage if the project is large enough.
What Happens When You Assume?
Given my background in the aerospace industry, and due to the highly visible nature of aerospace failures, I like to bring up examples from this domain to illustrate important points. Let's examine a pair of failed Mars missions - the Mars Climate Orbiter and Mars Polar Lander. Both missions failed due to software problems -- because engineers made invalid assumptions due, in part, to unclear and poorly-communicated requirements.
Mars Climate Orbiter - this case is typically cited as what happens when NASA tries to convert English to Metric units. However, that is an overly simplistic and poor representation of what really transpired. True, there was a conversion problem, but it was due to poorly-communicated requirements in the design phase and an improper verification/validation scheme. Furthermore, when two different engineers noticed the problem because it was obvious from flight trajectory data, they didn't raise the issue to the proper level because they assumed it was a transmission error. Would the mission ops team have been made aware of the issue, there was adequate time to correct it and save the mission. In this case, there was an impossible logical condition that was not recognized for what it was, leading to costly mission failure.
Mars Polar Lander - this case is a little less well-known, but possibly more embarassing due to its temporal proximity to the Mars Climate Orbiter failure. In this mission, the software controlled the thruster-assisted descent of the rocket into the Martian surface. At a point 40 meters above the surface, the legs of the lander deployed in preparation for landing. There was also a sensor on the legs that detected motion (to signal when they had impacted) to tell the software to shut off the engine. NASA's best guess as to what happened (because there are multiple possibile failures and incomplete data) is that random vibrations in the legs due to their deployment simultaneously and improperly triggered the shutdown mechanism 40m above the surface, resulting in the crash and destruction of the $110M spacecraft. This possibility was raised in development, but was never addressed. Ultimately, the software team made invalid assumptions about how this code needed to run (one such assumption is that a spurious signal would be too short-lived to be picked up, despite tests showing the contrary), and those assumptions were never questioned until after the fact.
Interviewing and evaluating people is a tricky business. There are several dimensions of a candidate that an interviewer may wish to explore, but one of the most important is an idividual's ability to think critically. For a variety of reasons, not the least of which is that critical thinking is poorly-defined, we have a very difficult time evaluating critical thinking skills.
As an engineering instructor, one of my favorite ways to evaluate a student's ability to think critically was to ask a somewhat ambiguous question. The sharper students would pick up on the question's faulty premise, note it, and either answer given the premise or decline to answer altogether. Typically, I would ask a question similar to the following:
You pick up a drawing from your stack of work. The drawing contains a variety of different callouts, but the most important points to a horizontal surface and says "Perfectly flat". The surface is 5" wide by 16" long, and the part is made of aluminum. How will you machine the part to create this feature?
(By the way, you would be shocked at how often such a poor specification appears in the workplace.)
I expect that students will recognize that it is not possible to create a perfect feature, and that they will state this in their answer. I typically would award a bonus point if they say they will go back to the designer and ask for clarification before making the part. If a student proceeds to tell me how they are going to achieve .001 planarity or some other made up value, I award zero points. This helps me make a point to my students that they need to be thinking of the bigger picture.
If I am interviewing an engineer (or similar profession), I am looking for someone who can think critically and question what has been placed in front of him. I want someone who asks the question "Does this make sense?" .
It does not make sense to ask for a perfectly flat part, because there is no such thing as perfect. It does not make sense to ask for a function that never returns a duplicate value, because it is impossible to make such a guarantee. In programming, we often hear the phrase "garbage in, garbage out." If you are handed garbage for requirements, it is your ethical responsibility to stop and ask whatever question helps you elicit the true intent. If I'm interviewing a candidate, and I give them an unclear requirement, I am going to expect clarification questions.