Hello user,
We're excited to have you come back for our 6th round interview. Please follow our Senior Software Engineer Tyrone Jackson to the whiteboard room.
Given a list of intervals like:
[(5, 7), (11, 116), (3, 6), (10, 12), (6, 12)]
Write a function that will merge overlapping intervals.
You should be able to do this, user.
Other urls found in this thread:
Easiet way would be to enumerate the intervals and remove duplicates, then separate non consecutive ranges
>Asked in: Amazon, Google
>This article is compiled by Ravi Chandra Enaganti
you should be able to do this in log-linear time
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
>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
example = [(5, 7), (11, 116), (3, 6), (10, 12), (6, 12)]
def mergeOne(l):
m = l[0]
r = []
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))
>quadratic+
Thank you for your time.
you first
Only correct results matter in an interview, if he doesn't specify a run-time requirement.
already did
The scala solution?
"sorted" using quick sort, so has O(n^2) worst case
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.
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?
A quadratic run time solution for something that essentially needs a comparison sort is completely acceptable.
today I learned that Jow Forums doesn't know how to use a simple stack algorithm
this is just a balanced brackets problem
sort, segment tree. you easily get nlogn
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
C-can I have one more chance, Mr. user..?
(;__;)
Looks more likely to be timsort-inspired
stackoverflow.com
ARE YOU SURE ABOUT THAT ANSWER?
TEST YOUR CODE user
>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?
No one ever failed an interview because he used quick sort.
Meh, that's waht you get for renaming a/b to one/two to mkae it more readable..
But apart form that naming issue it works.
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]
Easy. Don't let this die until I get home.
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)
Python one.liner because why not
>>> (lambda l: reduce(lambda s, x: s[:-1] +((s[-1][0], x[1]),) if s[-1][1] >= x[0] else s+(x,), sorted(l, key=lambda x: x[0]), ((-1,-1),))[1:])([(5, 7), (11, 116), (3, 6), (10, 12), (6, 12)])
((3, 116),)
Best I can do. Worse case 2(n^2)
t = [(5, 7), (11, 116), (3, 6), (10, 12), (6, 12)];
t.sort(key=lambda x: x[0])
lim = len(t)
for i in range(lim - 1):
j = i + 1
while j < lim:
if t[j][0]
I like this thread.
>TEST YOUR CODE
I thought end users were QA now.
>But apart form that naming issue it works.
heh
the utter state of (You)
all solutions in this thread are invalid because for example (3, 6) (6, 12) exclude 6 and therefore are not overlapping
This is trivial to account for m8
This is my solution, change line 6
From b < n_a to b
If OP was using the correct syntax of () and [], he wouldn't be using brackets for the list.
Anyone got a better solution? Maybe not in place?
yeah, if he was using [ and ] he would just use ( and ) for the list
>Sorting before the quadratic
Mate
You could've just written a quadratic without sorting
Not my code bro.
Besides, is there even an algorithm with a worst case better than n2?
Heapsort, then merge in a single iteration:
O(n+nlogn) = O(nlogn)
This should work
(defun solve-better (data)
(let ((data (stable-sort data #'< :key #'car)))
(merge-lst data '())))
(defun merge-lst (lst help)
(if (null lst)
help
(let ((cell1 (car lst))
(cell2 (cadr lst)))
(if (comp-cells cell1 cell2)
(progn
(setf lst (cddr lst))
(let ((merged (merge-cells cell1 cell2)))
(merge-lst (push merged lst) help)))
(merge-lst (cdr lst) (push cell1 help))))))
(defun comp-cells (c1 c2)
(if (or(null c1) (null c2))
nil
(> (cadr c1) (car c2))))
(defun merge-cells (c1 c2)
(let ((min-range (car c1))
(max-range (max (cadr c2) (cadr c1))))
(list min-range max-range)))
[\code]
vector merge_overlapping_intervals(vector vec){
sort(vec.begin(), vec.end());
vector result;
result.push_back(vec[0]);
for(int i=1; i= get(vec[i]))
#else
if(get(result.back()) > get(vec[i]))
#endif
get(result.back()) = get(vec[i]);
else
result.push_back(vec[i]);
}
}
O(n*ln(n))
***
return result;
}
>#ifdef INCLUSIVE
>if inclusive
We are always inclusive you fucking nazi! Get out!
>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.
So, have you figured out how to merge the already sorted intervals in a single pass?
Well?
interviewing is literally hell
try being unemployed for 5
I'm at 6 months
fuck my life and suck my dick
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.
Yep.
You also need to extend the "current" interval when appropriate, example:
Sorting sounds like a waste of time.
>sounds like a waste of time
Please, enlighten us with your better alternative.
That's exactly what is doing.
>I get an interview
>Google all the answers
>wowee paste
I'm such an amazing engineer.
Y-you sound like a waste of time ;_;
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
BBY don't listen to him. You're a cutie and your sorting methods make you better than that buttface.
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.
:)))))))))
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*
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.
>reduce
>not fold
REEEEEEE
tf are you trying to do
just keep a current interval and merge intervals when needed, and directly append it to result
Do they do these kinds of interviews in data science ? I want to switch over. This shit is fucked
>6th round interview
>ask trivial shit
Why would I want to work at such a company?
Just restarted from scratch and I'm pretty much doing that now. Not sure where I was going desu...
yeah you do, just not as difficult as most algorithm questions
also this is an easy question compared to most algorithm questions
Python doesn't have fold
reduce is the same fucking thing as (left) fold
When did people start calling it "fold"?
LISP called it reduce.
Yeah, everyone knows the basic HOFs are
- ConvertToMany
- remove-if-not
- reduce
>- ConvertToMany
What's that? map?
>install gentoo
Barely tested
let sort_pass ints = List.sort (fun (b1, _) (b2, _) -> b1 - b2) ints;;
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
;;
oh the verbosity
I thought you FP weenies preferred less verbose variable names
>doing manual recursion instead of fold
for shame
I like my code like I like women: chatty.
That's exactly the same thing.
>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.
>unnecessarily difficult to read and more error-prone way
Only in your head.
I like my code like I like women talkback: single-syllable (due to the ballgag)
and everyone else that's heard of basic shit like folds
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".
I like my code like I like my women: with a dick
>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".
It isn't bait son.
It's the FP equivalent of Cnile-posting.
Reduce is similar to fold, not the same.
What's the difference between foldl and reduce?
error: reduce called on empty list
>>> reduce(str, () ())
()
>import overlap_solver
Now add $50k/yr to my offer and I'll think about accepting.
>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?
Hello user,
Can you please demonstrate how to invert a binary tree?
You should be able to do this, user.
Like uhhhh, get the pointy part below instead of above?
Interviewing in tech sounds like literal hell.
Thank god we don't have this stupid shit in other disciplines of engineering
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.
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.
I'd assume it's also not possible to copy-paste your way through something like a mechanical engineering job.
I'd hope so.
Although judging by those chinese escalator videos, it may be a regional thing.
tree.rotate(180)
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