Data Structure Problem
Problem 3-2. Catering Challenge App Bonatite is catering for pavilion festivities at MIT. They know the total amount of food they will bring, and have a list of all the students who are attending, but they aren't sure how much food to portion for each student. So they reach out to some contacts at the dining halls, who report back relative amounts of what students eat. For instance, it might be observed that student A eats 1.5 as much as student B. No one keeps record of specific quantities of food eaten; only ratios between how much different students eat are observed. App Bonatite wants to know when they will have enough information to set up all the food for the pavilion festivities, or at least be able to quickly report how much information they currently have. More formally: suppose we have some student s. Let f(s) denote the amount of food s should get (assume some consistent unit of food throughout this problem). Devise a data structure which can handle the following operations. Update(S1, S2,x): Given two students S and s2 such that f($1/f (S2) = x, update the data structure with this knowledge. GetRatio(S1, S2): Given two students si and S2, return their relative food ratio f(si)/f or "insufficient information" if this information is not yet known. SetupFood(s, f): Given a students, and the amount of food f they eat, report whether or not there is sufficient information to set up all the food. (In particular, if App Bonatite knows the ratios between all students, then they can set up all the food). Design and describe a data structure that can handle the Update, GetRatio and Setup Food operations in amortized O(a(n)) time. Problem 3-2. Catering Challenge App Bonatite is catering for pavilion festivities at MIT. They know the total amount of food they will bring, and have a list of all the students who are attending, but they aren't sure how much food to portion for each student. So they reach out to some contacts at the dining halls, who report back relative amounts of what students eat. For instance, it might be observed that student A eats 1.5 as much as student B. No one keeps record of specific quantities of food eaten; only ratios between how much different students eat are observed. App Bonatite wants to know when they will have enough information to set up all the food for the pavilion festivities, or at least be able to quickly report how much information they currently have. More formally: suppose we have some student s. Let f(s) denote the amount of food s should get (assume some consistent unit of food throughout this problem). Devise a data structure which can handle the following operations. Update(S1, S2,x): Given two students S and s2 such that f($1/f (S2) = x, update the data structure with this knowledge. GetRatio(S1, S2): Given two students si and S2, return their relative food ratio f(si)/f or "insufficient information" if this information is not yet known. SetupFood(s, f): Given a students, and the amount of food f they eat, report whether or not there is sufficient information to set up all the food. (In particular, if App Bonatite knows the ratios between all students, then they can set up all the food). Design and describe a data structure that can handle the Update, GetRatio and Setup Food operations in amortized O(a(n)) time
