23

This is a question I was asked at a job interview, and I can't figure out the answer they were looking for, so I'm hoping someone here might have some ideas. The goal is to write a function that is guaranteed to never return the same value twice. Assume that this function will be accessed by multiple machines concurrently.

My idea was to assign each machine a unique id and pass that value into the unique value generator function:

var i = 0;
function uniq(process_id, machine_id) {
   return (i += 1).toString() + machine_id + "-" + process_id;
}

This would avoid the fallout from race conditions since even if two or more processes read the same value for i, each return value is tagged a unique combination of process id and machine id. However, my interviewer didn't like this answer because bringing another machine online involves assigning it an id.

So can anybody think of another way to solve this that doesn't involve configuring each machine to have a unique id? I'd like to have an answer in case this question comes up again. Thanks.

  • 31
    Guaranteed in the strict sense of the word? I mean, even Guids will at some point start to repeat themselves. We may not live anymore, but guarantees .. And by the way, a process ID is far from being unique. – JensG Nov 23 '14 at 22:30
  • 7
    @CodesInChaos - That is a fairly terrible assumption, given that it is trivial in some operating systems to change your mac address. – Telastyn Nov 24 '14 at 2:04
  • 7
    "Assume that this function will be accessed by multiple machines concurrently" - honestly, this could either mean "the code runs on each machine indivually, with no communication between the machines", or "there is a central machine / central database where the function is provided for the other machines, available over the network". You should start clarifying this first. – Doc Brown Nov 24 '14 at 6:32
  • 28
    Was it a trick question? For example, a function containing an infinite loop will never return the same value twice.. – Brendan Nov 24 '14 at 11:54
  • 8
    Perhaps they were looking for a programmer who asks questions about dubious requirements, rather than making assumptions and running with it :) – theMayer Nov 24 '14 at 14:32
60

Don't get fancy, just toss a simple (threadsafe) counter behind some communication endpoint (WCF, web service, whatever):

   long x = long.MinValue;
   public long ID(){
       return Interlocked.Increment(ref x);
   }

Yes, it will eventually overflow. Yes, it doesn't handle reboots. Yes, it's not random. Yes, someone could run this on multiple servers.

This is the simplest thing that satisfies practical requirements. Then let them be the ones that follow up with those problems (to make sure they understand the limitations, do they really think you need more than 2^64 ids), so you can then ask about what trade-offs are okay. Does it need to survive reboots? What about hard drive failure? What about nuclear war? Does it need to be random? How random?

  • 7
    This is a good answer, because interviewer never ask questions to get a straight answer. They want you to give an answer where you can justify your decisions. If you understand the domain, nearly any answer will be suitable if you can justify it. – user69037 Nov 24 '14 at 5:31
  • 7
    How is this supposed to work if the code runs on different machines (so obviously in different processes)? Each process will have a different copy of x. And I think without an explanation about the kind of interlocking mechanism you have in mind, this answer is pretty vague. – Doc Brown Nov 24 '14 at 6:39
  • 7
    @DocBrown "accessed by multiple Machines concurrecntly" seems to imply that multiple machines access a single function on a single server. Otherwise it should be worded "Multiple machines will run a copy of this function at the same time" – Falco Nov 24 '14 at 10:43
  • 3
    @LightnessRacesinOrbit: I guess this is meant to be C#, and the System.Threading.Interlocked class, which provides atomic increments. But you could this also read as some kind of pseudo code. – Doc Brown Nov 24 '14 at 12:07
  • 3
    If I were the person asking I would be very unhappy with this proposal. Starting implementing something without even knowing what the requirements are is a big red flag. I would expect you to ask. – JensG Nov 24 '14 at 12:51
25

If I were asked that question, and they made it clear that it has to be unique across reboots and across different machines, I'd give them a function that calls into the standard mechanism for creating a new GUID, whatever that happens to be in the language being used.

  • The problem with v4 GUIDs is that they're only very likely unique, not guaranteed unique. Not a big issue in practice, but not satisfy the requirements if the interviewer takes them literally. – CodesInChaos Nov 23 '14 at 22:37
  • In particular, if the standard GUID mechanism doesn't meet the interviewer's requirements, then tease out the differences in requirements between the interviewer and an ordinary user of GUIDs. A sensible interviewer asking this kind of question ("how do you do <some generally-known standard thing perhaps with a slight variation from the usual requirements>") should expect very different kinds of answer from candidates who know about the state of the art for GUIDs and candidates who are inventing something from scratch. – Steve Jessop Nov 24 '14 at 11:04
  • This is probably the simplest answer, assuming flexible requirements. – theMayer Nov 24 '14 at 16:11
  • 9
    +1 because this is basically the problem that guids solve. Producing a duplicate Guid, no matter its format, is the most difficult lottery on the planet. Apparently many people don't have a sense for the exponential unlikeliness of collisions. – usr Nov 24 '14 at 16:49
  • 3
    Oh, and if you offer the "use a standard function" answer to any such question, expect a follow-up question "and how is the standard function implemented?". To which you might very well answer "I don't know, but I'd definitely look it up rather than trying to invent something", which is a completely accurate answer that completely fails to maintain the expected suspension of disbelief in interview conditions, that you'd ever do anything important without researching it first ;-) – Steve Jessop Nov 24 '14 at 18:36
22

The interviewer said the method will be called concurrently, not in parallel; just return the date/time down to as many decimal places as you can.

Why is everyone over-thinking this? You'll be dead a long time before any finiteness is expended and you don't have a chance of a collision.

If you're worried about it returning the same time, add a delay for the smallest amount of measurable time.

If you're worried about setting a clock back for daylight savings time (experiencing 1 time twice), add a constant to the time the second time you experience it.

  • 12
    Or just return UTC time regardless of the requestors timezone. As UTC is not localised then it wont be affected by DST changes. – Mauro Nov 24 '14 at 8:40
  • 1
    System.currentTimeNanos() :-) – Falco Nov 24 '14 at 10:44
  • 1
    Unless you're returning the date & time in a human-readable format, your value shouldn't have any timezone information inside of it anyway. – Lightness Races with Monica Nov 24 '14 at 12:01
  • 12
    The smallest amount of time is still going to produce collisions if called frequently/concurrently enough. It will also produce collisions due to clock synchronization drift, malicious clock manipulation, and if you're not careful - daylight savings. – Telastyn Nov 24 '14 at 12:19
  • 1
    Very creative, at least. Relying on a clock that is going to be adjusted every now and then is still not such a great idea, IMHO. The offset will not save you from collisions. – JensG Nov 24 '14 at 12:56
15

Firstly, you will want to ask the interviewer two questions.


Question 1.

whether the interviewer expects one or more "central machines" to be used to assign some unique numbers, or blocks of unique numbers.


Question 2.

Whether the interviewer expects a mechanism for collision detection, or instead accept the calculated risk of a minuscule chance of collision without explicitly detecting them.

There is also the defense-in-depth approach, in which one incorporates some part of user-ID into the randomness (thus, not entirely random). The chance that the same user encounters a collision within the content created by that same user is therefore lowered.


There is an implicit question 3, ...

But it is one you'll have to gauge yourself without asking, because it is extremely impolite to ask your interviewer.

Whether the interviewer assumes the knowledge of probability, risk, and some simple techniques employed in cryptographic and information-security systems.

The first kind of knowledge ensures you're not trying to convince a non-scientific person into accepting a scientific concept they won't accept.

The second kind of knowledge ensures that you addresses concerns which are in addition to mere probability. In other words, how to defend against "assailants" who want to intentionally break your randomization scheme, by manipulating the machine(s) or their virtual hosts to force two machines to generate the same value.


Why ask.

The reason is that if the interviewer expects it one way or another, trying to answer with the opposite approach will never make the interviewer happy.

The deeper reason is that some people do not like the idea of say, a 1.0e-20 chance of failing. (I'll try not to stir up philosophical or religious arguments here.)


First of all the "namespace" of random numbers are made into a hierarchy, with certain number of bits allocated to one source of randomization, and the other number of bits allocated to some other ways, etc.

The centralized approach relies on some central authority to uniquely assign the first level of bits. Then, the other machines can fill the rest of the bits.

There are several decentralized approaches:

  • Just generate random numbers as good as one could, and accept the practically-zero chance of failing justified by calculations.
  • Use cryptographic means of generating random values from deterministic source, say, an incrementing values.
  • I think this is the best answer. The others are solutions without requirements. – Jack Aidley Nov 24 '14 at 15:42
  • Remarking on your third question - it seems that competence is a safe assumption, or at least an irrelevant one. If a company didn't provide a competent interviewer, there will likely be larger flaws to the selection process. If they did, then he/she will appreciate the questions. – theMayer Nov 24 '14 at 16:09
  • 1
    Why couldn't "question 3" be addressed by asking something along the lines of, "Do we need truly guaranteed uniqueness or just a very, very low probability of collisions?" and, "How secure does this need to be? Do we need to assume an attacker will be trying to break the mechanism? What kinds of attacks are we concerned about?" Answers to those questions should clarify whether the asker understands these issues and what they expect. – jpmc26 Nov 24 '14 at 23:19
12

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?

Never Assume.

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.

Additional Considerations

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.

Bottom Line

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.

5

Guaranteeing uniqueness is difficult because computers do not have infinitely-large variables. No real-world Turing machine can.

The way I see it there are two problems here, and both have well-established solutions.

  • Concurrency. Multiple machines may need a value at the same time. Thankfully, modern CPUs have concurrency built-in and some languages provide developer-friendly facilities to take advantage of this.
  • Uniqueness. While impossible to guarantee uniqueness, we can have arbitrarily-large variables which can hold values so large that a real-world system would have a very difficult time exhausting all of the unique values

Here is my solution in Java:

public class Foo {
  private static BigInteger value = BigInteger.ZERO;
  private static final Lock lock = new ReentrantLock();

  public static BigInteger nextValue() {
    try {
      lock.lock();
      value = value.add(BigInteger.ONE);
      return value;
    }
    finally {
      lock.unlock();
    }
  }
}

BigInteger is an arbitrary-size integer type. It can grow to hold values that are quite large, even if not infinite. The lock ensures concurrency, so the same value cannot be returned twice by two simultaneous requests serviced by separate threads.

  • I think the assumption that the code will only be used for less than five hundred years is a valid assumption. If you simply return increasing values in 64bit storage, you're fine for quite a while. At 1 call per us, in 584555 years. – Mooing Duck Nov 24 '14 at 23:05
  • 1
    At least in Java, that is 2^63 values (so half that long). Still longer than the human race will likely exist given our tendency to kill each other. Regardless, I took a more theoretical approach. Realistically, 64 (or 63) bits should be enough. – user22815 Nov 24 '14 at 23:08
  • 1
    @Snowman: WHAT?!? Your solution is only valid for 250K years?!?!? NEXT CANDIDATE!!!!!! :-) – Bob Jarvis - Reinstate Monica Nov 25 '14 at 2:55
0

I would expose the function via a port on the server; to call the function, the requesting machine requests a connection and is granted one, while at the same time being allocated an identifying code (sequential number for simplicity). Whenever a message is sent to the port requesting the unique value, the value is generated by concatenating the MD5 hash of the current date and time with the MD5 hash of the identifying code.

If they want a more bulletproof solution they would have to specify their actual requirements rather than being all vague about things.

-1
string uniq(string machine_id) 
{
   static long u = long.MinValue;
   Interlocked.Increment(ref u);

   //Time stamp with millisecond precison
   string timestamp = DateTime.UtcNow.ToString("yyyy-MM-dd HH:mm:ss.fff",
                                            CultureInfo.InvariantCulture);

   return machine_id + "-" + timestamp + "-" + u;
}

In the above way we can make sure that return value is different even if there are restart or even if called simultaneous from different machines.

  • Programmers is about conceptual questions and answers are expected to explain things. Throwing code dumps instead of explanation is like copying code from IDE to whiteboard: it may look familiar and even sometimes be understandable, but it feels weird... just weird. Whiteboard doesn't have compiler – gnat Nov 29 '14 at 11:29
  • Thanks gnat for pointing it out, will take care to explain the solution from next time – techExplorer Dec 9 '14 at 6:10

Not the answer you're looking for? Browse other questions tagged or ask your own question.