Shutterfly Interview Question for Software Engineer / Developers


Country: United States




Comment hidden because of low score. Click to expand.
3
of 3 vote

On a classical computer, it's impossible to write code to generate truly random numbers without access to a physical device that can do it, such as a quantum device or other physical source of randomness. This is because classical computers are deterministic: the future state of a machine is entirely determined by its current state.

For this reason, classical computers use PRNGs (pseudo-random number generators). These use some complicated arithmetic to deterministically generate sequences of numbers that appear random. Often, the next "random" number is generated by applying some function to the previous "random" number, with the first random number being taken from the system time or something like that. To someone who doesn't know the pattern and doesn't time the launch of the program to the nanosecond, the numbers appear random and usually behave as if they were random. To understand this concept, search Wikipedia for "Middle Square Method", a very simple method for generating random numbers (that is quite flawed -- I only recommend it for understanding the concept of pseudo-random generation, not for actually implementing PRNGs). If you want serious methods for pseudo-random number generation, look up "linear congruential generator", "Mersenne Twister", and "Blum Blum Shub" (these are just examples; there are many more). Out of the three I named, all but the linear congruential generator are nontrivial to understand mathematically.

As for true randomness, it's actually not even known for certain whether true randomness even exists. We believe certain events, such as quantum mechanical observations, to be truly random, but as we do not fully understand quantum mechanics, we can't say for certain. Processes like dice rolls are not really random, but may be indistinguishable from randomness because tiny, unobservable changes in the initial state of the system translate into huge differences in outcomes. There is a whole field of physics / mathematics / mathematical physics called Chaos Theory that studies such sensitivity to initial values. Chaos Theory sounds really cool and actually is. It also has sister topics called great names like Bifurcation Theory and Catastrophe Theory.

In any event, you can't give an algorithm to produce truly random bits. What you can try to do is access some external source of data that is in no way related to your program and that will thus hopefully appear random. If you access a quantum pool it might be truly random. Otherwise, you could use time between packet delays on your local network, mapped in some way to a specific range, as random numbers. If your computer has wireless, you might be able to use delays between various signals you pick up from surrounding networks. You might be able to use thermal noise. Or noise in radio signals. There are many possible ideas here, but an important thing to keep in mind is that many environmental factors can be manipulated by an attacker, so one should be careful when using data from the environment as a source of randomness in applications whose security depends on the random numbers being unpredictable.

Finally, you could always return digits of pi. Though obviously not truly random (since they can be calculated by a formula), as far as I know, they pass every typical statistical test for randomness.

- eugene.yarovoi August 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

+1

- dc360 August 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

randomness can be predicted while pseudo random nos can be predicted... follow pari library of math for more details and functions

- karuna nidhan August 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is kind of a bad explanation.

You mean randomness *cannot* be predicted?

And there are no functions for true randomness.

- Anonymous August 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Random numbers are simply numbers which doesn't obey any reason.
Its basically like, at an instant a number comes to your mind for no reason.

Pseudo random numbers, are numbers generated using algorithm with high degree of randomness. Since machine can't simply come up with any number, the cases where we need random numbers for computers, we use random number generator algorithms, and the number they generate are called pseudo random number.

hope this helps

- Varun August 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The long post sums things up very nicely.

The existence of randomness is an undecided (and possibly undecidable) philosophical question. Assuming tiny particles do indeed behave randomly, we can do measurements on them to create "true" random generators.
Binary-logic based computers (the ones we have now) are entirely non-random. The way we generate pseudo-random numbers on them is by divisibility tricks. (Or other tricks, for that matter. Such as looking at the clock with high precision.) Namely, if you find some large prime, you can easily iterate over all numbers smaller than it in a manner that looks random, but isn't.

- mathytime September 25, 2014 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More