Tag Info

Hot answers tagged

57

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. ...


32

In days of old, scientists would publish anagrams of their work to be able to say "I thought of this idea." (look at the 'history' and 'establishment of priority' sections) The thing is, they wanted to be able to take credit for it, but also give other scientists to publish their results if they had other ideas without building on the original idea. For ...


29

You can do that quite easy. If you have a plaintext text, secret key S and public key P you do S(text) and get the cipher. Now you can publish cipher and P but not S. Therefore, everyone can decrypt the cipher with P by doing P(cipher). If you now want to prove, that you are the one who created the cipher (and therefore the original text), you can either ...


23

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.


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 ...


18

It's possible to hash the data you wish to timestamp and turn it into a Bitcoin address. This is known as trusted timestamping. By making a small payment (a satoshi, or 0.00000001 BTC) to it, the payment is stored on the blockchain along with the address you paid to. Since only the hash is stored on the Bitcoin blockchain, no one can tell what data you ...


14

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 ...


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 ...


10

Lets say you have n items and know you want to mark m items, m<=n (according to the % value). Now you mark the items one-by-one, starting with a random probability of m/n for marking the first item. But instead of keeping that probability fixed, after each step you adapt the actual probability to what is needed now! So when after k steps you have marked ...


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 ...


5

You are trying to solve an optimization problem. Realizing this is important for two reasons: You do not necessarily have to find the absolutely best solution (that would take too long to calculate), but you can settle for a good-enough solution. You can fine-tune your algorithm later. You have to very precisely state what you're optimizing for. I assume ...


4

Yes, constant factors matter very much in practice. Big-O notation is only the first step(albeit highly useful) in measuring the performance of an algorithm/program. An algorithm that takes only n^2 steps is certainly preferable to one that takes 2*n^2 steps, all things else being equal.


4

Your code needs to be released under the GPLv3 as you believe it is a derivative work of the algs4.jar implementation. Other projects utilizing your code will likely need to be released as GPLv3. Most larger applications just incorporate code from smaller projects, and treat the smaller code base as part of the larger. That will trigger the "viral" aspect ...


4

In order to attach your own license to code, you must own the copyright. Generally speaking, that means that it must be code that you have written. As an example, there are libraries out there already that provide some capability I want in my program. I have two choices: I can either live with the license that the library provides, or I can write my own ...


4

Believe it or not, this problem is solvable in time O(n). First, let m be the median of the array. For a pair (x, y) that are next to each other, define the contribution of x from that pair to be: def contribution (x, y, m): if m < x: if x < y: return 0 elif y < m: return x - m else: ...


4

It seems to me that your problem is in your first sentence: Our company implemented a calendar system a few months back with recurring appointments, using iCal strings to store the recurring appointment criteria. Having to scan all records to determine date ranges is simply not scalable. In essence, you're using your database as a flat file, so of ...


3

An int represents a fixed number of bits (usually 32 or 64). This is a measure of information content; it is fundamentally impossible to store more than this number of yes/no decisions in it. With three-way decisions the arithmetic becomes slightly more involved because they represent fractional numbers of bits (two three-way questions contain slightly more ...


3

There is an O(N) solution to this problem based on Knuth-Morris-Pratt string matching algorithm. A few observations first. Every string S has a trivial automorphism, S(0) (if S(i) is the ith cyclic shift as defined above.) If a string S of length N has a non-trivial automorphism, then S must be of form S = sssss...s, i.e., a smaller string s repeated some ...


2

The body of loop you've written is entered n+1 times (i from 0 to n), after that the variable i is incremented again, it's value now becomes n+1. Then it is compared to n ( i <= n ), this test fails and the body of the loop is skipped.


2

There is, and in fact there are programs in real life that solve the halting problem for other problems all the time. They are part of the operating system you are running your computer on. Undecidability is a weird claim that only says that there isn't such a program that works for ALL other programs. One person correctly stated that the halting proof ...


2

Minimum occupancies of greater than 50% don't work, because when you need to split a node because the node is too full, it would be impossible to cut a node such that the two resulting nodes were greater than 50% full. (You could do 60/40 or something like that but the smaller node would always fail the data structure's invariant of each node being greater ...


2

A minimum occupancy of 1 isn't possible with a B+ tree as each node has to have one entry from the parent node. Occupancies of less than 50% means that the tree can be made more efficient by redistributing entries between nodes and if two nodes have less than 50% occupancy, they get merged into one node. Or as Billy ONeal points out, the tree grows by ...


2

While it would result is much more code, there's nothing inherently wrong with adding "nextLeft, nextDown, etc." to your keys. You'll be able to 100% ensure which key is next when navigating, so all of the guess work is gone. If you insist on a solution that uses solving, give each key an x offset and width, then when down is pressed, move to the key whose ...


2

It's possible that heuristics exist which improve your success rate, and if they exist, it's possible that you can program something that will find them. But for a game this small you're almost certainly better off programming a complete search and looking at the solutions that pop up. Then, when you compare what works and what doesn't, your human brain ...


2

For date of birth and people in general, one will need to validate if that person exists and if thier address is valid. You can do both of these using 3rd party services that will: Validate if the person is a real person Validate and standardize address information You can do this yourself using algorithms that you have mentioned, but why re-invent the ...


1

My thought is to set the duplicate numbers to negative and then count only the positives It sounds like you're using negatives as an "isDuplicate" flag. This is a great example of the difference between competitive programming and professional programming. In a competitive environment, you're trying to optimize the time it takes to write the program. ...


1

We're currently building a web service to solve problems like this (with very complex rules, including negative rules - things not happening). Unfortunately it's in private beta right now and we're capped on users. However, hopefully I can share the details on how to build a much simpler version (minus negation). As you outlined as your data grows it will ...


1

In the end the runtime [seconds] of the implementation of an algorithm is the deciding factor but the coefficients and the big-O notation help you in inventing efficient algorithms. The big-O notation tells you how the algorithm behaves if the number of inputs/.. n changes dramatically (orders of magnitude). You mostly use it in a relative sense, i.e. ...


1

Here is a simple improvement which will most probably meet your time constraints. For every divisor i of N, there is also a corresponding divisisor N/i. And to find all pairs of divisors, you need only to loop from 1 to the square root N. So try something along the lines of int maxD = (int)Math.sqrt(input); int sum=1; for(int i = 2; i <= ...


1

A much more efficient way would be to factorize the number into prime factors (using existing libraries, although I do not know one by heart). Say the factorization is a HashMap<Integer,Integer> factorization where each prime factor is mapped to its multiplicity, then one can compute your sum as follows. int N = 84684684; //your integer ...



Only top voted, non community-wiki answers of a minimum length are eligible