Meta interview question

Solve the skyline problem

Interview Answers

Anonymous

13 May 2013

For 0sum triplet : function lca(root, a, b){ var res = null; (function(subroot){ var ret = 0; if(subroot == a) ret += 1; if(subroot == b) ret += 2; // a, b can be the same // lca can be either a or b as well if( ret == 3 ) { res = subroot; return 0; } if(subroot.left != null){ ret += arguments.callee(subroot.left); } if(subroot.right != null){ ret += arguments.callee(subroot.right); } if (ret === 3) { res = subroot; return 0; } return ret; })(root); return res; }

Anonymous

13 May 2013

function zerotrip(arr){ arr.sort(); var pivot = 0; var res = {}; while (pivot target){ -- high; }else if(cur_sum < target){ ++ low; }else{ var tuple = [arr[pivot], arr[low], arr[high]]; tuple.sort(); var key = tuple.join(','); if(res[key] == void 0){ res[key] = tuple; } // either inc low or dec high, since arr contains no duplicate ++ low; } } ++ pivot; } for(var key in res){ console.log(res[key]); } } zerotrip([-1, -2, -3, 2, 0, 1]);

Anonymous

18 Jun 2013

import java.io.*; import java.util.ArrayList; import java.util.List; public class skyline { public static void main (String args[]) { List val = new ArrayList(); List tuples = new ArrayList(); int start = 0; boolean new_seg = false; try { BufferedReader in = new BufferedReader(new FileReader("skyline_problem.txt")); //Passo 0 String s = in.readLine(); tuple t = new tuple(s); tuples.add(t); //Cicli dopo for(s = in.readLine(); s != null; s=in.readLine()) { if(new_seg) { val.add(new segment(t.s,t.h)); new_seg = false; } t = new tuple(s); boolean seg_trov = false; int o; for(o=start; ot2.h) { val.add(new segment(t.s,t.h)); } } if(t.f>t2.f) { if(t.h>t2.h) { val.add(new segment(t.f,0)); } else { val.add(new segment(t2.f,t.h)); val.add(new segment(t.f,0)); } } else { if(t.h>t2.h) { val.add(new segment(t.f,t2.h)); val.add(new segment(t2.f,0)); } } seg_trov = true; } else { start = o+1; } } if(!seg_trov) { start = o; new_seg = true; } //Aggiungo la tupla appena ispezionata alla lista tuples.add(t); } in.close(); //Pulisco int min = 999999999; for (int i = val.size()-1; i >= 0; i--) { segment g = val.get(i); if(g.x