Flatten 2D array and convert subscripts #MS algo IV

Here’s a standard way to flatten a 2D array into a 1D array. Suppose A is an 2D array int[3][5]. I flattens to 1D array F of int[15]. Imagine A as 3 rows of 4 items each. Denote constants R = 3, S = 5. So A(1,2) → F(7). All subscripts are 0-based.

Q1: Implement

int convertSubscripts(r,s)

Q2: Now B is 3D array int [Q][R][S], where Q, R and S are the sizes. Implement

int convertSubscripts(q,r,s)

You need to work out the algorithm on the white board. I actually drew the 3D array on white board to show my thinking.

3groupsOf3digits{yihai

Q: Find three 3-digit numbers with a ratio of 1:2:3;
These numbers pick their 3 digits from a range of 1 to 9;
All digits that form these numbers must be completely unique, i.e. you must use up all distinct 9 digits. For example, a set of 123:246:369 doesn’t qualify.

def failed_to_add(myset, digit): # return False when failed
    return digit == 0 or len(myset) == ( myset.add(digit) or len(myset))

def other_number_failed(myset, num): # returns False by default if everything good
    for digit in(num/100, num/10%10, num%10):
        if failed_to_add(myset, digit):     return True

def check(number1, myset):
    number2 = 2*number1
    if other_number_failed(myset, number2): return 
    number3 = 3*number1
    if other_number_failed(myset, number3): return 
    print number1, number2, number3, myset
    winners.append([number1, number2, number3])

winners=list()
nine_digits = tuple(range(1,10))
for digit1 in (1,2,3):
    last8 = list(nine_digits)
    last8.remove(digit1)
    for digit2 in last8:
        last7 = list(last8)
        last7.remove(digit2)
        for digit3 in last7:
            number1 = digit1*100 + digit2*10 + digit3
            if number1 > 329: break
            check(number1, {digit1, digit2, digit3})
print "-- lucky winners --", winners

ref-counted copy-on-write string #MIAX exchange IV

I completely failed this 2011 IV question from MIAX options exchange:

Q: outline a ref-counted copy-on-write string class, showing all the function declarations
A: here’s my 2017 answer

class Str{
	char * arr;
	unsigned int refCount; // size_t is more conventional
public:
	~Str(); //decrement and if needed, delete the payload
	//Str(); //empty ctor is useless since we can't really modify this instance, due to copy-on-write
	Str(Str const &); // similar to shared_ptr

	Str & Operator=(Str const & other) const; // will return a reference to another instance constructed on heap (never on stack!)
	Str & replace_with(char const * arr, size_t const len) const; //ditto

// optional utilities
	char const * c_str()    const; // <-- Hey mine is very similar to std::string
	Str(char const * arr, size_t const len); // <-- Hey mine looks similar to std::string 
	Str(std::str const &); 
	friend ostream & operator<<(ostream &, Str const &); // <-- Hey I got this right 100% 
};

java GC frequency and duration

Actually, GC overhead is more important than GC frequency or duration, except in low latency systems. This blog has many posts on overhead.

–frq

Could be Every 10 sec , as documented in my blog

–stop-the-world duration: (Concurrent collection probably doesn’t worry us as much.)

100 msec duration is probably good enough for most apps but too long for latency sensitive apps, according to my blog.

 

PIMCO(accrual account`)c++/java/sql IV

Q: (no good answer) You said users sometimes don’t know what they are requesting so their requirements actually don’t make sense. We as developers need good knowledge to discuss with them and solve the problem, not just take their instructions. Give an example where you challenged a user to understand better what she wants and then proposed a solution that better solves her problem.

Q: bond with sinking fund provision?

Q: suppose you bought at $104.5 with the $4.5 premium (or discount), how do you amortize that amount over the remaining 23 years of the bond? I guess the book value changes over time unlike stocks.

Q: compare a stock and a bond on the same company
%%A: coupon payments follow a predetermined schedule, not discretionary
%%A: bond has an end of life
%%A: future cashflow of the bond is known in advance
%%A: creditor vs partial owner, in the event of bankruptcy
A: bonds (esp. long-duration bonds) are more sensitive to interest rate changes

Q: what’s a bullet bond?
AA: Most bonds repay the principal as a single payment at the end of its maturity, which is known as a bullet payment. For this reason, conventional bonds are also known as bullet bonds. Amortizing bonds, on the other hand, repay the principal over a series of payments rather than all at once on the maturity date, so some or all of the periodic payments will consist of both interest and principal.

Q: how would you describe OO to a procedural programming student
%%A: use a real yet simple example like students/projects/grades/classes/labs/semesters/events/teams to illustrate the essential OO features

Q: how would you describe the spring framework?

q: java vs c++ for a concurrency system like a basic consumer/producer design?

q: java vs c++ for hadoop

%%Q: could I say std::transform() is a swiss army knife?

Q: a SAM interface in c++? Makes sense?

q: describe factory method pattern in c++?

q: bridge pattern implemented in pimpl?

q: can you use scoped_ptr or unique_ptr as class fields?
%%a: scoped doesn’t make sense
AA: wrong interpretation of “scope”. It can be a class field!

q: enable_shared_from_this ? I guess this has to do with the common scenario of two shared_ptr “clubs” each thinking it has sole ownership of a raw pointer

q: how do you declare an interface in c++?
%%A: no field. All methods are pure virtual. No ctor but dtor should be virtual

q: if you don’t declare a copy ctor what does the default copy ctor do?
%%A: bit-wise copy

q: can move ctor be synthesized if you don’t declare one?
%%A: some times it can, but I don’t think it’s always possible.
AA: Correct. for some classes, the standard forbids synthesized move ctor

q: what’s martingale
%%a: a process whose expected value at any future time is equal to the last realized or observed value. No drift.

q: what’s hitting time
%%a: expected time the process will hit a certain level

q: what if my join query produces duplicates, and those tables I join are not my table so I can’t redesign them?
%%a: use distinct or order by.
A: now I think it can happen if you select nothing but “gender”

q: what access modifiers can apply to a java interface?
%%a: private and protected doesn’t make sense. If it’s only used within a package and should not be exposed outside, then the default access may do.
AA: correct

c++base class method accessing subclass field#ICE IV

Surprisingly, the base class method can Never know that it’s actually an instance of the subclass. A few workarounds:

1. virtual function in subclass
2. curiously recurring template pattern
3. down cast the base pointer and access the field

#include <iostream>
using namespace std;
struct B {
	char id = 'B';
	virtual ~B() {}
	char getId() {
		return id;
	}
} b;
struct C: public B{
	char id = 'C';
} c;
int main() {
	B* ptr = new C();
	C* ptr2 = dynamic_cast<C*>(ptr);

	cout << "base class nonref: " << b.getId() << endl;
	cout << "sub class nonref: " << c.getId() << endl; //still base class method. 
	// The fact that host object is subclass doesn't matter.

	cout << "base class ptr to subclass instance: " << ptr->getId() << endl; //B
	cout << "downcast ptr non-virtual method: " << ptr2->getId() << endl; //B
	cout << "downcast ptr direct access: " << ptr2->id << endl; //C
	return 0;
}

UBS java IV 2017

Q: How could you get short theta?

Q: For a double-linked list, what if the prev pointer field is final?

Q1b: Can you construct such a list?

Q1c: What operation can you perform on it?

Q: How do you tell if a java app (or part thereof) is live-locked?

Q: How do you know if a jvm is short of memory, without seeing OOM error?

%%A: GC log would show much higher activity than the “baseline”.

Q: if a java app has hundreds of threads but most of them are not doing work, then what thread states would they have?

%%A: they must be blocked

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/

BGC IV – c++ and Java

Mostly QQ challenges.
—socket
Q: is select() blocking or non-blocking?
A: Yes select() takes a timeout argument to specify the blocking interval!
A: More interestingly, https://stackoverflow.com/questions/5351994/will-read-ever-block-after-select/5352634#5352634 says after select(), you should use read() which normally won’t block.

Q: server uses socket() listen() bind() accept(). How about client side?
Q1: if a producer thread uses select to send packets to multiple receivers by tcp and a single receiver has very low capacity, what would happen?
Q1b: select() would show the producer’s socket as writable or failed?

Q1c: what if producer keeps sending? What happens next?
%%A: the producers function stack will get an error code

Q1d: what if UDP rather than TCP
%%A: then no error would occur in the producer system. The slow consumer would be left unnoticed.

%%Q: can a socket specify a wild card for its local port?

—IPC
Q: fastest IPC method between producer and consumer? OK you said shared memory, so how do you synchronize the producer and consumer? %%A: use a named sys-V semaphore in the kernel
Q: how does the producer/consumer actually use the shared memory? %%A: memory mapped file

—brain teasers:
Q: Only a 5L and a 3L pail and a running tap. How to get exactly 4L water in the 5L pail?
Q: you are a given a bag of coins (like 1c 1c 1c 5c 5c 10c 25c). Tell me whats the smallest exact payment thats impossible. Every payment must be exact. Hint: sort the coins first, then a clever O(1) single-pass will do. Q: given a list of integers, find if any pair adds up to 18
%%A: in one pass, build a hashset of brown items i.e. every item processed so far. For every new (i.e green) item, compute the partner, and look for it in the hashset. If not there, then add the green item as a brown item.

—coding challenge
Q: given a singly linked list with a start node and null-end node, print each node in reverse, without using any “new” implicitly/explicitly

Q: Given an arbitrary directed graph where each parent node has 0 to K children, write a function hasCycle() to check for existence of cycle, visiting each node and each edge once only..
%%A: My verbal algorithm — use breadth-first traversal to trace every branch from root to a leaf node. Detect cycle in each branch. We cant simply keep a seen hashtable, because a node seen twice could be visited on two branches.

Whenever we branch out to 2 child branches, duplicate the parent branch, so that each child branch object has a full path from root.

Each branch object could be a (possibly linked[1]) hashset.
[1] for instrumentation.

Q: given a blackbox utility function String convert(String), write a parallelized Collection parellelConvert(Collection theSequence)
Requirement: theSequence need to be maintained. Size of input is preserved Requirement: Out of 100 items in theSequence, #3 and #5 might be identical, but they still need to show up as “converted” in the output
Requirement: converter uses a very slow and expensive remote system, so we don’t want to send it the same string twice.

—-
%%Q: is countdown latch and join() implemented using wait/notify? %%Q: readResolve vs readObject
%%Q: can CMS ever stop the world?
%%Q: CMS is used in which region of the heap?
Q: what if you suspect theres leak?
Q: what can cause mem leak in java?
%%A: registered listeners; static variables pointing to a collection

Q: why is swing memory footprint so bad?
Q: how do you mark a memory region as always resident?
Q: array blocking queue — when would it block?
%%A: I think a circular array is the underlying.

pimco java IV#Zoltan

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?

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: CAS; mutex; Read-Copy-Update; immutable objects; copy-on-write; thread local

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/