## c++ know-how for coding IV

## c++ know-how for coding challenge

cStr and std::string

array, vector, sorted data structure (i.e. stl map), unordered_map

stack, queue

pointer arithmetic

iterator – basic usage

shared_ptr

Node class used in a linked graph

dtor, copier, op=

ref

double pointer

adv: matrix

adv: circular buffer

no exception

no stl algo

no pointer to function

no template

no (very, very seldom) threading

## c++topics seldom quizzed

(master -> pearl)

some low-level details I thought would be popular but seldom asked:

* L-value

* iterator types and implementations

* static variables outside classes

* implicit acts of magic by compiler

* array and cStr – syntax, memory, ... the gory details beyond the basics

* template specialization

* ref/pointer typedef inside  templates

* non-dummy-type args in template

* MI

* enum

* exception spec

* C integration
* pimp

* fwd declaration

* namespace

* linker

* extern

* double pointers

* hiding rule

* swap – all the important usages and no-fail

* overloading and  method resolution

* casting and conversion

*** OOC and  conversion ctor

-- "mid-level"

* boost Any vs Variant

* i/o stream

* regex

* file access (including random)

* serialization

* memory leak detection

* details of boost thread

* boost smart pointer beyond the shared_ptr

* std::string details

Most algo interviews don't care about efficiency

Most challenging algo interviews (onsite) are really about "solve it by hook or by crook" regardless of efficiency. (Usually there isn't, but if there's an obvious brute-force solution it gives you no credit anyway.)

In the toughest algo questions, usually there's no memory capacity issue to worry about.

Occasionally, interviewer stipulates O(N logN) or O(1)

Once we solve it we can improve efficiency. It's a second phase. Can be easier than first phase.

In that case threading, sorting ... are unimportant. Instead we need judicious use of trees, recursions, pattern recognition... and very clear thinking.

See [[EPI300]] and the green book by Zhou Xinfeng

London bbg IV

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.

DRW IV

a vector needs to allocate N instances of Account but Account has no default ctor. How does the compiler achieve it?

A: indeed the call to array new would prevent the vector<Account> concrete class from compiling due to SFINE rule or something like that. (Java and c# would use type constraints instead.) The compiler must be using 2 separate lines – one to allocate raw memory, the other to initialize the object.

 

However, when is vector internal array allocated by array new? I discussed with Ashish but found no answer.

 

Q: why do you need to write your own smart ptr?

A: super simple one, just to deal with some issue of the raw ptr... probably dangle pointer, by overriding the deref operator?

 

Q: why use unique ptr when shared ptr is general purpose

A: threading...

 

Q: is the lambda functionality doable in c++98? what is the c++98 equivalent?

 

Q: OK you don't use c++11 at work, but do you hack around at home?

 

Q: why is  the bid/ask spread much wider in options than the underlier?

A: must be the risk to the writer. Competition didn't drive down the bid/ask spread like it did in FX and cash equities.

AA: delta hedge adjustment can't be done every second. Before the next adjust, the risk to the writer (market maker and quoter) would be quite high.

 

sticky## c++weakness revealed by interviews(+projects)

See also pearl post on "sticky:High-end c++ developer interviews tend to beat us in 2 ways"

Relative to java/c#, c++ questions are more low-level (often using non-OO constructs). This is generally my strength.

I used to feel confident I can see patterns in tech interview questions and figure out what specific types of knowledge is required at a certain seniority. I was fairly successful with java/SQL/c#, but less so with c++. Based on the past questions i'm trying to make out the patterns.
=======weaknesses revealed by interviews. Probably need more work experience
(No one tested me on MI, template wizardry, etc)
STL useful tricks (like swing) -- Shanghai, synechron, Jap, WQ
specific threading constructs/techniques -- sapient, jump, SCB
boost -- jump, Jap, synechron,
mem management/optimization (like heap-only classes) -- barc-mtg, nQuant
[lg] socket -- nquant
firm grasp of language features (like rvalue ref) -- 3Arrow, bbg
essential class-based techniques/constructs (eg ref counting) -- Miami, espeed, nQuant,
[lg] COM - Barc RnA
c++11 features - DRW, 3arrow
initializing common data structures like arrays, vectors, classes -- needed in a lot of coding challenges

==These are harder to self-study -- too specialized and no pointers
linux (instrumentation) tools like truss, LD_library_path -- jump, Miami, nQuant
[lg] essential/deeper know-how (signals, OOM, stack size) not expected of a junior developer ...-- jump, Japanese, nQuant, 3Arrow, barc-mtg
[lg] extreme low-level optimization (CPU cache, custom-RTTI, byte alignment, placement new) ..-- Miami, nquant, jump

=========much-needed practical skills not quizzed by IV
pre-processor tricks
python integration
makefiles, continuous build
pthreads
debuggers,
memory leak detectors,

AOC c++ iv (Jens/Ruban)

Q: buffer overflow?

%%A: avoid arrays, use vector

A: a big topic -- http://www.dwheeler.com/secure-class/Secure-Programs-HOWTO/buffer-overflow.html

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

what's wrong with pointers?

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.

A: http://google-styleguide.googlecode.com/svn/trunk/cppguide.html?showone=Exceptions#Exceptions

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: 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"

bbg C++ 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
17. Linux (Windows doesn't work, it's difficult to test the person since we don't know Windows)
18. Multithreading
19. TCP/IP and Multicast
20. STL and Boost libraries

sticky:High-end c++ interviews tend to beat us in 2 ways

(master copy -> pripri)

bbg algo IV - binary tree inorder walk

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 inorder 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 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

IV c++11 (3arrow)

Q: In a move constructor, is the parameter an rvalue reference? is there another rvalue reference in the call?

Q: What's an rvalue reference actually?

Q: mutable keyword's usage? How about in c++11?
AA: closure - captured variables can be modified if "mutable".
http://stackoverflow.com/questions/105014/does-the-mutable-keyword-have-any-purpose-other-than-allowing-the-variable-to

Translation lookaside buffer

What part of the boost thread library did you use?

for-loop in c++11?

Why did you implement your own smart pointer?
A: to avoid uninitialized primitives? That's a wrapper not a smart ptr

noexcept
AA: both an operator and a function specifier...

Can ctor throw exception? Why do you say it's not best practice?

How does a vector resize?
A: after copying the objects, destroy the old objects. (move ctor?)

What kind of algo is qsort? Average and worst runtime complexity?
A: average nLog(n), worse n^2

Recursive vs iterative, which is faster?
A: comparable, but space complexity lower for iterative?

what's lockfree? How did you make it work in your projects?

How did you use parallel processing in GS?
A: data parallellism, threading, and other techniques. Coarse-grained is ideal.
A: i guess pipelining parallellism is also relevant, using task queues

advanced c++ interview 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: 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: 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: 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?

CompletionService + others (Credit Suisse IV

Other threading questions.

safe publication
fail fast vs fail safe
timers (scheduled task queue, scheduled thread pool)
3 ways to create threads
how to shut down a multithreaded app
handle all exceptions in a thread pool?

Fwd: Markit phone interview, full time position, 10/13/14

---------- Forwarded message ----------
Date: Tue, Oct 14, 2014 at 4:02 AM
Subject: Markit phone interview, full time position, 10/13/14

Which Java package do you particularly like?

To design a cache framework, in such a scenario, you have already 50 objects in the map, that's its capacity. Now 51st object comes in, you have to remove the first object in the cache (this implies the map is sorted) to make room for the new comer. How do you go with that?

The answer is to use LinkedBlockingQueue as the map's placeholder

What's weak reference? Explain how GC works? Do you know any GC algorithm? If to choose one GC algo for your application, how do you set the JVM parameter?

Java Serialization. If there is a serializable Singleton to be wired from one JVM to another, what do you do to guarantee the other JVM to have only one instance of the Singleton class v.s multiple instances?

Threadpool. Can you set the max size of a threadpool? How do you go about it? What if the max size is 10, what will happen to the new coming task but not serviced? What is the queue used in Thread pool? What if the queue is full? Why uses block queue?

Database. How do you detect deadlock in database? How do you read Threaddump?

Database. If you were handed with a complex query running against 10 tables, and there is a performance issue, how do you proceed to resolve it? Have you used Execution plan?

Fwd: Barcap onsite interview, 10/09/14

---------- Forwarded message ----------
Date: Fri, Oct 10, 2014 at 7:56 AM
Subject: Barcap onsite interview, 10/09/14

Coding, no pseudo code, must be workable code. On paper.

1. Read a file, find out the occurrence of the alphanumeric letters, like "122113, Hello world", returns 1:3; 2:2; 3:1; H:1;e:1; l:3; o:2; r:1;d:1

2. find out if a string brackets come in pairs. For example, "[{}]{([])}" will return true, but "[(])" will return false;

An algo: from an array of length of n, pick up m elements randomly, m<=n. Must be no dups, meaning once an element has been picked, it can't be picked again. Best way to implement it.

In an extreme, for a length of 1000, pick up 999 elements.

A bunch of multi-choice stupid Java questions, like "What's AWT stand for"

Some designing questions, how to implement N-Tiers applications; What's its pro and cons;

What's it that you don't like about Java? 

This is just some open discussion: my answer was that Java is now too huge a monster that tries to please everyone, which is against its original philosophy of simplicity. And I gave example of lamda expression, and multiple inheritance in Java 8, which is the center of debates. 

Then he asked if w/o lamda, how to do functional programming in java? and my answer was that other JVM language such as Scala can do it just fine or even better since it's created for that purpose. Also since it's in JVM ecosystem it can fit in seamlessly.

How to sync up with database in Hibernate?

Discussion:

What's asynchronous IO? How to achieve highly efficient concurrent processing services. 

I couldn't impress him as I didn't know it but it seems that I managed to get his attention by mentioning the emerging technologies such as Node.js, which is designed for that purpose

In a scenario, we have 10 requests being handled by all available threads in a thread pool, they are long processing tasks, thus more requests come in but can't be processed, then what? How to design an architecture that can prioritize the requests so that clients can have reasonable responsiveness.