Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

I had to give a wrong answer to get the job (2017)

dewitters.com

Post reply on HN
Print view View original

391–400 of 409 posts

Re: I had to give a wrong answer to get the job (2017)

#391

Post by vladf »

Dylan16807 wrote: post #390
vladf wrote: post #389

Earlier quoted context omitted.

Ah, I was in a rust/c++ frame of mind here—it seems you deeply rely on a copy operation being available, but unless you use indirection and weak pointers it might not be. I think with copy available this certainly works

I used copy mostly because the earlier post used it, but we can easily use moves instead. The access operator will just have to use some arithmetic to calculate which array an element is in. Moves also make it easier to have less memory overhead. If moves aren't available then a resizable array was doomed from the start.

Hrm, is it really that easy? If you only have a placeholder in one of your arrays that points to the moved object in the other, then you need to do the actual move back if you have a sequence of pops/pushes which force you to delloc the moved-to array (say you have a grow sequence which gets you almost ready to make the 64 array the small one and then a series of pops back)

Thought maybe in principle there’s yet another “amortization process“ which can be layered on top of what you already described that tries to keep the proportion of placeholders in both small and big arrays equal.

Re: I had to give a wrong answer to get the job (2017)

#392

Post by Dylan16807 »

vladf wrote: post #391
Dylan16807 wrote: post #390

Earlier quoted context omitted.

I used copy mostly because the earlier post used it, but we can easily use moves instead. The access operator will just have to use some arithmetic to calculate which array an element is in. Moves also make it easier to have less memory overhead. If moves aren't available then a resizable array was doomed from the start.

Hrm, is it really that easy? If you only have a placeholder in one of your arrays that points to the moved object in the other, then you need to do the actual move back if you have a sequence of pops/pushes which force you to delloc the moved-to array (say you have a grow sequence which gets you almost ready to make the 64 array the small one and then a series of pops back) Thought maybe in principle there’s yet anot…

You don't need placeholders. Can you explain why you're thinking about placeholders?

For using move, the most straightforward way is: pushes and pops go directly to the big array. For every push you also move one element from small to big. For every pop you also move one element from big to small. This is slightly different from the algorithm above, but basically equivalent.

Let's say you start with 32 elements in one array. If you grow into a bigger array, then by the time you add 32 more all your elements will be in the big array. If you shrink into a smaller array, then by the time you remove 16 all your elements will be in the small array.

> (say you have a grow sequence which gets you almost ready to make the 64 array the small one and then a series of pops back)

So let's say after the pushes we have 60/64 elements in the 64 array, almost full. There are also 2/32 in the smaller array.

Then we do 10 pops. Now there are 40/64 in the bigger array, and 12/32 in the smaller array.

Seems problem-free to me.

If we keep doing pops we end up with 0/64 in the bigger array and 32/32 in the smaller array. At this point we could push again, or we could promote the 32 array to 'big' if we need to pop.

When the arrays are size 32 and 64, the logic to access an element looks like this:

n = total number of elements

x = the key of element being accessed

if ((x % 32) < (n - 32)) return big[x] else return small[x]

Re: I had to give a wrong answer to get the job (2017)

#393

Post by [deleted] »

lmilcin wrote: post #286
munificent wrote: post #284

Earlier quoted context omitted.

> Arrays used as backing for lists are faster than linked list in almost all cases, assuming they are implemented correctly (as is the case in Java, which I bring as an example). I think you're overcorrecting here. There used to be a conventional wisdom that linked lists were always faster than dynamic arrays because you don't have to copy or shift items. But then CPUs got faster while memory didn't and caching effec…

> There used to be a conventional wisdom that linked lists were always faster than dynamic arrays because you don't have to copy or shift items. But then CPUs got faster while memory didn't and caching effects became so prevalent that that conventional wisdom is no longer true. Nothing to do with caches or conventional wisdom no longer being true. Think for a second, if you want to insert somewhere inside your shiny…

[deleted]

Re: I had to give a wrong answer to get the job (2017)

#394

Post by randomswede »

peferron wrote: post #348
lmilcin wrote: post #320

Earlier quoted context omitted.

Well, not exactly. What it really means is that the execution time does not depend on the size of input (n). What it does not say is how much time it takes to execute, whether it is exactly same amount of time every time or whether there exists some kind of upper bound on execution time. For example, an algorithm that takes 1/(randFloat()) time to insert an element to the data structure where randFloat() returns any…

> an algorithm that takes 1/(randFloat()) time to insert an element to the data structure where randFloat() returns any possible floating point number with equal distribution, is still O(1) algorithm, even though there is no upper limit on how long it can take to execute. According to the definition, if 1/(randFloat()) = O(1) then there must be a constant M that satisfies 1/(randFloat()) (In practice on most systems…

More a case of "f(n) = 1/randFloat() does not have a well-defined limit as n goes to infinity", so it would be hard to say that it fits in ANY complexity class.

What is, however, clear is that its run-time does not depend on the size of the input. And technically, that means we can find a constant (infinity) that always... But, that is pretty unsatisfying.

Re: I had to give a wrong answer to get the job (2017)

#395

Post by lmilcin »

areyousure wrote: post #386
whatshisface wrote: post #344

Earlier quoted context omitted.

I have never ever seen a linked list in a game, anywhere, serving any purpose.

Look at all the instances of "next" in this file: https://github.com/id-Software/Quake-III-Arena/blob/dbe4ddb1...

He is still probably technically right.

"I have never seen (...)"

Re: I had to give a wrong answer to get the job (2017)

#396

Post by IggleSniggle »

mewpmewp2 wrote: post #36
Radim wrote: post #9

Heh. Happens all the time with tests and questionnaires, the choice is always frustrating: * "Does the author really mean what they are asking? Are the mistakes in the phrasing or corner cases intentional, meant to catch me, test my deep knowledge?" , or * "Is the author just not very good with logic / not thinking this through?" I go with the latter in "soft social" contexts. Never regretted it yet. This saved my hi…

Same with some driving exam questions I have had. For example worded something like that, "does driving faster in some sections of the journey affect your planned time of arrival?" I don't remember if the wording was specifically like this, but it was something that to me logically obvious answer is "yes", but the correct answer and what they expect is "no", to show that you are a reasonable driver who won't speed un…

You’ve just reminded me of a question I had on a driver’s test many years ago.

The free-response question was something like: “What is the single most important thing you can do to improve your safety as a driver?”

I answered: “Always drive sober.”

The “correct” answer was: “Fasten your seatbelt.”

I can only imagine the grader’s face / thoughts when they had to mark my answer as incorrect.

Re: I had to give a wrong answer to get the job (2017)

#397

Post by dcow »

lmilcin wrote: post #395
areyousure wrote: post #386

Earlier quoted context omitted.

Look at all the instances of "next" in this file: https://github.com/id-Software/Quake-III-Arena/blob/dbe4ddb1...

He is still probably technically right. "I have never seen (...)"

Nobody responding asserted anything to the contrary. Rather, examples were provided rhetorically and for anybody interested in exploring more.

Re: I had to give a wrong answer to get the job (2017)

#398

Post by dcow »

randomswede wrote: post #394
peferron wrote: post #348

Earlier quoted context omitted.

> an algorithm that takes 1/(randFloat()) time to insert an element to the data structure where randFloat() returns any possible floating point number with equal distribution, is still O(1) algorithm, even though there is no upper limit on how long it can take to execute. According to the definition, if 1/(randFloat()) = O(1) then there must be a constant M that satisfies 1/(randFloat()) (In practice on most systems…

More a case of "f(n) = 1/randFloat() does not have a well-defined limit as n goes to infinity", so it would be hard to say that it fits in ANY complexity class. What is, however, clear is that its run-time does not depend on the size of the input. And technically, that means we can find a constant (infinity) that always... But, that is pretty unsatisfying.

https://www.quora.com/Why-isnt-infinity-a-constant

Re: I had to give a wrong answer to get the job (2017)

#399

Post by sagarm »

Buttons840 wrote: post #303
lmilcin wrote: post #290

Earlier quoted context omitted.

> None of the comments above yours in the thread mention any form of the word "fast" or "speed". They mention "performance" in reference to big-O complexity. Big-O is not always about speed. I am sorry, do you want to say "performance" and "big-O" have nothing to with trying to make the program go faster? I think you have lost your way and need to backtrack a little bit. The whole point of big-O analysis is to be abl…

If I ask for something to be done in O(1) I'm not asking for it to be fast, I'm asking for it to take the exact same amount of time every time no matter what. That might end up being slower, but so what, maybe that's what I need. If I ask for an O(1) algorithm and you build something that is as fast as possible, faster in every case, but sometimes it's really fast and sometimes it's a little less fast but still fast…

A hash table has E[O(1)] inserts and lookups. Most people ignore the expected part and just say those operations are O(1).

Asymptotic complexity is of course only loosely correlated with speed. In real systems with real workload sizes, constant factors matter a lot.

Re: I had to give a wrong answer to get the job (2017)

#400

Post by sagarm »

CuriousCosmic wrote: post #337
lmilcin wrote: post #316

Earlier quoted context omitted.

If your data structure is immutable, then an array is always faster than a linked list.

Immutable doesn't necessarily mean unchanging in the context of data structures. An immutable data structure can support adding, removing, and/or changing the data but the way it does it is in such a way that once data is created it isn't modified until it is completely unused and unreferenced. So an immutable data structure has the benefit that data stays the same and stays the same in memory so it can be shared whe…

The term you are looking for is pointer stability. It can be a useful property, but you can also get it storing pointers in a vector. That would often be faster in practice than a linked list.
Post reply on HN