pimco java IV onsite

Hint 81: fib(a,b, N) can be implemented as fib(b, a+b, N-1). For example, 8th Fibonacci number would be fib(0,1, 8), which would call fib(1,1,7), which would call fib(1,2,6)… This is related
to http://stackoverflow.com/questions/310974/what-is-tail-call-optimization

Q: can CMS ever stop the world?
AA: yes

Consider Fibonacci sequence. Write a function fib(N) that returns the N’th number in the sequence. fib(0) := 0, fib(1) :=1, fib(N) := fib(N-2) + fib(N-1).

Q1a: write a recursive version. What’s the time complexity and space complexity?
Q1b: write a non-recursive version. What’s the time complexity and space complexity?
Q1c: write a non-recursive version with space complexity of O(1) Q1d: write a tail-recursive version with time complexity O(N) and space complexity O(1). If no clue, look for the hint hidden nearby:)

Q2: Consider a simplified shared shopping cart. It contains any number of orders. Each order has {id, productName, quantity}. Only id is immutable; other fields are writable by multiple threads. Implement the following methods without locking (you could use atomic or other solutions to ensure thread safety):

int addOrder(productName, quantity);
boolean modifyOrder(id, productName, quantity); // two threads could modify the same order concurrently.
[Optional feature] boolean deleteOrder(id);
[Optional feature] boolean isOrderCompleted(id);

To keep requirements simple, It’s tolerable to have two orders both for the same productName.

Q3: At a high level, list all the common approaches to thread safety %%A: Read-Copy-Update; thread local; immutable objects; copy-on-write; mutex; CAS

Q4: how do you implement an immutable class with only primitive fields? %%A: make all fields private; provide no setter

Q4b: the fields need to be final?
%%A: I think unnecessary.

Q4c: class should be final?
A: I said yes but Now I think subclassing can be allowed since my fields will not be writable by subclasses. For example, a ImmutablePerson{SSN, DOB} can be sub-classed by Student{nationality, department}

Q5: what kind of classes can be a key in a map?
%%A: I feel the relevant fields should be primitive, string and enums only. Any other field I want to be careful about.
%%A: key class is effectively immutable — after the key goes into a map, the relevant fields should not change because the position of the key will not be updated.

Q6: for an overnight batch program, what GC algorithm is good for throughput?
%%A: long pauses are tolerable.
AA: Use parallel GC. See my blog
post https://bintanvictor.wordpress.com/2017/04/05/two-gc-algos-for-latencyt hroughput/

Q7: how frequent is the minor GC in your app?

Q8: how do you deal with OOM in production?
%%A: use jconsole, or somehow print a memory “report” to the log.

Q10: compare vector and linked list data structures
%%A: vector is random-access. Appending at the end is usually fast but can cause reallocation; linked list can insert anywhere but each node is too big.

Vector takes smaller space and is more cache-friendly.
See https://bintanvictor.wordpress.com/2017/04/05/contiguous-memory-data-str uctures-page-faultscache-miss/

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s