add a field in each node to simplify algo

In some algo questions, I like to add a tiny “metadata” field to the VO.

Q: how likely is interviewer to accept it?

A: I feel west coast interviews tend to entertain crazy ideas since algo challenges are more free-flowing, exploratory, thought-provoking. I remember the Bbg FX interviewer (Karin?) said my “in-place” is OK if I append to the existing vector then truncate the original portion.

A: I feel if it’s clever then they may appreciate it.

Space/time trade-off. The metadata field

  • can be a pointer to parent or next node (like LinkedHashMap)
  • can be an iterator into another data structure
  • can be the element’s own address if not already available
  • can be a sequence id as sorting key
    • insertion id is popular,
  • can be a bunch of flags packed into 8-bit integer

 

Advertisements

leetcode/hackerrank/geeksforgeeks.. #2D

My weakness — 2D problems

https://www.hackerrank.com/dashboard

  • ^ provides practice to hackerrank interviews
  • ^ organized by language and technical domain
  • ^ has a personal profile to build and show
  • ^ you can test your code, in many languages including C++, java, python
  • ▼ no solution

http://www.geeksforgeeks.org

  • ^ organized by language and data structure etc
  • ^ detailed explanation in each question
  • ▼not so many per-employer questions, but many question are rumored as “asked in XXX”

–leetcode

  • ^ The top-voted discussion posts are probably correct and often extremely short solutions!
  • ^ you can test your code, in many languages including C++, java, python
  • ^ you can see difficulty level
  • ▼you can see all Bloomberg questions, but this may require payment

–careerCup

  • ^ organized by employer

— hacker earth has many coding challenges, and many practice problems.  https://www.hackerearth.com/problems/

notable linux system calls: QQ question

https://syscalls.kernelgrok.com can sort the functions by function id

http://asm.sourceforge.net/syscall.html is ordered by function id

  • fork()
  • waitpid()
  • open() close() read() write()
  • –socket
  • socket() connect() accept()
  • recvfrom() sendto()
  • shutdown() is for socket shutdown and is more granular than the generic close()
  • select()
  • epoll family
  • –memory
  • brk

[18]why I avoid Java jobs #XR

My best recruiter Greg has discussed java roles with me many many times, in depth. Greg really listens and understands me. He showed me that java roles can pay on par with c++ if not higher.

I also agree with you that in financial IT, java is the reining top dog and there’s no credible challenger in sight. I think java will be top dog for 10 more years or longer.

Q: So then why do I turn down all java opportunities?

If java is a wing on my back, I’m not amputating this wing. I am committed to keeping my java skills up to date. I may switch to java in x months.

However, over many years I have invested heavily in c++ as another wing. Finally, this wing now feels firmer and stronger and I am going to test it, again, and again. If I start looking at java I’m going to lose focus.

c++ is harder in projects, and in interviews. It keeps my brain active — anti-aging. If I were to remain in java, i would feel bored and get old faster.

Many fellow c++ developers tell me java developers far outnumber c++ developers, so competition in java field is tougher. Therefore, they feel more secure in the c++ job market. I share that feeling to some extent.

I do feel stronger and more confident after conquering c# and c++. I also feel stronger due to python because I can now add python to my power tools.

As programmers, we all feel stagnant sometimes in our career growth. I tried many paths to break out of my stagnation. After java swing (partial success), c# (success), quant (unsuccssful) and python, C++ is now my chosen path.

I feel your chosen break-out path is data science applied to trading strategy discovery. Just as I sacrifice financially to grow my c++ wing, you may also make a sacrifice for your new career direction. I am sure you will learn something meaningful and your sacrifice will not be in vain.

Lastly, allow me to repeat that I don’t feel the need to earn the highest salary that’s available to me. I am not a slave of pay rate. I don’t have debt burden so I have financial freedom to take on new challenges that are worthwhile to me.

In 10 years I might regret “… not so worthwhile, just another broken dream like quant dream” but at this moment, I am convinced — yes worthwhile.

This is one of my many answers to the titular question. I’m asked the same question repeatedly and have given various answers.

Gayle: no rush2write code@@ #whiteboard

Gayle strongly advocates to get a brute-force solution as soon as possible, and walk through the “idea” in detail, before coding. However, I’d rather start coding up my idea much earlier since I need more time coding.

I guess Gayle’s experience shows that some interviewers are less worried about runnable working code than the thought process. For a tricky algo, if the idea is sound, then you basically pass….? See with algo cracked,ECT=雕虫小技

However, I feel an elaborated/detailed “idea” (item 2 below) alone is not enough to pass. I frequently run out of time implementing things like https://www.geeksforgeeks.org/print-a-given-matrix-in-spiral-form/. The algorithm is simple and not worth 40% but I was too slow completing a basic implementation. “Done is better than perfect”. Basic implementation is better than no implementation. You need to demonstrate you can implement a working solution.

Here’s my estimate of the point distribution in a typical whiteboard interview:

  1. 10(% clear understanding of requirements + clarifying questions
  2. 35(50)% detailed idea (even unimplemented) with decent performance enhancement
  3. 35(20-40)% basically working implementation.
  4. 5% performance analysis — can be tricky
  5. 5% readability — modularized, clean
  6. 5% eyeball test — can be hard to get right if code is convoluted with many variables
  7. 5% minor bugs, corner cases

unordered_map^map performance: unpredictable

Small halo, but the theories and explanations are subject to change.

Many people report that unordered_map can be slower than traditional std::map. I feel it’s implementation-dependent. Result may not apply to java or c#.

https://blog.dubbelboer.com/2012/12/04/lru-cache.html is mostly about lookup speed. It shows that key size (long strings) hurt hash table, and sample size hurts RBTree.

Hash collision is another potential problem. No one can really guarantee the next sample will be “uniform” according to our hashCode() function.

Cache affinity is another reported problem with hash tables.

Practical suggestion — it’s easy to swap the two in a given codebase, so just swap and benchmark. Either can be faster. If your data set changes over time, you may need to re-benchmark.

c++QQ interviews(HFT): not pickier than Facebook

I feel my HFT interviews are very picky on low-level kernel or compiler optimizations or network card engineering, but such QQ knowledge is not widely needed.

Don’t feel inferior to them.

  • Q: what if a HFT programmer goes to a Facebook interview?
  • Q: what if a coding contest champion from Facebook goes to an HFT interview?
  • Q: what if these guys go to a tough logic or probability quiz?

HFT interview is rarely about algo or ECT.