coding IV milesPerGallon{Deepak.cm

Similar to GS Tick Query question but without optimization requirements.

–Requirement: Your Choice of Editor, OS, Compiler & Programming Language. Total time allotted for this  test is 75 mins, The further rounds of Interview will be based on this programming test.

A group of N people go for driving. When ever they refill the fuel in their vehicles, they update a text file with the following fields

<Name of Persom>, <Car Model>, <No of Miles driven>, <NO of Gallons filled>,<Date of fill>

All the fields are comma separated. A sample such file is given below

John, Toyota Corolla, 350, 20, 20160920
Jonathan, Mercedes GLA, 220, 13, 20160920
Mishal, Ford Escort, 230, 35, 20160919
John, Honda Accord, 300, 22.5, 20161112

Write a function with the following parameters
GetMPG(name_of_person, Start_date, End_date)
such that it should return the following information for each User/driver
1) Name of Car
2) Miles per Gallon for the mentioned period for each of the Car

A person can have more than one car. If there is no record for the mentioned date range, the function should not return anything for that specific car.
— Here’s my python solution:

import sys,bisect
from pprint import pprint

allrec = dict()

class Trip:
  def __init__(self, car, date, miles, fuel):
    self.car = car
    self.date = int(date)
    self.miles = float(miles)
    self.fuel = float(fuel)
  def __repr__(self):
    return self.__str__() # supports pprint
  def __str__(self):
    return self.car + ' ' + str(self.date) + ': miles=' + str(self.miles) + ' fuel=' + str(self.fuel);

def load():
  with open('data.txt') as f:
    lines = f.readlines()
  for line in lines:
    if  not line.strip(): continue
    tok = [x.strip() for x in line.split(',')]
    r = Trip(tok[1], tok[4], tok[2], tok[3])
    #print r
    name = tok[0]
    if allrec.has_key(name):
      allrec[name].append(r)
    else:
      allrec[name] = [r]

  #pprint (allrec)

  for name in allrec:
    allrec[name].sort(key=lambda x: x.date)
  #pprint (allrec)

def getMPG(name, d1, d2):
  if not allrec.has_key(name): return 'name not found'
  li = allrec[name]
  keys = [rec.date for rec in li]
  idx1 = bisect.bisect_left(keys, d1)
  idx2 = bisect.bisect_left(keys, d2)
  #print idx1, idx2
  #print li

  perCar = dict()
  for idx in range(idx1, idx2+1):
    rec = li[idx]
    # put each trip under the given car
    if perCar.has_key(rec.car):
      perCar[rec.car][0]+=rec.miles
      perCar[rec.car][1]+=rec.fuel
    else:
      perCar[rec.car]=[rec.miles, rec.fuel]

  for car in perCar:
    tmp = perCar[car]
    print car, tmp[0], tmp[1], tmp[0]/tmp[1]

def main():
  load()
  getMPG('John', 20160920, 20170920)

if __name__== "__main__": # best practice.. make this script usable as a module
    sys.exit(main())
Advertisements

tail-recursion Fibonacci #any lang

Tail recursion is a “halo” skill in coding interviews.

Easiest problem is factorial(N). For Fibonacci, https://stackoverflow.com/questions/22111252/tail-recursion-fibonacci has a very short python implementation. Let me rephrase the question:

Q: Given f(firstVal=0, secondVal=1, length=0) returns 0, f(0,1,1) returns 1, can you implement f(0,1,N) using recursion but in O(N) time and O(1) space? Note Fib(N) ==f(0,1,N)

Key points in the python solution:

  • Start with iterative algo, then convert it to tail recursion.
  • use 2 extra arguments to hold last two intermediate values like Fib(2) Fib(3) etc
  • We saw in the iterative solution that memory usage is O(1), a good sign that tail recursion might be possible.
  • if you observe the sequence of Fib() values computed in the blackbox, actually, you see Fib(2), Fib(3) … up to Fib(N), exactly like the iterative solution.
  • solution is extremely short but non-trivial

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

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

struct Payload{ //this object must live outside any Str instance. If 1st Str instance in the group is destroyed, this object must live on.
	char * const arr;
	size_t const length;
	mutable size_t refCount;
	Payload(std::string const &);
};
class Str{
	Payload const * payload;
public:
	~Str(); //decrement refCount and if needed, delete the payload
	//Str(); //default ctor is useless since after construction we can't really modify this instance, due to copy-on-write
	Str(std::string const &);
	Str(Str const &); // similar to shared_ptr

	Str & Operator=(Str const & other) const; // will return a reference to a new instance constructed on heap (never on stack!). The new instance will have a ref-count initialized to 1
	Str & replace_with(std::string const &) 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
	friend ostream & operator<<(ostream &, Str const &);
};

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.