That was kind of as far as I got in my thinking, but that was after I'd finished the interview
I guess you could maintain a number of "additions since last 'percentile' call", and if it's < log n, do the insertions; if it's > log n, add them all to the back and sort the vector
Anyway, I feel a bit better now, since nobody said "Why didn't you use a ____, you idiot?"
I'm trying to go with you on this, but I still don't quite see how it would work. Each node tracks its total number of L and R children, all the way down?
class PercentileThingy:
def __init__(self):
self.tmp = []
self.s = []
self.i = []
def add(self, v):
self.tmp.append(v)
self.i.append(v)
def get(self, id):
return self.i[id]
def percentile(self, p)
p /= 100
j = int((len(self.s)+len(self.tmp))*p)
i = 0
r = -1
self.s += [1e1000]
while i < len(self.s):
for k,c in enumerate(self.tmp): if self.s[i] > c: self.s.insert(i, c); del self.tmp[k]
i += 1
if i == j: r = self.s[i]
self.s = self.s[:-1]
return r
@EricTressler Perhaps implement a non-balanced version and tell them that you know about red-black trees, but didn't have time.
The point of this kind of thing should be to see how you think about a problem and how much you know about the basics, not how quick you are at reproducing standard but non-trivial data structures from memory.
The challenge has the same problem the other one had. If you buy, it increases after you buy it. If you sell, it decreases after you sell it. The only logical thing to do it buy, then sell, then buy, then sell, etc.
CJam - 13
q~,>{mfW=}$0=
Try it at http://cjam.aditsu.net/
Example input: 2001 2014
Example output: 2002
Explanation:
q~ reads and evaluates the input, pushing the 2 numbers on the stack (say min and max)
, makes an array [0 1 ... max-1]
> slices the array starting at min, resulting in [min ...
This has to be one of the fastest-gaining answers I've seen on a golf challenge
@cjfaure If you buy the fastest rising stock, that means many people bought it last turn(s). If they think like you, you'll be on the trailing end of a sellout crash.
@Geobits I have another train of thought I need you to crush. Let's assume that you have no clue what other players will do. The only perfect knowledge that you have is what you are going to do. If you buy, you will positively affect the price. Likewise, if you sell, you will negatively affect the price. Without knowing anything about the other players, I think you should still max buy and max sell repeatedly.
I use Tudwell as an alias because one of my students called me that on a final exam years ago, because apparently he had never been to class or something.
There is a cheaty solution using J's . for that task, btw (it implements matrix multiplication using a given function for "addition" and another for "multiplication", more-or-less)
I think I'll implement it "for real" in J and include it as an aside
Regex (.NET flavour), 183 bytes
This is not really a contender for the win. But Eric Tressler suggested solving this problem with nothing but a regex, and I couldn't resist to give it a go. This might be possible in PCRE as well (and even shorter), but I chose .NET because my solution needs arbi...
You know a language is bad (from a readability point-of-view) when you write up your golfy solution formatted normally, and then you begin removing whitespace only to find there's (almost) none to be removed
ah, here's the one where I was eventually beaten by GolfScript (but not before starting quite a discussion whether regex solutions aren't even valid :D) codegolf.stackexchange.com/a/28612/8478
Sometimes I kinda miss regex from my active SO times... I almost never use it in real-life problems (except some search-replace-fu) and it's also quite rare that it's useful on PPCG.
I'm still not sure if I understand the question. My take is: Draw a 3D random walk that forks and doesn't intercept itself. Do this until there are N forks of M length (or no path is possible for that fork).
Sound right? If so, there's way too much unclear explanation going on.
@Doorknob Do you know if we can change the behaviour of Community♦ on PPCG? It says "I do things like ... randomly poke old unanswered questions every hour so they get some attention ..." (which I doubt - "every hour" seems a bit off imho). If we could change that to "randomly poke old (unclosed) questions" it would maybe also attract new answers for older questions. If we can we may open a discussion on meta whether we should do so or not.
@Howard I don't recall that that's been done on any SE site before, but it could be possible. I'll check to see whether that would be viable (by poking more people with sticks, of course).
@MartinBüttner I am rarely on chat - mainly because I'm doing most of the golfing when I am offline (or even without any computer at all - thinking about my code over and over again). I try to limit my time with PPCG to a few minutes which would be almost impossible when I am around in these chat rooms ;-)
@Howard Yes it's possible, but it's a bit... unusual. If you post a feature request with what criteria you would want (and why!), the team might consider it
On PPCG also old and already answered questions provide a valuable source for attraction of new answers and new users, which also supports growth of the site. Moreover, there are several barely noticed questions (often with only few answers) which are examples of good and noteworthy challenges.
...
@MartinBüttner And here the proof again - it is already very late and spent less time on "productive" work than intended. Not that it isn't pleasant to waste time with PPCG but I fear that I regret it somehow tomorrow morning.
@PeterTaylor Just finished reading that thesis on growing penrose tilings. Thanks a lot, that was very interesting. :) ... I don't think I'll get around to start working on my own GoL submission this week, but I might give it a shot on Monday.
CJam - 13
q~,>{mfW=}$0=
Try it at http://cjam.aditsu.net/
Example input: 2001 2014
Example output: 2002
Explanation:
q~ reads and evaluates the input, pushing the 2 numbers on the stack (say min and max)
, makes an array [0 1 ... max-1]
> slices the array starting at min, resulting in [min ...
