Amazon Interview Question
SDE-2sCountry: India
Interview Type: In-Person
code optimization
# -*- coding: utf-8 -*-
__author__ = 'ouyhui'
class BooleanSatisfiabilitySolver:
def count_ways(self, expression):
self.expression = expression
n = (len(expression) + 1) / 2
self.total_count = [1 for i in xrange(n - 1)]
for i in xrange(n - 1):
if i == 0:
continue
sum = 0
for j in xrange(i):
sum += self.total_count[j] * self.total_count[i - j -1]
self.total_count[i] = sum
self.true_count = [[-1 for j in xrange(n + 1)] for i in xrange(n + 1)]
for i in xrange(n):
self.true_count[i][i + 1] = 1 if expression[2 * i] else 0
return self.evaluate(0, n, True)
def evaluate(self, start, end, result=True):
count = 0
if self.true_count[start][end] > -1:
count = self.true_count[start][end]
else:
for i in range(start + 1, end):
operator = self.expression[2 * i - 1]
if operator == '&':
count += self.evaluate(start, i) * self.evaluate(i, end)
elif operator == '|':
count += self.total_count[i-start-1] * self.total_count[end-i-1] \
- self.evaluate(start, i, False) * self.evaluate(i, end, False)
else:
count += self.evaluate(start, i) * self.evaluate(i, end, False)
count += self.evaluate(start, i, False) * self.evaluate(i, end)
self.true_count[start][end] = count
if result:
return count
else:
return self.total_count[end - start - 1] - count
Recursive solution
#include <string>
#include <vector>
#include <boost/tokenizer.hpp>
int num_true(const std::vector<std::string>& exp, int s, int e);
int num_false(const std::vector<std::string>& exp, int s, int e);
int num_ways_evaluate_true(const std::string& exp)
{
boost::char_separator<char> sep(" ");
boost::tokenizer<boost::char_separator<char>> tokens(exp, sep);
std::vector<std::string> exp_v;
for (const auto& token : tokens)
{
exp_v.push_back(token);
}
return num_true(exp_v, 0, exp_v.size() - 1);
}
int num_true(const std::vector<std::string>& exp, int s, int e)
{
if (s == e) return (exp[s] == "true") ? 1 : 0;
int num = 0;
for (auto i = s + 1; i < e; i += 2)
{
if (exp[i] == "&")
{
num += num_true(exp, s, i - 1) * num_true(exp, i + 1, e);
}
else if (exp[i] == "|")
{
num += num_true(exp, s, i - 1) * num_true(exp, i + 1, e);
num += num_false(exp, s, i - 1) * num_true(exp, i + 1, e);
num += num_true(exp, s, i - 1) * num_false(exp, i + 1, e);
}
else if (exp[i] == "^")
{
num += num_false(exp, s, i - 1) * num_true(exp, i + 1, e);
num += num_true(exp, s, i - 1) * num_false(exp, i + 1, e);
}
}
return num;
}
int num_false(const std::vector<std::string>& exp, int s, int e)
{
if (s == e) return (exp[s] == "false") ? 1 : 0;
int num = 0;
for (auto i = s + 1; i < e; i += 2)
{
if (exp[i] == "&")
{
num += num_false(exp, s, i - 1) * num_false(exp, i + 1, e);
num += num_false(exp, s, i - 1) * num_true(exp, i + 1, e);
num += num_true(exp, s, i - 1) * num_false(exp, i + 1, e);
}
else if (exp[i] == "|")
{
num += num_false(exp, s, i - 1) * num_false(exp, i + 1, e);
}
else if (exp[i] == "^")
{
num += num_false(exp, s, i - 1) * num_false(exp, i + 1, e);
num += num_true(exp, s, i - 1) * num_true(exp, i + 1, e);
}
}
return num;
}
Use dp as follows:
DP1[i][j] = Number of ways to evaluate exp(i,j) as true
DP2[i][j] = Number of ways to evaluate exp(i,j) as false
Now use memoization to evaluate and return DP[0][n].
Following is an implementation in python:
- anantpushkar009 November 03, 2014