Java Puzzles
Overview
Few puzzles in java, to test the fundamentals
Github: https://github.com/gitorko/project01
Puzzles
Puzzle: 1 (pass by value vs pass by ref)
What is the output of the program?
1package com.demo.basics.puzzle._001_passbyvalue;
2
3import org.junit.jupiter.api.Test;
4
5public class PassByPuzzle {
6
7 @Test
8 public void test() {
9 Employee emp = new Employee("Dan");
10 modify1(emp);
11 System.out.println(emp.name);
12 modify2(emp);
13 System.out.println(emp.name);
14 }
15
16 private void modify1(Employee emp) {
17 emp = new Employee("John");
18 }
19
20 private void modify2(Employee emp) {
21 emp.name = "Jack";
22 }
23
24 class Employee {
25 String name;
26
27 public Employee(String name) {
28 this.name = name;
29 }
30 }
31}
Solution
Java always does pass by value. In the case of reference they are still passed by value but since they point to same memory location they update the same object.
Puzzle: 2 (finally block)
What is the output of the program?
1package com.demo.basics.puzzle._002_exception;
2
3import org.junit.jupiter.api.Test;
4
5public class ExceptionPuzzle {
6
7 @Test
8 public void test() {
9 String name = getName();
10 System.out.println(name);
11 }
12
13 private String getName() {
14 try {
15 throw new Exception("ERROR");
16 } finally {
17 return "OK";
18 }
19 }
20}
Solution
The finally block can still return a value if exception is thrown.
Puzzle: 3 (static variable vs instance variable)
What is the output of the program?
1package com.demo.basics.puzzle._003_static;
2
3import org.junit.jupiter.api.Test;
4
5public class StaticPuzzle {
6
7 @Test
8 public void test() {
9 Employee employee1 = new Employee("Dan", "ABC");
10 Employee employee2 = new Employee("John", "DEF");
11 System.out.println(employee1.getName() + ", " + employee1.getCompany());
12 System.out.println(employee2.getName() + ", " + employee2.getCompany());
13 }
14
15}
16class Employee {
17 String name;
18 static String company;
19
20 public Employee(String name, String company) {
21 this.name = name;
22 Employee.company = company;
23 }
24
25 public String getName() {
26 return name;
27 }
28
29 public String getCompany() {
30 return company;
31 }
32
33}
Solution
The static variables are common to all instances, so instance variables should not be static.
Puzzle: 4 (equals & hashcode)
What is the output of the program?
1package com.demo.basics.puzzle._004_hashcode;
2
3import java.util.HashSet;
4import java.util.Set;
5
6import org.junit.jupiter.api.Test;
7
8public class ObjectPuzzle {
9
10 @Test
11 public void test() {
12 Set<Person> set = new HashSet<>();
13 Person p1 = new Person("Jack", 34);
14 Person p2 = new Person("Jack", 34);
15 set.add(p1);
16 set.add(p2);
17 System.out.println(set.size());
18 }
19
20 class Person {
21 public String name;
22 public Integer age;
23
24 public Person(String name, Integer age) {
25 this.name = name;
26 this.age = age;
27 }
28 }
29}
Solution
How 2 object are same is determined only if you override the equals and hashcode method. Set ensured that unique elements are stored but how does the set know that both these objects are same? That's why you need to override equals and hashcode. As a follow up you can read why hashcode and equals method need to be overridden together. What happens if you dont do them together?
Puzzle: 5 (Immutable class)
Is the class immutable?
1package com.demo.basics.puzzle._005_immutable;
2
3import java.util.Date;
4import java.util.HashMap;
5import java.util.Map;
6
7import org.junit.jupiter.api.Test;
8
9public class ImmutablePuzzle {
10
11 @Test
12 public void test() {
13 Map<String, String> props = new HashMap<>();
14 props.put("city", "london");
15 Person p1 = new Person("Jack", 34, new Date(), props);
16 System.out.println(p1);
17 p1.getDob().setTime(123);
18 p1.getProps().put("city", "bangalore");
19 System.out.println(p1);
20 }
21
22 final class Person {
23 private final String name;
24 private final Integer age;
25 private final Date dob;
26 private final Map<String, String> props;
27
28 public Person(String name, Integer age, Date dob, Map<String, String> props) {
29 this.name = name;
30 this.age = age;
31 this.dob = dob;
32 this.props = props;
33 }
34
35 public String getName() {
36 return name;
37 }
38
39 public Integer getAge() {
40 return age;
41 }
42
43 public Date getDob() {
44 return dob;
45 }
46
47 public Map<String, String> getProps() {
48 return props;
49 }
50
51 @Override
52 public String toString() {
53 return "Person{" +
54 "name='" + name + '\'' +
55 ", age=" + age +
56 ", dob=" + dob +
57 ", props=" + props +
58 '}';
59 }
60 }
61}
Solution
Class is not immutable, have to clone both hashmap and date to avoid modification.
- Make class final to avoid extending it.
- Remove setter method
- Make variables final so that they can be init only via constructor.
- Defensive copy of any variables that return reference objects. Deep copy vs shallow copy difference is important here. Reflection can still break immutability.
Puzzle: 6 (string pool vs heap)
What is the output of the program?
1package com.demo.basics.puzzle._006_datatype;
2
3import org.junit.jupiter.api.Test;
4
5public class DataTypePuzzle {
6
7 @Test
8 public void test1() {
9 String name1 = "Jack";
10 String name2 = new String("Jack");
11 System.out.println(name1 == name2);
12 System.out.println(name2.equals(name1));
13 }
14
15 @Test
16 public void test2() {
17 long num1 = 5l;
18 Long num2 = Long.valueOf(5);
19 System.out.println(num1 == num2);
20 System.out.println(num2.equals(num1));
21 }
22
23 @Test
24 public void test3() {
25 String name1 = new String("Jack");
26 String name2 = name1.intern();
27 System.out.println(name1 == name2);
28 System.out.println(name2.equals(name1));
29 }
30
31}
Solution
The String pool holds the strings, using new String() creates the string in heap. The difference between == and .equals() where the first checks the address and the second checks the value. To move an element from heap to string pool we use intern. As a follow up to this, why we shouldn't store/use password as string in java instead we should store password as char array? Because string pool objects will remain in memory longer than heap objects. if you create a password in string the string pool will not GC it after the function is done. So the password can remain for a long time. If someone gets a heap dump they can look at the passwords. Hence better to store in char so that object is GC after it goes out of scope.
Puzzle: 7 (memory leak)
What is the output of the program?
1package com.demo.basics.puzzle._007_map;
2
3import java.util.HashMap;
4import java.util.Map;
5import java.util.Objects;
6
7import org.junit.jupiter.api.Test;
8
9public class MapPuzzle {
10
11 @Test
12 public void test() {
13 Map<Employee, Boolean> map = new HashMap<>();
14 Employee e1 = new Employee("Jack", 25);
15 map.put(e1, true);
16 e1.name = "Rose";
17 Employee e2 = new Employee("John", 28);
18 map.put(e2, true);
19
20 Employee john = new Employee("John", 28);
21 Employee jack = new Employee("Rose", 25);
22 Employee rose = new Employee("Jack", 25);
23
24 System.out.println(map.size());
25 System.out.println(map.get(john));
26 System.out.println(map.get(jack));
27 System.out.println(map.get(rose));
28 }
29
30 class Employee {
31 public String name;
32 public Integer age;
33
34 public Employee(String name, Integer age) {
35 this.name = name;
36 this.age = age;
37 }
38
39 @Override
40 public boolean equals(Object o) {
41 if (this == o) return true;
42 if (o == null || getClass() != o.getClass()) return false;
43 Employee employee = (Employee) o;
44 return name.equals(employee.name) && age.equals(employee.age);
45 }
46
47 @Override
48 public int hashCode() {
49 return Objects.hash(name, age);
50 }
51 }
52}
Solution
Java has automatic memory management in terms of garbage collection unlike c/c++, hence ideally it means that there should be no memory leak, logic being garbage collector always identifies the objects that are not used and garbage collected. The puzzle above is a clear example of a memory leak in Java. The key of a Map has to be immutable, this is one of the hard requirements for a map. If you see someone using an object as key without equals/hashcode you raise a red flag. If the object is not immutable and used as a key in map you raise a red flag.
Hashmap is a array with each node of array pointing to a linkedlist. Jack was put on the hashmap table, but the value was changed to Rose. Rose hashcode will never point to the bucket of Jack. Jack hashcode will point to the bucket where Rose is present but then when it reaches that node it will again check if objects are same, in this case its not, so it will return null. So you will never be able to get jack. This is an example of memory leak in java. If it happens for many elements then jvm will crash. Garbage collector cant clean it because its still part of the map, but no one can reach it.
Puzzle: 8 (ThreadLocal)
What is the output of the program?
1package com.demo.basics.puzzle._008_threadlocal;
2
3import java.text.ParseException;
4import java.text.SimpleDateFormat;
5import java.util.Arrays;
6import java.util.Date;
7import java.util.List;
8import java.util.concurrent.CountDownLatch;
9import java.util.concurrent.ExecutorService;
10import java.util.concurrent.Executors;
11
12import org.junit.jupiter.api.Test;
13
14public class ThreadPuzzle {
15
16 SimpleDateFormat df = new SimpleDateFormat("dd/MM/yyyy");
17
18 @Test
19 public void test() {
20 List<String> joinDates = Arrays.asList("01/01/2015",
21 "01/01/2016",
22 "01/01/2017",
23 "01/01/2018",
24 "01/01/2019"
25 );
26 CountDownLatch latch = new CountDownLatch(joinDates.size());
27 ExecutorService executor = Executors.newCachedThreadPool();
28 for (String doj : joinDates) {
29 executor.execute(() -> {
30 try {
31 Date dojDt = df.parse(doj);
32 System.out.println("Saving : " + dojDt);
33 } catch (ParseException e) {
34 //e.printStackTrace();
35 } finally {
36 latch.countDown();
37 }
38 });
39 }
40 try {
41 latch.await();
42 } catch (InterruptedException e) {
43 e.printStackTrace();
44 }
45 }
46}
Solution
The program will work sometimes and will fail sometimes. Reason is SimpleDateFormat is not thread safe. The same object is sent to all threads and even though it looks like they are using SimpleDateFormat to just parse, internally SimpleDateFormat does few operation that are not thread safe. So now you might think i will pass a new SimpleDateFormat to each thread. However this is a costly object that will increase memory. This is where ThreadLocal comes into picture, Threadlocal will keep a copy of the object specific to that thread.
What is the difference between copy of SimpleDateFormat vs using new SimpleDateFormat() each time? Copy objects will be == number of threads new objects will be > number of threads. So if you have 10K dates, you will end up creating 10k new objects if you do new() With ThreadLocal you will at max have 5 SimpleDateFormat objects if the thread pool is of size 5.
This is the advantage of using ThreadLocal.
Puzzle: 9 (AtomicLong vs LongAdder)
What is the output of the program?
1package com.demo.basics.puzzle._009_counter;
2
3import java.util.ArrayList;
4import java.util.List;
5import java.util.concurrent.Callable;
6import java.util.concurrent.ExecutorService;
7import java.util.concurrent.Executors;
8import java.util.concurrent.TimeUnit;
9
10import org.junit.jupiter.api.Test;
11
12public class CounterPuzzle {
13
14 @Test
15 public void test() throws InterruptedException {
16 Job job = new Job();
17 job.runJob();
18 System.out.println(job.counter);
19 }
20
21 class Job {
22 long counter = 0l;
23
24 public void runJob() throws InterruptedException {
25 ExecutorService executor = Executors.newCachedThreadPool();
26 List<Callable<Void>> tasks = new ArrayList<>();
27 for (int i = 0; i < 250; i++) {
28 tasks.add(() -> {
29 counter = counter + 1;
30 return null;
31 });
32 }
33 executor.invokeAll(tasks, 5, TimeUnit.SECONDS);
34 executor.shutdown();
35 }
36 }
37}
Solution
There are 2 problem in the code above. Each thread is updating counter without syncronization block/lock, so what value the thread read and what value it wrote back is not guaranteed. Your first thought might be to make the variable volatile so that copy of counter is kept in main memory and not thread memory. However if every thread is reading and writing at different times even volatile wont help. So you might think of putting a syncronization block but that will impact performance. So using a AtomicLong is a good approach here. It guarantees that the CAS (Compare and Swap) operation is atomic and hence counter will be correct. There is another hidden problem that is long + 1 is not a single operation. integer + 1 is a single operation, but long + 1 is not a single operation even within jvm. So this can lead to race condition. Long + 1 takes 2 operation in JVM to add. The AtomicLong solves the problem but again is not optimal as it can lead to contention when there are lot of requests. This is when you use LongAdder which also guarantees count is 250 but the way it does it is different. LongAdder maintains an array of counters, each thread updates a different element in the array with the count +1 and when you finally call sum, it adds the array. This means there is no contention because each thread is writing to a different block.
Puzzle: 10 (volatile vs AtomicBoolean)
What is the output of the program?
1package com.demo.basics.puzzle._010_volatile;
2
3import java.time.Duration;
4import java.util.concurrent.TimeUnit;
5
6import org.junit.jupiter.api.Assertions;
7import org.junit.jupiter.api.Test;
8
9public class VolatilePuzzle {
10
11 private boolean sayHello = false;
12
13 @Test
14 public void test() {
15 Assertions.assertTimeoutPreemptively(Duration.ofSeconds(3), () -> {
16 //sayHello();
17 });
18 }
19
20 public void sayHello() throws InterruptedException {
21 Thread thread = new Thread(() -> {
22 while (!sayHello) {
23 }
24 System.out.println("Hello World!");
25 while (sayHello) {
26 }
27 System.out.println("Good Bye!");
28 });
29 thread.start();
30 TimeUnit.SECONDS.sleep(1);
31 sayHello = true;
32 TimeUnit.SECONDS.sleep(1);
33 sayHello = false;
34 thread.join();
35 }
36}
Solution
The puzzle explains the concept of thread memory cache. When you call a thread it creates a thread stack that maintains a copy of the global variable. If the variable changes within the thread the changes are flushed, however if the variable changes outside the changes will not be synchronised immediately. Thread can continue to use the local copy of the variable not knowing that it has already changed. In the puzzle above even though we are change the boolean, the thread doesnt know the boolean changed in the main thread so it continues to refer to its local copy in cache. How to prevent the thread from maintaining a local copy of the variable cache and always refer to global variable? You can use volatile or AtomicBoolean
Puzzle: 11 (instance lock vs class lock)
What is the output of the program?
1package com.demo.basics.puzzle._011_instanceclasslock;
2
3import java.util.concurrent.ExecutorService;
4import java.util.concurrent.Executors;
5import java.util.concurrent.TimeUnit;
6
7import org.junit.jupiter.api.Test;
8
9public class InstanceClassLockPuzzle {
10
11 @Test
12 public void test() throws InterruptedException {
13 Greet greet = new Greet();
14 ExecutorService executor = Executors.newCachedThreadPool();
15 executor.execute(() -> {
16 greet.task1();
17 });
18 TimeUnit.SECONDS.sleep(2);
19 executor.execute(() -> {
20 greet.task2();
21 });
22 executor.execute(() -> {
23 greet.task2();
24 });
25 executor.shutdown();
26 executor.awaitTermination(10, TimeUnit.SECONDS);
27 }
28
29 class Greet {
30
31 public void task1() {
32 synchronized (Greet.class) {
33 System.out.println("task1 class lock acquired!");
34 while (true) ;
35 }
36 }
37
38 public void task2() {
39 synchronized (this) {
40 System.out.println(Thread.currentThread().getName() + " task2 instance lock acquired!");
41 try {
42 TimeUnit.SECONDS.sleep(2);
43 } catch (InterruptedException e) {
44 e.printStackTrace();
45 }
46 System.out.println(Thread.currentThread().getName() + " task2 completed");
47 }
48 }
49 }
50}
51
52
Solution
There are 2 types of locks instance lock and class lock.
Puzzle: 13 (Double check locking)
What is the problem with this program?
1package com.demo.basics.puzzle._013_doublechecklock;
2
3import org.junit.jupiter.api.Test;
4
5public class CheckLockingPuzzle {
6
7 @Test
8 public void test() {
9 CheckLockingPuzzle.getInstance().greet();
10 }
11
12 private static volatile CheckLockingPuzzle instance;
13
14 private CheckLockingPuzzle() {
15 }
16
17 private static CheckLockingPuzzle getInstance() {
18 synchronized (CheckLockingPuzzle.class) {
19 if (instance == null) {
20 instance = new CheckLockingPuzzle();
21 }
22 }
23 return instance;
24 }
25
26 public void greet() {
27 System.out.println("Hello World!");
28 }
29}
Solution
Introduces the concept of double check locking, where each thread accessing the syncronized block is a costly operation, hence doing a null check before and after the syncronization improves performance.
Puzzle: 14 (Race Condition)
What is the problem with this program?
1package com.demo.basics.puzzle._014_racecondition;
2
3import java.util.ArrayList;
4import java.util.HashMap;
5import java.util.List;
6import java.util.Map;
7import java.util.concurrent.Callable;
8import java.util.concurrent.ExecutorService;
9import java.util.concurrent.Executors;
10import java.util.concurrent.TimeUnit;
11
12import org.junit.jupiter.api.Test;
13
14public class RacePuzzle {
15
16 Map<String, String> bookMap = new HashMap<>();
17
18 @Test
19 public void test() throws InterruptedException {
20 ExecutorService executor = Executors.newCachedThreadPool();
21 List<Callable<Void>> tasks = new ArrayList<>();
22 tasks.add(() -> {
23 if (!bookMap.containsKey("book1")) {
24 bookMap.put("book1", "user3");
25 }
26 return null;
27 });
28 tasks.add(() -> {
29 if (!bookMap.containsKey("book1")) {
30 bookMap.put("book1", "user5");
31 }
32 return null;
33 });
34 executor.invokeAll(tasks, 5, TimeUnit.SECONDS);
35 System.out.println(bookMap.get("book1"));
36 }
37}
Solution
Race condition, two threads can try to update at the same time leading to data corruption. Using the atomic putIfAbsent should fix it.