##5 algoIV constructs beyond dataStruct : xLang

  1. elegant, legit simplifications
  2. Judicious use of global -vs- argument -vs- local variables
  3. iterator and  Pointer in node/VO class
  4. Construct tree, hashmap or Sorted array as auxiliary, or for memoisation
  5. Recursion
  6. sentinel node trick: array/slists

The tools below are more specialized and less widely relevant

  • Graph traversal, recursive or iterative..
  • Permutations etc, recursive or iterative ..
  • Std::lower_bound etc
  • sorting

The topics below are Not really for a coding test:

  • DP
  • concurrency
Advertisements

##top5 std::map tasks 4cod`IV

custom hash func? See short example on P 364 [[c++standard library]]. [[optimized c++]] has many examples too.

initialize? There’s a simple constructor taking a long initializer, but the insert() methods support the same and are more versatile.

insert? single pair; range (anotherMap.being(), end());

** insert single value — won’t overwrite pre-existing
** map1.emplace(…)
** map1[key2] = val3 // overwrites pre-existing
** insert list of values — http://en.cppreference.com/w/cpp/container/unordered_map/insert

(returning the value) lookup? at() better than operator[]

a pointer type as key? useful technique.

erase? by a specific key. No need to call another function to really erase the node.

Q: create only if absent; no update please
A: insert()

Q2: create or uppate
Q2b: look up or create
A: operator []

Q1: update only; no create please
Q1b: look up only. No create please
A: find() method

Q: check for existance
A: c.find() is slightly better than c.count() esp. for multi_* containers

 

##9dataStruct(+..)for TIMED c++cod`IV

  1. generate a range from 1 to 9 — xrange() for py
  2. vector (more useful than array), std::string (more useful than cStr). Many string operations are still unfamiliar
    1. Array-based data structures are required in 80% of my coding tests.
    2. More than 50% of all my coding tests require nothing but arrays.
    3. Most of my toughest coding tests are presented in arrays but may need maps as helpers
  3. basics of map lookup
  4. sorting, operator<(), upper_bound, binary search … on containers
  5. sorted data structure (like std::multimap)
  6. [w] stringstream — ECT to improve

Very few NY interviewers would test you on graph or DP. Here are other less important constructs:

  1. [w] binary tree is common and simple, but they can ask very tough questions on it!
  2. [w] double pointer is trickier and my advantage
  3. [w] Node class in a linked data structure.
  4. [w] stack, queue.
  5. [w] grid or matrix
  6. file I/O? only for IDE tests, not pure algo or take-home tests
  7. [w] basic syntax for pointer arithmetic.
  8. [w] dtor, copier, op=? only for design questions, not algo questions.
  9. [w] shared_ptr? Only for design questions, never needed in algo questions!
  10. [w] ref variable only as function I/O.
  11. stl algo? Only Citadel array-shrink
  12. never exception
  13. never template
  14. no (very, very seldom) threading in coding Q
  15. adv: pointer to function
  16. adv: circular buffer
  17. [w = no weakness]

 

c++4beatFronts: which1to LetGo if I must pick 1

What to let go, given I have limited O2/laser/bandwidth and mental capacity?

  1. give up BP — biggest room for improvement but least hope
  2. give up codility style — Just get other friends to help me. See codility: ignore overflow, bigO
  3. give up algo — already decent. diminishing return. Smaller room for improvement? But practice on some small algo questions can significantly improve my ECT.

##failed c++cod`IV: home^IDE^whiteboard:4 beatFronts

Here I only list the failed ones. There are many successful ones in ##some@the significant coding IV experiences

QQ BP ECT algo coding@where
 ? 😦 NA ? home GS tick-engine
NA 😦 NA ? home Tetris
 ? 😦 NA ? home Mac
😦 😦 NA NA home MS-comm #java
? ? NA 😦 home Amazon
😦 ? NA NA home MS itr
😦 ? NA NA home MS FIX
NA NA 😦 ? IDE FXoption codility #java
NA NA 😦 ? IDE Jump #3 codility
NA NA 😦 good IDE Bbg 2017
 NA ? 😦 good IDE Citadel array-shrink
😦 NA NA 😦 paper FB regex
😦 NA NA 😦 paper Goog
😦 NA NA ? paper Barc SmartOrderRouter #java
😦 ? ? NA NA paper UBS YACC #java
😦 NA NA NA paper Bbg London.
😦 ? NA NA paper Imagine Software

See C++(n java)IV tend to beat us]4fronts.

Q: where is my biggest coding IV weakness? crack the algo, complete in pseudo code, or get the damn thing to compile and work?

  1. take-home tests usually beat me in terms of Best Practice
    • possibly give up if I must give up something 😦
  2. timed IDE tests usually beat me in terms of ECT speed
  3. white-board tests usually beat me in know-how

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

 

44tasks@array,str,dict ] algoIV

See also ##9dataStruct(+..)for TIMED c++cod`IV

See also EPI300

With STL, py, java, c#, and every other language, I need to develop fast fingers (ECT) over these basic tasks. Muscle memory is best.

  1. custom comparitor for a payload Trade class; Specify it in vector sorting or BST
    • custom hashcode is only popular in Java algoIV
  2. — custom tree/link node structs
  3. declare node class
  4. initialize a bunch of nodes
  5. — #1 vector of int (vector of other data type is rarely quizzed):
  6. populate with hard-coded data
  7. populate with default values to a fixed size
  8. append, prepend, insert
  9. dump, iterate, size
  10. copy the container — py/java require explicit ctor
  11. join 33 vectors
  12. slice — harder for c++
  13. max
  14. binary search, lower_bound
  15. — #2 string:
  16. initialize with content
  17. dump, iterate each char, size
  18. prepend, append, trim
  19. insert_by_pos — not easy
  20. substr
  21. split at custom delimiter
  22. join 3 strings
  23. search
  24. replace_substr
  25. read-write char by index
  26. successive find of target string from left (or from right)
  27. comp, sort among strings
  28. — #3 lookup (usually dict or std::map)
  29. populate with hard-coded data
  30. strictly insert
  31. strictly update
  32. lookup, possibly with failure
  33. dump, iterate, size
  34. — tree map: lower_bound
  35. — Queue: deque, enque, front, back,
  36. — Stack: push, pop, top
  37. — linked list? no special tasks
  38. — misc essential iterator tasks
  39. prev(), next(),
  40. distance()

 

##tough n high-leverage c++topics#IV QQ

I used to feel I have so much learning(absorption) capacity, but now I feel in my finite career I can’t really master and remember all the tough c++ topics.

Practical solution — Classify each difficult c++topic into one of

  1. QQ: high impact on QnA interview, probably the only type of high-leverage tough topic. Largely textbook knowledge. As such I’m basically confident I can learn all the basics on my own (perhaps slower than Venkat), provided I know the topics.
    1. including “coding questions” designed really for knowledge test, rather than algorithm thinking
    2. eg: HFT, Venkat…
  2. high impact on algo coding IV? No such topic. These coding IV are not about knowledge in tough topics!
  3. ZZ: high impact on GTD zbs — inevitably Low leverage during job hunt
  4. 00: no high impact on anything

Q: Is there a tough topic in both QQ and ZZ? I don’t know any.

I think 00 will be the biggest category:

  • [00] template wizardry;
  • [00] template specialization
  • [00] MI;
  • [00] operator overloading;
  • [00] pthread
  • ————-
  • [QQ]
  • [QQ] move semantics
  • [QQ] [p] boost common lib
  • [QQ] optimization tricks. Remember MIAX and SCB IV by Dmitry
  • [QQ] [p] singleton implementation — not really tough
  • [QQ] pimpl — not really tough
  • [QQ] op-new/malloc (interacting with ctor)
  • [QQ] memory layout
  • [QQ] [p] struct alignment
  • [QQ] specific threading constructs
  • [QQ] smart ptr details
  • [QQ] ptr as a field
  • [QQ] implement auto_ptr or ref-counting string
  • [QQ] [p] UDP —
  • [QQ] [p] multicast
  • [QQ] select()
  • [QQ]
  • [ZZ] IDE set-up
  • [ZZ] compiler/linker/makefile details
  • [ZZ] debuggers
  • [ZZ] crash analysis, like segmentation fault
  • [ZZ] c^c++:SAME debugging/tracing/instrumentation skills #ZZ

[p=paper tiger. ]