Johnb
BAN USER 0of 0 votes
AnswersYou have just earned $500 voucher to spend at any restaurant. However,
since you are a programmer and a foodie you want to maximize how you
allocate your money.
Attached is CSV that has a list of:
Beverages
Appetizers
Entrees
Desserts
Restaurants
The CSV file looks something like
Beverage Name,Beverage Cost,Beverage Value,Appetizer Name,Appetizer Cost,Appetizer Value,Entrée Name,Entrée Cost,Entrée Value,Desert Name,Desert Cost,Desert Value,Restaurant Name,Restaurant Drink Cost,Restaurant Value
7up, $92.00 ,32,Fresh Rolls, $82.00 ,30,Fried Rice, $78.00 ,29,Vanilla Ice Cream, $76.00 ,13,Applebee's, $43.00 ,19
Sprite, $89.00 ,24,Spring Rolls, $54.00 ,18,PB & J, $49.00 ,29,chocolate cake, $50.00 ,25,Arby's, $26.00 ,5
Next to each item there is a cost and a perceived value.
Your job is to construct a meal under your budget of $500 that includes:
1 Beverage
3 Appetizers
2 Entrees
1 Dessert
1 Flex Option (This can be an Appetizer, Entree, or Desert)
1 Restaurant
1. Please list the 25 Combinations with the highest perceived value
given your budget
2. Please list the 25 Combinations with the lowest perceived value
given your budget.
Make sure your program assumes that the number of items in each
category is N
The problem I am having is using the knapsack algorithm in this case, especially with item constraints. The problem seems to be poorly written.public static void main(String[] args) throws IOException { File file = new File("Menu.csv"); List<String> lines = Files.readAllLines(file.toPath(), StandardCharsets.UTF_8); List<Beverage> beverages = new ArrayList<>(); List<Appetizer> appetizers = new ArrayList<>(); List<Entree> entrees = new ArrayList<>(); List<Dessert> desserts = new ArrayList<>(); List<RestaurantDrink> restaurantDrinks = new ArrayList<>(); boolean firstLine = true; for (String line : lines) { if (firstLine) { firstLine = false; continue; //don't care about first line } String[] array = line.split(","); int j = 0; Beverage b = new Beverage(); Appetizer app = new Appetizer(); Entree e = new Entree(); Dessert d = new Dessert(); RestaurantDrink rd = new RestaurantDrink(); for (String a : array) { switch (j) { case 0: if (!a.equals("")) //nothing { b.name = a; } break; case 1: if (!a.equals("")) //nothing { b.cost = Double.parseDouble(a.replace("$", "")); } break; case 2: if (!a.equals("")) //nothing { b.perceivedValue = Integer.parseInt(a); beverages.add(b); } break; case 3: app.name = a; break; case 4: app.cost = Double.parseDouble(a.replace("$", "")); break; case 5: app.perceivedValue = Integer.parseInt(a); appetizers.add(app); break; case 6: e.name = a; break; case 7: e.cost = Double.parseDouble(a.replace("$", "")); break; case 8: e.perceivedValue = Integer.parseInt(a); entrees.add(e); break; case 9: d.name = a; break; case 10: if (a.equals("")) //free dessert { d.cost = 0.00; } else { d.cost = Double.parseDouble(a.replace("$", "")); } break; case 11: if (a.equals("")) //free dessert { d.perceivedValue = 0; } else { d.perceivedValue = Integer.parseInt(a); } desserts.add(d); break; case 12: rd.name = a; break; case 13: if (a.equals("")) //free restaurant drink { rd.cost = 0.00; } else { rd.cost = Double.parseDouble(a.replace("$", "")); } break; case 14: if (a.equals("")) //free dessert { rd.perceivedValue = 0; } else { rd.perceivedValue = Integer.parseInt(a); } restaurantDrinks.add(rd); break; } j++; } j = 0; } }
is all I got. I'm just having trouble with the knapsack portion.
 Johnb in United States Report Duplicate  Flag  PURGE
Hired.com None None Algorithm  0of 0 votes
AnswerGiven a string array and a pattern, find the number of occurrences
i.e. givenint[] a = new int[]{12, 789, 567, 1, 2};
Find out how many times a pattern like 12789 occurs. You can do "12" and "789" one time and also "1" "2" and "789" to make the pattern as well.
 Johnb in United States Report Duplicate  Flag  PURGE
Advent Associate Algorithm  3of 3 votes
AnswersHaving trouble with this array pair difference problem (NOT array pair sum) because of a certain edge case.
Example is: k = 4 a = [ 1, 1, 5, 6, 9, 16, 27] output: 3 (Due to 2x [1, 5], and [5, 9])
So, find the difference that equals to k. I used this code in my interview but realized it was wrong hours later unfortunately. It only gives 2.public static int arrayPairDifference(int[] a, int k) { HashMap<Integer, Integer> hashMap = new HashMap<>(); int count = 0; for (int i = 0; i < a.length; i++) { if (hashMap.containsValue(a[i]  k)) { count++; } hashMap.put(i, a[i]); } return count; }
How to account for the edge case of the 2x [1, 5] ?
 Johnb in United States Report Duplicate  Flag  PURGE
Algorithm Arrays Hash Table
public static int lastIndexDuplicateNumber(int[] input) {
if (input == null) {
return 1;
}
int prev = input[0];
int lastIndex = 1;
for (int i = 1; i < input.length; i++) {
int num = input[i];
if (prev == num) {
//duplicate number
lastIndex = i;
}
prev = num;
}
return lastIndex;
}

Johnb
January 12, 2018 public static int[] arrayPairSumIndices(int[] a, int k)
{
HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
for (int i = 0; i < a.length; i++)
{
if (hashMap.containsKey(k  a[i]))
{
return new int[]{hashMap.get(k  a[i]), i};
}
hashMap.put(a[i], i);
}
return null;
}
I'm pretty sure this is the best. O(n) time complexity and O(n) space. This returns the indices at which the two values are at.
 Johnb July 26, 2014/*
Problem: Return an array of strings that have repeated characters together
*/
public static String[] findConsecutiveCharacters(String[] arr)
{
ArrayList<String> arrayList = new ArrayList<>();
for (int i = 0; i < arr.length; i++)
{
String s = arr[i];
for (int j = 0; j < s.length()  1; j++) {
if (s.charAt(j + 1) == s.charAt(j)) {
arrayList.add(arr[i]);
}
}
}
return arrayList.toArray(new String[arrayList.size()]);
}
Similar solution to another poster here but I used ArrayList append so there aren't so many nulls in the final result array. This solution has a similar algorithm to what appears in Cracking the Coding Interview on Problem 1.5 Encode String.
 Johnb July 25, 2014The problem only required you to find how many pairs there were (i.e. a count) so no need to print out pairs :)
Some people are being rough on here on my question. It's not so difficult I think as I already got an O(2n) solution which is fine for interview purposes.
Oh, I figured out how to do it in two passes, but i'm still wondering if you can do it with only one.
public static int arrayPairDifference(int[] a, int k)
{
HashMap<Integer, Integer> hashMap = new HashMap<>();
int count = 0;
for (int i = 0; i < a.length; i++)
{
hashMap.put(i, a[i]);
}
for (int j = 0; j < a.length; j++)
{
if (hashMap.containsValue(a[j] + k))
{
count++;
}
}
return count;
}

Johnb
March 12, 2014 Open Chat in New Window
The problem doesn't make much sense unfortunately.
 Johnb January 16, 2018