CareerCup

O(nlogn) solution available here
faculty.kfupm.edu.sa/ics/darwish/stuff/ics353Handouts/Ch4Ch5.pdf

We did not have much time left in the interview (this was his 2nd question) so the objective was to only discuss ideas. I did not get too far but my basic idea was to find a way to create new points where buildings intersect (roof with wall) and throw away uninteresting points that are contained inside other buildings. That should provide you with an edge list basically of the "roof edges" that do not overlap. From that list, you can walk the edges (moving up or down as needed) to find the silhoutte.

We will maintain 2 lists, in first(L1) we will sort the buildings in descending order and in L2's each node we will keep range of silhouette constructed so far and the height of the endpoints (xh1,xh2) corresponding to node's range (x1,x2).

1. Sort the buildings according to height in descending order put them in L1.

2. Each time take the tallest building(T) from L1.(You may have a set of buildings with same height)

3. Insert this range in L2 in a sorted fashion as follows:- ( There can be 6 cases, say (a1,a2) is a node present and (b1,b2) corresponding to T is to be inserted.

a) If (b2 < a1) then insert new node b before the existing node a. Draw a line (b1,b2) at height of T. Set bh1 and bh2 to height of T.

b) If (b1 < a1 and b2 > a1 but b2 < a2), Draw a line (b1,a1) at height of T and vertical line from ah1 to T's height. Expand the range of existing node set a1 = b1 inside it. Update ah1 = T's height.

c) If (a1 > b1 and b1 > a2 and b2 > a2), Draw a line (a2,b2) at height of T and a vertical line from ah2 to T's height. Expand the range of existing node set a2 = b2 inside it. Update ah2 = T's height.

d) If (b1 < a1 and b2 > a2), Draw a line (b1,a1) and (a2,b2) at height of T. Draw vertical lines from ah1 and ah2 to T's height. Expand the range of existing node set a1=b1 and a2 = b2 inside it. Update ah1 and ah2 to T's height.

e) If (a2 < b1), insert the new node b after node a. Draw a line (b1,b2) at height of T. Set bh1 and bh2 to height of T.

f) Discard the node (New building's range and height is within the range of existing silhouette.


After this only vertical lines to ground will be left.

For each node x in L1 draw a vertical lines from xh1 and xh2 to ground.

Woah tough one, did he expect you to write code or just ideas/algorithm?

Btw how is the output supposed to be?

the x coordinate + height(h) wud suffice. It will mean that silhouette starts at x coordinate at height h and runs horizontal till another such ordered pair comes in...

other ways of representation cud also be there.

Sort the given set of buildings (x1,x2,height) on x1 in ascending order. Now draw a vertical line from first item of the sorted buildings at x1, vertically up of Height "height" given in first item of the sorted items. Them keep drawing a horizontal line and move right (I am asuming X-Y coordinates in first quadrent). While you draw the horizontal line, keep incrementing x (which was equal to x1) and keep checking if x=x2 or x=x1 of second item of sorted buildings. If x=x2, move vertically done, if x=x1 of second building (there is overlap of two buildings) discard previous x1 and use this new x1 and continue.

Well some more thoughts are needed. We cannot simply discard first x2, we can have the buildings like (2,20,50),(4,7,80),(8,12,40). Here first building is so broad that it is having the other end after all other buildings!...

Need to take this also into account.

dfg

i dint understand the question ?

is question is related to convex hull problem ?

is question is related to convex hull problem ?

is question is related to convex hull problem ?

"the x coordinate + height(h) wud suffice. It will mean that silhouette starts at x coordinate at height h and runs horizontal till another such ordered pair comes in...
"
-Well if that's the case the buildings would never overlap :)
BTW this problem can be used using segment trees where each leaf node contains the range and max. height for that range (rest of the nodes are zero).
Tat would run in O(NlogN). Note that for it to work we need to sort the array based upon heights.

This is extension to longest increasing subsequence..

- Store all the values of h in the hashmap with the index of x1 or x2
- Sort x1,x2 and put them in one array
- Now start from the lowest value of this new array, find the height and just draw a line (if you find more than one values for x1/x2 you take the higher value)

@Apal I was thinking the same thing and checked if te same solution is posted and have seen the hash solution. Google loves hashing :)

have 2 copies of build, which will have build.x, build.height, build,isStarting.
sort these 2n entries by build.x.
now,

for (2n build entries) {
  if (built.isStarting) {
    if (height of the root of maxHeap < build.height) {
      print (build.x, build.h)
    }
    insert build into maxHeap. Heap is based on height.
  } else { //build is ending
    currHeight = height of the root of maxHeap
    remove build from maxHeap.
    if (currHeight == build.height) { //we removed tallest build
      print (build.x, height of the root of maxHeap);
    }
  }
}

Honestly, this is such a screwed up question, can you really determine if candidate is good based on this question. Some interviewers have psychological issues and they want to hide their inferiority complex by asking such obscure problems that no one can answer.

I wrote this program to solve the Skyline problem of UVA 41.

This solves the problem in nlogn complexity. and requires no more than O(n) space.

import heapq as hq
buildings = [(1,11,5), (2,6,7), (3,13,9), (12,7,16), (14,3,25), (19,18,22), (23,13,29), (24,4,28)]
#1, 11, 3, 13, 9, 0, 12, 7, 16, 3, 19, 18, 22, 3, 23, 13, 29, 0
points = list()
for idx, building in enumerate(buildings):
    points.append((building[0], building[1], idx+1))
    points.append((building[2], building[1], -idx-1))

points.sort(key=lambda tup: tup[0])
points_q = list()
current_h = -1
current_x = -1
deleted_nodes=dict()
for point in points:
    current_x = point[0]
    id = 0
    if point[2] > 0:
        hq.heappush(points_q, (-point[1],point[2]))
        id = point[2]
    else:
        deleted_nodes[-point[2]] = True
    tp = hq.heappop(points_q)
    while tp[1] in deleted_nodes and points_q:
        tp = hq.heappop(points_q)
    if tp and tp[1] not in deleted_nodes:
        hq.heappush(points_q, tp)
    ll = hq.nsmallest(1, points_q)
    if ll:
        local_h = -ll[0][0]
    else:
        local_h = 0
    if local_h != current_h:
        current_h = local_h
        print('x=', current_x, 'y=', current_h)

leetcode.com/problems/the-skyline-problem/

simple

leetcode.com/problems/the-skyline-problem/discuss/719637/C%2B%2B-Solution-or-Sets-Does-it-All-or-O(NlogN)