Exercise

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) \)

Read more

K-Anonymisation on Streaming Data

The text of the exercise is the following: Imagine a stream of records arriving at a rate of one per second. For simplicity the records contain just one variable, a double. The goal is to generalise this variable to achieve a k-anonymity of 5 i.e., no generalised unique output value can appear fewer than 5 times. The effectiveness of the solution can be measured by its impact on data distortion and latency, with the aim of minimising both: Distortion is a measure of how close the generalised values are to the original ones. Latency is a measure of delay between ingesting the input record and publishing the generalised value. The solution should implement the StreamingKFilter interface that accepts InputRecords and transforms them into generalised OutputRecords. Method calls to the StreamingKFilter are strictly single threaded; as such the solution is expected to be single-threaded only. The code of the exercise and the tests are here. Under /src/test you will find two test suites for the solution. In order to run them, instantiate your filter in the​ CandidateFilterFactory.getStreamingKFilter()​ method. The project source code (solution and tests) can be built using Maven. Additional info: K-Anonymity A release of data is said to have the k-anonymity property if the information for each record contained in the release cannot be distinguished from at least k - 1 records whose information also appear in the release. My solution The StreamingKFilter interface contains two methods: void processNewRecord(InputRecord input); Collection<OutputRecord> returnPublishableRecords(); I implemented the processNewRecord as: @Override public void processNewRecord(InputRecord input) { Integer firstElementTime, lastElementTime, elapsedTime; this.inputBuffer.add(input); // calculating elapsed time firstElementTime = this.inputBuffer.get(0).getTime(); lastElementTime = this.inputBuffer.get(this.inputBuffer.size()-1).getTime(); elapsedTime = firstElementTime - lastElementTime; // update the current time this.currentTime = input.getTime(); // if enough records are received then process the block if (this.inputBuffer.size() >= this.blockSize) generateOutputRecords(); // if enough time is elapsed then process the block if (elapsedTime >= this.maxWaitTime && this.inputBuffer.size() >= this.K) { generateOutputRecords(); } } This function will trigger the generateOutputRecords (explained later on) in two circumstances: when there is enough input records received, controlled by the variable blockSize, in line 16. when enough time has passed, controlled by the variable maxWaitTime (and the minimum number of records to obtain k-anonymity has been received), in line 20. The input records are stored in the inputBuffer, in line 5. The function returnPublishableRecords is implemented as: @Override public Collection<OutputRecord> returnPublishableRecords() { Collection<OutputRecord > outputs = this.outputBuffer; this.outputBuffer = new ArrayList<OutputRecord >(); return outputs; } This function returns the records stored in the outputBuffer, filled by the function generateOutputRecords. The main function generateOutputRecords is implemented as: private void generateOutputRecords() { int size; double distortion, anonymizedValue, distortion_min = Double.MAX_VALUE; this.inputBuffer.sort(Comparator.comparing(InputRecord::getRawValue)); while (this.inputBuffer.isEmpty() == false) { // initialize the variables used in the search distortion_min = Double.MAX_VALUE; size = this.K -1; do { // process 'size' number of records size += 1; // process 'size' number of objects, if the remaining are less than this.K then process them all if (size > (this.inputBuffer.size() - this.K) ) size = this.inputBuffer.size(); // compute the distortion and the anonymized value on the records anonymizedValue = getAnonValue (this.inputBuffer.subList(0, size)); distortion = getDistortion(this.inputBuffer.subList(0, size), anonymizedValue); // if the distortion is decreasing when adding records then keep adding elements // otherwise output them if (distortion_min > distortion) distortion_min = distortion; else break; } while(size < this.inputBuffer.size()); // add the records to the output buffer addOutputRecords(this.inputBuffer.subList(0, size), anonymizedValue); // continue to process the other records in the input buffer this.inputBuffer = this.inputBuffer.subList(size, this.inputBuffer.size()); } // Clear the input buffer this.inputBuffer = new ArrayList<InputRecord>(); } In line 5, the inputBuffer is sorted to place similar values together. In line 12-33, the inputBuffer is chunked in pieces to minimize the distortions of each individual piece. Each chunk includes at least K elements and one more element will included iteratively until the distortion doesn’t decrease anymore. When the distortion stop decreasing then the chunk is removed from the input buffer and the output records are generated with the addOutputRecords function. This process will continue until there are no more records in the inputBuffer. Line 18-19 will make sure that even the last chunk has at least k elements to keep the k-anonymity property. (In line 23, the distortion is computed with the same function used in the measures package.) Trade-off Between Distortion and Latency The variable blockSize can be used to control the distortion and latency. Increasing the variable blockSize will decrease the distortion and increase latency. Decreasing the variable blockSize will increase the distortion and decrease latency. The variable maxWaitTime will top the latency, if necessary. You can download my solution here.

Read more

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 | \\) --

Read more

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 | \)

Read more