Solve the skyline problem

Question

Anónimo · Accepted Answer

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;
}

Anónimo · Answer

Matteo Gobbi · Answer

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

Meta

Pregunta de entrevista de Meta

Respuestas de entrevistas

Empresas seguidas

Búsquedas de empleo