## Google Interview Question for Software Developers

Country: United States
Interview Type: In-Person

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

dynamic programming O(n^2)

``````class Range implements Comparable<Range>{
private int l;
private int r;
private double cost;
public Range(int i, int j, int k) {
l = i;
r = j;
cost = k;

}
@Override
public int compareTo(Range obj) {
if (r  ==  obj.r) {
return obj.l - l;
}
return r - obj.r;
}
}

double minCost(Range[] ranges, int L, int R) {
Arrays.sort(ranges);
double[] dp = new double[R + 1];
for (int j = L + 1; j <= R; j++) {
double min = Double.MAX_VALUE;
int i = ranges.length - 1;
while ( i >= 0 && ranges[i].r >= j) {
if (ranges[i].l < j) {
if (dp[ranges[i].l] != -1 &&  dp[ranges[i].l]  + ranges[i].cost < min) {
min = dp[ranges[i].l]  + ranges[i].cost;
}
}
i--;
}
if (min == Double.MAX_VALUE) {
dp[j] = -1;
}
else
dp[j] = min;
}
return dp[R];
}``````

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

I think Ddijkstra algorithm would be good for this problem

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

``````class Range implements Comparable<Range>{
private int l;
private int r;
private double cost;
public Range(int i, int j, int k) {
l = i;
r = j;
cost = k;

}
@Override
public int compareTo(Range obj) {
if (r  ==  obj.r) {
return obj.l - l;
}
return r - obj.r;
}
}
double minCost(Range[] ranges, int L, int R) {
double[] dp = new double[R + 1];
for (int j = L + 1; j <= R; j++) {
double min = Double.MAX_VALUE;
int i = ranges.length - 1;
while (i >= 0) {
if (ranges[i].r >= j&& ranges[i].l < j) {
if (dp[ranges[i].l] != -1 &&  dp[ranges[i].l]  + ranges[i].cost < min) {
min = dp[ranges[i].l]  + ranges[i].cost;
}
}
i--;
}
if (min == Double.MAX_VALUE) {
dp[j] = -1;
}
else
dp[j] = min;
}
return dp[R];
}``````

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

``````//Assumptions each of the range objects somehow overlaps with first and last.

public class Range{
int left;
int right;
cost;
}

public int minCost(int start,int end, Range[] arr)
{
if(start<end||start<0||end<0||arrr==null||arr.length==0)
{
return -1}

double[][] m=new double[end-start+1][end-start+1];
for(int r=0;r<m.length;r++)
{
for(int c=0;c<m[0].length;c++)
{
m[r][c]=-1.0;
}
}

for(int i=0;i<arr.length;i++)
{

Range entry=arr[i];
int row=start-start;
int col=end-start;
if(entry.left>=start && entry.left<=end)
{
row=entry.left-start;
}
if(entry.right>=start && entry.right<=end)
{
col=entry.right-start;

}

m[row][col]=m[row][col]==-1.0||m[row][col]>entry.cost?entry.cost:m[row][cost];
}

for(int c=m[0].length-1;c>=0;c--)
{
if(m[0][c]==-1.0 ||m[0][c]>m[0][c+1] && m[0][c+1]>0.00))
{
m[0][c]=m[0][c+1];
}
}

for(int r=1;r<m.length;r++)
{
int col=m[0].length-1;
m[r][col]=m[r][col]==(-1.0||(m[r][col]>m[r-1][col] && m[r-1][col]>0.0))?m[r-1][col]:m[r][col];
while(col>=r)
{
m[r][col]=m[r][col]==-1.0||(m[r][col]>m[r][col+1] && m[r][col+1]>0.0)?m[r][col+1]:m[r][col];
m[r][col]=m[r][col]==(-1.0||(m[r][col]>m[r-1][col] && m[r-1][col]>(float)0.0)?m[r-1][col]:m[r][col];
col--;

}
}

double minCost=-1.0;
for(int i=0;i<arr.length;i++)
{
double total=arr[i].cost;
if((end-entry.right)>0 && (m[entry.right+1][last]>0.0))
{
total+= m[entry.right][last];
}
if((entry.left-start)>0 && (m[start][entry.left-1]>0.0))
{
total+=m[start][entry.left-1];
}

minCost=minCost==-1.0||total<minCost?total:minCost;
}

return minCost;
}

/**Time Complexity: O(NM + M^2) where N is the number of range objects and M is the size of the range between first and last.
Space Complexity: O(M^2)**/``````

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

C++, implementation, O(2^n * n^2)

``````struct Paint {
int f;
int l;
float cost;
};

bool coverAllRange(int first, int last, vector<Paint>& arr, vector<int>& v) {
vector<pair<int, int>> ranges, temp;
int f, l, i, j;
bool overlap;

for (i = 0; i < v.size(); i++) {
if (v[i] == 0) continue;
overlap = false;
f = arr[i].f;
l = arr[i].l;
for (j = 0; j < ranges.size(); j++) {
if (arr[i].f <= ranges[j].second && arr[i].l >= ranges[j].first) {
if (overlap == false) {
overlap = true;
f = min(arr[i].f, ranges[j].first);
l = max(arr[i].l, ranges[j].second);
} else {
f = min(f, min(arr[i].f, ranges[j].first));
l = max(l, max(arr[i].l, ranges[j].second));
}
if (f <= first && l >= last) return true;
} else {
temp.push_back(ranges[j]);
}
}
ranges = temp;
ranges.push_back(make_pair(f, l));
temp.clear();
}

return false;
}

float solve(int first, int last, vector<Paint>& arr) {
queue<pair<int, vector<int>>> q;
vector<int> v;
int i, r;
float cost, temp;

cost = -1.0;

q.push(make_pair(arr.size(), v));

while (!q.empty()) {
r = q.front().first;
v = q.front().second;
q.pop();
if (r > 0) {
v.push_back(0);
q.push(make_pair(r - 1, v));
v[v.size() - 1] = 1;
q.push(make_pair(r - 1, v));
} else {
if (coverAllRange(first, last, arr, v) == true) {
temp = 0.0;
for (i = 0; i < v.size(); i++) {
if (v[i] == 1) temp += arr[i].cost;
}
if (cost == -1.0 || cost > temp) cost = temp;
}
}
}

return cost;
}``````

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

Python Solution:

``````def paint_range(range_, tokens):

def _is_overlap(r, t):
return not (r[0] > t[1] and r[1] < t[0])

def _split_range(ranges, t):
# Given a token, returns the ramaining parts to paint
result = []
for r in ranges:
if _is_overlap(r, t):
tmp = [(r[0], t[0] - 1), (t[1] + 1, r[1])]
result.extend(x for x in tmp if x[1] - x[0] >= 0)
else:
result.append(r)
return result

def _is_useful(ranges, t):
# Check if we should use a given token
for r in ranges:
if _is_overlap(r, t):
return True
return False

def _paint_range(ranges, tokens, cost):
# print "New Call: %s %s %s" % (str(ranges), str(tokens), str(cost))
if not ranges:
# Found a value
return cost
if not tokens:
# There are ranges left, return inf
return float('inf')

min_cost = float('inf')
for i, t in enumerate(tokens):
if _is_useful(ranges, t):
min_cost = min(min_cost, _paint_range(_split_range(ranges, t),
tokens[:i] + tokens[i + 1:],
cost + t[2]))

return min_cost

return _paint_range([tuple(range_)], tokens, 0)

print paint_range([0, 5], [(0, 5, 10), (0, 4, 1), (0, 2, 5), (2, 5, 1)])
print paint_range([0, 5], [(1, 4, 10), (2, 5, 6)])
print paint_range([2, 6], [])
print paint_range([2, 6], [(3, 3, 1), (0, 8, 12), (2, 2, 1), (4, 6, 1)])``````

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

``````public class PaintRange
{
public int first;
public int last;
public int cost;

public PaintRange(int first, int last, int cost)
{
this.first = first;
this.last = last;
this.cost = cost;
}
}

public class PaintRangeBlack
{
public int FindMinimumCost(int first, int last, int cost, List<PaintRange> ranges)
{
int minCost = Int32.MaxValue;
int oldcost = cost;

foreach (var range in ranges)
{
if (range.first <= first && range.last > first)
{
if (minCost == Int32.MaxValue || cost + range.cost < minCost)
{
cost += range.cost;

if (range.last < last)
{
int temp = FindMinimumCost(range.last, last, cost, ranges);
if (temp != Int32.MaxValue && minCost>temp)
minCost = temp;
}

if (range.last >= last && minCost > cost)
{
minCost = cost;
cost = oldcost;
}
}
}
cost = oldcost;
}

return minCost;
}``````

}

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

``````def findCost(start, end, costs):
minsofar = -1
for idx, cost in enumerate(costs):
if cost[1] < start or cost[0] > start:
continue

currcost = None
if cost[1] >= end:
currcost = cost[2]

else:
if idx+1 < len(costs):
currcost = findCost(cost[1], end, costs[:idx] + costs[idx+1:])
if currcost is not None:
currcost += cost[2]

if minsofar == -1 or (currcost and minsofar > currcost):
minsofar = currcost

return minsofar

print(findCost(0, 5, [[0, 5, 10], [0, 4, 1], [0, 2,5], [2, 5, 1]]))
print(findCost(5, 10, [[0, 5, 10], [0, 4, 1], [0, 2,5], [2, 5, 1], [1, 11, 4]]))
print(findCost(0, 10, [[1, 5, 1], [0, 6, 2], [2, 8, 3], [5, 10, 1], [0, 11, 8]]))
print(findCost(0, 5, [[0, 5, 10], [0, 3, 1], [3, 4, 2], [3, 4, 1], [4, 5, 1], [0, 2, 5]]))
print(findCost(0, 5, [[1,4, 10], [2, 5, 6]]))``````

output:
2
4
3
3
-1

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

``````def findCost(start, end, costs):
minsofar = -1
for idx, cost in enumerate(costs):
if cost[1] < start or cost[0] > start:
continue

currcost = None
if cost[1] >= end:
currcost = cost[2]

else:
if idx+1 < len(costs):
currcost = findCost(cost[1], end, costs[:idx] + costs[idx+1:])
if currcost is not None:
currcost += cost[2]

if minsofar == -1 or (currcost and minsofar > currcost):
minsofar = currcost

return minsofar

print(findCost(0, 5, [[0, 5, 10], [0, 4, 1], [0, 2,5], [2, 5, 1]]))
print(findCost(5, 10, [[0, 5, 10], [0, 4, 1], [0, 2,5], [2, 5, 1], [1, 11, 4]]))
print(findCost(0, 10, [[1, 5, 1], [0, 6, 2], [2, 8, 3], [5, 10, 1], [0, 11, 8]]))
print(findCost(0, 5, [[0, 5, 10], [0, 3, 1], [3, 4, 2], [3, 4, 1], [4, 5, 1], [0, 2, 5]]))
print(findCost(0, 5, [[1,4, 10], [2, 5, 6]]))

output:
2
4
3
3
-1``````

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

``````public static Function()
{
int F = 0;
int L = 5;
float C = -1;
Dictionary<int, bool> w = new Dictionary<int, bool>();
for (int i = F; i <= L; i++)
{
w.Add(i, false);
}

string tupleList = "[0, 5, 10], [0, 4, 7], [0, 2, 5], [2, 5, 1]";//"[1,4, 10], [2, 5, 6]";
List<Tuple> tuples = new List<Tuple>();
foreach (string tuple in tupleList.Split(']'))
{
if (tuple.Length < 5)
{
continue;
}
string temp = tuple.Trim(new char[] { ',', ']', '[', ' '});
string[] fields = temp.Split(',');
Tuple tempTuple = new Tuple
{
f = int.Parse(fields[0]),
l = int.Parse(fields[1]),
c = float.Parse(fields[2])
};
tuples.Add(tempTuple);
}

Dictionary<HashSet<int>, float> solutions = new Dictionary<HashSet<int>, float>();

for (int i = 0; i < tuples.Count; i++)
{
int f = F;
int l = L;
float c = 0;

HashSet<int> chosen = new HashSet<int>();

for (int j = i; j < tuples.Count; j++)
{
Tuple current = tuples[j];
bool anyUsed = false;
for (int k = current.f; k <= current.l; k++)
{
if (!w[k])
{
anyUsed = true;
w[k] = true;
}
}

if (anyUsed)
{
c += current.c;
chosen.Add(j);
}

bool allPainted = w.Values.All(r => r == true);
if (allPainted)
{
solutions.Add(chosen, c);
for (int m = F; m <= L; m++)
{
w[m] = false;
}
break;
}
}
}
}

struct Tuple
{
public int f;
public int l;
public float c;``````

}

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

``````public static void Function7()
{
int F = 0;
int L = 5;
float C = -1;
Dictionary<int, bool> w = new Dictionary<int, bool>();
for (int i = F; i <= L; i++)
{
w.Add(i, false);
}

string tupleList = "[0, 5, 10], [0, 4, 7], [0, 2, 5], [2, 5, 1]";//"[1,4, 10], [2, 5, 6]";
List<Tuple> tuples = new List<Tuple>();
foreach (string tuple in tupleList.Split(']'))
{
if (tuple.Length < 5)
{
continue;
}
string temp = tuple.Trim(new char[] { ',', ']', '[', ' '});
string[] fields = temp.Split(',');
Tuple tempTuple = new Tuple
{
f = int.Parse(fields[0]),
l = int.Parse(fields[1]),
c = float.Parse(fields[2])
};
tuples.Add(tempTuple);
}

Dictionary<HashSet<int>, float> solutions = new Dictionary<HashSet<int>, float>();

for (int i = 0; i < tuples.Count; i++)
{
int f = F;
int l = L;
float c = 0;

HashSet<int> chosen = new HashSet<int>();

for (int j = i; j < tuples.Count; j++)
{
Tuple current = tuples[j];
bool anyUsed = false;
for (int k = current.f; k <= current.l; k++)
{
if (!w[k])
{
anyUsed = true;
w[k] = true;
}
}

if (anyUsed)
{
c += current.c;
chosen.Add(j);
}

bool allPainted = w.Values.All(r => r == true);
if (allPainted)
{
solutions.Add(chosen, c);
for (int m = F; m <= L; m++)
{
w[m] = false;
}
break;
}
}
}
}

struct Tuple
{
public int f;
public int l;
public float c;``````

}

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

``````public static void Function7()
{
int F = 0;
int L = 5;
float C = -1;
Dictionary<int, bool> w = new Dictionary<int, bool>();
for (int i = F; i <= L; i++)
{
w.Add(i, false);
}

string tupleList = "[0, 5, 10], [0, 4, 7], [0, 2, 5], [2, 5, 1]";//"[1,4, 10], [2, 5, 6]";
List<Tuple> tuples = new List<Tuple>();
foreach (string tuple in tupleList.Split(']'))
{
if (tuple.Length < 5)
{
continue;
}
string temp = tuple.Trim(new char[] { ',', ']', '[', ' '});
string[] fields = temp.Split(',');
Tuple tempTuple = new Tuple
{
f = int.Parse(fields[0]),
l = int.Parse(fields[1]),
c = float.Parse(fields[2])
};
tuples.Add(tempTuple);
}

Dictionary<HashSet<int>, float> solutions = new Dictionary<HashSet<int>, float>();

for (int i = 0; i < tuples.Count; i++)
{
int f = F;
int l = L;
float c = 0;

HashSet<int> chosen = new HashSet<int>();

for (int j = i; j < tuples.Count; j++)
{
Tuple current = tuples[j];
bool anyUsed = false;
for (int k = current.f; k <= current.l; k++)
{
if (!w[k])
{
anyUsed = true;
w[k] = true;
}
}

if (anyUsed)
{
c += current.c;
chosen.Add(j);
}

bool allPainted = w.Values.All(r => r == true);
if (allPainted)
{
solutions.Add(chosen, c);
for (int m = F; m <= L; m++)
{
w[m] = false;
}
break;
}
}
}
}

struct Tuple
{
public int f;
public int l;
public float c;
}``````

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

``````public static void Function7()
{
int F = 0;
int L = 5;
float C = -1;
Dictionary<int, bool> w = new Dictionary<int, bool>();
for (int i = F; i <= L; i++)
{
w.Add(i, false);
}

string tupleList = "[0, 5, 10], [0, 4, 7], [0, 2, 5], [2, 5, 1]";//"[1,4, 10], [2, 5, 6]";
List<Tuple> tuples = new List<Tuple>();
foreach (string tuple in tupleList.Split(']'))
{
if (tuple.Length < 5)
{
continue;
}
string temp = tuple.Trim(new char[] { ',', ']', '[', ' '});
string[] fields = temp.Split(',');
Tuple tempTuple = new Tuple
{
f = int.Parse(fields[0]),
l = int.Parse(fields[1]),
c = float.Parse(fields[2])
};
tuples.Add(tempTuple);
}

Dictionary<HashSet<int>, float> solutions = new Dictionary<HashSet<int>, float>();

for (int i = 0; i < tuples.Count; i++)
{
int f = F;
int l = L;
float c = 0;

HashSet<int> chosen = new HashSet<int>();

for (int j = i; j < tuples.Count; j++)
{
Tuple current = tuples[j];
bool anyUsed = false;
for (int k = current.f; k <= current.l; k++)
{
if (!w[k])
{
anyUsed = true;
w[k] = true;
}
}

if (anyUsed)
{
c += current.c;
chosen.Add(j);
}

bool allPainted = w.Values.All(r => r == true);
if (allPainted)
{
solutions.Add(chosen, c);
for (int m = F; m <= L; m++)
{
w[m] = false;
}
break;
}
}
}
}

struct Tuple
{
public int f;
public int l;
public float c;``````

}

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

``````public static void Function7()
{
int F = 0;
int L = 5;
float C = -1;
Dictionary<int, bool> w = new Dictionary<int, bool>();
for (int i = F; i <= L; i++)
{
w.Add(i, false);
}

string tupleList = "[0, 5, 10], [0, 4, 7], [0, 2, 5], [2, 5, 1]";//"[1,4, 10], [2, 5, 6]";
List<Tuple> tuples = new List<Tuple>();
foreach (string tuple in tupleList.Split(']'))
{
if (tuple.Length < 5)
{
continue;
}
string temp = tuple.Trim(new char[] { ',', ']', '[', ' '});
string[] fields = temp.Split(',');
Tuple tempTuple = new Tuple
{
f = int.Parse(fields[0]),
l = int.Parse(fields[1]),
c = float.Parse(fields[2])
};
tuples.Add(tempTuple);
}

Dictionary<HashSet<int>, float> solutions = new Dictionary<HashSet<int>, float>();

for (int i = 0; i < tuples.Count; i++)
{
int f = F;
int l = L;
float c = 0;

HashSet<int> chosen = new HashSet<int>();

for (int j = i; j < tuples.Count; j++)
{
Tuple current = tuples[j];
bool anyUsed = false;
for (int k = current.f; k <= current.l; k++)
{
if (!w[k])
{
anyUsed = true;
w[k] = true;
}
}

if (anyUsed)
{
c += current.c;
chosen.Add(j);
}

bool allPainted = w.Values.All(r => r == true);
if (allPainted)
{
solutions.Add(chosen, c);
for (int m = F; m <= L; m++)
{
w[m] = false;
}
break;
}
}
}
}

struct Tuple
{
public int f;
public int l;
public float c;``````

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

``````def findCost(start, end, costs):
minsofar = -1
for idx, cost in enumerate(costs):
if cost[1] < start or cost[0] > start:
continue

currcost = None
if cost[1] >= end:
currcost = cost[2]

else:
if idx+1 < len(costs):
currcost = findCost(cost[1], end, costs[:idx] + costs[idx+1:])
if currcost is not None:
currcost += cost[2]

if minsofar == -1 or (currcost and minsofar > currcost):
minsofar = currcost

return minsofar

print(findCost(0, 5, [[0, 5, 10], [0, 4, 1], [0, 2,5], [2, 5, 1]]))
print(findCost(5, 10, [[0, 5, 10], [0, 4, 1], [0, 2,5], [2, 5, 1], [1, 11, 4]]))
print(findCost(0, 10, [[1, 5, 1], [0, 6, 2], [2, 8, 3], [5, 10, 1], [0, 11, 8]]))
print(findCost(0, 5, [[0, 5, 10], [0, 3, 1], [3, 4, 2], [3, 4, 1], [4, 5, 1], [0, 2, 5]]))
print(findCost(0, 5, [[1,4, 10], [2, 5, 6]]))
print(findCost(0, 5, [(0, 5, 10), (0, 4, 1), (0, 2, 5), (2, 5, 1)]))
print(findCost(0, 5, [(1, 4, 10), (2, 5, 6)]))
print(findCost(2, 6, []))
print(findCost(2, 6, [(3, 3, 1), (0, 8, 12), (2, 2, 1), (4, 6, 1)]))``````

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

Here is "expected" solution. (N*log(N) where N is number of intervals)

``````import heapq

def solve(first, last, intervals):
heap = [(0, first)]
for pos, end, cost in sorted(intervals + [(last, last, 0)]):
while heap and heap[0][1] < pos:
heapq.heappop(heap)
if not heap:
return -1
curCost, curPos = heap[0]
if curPos >= last:
return curCost
heapq.heappush(heap, (cost + curCost, end))

assert solve(0, 5, [[0, 5, 10], [0, 4, 1], [0, 2,5], [2, 5, 1]]) == 2
assert solve(0, 5, [[1,4, 10], [2, 5, 6]]) == -1
assert solve(0, 0, []) == 0
assert solve(0, 5, [[-3, -1, 10], [-1, 5, 10]]) == 10``````

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

Greedy solution approach:

1. Filter all Triples not fit for selection (not within range) - O(n)
2. Sort triples according to weight formula (num. uncovered range length + cost). Best options will be picked first - O(n logn)
3. Keep removing triples from list while full range not covered and while list not empty.

Total Time: - O(n log n)

``````public class MinCostPaint {

public static void main(String[] args) {
Range r = new Range(0,5);
Triple t1 = new Triple(0,5, 10);
Triple t2 = new Triple(0,4, 1);
Triple t3 = new Triple(0,2, 5);
Triple t4 = new Triple(2,5, 1);
List<Triple> list = new ArrayList<>();
list.add(t1);
list.add(t2);
list.add(t3);
list.add(t4);
findMinCostPaint(r, list);

Triple t2a = new Triple(1,4, 10);
Triple t2b = new Triple(2,5, 6);
List<Triple> list2 = new ArrayList<>();
list2.add(t2a);
list2.add(t2b);
findMinCostPaint(r, list2);
}

public static int findMinCostPaint(Range r, List<Triple> ts) {

List<Triple> tss = new ArrayList<>();
for (Triple triple : ts) {
if (triple.s >= r.s && triple.s < triple.e) {
tss.add(triple);
}
}

tss.sort(new TripleComparator(r));

List<Triple> result = new ArrayList<>();
Map<Integer, Boolean> paintedMap = new HashMap<>();
for (int i = r.s; i <= r.e; i++) {
paintedMap.put(i, Boolean.FALSE);
}
int paintedCount = 0;
int cost = 0;

while(!tss.isEmpty() && paintedCount < paintedMap.size()) {
Triple t = tss.remove(0);
for (int i = t.s; i <= t.e; i++) {
if (paintedMap.containsKey(i) && paintedMap.get(i).equals(Boolean.FALSE)) {
paintedMap.put(i, Boolean.TRUE);
paintedCount++;
}
}
cost += t.cost;
result.add(t);
}

if (paintedCount < paintedMap.size()) {
System.out.println("No possible ranges");
return -1;
}

for (Triple triple : result) {
System.out.println("(" + triple.s + "," + triple.e + ")");
}
System.out.println("min cost = " + cost);

return cost;
}
}

class TripleComparator implements Comparator<Triple> {

private Range rangeToCover;

public TripleComparator(Range rangeToCover) {
super();
this.rangeToCover = rangeToCover;
}

@Override
public int compare(Triple o1, Triple o2) {
Integer o1RangeUnCovered = (rangeToCover.e - o1.e) + (o1.s - rangeToCover.s);
if (o1RangeUnCovered < 0) {
o1RangeUnCovered = rangeToCover.e - rangeToCover.s;
}

Integer o2RangeUnCovered = (rangeToCover.e - o2.e) + (o2.s - rangeToCover.s);
if (o2RangeUnCovered < 0) {
o2RangeUnCovered = rangeToCover.e - rangeToCover.s;
}

Integer o1Weight = o1RangeUnCovered + o1.cost;
Integer o2Weight = o2RangeUnCovered + o2.cost;

return o1Weight.compareTo(o2Weight);
}
}

class Range {
Integer s;
Integer e;
public Range(int s, int e) {
super();
this.s = s;
this.e = e;
}
}

class Triple extends Range {
Integer cost;

public Triple(int s, int e, int cost) {
super(s, e);
this.cost = cost;
}
}
/**
output:
(0,4)
(2,5)
min cost = 2

No possible ranges``````

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

n is the number of intervals in input.
Time complexity of this implementation is O((n*logn)^2)
Can be optimized to O(n*n) by replacing std::map with an ordered-hash implementation.

Idea is to construct a cost_map.
For each interval <f, l> in input, insert key f and key l into cost_map.
cost_map[k] contains:
1) Adjacency vector = [<k,i> for all <k,i> in set of intervals]
2) Least cost to destination (initialized to infinity)

Traverse keys in cost_map from highest to lowest.
For each interval <k,last> in cost_map[k]
update cost_map[k]'s least_cost to destination.
For each i such that k < i <= last, update least_cost at cost_map[i]

cost_map[0]'s least_cost is the cost to the destination. If it is infinity, return -1.

``````typedef struct {
int first;
int last;
double cost;
} Triple;

typedef struct {
std::map<int, double> *adj_map;
double least_cost;
} AdjacentCosts;

AdjacentCosts *add_to_cost_map(std::map<int, AdjacentCosts*>& cost_map, int v)
{
AdjacentCosts *adj_costs_ptr = new AdjacentCosts();
adj_costs_ptr->adj_map = new std::map<int, double>();
adj_costs_ptr->least_cost = std::numeric_limits<double>::infinity();
cost_map[v] = adj_costs_ptr;
return adj_costs_ptr;
}

void build_cost_map(int first, int last, std::vector<Triple>& triples,
std::map<int, AdjacentCosts*>& cost_map)
{
// Build cost_map
std::vector<Triple>::iterator it;

add_to_cost_map(cost_map, first);
add_to_cost_map(cost_map, last);

for (it = triples.begin(); it != triples.end(); it++) {

AdjacentCosts *adj_costs_ptr;

std::map<int, AdjacentCosts*>::iterator cost_map_it = cost_map.find(it->first);
if (cost_map_it == cost_map.end()) {
// Insert triple's first if it doesn't exist
adj_costs_ptr = add_to_cost_map(cost_map, it->first);
} else {
adj_costs_ptr = cost_map_it->second;
}

// Insert triple's last if it doesn't exist
if (cost_map.find(it->last) == cost_map.end()) {
add_to_cost_map(cost_map, it->last);
}

std::map<int, double>& adj_map = *(adj_costs_ptr->adj_map);
std::map<int, double>::iterator adj_map_it = adj_map.find(it->last);
if (adj_map_it == adj_map.end()) {
adj_map[it->last] = it->cost;
} else {
adj_map[it->last] = std::min(adj_map[it->last], it->cost);
}
}
}

void solve(int first, int last, std::vector<Triple>& triples,
std::map<int, AdjacentCosts*>& cost_map)
{
// For each 'f' in cost_map
std::map<int, AdjacentCosts*>::reverse_iterator it;
for (it = cost_map.rbegin(); it != cost_map.rend(); it++) {
int f = it->first;
AdjacentCosts *adj_costs_ptr = it->second;
std::map<int, double>& adj_map = *(adj_costs_ptr->adj_map);

// For each {l, cost} in cost_map[f]
std::map<int, double>::reverse_iterator adj_it;
for (adj_it = adj_map.rbegin(); adj_it != adj_map.rend(); adj_it++) {
int l = adj_it->first;
double cost = adj_it->second;
double my_least_cost = adj_costs_ptr->least_cost;

if (l == last) {
my_least_cost = std::min(my_least_cost, cost);
} else {
my_least_cost = std::min(my_least_cost, cost + cost_map[l]->least_cost);
}
adj_costs_ptr->least_cost = my_least_cost;

// update least_cost in cost_map[k] for all f < k <= l
// TODO:  Can interval trees help reduce time complexity here ?
std::map<int, AdjacentCosts*>::reverse_iterator cost_map_it;
for (cost_map_it = cost_map.rbegin();
(cost_map_it != cost_map.rend()) and  cost_map_it->first > f;
cost_map_it++) {
if (cost_map_it->first > l)
continue;
AdjacentCosts& adj_costs = *(cost_map_it->second);
adj_costs.least_cost = std::min(my_least_cost, adj_costs.least_cost);
}
}
}
}

double min_cost(int first, int last, std::vector<Triple>& triples)
{
std::map<int, AdjacentCosts*> cost_map; // Key=first, Value=NeighborCost

build_cost_map(first, last, triples, cost_map);
solve(first, last, triples, cost_map);

double result = cost_map[first]->least_cost;
if (result == std::numeric_limits<double>::infinity()) {
result = -1;
}

return result;
}``````

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

``````gyujgyjuj
jghjv``````

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

gfhfghgf

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

In Perl

``````#!/usr/bin/perl -W

use strict;

print find_cost(0, 5, [[0, 5, 10], [0, 4, 1], [0, 2,5], [2, 5, 1]])."\n";
print find_cost(5, 10, [[0, 5, 10], [0, 4, 1], [0, 2,5], [2, 5, 1], [1, 11, 4]])."\n";
print find_cost(0, 10, [[1, 5, 1], [0, 6, 2], [2, 8, 3], [5, 10, 1], [0, 11, 8]])."\n";
print find_cost(0, 5, [[0, 5, 10], [0, 3, 1], [3, 4, 2], [3, 4, 1], [4, 5, 1], [0, 2, 5]])."\n";
print find_cost(0, 5, [[1,4, 10], [2, 5, 6]])."\n";

sub find_cost
{
my \$first = shift;
my \$last = shift;
my \$triples = shift; # array reference

my \$min_cost = -1;

for (my \$i = 0; \$i < scalar @{\$triples}; \$i++)
{
if (\$triples->[\$i]->[0] > \$first  || # Starts after first
\$triples->[\$i]->[1] < \$first)    # Ends before first
{
next;
}

my \$cost = -1;

if (\$triples->[\$i]->[1] >= \$last) # Ends after last, so add the cost
{
\$cost = \$triples->[\$i]->[2];
}
else
{
if (\$i < scalar @{\$triples} - 1)
{
my @left = @{\$triples}; # copy because splice is destructive.
my @right = @{\$triples};# copy
my @newarray = (splice(@left, 0, \$i), splice(@right, \$i + 1));
\$cost = find_cost(\$triples->[\$i]->[1], \$last, \@newarray);

\$cost += \$triples->[\$i]->[2] if (\$cost != -1);
}
}

\$min_cost = \$cost
if (\$min_cost == -1 || (\$cost != -1 && \$min_cost > \$cost));
}

return \$min_cost;
}``````

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

My solution in Java:
F(first, last) = min{ (F(first, i) + F(i, last)) } (i : first+ 1 -> last). After that we need compare with min F(first, last) if (first, last) existed inside a range in input.

``````public class PrintCostPaint {
public static void main(String[] agrs) {
int[][] a = { { 0, 2, 5 }, { 0, 4, 1 }, { 0, 5, 10 }, { 2, 5, 1 } };
System.out.println(cost(0, 5, a));
}

private static int cost(int first, int last, int[][] input) {
int min = Integer.MAX_VALUE;
for (int i = 0; i < input.length; i++) {
if (last <= input[i][1] && first >= input[i][0]) {
if (min > input[i][2]) {
min = input[i][2];
}
}
}
if (last - first == 1) {
// if (min == Integer.MAX_VALUE)
return min;
}

int cost = min;
for (int i = first + 1; i < last; i++) {
int totalCost = sum(cost(first, i, input), cost(i, last, input));
if (cost > totalCost && totalCost > 0) {
cost = totalCost;
}

}
return cost == Integer.MAX_VALUE ? -1 : cost;
}

private static int sum(int a, int b) {
if (a == -1 || b == -1) {
return -1;
}
return a + b;
}

}``````

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

O(nlogn) time and O(2*n) space complexity solution Java:

``````class Node {
Node left;
Node right;
int a, b, val;
Node(int a, int b) {
this.a = a;
this.b = b;
this.val = -1;
}
}

Node buildTree(int a, int b) {
Node root = new Node(a,b);
if ( a != b ) {
root.left = buildTree( a, mid );
root.right = buildTree( mid + 1, b );
}
return root;
}

insertSegment(int a, int b, int cost, Node root) {
if ( root.a > b || root.b < a ) return;

if ( a <= root.a && b >= root.b ) {
if ( root.val == -1 || root.val > cost ) {
root.val = cost;
return;
}
}

insertSegment(a, b, cost, root.left, root.right);
insertSegment(a, b, cost, root.left, root.right);

if ( root.left.val != -1 && root.right.val != -1) {
if ( root.val == -1 || root.val > root.left.val + root.right.val ) {
root.val = root.left.val + root.right.val;
}
}
}

Node root = buildTree(0, 5);

insertSegment(0,5,10);
insertSegment(0,5,10);
insertSegment(0,5,10);
insertSegment(0,5,10);
insertSegment(0,5,10);

System.out.println(root.val);``````

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

``````#include <iostream>
#include <cstdio>
#include <climits>
#include <algorithm>
#include <queue>
#include <cstring>
#include <cmath>
#include <vector>
#include <list>
#include <stack>
#include <bitset>
#include <string>
#include <stack>
#include <set>
#include <map>
#include <deque>
#include <ctime>

#define lld long long
#define INF 10002

using namespace std;

struct interval{

int start,end,cost;
interval(){}
interval(int s,int e,int c){
start = s;
end = e;
cost = c;
}

bool contains(int key){

if(key>=start && key<=end)
return true;
else
return false;
}
};

int dp[INF];

int main(){

cin.sync_with_stdio(false);
cout.sync_with_stdio(false);

int start,end;

cin>>start>>end;

vector<interval> store;

int n;
cin>>n;

for(int i = 0;i<n;i++)
{
interval newInterval;
cin>>newInterval.start>>newInterval.end>>newInterval.cost;
store.push_back(newInterval);
}

dp[0] = INF;
for(int i = 0;i<n;i++){

if(store[i].contains(start))
dp[0] = min(dp[0],store[i].cost);
}

//   cout<<dp[0]<<endl;
for(int i = start+1;i<=end;i++){

dp[i-start]  = INF;

for(int j = 0;j<n;j++){
if(store[j].contains(i))
{
int cost = store[j].cost;

if(store[j].start>=start+1)
cost = cost + dp[store[j].start-start-1];

dp[i-start] = min(dp[i-start],cost);
}
}
}

//for(int i = 0;i<end-start+1;i++)
//   cout<<dp[i]<<" ";

if(dp[end-start]>=INF)
cout<<"-1\n";
else
cout<<dp[end-start]<<endl;

return 0;
}``````

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

``````// RangePaint.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <vector>
class Cost {
public:
Cost(int begin, int end, float cost) :_begin(begin), _end(end), _cost(cost) {
}
int getBegin() {
return _begin;
}
int getEnd() {
return _end;
}
float getCost() {
return _cost;
}

private:
int _begin;
int _end;
float _cost;
};

float findMinCost(int begin, int end, const std::vector<Cost *>& costs) {
float * cumulativeCost;
cumulativeCost = new float[end-begin];
for (int i = begin; i<end;i++) {
cumulativeCost[i] = -1;
}
std::vector<Cost *>::const_iterator itr = costs.cbegin();
while (itr != costs.cend())
{
float startCost = 0;
if((*itr)->getBegin() > begin){
if(cumulativeCost[(*itr)->getBegin() - begin] == -1) {
itr++;
continue;
}
startCost = cumulativeCost[(*itr)->getBegin() - begin];
}
for (int j = (*itr)->getBegin(); j <(*itr)->getEnd(); ++j) {
if( j - begin >= 0 && j < end && ( cumulativeCost[j - begin] == -1 || cumulativeCost[j - begin] > (startCost + (*itr)->getCost())) ) {
cumulativeCost[j - begin] = startCost + (*itr)->getCost();
}
}
++itr;
}
return cumulativeCost[end - begin - 1];
}

int _tmain(int argc, _TCHAR* argv[])
{
std::vector<Cost *> costs;
costs.push_back(new Cost(0,5,10));
costs.push_back(new Cost(0,4,1));
costs.push_back(new Cost(0,2,5));
costs.push_back(new Cost(2,5,1));
//costs.push_back(new Cost(1,4,10));
//costs.push_back(new Cost(2,5,6));
float minCost = findMinCost(0, 5, costs);
printf("Min Cost = %f", minCost);
getchar();
return 0;
}``````

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

Time complexity Min{ mlogm, n} where m in number of ranges and n is the end range

``````import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class MinimumCost {
private int INT_MAX = 999999999;

public static void main(String[] args) {
MinimumCost obj = new MinimumCost();
List<Range> ranges = new ArrayList<>();
ranges.add(obj.createRange(0, 1, 1.0));
ranges.add(obj.createRange(1, 2, 1.0));
ranges.add(obj.createRange(2, 4, 2.0));
ranges.add(obj.createRange(2, 5, 3.0));
ranges.add(obj.createRange(1, 3, 1.0));
ranges.add(obj.createRange(0, 2, 2.0));
ranges.add(obj.createRange(3, 5, 2.0));
System.out.println(obj.findMinimumCostToPaint(5, ranges));
}

public Range createRange(int start, int end, double cost) {
return new Range(start, end, cost);
}

public class Range {
private int start;
private int end;
private double cost;

public Range(int start, int end, double cost) {
this.start = start;
this.end = end;
this.cost = cost;
}

public int getStart() {
return start;
}

public int getEnd() {
return end;
}

public double getCost() {
return cost;
}

}

public class RangeComparator implements Comparator<Range> {

@Override
public int compare(Range o1, Range o2) {
if (o1.getStart() == o2.getStart()) {
return Integer.compare(o1.getEnd(), o2.getEnd());
}
return Integer.compare(o1.getStart(), o2.getEnd());
}

}

public double findMinimumCostToPaint(int n, List<Range> ranges) {
double[] result = new double[n + 1];
for (int i = 1; i <= n; i++) {
result[i] = INT_MAX;
}
result[0] = 0;
Collections.sort(ranges, new RangeComparator());
for (Range r : ranges) {
double temp = result[r.getStart()] + r.getCost();
if (temp < result[r.getEnd()]) {
result[r.getEnd()] = temp;
}
}
if (result[n] == INT_MAX) {
return -1;
}
return result[n];
}

}``````

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

This solution iterates thourgh all combinations of quote triplets. For each triplet, either it is included in final solution, or it is not. The solution evaluates both paths for each triplet and comes up with a minimum cost solution.

``````typedef struct {
int f;
int l;
double c;
} quote;

typedef struct {
int f;
int l;
} range;

quote add(quote q1, quote q2) {
if ((q1.f <= q2.f) && (q1.l >= q2.l))
return q1;

if ((q1.f >= q2.f) && (q1.l <= q2.l))
return q2;

// ranges are not inclusive of each other
quote result;
result.f = (q1.f < q2.f) ? q1.f : q2.f;
result.l = (q1.l > q2.l) ? q1.l : q2.l;
result.c = q1.c + q2.c;
return result;
}

double min_cost(quote q[], unsigned int n, range r) {
if ((n == 0) || (r.f > r.l))
return -1;

quote p;
p.f = r.l;
p.l = r.f;
p.c = 0;
return get_min_cost(q, n, r, p);
}

double get_min_cost(quote q[], unsigned int n, range r, quote p) {
if (n == 0)
return -1;

if ((p.f <= r.f) && (p.l >= r.l))
return p.c;

double c1 = get_min_cost(q + 1, n - 1, r, p);
double c2 = get_min_cost(q + 1, n - 1, r, add(p, q[0]));
if (c1 == -1)
return c2;

if (c2 == -1)
return c1;

return (c1 < c2) ? c1 : c2;
}``````

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

``````public class Solution {

public static void main(String [] args) {

Triples t1 = new Triples(0, 5, 10);
Triples t2 = new Triples(0, 4, 1);
Triples t3 = new Triples(0, 2, 5);
Triples t4 = new Triples(2, 5, 1);

Triples [] array = {t1, t2, t3, t4};

System.out.println(getCost(0, 5, array));
}

public static int getCost(int start, int end, Triples [] array) {

int sum = 0;
int index = 0;

Arrays.sort(array);

while (index <= end) {
boolean found = false;

for (int i = 0; i < array.length; i++) {
if (array[i].isInclude(index)) {
sum += array[i].cost;
index = array[i].end + 1;
found = true;
break;
}
}

if (!found) {
return -1;
}
}

return sum;
}
}

class Triples implements Comparable<Triples> {

final int start;
final int end;
final int cost;

public Triples(int start, int end, int cost) {
this.start = start;
this.end = end;
this.cost = cost;
}

@Override
public int compareTo(Triples o) {

if (this.cost == o.cost) {
return Integer.compare(this.start, o.end);
}

return Integer.compare(this.cost, o.cost);

}

public boolean isInclude(int index) {
return index <= this.end && index >= this.start;
}
}``````

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

``````public class Painter {

static class Interval implements Comparable {
int beg;
int end;
int cost;

public Interval(int beg, int end, int cost) {
this.beg = beg;
this.end = end;
this.cost = cost;
}

public int compareTo(Object o) {
Interval i = (Interval) o;
if (i.beg != this.beg) return this.beg - i.beg;
else return this.end - i.end;
}

public String toString() {
return "(" + this.beg + "," + this.end + "," + this.cost + ")";
}
}

// intervals must be sorted before using this method
static int minCost(int beg, int end, Interval[] intervals, int idx, int costSoFar) {
if (beg >= end) return costSoFar;
if (idx == intervals.length || beg < intervals[idx].beg) return Integer.MAX_VALUE;
if (beg > intervals[idx].end) return minCost(beg, end, intervals, idx + 1, costSoFar);
int costUsingIdx = minCost(intervals[idx].end, end, intervals, idx + 1, costSoFar + intervals[idx].cost);
int costWithoutIdx = minCost(beg, end, intervals, idx + 1, costSoFar);
return costUsingIdx < costWithoutIdx ? costUsingIdx : costWithoutIdx;
}

static void test(int beg, int end, Interval[] intervals) {
int minCost = minCost(beg, end, intervals, 0, 0);
System.out.println("min cost = " + minCost);
System.out.println("---------------------------");
}

public static void main(String[] args) {
Interval[] intervals1 = new Interval[] {new Interval(0,5,10), new Interval(0,4,1), new Interval(0,2,5), new Interval(2,5,1)};
Arrays.sort(intervals1);
test(0, 5, intervals1);

Interval[] intervals2 = new Interval[] {new Interval(2, 5, 6), new Interval(1,4, 10)};
Arrays.sort(intervals2);
test(0, 5, intervals2);
}
}``````

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

``````from itertools import combinations
def check_range(lb, ub, paint):
sets = set()
for i in xrange(len(lb)):
sets |= set(range(max(lb[i],paint[0]),\
min(ub[i],paint[1]) + 1))
if len(sets) == paint[1] - paint[0] + 1:
return True
else:
False

def minimize_cost(paint, costs):
min_cost = None
for i in xrange(1, len(costs) + 1):
for c in combinations(costs, i):
lb, ub, cost = zip(*c)
if check_range(lb, ub, paint):
cost_sum = sum(cost)
if not min_cost or min_cost > cost_sum:
min_cost = cost_sum

return min_cost

paint = [0, 5]
costs = [(0, 5, 10), (0, 4, 1), (0, 2,5), (2, 5, 1)]
print minimize_cost(paint, costs)``````

Add a Comment
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.

Learn More

### 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.

Learn More

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More