|
dfs and bfs are straightforward algos that I use quite often they're like the natural evolution of for loops
|
# ? Sep 13, 2016 02:10 |
|
|
# ? Jun 5, 2024 07:18 |
|
you have zero excuse if you can't whip them in a programming interview imo
|
# ? Sep 13, 2016 02:10 |
|
Symbolic Butt posted:you have zero excuse if you can't whip them in a programming interview imo people reading this thread are more likely to be fretting over their cost function for A* or which ordering is optimal for dfs than to have no idea how to create a "trivial" implementation of a bfs or dfs
|
# ? Sep 13, 2016 02:26 |
|
i tried to implement some kind of bi-directional A* but instead i just got two A*s that went right past each other at least the initial/goal states were correct for each direction so i was half right
|
# ? Sep 13, 2016 02:35 |
|
i have certainly sweat through a bfs/dfs whiteboard before, in part because the interviewer was an rear end in a top hat
|
# ? Sep 13, 2016 04:21 |
|
but like this is poo poo i use literally never, get off my nuts interview-man
|
# ? Sep 13, 2016 04:22 |
|
boob-first / dick-first search
|
# ? Sep 13, 2016 15:24 |
|
hobbesmaster posted:people reading this thread are more likely to be fretting over their cost function for A* or which ordering is optimal for dfs than to have no idea how to create a "trivial" implementation of a bfs or dfs i need to feel like an ultra-competent hardass by accusing everyone around me of fundamental incompetence, so please don't interrupt
|
# ? Sep 13, 2016 15:56 |
|
i used to know dfs and bfs, but mumps has hosed my brain because they can be fully replaced with $o and $q
|
# ? Sep 13, 2016 18:50 |
|
Captain Foo posted:boob-first / dick-first search
|
# ? Sep 13, 2016 19:56 |
|
have this been posted yet https://www.youtube.com/watch?v=ywWBy6J5gz8
|
# ? Sep 14, 2016 17:21 |
|
Zaito posted:have this been posted yet oh my goodness this is fantastic
|
# ? Sep 14, 2016 17:52 |
|
Symbolic Butt posted:you have zero excuse if you can't whip them in a programming interview imo whenever I do phone screens for entry/mid-level hires I usually ask them to write a "head-to-tail" solver and its always when they come up with very bad optimizations (hash the words in the dictionary and then sort?) and then when I do convince them to just write the bfs and track incoming edges they do p miserably . please just learn a search; it will make you comfortable with using several different data structures (set, queue, stack, and a map if you're storing back references) while not being more than like 10 lines of code. code:
FamDav fucked around with this message at 15:23 on Sep 15, 2016 |
# ? Sep 14, 2016 17:53 |
|
what's a "head-to-tail" solver?
|
# ? Sep 14, 2016 18:21 |
|
AWWNAW posted:what's a "head-to-tail" solver? an extra $50
|
# ? Sep 14, 2016 23:23 |
|
AWWNAW posted:what's a "head-to-tail" solver? if you're given two words (like head and tail) find a chain of words that's one letter different that link the two words. so head heal teal tell tall tail
|
# ? Sep 15, 2016 15:25 |
|
FamDav posted:if you're given two words (like head and tail) find a chain of words that's one letter different that link the two words. so this poo poo was a great way to kill time in high school poo poo shot soot toot tort port post
|
# ? Sep 15, 2016 15:33 |
|
FamDav posted:if you're given two words (like head and tail) find a chain of words that's one letter different that link the two words. so so i assume one of the preconditions of the interview question is that you can assume youre provided with a dictionary from which you can load words? and the expected answer is basically just "load these into a graph with edges between all words that are one letter apart performance be damned, then do a dfs or bfs to find a path between the two input words"? i really enjoy how in 90% of problems like this where someone wants you to use a graph to solve the problem, the lovely difficult part of actually building the graph is sort of a handwave.
|
# ? Sep 15, 2016 15:40 |
|
why do you need to load them into a graph? there are only (25 * length-of-word) possible connections, just enumerate them all at every step and check if they're in the dictionary. a constant factor of 100 is irrelevant in the "just get it working" stage.
|
# ? Sep 15, 2016 16:25 |
|
Jabor posted:why do you need to load them into a graph? but then you'd probably be told to trie again
|
# ? Sep 15, 2016 16:33 |
|
hobbesmaster posted:but then you'd probably be told to trie again lol
|
# ? Sep 15, 2016 16:36 |
|
LeftistMuslimObama posted:so i assume one of the preconditions of the interview question is that you can assume youre provided with a dictionary from which you can load words? and the expected answer is basically just "load these into a graph with edges between all words that are one letter apart performance be damned, then do a dfs or bfs to find a path between the two input words"? yeah no need to build a graph. just search and keep track of parents so you can reconstruct the path. the goal is to give you a no magic question; there shouldn't be a critical insight that makes things easy. it's also a question that requires you to use a few different data structures (even if it's an algorithm you should just know), as opposed to many others which are just array operations. this is for a phone screen, so in the event that they get this all very fast we start talking about similar problems that actually exist and how we can scale them beyond one off scripts.
|
# ? Sep 15, 2016 16:47 |
|
i did a genetic algorithm to find rare trade routes in elite: dangerous of course i dont actually play the game anymore so hell if i know if they are actually good or not http://i.imgur.com/n3l5xtc.gifv also i like genetic algorithms
|
# ? Sep 22, 2016 23:44 |
|
That's really cool. A couple years ago I wrote am iOS Worms clone that started off using genetic algorithms to find the best shot to take to hit an enemy player until I realised that actually just choosing the best angle/power out of 10,000 random shots worked even better. It was disappointing it was such a lame algorithm but the results were brilliant because it would always take the 'obvious' shots when they existed, and choose the shortest 'blow a tunnel through the mountain/roof' route when that was the only option. It was weird how intelligent it seemed when it did sneaky stuff like taking advantage of bugs in collision detection etc. My final year project at uni used them so a basic voice synthesiser would 'learn' how to pronounce words by example. It was sort of intelligible if you knew what it was trying to say.
|
# ? Sep 23, 2016 13:19 |
|
Captain Foo posted:this poo poo was a great way to kill time in high school
|
# ? Sep 23, 2016 15:56 |
|
i was trying to find a good memory efficient algorithm to compute the median of large datasets, didn't find one really but there are a number of cool approximations you can use. in the end i treated my data like a stream divided into frames and used reservoir gap sampling to approximate the median. it's not the most difficult or smartest algorithm out there but i thought it was nice i've also been having fun with algorithms for principal curvature estimation in point clouds, been implementing this thing and learned that "osculating" is a word https://otik.uk.zcu.cz/bitstream/handle/11025/10828/Getto.pdf i've come to the conclusion that point clouds suck for modelling 3d surfaces, use something with a continuous representation instead
|
# ? Sep 24, 2016 02:41 |
|
toiletbrush posted:That's really cool. A couple years ago I wrote am iOS Worms clone that started off using genetic algorithms to find the best shot to take to hit an enemy player until I realised that actually just choosing the best angle/power out of 10,000 random shots worked even better. It was disappointing it was such a lame algorithm but the results were brilliant because it would always take the 'obvious' shots when they existed, and choose the shortest 'blow a tunnel through the mountain/roof' route when that was the only option. It was weird how intelligent it seemed when it did sneaky stuff like taking advantage of bugs in collision detection etc. this is neat the bit about the algorithm doing sneaky stuff to seem more robust than it actually was is probably i think very close to how intelligence actually works i'm pretty sure that at least half of what i do is rationalized as a conscious act after the fact
|
# ? Sep 24, 2016 02:49 |
|
big scary monsters posted:i was trying to find a good memory efficient algorithm to compute the median of large datasets, didn't find one really but there are a number of cool approximations you can use. in the end i treated my data like a stream divided into frames and used reservoir gap sampling to approximate the median. it's not the most difficult or smartest algorithm out there but i thought it was nice you can implement quickselect with just streamed inputs and (intermediate) outputs - the actual resident-in-memory data is absolutely miniscule
|
# ? Sep 24, 2016 11:51 |
|
how do you stream quickselect with less than linear memory? seems non-obvious since you can't really do anything with the output of a partitioning round without knowing which partition will become larger (and solving that is tantamount to solving the original problem)
|
# ? Sep 24, 2016 15:23 |
|
you write two intermediate outputs, one for items larger than the pivot and one for items smaller - the only state you need to track is how many items went each way. the intermediate streams make it linear in total additional storage required, but streamable storage is a whole lot cheaper than random-access memory.
|
# ? Sep 24, 2016 15:38 |
|
|
# ? Jun 5, 2024 07:18 |
|
right, strictly speaking linear, but with a logarithmic bound on the number of reversals of head movement required on the work tape or something a bit wonky lik ethat. i expect "properly" sub-linear memory use is impossible without some solid additional assumptions though
|
# ? Sep 24, 2016 17:47 |