## StartUp Interview Question for Interns

Country: India
Interview Type: Written Test

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

Let us parse the expression into an array of lexical tokens, tokens[2*N:0] such that:
- tokens[2*i] i=0,N are the number values
- tokens[2*i-1], i=1,N are the operator values

For each pair of indices (i,j), 0 <= i <= j <= N we define:
• Exp(i,j) = the set of all the expressions can be built with the tokens from 2*i to 2*j
• Min(i,j) = the min value of all the expressions in Exp(i,j)
• Max(i,j) = the max value of all the expressions in Exp(i,j)

Max(0,N) is the max value for the entire expression.

We use dynamic programming to compute Min and Max, based on a few recursive equations.
We cache the computed values as two hash tables, hashMin, hashMax.

``````(int,int) computeMinMax(int i, int j) {
// If the pair (i,j) was already processed, use the values stored in the hash tables
if (hashMin(i,j) and hashMax(i,j)))
return (hashMin(i,j), hashMax(i,j))

// If i == j, then Exp(i,j) has the unique expression tokens[i]
if (i == j) {
hashMin(i,j) = tokens[i];
hashMax(i,j) = tokens[i];
return (tokens[i], tokens[i]);
}

// If i < j, explore all the expressions in Exp(i,j), based on the top operator tokens[2*k-1]
int Min_i_j = MinInt;
int Max_i_j = MaxInt
for (int k = i+1; k <=j; k ++) {
(Min_Left, Max_Left) = ComputeMinMax(i,k-1);
(Min_Right, Max_Right) = ComputeMinMax(k,j);
string operator = tokens[2*k-1];
if (operator == “-‘) {
Min_i_j = min(Min_i_j, Min_Left – Max_Right)
Max_i_j = max(Max_i_j, Max_Left – Min_Right)
}
else { // operator = “+”
Min_i_j = min(Min_i_j, Min_Left + Min _Right)
Max_i_j = min(Max_i_j, Max_Left + Max_Right)
}
}
hashMin(i,j) = Min_i_j
hashMax(i,j) = Max_i_j;
return (Min_i_j, Max_i_j)
}``````

Complexity: O(N^3).
There are O(N^2) pairs (i.j). For each pair we compute Min(i,j), Max(i,j) at most once, thanks to the caching. Iterating over k from i+1 to j, takes O(N), so the total is O(N^2 * N) = O(N^3)

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

I dont think there is a greedy approach to the problem

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.

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