(intuitive)derivation of the combination formula

Q1: how many ways to pick 3 boys out of 7 to form a choir?

Suppose we don’t know the 7_choose_3 formula, but my sister said answer is 18. Let’s verify it.

How many ways to line up the 7 boys? 7!

Now suppose the 3 boys are already picked, and we put them in the front 3 positions of the line.

Q2: Under this constraint, how many ways to line up the 7 boys?
A2: In the front segment, there are 3! ways to line up the 3 boys; in the back segment, there are 4! ways to line up the remaining 4 boys. So answer is 3! x (7-3)! = 144

Since there are supposedly 18 ways to pick, then 18 * 144 must equal 7! We find out 18 is wrong answer.

Advertisements

gdb –tui #split screen

You can also start gdb normally, then switch to split screen, with “ctrl-x  ctrl-a” (thanks to Gregory).

Upper screen shows the source code with a moving marker

–Here’s my full gdb command showing

  • –args to run the target executable with arguments
  • redirect stderr to a file so my gdb screen isn’t messed up — not always effective

gdb –tui –args $base/shared/tp_xtap/bin/xtap -D 9 -c $base/etc/test_replay.cfg 2 >

find lowest natural number !! in%%list#codility

Q: Write a function int solution(int[] A);  that, given an array A of N integers, returns the smallest natural number that does not occur in A. For example, given A = [1, 3, 6, 4, 1, 2], the function should return 5.
Given A = [1, 2, 3], the function should return 4.
Given A = [−1, −3], the function should return 1.

• each element of array A is an 32-bit signed int
• expected worst-case time complexity is O(N);
• expected worst-case space complexity is O(N).
* Elements of input arrays can be modified.

https://leetcode.com/problems/first-missing-positive/description/ is similar but O(1) space and average O(N) time!

—— my analysis —–
This is not testing coding abilities (ECT, syntax…), but comp science algo.

Codility is a fully automated system. I believe the O(N) requirement will not be checked by a human. The Codility system may not be able to determine O() by parsing the source code. In fact, a O(N) source code may run slower than a O(N logN) solution and fail the Codility hidden tests. Therefore, we can put aside the O(…) requirement initially.

One way to achieve O(N) is radix sort on A, dropping any negative values. Then iterate the sorted array and check for the earliest “gap”. Worst case — you get 1,2,3… without gap, so answer is the 1+ largest array element.

—-solutionB: make_heap O(1) space but O(N logN) time. Build a min-heap based on the array in O(1) space, then keep calling min().

  • make_heap shows random access container (vector used in demo), and “rearrange”, implying O(1) space
  • make_heap shows O(N) to construct the heap

min() is O(1) but delete_min() is O(log N), so overall we probably get O(N logN)

—-solutionC: radix sort. https://en.wikipedia.org/wiki/Radix_sort#In-place_MSD_radix_sort_implementations shows an in-place binary radix sort.

First pass to transform all negative numbers to 0.

O(W*N) where W is width of the largest integer. If we assume 64-bit then W is a constant:)

http://www.drdobbs.com/parallel/parallel-in-place-radix-sort-simplified/229000734 is another in-place radix sort.

file (de)serialization, for array of simple structures #Gregory

Not needed for IV..

// simple and fast (de)serialization to file given an array of structures

#include <fcntl.h>
#include <iostream>
using namespace std;
size_t const len=15;

struct A{
        int i1;
        char cstr[len];
        //string s4; //doesn't really work
        A(int i=999, string cs="default c-string", string s="default std::string"): i1(i){
                strncpy(cstr, cs.c_str(), len);
        }
};
size_t const  cnt=2, siz=cnt * sizeof(A);
A arr[cnt], ar2[cnt];

char fname[] = "/tmp/,.dat";
int main() {
        arr[0]=A(1,  "grin", "backbone");
        arr[1]=A(2,  "frown", "try/except/else");

        int fd = open(fname, O_CREAT | O_WRONLY, S_IRUSR | S_IWUSR);
        write(fd, arr, siz);
        close(fd);

        int fd2 = open(fname, O_RDONLY);
        read(fd2, ar2, siz);
        close(fd2);

        for (int idx = 0; idx < cnt; ++idx){
                A * tmp = ar2 + idx;
                cout<<tmp->i1<<" ; "<<tmp->cstr<<" ; "<<endl; //tmp->s4<<endl;
        }
}

sharing port or socket #index page

Opening example – we all know that once a local endpoint is occupied by a tcp server process, another process can’t bind to it.

However, various scenarios exist to allow some form of sharing.

https://bintanvictor.wordpress.com/2017/04/29/socket-shared-between-2-processes/

https://bintanvictor.wordpress.com/2017/04/29/so_reuseport-socket-option/

https://bintanvictor.wordpress.com/2017/04/29/2-tcp-clients-connected-to-a-single-server-socket/

https://bintanvictor.wordpress.com/2017/03/29/multiple-sockets-can-attach-to-the-same-addressport/

[13]arrayName^ptrVar differences tabulated

See other posts why an array name ((including c-str) is a permanent name plate on a permanently allocated room in memory. Once you understand that, you know
– can’t move this name plate to another room
– can’t put this array name on the LHS of assignment

I feel overall, in most everyday contexts you can treat the array name in this example as if it’s a variable whose type is int*. However, the differences lurk in the dark like snakes, and once bitten, you realize there are many many differences. The 2 constructs are fundamentally different.

Q: how to edit the below html table structure (content is easy)?
A: edit the html
A: copy paste to ms-word

ptr to heap array ptr-var array-name (array not on heap)
declaration array-new int* p//allocate 32bit int arr[3]//allocate 3 ints
declared as a struct/class field same as ptr-var 4-bytes onsite entire array embedded onsite
declared as func param var no such thing common converted a ptr-var by compiler
initialize probably not supported char* p=”abc”;// puts the literal string in RO memory char arr[]=”xyz”; //copying the literal string from RO memory to stack/heap where the array is allocated. The new copy is editable.
object passed as func arg same as ptr-var common converted to &arr[0]
dereference same as ptr-var common gives the first int element value. P119[[primer]]
address of same as ptr-var double ptr &arr[0]==&arr==arr. See headfirstC post and also
http://publications.gbdirect.co.uk
/c_book/chapter5
/arrays_and_address_of.html
rebind/reseat same as ptr-var common syntax error
add alias to the pointee same as ptr-var common unsupported
as LHS (not as func param) same as ptr-var common. Reseat syntax error

undefined reference to vtable

This error can be hard to track down if codebase is huge. I have seen it more than 4 times and often it takes a few minutes of investigaton because there are multiple causes:

  • If a virt function is defined in a .cpp file but you don’t link in that file, then you can hit this linker error.
  • if you declare a virt function but don’t define it, you hit this linker error

financial IT profession: !! so bad #long pre-retirement#Daniel

See also a profession u Enjoy with good {income+barrier}

(A letter I didn’t send out) Hi Daniel,

I think the programmer profession (financial software dev in particular) is not that bad:

  • Career Longevity — (I will delay or completely skip retirement) Reasonable in the U.S. Some professions (like doctors, accountants, teachers) are even better. but most professions (90% of the U.S. working population) can’t expect to have such a salary at age 65, including executives, lawyers, quants… Why do we always envy those guys?
    • Age discrimination — better than most professions including managers
  • Entry barrier — formidable, comparable to doctors or lawyers. See ##行行出状元,但有几个行业不容易出头
  • market depth — see salary probabilities(distro): mgr^NBA#market depth 
  • Job security — actually reasonable, despite the threat of globalization and threat from younger guys. I think the high entry barrier in financial IT is to our advantage
    • I was told some managers have job security concerns too
    • I was told U.S. university professors also face elimination (淘汰).
  • Work Stress — Significant variation across firms and across teams, but generally more stress than other professions.
  • Workload — much higher than other professions. Programming is a knowledge-intensive job.
  • Job market demand — very high for IT skills. Therefore people from other professions are drawn here.
    • Market depth is excellent. You can find plenty of jobs from $50k (easy to cope) to $300k
  • Income — well above average among all professions. Just look at national statistics and world-wide statistics.
  • not a sunset industry, not under threat like music, movie, journalism.
  • knowledge intensive, challenging complexity, engaging, but without excessive mental stress.

algo trading engine from scratch: ez route hopefully

Update: TrexQuant had an extremely simple trading system, mostly an FIX connectivity engine…

Start by identifying some high-quality, flexible, working code base that’s as close to our requirement as possible. Then slowly add X) business features + Y) optimizations (on throughput, latency etc.) I feel [Y] is harder than [X], thought [X] gives higher business value. Latency tuning is seldom high-value, but data volume could be a show-stopper.

Both X/Y enhancements could benefit from the trusty old SQL or an in-memory data store[1]. We can also introduce MOM. These are mature tools to help X+Y. [3]

As I told many peers, my priorities as architect are 1) instrumentation 2) transparent languages 3) product maturity

GTD Show-stopper: data rate overflow. Already addressed
GTD Show-stopper: frequent[4] crashes. Unlikely to happen if you start with a mature working code base. Roll back to last-working version and retest incrementally. Sometimes the crash is intermittent and hard to reproduce 😦 Good luck with those.

To blast through the stone walls, you need power tools like instrumentation, debuggers … I feel these are more important to GTD than optimization skills.

To optimize, you can also introduce memory manager such as the ring buffer and custom allocator in TP, or the custom malloc() in Facebook. If performance doesn’t improve, just roll back as in Rebus.

For backend, there are many high or low cost products, so they are effectively out of scope, including things like EOD PnL, position management, risk management, reporting. Ironically, many products in these domains advertise themselves as “trading platforms”. In contrast, what I consider in-scope would be algo executor, OMS[2], market data engine [2], real time PnL.

— The “easy route” above is probably an over-simplification, but architects must be cautiously optimistic to survive the inevitable onslaught of adversities and setbacks —

It’s possible that such a design gradually becomes outdated like GMDS or the Perl codebase in PWM-commissions, but that happens to many architects, often for no fault of their own. The better architects may start with a more future-proof design, but more likely, the stronger architects are better at adjusting both the legacy design + new requirements

Ultimately, you are benchmarked against your peers in terms of how fast you figure things out and GTD….

Socket tuning? Might be required to cope with data rate. Latency is seldom a hard requirement.

Threading? single-threaded model is probably best. Multiple processes rather than multiple threads.

Shared memory? Even though shared memory is the fastest way to move data between processes, the high-performance and high-throughput ticket plant uses TCP/Multicast instead.

MOM? for high-speed market data gateway, many banks use MOM because it’s simpler and flexible.

Inter-process data encoding? RTS uses a single simplified FIX-like, monolithic format “CTF”. There are thousands of token types defined in a “master” data dictionary — semi-static data.

GUI for trader? I would think HTML+javascript is most popular and quick. For a barebones trading engine, the GUI is fairly simple.

Scheduled tasks? Are less common in high speed trading engines and seldom latency-sensitive. I would rely on database or java/c++ async timers. For the batch tasks, I would use scripts/cron.

Testing? I would use scripts as much as possible.

[1] eg: GMDS architect chose memory-mapped-file which was the wrong choice. [2] both require an exchange interface
[3] data store is a must; MOM is optional;
[4]If it crashes once a day we could still cope. Most trading engines can shut down when market closed.

c++q[new] variations

  1. variation: new MyClass(arg1) // most common. Can throw bad_alloc
  2. variation: new MyClass() // better form, calling the no-arg ctor
  3. variation: new MyClass //bare word, same as above. See op-new: allocate^construct #placement #IV
  4. variation: new (nothrow) MyClass(…) // returns NULL upon failure
  5. variation: placement new
  6. variation: array-new // no argument allowed!

ssh host1 ssh host2 q[cmd1; cmd2]

This simple automation script demonstrates how to ssh 2 layers into a machine to run a command.

Obviously you need to set up authorized_keys.

#!/bin/bash
date=0710
tgz=nx$date.tgz
set -x
ssh -q uidev1 ssh -q bxbrdr2 "tar cfvz $tgz /data/mnt/captures/tp5/lfeeds/nysemkt/nysemkt-primary.2017${date}_03*"
ssh -q uidev1 ssh -q bxbrdr2 "hostname; ls -l ~/$tgz"
ssh -q uidev1 scp -pq bxbrdr2:$tgz .
set +x
ssh -q uidev1 "hostname; ls -l ~/$tgz"
scp -pq uidev1:$tgz .
ls -l $tgz

contractor^mgr^low-VP 3way-compare #XR

See also hands-on dev beats mgr @same pay and my discussion with Youwei in pureDev beats techLead: paycut=OK #CYW

In the U.S. context, I feel the FTE developer position is, on average, least appealing, though some do earn a lot, such as some quant developers. My very rough ranking of total income is

  1. senior mgr
  2. contractor
  3. FTE-dev including entry-level lead roles

Without bonus, the FTE-dev is often lowest. However, bonus is not guaranteed.

I exclude the pure quants (or physicians) as a different profession from IT.

 

## IV favorites ] sockets

There are dozens of sub-topics but in my small sample of interviews, the following sub-topics have received disproportionate attention:

  1. blocking vs non-blocking
  2. tuning
  3. multicast
  4. add basic reliability over UDP (many blog posts); how is TCP transmission control implemented
  5. accept() + threading
  6. select (or epoll) on multiple sockets

Background — The QQ/ZZ framework was first introduced in this post on c++ learning topics

Only c/c++ positions need socket knowledge. However, my perl/py/java experience with socket API is still relevant.

Socket is a low-level subject. Socket tough topics feel not as complex as concurrency, algorithms, probabilities, OO design, … Yet some QQ questions are so in-depth they remind me of java threading.

Interview is mostly knowledge test; but to do well in real projects, you probably need experience.

Coding practice? no need. Just read and blog.

Socket knowledge is seldom the #1 selection criteria for a given position, but could be #3. (In contrast, concurrency or algorithm skill could be #1.)

  • [ZZ] tweaking
  • [ZZ] exception handling in practice
  • —-Above topics are still worth studying to some extent—–
  • [QQ] tuning
  • [QQ] buffer management

 

##shared_ptr thr-safety: 3 cases

This topic is worthwhile as it is about two high-value topics … threading + smart ptr

At least 3 interviewers pointed out thread safety issues …

http://stackoverflow.com/questions/14482830/stdshared-ptr-thread-safety first answer shows many correct MT usages and incorrect MT usages. Looking at that answer, I see at least 3 distinct”objects” that could be “shared-mutable”:

  1. control block — shared by different club members. Any one club member, like global_instance could be a shared mutable object. Concurrent access to the control block is internally managed by the shared_ptr implementation and probably thread-safe.
  2. pointee on heap — is shared  mutable. If 2 threads call mutator methods on this object, you can hit race condition.
  3. global_instance variable —  a shared mutable instance of shared_ptr. race condition 😦

 

 

 

%%rwlock using only 1 mutex #Ashish

Q: implement a simple read/write lock using a basic mutex provided by a basic thread library.

— Target Usage Scenario —
Imagine a data table that any thread can read in the absence of concurrent updates, but only one writer thread at a time can update.

I feel some minimum fairness is needed. You don’t want a writer thread to keep waiting for a long time while readers come and go, as if the writer is a second-class citizen. In fact, this implementation favors writers to readers, assuming write is more urgent. Reader starvation is considered tolerable.

— implementation notes–

Since there are 2 mutexes involved, we will always acquire the police first. Helps reduce chance of deadlocks. Still, it’s better to use a single mutex, as shown in [[pthreads]]. One simple suggestion is replacing this->_mutex with a bool this->isWriting. I feel this is a common simplification to many synchronization designs.

After reading P84 [[pthreads]], the mutex field can be a nonref rather than a pointer. In that case, we should never copy this object. It should be created at time of construction.

Ashish pointed out a bug, so now, all 4 methods must acquire _police from onset, before reading/writing  internal shared data.

#include <cassert>
using namespace std;
class mutex{ //this class should be provided to us
public:
  void release();
  void acquire();
};

class raiiLock{//when an instance goes out of scope on the stack, dtor will release the lock
  mutex const _lock; 
public:
  raiiLock(){
    _lock.acquire();
  }
  ~raiiLock(){
    _lock.release();
  }
};

class rwlock{
  rwlock(rwlock const & other); //disabled
  rwlock & operator =(rwlock const & other); //disabled

  // data members
  mutex  _mutex; //used by writers only, never by readers
  mutex  _police; // controls modifications to internal data members
  size_t const _permits; // max number of concurrent readers allowed in theory
  size_t _available; // available permits, controlled by the police
  size_t _waitingWriters; // controlled by the police
public:
  // note dtor will be synthesized, which will do nothing if all data members are primitives or pointers
  // note no-arg ctor is not allowed.
  rwlock(size_t maxPermits):
    _permits  (maxPermits),
    _available(maxPermits),
    _waitingWriters(0){}

  void release1permit(){
    raiiLock autoLock(_police); //blocking briefly
    _available ++;
    if (_available == _permits && _waitingWriters){
      //wake up one of the writers, perhaps using a conditional variable tied to _police mutex
    }
  }
  void releaseWriterLock(){
    raiiLock autoLock(_police); //blocking briefly
    _available = _permits;
    _mutex.release();
    if (_waitingWriters){
      //wake up one of the writers, perhaps using a conditional variable tied to _police mutex
    }
  }
  char try_acquire1permit(){ // non-blocking
    //As Ashish pointed out, _police need to be acquired before 
    //checking _waitingWriters and _available. Any access to shared internal
    //data needs police protection.
    raiiLock autoLock(_police); //blocking briefly
    if (_waitingWriters) return 'w'; //immediately reject this
    // reader's request if there's any waiting writer.
    // Therefore, any subsequent reader requests will not affect the waiting writers.
    if (_available == 0 ) return 'a';

    assert( _available > 0 && _waitingWriters == 0);
    _available --;
    return '0'; // 0 means safe to read the protected data table
  }
  void acquireWriterLock(){ // blocking
    raiiLock autoLock(_police); //blocking briefly
    _waitingWriters ++ ; //Subsequent readers will be rejected, to avoid writer starvation
    while(_available < _permits){
      //block in some kind of waiting room perhaps using a conditional variable tied to _police mutex
    }
    assert (_available == _permits && "all permits should be released and the writer, if any, is done");
    _mutex.acquire(); // should never block
    _available = 0;
    _waitingWriters --;
    // now the current thread is free to update the table
  }
};

thread-unsafe shared_ptr: tiny examples

##shared_ptr thr-safety: 3 cases is a “framework”.

http://www.boost.org/doc/libs/1_35_0/libs/smart_ptr/shared_ptr.htm#ThreadSafety gave simple examples of unsafe access.

//— Example 3, where the shared mutable is a club member p3 ——————
// thread A
p = p3; // reads p3, writes p

// thread B
p3.reset(); // writes p3: Undefined, simultaneous read/write

I gave this example correctly to a Sep 2018 SCB interview 🙂

===> In the same clock cycle, p3 Object is accessed on 2 threads. This is nothing to do with the ref count, or the pointee object.

//— Example 4,  where the shared mutable is a club member p2 ——————
// thread A
p3 = refToP2; // reads p2, writes p3

// thread B
// p2 goes out of scope: Undefined, simultaneous read/write since the destructor is considered a “write access”

===> In the same clock cycle, p2 Object gets write-accessed.

cvs update/checkout a file or dir

–retrieve an old version without sticky

cvs up -p -r1.17 CTFXdpIntgPlugin.C> CTFXdpIntgPlugin.C.1.17

–cvs update a dir or file:

cvs update –dA package/aida/common/script Bring working dir specified up to date with the repository (merge changes made to the repository into the local files).
cvs update –A package/aida/common/script/MakefileAida.sun4
Bring just the named file up-to-date with the repository

–cvs checkout a dir or file:

cvs checkout edu Checks out everything under edu, placing an edu directory, plus all subordinate subdirectories, in the working dir.
cvs checkout app/alh Checks out everything under app/alh placing an app directory in your working directory, but only the alh subdirectory of app.
cvs co package/aida/common/script/MakefileAida.sun4
Checks out only the single file MakefileAida.sun4, creating package/aida/common/script/MakefileAida.sun4 in the working directory, containing that one file.