## Adobe Interview Question for Interns

• 0

Country: India

Comment hidden because of low score. Click to expand.
2
of 2 vote

``````//assume x1 < x2 || y1 <= y2
struct line_seg
{
double x1, y1, x2, y2;
};

struct comp
{
bool operator() (const line_seg ls1, const line_seg ls2) const
{
if( slope(ls1) != slope(ls2) )
return slope(s1) < slope(s2);

if(ls1.x1 != ls2.x1)
return ls1.x1 < ls2.x1;

return ls1.y1 < ls2.y1;
}
};

line_seg max_seg;

multi_set< line_seg, comp > lsegs;

line_seg findMaxSegment()
{
return max_seg;
}

{
//1. insert segment in the set.
//2. check if the segment has same slope and overlaps with the previous and/or next segments (could me multiple of them)
//3. if yes, combine them to create a new larger segment
//4. insert the larger segment and remove the smaller ones inside it
//5. update max_seg if necessary
}``````

By maintaining an ordered set of segments we can add new segments in O( log n ) time** and report max in O(1) time (here n means at most n segments have been processed so far).

**Find/insert/remove in ordered set (actually balanced BST) is O( log n ). Since the total number of merged segments cannot be more than n, merging operation should be amortized O( log n ).

Comment hidden because of low score. Click to expand.
0

meant amortized O( 1 )

Comment hidden because of low score. Click to expand.
0

>> **Find/insert/remove in ordered set (actually balanced BST) is O( log n ).

Can you explain this step a bit further.

Thanks

Comment hidden because of low score. Click to expand.
0

In C++ set/multiset is implemented using a height balanced binary search tree (AVL or red-black tree). As a result these operations are bounded by the tree height, which is O( log n ).

Comment hidden because of low score. Click to expand.
0

line sweep algorithm ?

Comment hidden because of low score. Click to expand.
0
of 2 vote

>> **Find/insert/remove in ordered set (actually balanced BST) is O( log n ).

Can you explain this step a bit further.

Thanks

Comment hidden because of low score. Click to expand.
0
of 0 vote

it says "one dimensional", the code is for 2D...

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Who asked you to write perfect C code?

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Who asked you to write perfect C code?

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.