car park concurrency design #volatile field#AshS

Design a car park class for concurrent access given

  • a single sensor A at the entry
  • a single sensor B at the exit

Without using locks, Provide enter() and leave() API methods that can be safely invoked on multiple threads.

— If at any time there’s only one thread calling enter (and leave), then volatile-based solution might work. I think this assumption is reasonable. Given there’s only one physical entry point, it’s not physically possible for two threads to run enter() simultaneously.

volatile int sensorA, sensorB;

int attemptToPark(){
count = this.senserA – this.sensorB;
if (count > CAPACITY) throw IllegalStateException;
if (count == CAPACITY) return 0;
this.senserA ++ ;
return count+1;
}
void leave(){
//concurrent access disallowed for this R/W operation
this.sensorB ++ ;
}

— If multiple threads are allowed to increment this.senserB, then we need (either a lock or) atomicInteger. ABA problem is not a concern here given the integer never decrements.

insert to sorted collection of N items: I can beat O(log N)

features/advantages of sorted collection

  • O(N) ascending iteration
  • O(log N) range query
  • O(log N) closest neighbor query above/below
  • O(log N) boolean contains() query
  • O(1) min() max() queries
  • deleteByKey is typically O(log N) but can be O(1) if we construct a hashtable of {key -> iterator} once the collection is built. This hashtable can also accept new items.

Q: insert is typically O(log N), but can we improve on it?

— A: if there’s only one insert, we can hold it in a hidden field of the collection, to be checked at the end of each operation above.

— A: if there are unlimited inserts but all 64-bit integers, then we can treat the incoming integer as a short radix array (8-elements for example). Take each element of the array as a lookup key, look up in an array to find a subtree.

Basically the entire sorted collection is an  8-level tree with fan_out=256

You may say that there are 8 lookups required so O(k) where K=8, but here we assume the size of the radix array is a constant equal to eight. Note the collection size is unlimited and far more than 2^64 if duplicates are permitted.

denigrate%%intellectual strength #ChengShi

I have a real self-esteem problem as I tend to belittle my theoretical and low-level technical strength. CHENG, Shi was the first to point out “你就是比别人强”.

  • eg: my grasp of middle-school physics was #1 strongest across my entire school (a top Beijing middle school) but I often told myself that math was more valuable and more important
  • eg: my core-java and c++ knowledge (QQ++) is stronger than most candidates (largely due to absorbency++) but i often say that project GTD is more relevant. Actually, to a technical expert, knowledge is more important than GTD.
  • eg: I gave my dad an illustration — medical professor vs GP. The Professor has more knowledge but GP is more productive at treating “common” cases. Who is a more trusted expert?
  • How about pure algo? I’m rated “A-” stronger than most, but pure algo has far lower practical value than low-level or theoretical knowledge. Well, this skill is highly sought-after by many world-leading employers.
    • Q: Do you dismiss pure algo expertise as worthless?
  • How about quant expertise? Most of the math has limited and questionable practical value, though the quants are smart individuals.

Nowadays I routinely trivialize my academic strength/trec relative to my sister’s professional success. To be fair, I should say my success was more admirable if measured against an objective standard.

Q: do you feel any IQ-measured intelligence is overvalued?

Q: do you feel anything intellectual (including everything theoretical) is overvalued?

Q: do you feel entire engineering education is too theoretical and overvalued? This system has evolved for a century in all successful nations.

The merit-based immigration process focus on expertise. Teaching positions require expertise. When laymen know you are a professional they expect you to have expertise. What kind of knowledge? Not GTD but published body of jargon and “bookish” knowledge based on verifiable facts.

count allocation strategies of $K into N funds

!! how is this related to the CSY staircase problem?

 

Q: given K dollars and N distinct mutual funds (including a cash fund), how many unique allocation strategies are there? It’s permissible to allocate $0 to any fund, but total amount in a strategy must add up to exactly K dollars

Note K can be higher or lower than N, both positive integers. Allocation amount must be whole dollars.

Without loss of generality, let’s say K is $5 and N is 3.

====Analysis

I think this is more a mathematical than an algorithm question. Each strategy can be represented by an N-element array. [0,5,0] is one strategy, allocation $5 to 2nd fund and $0 to the other funds. If we are required to enumerate all the strategies, we can print out the arrays.

My solution starts by defining a mathematical function f(k, n) := count of allocation strategies given k dollars and n funds. Based on this definition,

  • f(any_integer, 1) == 1 because there’s only one fund to receive the full amount. One strategy only.
  • f(0, any_integer p) == 1 because all p funds must receive $0 each. No other strategy.

Without loss of generality, let’s say K is 33 and N is 22. Using bottom-up DP, I assert that when we get a “new” fund, the 22nd fund, we can use the earlier answers to find f(33,22):

f($33,22) = f($33,21)f($0,1) + f($32,21)f($1,1) + f($31,21)f($2,1) +… +f($1,21)f($32,1)+f($0,21)f($33,1)

Let me explain the 3rd term on the right-hand-side. This term means the count for “$31 into the 21 existing funds” multiplied by the count for “$2 into the new fund”. This describes the scenario of first allocating $2 to the new fund, and then allocating the remaining $31 to the existing funds. The above formula simplifies to

f($33,22) = f($33,21) + f($32,21) + f($31,21) +… + f($1,21) +1

This formula for f(33,22) uses earlier results for f(smaller or equal amounts, one fund fewer). A bottom-up DP algorithm is straightforward. Generalization of this example gives

f(K,n+1) = f(K,n) + f(K-1,n) + f(K-2,n) + f(K-3,n)+..+ f(2,n) + f(1,n) + f(0,n)

 

zbs=vague,cf to QQ+GTD

Many zbs learning experiences (me or DQH) were arguably irrelevant if never quizzed.

–iv questions on malloc, tmalloc and the facebook malloc
In latency benchmarks, c++ should simply 1) avoid DMA or 2) pre-allocate. Therefore, if the iv question touches on benchmark, then the malloc question become moot.

–iv questions on lockfree in c++
messier and more low-level than java lockfree. I would say lockfree is seldom written by a c++ app developer. Therefore not a GTD topic at all. Purely QQ halo topic.

–iv question on volatile
Again, many interviewers use volatile as concurrency feature in c++ but it’s non-standard ! Even if it has a side effect under gcc, the practice is “not something I would recommend”, though I won’t criticize hiring team’s current practice.

Not a GTD skill, not zbs either.

–iv question on throwing dtor
c++ standard says UDB but still some interviewers ask about it. So this topic is not zbs not GTD but really QQ

–iv question on debugger breakpoint
Not GTD, not even zbs

–iv question (GS-HK) on CAS no slower than uncontended lock acquisition
I feel I don’t need to know how much faster. My knowledge is good enough for GTD

–iv question on how many clock cycles per instruction
no GTD but zbs for a latency enthusiast

 

unspecified^undefined behavior

Some interviewers really really go into UDB, so to impress them it is very very useful to understand UnSpecifiedBehavior (USB):

Compliant compilers are not required to document the behavior but the behavior should be consistent and valid such as crash. For a given program containing a USB, where possible the Standard provides two or more possibilities (i.e. permissible outcomes), such that an executable from a compliant compiler should produce one of these outcomes.

Compared to USB, UDB gives compilers more freedom. The actual result could be anything including invalid results in one instance and in another instance turning a blind eye.