🔧 Subroutines: Interview Problem Survey
Nachrichtenbereich: 🔧 Programmierung
🔗 Quelle: dev.to
Lets say we have an algorithm which performs a check if a string is a palindrome.
bool isPalindrome(string s) {
for(int i = 0; i < s.length()/2; i++) {
if(s.at(i) != s.at(s.length()-i-1)) {
return false;
}
}
return true;
}
This type of solution can be a subroutine to many questions; which may require pre-processing before calling isPalindrome(). An example may be removing spaces and alphanumeric characters.
bool cleanString(string s) {
string cleanedstr = "";
for(char c : s) {
if(isalnum(c)) {
cleanedstr += tolower(c);
}
}
return cleanedstr;
}
To better use the isPalindrome as a subroutine we can add additional parameters. This can help answering questions like leetcode 680; where at most one character can be deleted.
bool isPalindrome(string s, int i, int j) {
for(;i<j;i++,j++) {
if(s.at(i) != s.at(j)) {
return false;
}
}
return true;
}
and the parent function handles the case where we may have up to one deleted character.
bool atMostOneMissingPalendrome() {
int i = 0;
int j = s.length() -1;
for(int i = 0, j = s.length()-1; i<j; i++,j++) {
if(s.at(i) != s.at(j)) {
return isPalendrome(s, i, j-1) || isPalendrome(s, i+1, j);
}
}
return true;
}
Now a more common scenario during an interview is having to use depth-first search or breadth first search. One question where this appears is connected-components or connected islands style questions; where you are given a matrix and asked to find the number of islands or the biggest island where a '1' denotes sand presence and '0' denotes water.
example instance;
111000
100011
001010
example solution;
4
example code;
int depth_first_search(vector<vector<int>> matrix, int i, int j) {
if(matrix.at(i).at(j) == 0) {
return 0;
}
int total = 1;
if(i+1 < matrix.size())
total += depth_first_search(matrix, i+1, j);
if(i-1 >= 0)
total += depth_first_search(matrix, i-1, j);
if(j+1 < matrix.at(0).size())
total += depth_first_search(matrix, i, j+1);
if(j-1 >= 0)
total += depth_first_search(matrix, i, j-1);
return total;
}
int find_largest_island_size(vector<vector<int>> matrix) {
int max_island = 0;
for(int i = 0; i < matix.size(); i++) {
for(int j = 0; j < matrix.at(0).size(); j++) {
max_island = max(max_island, depth_first_search(matrix, i, j));
}
}
return max_island
}
Now we may have scenarios where instead of the classic up, down, left, right search options we have more complex operators such as in leetcode 282. Where we are given a String of numbers and a target number and can introduce binary operators which result in the expression resolving to the target number. The goal is to find all such expressions
example instance;
"332" 8
example solution;
3+3+2
example code;
class Solver {
private:
vector<string> ans;
int target;
string number;
void dfs(string path, int idx,
long long curr, long long prev) {
if(idx == num.size()) {
if(curr == target)
ans.push_back(path);
return;
}
for(int i = idx; i < num.size(); i++) {
if(i != idx && num[idx] == '0')
break;
string snumber = num.substr(idx, i - idx+1)
long long number = stoll(snumber);
//initially we have no choice but to take the number
if(idx == 0) {
dfs(path+snumber, i+1, number, number);
} else {
dfs(path+"+"+snumber, i+1, curr+number, number);
dfs(path+"-"+snumber, i+1, curr-number, -number);
// during the scenario we multiply we have to remove the
// the previous value from our running sum
dfs(path+"*"+snumber, i+1, curr-prev+(prev*number), prev * number);
}
}
}
public:
vector<string> getExpressions(string num, int target) {
this->target = target;
this->num = num;
dfs("", 0,0,0);
return ans;
}
}
🔧 Subroutines: Interview Problem Survey
📈 57.86 Punkte
🔧 Programmierung
🔧 Subroutines in c'
📈 34.71 Punkte
🔧 Programmierung
🔧 Optimal Substructure: Interview Problem Survey
📈 23.15 Punkte
🔧 Programmierung
🔧 Trees: Interview Problem Survey
📈 23.15 Punkte
🔧 Programmierung
🔧 Search Space: Interview Problem Survey
📈 23.15 Punkte
🔧 Programmierung