Answers & Hints

12,0.5,"%.f"
2
1
1
In this value set, addition wraps after 4 (i.e. mod 5) so 6 becomes 1.
3
Since int
requires 4 bytes, the value is
stored in a block that occupies addresses 400, 401, 402, and 403.
1
22
Trace it: m is 18%11 (which is 7) plus 15.
6
Reverse engineer it: if the output is 9 then it was obtained by computing 3am so 15m=9.
2
One object with state 2 and another with state 5. The first statement creates a new object with state 2. The second does not create a new object. The third creates a new object with state 5. The fourth creates a new object with state 2. Hence, the fragment creates 3 objects in total but only 2 of them have distinct states.
9
12
Reverse engineer it: If m were equal to EDGE the return would have been 203=17, which is wrong. And if m were less than EDGE the return would have been m/EDGE=0, which is also wrong. Hence, m must be greater than EDGE and the return is m+3=15, so m=12.
2
Trace it:
c  b 

2  0 
1  1 
0  2 
1  3 
2  4 
5
s==null
means we have a reference and no object.
Hence (1) is wrong because if s has not been declared than there
is neither an object nor a reference. (2) and (4) are wrong because
they describe an object with state "" so there is an object.
(3) is wrong because it describes a string with state "null" so
there is an object.
2
Reverse engineer it: if the return is "d" then it must have been extracted from the given string at position p=18. The length of the given string is 20, so we have 18 = 20  m.
2
At minimum, y must have one digit followed by one letter (X, Y, or Z).
hr hs hhr hhs
PPACP
The first replacement leads to "3PAC3". The second replaces 3 with P.
5
Reverse engineer it: the toString returns "[x,y,z...]", where x,y,z are the elements of the set in sorted order. The index/substring extraction returns x. Since the return is 5 then m must have been 5.
3
2
The method returns the largest or the smallest of the two passed integers depending on whether the passed boolean is false or true, respectively.
The shown implementation is incorrect if the list has three or more elements because
the positions are shifted after each removal, so some elements will not be removed.
For example, if the list is [a,b,c] then remove(0) in the first loop iteration makes
it [b,c], and remove(1) in the second (and last) iteration makes it [b], which is incorrect.
OR
The shown implementation is incorrect if the list has four or more elements because
the list size shrinks after each removal whereas n is fixed, so we will refer to a
nonexisting element. For example, if the list has 4 elements then remove(2) in the 3rd
iteration would throw an exception because, by then, the list has only two elements at
positions 0 and 1 (i.e. position 2 doesn't exists).
2
The loop iterates N times. Each iteration involves O(1) operations,
so the overall is O(N). Note that had the list been an instance of LinkedList
then the answer would have been 4 (i.e. O(N^{2})) because get
is O(N).
4
Two nested loops each iterating N times, hence N^{2}. The operations in the body are all Nindependent; i.e. O(1).
The shown implementation is incorrect because it bases the return on the uniqueness of the last value of the map only rather than all the values. For example, if the last value is unique then the return would be true even if all the other values are equal.
public static int sumDiv11(int a, int b) { int result = 1; for (int n = a; n <= b && result == 1; n++) { int sum = 0; for (int m = n; m > 0; m /= 10) { sum += m % 10; } if (sum % 11 == 0) result = n; } return result; }
public static double specialSum(double x, double e) { double sum = 0; int n = 0; double term = 1.0; while (term >= e) { sum += term; n++; term = Math.pow(x, n) / Math.pow(2, 2*n); } return sum; }
public static double multiply(String query) { double result; String regex = "(\\d+)\\s*[\\*x]\\s*(\\d+)"; Pattern pattern = Pattern.compile(regex); Matcher matcher = pattern.matcher(query); if (matcher.find()) { int a = Integer.parseInt(matcher.group(1)); int b = Integer.parseInt(matcher.group(2)); result = a * b; } else { result = Double.NaN; } return result; }
public static int vowel(String s) { final String VOWELS = "aeiouAEIOU"; int count = 0; for (int i = 0; i < s.length(); i++) { if (VOWELS.indexOf(s.substring(i, i+1)) != 1) count++; } return count; }
public static Set<Integer> negativeSubset(Set<Integer> set) { Set<Integer> result = new TreeSet<Integer>(); for (int x : set) { if (x < 0) result.add(x); } if (result.size() == 0) result = null; return result; }
public static Map<Integer,Integer> lengthStat(List<String> list) { Map<Integer,Integer> result = new TreeMap<Integer,Integer>(); for (String word : list) { int len = word.length(); if (!result.containsKey(len)) result.put(len, 1); else result.put(len, 1 + result.get(len)); } return result; }
public static List<String> aboveAverage(Map<String, Integer> map) { List<String> result = new ArrayList<String>(); int sum = 0; for (String k : map.keySet()) { sum += map.get(k); } double average = sum / (double) map.size(); for (String k : map.keySet()) { int mark = map.get(k); if (mark > average) result.add(k); } return result; }
public static void sortByLength(List<String> list) { Map<Integer,String> map = new TreeMap<Integer,String>(); for (String s : list) map.put(s.length(), s); list.clear(); for (int i : map.keySet()) list.add(map.get(i)); }
public static int largestEven(Set<Integer> set) { int result = 0; for (int x : set) { if (x % 2 == 0 && x > result) result = x; } return result; }
public static List<String> oldest(Map<String, Integer> map) { List<String> result = new ArrayList<String>(); int maxAge = 0; for (String k : map.keySet()) { int age = map.get(k); if (age > maxAge) maxAge = age; } for (String k : map.keySet()) { int age = map.get(k); if (age == maxAge) result.add(k); } return result; }
public static Set<Integer> pair(Set<Integer> set, int sum) { Set<Integer> result = new TreeSet<Integer>(); for (int a : set) { for (int b : set) { if (a != b && a + b == sum && result.size() == 0) { result.add(a); result.add(b); } } } return result; }
In order to find out if the given path is indeed the shortest, we compute its length (which is only O(N)) but then we need to compare this length to the lengths of all other possible paths, which are N! in number. Hence, our verification process involves N! iterations, which is not in P.
If P=NP then the effort needed to verify is placed at the same level as the effort needed to solve, which is bothersome because verification is normally thought of as mechanical or straightforward whereas solving is normally associated with innovation and ingenuity. For example, we don't feel that "recognising good music" is of the same calibre as "composing good music". Similarly, conducting experiments to verify the predictions of (say) the theory of relativity is not equated with the act of inventing the theory.
The first and the second and the fourth do increment x. The third adds 0 to it so it doesn't increment it. The fifth is a syntax error (the RHS is double while the LHS is int).
Both approaches correctly perform the conversion but the second is the preferred bestpractice because it uses indirection (see the CS Trail of this Chapter). The advantage here is clarity through selfdocumenting code. If the exchange rate is to be changed, the second approach makes the change easy especially if this code is burried in a big application. The first approaches does not indicate whether the magic number 1.33 is an exchange rate or something else.
The input is the values of w and h. The output is the value of result.