c++advanced IV questions – contributed by real interviewers

http://www.quora.com/Anyone-can-list-good-common-and-advanced-questions-for-testing-C++-STL-skill-during-interview

These authors are real interviewers. They really do care about the topics I mentioned to you Monday night. They are seeking c++ specialists who understand the low level details. They don't care about the high level, architecture, design, picking the right framework or library etc.
Victor

Fwd: difficult phone screen with Credit Suisse

Hi Bin,
I just finished a frustrating interview with Credit Suisse.
It's just a phone screen, but many questions I cannot answer. When you have time, please add some comments to below questions.
And because I work from home for the interview, so I can record the whole call. It's shared to you in another email. Please give me some comments about how I behaved, just assume if you were the interviewer, what's your feeling about this candidate?
It's not that urgent, so just do it only when you can find time. I know you have a lot of work to do, so don't waste too much of you time.
——————————————————
1. describe one of your best coding challenges in 2 to 3 years, that can show off your coding abilities and your object oriented skills.
Rong: I mentioned NIO server I had hands on experience.
Interrupted by him, he said: the key thing I'm asking for is the specific coding that you personally did.
Rong: I should not mention I lead a team, because maybe that's the reason he suspect I describe other developers' work as mine. I feel for developer role, management experience is a downside factor.
2. Describe how did the single threaded application avoid blocking IO.
Rong: I cannot articulate how NIO works. I actually indeed created a NIO server. That's true, but I don't know how to explain well in phone screen, and I cannot recall some details such as the class, methods.
3. He continued to asked some details about NIO, and I cannot recall details.
4. Now he start normal quiz procedure. I only list difficult ones here, but I attached the full list FYI.
……
Would you want to implement a maximum queue depth?(I didn't know what's maximum queue depth mean)
What happens if your queue backsup?(I don't known what's that mean)
Would you want a maximum length? Why?
What happens if your producer hit the maximum length?
Do you know what's the completion services?
There is an alternative that you can implement producer/consumer without a queue?
What are the 3 different ways of creating a thread?(implement Runnable, extend thread, what's the third?)
Different between Runnable and Callable? (Callable return result, Callable throw Exception)
Any other differences or advantages for one over the other?
Let's say we have a process that receives request to do work. And each request has no dependency on each other.
And the request queue backs up. How would you solve this? 
(I don't know what's backs up mean. So I assume it means the queue is full. So requesters are blocked and processor will process one by one.)
When you want to use a timer of some kind, what are the different way you can do it in your code?
(I said there is a scheduler class?? not sure if there is)
How would you shut down the multi-threaded system? let's assume you write your own multi-threaded system.
(use countdownlatch?)
What if the thread is blocked?
(call thread.interrupt())
That's it?
What's the exception chaining? (I don't know)
Apart from try-catch block, how can you ensure all exceptions in thread pool are caught by our code?
What's meant by safe publication and the context thread safty shared object retrieval?
fail-fast vs fail-safe?
How would you use the future task? Which method would you use? How would you retrieve the result later?
Do you know the method, what's that called?
Difference between semophore and mutex?
……

Fwd: java threading questions {xr

Question: 
Since vector is synchronized, is below code thread safe? If 2 threads are running below code, what will happen?
if(!vector.contains(element)) {
vector.add(element);
}
Rong answer: not thread safe, because another thread could add element in between vector.contains(element) and vector.add(element);
(my own question, not from interview, but just my own thought: What does “Vector is synchronized” mean?
my own answer: It means all methods that can update data are synchronized. So calling each single method is thread safe, 
but a transaction involving 2 synchronized methods is not thread safe. Only if a transaction is atomic, we can say it’s thread safe.
Question: 
synchronize(obj) {
obj.wait();
}
if 2 threads are running above code the same time, what will happen?
Rong answer: one thread acquire lock, then release lock, another thread acquire lock and then release lock, both wait forever.
follow up question: if a third thread call obj.notifyAll(), what will happen?
Rong answer: both waiting threads will be woken up, then one thread acquire lock and finish, then another thread acquire lock and finish.
Question:
synchronize(obj) {
print(“A”);
obj.wait();
Thread.sleep(100000000);
}
what will happen if 2 threads are running above code?
Rong answer: both print “A” then wait; if notified by a third thread, then will sleep for a long time.

Fwd: vague question { xr – production troubleshoot

This is another vague question I couldn’t handle well.
He said that if the production application is hung, how do you find out what caused the problem?
Rong: I check CPU, if CPU is busy… (He interrupted: “suppose CPU is not busy.”)
Rong: I will check memory usage, if …(He interrupted: “suppose not memory used up.”)
Rong: I will check if there is I/O blocking …(He interrupted “suppose not because of I/O blocking.”)
Rong: That’s my way to analyse issue, I will rule out something to … 
(He interrupted “ok, let’s suppose it’s I/O issue, but it’s million line code application, 
and could be thousands of part involves I/O, how do you solve the problem?)
Rong: For this huge application, troubleshooting needs deep understanding of the codes.
(He said: suppose you know the code very well, and suppose you wrote the code yourself.)
I thought for a while and cannot answer. (I guess he has a specific answer, but I just cannot spot it.)
He: it’s ok, let’s move on to next question.
Do you have any idea about what he want? And this is also a Indian. I tend to conclude that either Indian think in a way different from mine, or he intended to mess up the interview, because all interviewers who throw me a vague question and refuse to give further hints are Indians.

Fwd: MS IV 20141211

Question 1:
void transfer(Account accA, Account accB, double amount) {
synch(accA) {
sync(accB) {
}
}
}
There is a deadlock issue, e.g Thread1 transfer from accA to accB, and Thread2 transfer from accB to accA. How to fix this bug?
Question 2: 
class Trade
OptionTrade extends Trade
BondTrade extends Trade
SwapTrade extends Trade
Pricer
double getPV(OptionTrade trade)
double getPV(BondTrade trade)
double getPV(SwapTrade trade)
Trade trade = …//you got a trade instance
Pricer pricer = …//you got a pricer instance
//how to get price value of the trade
if(trade instanceOf OptionTrade) {
pricer.getPV((OptionTrade)trade) 
} else if(… instanceOf …) {
} else if (… instanceOf …){
}
He siad, this works, but looks he is not satisfied with this solution. He asked : “Is there a better way to do that?”
I cannot think of another way…, He followed with a question “what's polymorphism?”, so maybe the solution should be related to polymorphism.

Fwd: Bloomberg interview questions 2/13/2015 {XR

String getRegularExpression(String str1, String str2);
Base on input 2 strings, return a regex String that can cover 2 input strings.
e.g “Bloomberg”, “BloomingDale” should output “Bloom.*g.*”

I proposed a solution:
step 1: find out common segments of the 2 strings
step 2: insert “.*” in between the common segments to form a string

He asked: how to find the common segments?
also he let me think of below examples, but I really couldn’t find any
clue from his example.
“Bloomberg”, “BloomingDale”
“StarBucksCoffee”, “RedCoffee”

In the end, he said my proposed solution is not technically optimized.
Obviously, he has better solution, but he didn’t give me the hint.
So I still have no idea at all.

Can you think of a solution?

beware of creating reference to dereferenced pointer

In one sample code (p190 [[c++in24hour]]), we see that once you delete a pointer, the reference to the object becomes a dangling reference. More common when multi-threaded.

I guess sometimes we do create a reference to a dereferenced pointer, but we have standard guards to avoid dangling references. What are these guards? Not sure.

Reference param is best practice in c++. What if caller passes an unwrapped pointer into a function’s ref param? How do you ensure the underlying heap/stack thingy doesn’t get deallocated?
– Single-threaded — if the pointee is accessible only on this thread, it can’t possibly “vaporize” beneath my feet. The caller won’t (technically impossible) delete the ptr before the func returns.
– multi-threaded — all hells break lose. We need guards.

There are many similar multi-threading “delete” issues to be solved with ownership control. Only one function on one thread should delete.

memory leak in GUI event handlers – swing^c#

Here’s a common java swing memory leak as described on stack overflow — Essentially, because you register an object as a listener and forget to unregister, the notifier ends up holding onto the reference of the object, and leaks a bit of memory.

Same problem with c# events. [[effective c#]] refers to it as “runtime coupling despite compile-time loose coupling”. Recall an event
is a pseudo field in a class, and the fields’ type is a delegate, which is a list of 2-pointer constructs. First pointer usually points to a listener object. Imagine a bunch of large listener objects are added to the delegate’s inv list (registered for event), and one of them is no longer needed. You want its memory freed, but the event source object still holds a reference via the delegate instance. See [[effective c#]] item 23. One tip is to unregister in the listener’s Dispose()

I feel the dotnet event/delegate language construct has no exact java counterpart at the language level, but at runtime, swing event
paradigm == c# event paradigm. Fundamentally the same paradigm. Part of the paradigm is that the event source object holds a
collection of subscriber Objects. If the GUI stays up for 22 hours then the subscriber Objects are held “hostage” for that long, and
cannot be garbage collected.

haunted by negative workplace relations #YH

Hi YH,

I too get haunted by criticism, failed relationships (but not those sexual types;) with past coworkers, or my poor  judgement and decisions in past projects.

Q: Was I really as bad as accused?
Q: Did I make such an embarrassing mistake?
Q: Was I more than 50% responsible or there’s another person equally responsible? It takes 2 hard objects to have a clash.
In many cases, I find it tricky to answer these questions objectively, and identify where and how much of blame I deserve. I’m lucky to have a simplistic view —
      “I have always enjoyed good relationships with all my team members under the same manager. Everyone is friendly, nice or at least OK with me. Similarly, all my users liked me. Some colleagues and users even treat me as the best guy in my team.
In reality, if I examine every relationship maybe this is not 100% true, but i’m too lazy, so I never challenge this view. I keep repeating this view to myself and to everyone who asks. This loose view is a rather powerful protection when I feel “haunted”. This view may be naive but it’s an example of a healthy self-image IMO.
Note in this view I don’t single out my boss.  I don’t have such a perfect thing to say about relationships with my past bosses. Still I have another simplistic view that
         “Those managers I had problem with is an unpopular guy. Each has lost more than 1 team member due to the harsh mistreatment he gives. Each is hated by some team members and not respected by many. Basically, each is a difficult boss, but I actually managed to survive and adapt to them for longer than many fellow sufferers.
These simplistic views tend to protect my self-image. It’s important to me. They are like Guardian Angles. I hope they could work for you as well.

value-creation sectors – turn tech2highest profit

Notes on Raymond Teo discussion:  west coast shops … creating big value through high user base, high data, …..innovation is high risk — “risk premium”. In contrast, Singapore IT projects have a fixed “value” i.e. the project budget. ($1m is quite big.) Directly impacts IT salary.

Those “upstream” sectors often needs a smaller number of elite techies.The “upstream” don’t really exist in Singapore. Therefore, only a small elite of  techies in Singapore would end up in the financial IT domain. The vast majority of techies live in a totally different world and earn S$60k (up to $100k) a year as non-managers.

As I stated elsewhere, an mediocre techie easily earn a Wall St salary on Wall St, but the same guy would earn $60k in Singapore.
—–
Database/OperatingSys vendors enjoy highest margins (in silicon Valley) but no all Oracle clients get the same ROI buying oracle. Let’s compare the major client-industries that are using technologies. In which sectors does technology create the most profit? Note consumers are the largest user population of technology, but consumers don’t make profit and are not an “industry”, and (crucially) won’t pay us a salary. Our focus here is the major commercial sectors/industries using technology to make profit.

Telecom equipment makers make heavy use of technology and have good margin. Like the DB/OS creators, a small number of elite engineers create industry standards…. Anyway, here are a few sectors.

#1a) HFT or algo trading, either sell side or buy side
1a) other trading engines
2) risk engine, but is the calc really useful, relevant and accurate to be reliable?
2) settlement system can be just as critical and valuable to an i-bank

1b) search engine?
1b) facebook, linkedin, Amazon …

1c) DB/OS/language, as described above, is not a client industry, but DB/OS profit margin is higher than all other domains.
?) Atlassian

4) Telecom equipment maker, as described above
5) commercial banking, corporate/retail banking, insurance. Lower margin than trading, but higher than non-financial service industries. ecommerce like amazon, ebay…? I feel thousands of online services offer useful services but have low margin. B2B better than B2C.

#eor

telecom operators? I know a lot of operators (US or S’pore) don’t pay very high, partly because technology is at equipment makers. health care? logistics? no no no

using dB_t vs B_t in a formula

label – stoch

(dW is a common synonym of dB)

 

Whenever I see dB, I used to see it as a differential of “B”. But it’s undefined – no such thing as a differential for a Brownian motion!

 

Actually any dB equation is an integral equation involving a “stochastic integral” which has a non-trivial definition. Greg Lawler spent a lot of time explaining the meaning of a stochastic integral.

 

I seldom see B itself, rather than dB, used in a formula describing a random process. The one big exception is the exact formula describing a GBM process.

 

<!–[if gte msEquation 12]>St=S0exptm-s22+Bt s<![endif]–>

Greg confirmed that the regular BM can also be described in B rather than dB:

given <!–[if gte msEquation 12]>dXt=m dt+s dBt<![endif]–>

<!–[if gte msEquation 12]>Xt=X0+m t+s Bt<![endif]–>

This signal-noise formula (see other post) basically says random walk position X at time t is a non-random, predictable position with an chance element superimposed. The chance element is a random variable ~ N(mean 0, variance s2t).

 

This is actually the most precise description of the random process X(t).

 

We can also see this as a generalized Brownian motion, expressed using a Standard Brownian motion. Specifically, it adds drift rate and variance parameter to the SBM.

 

martingale – learning notes#non-trivial

A martingale is a process, always associated with a filtration, or the unfolding of a story.  Almost always [1]) the unfolding has a time element.
[1] except trivial cases like “revealing one poker card at a time” … don’t spend too much time on that.
In the Ito formula context, (local) martingale basically means zero dt coefficient. Easy to explain. Ito’s calculus always predicts the next increment using 1) revealed values of some random process and 2) the next random increment in a standard BM:
      dX = m(X, Y, …, t) dt    +   1(X, Y…, t)dB1      +   2(X, Y…, t)dB2 +…
Now, E[dX] = 0 for a (local) martingale, but we know the dB terms contribute nothing.
counter-example – P xxx [[Zhou Xinfeng]] has a simple, counter-intuitive illustration: B3 is NOT a martingale even though by symmetry E[B^3] = 0. (Local) Martingale requires
     E[B^3 | last revealed B_t value] = 0 , which doesn’t hold.

BM ^ GBM with or +! drift – quick summary

B1) BM with dB and drift = 0? the Standard BM, simple but not useless. A cornerstone building block of more complex stoch processes.

G1) GBM with dB and drift = 0? The simplest, purest GBM. The tilting function used in Girsanov theorem. See my blog “GBM + zero drift”

G2) GBM with drift without dB? a deterministic exponential growth path. Example – bank account. Used in BS and pricing.

B2) BM with drift without dB? a linear, non-random walker, not a real BM, useless in stoch.

B3) Now, how do we deal with a BM with both drift and dB? use G1 construct as “tilting function” to effect a change of measure. In a nutshell,

B3 –(G1)–> B1

G3) GBM with drift + dB? The most common stock price model.

from BM’s to GBM’s drift rate – eroded by .5 sigma^2

Let’s start with a regular BM with a known drift *rate* denoted “m”, and known variance parameter value, denoted “s”:
dX = m dt + s dBt
In other words,
Xt – X0 = m*t + s*Bt
Here, “… + t” has a non-trivial meaning. It is not same as adding two numbers or adding two variables, but rather a signal-noise formula… It describes a Process, with a non-random, deterministic part, and a random part whose variance at time t is equal to (s2 t)
Next, we construct or encounter a random process G(t) related but not derived from this BM:
dG/G = m dt + s dBt    …….. [2]
It turns out this process can be exactly described as
  G = G0exp[ (m- ½ s2)t  + s Bt ]     ………. [3]
Again, the simple-looking “… + s Bt” expression has a non-trivial meaning. It describes a Process, whose log value has a deterministic component, and a random component whose variance is (s2 t).
Note in the formula above (m- ½ s2) isn’t  the drift of GBM process G(t), because left hand side is “dG / G” rather than dG itself.
In contrast, (m- ½ s2) is a drift rate in the “log” process L(t) := log G(t). This log process is a BM.

                dL = (m – ½ s2) dt + s dBt    …… [4]

If we compare [2] vs [4], we see the drift rate eroded by (½ s2).
(You may feel dL =?= dG/G but that’s “before” Ito. Since G(t) is an Ito process, to get dL we must apply Ito’s and we end up with [4].)
I wish there’s only one form to remember, but unfortunately, [2] and [4] are both used extensively.
In summary
* Starting from a BM with drift = (u) dt
** the exponential process Y(t) derived from the BM has drift (not drift rate)
= [u + ½ s2 ] Y(t) dt
* Starting from a GBM (Not something derived from BM) process with drift (not drift rate) = m* G(t) dt
** the log process L(t), derived from the GBM process, is a BM with drift
= (m – ½ s2) dt, not “…L(t) dt”

BM: y Bt^3 isn’t a martingale

Greg gave a hint: . Basically, for positive X, the average is higher, because the curve is convex.
Consider the next brief interval (long interval also fine, but a brief dt is the standard approach). dX will be Normal and symmetric. the +/- 0.001 stands for dX. For each positive outcome of dx like 0.001, there’s an equally likely -0.001 outcome. We can just pick any pair and work out the contribution to E[(X+dX)3].
For a martingale, E[dY] = 0 i.e. E[Y+dY] = E[Y]. In our case, Y:=X3 , so E[(X+dX)3] need to equal E[X3] ….
Note that Bt3 is symmetric so mean = 0. It’s 50/50 to be positive or negative, which does NOT make it a martingale. I think the paradox is filtration or “last revealed value”.
Bt3 is symmetric only when predicting at time 0. Indeed, E[Bt3 | F_0] = 0 for any target time t. How about given X(t=2.187) = 4?
E[(4 + dX)^3] works out to be 4^3 + 3*4*E[dX^2] != 4^3

stoch integral – bets on each step of a random walk

label – intuitive
Gotcha — In ordinary integration, if we integrate from 0 to 1, then dx is always a positive “step”. If the integrand is positive in the “strip”, then the area is positive. Stoch integral is different. Even if integrand is always positive the strip “area” can be negative because the dW is a coin flip.

Total area is a RV with Expectation = 0.

In Greg Lawler’s first mention (P 11) of stoch integral, he models the integrand’s value (over a brief interval deltaT) as a “bet” on a coin flip, or a bet on a random walk. I find this a rather intuitive, memorable, and simplified description of stoch integral.
Note the coin flip can be positive or negative and beyond our control. We can bet positive or negative. The bet can be any value. For now, don’t worry about the magnitude of the random step. Just assume each step is +1/-1 like a coin flip
If the random walk has no drift (fair coin), then any way you bet on it, you are 50/50 i.e. no way to beat a martingale. Therefore, the integral is typically (expected to be) 0. Let’s denote the integral as C. What about E[C2] ? Surely positive.  We need the variance rule…
Q: Does a stoch integral always have expectation equal to last revealed value of the integral?
A: Yes. It is always a local martingale. If it’s bounded, then it’s also a martingale.

order routing inside an exchange #Nsdq

A major stock exchange’s job spec mentions that the exchange actually runs an internal SOR.

I thought only trading houses maintain SOR. Now I know that when an order (probably a market order) hits a stock exchange NDQ, NDQ may need to route it somewhere else. Not sure if it’s internal or external destination.

My friend Alan said all 13 U.S. exchange receive a live NBBO feed. Based on that, ABC can “forward” the order to the “best” venue.

change of measure, learning notes

See also — I have a long MSWord doc in my c:\0\b2b

Key — Start at discrete. Haksun’s example on coin flip…. Measure-P assigns 50/50 to head/tail. Measure-Q assigns 60/40 weights. Therefore we can see dQ/dP is a function (denoted M ), which maps each outcome (head/tail) to some amount of probability mass. Total probability mass adds up to 100%.

Requirement — the 2 measures are equivalent i.e. the pdf curve have exactly the same support. So M() is well-defined [1]. In the continuous case, suppose the original measure P is defined over a certain interval, then so is the function M(). However function M isn’t a distribution function like P, because it may not “add to 100%”. (I guess we just need the Q support to be a subset…)

Notation warning — V represents a particular event (like HT*TH), M(V) is a particular number, not a random variable IMO. Usually expectation is computed from probability. Here, however, probability is “defined” with expectation. I think when we view probability as a function, the input V is not a random variable like “X:=how many heads in 10 flips”, but a particular outcome like “X==2”.
Now we can look at the #1 important equation EQ1:

Q(V) := Ep [M(V) 1V] , where Ep () denotes expectation under the original Measure-P.

This equation defines a new probability distro “Q” using a P-expectation.

Now we can look at the #2 equation EQ2, mentioned in both Lawler’s notes and Haksun:

EQ[X] = Ep [ X M(X) ]

Notation warning — X is a random variable (such as how many heads in 10 flips), not a particular event like HT*TH. In this context, M(X) is a derived RV.

Key – here function M is used to “tilt” the original measure P. This tilting is supposed to be intuitive but not for me. The input to M() can be an event or (P141) a number! On P142 of Greg’s notes, M itself is a random variable.

Next look at a continuous distro.

Key – to develop intuition, use binomial approximation, the basis of computer simulation.

Key – in continuous setting, the “outcomes” are entire paths. Think of 1000 paths simulated. Each path gets a probability mass under P and under Q. Some paths get higher prob under Q than under P; the other paths get lower prob under Q.

The magic – with a certain tilting function, a BM with a constant drift rate C will “transform” to a symmetric BM. That magic tilting function happens to be …

I wonder what this magic tilting function looks like as a graph. Greg said it’s the exponential shape as given at end of P146, assuming m is a positive constant like 1.

In simple cases like this, the driftless BM would acquire a Positive drift via a Positive tilt. Intuitively, it’s just _weighted_average_:

* For the coin, physical measure says 50/50, but the new measure *assigns* more weight to head, so weighted average would be tilted up, positively towards heads.
* For the SBM, physical measure says 50/50, but the new measure *assigns” more weight to positive paths, so the new expectation is no longer 0 but positive.

[1] This function M is also described as a RV with Ep [M] = 1. For some outcomes Q assigns higher probability mass than P, and lower for other outcomes. Average out to be equal.

[17]U.S.hunt priorities #400w

To optimize for income, I would leverage on my 1) analytics 2) threading 3) SQL (+ possibly algo) expertise. Importance of income:

  • health insurance — will need for kids for sure
  • first few gigs might be low rate, given the dry season
  • home purchase in 5Y — confirmed requirement. If I want short commute + Chinese community, then price will be high
  • might go without income longer, like a few months
  • initial set-up cost — 5k-10k, but at this level adjustment on wife’s part will be tough. Even a 20k relief fund is drop in a bucket. Need 100k.
  • tail risk — I might come back to SGP sooner (like end of 2017) and take a low-pay job
  • tail risk — if GC process goes astray, I may go back to SG without a GC, so the X years I spent here I need to earn enough.

May not have much of a choice, given the slow c2c market right now.

My 2017 priorities:

  1. avoid churn? so avoid web, javascript, in-memory DB, spring/hibernate and most of the new technologies I hear about the west coast
  2. muscle-building contexx? so avoid java/sql? Better to deepen my c++ as a 2nd front. Willing to take lower salary? LG2 can postpone this to 2018/2019. See post on re-enter c++
  3. my c++ learning is reaching a critical mass
  4. —- unsorted lower priorities —-
  5. income to keep me feeling secure and self-respecting. I got this from the offers!
  6. flexibility to work from Singapore. Can spend more time with wife, parents and kids.
  7. location for upcoming home-purchase
  8. unlock new markets — west coast, c++, data science ..
  9. commute?
  10. chance to impress manager
  11. leisure time to exercise, improve c++, call home, learn driving etc

My ideal (yet realistic) 1st project:

  • slightly below (like 80%) my capacity. Chance to impress manager due to my specialty knowledge. “These managers could make things happen”.
  • has spare capacity to check out the potential homes
  • salary? LG2 like $65/hr
  • c++ or java
  • possibly west coast but the high rate is usually for FTE.

Alternatively, a temp contract to try c++ again, but only after I clear some high-end java interviews to build my confidence in earning capacity.

  • low salary like 120k
  • hands-on c++ (not C) on a large codebase to build mileage
  • NY or west coast or anywhere else