find first lonewolf ] unsorted natural number array

Q: if an integer appears only once in an array, then it’s a lone wolf. Find the first lone wolf in a given array.

One idea — hash table + heap in fwd scan

  • use a hash table to hold payload objects, and progressively mark each payload green or brown
  • each payload consists of {color, index}. The key in the hash table is arr[index]
  • As we create a payload (to put into hash table), we also save its address in a min-heap, sorted on the index
  • After the scan, extract minimum from the heap, until we get a green element.

one idea — reverse scan the array and find the last lonewolf? probably broken

one idea — forward scan the array.
* any “new” element will be appended to a LinkedHashMap and painted green
* any “seen” element will be repainted brown
* How to test for newness? Any examined element is tested by contains() against the green/brown collection.
* at end of the scan, return 1st green.

one idea — forward scan the array.
* any “new” element will be appended to a green LinkedHashSet
* any “seen” element will be moved from green into a brown HashSet
* How to test for newness? Any element is tested by contains() against the green and the brown.
* at end of the scan, return 1st green.

Advertisements

python list append -3ways

Note there could be some useful python tips in the pearl blog. Perhaps it’s better to move the z_py posts there.

li + [1,2,3] # can be used directly in a for loop

### all solutions below return None!

li.append(1) # one argument exactly. To append more than one, use extend:

li.extend( [1,2] )

li.extend(list2)

 

java exception passing between threads

Many people ask how to make a child thread’s exception “bubble up” to the parent thread.

Background — A Runnable task is unsure how to handle its own exception. It wants to escalate to parent thread. Note parent has to block for the entire duration of the child thread (right after child’s start()), blocked either in wait() or some derivative of wait().

This question is not that trivial. Here are my solutions:

1) Callable task and Futures results — but is the original exception escalated? Yes. P197 [[java threads]]

2) Runnable’s run() method can temporarily catch the exception, save the object in a global variable such as a blocking queue, and notifyAll(). Parent thread could check the global variable after getting notified. Any thread can monitor the gloabal.

If you don’t have to escalate to parent thread, then

3) setUncaughtExceptionHandler() – I think the handler method is called in the same exception thread — single-threaded. In the handler, you can give the task to a thread pool, so the exception thread can exit, but I don’t know how useful.

4) adopt invokeAndWait() design — invokeAndWait() javadoc says “Note that if the Runnable.run() method throws an uncaught exception (on EDT) it’s caught and rethrown, as an InvocationTargetException, on the callers thread”

In c#, there are various constructs similar to Futures.get() — seems to be the standard solutions for capturing child thread exception.
* Task.Wait()
* Task.Result property
* EndInvoke()

IRS trading system@@ – Eric of Citi

IRS is not transferable. IRS contract can be re-assigned in some cases, but the original 2 counter parties and the new party must all agree.

Both parties must scrutinize the other’s credit worthiness. Libor rate is for top-credit borrowers. If the floating-payer is lower, then the spread on Libor (or the fixed rate?) will reflect that – a.k.a. credit spread. Alternatively, the counter party (floating receiver) can demand collateral.

There’s no secondary market for IRS like there are in listed securities.

Q: Is there an IRS trading system?
%%A: Most needed system might be a deal management system that tracks all our unexpired IRS contracts. Since each deal is bespoke, volume is not high. The basic entity in the system is known not as a position, but a deal. It’s treated like a trade as there are 2 accounts involved, and multiple settlement dates.

Q: Is IRS market regulated?
A: Regulators set limits on total exposure. Participant’s quarterly balance sheets include these IR swaps. One big swap could push a company above the limit.

coding IV – favored by the smartest companies

XR,

I see a few categories of IV questions:

1a) fundamentals — Some Wall St (also in Asia) tough interviews like deep, low-level (not obscure) topics like threading, memory, vtbl, RB-tree ..

1b) lang — Some (IMO mediocre) interviewers (like programming language lawyers) focus on language details unrelated to 1a)
2) Some (IMO mediocre) interviewers like architecture or high level design questions (excluding algo designs) like OO rules and patterns but I feel these are not so tough.

3) algo — Some tough interviews focus on algo problem solving in pseudo-code. See http://bigblog.tanbin.com/2007/09/google-interviews-apply-comp-science.html. I got these at Google and Facebook. Some quants get these too.

4) compiler coding question — is another tough interview type, be it take-home, onsite or webex.
With some exceptions (like easy coding questions), each of these skills is somewhat “ivory tower” i.e. removed from everyday reality, often unneeded in commercial projects. However these skills (including coding) are heavily tested by the smartest employers, the most respected companies including Google, Facebook, Microsoft… You and I may feel like the little boy in “emperor’s new dress”, but these smart guys can’t all be wrong.
I will again predict that coding questions would grow more popular as the logistic cost is driven down progressively.
Candidate screening is tough, time consuming and, to some extent, hit-and-miss. With all of these screening strategies, the new hire still can fail on TECHNICAL ground. Perhaps she/he lacks some practical skills — Code reading; debugging using logs; automation scripts; tool knowledge (like version control, text search/replace tools, build tools, and many linux commands)
Needless to say, new hire more often fail on non-technical ground like communication and attitude — another topic altogether.

In terms of real difficulty, toughest comp science problems revolve around algorithm and data structures, often without optimal solutions. Algo interview questions are the mainstay at big tech firms, but not on Wall St. Some say “Practice 6 months”. Second toughest would be coding questions —
* Often there’s too little time given
* Sometimes interviewer didn’t like our style but onsite coding tends to focus on substance rather than style.

Tan bin

P.S. I had webex style coding interviews with 1) ICE Feb 2011, 2) Barclays (swing), 3) Thomson Reuters, 4) Bloomberg

P.S. I tend to have more success with algo interviews and onsite coding than take-home coding. See blog posts.. (
http://tigertanbin2.blogspot.com/2015/05/sticky-weakness-revealed-by-interviews-c.html
http://tigertanbinpripri.blogspot.com/2015/03/high-end-developer-interviews-tend-to.html
)

reversing linked list: tail-recursion^iterative

The tail-recursion is a simple transformation of the iterative solution.

My own solutions. The set-up in the beginning is useful in coding demos.

struct Node{
  int data;
  Node * next;
  Node (int payload, Node* n=NULL): data(payload), next(n){}
};
Node _1('1'); //tail
Node _2('2', &_1);
Node _3('3', &_2);
Node _4('4', &_3);
Node _5('5', &_4);
Node * head = &_5;
void dump(string const& headline){
   cout<<headline<<endl<<"New head: ";
   for (Node* t=head; t; t=t->next)
      cout<< static_cast<char>(t->data) <<"  # "<<t<<" -> "<<t->next<<endl;
}
// Above is a useful, simple set-up of linked list for coding interview

void reverse1(Node* a, Node* b, Node* c){
        b->next = a; //fix the "b" node
        a=b; b=c; c = c->next; //shift down the 3 markers

        if (c == NULL){ //now b is the original tail and the new head
                head = b;
                head->next = a;
                return;
        }
        reverse1(a,b,c);
}
void tailRecursion(){
  Node* second = head->next;
  head->next=NULL; // first fix the head node
  reverse1(head, second, second->next);
}
void iterative(){
   Node * a=head;
   Node * b=a->next;
   Node * c=b->next;
   // marker variables on 3 consecutive nodes

   a->next=NULL; // first fix the head node

   for (;;){
        b->next = a; //fix the "b" node
        a=b; b=c; c = c->next; //shift down the 3 markers
        // now between a and b there's no link; a is fixed; b is intact

        if (c == NULL){
                head = b;
                head->next = a;
                break;
        }
   }
}
int main(int argc, char *argv[]) {
   iterative();
   dump("Iterative Reverse Completed:");
   tailRecursion();
   dump("Tail recursion Reverse Completed:");
}

##criteria: domains2specialize over30Y

See also post on top 5 expertise I could teach.

In the US job market, people often ask “What do you specialize in?”. I think most non-managers in this industry, esp. the successful ones, do specialize in something. Whether you like it or not, you are often perceived that way.

Clearly, many professionals are jack of many trades (or a jack of few trades), and don’t have any real expertise, depth or insight. Depending on your view, this may not be a problem for them.

Like property evaluation, I have a list of criteria:

  1. theoretical complexity — so most peers can’t master it. I get lower stress. For example, Threading, statistics, pricing models, algorithms, data science? …
  2. market depth (entry barrier) — eg: quant is too hard to get into and very few jobs in the mid-range or low-end
  3. opportunities in research/teaching, for my later years. Relatively few choices.
  4. aptitude — (aka advantage) easier to add value and receive appreciation and recognition.
  5. Something I believe in or care about, such as personal investment, or health. Self-knowledge: If it has commercial value I will care about it.
  6. ———– Rest are secondary —————-
  7. pathway to self-employment
  8. (obvious) accumulation and low churn — Look at grandpa
  9. premium on job market — low priority in my later career
  10. Something related to early childhood education

threading – I/O^CPU intensive

See also — [[linux sys programming]] has an one-pager on this topic.
This is a common topic in IV and in the literature. HSBC market data + algo trading IV 2017 also touched on this.
IO-intensive – may scale up to hundreds of threads, even with just 4 cores. Each thread handles some I/O channel or connection.
eg(?): network server
eg: GUI – multiple threads could be waiting for disk or user input
CPU-intensive on multi-core machines – don’t need too many threads, but single-thread is non-optimal. Each core is effectively dedicated to a single thread.