The Programming Riddles Thread!

[Borealis7]

as long as we are using your imaginary computer...

of course we are using an imaginary computer, because this is an academic question, not a practical-real-world application of it. if you like you could benchmark my solution against a functoin that goes over an array and sets each index to the value, i'm still pretty sure my solution will work faster.

 

[slugg]

i can also sort a set of numbers less than O(nLog n) complexity the riddle will shortly follow.

Spoiler

Radix sort algorithm. In other words, lexicographical sort by grouping by the digits or characters in succession. This is done in O(KN), for N elements of length K. This is *sometimes* faster than O(n log n).

 

[bobross419]

I feel so dumb for asking this, but can someone explain what the heck O, K, and N mean? I'm pretty sure I N is some number of things, but a google search for O isn't going to help me much

 

[slugg]

hi guys, i'm back from the weekend and here to answer your questions.

slugg: yes, but not as you say it: i want a constructor of an array-like data structure to initialize to a value K (yes K can be any type, even Object).

QuickInitArray QIA = new QuickInitArray(K);
this operation shuold be done in O(1) complexity assuming creating a new TypeK[] is O(1) as well. that's all there is to it.
once the constructor finishes, then yes, "for all 0 <= i < N, MyStructure.get(i) == K".

Your original riddle said it needed to be initialized to size N during construction. There's no way this constructor can do that; it doesn't specify a size to initialize the structure to. Also, see the memory allocation/initialization debate everyone else has already mentioned.

 

[slugg]

I feel so dumb for asking this, but can someone explain what the heck O, K, and N mean? I'm pretty sure I N is some number of things, but a google search for O isn't going to help me much

O(blah blah) is the "in the order of blah blah." What this means is the theoretical upper bound of the complexity of the algorithm, ignoring constants. It's a description for the worst-case performance for very large sets on a given algorithm. There are other bounds, too, such as a lower bound (shown with an Omega symbol), and tight bound (shown with a Theta). This should not be confused with the actual running time of the algorithm, which does take into account constants.

N is usually the variable we use to represent the number of elements in the set. We also assume it's very large. In other words, when analyzing the performance of an algorithm, we only care about end behavior, not any specific size.

Sometimes, there's another factor involved for describing complexity. In the case of radix sort, we use K as the max number of characters in a string in our data set. In the case of some kind of graph algorithm, M is a common variable for graph edges. Most common algorithms, though, operate on lists/arrays, so you typically only see N.

Wiki: http://en.wikipedia.org/wiki/Analysis_of_algorithms

 

[bobross419]

Thanks, slugg.

 

[IHateMyJob2004]

11 years of software now. Barely remember big O notation anymore.

 

[dwell]

I feel so dumb for asking this, but can someone explain what the heck O, K, and N mean? I'm pretty sure I N is some number of things, but a google search for O isn't going to help me much

http://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

11 years of software now. Barely remember big O notation anymore.

Any developer worth their salt should at the very least know if the DSAs they are using are O(1) or O(N) or something else.

 

[iCyborg]

allocating some bytes of memory (which are zeroes already) and looking at them from the boolean perspective (which is primitive and thus zero equals 'false') is wrong? oh you 'unmanaged' boys...

The part that is wrong is "which are zeroes already". No, they are not zeros already, someone has to zero them, and that someone can't do it in O(1). Nothing to do with managed/unmanaged: in C++ you need to do it yourself, in some languages, semantics requires that the compiler do that automatically as a convenience. You can't just turn a blind eye to how the compiler does that.
Otherwise you can solve anything in O(1) with these "magic" constructors and imaginary computers, including NP problems.

of course we are using an imaginary computer, because this is an academic question, not a practical-real-world application of it. if you like you could benchmark my solution against a functoin that goes over an array and sets each index to the value, i'm still pretty sure my solution will work faster.

In order to prove a point, you would have to beat memset(), since your constructor probably uses something like that.

 

[Pia]

of course we are using an imaginary computer, because this is an academic question, not a practical-real-world application of it. if you like you could benchmark my solution against a functoin that goes over an array and sets each index to the value, i'm still pretty sure my solution will work faster.

As iCyborg explained, the problem is your assumption runs counter to all of computer science. If a memory reservation zeroes the memory, then the cost of making that reservation is definitely omega(N) so you can't assume it's O(1). Consequently your solution is O(n) instead of O(1) as required by the riddle.

Seriously, though, read my solution.

 

[degibson]

Seriously, though, read my solution.

Though it's clever, I think your solution still has a hidden O(N), because it still requires initialization.

In particular it requires contents of A to be initialized to something not on 0...N-1, or contents of B to be initialized to something not on 0...N-1. So even though its not assuming any particular initialization, it doesn't work for arbitrary initialization. I.e., 0 could start out as 'set'
A[0] = 0.

 

[iCyborg]

I thought so too at first, but it doesn't. Try constructing some values for A,B,D so it doesn't work, and you'll see why - S tracks the number of assigned and initialized memory, and it doesn't matter what A, B, D are outside of that, so no need for any initialization. A[0] will be interpreted as something meaningful only if S>0 which means it had to be set previously.

 

[degibson]

I forgot S. So long as contents of arrays are non-negative, seems to work?

 

[eLiu]

Ok, some riddles that don't rely on ridiculous "assumptions" (quotes b/c you're not even assuming something vaguely realistic) about how computers/compilers work...

0) Reverse a linked list (you can modify the list).

1) (I've posted this one before but I really like it) I give you a pointer to the head node of a linked list. I want to know whether the linked list has a cycle. What are the time & space complexities?

2) You're organizing an epic bachelor party where attendees have the chance to get a hooker and some blow. There's a list of available hookers & a list of available blow. All attendees (males) submit the particular hookers & blow that they would be interested in.

This party is gonna be epic, so each hooker can only service one attendee. And the blow gets consumed so clearly each "quantity" of blow (clearly I know nothing about drugs) can only be used by one attendee (and perhaps his hooker).

Maximize the number of <attendee,hooker,blow> combinations. Time & space complexities?

If the description is too confusing, this should be more clear: you have 3 sets of people, {F},{G}, and {H}. For each f \in F, LG(f) returns the subset of G that f is compatible with; similarly HG(f) returns the subset of H that f is compatible with. You want to maximize the number of <f,g,h> triples under the following conditions:
1) any single person can only placed in one triple
2) Each <f,g,h> triple you find must have property that g \in LG(f) and h \in HG(f)

edit: clearly if you've seen these, then no need to post an answer (like the first one is pretty easy/common)

 

[Pia]

I forgot S. So long as contents of arrays are non-negative, seems to work?

Not sure why you think they must be non-negative.
It makes sense for the arrays A and B to be unsigned, of course, since they will only ever be used to hold positive numbers. But if they were signed and therefore randomly held negative numbers in uninitialized cells, the data structure would still work. It would just waste half of the potential indexing space.

 

[degibson]

Not sure why you think they must be non-negative.
It makes sense for the arrays A and B to be unsigned, of course, since they will only ever be used to hold positive numbers. But if they were signed and therefore randomly held negative numbers in uninitialized cells, the data structure would still work. It would just waste half of the potential indexing space.

I was forgetting the check on index being in 0..N-1. I was thinking that perhaps A[index] < S could be satisfied for S = 0 if A could be initialized to negative values.

 

[Pia]

Unfortunately I cheated with eLiu's 1) by looking up the answer. I was slightly confused whether the riddle was about a single or double linked list, but for the benefit of others I can now say it's single linked. The answer is pretty fun if you work it out instead of being stupid like I was.

Sat down with 2) for a bit. It feels like a job for a normal search, but I'm guessing there must be a shortcut or it wouldn't be a riddle.

 

[Borealis7]

for 2) (edit: now it is 1)

Spoiler

have 2 pointers to the head of the list (the node), advance the first one to "next()" if exists, and the second one to "next().next()" if exists, keep going until next() == null for both pointers. if they ever meet, there is a circle, and the function will deterministically stop and not loop forever.

did you ninja-edit the question numbers?

 

[eLiu]

Pia: What is a 'normal search'? I will say that 2) will be pretty hard if you haven't at least had algorithms (or even discrete math) at an undergrad level or equivalent. I won't say (yet) which parts of those subjects would come in handy, but if you are familiar w/them, this problem is pretty cute. When it was first posed to me, I actually didn't find the most efficient solution.

Borealis7: Yup, nice You're one of the few people I've seen get that on the first try.

edit: I guess 0) is too easy for you guys, haha

 

[Pia]

Pia: What is a 'normal search'?

Y'know... generic search. Depth first, breadth first, etc. But I'm sure there is a much simpler way. Must resist peeking.

I have done basic algorithms stuff but this problem rings no bells whatsoever.

 

[Borealis7]

for 2)
i guess the hookers don't have preferred drugs? it would seem the two problems (maximize <attendee,hooker> and maximize <attendee,blow>) are independent by your description.

Spoiler

so i would think to use 2 2-sided-graphs and do a Euler traverse on both and then merge the solutions? but i don't remember exactly how that helps...

 

[Pia]

Not independent. If you have two bachelors and both want one hooker and one blow, you need to make one triplet. Independent distribution could cause the hooker and blow to go to different bachelors and you'd have zero triplets.

 

[iCyborg]

It looks like a graph matching problem to me. I think I can reduce it to bipartite matching in the following way:
- one part of the graph would be {F}
- the other would be {G}x{H}, the cartesian product.
There would be an edge from {F} to {G}x{H} if <f,g,h> is a valid triple. All you need to do is a maximum matching, and there are known efficient algorithms for that.
I'm at work and don't have much time to ponder about this and the time&space complexities, or if there's a better way to solve this particular problem...

 

[Pia]

I did some googling, and though I understand next to nothing about the relevant math, it looks like the hooker and blow problem is NP?

Spoiler

I assume we have a solution to find max triplets.
We run the solution.
We check if any blow, hookers or bachelors are left over (obviously O(n)).
We just solved Tripartite Matching.
Tripartite Matching is NP.
Our solution is NP.

 

[Apathetic]

I feel so dumb for asking this, but can someone explain what the heck O, K, and N mean? I'm pretty sure I N is some number of things, but a google search for O isn't going to help me much

Google/wikipedia "Big O Notation"

Dave