Nomura C++quant IV

Q: vector.at() vs operaotr[]?
%%A: operator[] throws exception only if you specify a compiler flag like D_GLIBCXX_DEBUG. I think this is correct

Q: given a vector or ints, how would you sort it by abs value?
%%A: free function
%%A: subclass “less” with operator(). body is same as the free function

Q: clustered index vs non-clustered?

Q: inputs to price an equity option?
%%A: 5 inputs: K, S, T, r, dividend rate. I missed “implied volatility”, which is a soft market data derived from a raw market data.

Q: inputs to a mortgage prepayment model (or callable bond)? ….
%%A: Black model to price a callable bond. Inputs include yield, maturity, interest rate, but there’s no strike per-se? I think the implied volatility (in which random process?) is the most important factor and needs to be backed out from some market data

Q: how did you construct your yield curves at Barcap?

Q: what’s local vol
A: the instantaneous volatility is a deterministic function of 2 inputs. Deterministic because there’s no dB … See other blog posts.

Q: zero-volatility spread?

Q: how do you compute OAS?
%%A: I think OAS is a curve.

Q: how about dv01?

Q: duration of a 10Y T-bond vs 10Y muni bond? I answered with the (more “visual”) Macaulay duration, which is slightly different from the (most useful) modified duration

Advertisements

bbg QnA c++2017

These interviews are mostly based on coding question but there are some QnA:

Q: write some simple code to determine if your system is big-endian or little-endian

Q: when would you (not) mark a function inline?

Q: after you successfully inline some functions the app runs slower than before. Any reasons?

 

 

show free slots between meetings #bbg c++11

Q: You are given a list of teleconference booking like {9,10} meaning from 9am to 10am. We can multi-task, so overlap is fine. Can you print out all the free slots within the day? You can safely assume all the input data are sensible and between 9 to 18, i.e. our workday.

I solved this problem on the spot. My weakness is still the ECT cycle esp. the compiler errors.

I was familiar with the inverse problem of listing all busy sessions. So I decided to *focus* on that. I took a calculated risk that once I get that to work, I will have the cool confidence to solve the original problem.

corner case: two adjacent meetings. I added comment to specify exactly how to check for that
corner case: what if the entire day is one busy session?

struct Intv{ //can be a single meeting, a joined session or a free slot
  size_t st, end; // 9 means 9 o'clock. Can be float
  Intv(size_t a, size_t b): st(a), end(b){}
  bool operator<(Intv const & other) const { return this->st < other.st;}
  friend ostream & operator<<(ostream & os, Intv const & a){
        os<<a.st<<'-'<<a.end;
        return os;
  }
};
void printBusy(vector<Intv> const & arg){
  if (arg.empty()) return;
  vector<Intv> & v = const_cast<vector<Intv>&> (arg);
  sort(v.begin(), v.end());
  size_t const sz = v.size(); //cache
  Intv growable = v[0];
  for(size_t i = 1; i<sz; ++i){
        Intv & req = v[i];
        if (growable.end < req.st){
          cout<<growable<<endl; //close current session
          growable = req;//start new session
          continue;
        }
        growable.end = max(growable.end, req.end);
  }
  cout<<"last session : "<<growable<<endl;
}
int main() {
        //pass in initializer list to initliaze a const vector
        printBusy({Intv(15,17), Intv(7,9), Intv(5,7)});
}

TradeWeb c++IV

100% QnA interview. No coding no white-board no ECT no BP no algo no data structure.

System is Multi-threaded VC++/MSSQL.

One technical interviewer only. (The other 2 are behavior interviewers.) He is a director and looks very technical. I have met perhaps 3 to 5 interviewers focused on the fundamentals of a language/compiler. They pick one of 10 important parts of a language (like java, c++ or c#) and try to determine how well a candidate understands the key details and the rationales.

Below, Q’s are questions from this interviewer. A’s are my answers/guesses.

Q1: let’s talk about non-virtual dtor. You said there are problems in deleting a subclass instance via a base class pointer. Show an example.
A: Eg: subclass holds some resources to be released in its dtor, but in our scenario only the base dtor is called. Subclass dtor is not invoked.

Q1b: if subclass dtor is invoked, does it always run the base dtor?
%%A: Yes guaranteed. See my blog.

Q1c: if a subclass dtor is virtual and you delete an instance via a subclass ptr, you said this is good and subclass dtor will run, so is the “virtual” unnecessary? What’s the difference virtual dtor  vs non-virtual dtor?
A: The dtor is still picked at run time (and slower), but yes in both cases the subclass dtor runs.  If your system is written such that you delete a subclass instance only via a subclass ptr and never superclass ptr, then drop the “virtual” to improve runtime performance.

Q3: Let’s talk about a static member function sf2() in class Base. If you have a reference to a Base instance, Can you call myInstance.sf2()?
A: yes

Q3b: if Base and Der both have a static method sf2()?
A: subclass sf2 tends to hide Base sf2. Static type of myInstance variable is used to determine which version is used.

Q3c: how about myPtr->sf2()? Obscure details that I don’t want to spend too much time on.
%%A: looks very odd, but if it compiles, then it’s static, never dynamic, binding.

Q4: when must you use the pointer “this”? Obscure details that I don’t want to spend too much time on.
%%A: ctor chaining? Actually chaining is supported in c++11 but not using “this”.
A: if there’s a field and a local variable of the same name, I use “this->” to disambiguate. CORRECT:) See
https://stackoverflow.com/questions/22832001/access-member-field-with-same-name-as-local-variable-or-argument
A: in my ctor (or method), i may want to print my address. Yes you can usually do that in the caller afterwards but not always
A (hindsight): Similarly, in my ctor (or method) I may want to conditionally save my address in some container. The conditional logic is not doable after the ctor.
A (hindsight): if I know the host object is in an array, I could do array arithmetic using “this” with precaution.
A: delete this. I have seen people doing it.
A (hindsight): if parent class has a const method m1() and non-const overload m1(), you can cast “this” to call either of them.
A (hindsight): what if inside a method you need to access a parent object field hidden by a host object field? Can you cast “this”? Yes tested but not a “must” use case. Alternative solution is B::nonStaticField
AA: sometimes you must return *this where the return type is HostClass&

Q4b: can you think of an example of using “this” to avoid access violation?

Q4h: why use ctor chaining even if it’s supported? Why not call a common (non-static) setter method s2() from multiple ctors of the same class?
A: that setter has to be non-static!

Q4i: You think ctor should not call a non-static method?
A: it can, but I don’t do it. The host object is half-initialized, so the setter method must strictly perform field initialization and nothing else.

Q5: why do people use class templates? Note — Interviewer didn’t ask function templates.
%%A: avoid the cost of virtual functions

Q5b: Let’s look at combining class hierarchy with templates.
A: not a good idea to combine them. STL has probably no virtual functions.

Q5c: Let’s see. You said you have a bunch of “payload” classes and you want to use a container of PL1 and container of PL2. Ok You said that’s a common use case of class templates unrelated to virtual functions. Suppose the container template requires each payload class to implement a method f2(). If f2 is provided by a base class, wouldn’t it be easier (can be virtual or non-virtual)?
A: If there’s a family of payload classes, like Shape, Rectangle, Square… then I feel it’s best practice to use a template of smart pointers. I think it reduces the risk of slicing.
A: if the payload classes don’t form a family hierarchy, then there is probably some template meta-programming technique to provide a default implementation of f2(). I’m no expert on template meta-programming.

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.

 

Monkey-jump problem{Ashish IV@Baml #solved

On the 2D-coordinate plane, A monkey starts from point [a,b] and wants to reach [P,Q]. From any point, the money can only jump to one of two points:

1. [x,y] up to [x, x+y]
2. [x,y] out to [x+y, y]

Q: Can you write bool canReach(unsigned long long a,b,P,Q)
A: start from [P,Q] and have no decision to make!

#include <iostream>
using namespace std;
struct Point {
    int x, y;
    Point(int x, int y) : x(x), y(y) {}
    friend ostream& operator<<(ostream& os, Point & n){
      os<<n.x<<","<<n.y;
      return os;
    }
};
bool canReach(unsigned int a, unsigned int b, unsigned int P, unsigned int Q){
  Point lower(a,b), higher(P,Q);
  for(Point p=higher;;cout<<p<<endl){
    if (p.x == lower.x && lower.y == p.y){
        cout<<"Good:)"<<endl;
        return true;
    }
    if (p.x==p.y || p.x<lower.x || p.y<lower.y){
        cout<<"Failed:( Can't jump further"<<endl;
        return false;
    }
    if (p.x<p.y){ p.y = p.y-p.x ; continue;} 
    if (p.x>p.y){ p.x = p.x-p.y ; continue;}
  }
}
int main() {
  cout<<canReach(1,10, 57,91);
}

 

threading, boost – IV questions

Read-guard, write-guard ?

Q: how to test if current thread already holds the lock?
AA: Boost namespace  function get_id() returns An instance of boost::thread::id class that represents that currently executing thread.
AA: pthread_self() is a C function (=> non-method) that returns the thread id of the current thread.
AA: see the pthreads recursive mutex note below.
A: using this thread::id object a lock can “remember” which thread is holding it.

Q: Is scoped_lock reentrant by default? Can you make it reentrant?
AA: With a boost recursive mutex, a single thread may lock the same mutex several times and must unlock the mutex the **same-number-of-times**.

AA: pthreads supports it. http://www.opengroup.org/onlinepubs/009695399/functions/pthread_mutex_lock.html says — If the mutex type is PTHREAD_MUTEX_RECURSIVE and the mutex is currently owned by the calling thread, the mutex lock count shall be incremented by one and the pthread_mutex_trylock() function shall immediately return success.

Q: Boost supports try_lock()?
AA: yes

Q: Boost supports lockInterruptibly()?
A: probably not, but there’s timed_lock

Q: Boost supports reader/writer locks?
AA: read/write lock in the form of boost::shared_mutex

Q: difference between mutex and condition var?

Q: can you write code to implement “recursive” locking with reader/writer threads?
A: key technique is a bool isHoldingLock(targetlock)

Q: what types of smart pointers did you use and when. What are the differences? I’d like to focus on the fundamentals not the superstructures.

Q: what other boost lib?
%%A: I briefly used boost bind. I believe STL binders are imperfect, and lambdas are superior

Q2: if I want a custom class as a map key?
%%A: must overload the less-than operator

Q2c: what if I can’t change the source code?
%%A: derive from binary_function to get a functor, and pass it to map constructor as the optional type param. However, the new functor only has “operator()” overloaded? I think it will still work, as the function doesn’t have to be named “less()”.
AA: Item 42 [[eff STL]]

%%Q2g: is operator less-than a friend func or a method?
AA: can be a non-friend(if everything public) or a friend class/func.