bigO CIV: clarify_requirement means..

———- Forwarded message ———
Date: Tue, 9 Jul 2019 at 23:10

Big-O means “worst” case complexity. We need to be doubly sure what “worst” case data look like. (Note it doesn’t mean ridiculously rare data like integer overflow.)

On high-end coding interviews, these “worst data set” frequently shed light on the structure of the original problem, and often point to the correct direction for an efficient solution. (Note a nice-looking solution is not efficient if it exhibits poor time complexity in the face of a worst yet realistic data set. Such a system may not scale well in practice, given its Achilles’ heel.)

If interviewer wants a solution optimized for bigO time complexity, you can waste precious time tackling the wrong problem. The wrong problem is the problem defined by your idea of “worst data set”, but the real worst data set is very different.

Sometimes, the worst data is _subtly_ different but it points to a different algorithm direction. It may point to an iterative solution rather than recursion, for example.

The original interview question may not be that hard iFF we identify the worst data set early on, but sadly, we run out of time.

For some tough problems, the first (sometimes the only) challenge is quickly identifying worst data set. Interviewer always gives you the simple data set, NEVER the worst data set. It’s your job to identify the worst data set… often the key insight into the problem.

It’s no exaggeration to say — identifying the worst data set early or too late can make-or-break your chance at this employer. You may kiss good-bye to this job opportunity exactly because you are too slow to identify the worst data set. I know what this means. Other candidates probably got shot by this arrow on the heel, without knowing what happened.

Time is ticking as soon as the problem is presented to you. If interviewer says time is not a factor… take your time.. we want quality and thought process … I just ignore it. Our speed is always part of assessment. Therefore, a very common failure scenario is —

.. tractable problem but candidate runs out of time after wasting time on preliminaries like using incorrect worst data set to reason about the (wrong) problem.

Advertisements

CIV: dataStructure-heavy problems are more realistic

Rahul said something like in real world designs, data structure design techniques is more relevant than smart algorithms.

I also feel most of the dataStructure-heavy algo questions are more realistic less contrived.

The Indeed questions are all dataStructure-heavy

## few theoretical compSci constructs for CIV

“Most comp science constructs are too advanced too complicated for a 45-minute coding interview. So reading any comp science book is like a student reading a science book not written for is exams. What a candidate need is practice targeted at interviews.”

Q: How about coding interview books? Can help. They are not as deep or wide ranging as algorithm books.

Q: how about bigO on common data structures? Yes relevant because of the interviewer’s insistence.

  • technique: back tracking
  • technique: shortest path
  • technique: disjoint set
  • technique: segment tree
  • technique: DP and greedy
  • technique bottom-up DP with memoization

Vultr.com linux on cloud 149.28

Today I managed to set up a simple, functional linux machine on the cloud

—- login via ip4v address 149.28.37.xx
I had to pick a “server size” big enough to get an ipv4 address. The smallest i.e. cheapest server size has 500GB bandwidth.

It takes a few seconds to deploy the instance and get the ipv4 address + the root password. I was then able to ssh as root from my windows git-bash which provides a functional ssh client.

—- github set-up
I had immediate access to github.com — a big win over Oracle virtual box 🙂 Not hard to set up my username, email address, credential store (to git-push quickly)

I needed to set up vim to edit my commit messages. Default was something unfamiliar, perhaps Emacs.

—- other set-up
My full screen is automatically usable, a big win over Oracle virtual box 🙂

I was able to install g++ and python, within seconds.

Once I ssh in, I changed the root password, because the generated password was hard to remember. The password to log in on http://www.vultr.com is separate and pretty long — 10-char.

I was able to log in again and see my personal files intact. So the same physical instance is still there.

—- cost: $3.50 a month for my instance.

I was told that as soon as I destroy (not “stop”) the instance, the “meter” stops ticking. All instances are billed hourly up to the monthly cap of $3.50, even if they are up everyday. The hourly rate is determined by dividing the monthly rate by 672 hours (28 days).

I had to provide my credit card details. To prevent accidental charge, need to destroy all instances after use.

 

CIV: we wish all corner cases+worst data sets r given

In a few problems, the real important “Aha” is getting the full list of corner cases. This list define the boundary of the problem, and would point out the direction, often immediately.

Of course coding test won’t give you the time.  Part of the skill tested is “clarifying requirement”. This is the real meaning.

Sugg: probe the interviewer

Sugg: Gayle pointed out some techniques to create some test data to reveal the boundary

FAQ@leetcode user guide

–“favorite”

For each question, these controls are found beside the votes.

I use the “Favorite” list to indicate “fuxi”

— personal notes on each problem

On the far right edge there’s a hidden button.

Under MyAcct, there’s also a readonly “NoteBook” i.e. all the problems having some notes.

Perhaps use the c++ code editor?

 

leetcode/hackerrank/geeksforgeeks..Q-selection priorities

–problem selection criteria

  • favor problems of my weakness
  • favor problems with more likes, or oldest problems on leetcode
  • favor “hard” problems, to protect self-esteem
  • For no-clue “ez/med” problems, just read the discussion, to minimize tcost. Similar to high school cram
  • For tractable “ez/med” problems, …?

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”

https://www.hackerrank.com/dashboard

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

–careerCup

  • ^ organized by employer
  • ^ no solution

–bloommerg (https://codecon.bloomberg.com/) is fine

  • ^ no solution

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

[19]cod`drill: XR discussion #low-end WC jobs

sustainable learning — Am not aiming for efficient learning. Instead, am aiming for sustainable learning. So I prefer problems without known solutions.

Life-long — Coding drill could become a lifelong hobby just like yoga. My tech-learning used to be 10% on coding drill but now 50% on coding drill. Ditto with yoga.

I can see my “west-coast coding IV” performance improving. It is still below the bar at Indeed, but I made big progress at the unfamiliar task dependency problem.

The harsh reality is, we are competing with fresh grads or even interns. Better accept the reality rather than burying our heads in the sand.

There are a large number of easier jobs on the west coast, so perhaps apply remotely and attend the remote coding rounds for practice.

The west-coast CIV is a more /level playing field/ than QQ IV. More objective. Am not negative about it.

versioned dict #indeed

Suppose a resume consists of key/value pairs of strings. We need to support two operations —

  1. Each write(key, value) operation creates or updates a key with a new value, and returns an incremented integer vid i.e. version ID. A version ID represents a point in history, i.e. a snapshot of the entire resume
  2. Each read(vid) returns a key/value dictionary as a complete resume snapshot
  3. * In a realistic system, we also need a deleteVersion(vid) but no need to optimize for it

Single threaded system. Version 0 is an empty resume.

Q: design an efficient solution.
Q: after creating N versions via N write() operations, what’s the time and space complexity of next write()? What’s the time and space complexity of the next read()?

——-

Without loss of generality, Let’s say there are K fields in the resume version N. Note K <= N. I should have differentiated K and N, which is useful for my clarity of thinking.

—Design 5 in hind sight, optimized for read(): Simple solution would snapshot entire dict at each write() i.e. each version. Space complexity is bad (I now believe time complexity is more important.) Worst case — K==N as version1 creates key1, version 5 creates key5 etc.

A single read() is presumably O(K) just to read the K fields. I was convinced this was the theoretically limit for read() complexity, because I was thinking of network serialization — either my system or client system need to iterate over all fields of the resume. Now in hind sight I feel interviewer was thinking in java mode — to return entire dict by reference is O(1) rather than O(K) … I didn’t get his hint when he said O(K) read was not really theoretical limit.

Each write() clones the dict for a new vid and saves the new dict in a vector of pointers (!) . Therefore write() is O(K).

—My design 1, Based on the same idea, I used a vector for each key. However, my read() had to create a dict to be returned, on the fly in O(K). I didn’t think of return-by-reference/pointer.

—My design 2 is a minor optimization to remove the cloning of unchanged values. I thought I was on to something efficient but in java (and python?), all strings are copied by reference so my optimization is meaningless in java.

—My design 3 is lazy write. So write() only appends to one of the K vectors. The other K-1 vectors are updated only when needed by a later read() or write(). Amortized cost?

This O(1) write() and O(?) read() complexity can be emulated and surpassed by …

—My design 4 used K RBTrees (small trees) to optimize for frequent write() at O(1). Each write appends on one tree. STL insert with hint is O(1). No such feature in java or python.

Read(vid) requires binary search in each [3] of K trees. After N updates, total node count across all K trees is N, so even a naive search would not exceed O(N).

If needed, I can also maintain at O(1) cost a “replay vector of originals” i.e. original {key, value} from each write(). We can use this vector for replay.

[3] Q1: Can we avoid scanning all K trees when vid is small or K is much smaller than N ?

A: Like rebus, let’s maintain a separate vector (or RBTree) “birthday” holding records {vid, pointer to a single small tree}. Birthday expands (O(1)) by one element whenever a new small-tree is born i.e. new key is created. My read(vid=55) would binary-search in this birthday data structure using vid to locate the last-born small-tree before version 55, and then iterate backward to visit each small tree born before version 55. This optimized read() uses binary-search throughout to eliminate unnecessary linear search.

Q1b: Worst case read():  K == N i.e. every write() creates a new key. So read() is still O(N)?

A: If we find out in practice K is close to N, we can use additional data structure to save previous read(vid) results. I can use a vector of records {vid pointer to read() result}, keyed by vid. Each read() would save, at O(1) cost [4], the result in this memoization vector. For the next read(vid=77) I would use binary search in this memoization vector to find the closest lower neighbor (eg 55), then replay from vid=77 towards  55, using XR’s algorithm.

[4] see my blogpost on memoization keyed by auto-increment id

Note RBTree supports efficient deletion from both birthday tree + small tree.

—-

Now i feel a big string representing the entire resume is still under 100KB. I assumed were were talking about millions of fields of gigabytes each.

For a long time I was confused and assumed that each write() could update multiple key/value pairs.

cod`drill:YOUR satisfactions@@ wipe_out defined #Rahul

Rahul used the word “satisfaction”. (Sometimes I call it “intrinsic motivation” or “joy”.) The satisfaction factor is crucial to absorbency. It enables Rahul to put in so many hours.

Q: What are my satisfactions i.e. intrinsic motivation?
A: discover my own solutions that are reasonably efficient even if not optimal. Almost never elegant and simple.

I don’t mind reading a classic solution in a Real (possibly online) publication but I hate to read solutions in forums as XR does. Those forum posts leads to wipe-out

  • completely wipe out that precious satisfaction.
  • positive feedback loop broken
  • self-esteem destroyed
  • self-mastery destroyed
  • sense of progress wiped out
  • sense of self-improvement wiped out
  • absorbency wiped out
  • I feel /diminished/ and worth-less.
  • i feel hopeless giving up

It’s possible that the forum posters also learned the solutions from publications. But I basically assume they are just so brainy.

short+efficient : holy grail ] algo search

For most of my tough algo problems (such as leetcode problems)

  1. many celebrated solutions are very short, but not so efficient
    • I think about 60% of them are easier to memorize due to length.
    • if you can understand and memorize them, they are quicker to write due to fewer keystrokes
    • About half of them are easier to understand, thanks to the source code size
    • eg: yield-based generators are a prime example
    • eg: recursive solutions are often brief but inefficient
  2. many great solutions are efficient in terms of O(), but verbose
    • eg: bottom-up DP
    • eg: top-down DP with memoization
    • eg: using a tree (when not required) can sometimes give an efficient solution

However, these two goals are often hard to harmonize. It is my holy grail to meet both criteria simultaneously, but i won”t try so hard.

  1. For real coding problems, I will prefer brevity
  2. For verbal discussions, I will concentrate on efficient solutions

##a few Advanced algo IV categories #study

By “Advanced” I mean — the average programmer without focused study will likely struggle.

  • problems that require recursion-in-loop — rather common
    • but I have analyzed quite a few. Now at a plateau. No thick->thin
  • grid or matrix problems — more common than I thought. My weakness,
    • but I have invested quite a bit. Fast early ascent is over
  • graph problems — sometimes harder than average. Hard for everyone but I often fare better.
  • DP and greedy problems — occasionally easy, but usually non-intuitive
  • single-str or two-str problems — usually hard
  • num-array problems
  • generator problems — not so common
  • problems that require backtracking — rare

However, some of the hardest problems involve nothing but an int array or a single string.

Q:how much syntax2memorize4speed cod`#python

I would say 5 times more than needed on the job.

Treat it like timed coding competition.

Compare to exam preparation in China.

—- python coding drill for indeed:
small problems using lot of python data structures around chars, strings, arrays
fuxi python blog posts
list comp
define classes with fields
combine multiple lines to 1
triple quote comments

xp: pure algo question often require QQ 打通脉络

  • eg: bbg 2017 pure algo question on tree serialization required a standard BFS. Just a few lines but I struggled for a long time. If you memorize the key parts and practice enough, then the *knowledge* would show as a algo skill
  • eg: facebook regex is very hard to anyone I know, unless they worked on a similar problem before, and *know* the tricks.
  • eg: generate permutations, combinations. Can be tricky unless you *know* the key points.
  • eg: DP bottom-up vs top-down with memoization
  • eg: SCB-FM IV: stack-based queue
  • .. many more examples

打通知识脉络 is the Chinese phrase

required experience: QQ imt CIV

A few years into my technology career, I observed that Solaris/Oracle was harder to self-teach at home than linux/mysql/php/python/perl/javascript because even a high-school student can install and hack with the latter. Entry-barrier was non-existent.

Similarly, I now observe that Wall St QQ-IV demands longer experience than coding IV of west-coast style. Coding drill can use Leetcode over months. QQ requires not so much project experience but a lot of interview experience. It takes more than months of exploration and self-learning.

  • example — tcp/ip. My friend Shanyou preferred to read books systematically, but a book touches on hundreds of topic. He wouldn’t know what topics interviews like to dig into.
  • example — c++ TMP. A fresh grad can read about it but won’t know the favorite topics for interviewers
  • Compelling Example — java concurrency. A fresh grad can build up theoretical knowledge but won’t have my level of insight

Many inexperienced candidates were highly appreciated in west coast interviews. No such appreciation on Wall St because Wall St can VP or contract roles require work experience .. tried-n-tested.

  • Wall St interviews are selective in terms of experience
  • West Coast coding interviews are selective in terms of … speed and optimality

cod`drill^quant self-study

quant knowledge used to be a halo, now replaced by coding IV skills like

  • classic generators
  • DP, recursion
  • clever data structures
  • clever graph algos
  • speed coding

In 2012 When I was studying quant in my spare time, I was on a powerful ascent. In the subsequent years, I gradually lost steam. The quant sector was shrinking and market depth was disappointing.

Since 2018, my coding drill feels very relevant, even though the gap behind the strong players continues to be a pain and a de-motivation. When I stop comparing myself with the stronger players, I would feel my improvement in a highly valuable skill

%% absorbency: experiment/SDI imt speed-coding

When you find yourself in high-absorbency mood, favor (#1 most draining) speed-coding. See list of less-draining drills at the bottom.

I can read dry QQ topics for hours each day for many days, but tend to lose steam after coding for a few hours. Speed coding drill drains my “laser” energy faster than QQ reading/blogging/experiment. When my laser is weakened (by boredom), I must drill harder to go through the “brick walls”.

I guess many fellow programmers enjoy coding more than reading. I feel lucky that in my interviews, knowledge tests still outweigh coding test.

Q: What part of coding drill is worst on my absorbency?

A: speed coding implementation is worst. It drains my laser energy fastest. After coding for a few hours I always feel like a deflated balloon and discharged battery and and need a full day to recharge.

I think frustration is the key. Self-expectation (about progress and traction) and self-image create the frustration and the drain.

Instead of traction, I often feel stuck and overspent.

I feel disappointed with myself (Deepak self-identify as “annoyed”. )

Q: Can we stop comparing with others and just compare with our past? Doable sometimes. Consider Leetcode speed-coding contest #Rahul

— Just like yoga

  • if I work on easy problems I feel wasting my time
  • if I work on tough problems I feel painful, draining and want to give up. After the practice i need hours to recover.

Q: … So can we find easier coding drills that I could enjoy (as Rahul suggested)? Definitely not easy. I think the first difficult step is self-acceptance that I can’t improve much at this age.

Q (excellent question): What type of “coding” drill can I do for hours like reading/blogging?

  • pseudo-code algo on paper/whiteboard is lighter. No ECT so I am swift and efficient. Less draining/frustrating.
  • SDI is most fun, least boring, not draining/frustrating. I can spend hours on a SDI. I feel a bit of accu. More like QQ less like coding drill.
  • concurrency coding questions are less draining as other guys are not faster
  • c++/java language feature QQ experiments are more like QQ. I can spend hours on a QQ experiment. More interesting as there’s no time-line no benchmark no frustration. Also other guys are not stronger. I feel some accu exactly like reading on these me features
  • review of my previous code is much less draining (than writing new solutions) as there’s no time-line and code is already working
  • analyzing patterns and reusable techniques (very few) in past problems. Thick->thin is the holy grail. I work hard towards it.
  • reading syntax and ECT tips in books and my blog

 

#1(reusable)AuxDS for algo challenges

Here’s a Reusable data structure for many pure algo challenges:

Construct a data store to hold a bunch of “structs” in linked list OR growing vector (O(1) insertion). Then we can build multiple “indices” pointing to the nodes

Here are a few average-O(1) indices:
(Note O(1) lookup is the best we can dream of)

  • hashtable keyed by a struct field like a string
  • array indexed by a struct field like small int id
  • If there’s a non-unique int field, then we can use the same array lookup to reach a “group”, and within it use one (or multiple) hashtable(s) keyed by another field

Will tough coding IV decline]10Y@@ #Rahul

It’s possible that as easy coding IVs spread or grow, tough coding IVs decline i.e. less wide-spread. In such a case, my t-investment now will have lower ROTI than expected.

It’s possible that as easy coding IVs spread or grow, tough coding IVs also grow … for differentiation of talent.

Rahul responded to my question and pointed out the two styles of interviewers he observed:

* interested in can/can’t solve — can this candidate get the problem solved in time?
* interested in thought process

Rahul felt the first type will want to use ever tougher problems to pick outstanding candidates… selectivity

Rahul felt the second type will want to use easier problems to get more insight into the candidate’s thought process.

Rahul felt to differentiate, employers can compare completion time on easy questions

3Hr@knapsack problem..overspent@@

I spent 2-4 hours implementing/refining my own knapsack DP solution — https://github.com/tiger40490/repo1/blob/py1/py/algo_combo_perm/knapsack.py

Many “peers” would consider it overspent. This kind of “conventional” view tend to destroy the precious satisfaction, the wellspring of positive energy.

Some peers complete it in a hurry and move on.

They may not compare it against the comboSum problem … x-ref is crucial to pattern recognition

They may not learn a lot by doing it quickly. I wouldn’t learn much of anything if I do that .. 囫囵吞枣

%% pure-algo/dStructure skill@recent CIV

Hi Friends,

Over recent (about 12) months I have attempted several coding interviews

  • passed a Standard Chartered pure algo test over phone, short questions but non-trivial
  • probably passed a big weekend coding assignment given by an e-commerce start-up. I later found out my solution is similar to a published topological sorting algorithm so my algo is probably close to optimal.
  • passed another weekend big coding assignment given by Nasdaq
  • passed two separate paper+pencil coding tests at two reputable sell-side firms (i.e. banks or brokers)
  • passed a speed coding test at a reputable internet company headquartered in Texas.
  • probably passed a few bloomberg coding tests, both remote and onsite, on computers or whiteboard.
  • (All recent failed coding tests happened at High-frequency trading shops .. very picky.)

All of these positive experiences convinced me that my algo and esp. data structure skills are improving. So I gave myself a rating of “A-minus” among Wall Street candidates. I felt esp. confident with white-board coding — with a real compiler, my proficiency is lower than other candidates.

Then I failed, on technical ground, at two big internet companies (FB and … let’s say company XX). Ironically, these were white-board pure-algo problems involving non-trivial data structures — my traditional strengths. So what’s going on? Unexpected failures deserve analyses.

— First, I think I was still too slow by their standard. One interviewer (at XX) told me they wouldn’t reject candidates because of slow completion, but I believe that’s not what she actually meant to say (She is not native speaker). Suppose a candidate takes a long time to come up with a sub-optimal solution, I actually believe given more time he would find an optimal solution because I am that type of candidate. But interviewers would have to assume he is weaker than those who complete the optimal solution quickly.

Interviewers often say they look out for thought process, but that’s probably something they look out for in-addition-to finding decent solutions in time. I think I tend to show clear (not always correct) thought process but that’s not enough.

I think those interviewers really look for “near-optimal solutions but not because candidates memorized it before hand”, so candidate need to 1) find good solution 2) be able to explain when challenged.

— Second, I think the competitors are stronger (faster) than on Wall St. I call them “west-coast competitors” though they could be working in any country, all competing for west-coast tech jobs. I guess they practice hundreds of problems at Leetcode. Such heavy practice doesn’t guarantee success but increase their winning chance.

— Third, I think my big-O estimate needs improvement. I made multiple mistakes at XX coding rounds, and elsewhere.

Big-O has never been a show-stopper in my Wall St interviews so I didn’t pay close attention on details.

— Fourth, I think I have not tried often enough. If I keep trying similar internet companies I might get lucky and score a technical win.

—-

Given the stiff competition and high standard at west coast coding tests, I now feel it’s extremely important to set intermediate goals

  1. goal — pass some quick algo quizzes given by west coast interviewers over phone. I used to get those quizzes from Google phone round
  2. goal — pass some initial (simpler) coding round via webex/coderpad
  3. goal — impress at least one interviewer at one coding round. I can often sense that an interviewer is delighted to hear my idea
  4. goal — impress multiple interviewers, even if your solution is not optimal. I achieved this at Bloomberg
  5. goal — pass all coding rounds at a reputable west-coast tech shop — which is my original goal, never achieved
  6. goal — 100% technical win i.e. pass all technical rounds including system-design-interviews. Note you can still fail the soft skill test.
  7. goal — get an offer

With these intermediate goals, the picture is no longer black and white, but grayscale. We might have hit some of the intermediate goals already 🙂

prevalence@speed coding among coding-IV

25-33% of my past coding IV (counted by hour) were tough Speed-coding. The remaining hours were

  • Easy speed-coding problems, easy to me
  • no-coding Pure-algo quizzes, often telephonic
  • Take-home assignments
  • Threading
  • latency engineering
  • test of language knowledge
  • SDI without implementation

— west-coast coding IV≅speed-coding contest

The skillset is unneeded on any job. For GTD or PKI, this skillset is not in top 10

You need everything fast. Many students practice heavily to gain speed.

 

%%AuxDS strength ] coding test #algoQQ

Update — Indeed experience..

  1. when a tough problem requires us to construct an explicit and non-trivial auxiliary data structures (AuxDS), i often have an intuitive feel for the data structures needed, not always the optimal.
  2. when a tough problem requires a simpler AuxDS + unusual algo, I don’t have an edge.
  3. When a tough problem requires only an unusual algo, I don’t have an edge.
    * eg: edit distance
    * eg: sliding window max
    * eg: maximal sub-matrix

    • Suggestion: invest in algoQQ. I feel they will stick with me.

Leetcode speed-coding contest #Rahul

  • don’t look at ranking
  • yoga — I CAN keep up this practice. This practice is good for my mental health and family well-being
  • yoga — I feel even if i don’t improve visbly, the fact that my participation count is increasing means I’m improving
  • if I don’t do the contest then I may not do any coding drill at all
  • What if I give up after one or a few episodes?
  • impact on family well-being?
  • leverage over long term?

In [[who moved my cheese]], we discover the world has changed. The harsh reality is, in this profession, your experience (like doctors) is heavily discounted. Your current runtime performance is easily benchmarked, just like a painter, or pianist, or chef.

G9 workhorse-algos ] speedCoding #XR

XR said we should take speed coding contests to find out what basic algos are needed.

Opening example — parent/child pairs→tree algos #Indeed is one example of realistic problem that requires common comp-science constructs…

Need to memorize enough to implement on the spot, as these are basic “comp science constructs” needed for “realistic problems”

  • dft/bft, with levels
  • BST find predecessor
  • Binary search in array
  • Merge-sort/insertion-sort/partitioning
  • .. realistic string problems:
  • .. realistic int array problems:
  • max profit; max subarray sum
  • .. realistic matrix problems:

Below are basic algos for hackerrank/codility but NOT applicable to realistic problems typical of Indeed/FB

  • Linked list: remove dupes
  • string: collapse consecutive chars

short coding IV: ibank^HFT^inetShop

See also prevalence@speed coding among coding-IV

  • “InetShop” includes all west-coast type of hiring teams including China shops
  • Ibanks are mostly interested in language knowledge, so they use coding test (including multithreaded) for that purpose.  Ibanks also use simpler coding questions for basic screening.
  • HFT shops (and bbg) have an unpredictable mix of focuses

I predict that Wall St will Not adopt the west coast practice due to .. poor test-coverage — Not testing language knowledge, latency engineering, threading etc.

The table below excludes take-home tests and includes hackerrank, white-board, webex, and by-phone algo questions.

ibanks web2.0 Shops HFT
language knowledge; latency NOT bigO #1 focus never key focus, not #1
simple-medium speed coding rare #1 focus. High bar common
medium-simple algo without implementation,
logistically easiest => popular
common #SCB
minimum bar is low
common key focus, not #1
tough algo never sometimes rare
big-O of your solution NOT latency LGlp. low bar #2 focus. high bar LGlp
concurrency coding test G5 focus never #python/ruby/js sometimes

 

tech firms value motivation in coding drill

I agree with you that to pass FB/Goog/indeed/twitter interviews, we all need to practice for months.

We also need to study the problem patterns during our practice. “Study” is euphemism for a hard long struggle. If we don’t put in a hell lot of focused energy, we can’t absorb the amount of variations and *recognize* the patterns — 从厚学到薄. Without learning the patterns, we will be overwhelmed by the sheer amount of variations in the problems, and forget a lot, as in 狗熊掰棒子.

Q: Why the hell do these firms like to hire coders who practice so hard?
A: My hypothesis:

  • such a coder is typically young — with plenty of spare energy and spare time. An older techie with kids is unlikely to endure such heavy coding drill. We lack spare energy and spare time.
  • such a coder has perseverance and dedication — hard-driving, hard-working, focused, achievement-oriented and determined
  • such a coder is able to tolerate repetitive, boring, lonely tasks — even joy the boredom. I call it absorbency capacity or 耐得住寂寞. This is not only attitude; but an aptitude. My son currently lacks this capacity, but my dad, my daughter and I have this capacity, to varying degrees.
  • such a coder is able to pay attention to details — Getting a program to work on a range of corner cases requires attention to details.
  • such a coder has a quick analytical mind for abstract logical problem solving

In contrast, financial firms target slightly different skills. Their coding questions test language-specific efficiency, language features, or pseudo-code algorithm. Tech firms don’t test these.

I don’t have2aim@optimal solution on Leetcode

My friend Shanyou consistently holds a position like “I don’t need to find the better solutions (forget the “optimal”). If my solution is brute force or non-optimal, at least it works, so it will be good enough for many interviews and good enough for my coding drill. Many candidates can’t find even a brute force solution in the given time, so if I strengthen my capabilities to this level it’s valuable.

Admirable !

That’s inner strength — 定力
That’s much-needed focus
That’s undervalued realism
That’s celebration of every progress
That’s a pat on our own back

The all-or-nothing, single-minded pursuit of optimal solution can often wipe out my motivation, joy, satisfaction, self-esteem.

It’s a common and fatal de-motivation to tell ourselves (like XR … ) “There’s no value in pursuing non-optimal solution.” Well there ARE a few:

  1. pride and achievement from completion of a tough challenge
  2. ECT, speed
  3. syntax idioms
  4. self-mastery, internal locus of control, similar to my yoga practice
  5. absorbency — demonstrate to myself; self confidence in absorbency
  6. joy, self-satisfaction — see exactly what I want{cod`drill beside immediate IV #Rahul
  7. … Other blogs provide other perspectives

!! Many published solutions are non-optimal in O()
!! Most solutions out there are non-optimal in terms of concise implementation, even if matching the best solutions in big-O.

Some interviewers only care about big-O and don’t care about too many loops; Other interviews want an elegant, simple solution; The most extreme interviews (FB?) score candidates on syntax and code quality too. Which one do you target? Realistically, I would take Shanyou’s target.

what I want{cod`drill beside tech muscle-build`#Rahul

Hi XR,

I had a brief chat with my young, talented Indian colleague (not the talented intern). He pointed out that he is making progress with his Leetcode real-code drill better than 2 years ago in his Master’s program, because at that time he was in a (job-hunting) hurry and under real pressure. I can identify with him — at present, both he and I feel low or no pressure to improve coding skill so our brains work more efficiently. When I made this point he immediately agreed.

Over-stress inhibits brain capacity; Insufficient stress reduces energy level in the brain.

This colleague always focus on passing Leetcode tests.

You asked me this question —

Q: so exactly what do you want from your coding drill? I won’t answer for my colleague, but my answer is related to him nevertheless.

Indeed if my goal was to pass coding interviews, then my real-code practice is not efficient and overkill. So why am I spending 20% to 33% of my coding drill effort on real-coding rather than reading key ideas… what’s the real reason? I described a fundamental reason in
https://bintanvictor.wordpress.com/2018/08/04/why-our-coding-drills-are-different-fundamental-reason/ but today I will shift focus.

  • A1: I want enjoyment, positive feedback, self-esteem, feeling good about myself …
  • A2: I want some sense of achievement — when you read posted solutions you probably feel you learned something and achieved something. I feel more achievement when I come up with my own solutions, even if not optimal nor elegant.
  • A3: I want visible progress— When you read posted solutions to three common questions, clearly you feel progress. That’s why you aim to study 800 questions. I’m different. I don’t feel significant progress reading posted solutions.
  • A4: I want self-mastery — overcoming many obstacles, similar to yoga. I want to regain control of my spare time and follow some self-directed course.
  • A9: I want to build my mileage — as in driving. Mileage means how many productive hours I have spent on coding problems since age 20. A1/A2/A3 above all help keep me focused on doing more problems. Even with all the joy, achievement and progress, it’s still very easy to give up or lose steam.

[18] Continuous coding drill #Shi

My friend CSY said some students like his son could conceivably focus “all their time” on one skill (coding drill) for fours years in college, so they will “surely” outperform.

I pointed out that I am often seen as such an individual, but my speed coding interview performance is hardly improving.

I pointed at the number of Leetcode problems I solved with all tests passed. It grew by up to 10 each year, but a student can solve 10 leetcode problems in half a day.

I gave an analogy of my Macq manager’s weekly slow-jogging, for health not for performance. Consistent jogging like that is great for health. Health is more important than athletic performance. I said jogging and my coding drill are life-style hobbies and recreations.

For years I practiced continuous self-learning on

  • java, c++, SQL, MOM, swing — IV and GTD growth
  • Unix, python — mostly GTD
  • quant

I consider my continuous self-learning a key competitive advantage, and an important part of my absorbency capacity.

I asked a bright young Chinese grad ChengShi. He practiced real coding for months in college. I said “fast and accurate” is the goal and he agreed. A few years into his full time job, he stopped practicing the same. Result? He said for the same coding problem he was able to make it work in 10 min then, but now probably 20 minutes. I think this is typical of the student candidates.

I asked “Do you know anyone who keeps up the coding drill?” He didn’t tell me any individual but gave a few points

  • he believed the only reason for coding drill is job hunting
  • when I said continuous practice all year round will make a big difference compared to practice only when job hunting, he agreed wholeheartedly and reiterated the same observation/belief
  • but he disagrees that continuous coding drill would lead to significant professional growth as a programmer, so he would probably channel his spare energy elsewhere.
  • I think he has other ideas of significant growth. At my age, I don’t foresee any “significant growth”.

our coding drills r different: fundamental reason #le2XR

Fundamentally, one chooses how to practice based on past interview experience of his own, not hearsays.

Question for you — how many times in the last 18 months did you get a coding interview that required 30+ minutes per question?

A: about 20 out of 25 positions in my recent experience, not including a BGC-partners onsite when they gave me 4 different questions but each 20 minutes only.

Most of my coding rounds are hackerrank/codility or over weekend.

  • Now I think for you the answer is 10% (but did you include those hacker rank tests?)
  • Now I think for you, mostly you don’t need to compile ! That’s why you call them “algorithm questions” rather than coding questions.

Even if I persuade you on the importance of edit-compile-test speed, or the value of python, sooner or later you would doubt “Really? How come I seldom need to write real code so fast in an interview?”. You would eventually stop practicing with real-code and refocus on pure algorithms, by reading key ideas behind common questions.

If you spend hours of focused energy writing real code as practice, and feel worn out, your own, personal experience would eventually kick in and remind you that it’s not worth it.

Conversely, if I were to follow your method to memorize key ideas only, my personal experience would soon shout out — “Take a step back and look again, you are already pretty fast coming up with data structure and algorithm ideas, but your REAL weakness is implementing them — too slow !”

I listed all recent interview episodes in tabular format — https://bintanvictor.wordpress.com/2018/04/28/some-worthwhile-coding-iv-experiences/.

  • 100% of big tech companies require at least one coding question lasting more than 30 minutes.
  • 100% of big buy-side shops require at least one coding question lasting more than 30 minutes.
  • More than 50% of investment bank jobs also require it.
  • For the other c++ financial companies (the so-called “third party” players) like Bloomberg, exchanges, brokers, market data providers, about 80% of the jobs require it.

peek@solution,get hint,then solve the problem yourself

I have found it rather important to follow this routine — Suppose a given easy or hard leetcode problem is too unfamiliar to me (might be familiar to you) so I have very few ideas, all on the wrong track. I would peek at the discussions to get some useful hint. I stop reading right there and go back to my drawing board and spend the next hour (or day) conceiving my own solution.

This has worked more than half the times. Benefit? I get to implement and remember my own solution.

There is a more important but subtle benefit — that hint is often related to a Reusable problem-solving technique, the holy grail of coding drill.

The way I see it, there are only a dozen or so (below 20) reusable techniques. Even if I were to memorize all of them, they would be useless to me because the real challenge is how to Apply a technique to a given problem. The way I learn to apply a technique is

* make sure I feel the hint i.e. it connects some dots in my mind
* experiment with various ways to use the hint to tackle the problem
* some experiments show progress; some become dead-end because they are the wrong ways to apply the technique
* keep sharpening "pattern recognition" until the key characteristics of the problem becomes clear in my mind.

The more I experiment with the hint, the more familiar I get… familiar with the problem, the hint, and the hitherto hidden gem behind the hint. That gem is often (not always) a reusable technique.

I won’t learn how to apply a Reusable technique if I don’t experiment, if I read a solution directly. The dots won’t connect. Pattern-recognition will still develop but slowly. Worse still, I may completely miss the hidden Reusable technique in the solution.

I always believe the real value in doing a Leetcode problem is the technique, reusable or not.

The solution I conceive will Not be as optimal as the one in the discussion … but it is easier to digest. The optimal solution in the discussion is usually rather concise (since the authors want to look cool) and elegant, but I don’t need to learn an elegant solution. I need to learn a Reusable technique. For that purpose, my own solution is easier to digest because it uses only a bit of the new technique + many familiar techniques.

[18] get ideas@G200 common Q #XR

Update — Now I realize my energy is limited so I need to allocate my spare time between

  • real coding
  • reading the key ideas

Also, I feel no positive feedback when reading the key ideas. I hit de-motivation.

Hi XR,

I now agree with your analysis — if I understand and memorize 1 key point about each problem, by reading leetcode, those points will help me significantly in a coding interview. This is one of the 4 benefits of coding practice #syntax,ECT,BP

  • If the problem is easy, then those key points will save me from running out of time.
  • If the problem is hard for everyone, then interviewer would have a lower expectation i.e. no need to complete it 100%. If I am on the right track (while other candidates are not) then i have an edge.
    1. case in point —- Last Friday I told you about shortest-path problems. I learned the technique from past interviews.
    2. case in point —- remember I told you about my own facebook question (3-way sorter/classifier #FB) Your swap technique is a valuable key point, even though it won’t help me finish the solution within 30 minutes
    3. case in point —- In 2018 I encountered comparable int array shuffling problems within 2 months at MS and LiquidNet. Key points are relevant.
    4. case in point —- In a 2018 interview, I learned to use N-by-N matrix to represent a N-node graph, then I used this key idea in another coding interview.

I wonder if I could get myself to follow a plan similar to yours:

  • every weekend (+ weekday evenings) spend 30 – 120 minutes.
  • First select some interesting” and popular question. If no idea, put it on back-burner
  • after a while, give up and read the solution to get the ideas
  • eg: edit distance
  • eg: punctuating continuous sentence
  • eg: regex
  • eg: maximum all-black sub-matrix

prior knowledge can make you look brainy: algo IV

After solving the min-stack problem, I found something paradoxical , even nonsensical — Someone said this question is considered “easy”, but if you have not seen it before then you may find it extremely hard. I thought O(1) worst case was impossible. I have experienced many similar situations where prior knowledge can make you look very brainy.
  • example — detect loops in a singly linked list, where the loop could be far out.
  • example — reverse an extremely long singly linked list which breaks any recursive solution, so you must use non-recursion
  • example — in a regular unsorted binary tree (every node has up to 2 child nodes and no uplink to parent) how to print all nodes in-order but with O(1) additional space and O(N) time
I feel west coast (and Bloomberg) tend to ask this type of questions because they expect their candidates to study and acquire the knowledge before applying.
If you don’t study, and hope to come up with a reasonable solution on the spot, then you must be extremely intelligent or lucky. I think the math Olympiad gold medalists also need to study before their competitions.

[18] confidence-build`:another reason y I don’t look@answer

Update — my view was overridden by recent IV experiences. In math problem solving, I studied solutions then built my intuition. My peers actually do the same with algo challenges. They become very confident this way.

–confidence-build`:another reason y I don’t look@answer

Hi XR,

Just to share some minor thoughts.

I solved many “hard” leetcode problems and also the 25-horse puzzle without peeking at answers. These problems are non-trivial, and my solutions are usually efficient but not easy to understand. They are part of a tiny but growing wellspring of technical confidence. They reinforced my self-image of analytical mind. Similarly, CSDoctor Wang often shows a healthy self-image of technical competence, based on many successful experiences. It’s hard to feel confident without experience, simply by reading other people’s answers. (Experience is not that effective at building confidence — we could get a string of unsuccessful experiences … but personal experience is usually the most important factor.)

Also, these problems gave me confidence during non-technical interview, so I could say with conviction that

I am confident with algorithms + data structures even though I’m not the best. I solved more than 20 of the hard leetcode problems on my own, without reading any discussion.

I won’t have the conviction to say the same if I mostly read other people’s solutions.

I sometimes give this long answer to the behavior question “Q: tell me your strength and why”

A: The best comp science students might have good answer to, say, 30% of a question pool including familiar and novel problems. I’m slightly below their standard. However, if the question pool consists of only familiar problems like Leetcode problems, then they would be much stronger than me since I don’t have very high mileage on Leetcode and similar sites. If you want to benchmark me then please pick highly non-standard questions. I am fairly good at creating original algorithms.

Some naysayers would cast doubt — Having solved those problems years ago doesn’t mean he can solve them now. Well, you can say the same about any skill, but we know that once the “circuitry” is wired up in our “system”, the problem solving skills are enhanced. A Programmer who has never solved these problems independently is clearly weaker.

tried 3″hard”leetcode Q’s #tests !! 100%

I tried Q4, Q10, Q23.

Observation — they are not really harder in terms of pure algo. I found some “medium” questions actually harder than Q4/Q23 in terms of pure algo.

Beside the algorithm, there are other factor to make a problem hard. For me and my peers, coding speed and syntax are a real problem. So the longer my program, the harder it becomes. Some of the “medium” questions require longer solutions than these “hard” problems.

Logistics of instrumentation is another factor. Some problems are easy to set up and easy to debug, whereas 3D, graph or recursive problems are tedious to set up and often confusing when you try to debug with print’s.

There’s another factor that can make any “medium” problem really hard

xx: weekendCIV^codingDrill^work

Amount of tech learning and zbs growth over weekend coding assignments are different from coding drill or work projects

  • intensity — highest
  • QQ halos — comparable to my language feature experiments — improves QQ
  • scale — larger than coding drill but not too large like work projects
  • BP — is a major learning focus and evaluation criteria
  • absorbency — highest
  • sustained focus — lasting over a few days, pretty rare for me

I separate pure-algo from real-coding questions

Many job seekers simply say “algorithm question” or “coding interview” as if they mean the same. I see significant differences between two types of coding test — compilable code vs pure algo.

Here’s one difference to start with — real-coding questions require us to be very familiar with syntax and very fast edit-compile-test cycles. I often struggle even when my idea was correct. I often run out of time. No such requirement in a white-board algo test.

I try to visualize a spectrum image like

<=== harder on language+implementation (blue side) … (red side) increasingly harder on pure algorithm ===>

  • * (On far left “Ultraviolet” side of the spectrum) multi-threading coding questions are light on pure computer science algorithms.
  • * (Also on the far left  side) some weekend coding assignments are very serious about design trade-off’s, reasonable assumptions, thorough automated testing … No such requirement in a pure-algo test.
  • * (On the mid-left side) real coding questions can have a code smell issue, esp. in the weekend take-home assignment. I failed many times there even though my code worked fine.
  • * (in the middle) many Hackerrank and Codility questions involve difficult algorithm and fast edit-compile-test. Very hard for me.
  • * (on the right side) pure algorithm questions are sometimes on white board, and even over phone if very short. Light on syntax; no edit-compile-test; no code smells.
  • * (on the far right side) some west coast white board interviews require candidates to ask clarifying questions, and later eyeball-test our code without a compiler. No such requirement in a real-coding interview.
  • * (On the extreme right end) very tough algorithm questions care only about O() not about language efficiency. Pick your language. The toughest algorithm questions don’t even care about O() so long as you can find any solution within 15 minutes.

I often perform better with pure algo questions than real-coding questions. My worst game is codility/hackerrank.

I find it imprecise to call all of them “algorithm questions” and disregard the key distinctions between the two types. Both types have some algorithm elements, but the real-coding questions often require additional skills such as quick completion, language efficiency, and code smells knowledge. A bug can often take us 10 minutes to locate — something rare in pure-algo questions.

Effective strategies to prepare for real-coding vs pure algo interviews are rather different. In this email I will only mention a few.
1) for speed, we need to practice and practice writing real code and solving short problems; you can try timing yourself.
2) for pure algo, we can use python; we can look at other people’s solutions; we still need to practice implementing the ideas
3) for white-board, we need to practice talking through a problem solution… need to practice asking clarifying questions and eyeball-testing
4) for weekend take-home tests, practice is not effective for me. I won’t prepare.
5) for multi-threading problem, need to practice with basic multi-threading problems.

coding drill:LASTING value4family-well-being]U.S.10Y

This blog post is poorly structured, but let’s not spend too much cleaning it up. Not worth it. Most of the content is repeated elsewhere.

See also  the benefits of coding drill in 4 benefits of coding practice #beatFront and Coding drill is anti-aging

Background: for many years until late 2017, I have focused on QQ, and neglected coding tests.

  • If you bring your pure algo skill from 4/10 to 6/10, it will remain around that level, or slightly lower. It will help you with your high-end job interviews for 5-10 years.
  • a lot of “algo skill” consist of key ideas behind the top 100 common coding questions. (I tried about 1/3 of them.) I feel it’s crucial to review the high-value problems to refresh 1 or 2 key ideas for each problem.
    • Note the various max-profit problems look similar but Key ideas are vastly different.
  • If you rely on your work projects, you will remain around 3/10 😦 Your projects won’t train you for those coding challenges in terms of algo, BestPractice, ECT…
  • Only a small part of the required syntax can be practiced but a lot more practice still needed 😦
  • You may think the STL syntax will become familiar naturally, but in reality over a year our projects used no std::map no lower_bound() no sort() no getline() so most of the basic syntax were not developed!
  • One builds the ECT skills (including syntax) with focused practice, outside the day job. No shortcut. Programmers without this “mileage” won’t have this skill. Just like driving or any athletic or artistic skills.

I’m reluctant to break down by “skill” but ..

  1. quick-n-dirty syntax used for coding test — Yes we can remember most of it for 10Y, based on my experience with perl, java, php
  2. ECT — easy to lose the speed. I feel some of the ECT improvement does remain.
  3. pure algo ideas — already discussed above

Low “churn” — most coding questions have remained unchanged for 20 years.

I also realized that my c++ ECT/BP proficiency is different from my java ECT/BP proficiency.

 

## Are those leetcoders really stronger@@

You wrote “I think many leetcoders are fresh graduates, or young people, who have more time and energy.  I know I cannot compete them …”

Q: Are those leetcoders really stronger in coding tests? Generally yes, but it depends on the type of coding question.

  • For a weekend take-home assignments …. I am not sure they would produce better quality code than us. (I’m not very good either). Code smells matter to my past interviewers.
    • They may not run as many tests as we do.
    • I tend to spend 200%+ more time on the assignment
  • For white-board ….. or remote dumb editor pair programming (west coast favorite), they may not be able to explain their thought process as well as I do.
    • My 2007 Google white-board interview used pseudo code, so the leetcoders’ advantage would be much lower.
  • For completely original questions created by a hiring manager then sent via hacker rank platform, leetcoders may not be fast enough to solve them, since leetcode problems can’t include every newly invented problems.
    • I hit two problems related to shortest-path algorithm, which can be similar to leetcode problems. I also hit very unusual problems.
  • For multi-threading coding questions, leetcode doesn’t help.
    • hit me at least 8 times — UBS, Barcap, Gelber, Bbg ..

4 technique gains { coding drill #技巧提升

An essential review can be good once a while, but over-analysis can reduce our motivation for practice:(

See also my google-sheet on codingIV types and skills required —

Note I don’t target a skill like “passing all Leetcode tests” since those tests require very refined algorithm, but most coding tests focus on just a decent algorithm with normal test cases. See my letter sent to friends about “hard problems”

benefit : quick-n-dirty
syntax+idiom
other part of ECT best practices
Can we remember after X years? 3Y #highly specific items unsure 4Y
Did we improve through past IV? y they are wake-up calls
Can we improve it on the job? actually no rarely slightly
important in short codility IV? crucial y n
important in white board pair-coding? secondary FB only, not GOOG n
important in long take-home assignment? n n y

—-#1 benefit: syntax+idioms. See ##examples@syntax learning via mock coding IV 

I also realized my data structure syntax grasp is insufficient with STL etc. In a timed coding tests I had no time searching online. I feel STL syntax is more messy.

—-benefit: ECT speed of completion.

I was able to complete many timed online tests but still rejected. Still, I did better than before.

—-benefit: best practices — designs, code smells

—-benefit: key ideas (sometimes insight) into a classic problem. A real insight is powerful and reusable. This is mostly useful when we hit a “previous problem”. See https://bintanvictor.wordpress.com/2018/06/09/study-top-100-common-coding-challenges-to-learn-key-techniques/

This is the #1 benefit to XR.

I feel I hit something similar to previous problems about 50% of the time.

[18] y I don’t like leetcode+similar sites #XR

wipe-out — I would say this letter described something like a wipe-out experience…

Hi XR,

I may need your advice here. On 23 June I tried one medium level question on LeetCode. (Before Bloomberg interviews, I tried Bloomerg CodeCon website for a few days, with similar experience, but there’s no posted solution 🙂

To my dismay, it took me 4+ hours because I hit lots of “devils in the implementation details”.

* I dare not submit my code and run LeetCode test cases because I am scare to see tons of failures, a huge discouragement.
* I am tempted to look at the top solutions, but they are likely much cleaner and better than mine, a huge discouragement.
* Until I pass all test cases, this question is not done and I would feel guilty to give up. In contrast, my own coding projects can be 50% done and I can leave it as is. I would not feel like a quitter. My own projects have no standard test cases to show I’m 50% done or 90% done. You could say LeetCode acceptance criteria is uncompromising and uncomfortable.

Since I don’t want to be a quitter, I must keep spending hours and hours on this one question. The longer I go, the more tired and I just feel increasingly frustrated that I can’t complete even one question. In my own projects, I could give up without shame or guilt.

* Even if I were to complete a few questions 100%, I would not feel proud because other coders have completed a hundred questions, a huge discouragement.

These discouragements would presumably destroy the precious joy of coding. This “joy of coding” is precious because it’s so hard to get — I need plenty of energy, plenty of quiet time with background music, positive mood to take on tough challenges …. Each hour of coding practice easily consume twice the energy of other type of learning.

Here are other drawbacks to LeetCode:

On the Leetcode code editor, I’m unable to run my own small tests until I have a complete solution. In contrast, in my own coding projects, after I have a small module written I can test it and get some immediate satisfaction and make progress on that module. On LeetCode site, I feel like digging and digging in darkness, until I see some light at end of the tunnel.

In conclusion
* skill improvement is not higher than my own coding practice

* satisfaction, positive feedback .. is much lower
* stress is higher
Therefore, I don’t look forward to doing it again. To continue my coding practice, I would stay away from these web sites.

Then something hit me — I now realize my son is not as lazy as I thought. As a Chinese father I automatically feel he is not putting the same amount of effort as other kids in his school. But looking at myself .. Am I putting in the same amount of effort as LeetCoders? If we compare to the wrong peer group, we inevitably feel lazy, inferior, inadequate, sub-standard. Such a comparison is not the best way to motivate our kids. It is erosive, hurtful, counter-productive.

In the long run, his classmates who put in more effort doing math problems now may not do better than him. They might do better in standardized exams, but what about university level (no more standardized tests) ?

[18] weekly coding drill plan

  • No need to pass all the tests on leetcode! See tried 3 “hard” leetcode Q’s #tests100%
  • focus on effort, the process of learning
    • not the result like how many questions I have “learned”. Result is unreliable to measure.
  • time slot? mostly weekends. Weekday evenings are probably tough but I did it many times
  • time quantum? Ideally 30-90 min, not 3 hours like in the past.
  • interview format to target?
    1. codility
    2. white-board
    3. take-home?
  • skills to target
    1. pure algo ideas
    2. ECT
    3. syntax
  • select the top 50 classic problems or contrived but popular questions.
  • don’t waste time on questions with many “dislikes”.
  • level? Some past problems are very hard. We could still try those “hard” problems when we feel engaged and confident to grow through them. If too hard, just read the solutions straightaway.
  • question pool? retry — past questions in blog. 温故而知新
  • question pool? Leetcode — if the problem is engaging and classic, even if easy
  • language? py or c++ are easier (than java) to test on my laptops
  • target? 60 minutes a week (better than 0 minutes as in the past). This includes coding, blogging, email discussions
  • how many weeks? 3, starting from late Apr 2019
  • involve friends to increase the engagement — CSY, Ashish, XR, YH, Deepak, Alok, YH,

[19]Cod`drill in our 50’s #CSY

  • I agree that Competing with younger guys on (speed) coding test is like math competition, sports competition, … where experience doesn’t matter. But in our chosen profession, this is reality to be accepted.
  • I agree on Wall St etc there exist decent jobs with modest, reasonable coding tests. I hope coding test do not grow in popularity but I think they will.
  • I agree that you and me are not less intelligent than those strong candidates at coding tests. Your steadfast conviction is inspiring n uplifting. I tend to have self doubts.

I agree that most peers at my age have stopped coding practice.  Some individuals still do. (Deepak is just one example.) I see them as role models just like male yoga practitioners, among a sea of women. Most of my peers see coding drill as a chore, a hard job, a pain in the ass, but I’m different.

For the next 5 to 10 years I hope to find joy in coding drill. Coding drill is like jigsaw puzzle n board games … mental gymnastics to keep our brain young.

There is no shame in revisiting college level subjects.  At age 44 I still studied calculus and passed math exams with flying colors. I am proud of myself, not ashamed of myself. I can probably help my son n my daughters with math till their college. Not many dads can do that.

I will say this again — some technical interviews ask probabilities n SQL. These are college level topics. We just accept and prepare for these interview questions.

[19] camp-out4cod`drill #+localSys

My most effective coding drill is less like hackathon, more like camp-out. My localSys learning is similar.

When I’m in the mood, I know it will last a few hours up to a day, I need to shut out all distractions and capture the momentum until it subsides.

  • weekend assignment: redmart
  • weekend assignment: Jump/iRage orderbook
  • weekend assignment: Houston (quantlab?)
  • weekend assignment: GS tickDB
  • weekend assignment: DRW
  • weekend assignment: nsdq
  • Chartered unix hacking

coding drill≈yoga + weight loss

I had a brief discussion with my friend Ashish.. Coding test improvement is similar to weight or flexibility improvement. I also tell my son about diet control. You probably can think of many other examples.

  • we don’t notice any improvement for a long time. Still, I believe the practice makes me better than before.
    • In the absence of visible progress, Optimism and Faith is important. A pessimist tends to give up before seeing ROTI
  • when we stop the exercise, we are likely to lose part of the effort and continue the downward spiral, esp. with flexibility. See coding drill: LASTING value4family wellbeing for10Y 
  • as we grow older, we feel we tend to lose the competition, even though there’s not enough evidence.
  • it can feel boring and repetitive
  • pair exercise is easier
    • Otherwise, promise a friend

prefer std::deque when you need stack/queue

  • std::stack is unnecessarily troublesome for dumping and troubleshooting … see https://github.com/tiger40490/repo1/blob/cpp1/cpp/2d/maxRectangle.cpp
  • std::queue has a similar restriction.

Philosophically, std::stack and std::queue are container adapters designed to deny random access, often for safety. They are often based on an underlying “crippled deque”. As soon as you need to dump the container content, you want a full-fledged deque.

nsdq=lightweight west coast CIV

  • like west-coast, No coding questions in threading like bbg
  • like west-coast, no memory mgmt questions
  • like west-coast, no question on containers as implemented in any language
  • arch design question — more in-depth than Indeed
  • algo + whiteboard
  • unlike west-coast, there were a bit of knowledge questions, but nothing in-depth like on Wall St.
  • Unlike west-coast, there was a weekend assignment

Now I feel some west coast interviews might be similar to nsdq interview.

IDE IV=easier4some !!4me

I guess many (majority ?) candidates consider IDE coding IV easier than white-board. I think they rely on IDE as a coding aid. Many programmers are not used to “demo” coding using white board … stressful, unnatural?

The “coding aid” feature helps me too, but it helps my competitors more !

If on white-board (or paper), my relative rating is A-, then on IDE i would score B

  • my relative weakness on IDE — ECT speed
  • my relative strength on white-board — clarity of thinking/explanation

[19] problems+!published solutions: better4me

Nowadays I feel problems without published solutions, without extensive test cases are better for me, since I don’t worry about … wipe-out, like bloodshed.

-> better avoid Leetcode. Careercup and bbg codecon are fine. Hackerrank?

I used to worry about not knowing correct solutions -> wasting my time. Now I know from extensive experience that coming up with my homemade solutions is good enough and rewarding, even if incorrect/incomplete.

I don’t always need or want to know the correct solution, not every time.

Further, I often wish there’s no known solution, since they always wipe out my satisfaction and self-esteem.

 

[19] new problems!=the best drill

I used to focus on how many new problems solved each week, but that’s very challenging and not necessarily most effective.

Reviewing existing code is easier i.e. requires lower absorbency, but can still take hours.  Worth the time!

No one can remember so well without refresh. Therefore, am growing stronger than before and stronger than my peers who don’t invest this time to refresh.

There’s a real risk to overspend time on new problems. We don’t always fully digest the solved problems.

##eg@syntax/idiom learning via coding drill

Syntax (+ some best practice in syntax) is essential in 70% of my real-coding interviews.

There are many memorable exceptions like char-array/int-array, tree, linked list, regex ….. , which require ECT, BP and pure algo, but trivial syntax. Some of them are relatively “hard” on pure algo and my relative strength shines through among Wall St candidates.

Below are some examples of syntax learning via coding drill

  • pointer manipulation in linked graph
  • matrix manipulation
  • pitfall — iterator invalidation
  • pitfall — output iterator hitting end()
  • c++ search within string
  • eg: multi-threading problems —- I had at least 8 experiences in java and c++ (UBS-Yang, Barcap, Gelber, SCB, HSBC, Wells, Bbg thrPool, Pimco + some minor ones in BGC)
  • eg: template, move semantic and placement-new … asked in white-board coding, nothing to do with ECT!
  • eg: lower_bound() means touchUpperBound is all about syntax not algorithm. Revealed via coding interview!
  • See also categories pyECT_nlg, t_c++syntaxTip, t_c++tecniq, T3_stdStr_tagT2_cStr/arr/vector
  • see tags t_c++ECT_nlg
  • c++ syntax requires 3-6 times more learning than python

## coding IV P/F

See also ##failed c++cod`IV: home^IDE^whiteboard:4 beat-fronts

  • paper — is a shorthand for paper, dumb editor, white-board etc
  • webex vs onsite are somewhat similar, usually pair-programming. Take-Home setting is vastly different.
  • pts (points) — awarded to myself, indicating the performance, value, difficulty ..
  • p/f are only based on interviewer’s subjective judgement
  • pp means passed convincingly, with flying colors
  • [1] I focused on working solution! See %% priorities in a take-home coding IV
  • [2] highlight: where practice can make a difference in a make-or-break test
lang location IDE? firm/person pts 1-5 Notes category type@practice needed [2]
c weekend IDE HRT 5 2019 parser dStruct heavy
py onsite paper 😦 Indeed 3 2019 algo algo practice
c weekend IDE they gave up redMart 5 2019
c/py home hackerrank no news Altonomy 4 2019 4 problems #Deepak
c onsite paper p Quoine 1 2019 balanced brackets #5-min job algo
py webex IDE p Indeed 5 2019 see my blogposts algo speed-coding; memorize syntax
c home hackerrank p TradeWeb 1 2019 CSY: basic STL map manipulation algo STL + basic algo practice needed definitely
c phone phone p SCB-FM 2 2018 pure algo 1 easy + 2 hard ones. I over-performed algo array/slist problems
c weekend IDE 😦 quantlab 4 2018 Houston HFT weekend coding drill ROTI dStruct
c/thr home IDE p Pimco quant 3 2018 2H parallel programming thr study pthreads
c home hackerrank p FlexTrade 3 2018 slist cleanup#github std algo array+list problems
java home hackerrank 😦 Pimco #190m 2 2018 Q9: path through matrix. Ineffi [1] std algo too hard, but some 2D practice can help
java home hackerrank 😦 Pimco #190m 2018 Q8: buy 1 sell any algo array problems
c onsite paper p LiquidNet 2 2018 30 minutes algo array problems
c home codility 😦 Mako 4 2018 monkey. Ineffi [1] algo too hard
c home codility 😦 Mako 3 2018 quasiconstant [1] algo array practice
c onsite paper p SIG 2 2018 15-30min … RAII smart ptr std lang
c onsite paper p SIG 3 2018 push_back std lang
py onsite IDE p SIG 3 2018 movie query dStruct algo practice
c weekend hackerrank p Promethean 5 2018 2 tough graph problems algo too hard but some QQ can help
c/py home hackerrank pp Kraken 3 2018 3 (small?) problems algo algo
any onsite paper 😦 Nsdq 2018 oracle day-trading algo array problems
any onsite paper 😦 Nsdq 2018 check array 0-N in-situ algo array@int problems
java home IDE pp Nsda 4 2018 drone: medium-level implementation SDI hard to prepare
c onsite paper pp CVA 3 2018 O(N) in-situ filtering algo array problems
c onsite paper 😦 FB 2018 2 short problems std algo algo
c onsite 😦 Trex 2018 exchange messaging SDI no practice can help
py onsite IDE pp Trex 1 2018 3 short tricky problems. only 1 implemented algo algo practice can help
c onsite paper pp Quantum 1 2018 virt func not declared in base trivial lang
c/thr webex paper pp bbg 4 2018 single-thr pool QQ lang
c webex paper pp bbg 3 2018 shared ptr ctor/dtor QQ lang
py onsite paper pp bbg 5 2018 continuousSentence algo backtracking, string problems
c/thr onsite paper ? Wells 2 2017 concurrent queue std
c onsite paper p Wells 1 2017 remove_spaces. Ineffi trivial string problems
c onsite paper p bbg 2 teams 2 2017 array reshuffle lang
c onsite IDE p bbg 2 teams 1 2017 isBST() std tree problems
c onsite paper P! bbg 2 teams 1 2017 string string problems
c onsite paper 😦 bbg 2 teams 2017 filters on screen dStruct heavy dStruct
C home hackerrank 😦 Thesys 2017 3 problems out of 5 algo algo
C home IDE pp Thesys 5 2017 first N prime Fibonacci hard to prepare
c webex IDE pp bbg 2 2017 top N active stocks dStruct heavy dStruct
c onsite paper pp BAML 1 2017 various lang
c weekend IDE 😦 GS 3 2017 TickEngine dStruct heavy dStruct problems can help
C webex IDE pp bbg 2 2017 free slots dStruct heavy algo
C webex paper p bbg 1st round 2 2017 tree serialization std algo tree algo
Java onsite paper pp BGC 2 2017 multiple short programs lang
Java weekend IDE pp BGC 3 2017 connected or not hard to prepare
Java/thr weekend IDE p HSBC 4 2017 3 big questions barely passed hard to prepare
Java/thr home IDE pp pimco 4 2017 iterator again lang
Java onsite paper pp pimco-Zoltan 2 2017 a few short problems lang?
c webex IDE 😦 Citadel 2017 array shrinking array problems
py webex paper ? Broadway 2017 hashtable. Code (on github) works std algo implement std containers
cpp weekend IDE ? iRage 3 2015 order book again. No response dStruct heavy hard to prepare
py home codility p baml 2016 Ashish: applying to Qz algo
Java home codility 😦 baml 2015 Qz FX option team. too lazy algo
c home codility 😦 Jump 3rd 2015 algo
c weekend IDE pp jump 1st 3 2012 order book dStruct heavy hard to prepare
c weekend IDE 😦 DRW 3 2015 Tetris. code quality hard to prepare
c webex paper 😦 bbg -London 2015 unable to understand Q1 of 4 std algo algo
c# webex paper pp eikon 2 2013 short, easy questions QQ lang won’t practice
java home IDE 😦 MS 4 2011 FIX. Big take-home test hard to prepare
swing webex IDE pp Barx 2 2012 swing QQ lang won’t practice
C home IDE 😦 Mac 2012 2 short problems lang
java home IDE 😦 MS-comm 2012 too lazy hard to prepare
c onsite paper pp Cantor 1 2011 auto-ptr QQ lang won’t practice
java onsite paper 😦 Barc SOR 2011 recursion recursion
java onsite IDE pp RBC 1 2011 30-45 min, bond tick conversion lang
java onsite IDE 😦 UBS 2011 Suntec lang
java/thr onsite whiteboard 😦 UBS 2011 Jack Yang lockfree stack QQ
java/thr onsite whiteboard 😦 Barc 2011 wait/notify + lockfree QQ
java/thr onsite IDE 😦 Lab49 2010 executor lang
java/thr home IDE pp Gelber 3 2011 multithreaded hard to prepare
C home IDE 😦 Amazon 2011 didn’t take it seriously algo
C onsite whiteboard 😦 FB 2012 regex QQ std algo too hard, but some QQ can make a diff
any onsite whiteboard 😦 Goog 2007 algo

online solution2algoQ:I always try%%self1st #maxRectangle

https://bintanvictor.wordpress.com/2018/04/07/check-array-of-0-to-n-nasdaq/ is the Nasdaq question. It includes a link to my solution in github. I came up with my own solution. Then I tried your solution found online.

https://bintanvictor.wordpress.com/2018/04/10/check-array-can-be-preorder-bst-walk/ is another interview question. I tried my own and came up with a “better” solution.

If I don’t try my own solution, I would not learn a lot, and I would not have fun implementing my own idea (even if not optimal).

I also find it hard to absorb then remember clever solutions I found online, such as the maxRectangle.

Solving problems myself also grows my confidence when facing unfamiliar problems. I do read online solutions when I have no clue. confidence-build`: another reason y I don’t look at Leetcode answer

By the way, one advantage of my solution is — it can identify the missing numbers, all within O(N) time and O(1) space.

bitwise coding questions: uncommon

Don’t over-invest.

Q: How prevalent are these questions in coding interviews?

  • I feel these questions are usually contrived, and therefore low-quality and unpopular among hiring firms.
  • There’s no classic comp-science constructs at bitwise level, and bitwise doesn’t play well with those contructs
  • the bitwise hacks must be language-neutral wrt python and javascript, so quality questions are scarce.
  • phone round? impossible

white-board real estate usage

  1. We often insert lines later at …
    1. Leave 2 lines of space before  and after loop header.
    2. leave 2 lines of space after function header
    3. leave space before and after if-header
  2. Example data — should be drawn at bottom right, but make sure you can see them as you code
  3. global var list — I tend to keep them at bottom left on one line
  4. I like many utility functions
    1. short utility function — you can start it near the bottom, or above existing code, with limited “runway”
    2. lengthy yet easy utility — If you worry a utility function may be lengthy, you can start writing on paper and stick it near the board
  5. top right — is for a 2nd major function, perhaps extracted from the first major function
  6. top level driver function — is never complicated but can grow.  I can write it below an existing function
  7. center of the board — leave empty for eyeball test, other examples, graph etc

AuxDS ] each node2simplify algo #shadow matrix

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

eg: BFT showing level

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

 

sentinel node trick: array/slist

  • eg: STL uses sentinel nodes. I believe container.end() returns that.
  • eg: c-string uses \0 as sentinel value.
  • eg: binary search needle can be too high and we have to test if the return value is a real element or the end-of-container, so it’s extremely useful to add another sentinel to guarantee a successful search

When solving timed coding questions on “clean” arrays, it can be useful to append a sentinel node. It can simplify some algorithms which take action after each segment.

P 90 [[Pearls]] introduced a loop coding idiom. Idiom is applicable whenever we loop over a container and have an early-exit “break”. Such a loop has exactly two [1] conditional tests per iteration, therefore can run faster if we combine the two into one conditional test. This is a small halo idiom for latency. But beyond latency, there are more interesting benefits such as cognitive complexity reduction.

For example, consider the business logic after reaching “normal” end of the container without hitting the early exit. Rarely can we “forget” this business logic and simply exit the function and rely on the implicit return. Instead, this normal-completion scenario requires careful handling and a cognitive burden. To remind myself, I often place a comment after end of the loop. (Python provides an Else clause for a for-loop.)

In some cases, the business logic after end of the loop is 2 pages away from the early-exit business logic, but they really should be in one module. I hate this situation so much that I always have set a flag and use a “break” so that the two routines are both written after end of the loop.

In all these scenarios, it’s often simpler to append an artificial sentinel element at end of the container!  The sentinel is guaranteed to hit the early-exit, so the loop would never exhaust all elements and complete normally. Therefore we can combine the two into one conditional test:)

I usually replace “break” with “exit”, further reducing the control-flow complexity. Such micro simplifications can pay huge dividends in high-pressure timed tests.

Right before the exit/break we may still need to handle normal-completion scenario by checking if we are at the sentinel. Interesting scenario. Now we can combine the logic of normal-completion vs early exit. In many cases, they are (nearly) identical, so we can express the logic in very structured code.

Whether they are identical or not, handling the two scenarios (early vs normal completion) in a centralized module is usually simpler and more structured, reducing the cognitive complexity.

[1] what if three tests (two breaks)? The mental burden is even worse. The sentinel could reduce it

Gayle: no rush2write code: point allocation

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

Gayle: use big,ugly sample2explore; tiny sample4test

–In the initial exploration (only 50% clear direction), the big ugly sample would clarify many assumptions.

Any mis-assumption corrected is a potential life-saver since the mis-assumption could lead us down the wrong track.

Such a sample will help us see the pattern in data and get to the gist of the problem.

–However, during the eyeball testing on white board, a large sample would take too much time. A tiny sample can flush out the bugs more quickly

## BRING reminder sheet : cod`IV

  1. edge case — my loop may get skipped completely
  2. edge case — empty output
  3. drive to improve af it works
  • bring rectangular post-it + breakable tape

—-todo:

bbg cod`interviewer: Problem-Solving skill #GTD

I think this skill is like IQ…

I feel this is broadly similar to west coast interviews, perhaps with subtle differences in how Mistakes are assessed.

One Bbg interviewer shared with me what he means by “problem solving skill” — given a well-defined programming problem

  • not superb performance
  • not syntax perfection
  • solution should be “reliable”
  • problem is often realistic
  • I said many candidates go on the wrong track and (usually) get stuck. He agreed.
  • I said many solutions are broken because candidate misses some key factor. He agreed.
    • perhaps a factor about requirement
  • I now think some candidates have no experience no basic understanding on a given programming topic (say, DP, or regex parser, or condVar) so they will never get off the wrong tracks.

c++matrix using deque@deque #python easier

My own experiment https://github.com/tiger40490/repo1/blob/cpp1/cpp1/miscIVQ/spiral_FB.cpp shows

  • had better default-populate with zeros. Afterwards, you can easily overwrite individual cells without bound check.
  • it’s easy to insert a new row anywhere. Vector would be inefficient.
  • To insert a new column, we need a simple loop

For python, # zero-initialize a 5-row, 8-column matrix:
width, height = 8, 5
Matrix = [[0 for x in range(width)] for y in range(height)]

In any programming language, the underlying data structure is a uniform pile-of-horizontal-arrays, therefore it’s crucial (and tricky) to understand indexing. It’s very similar to matrix indexing — Mat[0,1] refers to first row, 2nd element.

Warning: 2d array is hard to pass in c++, based on personal experience 😦 You often need to specify the size in the receiving function declaration. Even if this is feasible, it’s unwanted legwork.

[1] Warning — The concept of “column” is mathematical (matrix) and non-existent in our implementation, therefore misleading! I will avoid any mention of it in my source code. No object no data structure for the “column”!

[2] Warning — Another confusion due to mathematics training. Better avoid Cartesian coordinates. Point(4,1) is on 2nd row, 5th item, therefore arr[2][5] — so you need to swap the subscripts.

1st subscript 2nd subscript
max subscript  44  77
height #rowCnt 45 #not an index value  <==
width #rowSz [1]  ==> 78 #not an index value
example value 1 picks 2nd row 4 picks 5th item in the row
variable name rowId, whichRow subId [1]
Cartesian coordinate[2] y=1 (Left index) x=4

FB cod`IV tips: #official

bucket sort; merge sort; graph

watch more videos

go through the Prep emails.

  • Practice.. Test your code on the board not code in your head.
  • U can confirm with interviewer if u want to start coding earlier. I tend to run out of time solving the problem. Kelly said just practice more to speed up.
  • You can request to skip small talk n start technical part earlier.
  • Messy code is ok for some interviewers, as long as they can follow your thoughts. Poor recall of language details probably OK, but not fundamental mistakes.
  • Always .. Interviewer will under-specify the problem, waiting for you to ask clarifying questions. The more corner cases you identify the better.
  • Always .. for all coding interviews, the problem is solvable within 30-40 minutes.
  • Always .. Done is more important than perfect. You can improve on a imperfect solution in terms of big-O.
  • Always .. walk through your solution with some unusual cases. Some interviewers don’t care about trivial corner cases, but some unusual inputs are valid and important, like an extremely lopsided tree.
  • Better be “deep” with one language so you can demonstrate your depth (esp. about big-O), but you could also choose different languages for different problems.
  • FB is very specific about big-O
  • some interviewers are very specific about details in the output. Empty input? What are the exact characters in the output? A client program will need the output to be exactly right.
  • FB is very specific about details in the input. Ask clarifying questions.
  • Never invent facts that don’t exist.
  • You should be constantly talking while solving the problem. Talk through more than you usually do.

y I use lots of if..{continue;}

Inside a loop, many people prefer if/elif/else. To them, it looks neat and structured.

However, I prefer the messier if…continue; if…continue; if..continue. Justification?

I don’t have to look past pageful of if/elif/elif/…/else to see what else happens to my current item. I can ignore the rest of the loop body.

Beside the current item, I also can safely let go (rather than keeping track) of all the loop-local variable values longer. All of them will be wiped out and reset to new values.

## G5 algoIV constructs x-lang #dataStruct++

  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

A/Bob/C: cod`IV #hm

Here are other variables names frequent needed in coding puzzles:

  • Once you declared a long, meaningful var name, you could use abbr of it afterwards.
  • if you have an array of composite objects like “frame” or “trade”, each represented by a inner array, then be careful with frame[1]. Better call it aFrame[1] or frames[0].
  • what about “sorted” which is a python function name:( …. I would use ascd by default.
  • B4 means “before”; Af means “after”
  • hm means hashtable; tm means treeMap or std::map
  • targetRepetition or tgtRep
  • “val” — payload data filed in a Node class. This name is short, easy to type. Harder to global-replace but LG in a short program
  • candd” — candidate
  • “End” for the last element in a container
  • li means list … vec means vector … arr means array
  • cnt means count or counter
  • — for a matrix
  • M, m or mat for the matrix
  • r as the 1st index; c as the 2nd index. Avoid x/y
  • height/rows as number of rows; width/cols as number of columns
  • I will refer to each element as a “cell”

—It’s more useful to have personal names than mere “Person A”. Shorter names are easier to write. Gender doesn’t matter.

  1. Alan, Alice, Aaron,
  2. Bob, Ben (Big Ben), Bill,
  3. Cody,Chris, Charlie
  4. Dan, David
  5. Ed, Emily, Elizabeth (queen)
  6. Fred
  7. Greg, Gail
  8. Henry, Harry,
  9. Ilya, Ivy, Ian
  10. Jen, Jim, Joe, Jack, John, Jason,
  11. Ken, Kate, Kevin,
  12. Lucy, Lee, Lilly, Larry,
  13. Mike, Mary, Matt,
  14. Nick, Nancy,
  15. Oliver, Oscar, …
  16. Pam, Peter, Paul, Peggy
  17. Quincy
  18. Raj, Rob, Ray,
  19. Sam, Sue,
  20. Tom, Ted, Tim,
  21. Uday ….
  22. Vic, Venkat
  23. Wendy, Will
  24. Xavier, Xander/Zander …
  25. Yixin, Yang ….
  26. Zofia, Zack,

Codility: ignore overflow+bigO

The machine won’t check your bigO!

Focus on getting it to work. If you have time, address the overflow. If you get bogged down by the overflow concerns, you lose focus and lose speed.

–Here are my practical strategy for codility

  1. Don’t aim for high marks, since these tests are very hard-to-please and not very popular.
  2. Get friends to help crack it.
  3. Remember that ROTI is lower than other coding tests like Bloomberg style.  ECT and thinking speed is way too demanding.

##elegant/legit simplifications ] cod`IV

  • eg: reverse link list in K-groups — (CS algo challenge) assume there’s no stub, solve the real problem, then deal with the stub
  • eg: consumer thread dequeue() method. When empty, it “should” be waiting for a notification, according to Jun of Wells Fargo, but a simpler design returns a special value to indicate empty. The thread can then do other things or return to the thread pool or just die. I think the wait model is not ideal. It can waste a thread resource. We could end up with lots of waiting threads.
  • Eg: https://bintanvictor.wordpress.com/2017/09/10/lru-cache-concise-c-implementation/ requirement is daunting, so it’s important and completely legitimate to simplify lookup() so it doesn’t insert any data. API is simpler, not incomplete
  • Eg: find every combination adding up to a given target #Ashish permutation within each combination is a separate issue and not the main issue
  • recursive solution is often a quicker route to working code. Once we cross that milestone, we could optimize away the recursion.
  • eg: extract isPrime() as a unimplemented function and simply assume it is easy to implement when I get around to do it.
  • Eg: show free slots between meetings #bbg I solved a similar and more familiar problem.
  • eg: violation check for Sudoku is a tedious but simple utility function. We could assume it’s available
  • eg: violation check for n-queens is likewise slightly harder

 

## G20 operations(4cod`IV)on containers+str

“Operation” means logical operations any programmer (java, Perl, javascript, whatever) frequently performs on a common data structure. STL offers about 30 to 60 everyday operations. A beginner can benefit from a good short list.

List below leans towards sequential containers (shows up in 80% coding questions), but also includes essential operations on associative containers.

  1. ) print — using copy and ostream_iterator. See post. See stl-tut
  2. ) find, find_all
  3. slicing i.e. subsequence
  4. [iv] sort — using custom “myLess” as a type param. See post on functor-type. See effSTL
  5. [iv] construct a sorted container using customer “myLess” as type param. See blog
  6. filter
  7. [iv] nested container
  8. truncate at a point
  9. append, in bulk
  10. pop front
  11. binary search in pre-sorted
  12. [iv] deep copy
  13. mass-populate with one default value
  14. remove/erase – see effSTLplug back_inserter into copy, remove_copy, replace_copy …
  15. [iv] plug bind2nd into replace_if/replace_copy_if, count_if, remove_if/remove_copy_if …. See blog
  16. initialize with hardcoded literals — relatively easy
  17. conversion like between string and vector of char. See blog. See [[ stl tut ]]
  18. —-2nd tier
  19. insert mid-stream, in bulk
  20. [iv] = possibly picked by interviewers

##9dataStruct(+..)for c++speed cod`

  1. linked node manipulation in a graph context
  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. string in std::string or c-str
  4. iterator manipulation like erase, lower_bound, find,
  5. sorting, operator<(), upper_bound, binary search … on containers
  6. sorted data structure like std::map
  7. [w] stringstream — ECT to improve

Very few Wall St 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]

 

##failed cod`IV

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

 

QQ BP ECT speed syntax algo where
 ? 😦 NA NA ? home c GS tick-engine
NA 😦 NA NA ? home c Tetris
 ? 😦 NA NA ? home c Macq
😦 😦 NA NA NA home j MS-commodity
? ? NA NA 😦 home j Amazon
😦 ? NA NA NA home j MS itr
😦 ? NA NA NA home j MS FIX
? NA good good 😦 codility c/j Mako
NA NA 😦 ? ? codility j FXoption
NA NA 😦 ? ? codility c Jump #3
NA NA 😦 slow good IDE c Bbg 2017
 NA ? 😦 slow good webex c Citadel array-shrink
none ? 😦 good simple IDE j UBS Suntec
😦 NA NA NA ? paper c Nsdq array 0-N
NA NA NA NA 😦 paper c Nsdq day-trading
😦 NA NA NA 😦 paper c FB regex
😦 NA NA NA 😦 paper c Goog
😦 NA NA NA ? paper j Barc SmartOrderRouter
😦 ? ? NA NA NA paper j UBS YACC
😦 NA NA NA NA paper c Bbg London
😦 ? NA NA NA paper c 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. speed coding tests usually beat me in terms of ECT speed
  3. white-board tests usually beat me in algoQQ

c++cod`IV: no threading/boost/template/socket..

See C++(n java) high-end IV tend2beat us]4ways

This post is about the c++ topics. The BP/ECT/algo fronts primarily use basic constructs in ##10 basic programm`constructs for c++ cod`IV

QQ BP ECT algo#pure
heavy no never never thread
heavy yes seldom never smart ptr
seldom never never never other boost
yes never never never rvr+move
seldom optional never other c++11
heavy seldom never never memory tricks
yes never never never templates meta..
heavy yes never never c^c++
heavy never never never sockets
never never never once object graph serialization
heavy never never never inline
heavy never never never cpu cache
yes never never never exception safety
yes never never never pimpl

once algo cracked,syntax/idiom=雕虫小技@@ NO

Background — Let’s focus on short coding tests , compiler-based.

Q: If it takes 2Y to improve from 3 to 6, then how many percent of the effort is syntax?
A: less than 50%, but can be as short as a few days. ECT is harder.

In java or python, my coding test track record is better. The syntax know-how required is relatively small, because the questions use only array, hash table, linked nodes, StringBuilder/stringstream… Look at EPI300.

C++ feels similar. Once the algo (and data structures) is cracked, the syntax know-how required consist of about 500 common operations. (I have some of it listed in my blog…)

However, once I have a decent idea, it often takes me 20 – 60 minutes to pass the basic tests, but i am given only 30 minutes! Why am I so slow? Syntax is sometimes non-trivial and also ECT, even if without debugging the corner cases.

Some non-trivial syntax + idioms needed in speed coding — ##eg@syntax learning via coding drill

leetcode 40% accepted … means nothing

Hi XR,

1) Some leetcoders (me too) would spent 5 seconds reading a discussion thread, get a basic idea and implement and submit her own solution and get accepted.

Therefore, the 40% acceptance rate doesn’t mean the problem was solved independently by 40% of the readers.

2) Also, some questions are not interesting so leetcoders don’t even try. Therefore, some relatively easy questions may have low acceptance rates.

I told myself to ignore the acceptance rate, but it’s too visible on the web page, so instead of complaining, I do look at the acceptance number. Mentally, I follow a simple heuristic rule — if the problem has high acceptance percentage then it is probably easy.

This heuristic rule (like all heuristics) can still be incorrect in the 25-horse (or linkedlist-loop-detection) problem where a very clever solution has become well-known.

don’t feel so bad about recursive solutions #CSY

If I only have a recursive solution and interviewer points out it could overflow the stack, then here’s my answer

"Indeed I wish there’s an iterative solution. It would be more efficient. However, if there are multiple threads available, then iterative solution might be less adaptable to use multiple threads.

As to stack overflow, I understand the run time stack space is much smaller than the heap space, so if I am given a large data set and I hit a million nested recursive calls, then I will follow standard procedure to convert my recursive solution to an iterative solution, and maintain my own stack in heap. This will relieve the pressure on stack space"

This answer applies to all your recursive solutions.

10front-stage(+backstage)data structures@cod`IV

Based on my experience of algorithm interviewing at investment banks, high or low frequency hedge funds, 3rd-party financial firms like data providers, liquidity venues, a few deep-pocketed startups and a few WestCoast tech giants.. here’s the breakdown in terms of the data structure used in the original problem description.

  • 5%of them are presented in nothing but a single integer or two integers or all integers under 10000. Calculation required.
  • 5% of them are presented in huge stacks or queues
  • — arrays in 1D or 2D
  • 10% of them are presented in huge integer arrays, that require comparison, summation, subtraction or other simple calculations
  • 15%+ of them are presented in a huge sequence of value-objects, not pre-sorted
    • This is the default way to receive input data
  • 10% of them are presented in huge 2D arrays including matrices, mazes and primitive images
    • my #1 weakness
  • — strings
  • 15% of them are presented in nothing but a single char-array or two strings
  • 10% of them are presented in huge collection of strings like words
  • — linked node data structures:
  • 10% of them are presented in long linked lists
  • 10% of them are presented in huge unsorted trees
  • 5% of them are presented in huge binary search trees
  • 4% of them are presented in other huge directed graphs but not binary trees or linked lists
  • 1% of them are presented as huge collection of points on an x/y coordinate plane. Always some math required, therefore rare.
  • =====
  • 100% in total

Any of these problems could require a solution using DP/Greedy, swapping, and auxiliary data structures like binary trees, hash tables, linked lists, stacks, queues or priority queues..

  1. 70% need auxiliary arrays or hash table
  2. 50% can be solved with recursion excluding DFT
  3. 25% needs a breadth/depth-first tree traversal
  4. 25% can use DP or greedy algo, usually in one iteration — tough
  5. 20% can use an auxiliary BST
  6. 10% can use an auxiliary tree but not a BST — tough and non-intuitive. Eg: many matrix problems
  7. 10% can use an auxiliary linked list
  8. 10% require recursion in a loop — tough
  9. 10% can use an auxiliary stack or queue excluding BFT
  10. 10% can use an auxiliary sorted vector
  11. 5% can use an auxiliary matrix — tough and non-intuitive. Eg: EditDistance

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, we 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. copy the container — py/java require explicit ctor
  9. join 33 vectors
  10. slice — harder for c++
  11. max
  12. truncate
  13. reverse-copy and reverse-in-place
  14. append, prepend, insert
  15. binary search, lower_bound
  16. dump, iterate, size
  17. — #2 string:
  18. convert between string and vector<char>
  19. initialize with content
  20. prepend, append, trim
  21. insert_by_pos — not easy
  22. replace_substr
  23. read-write char by index
  24. reverse-copy
  25. successive find of target string from left (or from right)
  26. comp, sort among strings
  27. split at custom delimiter
  28. join 3 strings
  29. search
  30. substr
  31. dump, iterate each char, size
  32. — #3 lookup (usually dict or std::map)
  33. populate with hard-coded data
  34. strictly insert
  35. strictly update
  36. lookup, possibly with failure
  37. dump, iterate, size
  38. — tree map: lower_bound
  39. — Queue: deque, enque, front, back,
  40. — Stack: push, pop, top
  41. — linked list? no special tasks
  42. — misc essential iterator tasks
  43. prev(), next(),
  44. distance()

 

9tips: hacker rank test #cout-macro

similar to codiliy…

  • I may need a macro for cout, so I can disable all cout quickly before uploading my source.
    • #define ss if(1>2)cout //1>0
  • I keep my own container data dumper function for instrumentation.
  • you can submit multiple times. So as soon as you can pass some tests, please submit.
  • 🙂 You can look at multiple questions at the same time, so feel free to skip tough or time-consuming questions.
  • You absolutely need your own local compiler and ECT environment.
    • I put a small dos window (for g++ and a.exe) over a notepad++ editor. I use F2 to save

The online one is too slow and provides a single screen. You can copy paste code from local IDE, but you can’t copy paste test data. You could try downloading test data, but you need to be really efficient there. Setting up test can take 5 minutes out of average 20 minutes per question.

  • There could be hidden test cases. Don’t worry too much about them. It’s a real achievement if you can pass all the visible test cases.
  • Ignore integer overflow. If there’s a hidden test for it, you will see the failure
  • Don’t ever worry about minor inefficiency. You won’t have the time. Just get it to work first.
  • pass by clone by default. Easier to debug
  • avoid long variable names. Use std abbreviations like li, vec, ma (for map)
  • I maintain many (unnecessary) global variables of generic names like i1, s2
  • 😦 lost connectivity? timer keeps ticking

 

cod`IV – favored by the smartest companies

XR,

I see a few categories of IV questions:

1a) fundamentals — Some Wall St (also in Asia) tough interviews like deep, low-level (not obscure) topics like threading, memory, vtbl, RB-tree ..

1b) lang — Some (IMO mediocre) interviewers (like programming language lawyers) focus on language details unrelated to 1a)
2) Some (IMO mediocre) interviewers like architecture or high level design questions (excluding algo designs) like OO rules and patterns but I feel these are not so tough.

3) algo — Some tough interviews focus on algo problem solving in pseudo-code. See http://bigblog.tanbin.com/2007/09/google-interviews-apply-comp-science.html. I got these at Google and Facebook. Some quants get these too.

4) compiler coding question — is another tough interview type, be it take-home, onsite or webex.
With some exceptions (like easy coding questions), each of these skills is somewhat “ivory tower” i.e. removed from everyday reality, often unneeded in commercial projects. However these skills (including coding) are heavily tested by the smartest employers, the most respected companies including Google, Facebook, Microsoft… You and I may feel like the little boy in “emperor’s new dress”, but these smart guys can’t all be wrong.
I will again predict that coding questions would grow more popular as the logistic cost is driven down progressively.
Candidate screening is tough, time consuming and, to some extent, hit-and-miss. With all of these screening strategies, the new hire still can fail on TECHNICAL ground. Perhaps she/he lacks some practical skills — Code reading; debugging using logs; automation scripts; tool knowledge (like version control, text search/replace tools, build tools, and many linux commands)
Needless to say, new hire more often fail on non-technical ground like communication and attitude — another topic altogether.

In terms of real difficulty, toughest comp science problems revolve around algorithm and data structures, often without optimal solutions. Algo interview questions are the mainstay at big tech firms, but not on Wall St. Some say “Practice 6 months”. Second toughest would be coding questions —
* Often there’s too little time given
* Sometimes interviewer didn’t like our style but onsite coding tends to focus on substance rather than style.

Tan bin

P.S. I had webex style coding interviews with 1) ICE Feb 2011, 2) Barclays (swing), 3) Thomson Reuters, 4) Bloomberg

P.S. I tend to have more success with algo interviews and onsite coding than take-home coding. See blog posts.. (
http://tigertanbin2.blogspot.com/2015/05/sticky-weakness-revealed-by-interviews-c.html
http://tigertanbinpripri.blogspot.com/2015/03/high-end-developer-interviews-tend-to.html
)

quicksort learning notes #no src

Quick sort is not the most efficient in many situations. It’s not the implementation of sort() in many popular languages. Yet, it’s the most valuable sort to learn, primarily because of interview. I think quicksort is a good test of coding abilities. The challenges:

#1 high-level goal of first pass — hard to remember!
#2 the gist of the first pass
#3 implementation in any language — many pitfalls

http://baike.baidu.com/link?url=rl5hQIbAqdmt53Pmxp7FXhrksHQxjOIb8Knd7dI4xQ0lRSjLNdSbcVj_Dcav-V17dKBe1ggrOWXsDinNPINd22RnFZ2cQ5MDkWdGM8XZwc1TTqtMNfc8kM-0LuT6iCrDR-RigbcKPpYQwK_gDWWOQ_ has real code.

High-level keywords:

  • pivot Object — the rightmost object in a section can be designated the pivot object. Some people use the 1st object or a random object within the section. To keep things simple, we will assume the values are unique
  • final resting place — goal is to put the pivot object into its final resting place within the section, using scan-and-swap
  • swaps — are the mechanism of movements
  • scan — you must scan in some direction
  • partition — after the first pass, the pivot object is in its final resting place and all smaller objects are on its left.

First we need to understand the high-level goal. Then the next challenge is the partition algorithm. The only way to remember the implementation details is writing the code.

On P 146 [[introduction to algorithms]], the procedure partition(A,p,r) does the following on the Section A[p,r] inclusive.

  • it progressively shifts the rightmost (pivot) object from r to the grave/anchor position within the section
  • it keeps the rightmost object value as the benchmark value throughout the procedure.
  • it returns the new index of this object. The index is defined in the entire array A[].
  • it shuffles 0 or more elements within the section
  • it doesn’t try to sort any subsection

Upon receiving an unsorted section, the procedure simply puts the rightmost thingy into the grave position within the section.

Corollary: first scene in the quicksort movie actually completes the job of putting the rightmost object into its final resting place as an anchor within the entire array. After that, we focus on sorting the “left-section” and the “right-section” (in separate threads) without worrying about the first anchor object. Within the left-section, first scene completes the job of putting the rightmost object into its grave, a final resting place within the entire array.

Coding note — the recursion is not using a single function name like A calling A itself. Instead, qsort() calls partition() then qsort(). Most of the work is in partition().

Coding note — partition() function isn’t recursive in itself.

Wall St cod`IV don’t care about efficiency

Most challenging algo interviews (onsite) are really about “solve it by hook or by crook” regardless of efficiency. (Usually there isn't, but if there's an obvious brute-force solution it gives you no credit anyway.)

In the toughest algo questions, usually there's no memory capacity issue to worry about.
Occasionally, interviewer stipulates O(N logN) or O(1)
Once we solve it we can improve efficiency. It's a second phase. Can be easier than first phase.
In that case threading, sorting … are unimportant. Instead we need judicious use of trees, recursions, pattern recognition… and very clear thinking.
See [[EPI300]] and the green book by Zhou Xinfeng

prefer for(;;)+break: cod`IV

For me at least, the sequencing of the 3-piece for-loop is sometimes trickier than I thought. It’s supposedly simple rule(s), but I don’t get it exactly right sometimes. Can you always intuitively answer these simple questions? (Answers scattered.)

A87: ALWAYS absolutely nothing
A29: many statements. They are separated by many statements.

Q1: how many times (minimum, maximum) does the #1 piece execute?
Q2: how many times (minimum, maximum) does the #2 piece execute?
Q3: how many times (minimum, maximum) does the #3 piece execute?
Q: Does the number in A2 always exceeds A3 or the reverse, or no always-rule?
Q29: what might happen between #2 and #3 statements?
Q30: what might happen between #3 and #2? I feel nothing could happen.
Q87: what might happen between #1 and #2 statements?
Q: what’s the very last statement (one of 3 pieces or a something in loop body) executed before loop exit? Is it an “always” rule?

If there’s a q(continue), then things get less intuitive. http://stackoverflow.com/questions/16598222/why-is-continue-statement-ignoring-the-loop-counter-increment-in-while-loop explains the subtle difference between while-loop vs for-loop when you use “continue”.

In contrast, while-loop is explicit. So is do-while. In projects, for-loop is concise and often more expressive. In coding interviews, conditions are seldom perfect, simple and straightforward, so for-loop is error prone. White-board coding IV (perhaps bbg too) is all about nitty-gritty details. The condition hidden in the for-loop is not explicit enough! I would rather use for(;;) and check the condition inside and break.

The least error-prone is for(;;) with breaks. I guess some coding interviewers may not like it, but the more tricky the algorithm is, the more we appreciate the simplicity of this coding style.

Always safe to start your coding interview with an a for(;;) loop and carefully add to the header. You can still have increments and /break/continue inside.

## tips: quickly get into shape4algo IV

Q: how many days (immersion) do you need to get back to shape for coding interview?
A: a week to 2 months

This question becomes more relevant when you realize your proficiency is way off your peak level achieved x years ago.

xp: I was full time job hunting after layoff from BofA. At the same time Ashish was also trying. He took a few months to get into shape.

Note “shape” doesn’t involve advanced skills. It’s all about basic know-how. Therefore, this goal is a relatively low-hanging fruit and within my reach. Therefore, I feel motivated. I feel (including coding) interview preparation is my favorite sport. I fee like a prize fighter. When I prepare for this, I never feel spinning my wheel as I feel in other endeavors. My spare time utilization is highest in this area. In this area, I can more easily sink my teeth in, engage, and dig in my heels (as in tug-of-war)

  1. review my eclipse IV code in java and c++. Real code supposed to help memory more.
    1. review the tricky algo in my blog
  2. books like [[Elements of Programming Interview]]
    1. careercup? less ideal than EPI
  3. paste everywhere tiny stickers with Q&A? less important for pure algo quizzes
  4. self-tests like gaokao

 

%% priorities in a take-home cod`IV

A lot of times the requirements are way too numerous or stringent, given the time limit. Must give up some. Here are my priorities:

  1.  basic functionality. The essential problem should be solved, or shown to be solvable.
    • pass the essential test cases only
  2. On that foundation, add as many big features (in the problem statement) as I can within the time limit. Leave out the small features.
  3. simplify. Simplicity is the first element of clean , readable code.

I guess some hiring managers are very particular about code quality and readability. I feel it’s like beauty contest. I would give up in those cases. I was told JPM follows [[Clean Code]] when judging/scoring/ranking code submitted.

Need to ensure file timestamps are all within a short window. Prefer to use fewer files. Java solutions require more files :(. If I claim 2H, then better leave some rough edges in the code like input validations.

tips for bbg cod`IV

  • chrome (not Opera) supports Alt-R
  • Show 67 lines of source code
    • chrome F11 to toggle full screen
    • chrome can zoom out 75% to show 67 lines in editor, if you can’t find a bigger monitor.
    • use hackerrank top right icon -> settings -> SMALL font
    • put multiple lines in one line as much as possible
    • Can we hide the address bar?
  • hackerrank top right icon -> settings -> light (not dark) scheme shows line highlight better, but dark shows text better.
  • add comments to show your thinking

Here’s some code we can copy-paste:

#include 
#include 
#define ss if(1>0)cout
using namespace std;   int i1, i2, i3, N;   string s, s1, s2, s3;
int main(){
    ss<<"s = "<<s<<endl;
}

 

[07] google-style interviews: apply comp-science Constructs on realistic problems

Hi LS,

Now I think yesterday’s toughest interview questions are similar in spirit to Google interview questions. I think the key skill tested yesterday was “how does this candidate apply computer science constructs to real world problems”. That’s what I meant when I said “connecting the algorithms/data-structures with the given requirements“. Before you can identify any algo/data-structure to model the requirements, you have no clue how to support the requirements. Whenever we see a first-in-first-out system like Green Card applicants, we automatically think of a Queue data structure — ie connecting the Queue construct to a real world problem.

A 6-year veteran developer like me is supposed to be familiar with
1) associative arrays, hashmaps, sets, binary search trees, doubly linked lists, multi-dimensional arrays and (hopefully) circular linked lists, binary heaps, red-black trees, and any combination of the above like a stack of hashmaps,
2) the concepts of space efficiency, time efficiency, random access, sequential access, what can/can’t be sorted …
3) OO concepts of dependency, coupling, polymorphism, static, multiple inheritance, HAS-A vs IS-A, setters (extremely important) …
4) OO design patterns

But this veteran may not know how to APPLY these constructs to a real-world problem, according to my observation. All of Google’s and my recent problem-solving interview questions attempt to test a candidate’s analysis skill to “apply tools to problems”. In my case, I couldn’t applied the Strategy design pattern unless I spot the similarity between the given requirement and the Strategy pattern’s requirements.

The 4 groups of tools mentioned above are simple tools when studied individually, but any design that need tools from 3 of these groups is likely to be non-trivial. Consider algorithms to delete a node from a binary search tree.

Finally I have some idea why Google like those questions, including the question about “1-7 random number generator using a 1-5 generator”.

recursion – whiteboard cod`IV tips

  • spend some time writing down the external interface of the recursive func — exactly what to print/return, and what global variables to update.
  • define end-of-recursion condition explicitly. Interviewers want to see that.
  • list all important local variables vs global variables on the side.
  • Some variables must be local — on the stack. All other variables had better be global variables.
    • sometimes local variables are simpler — throw-away temp
    • sometimes global variables are simpler — fewer stateful objects.
    • Simplifies the visualization. Any variable passed into a recursive call is additional state on every stack frame and makes the logic harder to reason about. This is more serious when there are many such local states to keep in mind