DMA low latency interview (European bank Midtown

Q: Given a 32-core machine and a lot of CPU-bound calculations, how would you size your thread pool?
A: First, find out how many kernel threads — probably 32 * 2 or 4. i feel if tasks are IO intensive like waiting for a pricing or risk assessment from JMS, then a lot of threads would be waiting for IO. If each thread spends 90% of its time waiting for IO, then each cpu should handle 10 threads roughly. This way, each thread after getting the data needed won’t need to wait to get CPU.

The below questions were probably not prepared in advance.

Q1: for a one-direction linked list of size N, efficiently find the item at Position floor(N/2). Positions are 1 to N. You don’t know the size until you finish scanning.

Q2: for a strictly sorted binary tree of numbers, I give you a pointer to the root node and 2 arbitrary numbers in the tree, find the lowest common ancestor node. The only entry point is the root node address. The 2 input numbers are passed by value and guaranteed to exist in the tree. Note for this binary tree, any node on my left are less than me.

Q3: efficiently reshuffle a PokerCard[52] array. You can call a rand(int max) function to get a random number between 0 and max.
Tip: avoid “retry” as that wastes CPU
A: i think we need to call rand(51), rand(50), rand(49)….

Advertisements

recursive tree walk -> iterative #barcap

Suppose there’s a deep directory tree (no hard/soft links) with millions of files and directories. Write a tree walker to list files excluding directories. For memory efficiency, turn the recursive algorithm into iterative.

I feel recursive thinking is far more powerful than iterative, because it solves problems otherwise unsolvable. Most classic algo problems fall into this category. I always try to train myself to think recursively. In this regard, It’s good to study and compare iterative algorithms. What kind of recursive algo can be converted to iterative? I feel only simple ones.

Inspired by the article in the link, here are my rules for converting recursion to iteration

Rule: one push (on the stack) per call of the recursive func.

Rule: a stack to hold the arg of the recursive calls, in the correct order. Assuming m(1) -> m(2) -> m(3), then we should push 1,2,3 on the stack. Ideally, the order in our stack should match the recursive call stack.

Rule: since it’s a stack, you remove from the top and add to the top too.

Rule: first step when you reenter the while(not_empty) loop, you simulate a new recursive call by _popping_ the stack. The popped item is no longer a “pending” todo item.

Next Question: how to parallelize? You don’t know how deep each sub-tree is.


public class LowLatencyTreeWalker {
static java.util.LinkedList envelopesToOpen = new java.util.LinkedList();

static void factorial() { // a simple iterative solution to compute
// factorials
envelopesToOpen.add(6);
long ret = 1;
while (!envelopesToOpen.isEmpty()) {
int currNum = envelopesToOpen.removeLast();
System.out.println(ret = ret * currNum);
if (currNum > 1)
envelopesToOpen.add(currNum - 1);
}
}

static void walkTree(String args[]) { // a harder iterative algorithm for
// tree-walk
envelopesToOpen.add(new File("C:/"));
while (!envelopesToOpen.isEmpty()) {
// once we open an envelope, we remove from the todo stack
File f = envelopesToOpen.removeLast();
System.out.println(f.getAbsolutePath());
if (f.listFiles() != null)
envelopesToOpen.addAll(Arrays.asList(f.listFiles()));
}
}
}

const overloading — needed in these cases

volatile and const are 2 keywords treated specially.

typedef …. my_iterator;
typedef …. my_const_interator;

my_iterator begin();
my_const_iterator begin() const;

Are we looking at method-overloading? yes due to the const. Note the return type is ignored when overloading.

The c++ const correctness article explains the motivation of const overloading. Here’s my explanation. Suppose you have 2 variables of MyType, one const var (call it varC), the other non-const var (call it var2). Suppose MyType has a non-const getter method. How would you call getter on varC ? Won’t compile[3]. You need to “const overload” the getter. So the 2 overloaded getters differ only in constness. How does compiler resolve the call? varC.getIt() would call the const getter; var2.getIt() would call the mutable getter.

[3] varC is a const “handle” on the object, so compiler promises not to modify the object state through this handle. Compiler won’t pass the unsafe (ie mutable) message getIt() to the object through this handle. Doing so creates the possibility of state mutation via a const handle.

http://www.parashift.com/c++-faq-lite/const-correctness.html#faq-18.12
gave a good coding convention, and gave detailed and simple examples.

Fred const& operator[] (unsigned index) const; ← subscript operators often come in pairs
Fred& operator[] (unsigned index); ← subscript operators often come in pairs

Annoying trivial exceptions when debugging apps in Eclipse/MSVS

My eclipse debugger always stops at URLClassPath$JarLoader. Solution – Try turning off Window>Preferences>Java>Debug>Suspend execution on uncaught exceptions?

For MSVS, I find it extrememly useful to turn on “break on exception” but some exceptions like System.TypeLoadException are useless. To disable them, Debug->Exceptions->Find and uncheck the specific exceptions

pbref between const levels (const radiates left

When you pass an arg  into a function param by reference, check the const-ness of LHS vs RHS. This post is about when they differ const-wise. Note the most common and tricky situation is func pbref (ie pass-by-reference). A programmer needs to recognize them without thinking. The assignment operations below are less common but simpler.

Note — in pbref, on LHS we sometimes create a completely new ref (4-byte) with(out) const-ness. This ref has its (unknowable) new address. This address is different from address of the RHS (which must be a lval — u can’t do int& r = 4444).

I feel a const stackVar is a const object. There’s no other way to get at the object, since the const var blocks all [3] edits.

Q: Given f(const int & i), can you pass in an arg of non-const int variable?
A: yes. Const LHS is tolerant and extremely widespread[1]. The pbref process adds constness to the new LHS reference. Equivalent to the simpler but less common

int arg = 9;
const int & a = arg;

Q: Remove const — Given f(int & i), can you pass in a const int variable?
A: illegal. The arg variable is const, so it promises not to modify state. The pbref process attempts to remove the constness. Equivalent to the simpler but less common

const int arg = 9;
int & a = arg; // illegal

In summary, Const-ness radiates from RHS to LHS. Illegal to block it.
* If RHS is a const ptr to a mutable object, then that constness doesn’t radiate left-ward
* If RHS is any handle[2] on a const object, then yes that constness radiates left-ward.
* If RHS is a handle on a mutable object, then LHS can be anything.

sound byte– if you have only a handle on a const object, then you can’t [3] modify its state even if you copy that handle. Object is not editable *via* this handle.

sound byte — If a (method or) variable is declared without “const”, compiler assumes this “handle” (can and therefore) will modify object state.

Compiler disallows assigning a const RHS handle to a mutable LHS handle. “Handle” is typically a ref. (For a ptr, “const handle” means ptr-to-const). However, if you deep-copy a target object (not the 4-byte address), then const-ness doesn’t radiate left. You can make a mutable deep copy from a const object, without compromising const-ness of the RHS object. All subsequent “edits” happen on the deep copy.

Tricky context — Constness still radiates leftward upon method-calling, because we perform a

implicit_this_param = & handleObj; //LHS is const param IFF a const method

  • constObj.constMethod() // good
  • constObj.mutableMethod() // won’t compile
  • mutableObj.constMethod() //good

Q: need to explicitly remove constness of a q(const char *), which is a c-string
A: Yes. Constness radiates left. Use const_cast. See post on const char *

[1] copiers and assignments usually have const ref params.
[2] handle can mean a nonref variable or a ref/ptr
[3] except via explicit const_cast

(below is a piece of work in progress….)
Now we can better understand why auto_ptr is bad for containers. Given an auto_ptr object A. A’s copier and assignment both take a non-const RHS. Container functions need copier with const param ie a const LHS, but
* can they enforce that copier LHS be declared const? No. If you could then auto_ptr + container would have been illegal combination??
* can they enforce that copier RHS be declared const? No compiler can’t enforce it — const radiates left. Compiler can only enforce LHS to be const.

FIX session msg vs session tags

The “content” of FIX data is surrounded by session related data, including session Messages and session Tags. As a beginner, I was a bit confused over the difference between session Messages vs session Tags

A) There are very few (5 to 10) session message types, such as heart beat, logon/logout, request for resend…
** All the types — session msg subtypes or app msg subtypes — show up under Tag 35.

B) In ANY (session/app) Message, there are session-related Tags such as (34)seqNum, (10)checksum, (9)bodyLength, (52) timeStamp, encryption. I’d say even the all-important (35)MsgType tag qualifies as session tag.

In fact, application data are “surrounded” by session data. App data are the stars of the show, surrounded by a huge “supporting crew” —
– A session msg’s fields are 100% session-related;
– An app msg is not free of session information. It is partly a session msg — due to those session tags.
– If you snoop the conversation, most messages are session messages — heart beats
– every business data exchange starts with and ends with session messages — logon and logout.

append/removeLast on c#delegate inv list

Note — inv list is like an ordered list. Order is the invocation order. Invocation is strictly sequential.

— Based on http://www.yoda.arachsys.com/csharp/events.html
Like java String, Delegate objects are Immutable — always. Seehttp://msdn.microsoft.com/en-us/library/system.delegate.aspx. Personally, I interpret this rule in terms of the invocation list. (a delegate object’s state is nothing but the inv list.)

Like java String, Delegate concatenation (implicitly using Delegate.Combine()) produces new objects, leaving original objects intact.

  d1 = d1+d2; // appends d2 to the end of d1, both are potentially lists of single delegates.
  d1 += d2; //same thing

Like java String, such assignments __Reseat__ d1 to point at the new object, keeping original objects immutable
Like java String, the “+” operator Appends to the end
Like java String, you can add [d1,d2] + [d2] to get [d1,d2,d2] with duplicates!
Unlike java String, you can Remove too. This illustration is worth 1000 words —

Expression Result
null + d1 d1
d1 + null d1
d1 + d2 [d1, d2]
d1 + [d2, d3] [d1, d2, d3]
[d1, d2] + [d2, d3] [d1, d2, d2, d3]
[d1, d2] – d1 d2
[d1, d2] – d2 d1
[d1, d2, d1] – d1 [d1, d2]
[d1, d2, d3] – [d1, d2] d3
[d1, d2, d3] – [d2, d1] [d1, d2, d3]
[d1, d2, d3, d1, d2] – [d1, d2] [d1, d2, d3]
[d1, d2] – [d1, d2] null

Here’s a bit of the official MSDN spec (adapted) —
The invocation list of a delegate instance is an ordered linked list of what I call “singles”. An invocation list can contain duplicate methods. During an invocation, methods are invoked in the order in which they appear in the invocation list. A delegate attempts to invoke every method in its invocation list; duplicates are invoked once for each time they appear in the invocation list. Delegates are immutable; once created, the invocation list of a delegate does not change.

void ptr && TYPE of ptr

P197 [[nitty gritty]] points out that at compile time and/or runtime, “system” knows the type of each ptr object. One exception is the void ptr, whose type is undefined.

“Pointer object” means the 4-byte ptr object. This object could be a field of a class object; or a stackVar, or a global var.

Obviously as a pointer this variable holds an address. This address should[1] be another object. The type of the pointee object is the type of the pointer. System remembers each pointer’s type. That’s why pointer cast is a controlled operation. A compiler need this type information to allocate memory.

What if the pointee is a derived object? See the post on AOB (ie address of basement).

In conclusion, a ptr object
* has an address of its own
* holds an address unless it’s a null or uninitialized pointer
* has a type unless it’s a void ptr
* has a name ie the variable name
* has an optional pointee-name — qq(Cat * cptr = &myCat; ). Pointee could be on heap or stack. If it’s on heap, the pointee object is always nameless but myCat could be a name attached to it subsequently.

[1] if dangling, then the pointee could be another stackframe, or any used/unused heap address.

anctionListener Instance may(not) be a jcomponent (stateful

A) I have seen many examples where we subclass a jcomponent and implement ActionListener. See http://docs.oracle.com/javase/tutorial/uiswing/events/actionlistener.html

B) There are also numerous (simple) examples where you create an anonymous stateless subtype of ActionListener, but do not subclass jcomponent. See http://stackoverflow.com/questions/1346978/java-using-an-actionlistener-to-call-a-function-in-another-class-on-an-object-f

I think it’s a common misconception to assume a listener is typically a jcomponent or a listener is usually separate from any jcomponent, but those are wrong thoughts.