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)….

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

Update, here’s an example of a session-related business message: 35=3

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

A) There are only a few (I guess 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 (3 to 30) session-related header tags such often routing-related, such as (34)seqNum, (10)checksum, (8)beginString, (9)bodyLength, (52) timeStamp, encryption. I’d say even the all-important (35)MsgType tag qualifies as session tag.

Most of the standard header tags are optional.

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 — heartbeats
– 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.

allpages locking ≠ table-level locking

Nikhil,

http://infocenter.sybase.com/help/index.jsp?topic=/com.sybase.dc20021_1251/html/locking/locking7.htm

Allpages locking locks both data pages and index pages. When a query updates a value in a row in an allpages-locked table, the data page [1] is locked with an exclusive lock. Any index pages affected by the update are also locked with exclusive locks.

[1] not the entire table

MS iview

Q: what’s your take on stored proc vs dynamic sql?

Q: If there’s an outOfMemory, how do you identify root cause and resolve it?

Q: Any clue on memory leak?

Q: front-end — how do u implement securiy?

Q: If login failed, what do you show on the page?

Q: how do you prevent sql injection

Q: how do you prevent javascript injection

y invokeLater() important to swing (creditx

A Creditex Swing developer explained to me that UI redraw is an operation happening on the dispatcher thread. This thread should be the only thread that modifies UI objects, otherwise the screen may get messed up by uncoordinated concurrent updates.

Suppose you have an onMsg() listener triggered by market data.  This onMsg() obviously runs in it’s own thread, which blocks until waken up by incoming message. If a naive developer decides to modify some JTable object in onMsg() thread[2], and at the same time another timer thread is also updating the JTable, and the event-dispatcher thread is redrawing the screen … display will change in unexpected ways.

In WPF, every UI control is owned by the UI thread ie the dispatcher thread, according to Longbo — Good simplification. No other thread can modify UI controls, though they can modify the data binding (models?) behind the UI controls. To effect a change on UI, other threads must go through dispatcher thread as the choke point of control. I was told this is done by some event publication model, probably with INotifyPropertyChanged.

[[Learning java]] shows swing has a single event queue — see my post on async buffer. If UI thread is in the middle of some long calculation when you publish, then synchronous call is not possible. In fact, synchronous call would mean the event sender thread is the only thread involved, which is the scenario [2] above.

python exec keyword ^ eval() function

Based on my experience in other scripting languages, I don’t think these are widely used in everyday scripting, but veterans must know.

– exec is a keyword[1] and not a function so can’t return a value.
– eval() is a function so returns a value.

Both accept a string “argument”, or (more advanced) code object from compile() function.
[1] Other keywords include while/for/lamda and raise/try/except — note “except” is like “catch”

See P90 [[py ref]]

3 essential JGC actions af marking

In this write-up, let’s put aside “live vs dead” object marking, and focus on actions after marking. Across all the GC engines as of java 5, there are only 3 post-deallocation actions.

C) copier action young generation
Coping needs a “destination” space in the form of the survivors. So copier is inapplicable to oldgen

S) sliding compaction action => oldgen
F) non-relocating free-list action => oldgen

(notation — the arrow sign “A=>B” means “A requires/implies B”)

Among the 3, C and S create “frontiers” to support fast allocation at the expense of long pauses. F offers low-pause but fragmentation.

Among the 3, C is always young gen. S and F are always oldgen.

Once you are clear about these 3 GC actions, you understand a lot of jargons such as

mark-and-sweep
mark-and-compact
concurrent GC
low-pause
promotion failure

Nomura java/sql iview

Q: If you keep Employee.java instances in a list, how do you keep the list sorted on Employee.firstName? What if you can’t modify Employee.java source code?
%%A: define a new comparitor class

Q: what kind of messaging designs do you know?
A: multicast (RV) vs non-multicast; durable vs non-durable; point-to-point vs pub/sub

Q: can a message consumer subscribe to multiple topics?
A: single-thread model. each session has a dedicated thread?
(Interviewer said there are ways around it.)

Q: perl advantage over shell script? what can perl do that shell script can’t?
A: (I said on the spot) IPC, unicode, creating threads, OO, socket server
Now i think i can add — DB access, network access

Q: A text file contains 200 tab-delimited lines like “Stock1 $100n”. Write a shell/perl script to print the 10 most expensive stocks.

Q: write a shell/perl script to kill a unix process named Prc1, assume Prc1 is a unique process name.

Q: write a full singleton class. Don’t omit anything.

Q: write a LinkedList class with a reverse() method to reverse the list in-place. How about an ArrayList or a Vector? You are allowed to create your own Node class in the LinkedList.

Q: write the code to reverse a String without using String.reverse()

Q: what’s the benefit of hashing in a hash table? What’s wrong with a million bucket holding one entry each?
A: without hashCode, how do we save an entry in an array? I feel a million entry without collision is gr8.

—SQL

Q: for SQL what’s the advantage of clustered index over regular indices?
A: range select; avoid insert hot spot; probably the fastest index(?) I have a post in http://bigblog.tanbin.com/2007/07/clustered-index.html

Q: select * from tableA, tableA (TableA has 10 columns and 10 rows) How many rows and columns do u get?

Q: select * from tableA, tableB where…
TableB has 20 rows. What where-clause can u use to get the minimum/maximum resultset?

Q: Table C has Stock and Price columns. Select the 10 most expensive stocks

Q: (multipart SQL question)
select entity=’EntireBank’, minCode=1, maxCode=24 into e — entity table
insert e select ‘FI’, 2, 12
insert e select ‘mortgage’, 3,4 — a desk
insert e select ‘muni’, 5,6 — a desk
insert e select ‘repo’, 7,8 — a desk
insert e select ‘eq’, 13,23
insert e select ‘US’, 14,15 — a desk
insert e select ‘Japan’, 16,17 — a desk
insert e select ‘eqFutures’, 18,19 — a desk

select entity=’mortgage’, PL=-281 into pl — 281 millions Loss
insert pl select ‘muni’, 81
insert pl select ‘repo’, 100
insert pl select ‘US’, 709
insert pl select ‘Japan’, -555
insert pl select ‘eqFutures’, 90

You can roll up trading desk P/L into department P/L, and roll up department p/l into bank p/l. Now there are 3 roll-up levels, but system will support 10 roll-up levels.

For example, FI department P/L = -281 + 81 + 100 = -$100 million

Task1: design the java classes, important method signatures, queries … to support ad-hoc report P/L for any entity. Analyze performance, scalability,

Task 2: write a query to list all entities and number of desks within.

Task 3: write a query to show all level-2 entities (departments) and their P/L

heap allocation +! malloc()

Someone speculated that “in any programming language, heap memory is allocated always using the C function malloc(). There’s no alternative.” Nigel (Citi) disagrees. If a language is not based on C, then it can use its own heap-management library.

The heap-mgmt library is a wholesaler/retailer. For efficiency this library requests large blocks [1] of memory and gives out small chunks to the application. Probably many languages have a heap-mgmt library. C’s heap library (in glibc) uses malloc(). Nigel felt C# has its own heap-mgmt library and may have a malloc-equivalent. JVM is written in C but it could re-implement the heap-mgmt library with its own malloc-equivalent.

Everyone must file tax returns with the same government, but through different tax consultants. Tax consultants are not part of the government. Similarly, Heap-mgmt library is one level above system calls. It makes system calls (perhaps brk()/sbrk()) to request the large blocks from OS. Every language must use system calls to request memory but possibly using its own heap-mgmt library.

JPMC IV #stock loan

Q: concurrent hashmap locking — locking on an internal bucket object or a map entry object?

Q: a weak reference object can have a finalize()? What if in finalize() you make the object “reachable from the GC root set”?

Q: when do you use WeakHashMap?

Q: what’s a phantom reference?

Q: static fields during serialization?

Q: how do you make a hashmap (not a hashtable) thread safe?

Q: how does jms provider keep track of which message has not been delivered to each durable subscriber?

Q: different modes of acknowledgment in JMS? what’s the default mode?

Q: what’s JMS correlation id?

Q: how does a java app know a file is already open for writing by another unix process id, so it should wait and avoid concurrent edit?
A: see https://www.thegeekstuff.com/2012/04/linux-file-locking-types/

Q: if one method has synchronized(b){synchronized(c){…}}, and another method has synchronized(c){synchronized(b){…}}, and b and c point to the same object, can you think of when people write such code?
A: always bad design, unnecessarily confusing. Deadlock prone. Programmer must know for certain that b and c reference the same object throughout. I’d add an assert as documentation.

Q: A set should contain unique objects but what if you input 2 unique objects and then make them identical twins (ie a.equals(b))? So the set has duplicate entries? Consequence?

Q: how many types of iterators are there?

Q: what classic design patterns did you use?

Q: how is the treeMap or TreeSet implemented internally? What kind of binary tree?

Q: what’s Shell sort? What other sorts do you know?

Q: what’s the time complexity of quick sort?

Q: name 5 things you would consider before developing a java threading app.
A: privatize all fields in shared objects
A: immutables
A: reduce number of locks
A: I should know exactly how many threads system will create. Reduce the number.
A: any wait/notify required? Need to know early since they tend to mess up my design
A: extremely mindful of deadlocks
A: avoid synchronization if possible — use concurrent data structures
A: producer/consumer and other threading patterns. Avoid creating my own threading “pattern” or framework.

which thread runs onMessage()

Anthony,

You brought up a good requirement: a MessageListener instance must receive messages in the order published.

My solution: A simple thread-pool worker thread picks up a task in the task queue and calls myListener.onMessage(..). Task queue (being a Queue) maintains the message sequence. (A Task object wraps a listener object and an immutable message object.)

Now, what if one of the onMessage() calls inserts to DB and runs too slow? I would argue it’s “your problem” as the app developer, not “my problem” as the JMS api developer. My job is to call your onMessage() sequentially. I can’t control if the messages go into your DB in sequence.

If 5 messages are found in the task queue, a worker thread should intelligently pick up all and somehow prevent another worker thread from picking up the 6th message (that comes later) and pushing it to myListener before the 5. Essentially, this worker thread should lock on the listener.

I feel in general onMessage() should NOT be synchronized.

swing action listener callback and wait/notify

Anthony,

Last month I asked “Exactly which thread calls the callback method in a Swing action listener when I click on a mouse?” I think Answer is, the EDT or “AWT event queue thread” in debugger thread listing.

This thread is started when the app starts and it waits in Object.wait() — confirmed. When you click on a button in the swing JFrame, the callback method runs in this thread. System doesn’t create a new thread to run the callback method. I think that would be too expensive since creating a new thread is not cheap. There are other fundamental reasons to run all event callbacks on EDT — see other posts in my blog.

For JMS onMessage() callback, I guess it might be similar — a single dedicated, long-running thread, not 5 new threads for 5 new messages. The volume of incoming messages is way too high if we create a new thread each time.

Next question is, what is this dedicated thread doing when there’s a long quiet period? I think it has to do a wait(), just like Swing.

Your input is welcome.

Bin