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.


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])

nine_digits = tuple(range(1,10))
for digit1 in (1,2,3):
    last8 = list(nine_digits)
    for digit2 in last8:
        last7 = list(last8)
        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
	~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.


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

The base class 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 rather than the method!

#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