Wednesday, December 2, 2009

list^vector, copier signature - bloomberg

Q: list advantage over vector?
%%A: no iterator invalidation
%%A: efficient head operation, without shifting entire array
AA: efficient insert()/erase() on internal positions, without shifting subsequent nodes, esp. if each object is physically stored in the array and expensive to copy. (In java, only the 32 bit address is physically stored in the array.) However, locating the position requires a graph traversal.

Q: vector advantage over list?
%%A: random access to internal nodes
%%A: sorting
%%A: less frequent (bulk) memory allocations. List must allocate memory for each new node
%%A: each node needs no pointer to next node

Q: efficiently find anagrams in a file of English words, using just one loop
%%A: create objects wrapping {original string, normalized string} and throw them into a list. Sort the list using the normalized string. But this is considered 2 loops.
%%A: throw them into a multimap instead, using a customized less functor

Q2: There are the 100 unique integers between 1 and 100 in a file, but one of them is deleted. How do u find it with 1 loop?
%%A: pre-compute the sum of 100, then subtract each number found

Q2b: five numbers deleted?
%%A: start with the 100-bit binary number of all ones – call it base. For each number (say 66) read from the file, shift a one by 66 bits (easy for a computer) and subtract it from the base. This will flip a single bit in base. In the end we are left with a binary number containing only five bits. To quickly find the most significant of the five bits, compute base-2-log and take the integer portion.

Q3: what’s the copy constructor signature?

Q3b: why override it?
%%A: a ptr field will be shallow-copied

Q3c: what if I drop the const?

Q3d: What if I drop the “&”
%%A: the pass-by-value will call copy ctor in another stack frame
AA: pbclone will call the same custom copy ctor recursively.
AA: compiler warning; infinite recursion and stack overflow

%%Q: in most companies, templates are too hard so people avoid creating home-grown templates
A: we avoid them but we do have some.

No comments:

Total Pageviews

my favorite topics (labels)

_fuxi (302) _misLabel (13) _orig? (3) _rm (2) _vague (2) clarified (58) cpp (39) cpp_const (22) cpp_real (76) cpp/java/c# (101) cppBig4 (54) cppSmartPtr (35) cppSTL (33) cppSTL_itr (27) cppSTL_real (26) cppTemplate (28) creditMkt (14) db (65) db_sybase (43) deepUnder (31) dotnet (20) ECN (27) econ/bank` (36) fin/sys_misc (43) finGreek (34) finReal (45) finRisk (30) finTechDesign (46) finTechMisc (32) finVol (66) FixedIncom (28) fMath (7) fMathOption (33) fMathStoch (67) forex (39) gr8IV_Q (46) GTD_skill (15) GUI_event (30) inMemDB (42) intuit_math (41) intuitFinance (57) javaMisc (68) javaServerSide (13) lambda/delegate (22) marketData (28) math (10) mathStat (55) memIssue (8) memMgmt (66) metaProgram` (6) OO_Design (84) original_content (749) polymorphic/vptr (40) productive (21) ptr/ref (48) py (28) reflect (8) script`/unix (82) socket/stream (39) subquery/join (30) subvert (13) swing/wpf (9) sysProgram` (16) thread (164) thread_CAS (15) thread_cpp (28) Thread* (22) timeSaver (80) transactional (23) tune (24) tuneDB (40) tuneLatency (30) z_ajax (9) z_algoDataStruct (41) z_arch (26) z_arch_job (27) z_automateTest (17) z_autoTrad` (19) z_bestPractice (39) z_bold (83) z_bondMath (35) z_book (18) z_boost (19) z_byRef^Val (32) z_c#GUI (43) z_c#misc (80) z_cast/convert (28) z_container (67) z_cStr/arr (39) z_Favorite* (8) z_FIX (15) z_forex (48) z_fwd_Deal (18) z_gz=job (33) z_gzBig20 (13) z_gzMgr (13) z_gzPain (20) z_gzThreat (19) z_hib (19) z_IDE (52) z_ikm (5) z_IR_misc (36) z_IRS (26) z_javaWeb (28) z_jdbc (10) z_jobFinTech (46) z_jobHunt (20) z_jobRealXp (10) z_jobStrength (15) z_jobUS^asia (27) z_letter (42) z_linq (10) z_memberHid` (11) z_MOM (54) z_nestedClass (5) z_oq (24) z_PCP (12) z_pearl (1) z_php (20) z_prodSupport (7) z_py (31) z_quant (14) z_regex (8) z_rv (38) z_skillist (48) z_slic`Problem (6) z_SOA (14) z_spring (25) z_src_code (8) z_swingMisc (50) z_swingTable (26) z_unpublish (2) z_VBA/Excel (8) z_windoz (17) z_wpfCommand (9)

About Me

New York (Time Square), NY, United States
http://www.linkedin.com/in/tanbin