Optimal Substructure: Interview Problem Survey
In computer science, a problem is said to have optimal substructure if an optimal solution can be constructed from optimal solutions of its subproblems. This property is used to determine the usefulness of greedy algorithms for a problem.Wikipedia In other words optimal solutions to sub-problems form the overall optimal solution. Here we can use the property of optimal sub-structure to explore the space of all possible entries into a phone pad leetcode [17]. example instance; "232" example solution; ["ada","adb","adc","aea","aeb","aec","afa","afb","afc","bda","bdb","bdc","bea","beb","bec","bfa","bfb","bfc","cda","cdb","cdc","cea","ceb","cec","cfa","cfb","cfc"] example code; class Solver { unordered_map operators = { {'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'4', "ghi"}, {'5', "jkl"}, {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"} } vector SOLUTION; string packetNumber; //in order depth-first-search void depthFirstSearch(int index, string path) { if(path.length() == packet_number.length()) { solution.push_back(path); return } map::iterator letters_iterator = operators.find(string[index]); for(char c : letters_iterator.second) { path.push_back(c); depthFirstSearch(index+1, path); path.pop_back(); } } public: vector letterCombinations(string digits) { if(digits.length() == 0) { return SOLUTION; } packetNumber = digits; depthFirstSearch("", 0); return SOLUTION; } } Here the solution requires going through all possible state changes and should be seen as a graph where the number of nodes are 2^4*n where n is the number of digits in the input and we know and it's safe to assume n < "a relatively small constant" so we can bound or algorithm to be constant. In this type of question we care about "revealing the search space" which should include a paper-napkin style verification the space is calculable. next we can take a leetcode [743] which can be solved using Dijkstra's algorithm. This is one of the properties in the ever famous Dijkstra's short path algorithm having optimal substructure we can take advantage of to not search the entire space of traversing the graph, the neat thing of Dijkstra's is we get to keep the structure to re-use. Here the example being calculating Network Delay from one node to another. class Solver { private: struct comp { bool operator()(const pair& a, const pair b) { return a.second > b.second; } } public: networkDelayTime(vector& times, int n, int k) { vector graph(n+1); for(auto& t : times) { graph[t[0]].emplace_back(make_pair(t[1], t[2])); } vector total_cost_to_travel(n+1, INT_MAX); priority_queue pq; pq.push(make_pair(k, 0)); total_cost_to_travel[k] = 0; int vertex_count = 0, maximum_delay = -1; while(not pq.empty()) { pair edgeIn = pq.top(); pq.pop(); if(total_cost_to_travel[edgeIn.first] < edgeIn.second) { continue; } ++vertex_count; maximum_delay = max(maximum_delay, total_cost_to_travel[edgeIn.first]); for(pair edgeOut : graph[edgeIn.first]) { int edgeWeight = total_cost_to_travel[edgeOut.first]; if(edgeWeight > edgeOut.second + edgeWeight) { total_cost_to_travel[edgeOut.first] = edgeOut.second + edgeWeight; pq.push(make_pair(edgeOut.first, tc[edgeOut.first])); } } } return vertex_count == n ? maximum_delay : -1; } }
In computer science, a problem is said to have optimal substructure if an optimal solution can be constructed from optimal solutions of its subproblems. This property is used to determine the usefulness of greedy algorithms for a problem.Wikipedia
In other words optimal solutions to sub-problems form the overall optimal solution.
Here we can use the property of optimal sub-structure to explore the space of all possible entries into a phone pad leetcode [17].
example instance;
"232"
example solution;
["ada","adb","adc","aea","aeb","aec","afa","afb","afc","bda","bdb","bdc","bea","beb","bec","bfa","bfb","bfc","cda","cdb","cdc","cea","ceb","cec","cfa","cfb","cfc"]
example code;
class Solver {
unordered_map operators = {
{'2', "abc"}, {'3', "def"}, {'4', "ghi"},
{'4', "ghi"}, {'5', "jkl"}, {'6', "mno"},
{'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}
}
vector SOLUTION;
string packetNumber;
//in order depth-first-search
void depthFirstSearch(int index, string path) {
if(path.length() == packet_number.length()) {
solution.push_back(path);
return
}
map::iterator letters_iterator = operators.find(string[index]);
for(char c : letters_iterator.second) {
path.push_back(c);
depthFirstSearch(index+1, path);
path.pop_back();
}
}
public:
vector letterCombinations(string digits) {
if(digits.length() == 0) {
return SOLUTION;
}
packetNumber = digits;
depthFirstSearch("", 0);
return SOLUTION;
}
}
Here the solution requires going through all possible state changes and should be seen as a graph where the number of nodes are 2^4*n where n is the number of digits in the input and we know and it's safe to assume n < "a relatively small constant" so we can bound or algorithm to be constant.
In this type of question we care about "revealing the search space" which should include a paper-napkin style verification the space is calculable.
next we can take a leetcode [743] which can be solved using Dijkstra's algorithm.
This is one of the properties in the ever famous Dijkstra's short path algorithm having optimal substructure we can take advantage of to not search the entire space of traversing the graph, the neat thing of Dijkstra's is we get to keep the structure to re-use.
Here the example being calculating Network Delay from one node to another.
class Solver {
private:
struct comp {
bool operator()(const pair& a, const pair b) {
return a.second > b.second;
}
}
public:
networkDelayTime(vector>& times, int n, int k) {
vector>> graph(n+1);
for(auto& t : times) {
graph[t[0]].emplace_back(make_pair(t[1], t[2]));
}
vector total_cost_to_travel(n+1, INT_MAX);
priority_queue, vector>, comp> pq;
pq.push(make_pair(k, 0));
total_cost_to_travel[k] = 0;
int vertex_count = 0, maximum_delay = -1;
while(not pq.empty()) {
pair edgeIn = pq.top(); pq.pop();
if(total_cost_to_travel[edgeIn.first] < edgeIn.second) {
continue;
}
++vertex_count;
maximum_delay = max(maximum_delay, total_cost_to_travel[edgeIn.first]);
for(pair edgeOut : graph[edgeIn.first]) {
int edgeWeight = total_cost_to_travel[edgeOut.first];
if(edgeWeight > edgeOut.second + edgeWeight) {
total_cost_to_travel[edgeOut.first] = edgeOut.second + edgeWeight;
pq.push(make_pair(edgeOut.first, tc[edgeOut.first]));
}
}
}
return vertex_count == n ? maximum_delay : -1;
}
}
