Python
Building Houses
The text of the exercise is the following: A builder is looking to build a row of N houses that can be of K different colours. He has a goal of minimizing cost while ensuring that no two neighbouring houses are not of the same colour. Given an N by K matrix where the nth row and kth column represents the cost to build the nth house with kth colour, return the minimum cost which achieves this goal. Before solving the exercise, we can ask few questions to specify few aspects that might not be clear: Can an house cost 0? No. Can N > K or N < K ? Yes. My solution It is clear that finding the minimum iteratively for each house can return a local minimal solution but we are interested in the global minima. Python C Java import math N = 6 K = 4 cost_matrix = [ [1 , 20, 34, 20], [40, 10, 15, 30], [50, 1, 20, 40], [70, 80, 30, 1 ], [1 , 60, 30, 40], [70, 50, 1 , 20] ] def find_house(row, col, tot, min_tot): if row < N: tot += cost_matrix[row][col] for c in range(K): if c != col: min_tot = find_house(row+1, c, tot, min_tot) else: if min_tot > tot: min_tot = tot return min_tot def main(): print ("Minimum value found:", find_house(0,0,0, math.inf)) #include<stdio.h> #include<limits.h> #define K 4 #define N 6 int cost_matrix[N][K] = { {1 , 20, 34, 20}, {40, 10, 15, 30}, {50, 1, 20, 40}, {70, 80, 30, 1 }, {1 , 60, 30, 40}, {70, 50, 1 , 20} }; int find_house(int row, int col, int tot, int min_tot) { if (row < N) { tot += cost_matrix[row][col]; for (int c=0; c<K; c++) { if (c != col) min_tot = find_house(row+1,c, tot, min_tot); } } else { if (min_tot > tot) min_tot = tot; } return min_tot; } int main() { printf("Minimal cost: %d\n", find_house(0, 0, 0, INT_MAX)); return 0; } public class BuildHouse { static int N=6; static int K=4; static int cost_matrix[][] = { {1 , 20, 34, 20}, {40, 10, 15, 30}, {50, 1, 20, 40}, {70, 80, 30, 1 }, {1 , 60, 30, 40}, {70, 50, 1 , 20} }; public static void main(String[] args) { System.out.println("Minimum value found: "+ findHouse(0,0,0,Integer.MAX_VALUE)); } static int findHouse(int row, int col, int tot, int min_tot) { if (row < N) { tot += cost_matrix[row][col]; for (int c=0; c<K; c++) { if (c != col) min_tot = findHouse(row+1, c, tot, min_tot); } } else { if (min_tot > tot) min_tot = tot; } return min_tot; } } Code Explanation The function find_house is a recursive function that takes the row, col, tot and min_tot as input parameters. The function transform the matrix into a tree and perform a kind of “depth-first” exploration returning the minimum of the total found. row represents the row of the house. col represents column of the house. tot represents the total up to the reached node. min_tot represents the minimum of the cost found up to that moment The recursion stops when all the nodes have been explored. Time complexity: \( O(N^K) \) Space complexity: \( O(N^K) \)
Longest Palindromic Substring
The text of the exercise is the following: Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Example 1: Input: “babad” Output: “bab” Note: “aba” is also a valid answer. Example 2: Input: “cbbd” Output: “bb” My solution Python C Java N = 4 solutions = [] def staircase(n, result): if n == 1: solutions.append(result+","+"1") return if n == 0: solutions.append(result) return staircase(n-2, result + ",2") staircase(n-1, result + ",1") if __name__ == "__main__": staircase(N,"") print("\n".join([s[1:] for s in solutions])) #include <stdio.h> #include <stdlib.h> #include <string.h> char** solutions; int N = 4; int n_solution=0; void staircase(int n, char *result); char* strAdd(char* begin, char* end); void addSolution(char* solution); void staircase(int n, char *result) { char *str1,*str2; if (n == 1) { str1 = strAdd(result, ",1"); addSolution(str1); free((void*)str1); return; } else if (n == 0) { addSolution(result); return; } str1 = strAdd(result, ",1"); str2 = strAdd(result, ",2"); staircase(n-1, str1); staircase(n-2, str2); free((void*)str1); free((void*)str2); } char* strAdd(char* begin, char* end) { char* str; str = (char*) malloc(sizeof(char) * (strlen(begin)+ strlen(end) + 1)); if (str == NULL) exit(1); str = strcpy(str, begin); str = strcat(str, end); return str; } void addSolution(char* solution) { char *str = (char*) malloc(sizeof(char) * strlen(solution) + 1); if (str == NULL) exit(1); n_solution++; solutions = (char**) realloc(solutions, sizeof(char*) * n_solution); if (solutions == NULL) { free(solutions); exit(1); } str = strcpy(str, solution); solutions[n_solution-1] = str; return; } int main(int argc, char* argv[]) { int i; solutions = solutions=malloc(sizeof(char**)); if (solutions == NULL) exit(1); staircase(N,""); for(i=0; i< n_solution; i++ ) { printf("%s\n", solutions[i]+1); free((void*)solutions[i]); } free(solutions); return 0; } import java.util.ArrayList; import java.util.Iterator; import java.util.List; public class NStepStaircase { static List<String> solutions = new ArrayList<String>(); public static void main(String[] args) { int N=4; staircase(N, new StringBuffer()); Iterator<String> iter = NStepStaircase.solutions.iterator(); String str; while(iter.hasNext()) { str = iter.next(); System.out.println(str.substring(1, str.length())); } } static void staircase(int n, StringBuffer result) { if (n == 1) { NStepStaircase.solutions.add(result.append(",1").toString()); return; } else if (n == 0) { solutions.add(result.toString()); return; } staircase(n-1, new StringBuffer(result).append(",1")); staircase(n-2, new StringBuffer(result).append(",2")); } } Code Explanation The function `staircase` is a recursive function that takes the `n` and `result` as input parameters. * `n` represents the number of stairs that remains to be climbed. * `result` represents the steps covered so far. The recursion stops when there are no more steps to climb or when there are only 1 stair left. **Time complexity**: \\( O(2^N) \\) **Space complexity**: \\( O(2^N) \\) Generalized solution Python C Java N = 9 solutions = [] STEPS = [1, 3, 5] def staircase(n, result): if n == 0: solutions.append(result) return for s in STEPS: if n-s >= 0: staircase(n-s, result + "," + str(s)) if __name__ == "__main__": staircase(N,"") print("\n".join([s[1:] for s in solutions])) #include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> char** solutions; int N = 4; int n_solution=0; int STEPS[] = {1,2,3}; void staircase(int n, char *result); char* strAdd(char* begin, int number); void addSolution(char* solution); void staircase(int n, char *result) { char *str; if (n == 0) { addSolution(result); return; } for (int i=0; i<sizeof(STEPS)/sizeof(STEPS[0]); i++) { if ( n-STEPS[i] >= 0) { str = strAdd(result, STEPS[i]); staircase(n-STEPS[i], str); free((void*)str); } } } char* strAdd(char* begin, int number) { char* str; str = (char*) malloc(sizeof(char) * (strlen(begin)+ floor(log10(number))+1 +1 + 1)); //1 for '\0', 1 for ',', 1 for if (str == NULL) exit(1); sprintf(str, "%s,%d", begin, number); return str; } void addSolution(char* solution) { char *str = (char*) malloc(sizeof(char) * strlen(solution) + 1); if (str == NULL) exit(1); n_solution++; solutions = (char**) realloc(solutions, sizeof(char*) * n_solution); if (solutions == NULL) { free(solutions); exit(1); } str = strcpy(str, solution); solutions[n_solution-1] = str; return; } int main(int argc, char* argv[]) { int i; solutions = solutions=malloc(sizeof(char**)); if (solutions == NULL) exit(1); staircase(N,""); for(i=0; i< n_solution; i++ ) { printf("%s\n", solutions[i]+1); free((void*)solutions[i]); } free(solutions); return 0; } import java.util.ArrayList; import java.util.Iterator; import java.util.List; import java.util.Arrays; public class NStepStaircaseGeneral { static List<String> solutions = new ArrayList<String> (); static List<Integer> STEPS = new ArrayList<Integer>(Arrays.asList(1,2)); public static void main(String[] args) { int N=4; staircase(N, new StringBuffer()); Iterator<String> iter = NStepStaircaseGeneral.solutions.iterator(); String str; while(iter.hasNext()) { str = iter.next(); System.out.println(str.substring(1, str.length())); } } static void staircase(int n, StringBuffer result) { Iterator<Integer> iter = NStepStaircaseGeneral.STEPS.iterator(); Integer step; if (n == 0) { solutions.add(result.toString()); return; } while (iter.hasNext()) { step = iter.next(); if ((n - step) >= 0) { staircase(n-step, new StringBuffer(result).append(","+step)); } } } } **Time complexity**: \\( O(k^N) \\) \\(;\\) \\(k = | STEPS | \\) **Space complexity**: \\( O(k^N) \\) \\(;\\) \\(k = | STEPS | \\) --
N Steps Staircase
The text of the exercise is the following: There’s a staircase with N steps, and you can climb 1 or 2 steps at a time. Given N, write a function that prints all the unique ways you can climb the staircase. The order of the steps matters. For example, if N is 4, then there are 5 unique ways: 1, 1, 1, 1 2, 1, 1 1, 2, 1 1, 1, 2 2, 2 What if, instead of being able to climb 1 or 2 steps at a time, you could climb any number from a set of positive integers X? For example, if X = {1, 3, 5}, you could climb 1, 3, or 5 steps at a time. Generalize your function to take in X. Before solving the exercise, we can ask few questions to specify few aspects that might not be clear. Are the steps going to be always positive number? Yes. In the general case, is 1 going to be always in the possible steps? No. My solution Python C Java N = 4 solutions = [] def staircase(n, result): if n == 1: solutions.append(result+","+"1") return if n == 0: solutions.append(result) return staircase(n-2, result + ",2") staircase(n-1, result + ",1") if __name__ == "__main__": staircase(N,"") print("\n".join([s[1:] for s in solutions])) #include <stdio.h> #include <stdlib.h> #include <string.h> char** solutions; int N = 4; int n_solution=0; void staircase(int n, char *result); char* strAdd(char* begin, char* end); void addSolution(char* solution); void staircase(int n, char *result) { char *str1,*str2; if (n == 1) { str1 = strAdd(result, ",1"); addSolution(str1); free((void*)str1); return; } else if (n == 0) { addSolution(result); return; } str1 = strAdd(result, ",1"); str2 = strAdd(result, ",2"); staircase(n-1, str1); staircase(n-2, str2); free((void*)str1); free((void*)str2); } char* strAdd(char* begin, char* end) { char* str; str = (char*) malloc(sizeof(char) * (strlen(begin)+ strlen(end) + 1)); if (str == NULL) exit(1); str = strcpy(str, begin); str = strcat(str, end); return str; } void addSolution(char* solution) { char *str = (char*) malloc(sizeof(char) * strlen(solution) + 1); if (str == NULL) exit(1); n_solution++; solutions = (char**) realloc(solutions, sizeof(char*) * n_solution); if (solutions == NULL) { free(solutions); exit(1); } str = strcpy(str, solution); solutions[n_solution-1] = str; return; } int main(int argc, char* argv[]) { int i; solutions = solutions=malloc(sizeof(char**)); if (solutions == NULL) exit(1); staircase(N,""); for(i=0; i< n_solution; i++ ) { printf("%s\n", solutions[i]+1); free((void*)solutions[i]); } free(solutions); return 0; } import java.util.ArrayList; import java.util.Iterator; import java.util.List; public class NStepStaircase { static List<String> solutions = new ArrayList<String>(); public static void main(String[] args) { int N=4; staircase(N, new StringBuffer()); Iterator<String> iter = NStepStaircase.solutions.iterator(); String str; while(iter.hasNext()) { str = iter.next(); System.out.println(str.substring(1, str.length())); } } static void staircase(int n, StringBuffer result) { if (n == 1) { NStepStaircase.solutions.add(result.append(",1").toString()); return; } else if (n == 0) { solutions.add(result.toString()); return; } staircase(n-1, new StringBuffer(result).append(",1")); staircase(n-2, new StringBuffer(result).append(",2")); } } Code Explanation The function staircase is a recursive function that takes the n and result as input parameters. n represents the number of stairs that remains to be climbed. result represents the steps covered so far. The recursion stops when there are no more steps to climb or when there are only 1 stair left. Time complexity: \( O(2^N) \) Space complexity: \( O(2^N) \) Generalized solution Python C Java N = 9 solutions = [] STEPS = [1, 3, 5] def staircase(n, result): if n == 0: solutions.append(result) return for s in STEPS: if n-s >= 0: staircase(n-s, result + "," + str(s)) if __name__ == "__main__": staircase(N,"") print("\n".join([s[1:] for s in solutions])) #include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> char** solutions; int N = 4; int n_solution=0; int STEPS[] = {1,2,3}; void staircase(int n, char *result); char* strAdd(char* begin, int number); void addSolution(char* solution); void staircase(int n, char *result) { char *str; if (n == 0) { addSolution(result); return; } for (int i=0; i<sizeof(STEPS)/sizeof(STEPS[0]); i++) { if ( n-STEPS[i] >= 0) { str = strAdd(result, STEPS[i]); staircase(n-STEPS[i], str); free((void*)str); } } } char* strAdd(char* begin, int number) { char* str; str = (char*) malloc(sizeof(char) * (strlen(begin)+ floor(log10(number))+1 +1 + 1)); //1 for '\0', 1 for ',', 1 for if (str == NULL) exit(1); sprintf(str, "%s,%d", begin, number); return str; } void addSolution(char* solution) { char *str = (char*) malloc(sizeof(char) * strlen(solution) + 1); if (str == NULL) exit(1); n_solution++; solutions = (char**) realloc(solutions, sizeof(char*) * n_solution); if (solutions == NULL) { free(solutions); exit(1); } str = strcpy(str, solution); solutions[n_solution-1] = str; return; } int main(int argc, char* argv[]) { int i; solutions = solutions=malloc(sizeof(char**)); if (solutions == NULL) exit(1); staircase(N,""); for(i=0; i< n_solution; i++ ) { printf("%s\n", solutions[i]+1); free((void*)solutions[i]); } free(solutions); return 0; } import java.util.ArrayList; import java.util.Iterator; import java.util.List; import java.util.Arrays; public class NStepStaircaseGeneral { static List<String> solutions = new ArrayList<String> (); static List<Integer> STEPS = new ArrayList<Integer>(Arrays.asList(1,2)); public static void main(String[] args) { int N=4; staircase(N, new StringBuffer()); Iterator<String> iter = NStepStaircaseGeneral.solutions.iterator(); String str; while(iter.hasNext()) { str = iter.next(); System.out.println(str.substring(1, str.length())); } } static void staircase(int n, StringBuffer result) { Iterator<Integer> iter = NStepStaircaseGeneral.STEPS.iterator(); Integer step; if (n == 0) { solutions.add(result.toString()); return; } while (iter.hasNext()) { step = iter.next(); if ((n - step) >= 0) { staircase(n-step, new StringBuffer(result).append(","+step)); } } } } Time complexity: \( O(k^N) \) \(;\) \(k = | STEPS | \) Space complexity: \( O(k^N) \) \(;\) \(k = | STEPS | \)
