CareerCup

package com.mirak.careercup.palantir;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class DecodeGrid {

  private class Pair {
    char c;
    int count;

    Pair(char c, int count) {
      this.c = c;
      this.count = count;
    }
  }

  public List<String> decodeGrid(String grid) {
    ArrayList<Pair> list = new ArrayList<>();
    Set<Character> validChars = new HashSet<>();
    validChars.add('_');
    validChars.add('r');
    validChars.add('b');

    int rows = decodeGridToChars(grid, list, validChars);

    int n = findLeastDivisor(rows);
    List<String> decodedGrid = new ArrayList<>();
    StringBuilder builder = new StringBuilder();
    int takenColumns = 0;
    for (int i = 0; i < list.size(); i++) {
      Pair pair = list.get(i);
      for (int j = 0; j < pair.count; j++) {
        builder.append("|").append(pair.c);
        takenColumns++;
        if (takenColumns == n) {
          pair.count -= (j + 1);
          takenColumns = 0;
          decodedGrid.add(builder.append("|").toString());
          builder = new StringBuilder();
          i--;
          break;
        }
      }
    }
    return decodedGrid;
  }

  private int findLeastDivisor(int len) {
    for (int i = 2; i * i <= len; i++) {
      if (len % i == 0) {
        return i;
      }
    }
    return 1;
  }

  private int decodeGridToChars(String grid, ArrayList<Pair> list, Set<Character> validChars) {
    int len = 0;
    int idx = 0;
    while (idx < grid.length()) {

      if (Character.isDigit(grid.charAt(idx))) {
        int j = idx + 1;
        while (j < grid.length() && Character.isDigit(grid.charAt(j))) {
          j++;
        }

        if (j == grid.length() || !validChars.contains(grid.charAt(j))) {
          return -1;
        }
        len += Integer.parseInt(grid.substring(idx, j));
        list.add(new Pair(grid.charAt(j), Integer.parseInt(grid.substring(idx, j))));
        idx = j + 1;
      } else {
        if (!validChars.contains(grid.charAt(idx))) {
          return -1;
        }
        list.add(new Pair(grid.charAt(idx), 1));
        idx++;
        len++;
      }
    }
    return len;
  }
}

public class ReplaceBits {
  public int replaceRangeBits(int n, int a, int b, int k) {
    if(b < a) {
      return -1;
    }
    // 1. take first (b-a) bits from k
    int d1 = ((1 << (b - a + 1)) -1);
    k &= d1;

    // 2. reset bits from position a to b in n.
    n &= ~(d1 << a);

    return n | (k << a);
  }
}

Here is O(n^3) solution. I loop through all the triplets of points, looking for only points that may form rectangle in clockwise order, meaning that we first hold the top_left point, then look for the top_right, then look for the bottom_right, finally look for the bottom_right, using math we deduce the position of the missing point and check if we have already this point given in the input points.
This may not give us duplicate rectangles because of the way we look for the rectangle in the set.

typedef pair<double, double> dd;
double oo = 10000000000000.0;
struct Point{
    double x,y;
    Point(double x, double y){
        this->x = x;
        this->y = y;
    }
};
Point* get_missing_point(Point* top_left, Point* top_right, Point* bottom_right, double m1, double m2){
    // m1 is the slope of line (top_left <--> top_right)
    // m2 is the slope of line (top_left <--> bottom_left)
    double ck = bottom_right->y - m1 * bottom_right->x;
    double ci = top_left->y - m2 * top_left->x;
    double x_bottom_left = (ci-ck) / (m1-m2);
    double y_bottom_right = m1*x_bottom_left + ck;
    return new Point(x_bottom_left, y_bottom_right);
}
double get_slope(Point* p, Point* q){
    double dy = p->y-q->y;
    double dx = p->x-q->x;
    if (dx == 0) {
        return oo;
    }
    return dy/dx;
}
bool is_perpendicular(double m1, double m2){
    if(m1 == oo || m2 == oo){
        return m1*m2 == 0.0;
    }
    return m1*m2 == -1.0;
}
double get_line_length(Point* p, Point* q){
    return sqrt( pow(p->x - q->x, 2)  + pow(p->y - q->y, 2));
}
int count_rectangles(vector<Point*>& points){
    unordered_set<dd> vis;
    
    for(Point* p : points){
        vis.insert({p->x, p->y});
    }
    
    int rec_cnt = 0;
    int n = (int)points.size();
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            
            if(points[j]->x <= points[i]->x){
                continue;
            }
            
            double m1 = get_slope(points[i], points[j]);
            for(int k=0; k<n; k++){
                
                if(points[k]->y >= points[j]->y){
                    continue;
                }
                
                double m2 = get_slope(points[j], points[k]);
                if(is_perpendicular(m1, m2)){
                    Point* missing_point = NULL;
                    if(m2 == oo){
                        missing_point = new Point(points[k]->x-get_line_length(points[i], points[j]), points[k]->y);
                    }else{
                        missing_point = get_missing_point(points[i], points[j], points[k], m1, m2);
                    }
                    if(vis.count({missing_point->x, missing_point->y})){
                        rec_cnt++;
                    }
                }
            }
        }
    }
    return rec_cnt;
}

Simple solution using two pointers.
Time Complexity: O(n). Space complexity: O(1) (no extra memory except the return merged intervals).

struct Interval{
    int begin, end;
    Interval(int begin, int end){
        this->begin = begin;
        this->end = end;
    }
};

void merge_interval(vector<Interval*> &intervals, Interval* to_be_merged){
    int n = (int) intervals.size();
    if(n == 0){
        intervals.push_back(to_be_merged);
        return;
    }
    
    if(to_be_merged->begin > intervals[n-1]->end){
        intervals.push_back(to_be_merged);
    }else{
        intervals[n-1]->end = max(intervals[n-1]->end, to_be_merged->end);
    }
}
vector<Interval*> merge_intervals(vector<Interval*> &intervals1, vector<Interval*> &intervals2){
    if(intervals1.size() == 0){
        return intervals2;
    }
    if(intervals2.size() == 0){
        return intervals1;
    }
    vector<Interval*> merged_intervals;
    // now we are sure that none of them is empty.
    int i=0, j =0;
    while(i < intervals1.size() && j < intervals2.size() ){
        if(intervals1[i]->begin < intervals2[j]->begin){
            merge_interval(merged_intervals, intervals1[i++]);
        }else{
            merge_interval(merged_intervals, intervals2[j++]);
        }
    }
    
    while(i < intervals1.size()){
        merge_interval(merged_intervals, intervals1[i++]);
    }
    while(j < intervals2.size()){
        merge_interval(merged_intervals, intervals2[j++]);
    }
    return merged_intervals;
}

Simple tree traversal then sort.
Time complexity: O(n log n), Space complexity: O(n).
code:

struct TreeNode{
    int val;
    TreeNode* left, *right;
    TreeNode(int x){
        val = x;
        left = right = NULL;
    }
};

struct output_node{
    int row, column;
    int val;
    output_node(int row, int column, int val){
        this->row = row;
        this->column = column;
        this->val = val;
    }
    
};

void traverse_tree(TreeNode* node, int row, int column, vector<output_node*> &nodes){
    if(node == NULL){
        return;
    }
    nodes.push_back(new output_node(row, column, node->val));
    
    traverse_tree(node->left, row+1, column-1, nodes);
    traverse_tree(node->right, row+1, column+1, nodes);
    
}
bool compare(output_node *a, output_node *b){
    if(a->column < b->column)
        return true;
    else if(a->column > b->column)
        return false;
    return a->row < b->row;
}
void print_inColumn_order(TreeNode* root){
    if(root == NULL){
        return;
    }
    vector<output_node*> nodes;
    traverse_tree(root, 0, 0, nodes);
    sort(nodes.begin(), nodes.end(), compare);
    printf("%d", nodes[0]->val);
    for(int i=1; i<nodes.size(); i++){
        printf(" %d", nodes[i]->val);
    }
    printf("\n");
}