BGC IV – c++ and Java

Mostly QQ challenges.
—socket
Q: is select() blocking or non-blocking?
A: Yes select() takes a timeout argument to specify the blocking interval!
A: More interestingly, https://stackoverflow.com/questions/5351994/will-read-ever-block-after-select/5352634#5352634 says after select(), you should use read() which normally won’t block.

Q: server uses socket() listen() bind() accept(). How about client side?
Q1: if a producer thread uses select to send packets to multiple receivers by tcp and a single receiver has very low capacity, what would happen?
Q1b: select() would show the producer’s socket as writable or failed?

Q1c: what if producer keeps sending? What happens next?
%%A: the producers function stack will get an error code

Q1d: what if UDP rather than TCP
%%A: then no error would occur in the producer system. The slow consumer would be left unnoticed.

%%Q: can a socket specify a wild card for its local port?

—IPC
Q: fastest IPC method between producer and consumer? OK you said shared memory, so how do you synchronize the producer and consumer? %%A: use a named sys-V semaphore in the kernel
Q: how does the producer/consumer actually use the shared memory? %%A: memory mapped file

—brain teasers:
Q: Only a 5L and a 3L pail and a running tap. How to get exactly 4L water in the 5L pail?
Q: you are a given a bag of coins (like 1c 1c 1c 5c 5c 10c 25c). Tell me whats the smallest exact payment thats impossible. Every payment must be exact. Hint: sort the coins first, then a clever O(1) single-pass will do. Q: given a list of integers, find if any pair adds up to 18
%%A: in one pass, build a hashset of brown items i.e. every item processed so far. For every new (i.e green) item, compute the partner, and look for it in the hashset. If not there, then add the green item as a brown item.

—coding challenge
Q: given a singly linked list with a start node and null-end node, print each node in reverse, without using any “new” implicitly/explicitly

Q: Given an arbitrary directed graph where each parent node has 0 to K children, write a function hasCycle() to check for existence of cycle, visiting each node and each edge once only..
%%A: My verbal algorithm — use breadth-first traversal to trace every branch from root to a leaf node. Detect cycle in each branch. We cant simply keep a seen hashtable, because a node seen twice could be visited on two branches.

Whenever we branch out to 2 child branches, duplicate the parent branch, so that each child branch object has a full path from root.

Each branch object could be a (possibly linked[1]) hashset.
[1] for instrumentation.

Q: given a blackbox utility function String convert(String), write a parallelized Collection parellelConvert(Collection theSequence)
Requirement: theSequence need to be maintained. Size of input is preserved Requirement: Out of 100 items in theSequence, #3 and #5 might be identical, but they still need to show up as “converted” in the output
Requirement: converter uses a very slow and expensive remote system, so we don’t want to send it the same string twice.

—-
%%Q: is countdown latch and join() implemented using wait/notify? %%Q: readResolve vs readObject
%%Q: can CMS ever stop the world?
%%Q: CMS is used in which region of the heap?
Q: what if you suspect theres leak?
Q: what can cause mem leak in java?
%%A: registered listeners; static variables pointing to a collection

Q: why is swing memory footprint so bad?
Q: how do you mark a memory region as always resident?
Q: array blocking queue — when would it block?
%%A: I think a circular array is the underlying.

c++CollabEdit/Broadway IV: implement hash table#I used py

Q: implement a hash table class in any language. You could use existing implementations of linked list, array, hash function…

Q: talk about how you would implement rehash?
%%A: hash code won’t change for the key objects. But I would rerun the modulus against the new bucketCount. Based on the new index values, I would create the linked lists in each new bucket. Every pair needs to be relocated. Lastly I need to get rid of the old bucket array.

Q: how would you test your hash table?
%%A: try inserting (key1, val1), then (key1, val2), then look up key1
%%A: if I know any common weakness of the hash function, then test those.
%%A: trigger rehash

Q: what could go wrong in a multi-threaded context?
%%A: things like lost update or duplicate entries

Q: What concurrency solution would you choose for best performance?
%%A: could use lockfree algo at each point of writing to the bucket array or writing to a linked list.

##10basic constructs4c++cod`IV

See EPI300

  1. std::string (more useful than cStr)
  2. vector (more useful than array) sorted data structure (i.e. stl map), unordered_map
  3. Node class used in a linked graph
  4. dtor, copier, op=
  5. ref only as function I/O
  6. iterator – basic usage
  7. double pointer
  8. stack, queue
  9. pointer arithmetic
  10. shared_ptr
  11. local static

no exception
stl algo? Only Citadel array-shrink
no pointer to function
no template
no (very, very seldom) threading in coding Q
adv: matrix
adv: circular buffer

 

c++SCB eFX IV#Dmitry

I feel these are all QQ type, as defined in https://bintanvictor.wordpress.com/2017/02/15/qqzz-mutual-exclusion-cjava/

Q: Scanning a vector of int (like finding the average or max). Forward iteration vs backward iteration, which one could be faster, considering all possible compiler optimizations.

%%A: forward. Memory read into cpu cache will be in chunks, not one element at a time. Easy for forward iteration. Not sure about backward.

Q: Which one could be fastest:

void f(double arg){…..}
void f(double & arg){….}

%%A: inlining for first but not 2nd?
A: See http://stackoverflow.com/questions/722257/should-i-take-arguments-to-inline-functions-by-reference-or-value esp. the long answer.

Q: Thr1 and Thr2 on 2 CPU’s both update an object s, having 2 fields. Thr1 only updats s.field1. Thr2 only updates s.field2. No interference. No synchronization required. We observe the performance is slower than using one thread to update both fields. Any explanation?

Q: weak_ptr justification, when we have shared_ptr already? I feel [[effectiveModernC++]] has a good chapter on it.

Ashish pointed out in some apps, you could identify a clear risk of circular dependency. Replace with weak_ptr.

Q: given an 2D array arr[10][5], how do you use pointer arithmetic to hit arr[1][5]

A: Contiguous. see http://stackoverflow.com/questions/7784758/c-c-multidimensional-array-internals. Note this is different from an array of pointers.

Q: what would you see if a TCP socket server has a full queue
%%A: TCP requires ack, so if server is unable to accept a request the client would know it.

Q: what STL algorithms did you use?
%%A: foreach(), find(), copy_if(), transform(), reverse()

c++method default arg isn’t saved]vtable #Ashish

Ashish said he was asked the same question in multiple c++ interviews. The default param value is “declared” in base class and/or derived class and isn’t saved in the vtable. It’s basically resolved statically, at compile time.

If you use a pointer to Base to invoke the virtual method, then the Base default value applies unconditionally, even though the subclass method is chosen at run time, via the vtable.

c++ static field init – basic rules

See also post on extern…

These rules are mostly based on [[c++primer]], about static Field, not local statics or file-scope static variables.

Rule 1 (the “Once” rule) — init must appear AND execute exactly once for each static field.

In my Ticker Plant xtap experience, the static field definition crucially sets aside storage for the static field. The initial value is often unused.

Corollary: avoid doing init in header files, which is often included multiple times.

Rule 2 (the “Twice” rule) — static field Must be DECLARED in the class definition block, and also DEFINED outside. No exception. Therefore, the same variable is “specified” exactly twice [1]. However, the run time would “see” the declaration multiple times if it’s included in multiple places.

Corollary: always illegal to init a static field at both declaration and definition.

[1] Note ‘static’ keyword should be at declaration not definition. Ditto for static methods. See P117 [[essential c++]]

Integer constant fields are special, and can be initialized in 2 ways
* at declaration. However, you MUST still (Rule2) define without initialization. Such a definition is rather non-intuitive and inconsistent with other definitions.
* at definition, outside the class. In this case, declaration would NOT initialize — Rule 1

Rule 3: For all other static fields, init MUST be at-definition, outside the class.

Therefore, it’s simpler to follow Rule 3 for all static fields including integer constants, though other people’s code are beyond my control.

 

## c++topics seldom quizzed

(master -> pearl)
some low-level details I thought would be popular but seldom asked:
* L-value
* iterator types and implementations
* static variables outside classes
* implicit acts of magic by compiler
* array and cStr – syntax, memory, … the gory details beyond the basics
* template specialization
* ref/pointer typedef inside  templates
* non-dummy-type args in template
* MI
* enum
* exception spec
* C integration
* pimp
* fwd declaration
* namespace
* linker
* extern
* double pointers
* hiding rule
* swap – all the important usages and no-fail
* overloading and  method resolution
* casting and conversion
*** OOC and  conversion ctor
— “mid-level”
* boost Any vs Variant
* i/o stream
* regex
* file access (including random)
* serialization
* memory leak detection
* details of boost thread
* boost smart pointer beyond the shared_ptr
* std::string details