LiquidNet IV c++

Q1: partition list into good^bad sections

Q3b: fix a sample source code that passes unique_ptr<int> by value to a foo() function:

unique_ptr<int> foo(unique_ptr<int> kk)

Q3b.1: give examples of move semantic

Q3b.2: write a template solution to check if the template argument T is a pointer type. I don’t have a good solution but I mentioned SFINAE. My github has a sample sfinae code to check for specific types of pointers. In contrast, std::is_pointer doesn’t handle ptr to member etc.

How about static_assert? Yes tested

See post on template type arg validation

Q3a: improve

string & find(list<Person> li, string name){
  for (auto i=li.begin(); i!=li.end(); i++)
    if (*i == name) return i->nickname;
  return "";
}

%%A: last return will crash due to return-by-ref. If my function’s return value can be empty, then I usually return by pointer
%%A: equality check is dubious. Better be explicit like Person(name) or i->convertToString()
%%A: li.end() can be cached
%%A: ++i
%%A: li and name should really be const ref

Q4: predict output
%%A: I feel #2/3 are bad code but compiler may not be able to

struct B{void foo(){cout<<"hello\n";}; b = new B(); b->foo(); //#1
delete b;
b->foo(); //#2 .. what?
b=NULL;
b->foo(); //#3 .. what?
Advertisements

Bbg QnA IV

Q: how would you write your own program to see if local system is big-endian or little-endian.

Q2: what design patterns do you use?
A: factory, template-method are used a lot in my code.
A: producer-consumer is an essential pattern in async designs
A: adapter — wrapper functions?
A: When needed, I use visitor as a big gun.

Q2b: you said template method is often used implicitly. Can you give some examples in STL?
A: would be hard since classic template method uses virtual functions but there are very few of them in STL. std::sort() fixes the procedure and let user specify the comparison, using template techniques instead of virtual

Q: how would you design multicast to a number of registered users?

 

thesys mgr QnA IV

Q: why do you say look-up can be slower on hash table than RBTree?
A: hash collision; slow hashing;

Q: Given a fast parser but a slow disk writer, how do you persist all the messages received?
%%A: socket for IPC
%%A: shared mem is probably faster, even with synchronization cost
%%A: we can also use threads. Now I feel we should use coarse-grained concurrency. Each task is a big chunk of data. One of multiple consumers/writers pick up a chunk and spend a sizable amount of time writing to disk.

Q: what’s your concept of multiplexing?

Q: you notice packet dropping due to overcapacity. What would you do to improve throughput?

Q: what system calls have you used?

bbg cod`IV: %%clarifications

I had four technical discussions (before and after the wonderful lunch chat with Chitan and Neel). For three of them, I have a few echnical clarifications, as in a product design discussion.

  1. FX team:  in-place list shuffle — At home, I wrote and tested a splice() solution, but splice() works only on a linked list, which has roughly double the memory footprint of a vector of integers. If we forcibly apply some kind of splice on a vector, runtime cost of repeated shifts will be unacceptable. If there’s an in-place solution with O(1) space complexity and O(N) time complexity, then I have not found it.
  2. FX team: local static variables are zero-initialized by default, contrary to what we assumed in our discussion. This represents a bug in my solution. The extreme-value tests will indeed flush out this bug.
  3. Equities team: filters in screen —

At Akhil’s hint I sketched a conceptual design based on sorted map<priceValue, ticker>. I will call it a RBTree. This RBTree must be updated with each message, by erase/insert. Suppose we care only about filter latency, not about update latency. Or suppose we get relatively infrequent updates but many users perform applyAllFilters(). Then this RBTree can help. We will use lower_bound followed by backward iteration (for example, Price < 150). This is presumably faster than my simple solution of full hash table iteration. With both designs, we get the list of “survivor tickers” from this filter.

That’s the first filter in a screen. How about the second filter?  In my simple solution, I take the survivor list (of size N) from first apply_filter and then look up N times against filter2’s hash table (no full iteration). With the RBTree design, we have a choice. Let’s name the filter2’s RBTree as “tree2”.

  • if tree2.lower_bound() leaves very few (like 5) qualified tickers, but the survivor list from filter1 is large, then we should take each qualified ticker from tree2.lower_bound() and check if it is in filter1’s survivor list.
  • If tree2.lower_bound() leaves many (like 99999999) tickers to be checked, then we should drive from the survivor list. The tree2 won’t be used.
  • However, in a RBTree, how many nodes come before a given node is hard to count. This counting requires expensive iteration. so I feel the choice cannot be made at runtime.

As I told Akhil and Rajan, the RBTree vs my simple solution should be benchmarked in a realistic setting. Depending on the context, one will outperform the other.

bbg-Eq: filters in a screen

Exchanges constantly send you live update messages in a fixed format like

IBM, Price, 100
GOOG, Volume, 5000
MSFT, Volume, 14000
IBM, Price, 99
GS, Volume, 7000
MSFT, Price, 250
GOOG, Price 332

Each message always has exactly 3 fields — ticker, field name, integer value. The value only overwrites the previous value and never aggregates. In this example, the IBM price 99 will wipe out the IBM price 100.

There are up to 100 distinct field names, but many tickers and very high messaging rate.

Each user has a Screen, which holds a variable number of Filters defined by this user. Each Filter has a fixed format like “Price > 150” or “Volume < 9000”. All the filters need to be applied, to return a list of qualifying tickers. In this example, first filter alone returns a list of tickers {MSFT,GOOG} and 2nd filter alone returns {GS,GOOG}. Applying all filters would reduce the list to {GOOG}

Data feed goes into the server. Server maintains thousands of Screen objects, each for one user. When a new message is received, the server must apply all relevant filters. If out of 3000 screens 500 Screens’ lists get updated, then another module will update those 500 clients. You don’t need to design the interface to clients, data feed, threading.

Requirement: design the data store, the screen and filter.

I will assume 3000 Screens. On average, each Screen has 4 filters, defined by that user. If you assume every incoming message must be go through 3000*4 = 12000 filters, I guess you are probably right.

Can you avoid linear searches when applying filters? To illustrate, suppose all the messages are Price numbers. I maintain an unorder_map<ticker, priceValue>, updated constantly. When server applies a single filter, we start with the survivor list from previous filter. Go through each key/value of the map, and erase each disqualified ticker from survivor list. If I start with N tickers and perform N look-ups we get O(N).

Akhil hinted a reverse sorted map<priceValue, ticker>. I will call it a RBTree. This RBTree must be updated with each message, by erase/insert. Suppose we care only about filter latency, not about update latency. Or suppose we get very few updates but many Screens to applyFilters(), then this RBTree can help. We will use lower_bound followed by backward iteration (for example, Price < 150). This is presumably faster than my simple solution of full hash table iteration.

That’s the first filter. How about second filter? Let’s name the RBTree for the second filter “tree2”.  In my simple solution, I start with the survivor list (of size N) from first filter and look up N times against the hash table of the second filter, without full iteration. With the RBTree, we have a choice

  • if tree2.lower_bound() leaves very few (like 5) tickers to be checked, but the survivor list from first filter is large, then we should convert the survivor list to an unordered_set and drive from filter2.lower_bound()
  • If tree2.lower_bound() leaves many (like 9999) tickers to be checked, then we should drive from the survivor list. The tree2 won’t be used.
  • However, in a RBTree, how many nodes come before a given node is hard to count. This counting requires expensive iteration. so I feel the choice cannot be made at runtime. See RBTree range count #enum,auto

bbg-Eq: fewest increments on odometer

There’s a special odometer with N (eg 5) digits. Each digit can increment (never decrement, to keep the problem simpler) independently and cyclically, like 8->9->0->1. You can think of them as 5 independent mini-odometers. The starting sequence is input (perhaps something like 07748). Ending sequence can be any other value.

Each increment on any mini-odometer has cost of $1. Find the cheapest way to go from start to end. One simple solution (from me) –increment each digit cyclically to the target value. So a “8” will increment to 9 -> 0 -> 1. Other mini-odometers are not affected by this mini-odometer.

However, 18021 is one of many illegal sequences — barriers.

Key insight — When N==2, this becomes a 2D matrix Tom-n-Jerry problem with barriers. We can simplify the problem to a 3×3 matrix i.e. 2-digit odometer from 00 to 22. Nine possible sequences.

We need to build a graph of nine nodes, which helps answer

  • Q: feasible? [2,2] would be unreachable if [1,2] and [2,1] are blocked.
  • Q: which path is shortest path

Once we build the graph, shortest path btw 2 graph nodes #binary matrix as illutration will solve it.

bbg-Eq: longest abbreviation #easier

Given a long word with N non-unique characters, we know there can be 2^N abbreviations (including the original word, and including the empty string).

Requirement: I give you a list of strings and you suspect some of them could be an abbreviation of your word. Find the longest string among them that’s a valid abbreviation. Optimize for time complexity.

I feel this problem appears simple but not easy to complete quickly

https://github.com/tiger40490/repo1/blob/py1/py/str/testAbbr_ez.py is my python solution, different from the c++ solution below. Not sure which has more bugs.


I started with string::find() and hit the problem of non-unique characters. Interviewer hinted char-matching — the key point I needed for this type of problem.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

typedef string candidate;

vector<candidate> v{"monkey","aaaaaaaaaaaaaaaaaa", "mamalon", "monk"};
string const haystack{"mamalonkey"};
size_t hsize=haystack.size();

//Tip: can use typdef alias in argument:)
bool lenComp(candidate const & a, candidate const & b){
  return a.size()<=b.size();
}
ostream & operator<<(ostream & os, vector<candidate> const & c){
  size_t const sz = c.size();
  for (int i=0;i<sz; ++i){
        os<<c[i]<<" ";
  }
  os<<endl; return os; } //single-pass 🙂 
} 

bool check1candate(candidate const & c){ 
  if (c.size() > hsize) return false;

  for(int i=0, h=0; h<hsize; ++h){
        if (c[i] == haystack[h]){
          if (i==c.size()-1) return true;
          ++i;
        }
  }
  return false;
}
int main(){
  sort(v.begin(), v.end(), lenComp);
  cout<<v; for (int i=v.size()-1; i>=0; --i){
    if (check1candate(v[i])){
        cout<<"winner is "<<v[i];
        return 0;
    }
  }
}

 

bbg-FX: in-place array shuffle #splice^evict

Update: In-Place usually requires 1) splice 2) swap.

Requirement: given a list like

{1,2,3,4,  25,29,44,33,  159,139,155,150,  177,176,169,180} which describes four Persons
{id1,id2,..age1,age2, weight1,weight2,…height1,height2,..}

Write a program to output each person’s full attributes like

{1, 25, 139, 177,   2, 29, 129, 176,   3, 24, 135, 169,   4, 33, 140, 180}

Note the number of attributes (in this case 4) is an input parameter to your program. You don’t know (or care about) the name of each attribute. If you are told there are 37 attributes in each person, just output attr1 .. attr37.

Note the input and output sequence are important.

Q (Bonus question): do it in-place without creating a new collection. You can still have a small number of variables in your code.
A: one way to “cheat” is to append each output person to end of the original vector. It will double in size, so we will truncate the first half.
A: I believe I can use the “homeless/displacement” technique.
A: I now feel many in-place array reshuffle can be done in place with a single temp variable but this may not be one of them.
A: how about starting with a linked list?

https://github.com/tiger40490/repo1/blob/cpp1/cpp/array/insitu_reshuffle_attrib_bbg.cpp has ..

bbg-FX: check if a binary tree is BST #no deep recursion

Binary search tree has an “ascending” property — any node in my left sub-tree are smaller than me.

Q1: given a binary tree, check if it’s a BST. (No performance optimization required.) Compile and run the program.

Suppose someone tells you that the lastSeen variable can start with a random (high) initial value, what kind of test tree would flush out the bug? My solution is below, but let’s Look at Q1b.

Q1b: what if the tree could be deep so you can’t use recursion?
A: use BFT. When we actually “print” each node, we check left/right child nodes.


I made a mistake with lastSeen initial value. There’s no “special” initial value to represent “uninitialized”. Therefore I added a boolean flag.

Contrary to the interviewer’s claim, local statics are automatically initialized to zerohttps://stackoverflow.com/questions/1597405/what-happens-to-a-declared-uninitialized-variable-in-c-does-it-have-a-value, but zero or any initial value is unsuitable (payload can be any large negative value), so we still need the flag.

#include <iostream>
#include <climits>
using namespace std;

struct Node {
    int data;
    Node *le, *ri;
    Node(int x, Node * left = NULL, Node * right = NULL) : data(x), le(left), ri(right){}
};
/*    5
  2       7
 1 a
*/
Node _7(7);
Node _a(6);
Node _1(1);
Node _2(2, &_1, &_a);
Node _5(5, &_2, &_7); //root

bool isAscending = true; //first assume this tree is BST
void recur(Node * n){
//static int lastSeen; // I don't know what initial value can safely represent a special value

  //simulate a random but unlucky initial value, which can break us if without isFirstNodeDone
  static int lastSeen = INT_MAX; //simulate a random but unlucky initial value
  static bool isFirstNodeDone=false; //should initialize to false

  if (!n) return;
  if (n->le) recur(n->le);

  // used to be open(Node *):
  if (!isAscending) return; //check before opening any node
  cout<<"opening "<<n->data<<endl; if (!isFirstNodeDone){ isFirstNodeDone = true; }else if (lastSeen > n->data){
        isAscending=false;
        return; //early return to save time
  }
  lastSeen = n->data;

  if (n->ri) recur(n->ri);
}

int main(){
  recur(&_5);
  cout<< (isAscending?"ok":"nok");
}

Thesys QnA IV

Q: what’s the average O() complexity of insertion sort
AA: N^2 in most implementations — comparison-based, but using contiguous memory. NlogN if using skip list

Q: what’s the average O() complexity of heap sort
AA: NlogN, since it’s comparison-based.

Q: what are the synchronization primitives on the operating systems you know

Q: how many levels of caches are in a typical Intel processor
%%A: at least 3 possibly 4.
AA: some intel processors do have 4 levels

Q: name some IPC mechanisms
%%A: 1) shared mem 2) sockets 3) pipes

–2nd round (Don Bush?)

Q: Requirement: insert into a std::map only if key is absent
AA: the insert() function does that by default! Returns a pair<Iterator-where-inserted, bool-isInserted>. I used this same technique in my handleInputInternal()

Q: if my class Student has a private dtor, will it compile?
%%A: yes it’s possible to define a member function to invoke the dtor on a pointer passed in
%%A: deleting a ptr-to-Student won’t compile. Correct!
AA: have a friend call the dtor!

Q: Any guess why STL stack designer didn’t combine top() and void pop() like in other languages? hint: what if the copy ctor throws?
%%A: it’s more efficient if a function doesn’t need to return anything, so we don’t want to force the pop() users to pay a price for something they don’t need.

Q: do you create your own templates?
A: I should name the SFINAE hack!

Q: any restriction on a non-type template parameter’s type?
%%A: int and bool are common. Pointers are allowed. https://www.ibm.com/support/knowledgecenter/en/SSLTBW_2.2.0/com.ibm.zos.v2r2.cbclx01/non-type_template_parameters.htm shows even arrays and ptr-to-functions are allowed.
AA: has to be a discrete type, not a float

%%Q: what’s the usage of this non-type parameter?
A: std::array uses it for the size. It can’t be a ctor argument since if you construct an array on stack the size must be known at compile time.

Q: can you use new-arrays with shared_ptr? I think he wanted vector<shared_ptr>
%%A: if I have a new-array to store somewhere, then I think shared_array or scoped_array
A: how about shared_ptr<vector>?

Q: what if ctor failes in Foo * p = new Foo() // will memory leak?
%%A: i know it’s common practice to throw from ctor…

Q: name some c++11 features you used in your recent projects
%%A: unique_ptr, shared_ptr, auto, unordered_map, initializer list for vector/map

top N active stocks #bbg#cache,VO

Requirement: implement top_n(int N): top N most active stocks

Requirement 2: add a top_n_last_x_minute(int N, int X): top N that are last traded in the last X millisec

This program also demonstrates how to avoid storing the same string twice, as map key and also as field of the map value

//
#include <unordered_map> //requires -std=c++0x
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <chrono>
#include <assert.h>
using namespace std;

struct Rec{
  string const * strPtr; //a best-effort to avoid storing duplicate strings
  int cumvol; //cum vol
  long lastUpd; //millsec since epoch

  Rec(int vol): strPtr(NULL), cumvol(vol),
    lastUpd( (chrono::system_clock::now().time_since_epoch()).count()) { }

  bool operator<(Rec const & other) const{
        return this->cumvol < other.cumvol;
  }
  friend ostream & operator<<(ostream & os, Rec const & r){
        os<<r.lastUpd<<"-"<<*(r.strPtr)<<"  : "<<r.cumvol;
        return os;
  }
};

typedef unordered_map<string, Rec>::iterator ITR;

class App{
  unordered_map<string, Rec> lookup;
  vector<Rec> v;
  bool dirty;
public:
  App(): dirty(true){}
  void update(string const & symbol, int vol){
    this->dirty = true;
    ITR it = lookup.find(symbol);
    if (it == lookup.end()){
        pair<ITR, bool> pair = lookup.insert(make_pair(symbol, Rec(vol)));
        assert(pair.first->second.strPtr == NULL);
        pair.first->second.strPtr = //second is the valye in the pair
          & pair.first->first; //the key of the new pair
    }else{
        assert(it->second.strPtr != NULL);
        it->second.cumvol += vol;
        it->second.lastUpd = (std::chrono::system_clock::now().time_since_epoch()).count();
    }
  }
  void top_n(int N, unsigned long X=-1){ //unsigned -1 gives the largest positive value!
    size_t sz=lookup.size();
    if (dirty){
      cout<<"resorting due to updates to database ..."<<endl;
      v.clear();
      for(ITR i=lookup.begin(); i!= lookup.end(); ++i){
        v.push_back(i->second);
      }
      sort(v.begin(), v.end());
      dirty = false;
    }
    long now = (std::chrono::system_clock::now().time_since_epoch()).count();
    //cout<<now<<" is now"<<endl;
    for(int k=sz-1, count=0; k>=0; --k){
        if (now - v[k].lastUpd > X) continue;
        cout<<v[k]<<endl;
        if (++count >= N) break;
    }
  }
};
int main(){
  App app;
  app.update("ibm", 1000);
  app.update("gs", 700);
  app.update("gs", 500);
  app.update("goog", 600);
  app.update("msft", 800);
  app.update("ge", 500);
  app.update("ibm", 160);
  app.top_n(6,29);
  app.update("c", 400);
  app.top_n(3,39);
}

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?

int const SOD = 0, EOD=24;

struct Intv{ //can be a single meeting, a joined session or a free window
  int bgn, end; //end = 10 means 10 o'clock sharp. Will become float
  Intv(int a, int b): bgn(a), end(b){}
  bool operator<(Intv const & other) const { return this->bgn < other.bgn;}

  //can be a free function if no private fields
  friend ostream & operator<<(ostream & os, Intv const & a){
        os<<a.bgn<<'-'<<(float)a.end-0.41;
        return os;
  }
};
template<typename T> ostream & operator<<(ostream & os, vector<T> const & v){
        for(int i = 0; i<v.size(); ++i) os<<v[i]<<"  ";
        os<<endl;
}
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;
}
void printWindow(vector<Intv> const & arg){ //subsequent exercise
        if (arg.empty()){
                cout<<"free slot "<<Intv(SOD, EOD)<<endl;
                return;
        }
        vector<Intv> &v = const_cast<vector<Intv> &>(arg); //avoid vector deep cloning
        sort(v.begin(), v.end());
        cout<<v<<endl;
        if (v[0].bgn > SOD){
          cout<<"SOD free slot "<<Intv(SOD, v[0].bgn)<<endl;
        }
        Intv growing(v[0]); //current busy period
        for(int i=1; i<v.size(); ++i){
          //Heart of the algo. each new meeting either extends the current
          //busy period or prints a free window before it
          Intv & meeting = v[i];
          //cout<<i<<" a meeting: "<<meeting<<endl;
          //cout<<"growing = "<<growing<<endl;
          if (growing.end < meeting.bgn){
                cout<<"free slot "<<Intv(growing.end, meeting.bgn)<<endl;
                growing = meeting;
          }else{
                growing.end = max(growing.end, meeting.end);
          }
        }
        if (growing.end < EOD)
                cout<<"EOD free slot "<<Intv(growing.end, EOD)<<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): CRTP
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 PL1/PL2/… 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 container of smart pointers. I think it reduces the risk of slicing, among other benefits.
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.

[11] threading,boost IV #Sapient perhaps

Read-guard, write-guard ?

Q: how to test if current thread already holds a target lock?
%%A: Though there might be platform-specific tricks, I think it’s not widely supported. Best to use recursive mutex to bypass the problem.
AA: pthread_self() is a C function (=> non-method) that returns the thread id of the current thread.
AA: https://blogs.msdn.microsoft.com/oldnewthing/20130712-00/?p=3823 has a microsoft specific solution
AA: using this thread::id object a lock can “remember” which thread is holding it.  https://stackoverflow.com/questions/3483094/is-it-possible-to-determine-the-thread-holding-a-mutex shows a gdb technique, not available at runtime.

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.

2H life-changing xp#Pimco#income,home location,industry…

Here’s a real story in 2010 — I was completely hopeless and stuck in despair after my Goldman Sachs internal transfer was blocked in the last stage. I considered moving my whole family back to Singapore without any offer, and start my job search there. I was seriously considering a S$100k job in a back office batch programming job. Absolutely the lowest point in my entire career. After licking the would for 2 months, tentatively I started looking for jobs outside Goldman and slowly found my foothold. Then in early 2010, I passed a phone screening and attended a Citigroup “superday”. I spent half an hour each with 3 interviewers. By end of the day, recruiter said I was the #1 pick. I took the offer, at a 80% increment. In the next 12 months, I built up my track record + knowledge in

  1. real time trading engine components, esp. real time pricing engine
  2. fixed income math,
  3. c++ (knowledge rebuild)

I have never looked back since. Fair to say that my family won’t be where we are today, without this Citigroup experience. With this track record I was able to take on relatively high-end programming jobs in U.S. and Singapore. I was able to live in a convenient location, and buy properties and send my kids to mid-range preschools (too pricey in hind sight). Obviously I wanted this kind of job even in 2009. That dream became reality when I passed the superday interview. That interview was one of the turning points in my career.

Fast forward to Apr 2017 — I had a 20-minute phone interview with the world’s biggest asset management firm (Let’s call it PP), then I had a 2-hour skype interview. They made an offer. I discussed with my recruiter their proposal —

  • I would relocate to California
  • I would get paid around 200k pretax and possibly with an increment in 6 months. PP usually increase billing rate after 12 months if contractor does well.
  • recruitment agency CEO said he would transfer my visa and sponsor green card.

If I were to take this offer, my life would be transformed. (I would also have a better chance to break into the  high tech industry in nearby silicon valley, because I would have local friends in that domain.) Such a big change in my life is now possible because … I did well [1] in the interview.

Stripped to the core, that’s the reality in our world of contract programmers.  Project delivery, debugging, and relationship with boss can get you promoted, but those on-the-job efforts have much lower impact than your performance during an interview. Like an NBA playoff match. A short few hour under the spot light can change your life forever.

This is not a rare experience. There are higher-paying contract job offers that could “change your life”, and you only need to do well in the interviews to make it happen.

I feel this is typical of U.S. market and perhaps London. In Singapore. contract roles can’t pay this much. A permanent role has a few subtle implications so I feel it’s a different game.

[1] The 7 interviewers felt I was strong in c++ (not really), java and sql, and competent in fixed income math (I only worked with it for a year). Unlike other high-end interviews, there are not many tough tech questions like threading, algorithms, or coding tests. I feel they liked my interview mostly because of the combination of c++/java/fixed income math — not a common combination.

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 #RTS IV

Surprisingly, the non-virtual base class method can Never know that it’s actually operating within a subclass instance. It always behaves as a strictly-baseclass method and can’t access subclass data. The non-virtual method getId() is compiled into base class binary, so it only knows the fields of the base class. When a subclass adds a field of the same name, it is not accessible to the getId(). A few workarounds:

  1. curiously recurring template pattern
  2. virtual function in subclass
  3. down cast the pointer and directly 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; 
	cout << "downcast ptr non-virtual method: " << ptr2->getId() << endl; //B
	cout << "downcast ptr direct access: " << ptr2->id << endl; //C
	return 0;
}

 

BGC IV – c++ and Java

Q: how do you mark a memory region as always resident?
A: See mlock() : prevent paging ] real time apps

—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 22 receivers via 22 tcp sockets and a single receiver has very low capacity, what would happen? See tcp: one of 3 client-receivers is too slow

Q1b: select() would show that one sender socket as writable or failed?

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

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

%%Q: can a socket specify a wild card for its local port?
%%A: no. Wildcard is only for local IP
—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
A: See boos::interprocess documentation. This is a common requirement addressed in boost.

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 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.
AA: coin problem #all large-enough amounts are decomposable

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.
AA: https://bintanvictor.wordpress.com/2015/07/21/locate-a-pair-whose-diff55/ is a clever solution.

—whiteboard 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
A: reverse the list first (tail recursion or iteratively), then print normally.

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. But I wonder whether two parent nodes can have the same descendant node.

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: array blocking queue — when would it block?
%%A: I think a circular array is the underlying.

c++CollabEdit/Broadway IV: implement hash table#python

Q: implement a hash table class in any language. You could use existing implementations of linked list, array, hash function…

Q: talk about how you would implement rehash?
%%A: hash code won’t change for the key objects. But I would rerun the modulus against the new bucketCount. Based on the new index values, I would create the linked lists in each new bucket. Every pair needs to be relocated. Lastly I need to get rid of the old bucket array.

Q: how would you test your hash table?
%%A: try inserting (key1, val1), then (key1, val2), then look up key1
%%A: if I know any common weakness of the hash function, then test those.
%%A: trigger rehash

Q: what could go wrong in a multi-threaded context?
%%A: things like lost update or duplicate entries

Q: What concurrency solution would you choose for best performance?
%%A: could use lockfree algo at each point of writing to the bucket array or writing to a linked list.

C++ ICE mkt-data – some of the more difficult questions

Q: you said you write code on Windows, but production platform is linux, so how do you test your code?
Q: difference between a C struct and a C++ struct?
Q: have you used memory leak detectors?
Q: How do you link c and c++ code? dlopen()?
Q: have you used memory leak detectors?
Q: scope resolution operator?
Q: default constructor?

Q: what other things are synthesized?
%%A: dtor, copier, op= but c++11 add some move operators
A: indeed, c++11 would synthesize 1) move ctor and 2) move-assignment operator under strict conditions. See http://stackoverflow.com/questions/3734247/what-are-all-the-member-functions-created-by-compiler-for-a-class-does-that-hap

Q: given template<typename T> void f(T a, T b), can f(3, 0.8) compile?

Q: how do you use gdb to view a core file?

Q: write a sqrt(int) function without using the math library.  Estimate to 0.01 precision.

Q: UDP vs TCP?
A: virtual circuit. Single remote socket. In contrast UDP can send to multiple receivers efficiently – broadcast or multicast. A: transmission control, with data loss prevention

Q: what’s wrong with multiple inheritance? How do you deal with it?
%%A: diamond problem. I don’t use virtual inheritance. I use MI when base class is an interface without any field.

Q1: how do you create a thread in c++?
A: std::thread is RAII so the constructor starts the thread, and the dtor must run after joining or detaching.

Q1b: Have you used posix_thread?
A: it’s a c library, so no constructor magic. Probably some pthread_something() function. Correct! pthread_create()

locate a pair with targetSum==55 #bbg IV #Morris

Update

Q: any O(1) space sort?

Q: From an unsorted array of positive integers, is it possible to find a pair of integers that sum up to a given sum?

Constraints: This should be done in O(n) and in-place without any external storage like arrays, hash-maps, but you can use extra variables/pointers.

If this is not possible, can there be a proof given for the same?

—–Initial analysis—-
I wish I were allowed to use a hash table of “wanted ” values. (iterate once and build hashtable. For Each new value encountered, check if it is in the “wanted” list…)

I feel this is typical of west coast algorithm quiz.

I feel it’s technically impossible, but proof?  I don’t know the standard procedure to prove O(n) is impossible. Here’s my feeble attempt:

Worst case — the pair happens to be the 1st and last in the array. Without external storage, how do we remember the 1st element?  We can only use a small number of variables, even if the array size is 99999999. As we iterate the array, I guess there would be no clue  that 1st element is worth remembering. Obviously if we forget the 1st element, then when we see the last element we won’t recognize they are the pair.
—–2nd analysis—-
If we can find a O(n) in-place sort then problem is solvable [1]. Let’s look at Radix sort, one of the most promising candidates. https://stackoverflow.com/questions/463105/in-place-radix-sort has an implementation for DNA strings.

Assumption 1: the integers all have a maximum “size” in terms of digits. Let’s say 32-bit. then yes radix is O(n) but not sure about space complexity. Now, with any big-O analysis we impose no limit on the sample size. For example we could have 999888777666555444333 integers. Now, 32-bit gives about 4 billion distinct “pigeon-holes”, so by the pigeon-hole principle most integers in our sample have to be duplicates!

Therefore, Assumption 1 is questionable. In fact, some programming languages impose no limit on integer size. One integer, be it 32 thousand bits or 32 billion bits, could use up as much memory as there is in the system. Therefore, Assumption 1 is actually superfluous.

Without Assumption 1, and if we allow our sample to be freely distributed, we must assume nothing about the maximum number of digits. I would simply use

Assumption 2: maximum number of digits is about log(n). In that case radix sort is O(n log(n)), not linear time:(

—– new analysis as of Jun 2017 —-
Can Morris algo sort an array (external storage)? If yes,  then use the 2-moving-pointer algo in locate a pair whose diff=55

However, Morris needs a tree not an array.

[1] locate a pair with targetSum=55 : pre-sorted #O(N) 1-pass

3c++London bbg algo IV #all about array

Q: given a string of characters, find the longest “run” of any repeating character.

Q: given an array of integers, and a target, determine if there’s any pair that add up to the target. Return true/false.

Q: maximum profit problem. Given a time series of historical spot FX rates, find the maximum possible trading profit by exactly one buy one sell.
A: I have seen this many times. First write pseudo-code.

c++IV Art@Click #Jens

Q: buffer overflow?
%%A: avoid arrays, use vector
Q: XOR usage?
AA: usages? easy to google
Q: why bitwise shift?
%%A: mostly an optimization as far as I know, but the compiler probably translates integer multiply/divide already.
AA: usages? easy to google
Q: what’s wrong with pointers?
Q: dangling pointer?
Q3: what are the common exceptions in c++?
%%A: c++ has a few standard exceptions and a lot of UB; java has lots of standard exceptions and no UB. q(new) and dynamic_cast…
Q3b: undefined behavior?
%%A: much worse than exceptions or error codes
%%A: perhaps fairly consistent on one platform, but I know writing beyond an array’s limit is indeterminate. See [[c++ debugging)]
Q: exceptions – why do you not want to use it in your API?
%%A: can of worm. If I throw I can’t control how clients use this API. What if it’s thrown in a dtor? What if they don’t catch by reference? What if they catch a sliced one or a copy rather than the original exception object I want them to get? What if they catch by pointer and try to delete or forget to delete? Java cleaned it up.
%%A: I don’t see a lot of well-regarded API’s exposing exceptions
%%A: there’s performance cost
A: the best practice has always frowned on exception specifications. C++11 favors “noexcept”
A: now I think we should be consistent throughout – either throw exceptions consistently or never.
Q: memory leak – what is it and how do you deal with it?
%%A: valgrind replaces malloc with …?
%%A: provide class-specific op-new (and delete), which is safer (see effC++) than a customized global op-new. Add your own house keeping code therein…
Q: how is semaphore different from a mutex
%%A: I think a mutex is more basic and usually provided by the kernel (For a userland thread the thread library not the kernel must provide the mutex). I guess the counting semaphore is implemented using mutex + condition variables, since the semephore may need to inform the waiting threads.
Q: preprocessors?
%%A: 3 usages in my projects – #includes, macros and conditional compile. Now I think template meta programming also uses a lot of macros.
Q: stack trace?
%%A: very useful, that’s why java, c#, python, perl provide it, and GDB too.
A: [[safe c++]] shows simple and robust technique to build a stack trace upon assertion failure
I said many times “I’m philosophical about that” – meaning “it’s controversial IMO and I have my views which may look naive or extreme or eccentric”

C++bbg Standard IV Questions { Zack

1. How is keyword virtual used in C++?

2. Does better O() algorithm always works faster in real cases?

3. Between pre-increment (++i) and post-increment (i++) operator, which one is more efficient in both built-in and overloading case? …….. [[more eff c++]] item 6

4. Please compare array and linked-list in terms of insertion and access

5. Please name some sorting algorithms and their time complexity

6. Can you tell me the difference between stack and heap?

7. What Linux command do I use the find a file in a directory recursively?

8. what is the virtual functions and destructors

9. what is the constructor destructor orders of a class then an inherited class

10. what is the most known sort algorithms , and what is the complexity of each

11. Smart Pointer, how does it work.

12. Templates, when use instead of inheritance…….. [[eff c++]] Item 41

13. Polymorphism, when use multi inheritance, problems that can happen, ……. [[eff c++]]

14. Sockets, monitoring sockets.

15. Multithreading, give a small example of Producer, Consumer.

16. Debugging issues, using GDB

19. TCP/IP and Multicast

20. STL and Boost libraries

binary tree in-order walk #famed bbg Q

Is there a way to design an iterator over a binary search tree with the following properties?

1. Elements are visited in ascending order (i.e. an in-order traversal)
2. next() and hasNext() queries run in O(1) time.
3. Memory usage is O(1)

——-
I feel O(1) memory is impossible since this is recursive (though all recursions can convert to iteration with a queue bigger than O(1)), with a stack data structure of size H := height of tree.

Similarly, hasNext() need to work through the stack of size H, so O(1) run time impossible

Morris may meet the requirement.

2011 Pimco c++ #+perl/SQL #done

Many obscure QQ questions. Be selective what to study!

Q: diff between malloc() and new()?
%%A: must cast void ptr; must call ctor
A(hind sight): malloc need to be told the size. In contrast. new() relies on knowledge about the class
A(hind sight): array new can be done with malloc too
A (hind sight): new can be a (static) method, therefore inherited or hidden.
A: q(new) would put some housekeeping data in a header. Therefore, you can’t use free() on a new() ..

Q: ok, so malloc doesn’t call ctor, but can I pass the malloc void ptr to a ctor for initialization?
%%A: placement new will initialize a block of memory without allocation.
%%A: it’s not common. C++ language doesn’t encourage this operation.
A(hind sight): ctor doesn’t take a ptr argument?
AA: placement-new — https://stackoverflow.com/questions/2995099/malloc-and-constructors. Also see https://bintanvictor.wordpress.com/2017/06/28/op-new-allocateconstruct/

Q3: can you call a dtor explicitly?
%%A: yes though not a good idea. See C++ FAQ
A (hindsight): placement delete

Q3b: when would yo do that?
%%A: when i want to free a large block of heap memory as early as possible, and the dtor is not scheduled to run any time soon. But without delete() the heap memory isn’t freed. Probably delete can achieve the same purpose without looking ugly.
%%A: again, not  common and not encouraged by C++ language. I don’t think i would ever do that.
A(hind sight): placement new? Correct 🙂

Q5: can a dtor throw exception as the last statement?
%%A: no cos the dtor can be invoked as part of stack unwinding

Q5b: so what?
%%A: stack is unwinding due to another exception, and now your dtor creates a 2nd exception object. System is going to lose critical information in the 2 exceptions. The original exception handling flow is halfway through.

Q: given an instance of an absolutely empty class, can I downcast a ptr (or reference) to it?
%%A: assuming this class inherits from another empty class, you can’t since there’s no vtbl.

Q4: can you specialize a template with a ptr type as the type argument?
%%A: yes vector of raw ptr is common

Q4b: what must this template do to accommodate ptr template arguments? Too advanced and not one of my Tier 1/2 specializations
%%A: handle dtor, assignment and copier.
%%A: any memory-management operations must be customized. Default behavior is not good for ptr type arguments

Q: which part of c++ is most interesting to you?
%%A: low level access. Few other languages provide the low-level access

The remaining (perl and sql) questions are less daunting.

Q: perl pass an array by reference into a sub?
%%A: you can pass the address of the array. Array can be modified in-placer by the receiving sub
A: http://www.troubleshooters.com/codecorn/littperl/perlsub.htm

Q: chomp?

Q: perl open a file in append mode?
A: use “>>”

Q: when would you create a non-clustered index?

Q: select 2nd highest salary from a salary table?

Q: if my query need all 3 columns of an index (id, name, salary), how would you order the 3 columns when creating the index? Suppose salary has the highest selectivity
%%A: salary first

[11]Cantor/eSpeed c++ #manyQ

Mostly knowledge-based QQ questions. I need to be selective what to study.

Q1: The reverse is common but when do we provide c wrapper around c++ classes?
A: internal implementation is c++ but clients need C API

Q1b: can c call c++ # <—— very common question
%%A: at compile time, c++ code may be uncompilable by a c compiler. CFRONT converts c++ code into c source code until exceptions were added to the c++ language. At run time, if I have object code precompiled from c++, can c call it? I think it’s often possible.
A: check out the C Application Binary Interface. If your C and C++ code are interoperable, it is because your C and C++ compilers also conform to the same ABI.
A: yes that’s what extern “C” is for.

Q: tool for binary code dependency? (I guess the dependencies are dynamic libraries, rather than static libs linked in.)
AA: ldd or objdump. See http://ask.xmodulo.com/check-library-dependency-program-process-linux.html

Q9: call java from c++, what’re the c++ function(s)?
A: create_vm(), CallStaticVoidMethod(), CallVoidMethod() etc

Q9b: How do I access an int field of a java class?
%%A: if I have a pointer to the java object, I should be able to directly access the int field

Q: how do u implement a singleton

Q: semaphore(1) == mutex?
%%A: no since semaphore in most implementations uses a mutex internally. Functionally they are identical
%%A: semaphore is often cross process. Mutex can also be used on shared memory.

Q: for a const method getAge(), can it return a ptr to a non-const int which is a field?
%%A: i have seen sample code, so probably compilable
A: tricky. P215 effSTL says that inside a const method, all non-static fields become const.

Q3a: what’s the return type of operator*()?
%%A: can be anything, just like operator[], but not void not empty

Q3b: How about qq[ operator T*() ] ?
A(now): is it the OOC to a ptr? Correct. See http://en.cppreference.com/w/cpp/language/cast_operator

Q: if Base class has a virtual method f(int), and Derived class has an overload virtual method f(float, char), is the Base f() accessible via a D object?
%%A: the D f() hides the base f(), but base f() may still be accessible using A::f()

Q: 1 process, 30 threads vs 10 processes * 3 threads each? Assuming there’s data sharing among the threads
%%A: avoid ITC and serialization
%%A (Now): I feel single-process has a single point of failure without redundancy.
A: depends on the IPC cost. If non-trivial cost then favor 30-threads.

Q: how do u change the default fair-share scheduling among threads? #<— uncommon
%%A: I can make some threads sleep or wait. I can control thread-lib-level priorities, but the kernel thread priority levels could be very coarse
%%A(now): if userland thread, then scheduling is done in the thrd lib.

Q: unix performance monitoring?
%%A: jconsole; top; vmstat; perfmeter

 

Q: Dynamic loadable library. How do we configure the system to load a new version of the library?
%%A: $LD_LIBRARY_PATH
%%A: just overwrite the existing *.so file??

Q: how to convert a ptr-to-non-const to a ptr-to-const?
AA: just assign it. The reverse assignment needs const_cast. Tested in g++. I feel this is an obscure technicality.

— communication layer
Q: how do I see syscalls and sockets open by a process?
%%A: truss; lsof; snoop/tcpdump; netstat

Q: practical use of signals?
%%A: kill, core dump, thread dump, suspend,..
A: I used q(trap) to install my signal handler in my bash

Q: what are named pipe? #<—– uncommon
%%A: I think they exist in the file system as fake files. “cat | more” uses an unnamed pipe I believe.
A: now I think I should just say “never used it”.

2011 BGC c++IV #socket #done

Q3: what can go wrong during a write to a socket??? (LG)
Q3b: if buffer is full, will the writing thread block???
%A: by default it blocks, but it’s probably possible to configure it to return an error code or even thrown an exception

Q: blocking vs non-blocking socket?

Q: socket programming – what’s select ?

Q: Should base class dtor always be virtual?
%%A: I would say yes. If a dotr is really not virtual, then it’s not supposed to be a base class. However, SOF mentions: “If you want to prevent the deletion of an instance through a base class pointer, you can make the base class destructor protected and non-virtual; by doing so, the compiler won’t let you call deleteon a base class pointer.”

Q: how many ways to share data between 2 processes? How about shared memory

Q: synchronize 2 unix processes accessing a shared file?
A: named semaphore

auto_ptr implementation notes – eSpeed IV

Someone asked me to implement a basic auto_ptr class template. It should be usable like

void foo(int * ip){…}

int* intP = new int(3);
AutoPtr aptr = ….. // create an AutoPtr object to encapsulate intP;
foo(someExpressionOfAptr);

Implement dtor, copier, op=… for the AutoPtr class,

Overload dereference, arrow to mimic pointer behavior.

Q: And what else?
A: cvctor to convert int ptr to an AutoPtr

Q: how about an operator-overload-converter (OOC) to convert from an AutoPtr to an int ptr? Why do we need it?
A: an auto ptr should be usable as an int ptr, ie foo(aptr). This requires the OOC.

Now you see the need to implicit convert both ways between AutoPtr and raw ptr!