Easiet way would be to enumerate the intervals and remove duplicates, then separate non consecutive ranges
Brody Miller
>Asked in: Amazon, Google >This article is compiled by Ravi Chandra Enaganti
Aiden Richardson
you should be able to do this in log-linear time
Grayson Powell
case class I(start: Int, end: Int)
def merged(is: Seq[I]) = is sortBy {_.start} match { case Seq() => Seq() case sorted => val res = collection.mutable.ArrayBuffer.empty[I] var curr = sorted.head for (i
Tyler Thompson
>apply for job >great first intake with mister Tyrone Jackson >sounded really interesting and was willing to have me >"user, we would like to invite you to the next phase of the interview, you will do some small function-related exercises, so we can scale your competence" >great >mfw it's one question, multiple rounds, one question every 2 weeks >mfw round 6 >mfw i've been unemployed for 3 months now thanks to this job interview
for i in l[1:]: if m[0] < i[1] and m[1] > i[0]: m = (min(m[0], i[0]), max(m[1], i[1])) else: r.append(i) if m != l[0]: return mergeOne([m] + r) return (m, r)
def merge(l): while len(l) > 0: m, l = mergeOne(l) yield m
print list(merge(example))
Isaac Ward
>quadratic+ Thank you for your time.
Benjamin Allen
you first
Luke Perez
Only correct results matter in an interview, if he doesn't specify a run-time requirement.
Isaac Ramirez
already did
Henry Watson
The scala solution? "sorted" using quick sort, so has O(n^2) worst case
Zachary Perez
That depends, really. Quadratic would be acceptable for an intern or a junior. Anything above that should either do better the first time or do this shit in like 30 seconds and say that it is in fact a shitty solution.
Jaxon Harris
SELECT a.start, b.end INTO merged_intervals FROM intervals AS one, intervals AS two WHERE one.start = two.start
When do I start, mr. user?
Brayden Powell
A quadratic run time solution for something that essentially needs a comparison sort is completely acceptable.
Anthony Gomez
today I learned that Jow Forums doesn't know how to use a simple stack algorithm
this is just a balanced brackets problem
Benjamin Sanders
sort, segment tree. you easily get nlogn
Aaron Stewart
Oh no, I f*cked it up..
SELECT a.start AS start, CASE WHEN a.end >= b.end THEN a.end ELSE b.end END AS end INTO merged_intervals FROM intervals AS one, intervals AS two WHERE one.start = two.start
>qudratic completely acceptable >for nlogn problem might as well use bubble sort then huh >Average performance O(n^2) >just a balanced brackets problem elaborate >segment tree unnecessary complexity?
Thomas Jenkins
No one ever failed an interview because he used quick sort.
Nathan Miller
Meh, that's waht you get for renaming a/b to one/two to mkae it more readable..
def mergeIntervals(listOfIntervals): result = [] for i in listOfIntervals: a = [listOfIntervals[i[0]],listOfIntervals[i[1]]] for j in listOfIntervals: b = listOfIntervals[j] if b[0]
Camden Smith
Easy. Don't let this die until I get home.
Daniel Miller
intervals = [(5, 7), (11, 116), (3, 6), (10, 12), (6, 12)] def merge_once(l, n): a,b = l[n] for i in range(n+1, len(l)): n_a,n_b = l[i] if not (a > n_b or b < n_a): l[n] = (min(a,n_a), max(b,n_b)) l.remove(l[i]) return True return False
n = 0 while n < len(intervals): if not merge_once(intervals, n): n += 1 print (intervals)
We are always inclusive you fucking nazi! Get out!
Anthony Ward
>Activate Inactive >Boole what is this even srspost: this is why I preferred the filthy imperative solution as opposed to the fold one, I feel the readability suffers too much.
Lincoln Miller
So, have you figured out how to merge the already sorted intervals in a single pass?
Julian Hall
Well?
Parker Hughes
interviewing is literally hell
try being unemployed for 5
Justin Perez
I'm at 6 months
fuck my life and suck my dick
Jacob Foster
Too lazy to code. The idea is to sort the (a,b) intervals by a value ascending, and then iterate once over the sorted list. Two adjacent intervals are merged if and only if the left b is greater than the right a.
Lucas Lopez
Yep. You also need to extend the "current" interval when appropriate, example:
Levi Ross
Sorting sounds like a waste of time.
Aaron Torres
>sounds like a waste of time Please, enlighten us with your better alternative.
Jacob Lewis
That's exactly what is doing.
Isaac Murphy
>I get an interview >Google all the answers >wowee paste
I'm such an amazing engineer.
Luis Garcia
Y-you sound like a waste of time ;_;
Owen Williams
that's exactly what multiple posters were doing, you just happened to point to the least readable one hell, even 's moon language fold is more readable than the code golf you linked to
Luis Barnes
BBY don't listen to him. You're a cutie and your sorting methods make you better than that buttface.
Jaxson Russell
That's the whole point. Forcing unreadable one-liners into a language that was designed to not have those is fun. Though it isn't even a such bad case here, basically just a single reduce statement.
Leo Morris
:)))))))))
do other industries have the same bullshit interview process?
"we want to see if you can program"
*proceed to give some shitty algorithmic question that relates in no way to the API plumbing youll be doing in reality*
Charles Hall
def merge_intervals(l): l.sort()
result = [] stack = []
for tup in l: if len(stack) == 0: stack.append(tup[0]) stack.append(tup[1]) else: if stack[-1] >= tup[0]: stack.append(tup[0]) stack.append(tup[1]) else: stack = []
result.append((stack[0], stack[-1]))
return result
This works fine for one interval - how can I make it work for two or more?
Also, yes, it's not efficient.
Brandon Brooks
>reduce >not fold REEEEEEE
Henry Stewart
tf are you trying to do just keep a current interval and merge intervals when needed, and directly append it to result
Michael Cook
Do they do these kinds of interviews in data science ? I want to switch over. This shit is fucked
Landon Ward
>6th round interview >ask trivial shit Why would I want to work at such a company?
Josiah Jackson
Just restarted from scratch and I'm pretty much doing that now. Not sure where I was going desu...
Jacob Rivera
yeah you do, just not as difficult as most algorithm questions
also this is an easy question compared to most algorithm questions
James Jones
Python doesn't have fold
Nathaniel Rodriguez
reduce is the same fucking thing as (left) fold When did people start calling it "fold"? LISP called it reduce.
Camden Martinez
Yeah, everyone knows the basic HOFs are - ConvertToMany - remove-if-not - reduce
let merge_pass ints = let rec loop accu current_begin current_end = function | [] -> List.rev ((current_begin, current_end) :: accu) | (next_begin, next_end) :: ints -> if next_begin > current_end then merge_pass ((current_begin, current_end) :: accu) next_begin next_end ints else merge_pass accu current_begin next_end ints in match ints with | [] -> [] | (current_begin, current_end) :: ints -> loop [] current_begin current_end ints ;;
let merge ints = let ints = sort_pass ints in let ints = merge_pass ints in ints ;;
Ethan Rivera
oh the verbosity I thought you FP weenies preferred less verbose variable names
Christopher Cook
>doing manual recursion instead of fold for shame
Leo Scott
I like my code like I like women: chatty.
That's exactly the same thing.
Justin Long
>writing everything in a more verbose, unnecessarily difficult to read and more error-prone way, avoiding reuse of common patterns, is exactly the same thing.
David Perez
>unnecessarily difficult to read and more error-prone way Only in your head.
Nolan Clark
I like my code like I like women talkback: single-syllable (due to the ballgag)
Ayden Cox
and everyone else that's heard of basic shit like folds
Samuel Cox
You didn't grow out of fold_left? It will come, and that day you'll see why all good code begin with "let rec loop".
Brody Bailey
I like my code like I like my women: with a dick
Brayden Allen
>You didn't grow out of fold_left? It will come, and that day you'll see why all good code begin with "let rec loop".
>import overlap_solver Now add $50k/yr to my offer and I'll think about accepting.
William Richardson
>get phone call from Big Four company in Silicon Valley >they want to interview me for devops role >mostly used bash/zsh and Python before at work >nervous as all fuck about the interview What should I focus on? I'm boning up on data structures and file I/O in python, but what else?
Can you please demonstrate how to invert a binary tree?
You should be able to do this, user.
Anthony Lewis
Like uhhhh, get the pointy part below instead of above?
Nathan Thomas
Interviewing in tech sounds like literal hell. Thank god we don't have this stupid shit in other disciplines of engineering
Nicholas Lopez
You have fewer idiots who can't into fizzbuzz applying for jobs in other disciplines of engineering. Hence, recruitment doesn't need to add so many idiot filters. That, and computer nerds will put up with more abuse than most other types of nerds.
Sebastian Reyes
Other disciplines of engineering are simpler. You either have the degree or you don't. Most software related degrees have little to no bearing on the actual job duties you will be performing, AND there are a gorillion posers claiming they can do the job when they clearly can't, so we get all this mickey mouse bullshit.
Easton Robinson
I'd assume it's also not possible to copy-paste your way through something like a mechanical engineering job.
Levi Baker
I'd hope so. Although judging by those chinese escalator videos, it may be a regional thing.
Bentley Walker
tree.rotate(180)
Carson Sanders
People parrot and repeat this, but dogmatic type of thinking "just use da fizzbuss duuuhh" screams to me that perhaps people dont understand its a failure of the industry and not the applicants
Like what said. If we accept that the college degree is the ticket to a job, then maybe industry needs to adjust to that gatekeeping and accept they will need to mentor junior developers who dont really know shit, or convince higher education to change their teaching practices to better reflect the industry practice