14 ms·
How to Find the Longest Increasing Subsequence of an Array
- stevemk14ebr 9y agoI would fail this so hard
- deleted 9y ago[deleted]
- deleted 9y ago[deleted]
- annon23 9y agolol dumb$ter
- pianom4n 9y agoI'm pretty sure if you use a sorted map you can do this in n log n time, still with just n space. edit: https://www.jdoodle.com/a/pZv https://www.jdoodle.com/a/pZv
- dver 9y agoI explained to one of my neighbors, who's not in the industry, job searching in software dev is like the nightmare where you forgot that you had a college final and you haven't studied.
- NTDF9 9y agoI explained to my cousin who does Power engineering, "Imagine I fail you for inability to solve hard calculus problems from sem 1 of college on a whiteboard, even though you don't need any more than basics". He said, "I'd never subject myself to such crap interviewers"
- QML 9y agoThis is a dynamic programming problem; if anyone wants a resource, I'd recommend this book [1]. Longest Increasing Subsequence is on page 162. [1] http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-...
- nsporillo 9y agoInteresting to see this posted as I'm taking algorithms this semester and the homework due in 2 weeks has a LIS question. I accidentally implemented the longest common subsequence that runs in linear space[1] and it actually worked as a drop in replacement for LIS, for my particular question. [1] http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/DynProg/Docs/Hirschberg-LCS-1975.pdf http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/Dyn...