key^payload: realistic treeNode #hashset

I think only SEARCH trees have keys. “Search” means key search. In a search tree (and hashset), each node carries a (usually unique) key + 0 or more data fields as payload.

Insight — Conceptually the key is not part of the payload. Payload implies “additional information”. In contrast, key is part of the search tree (and hashset) infrastructure, similar to auto-increment record IDs in database. In many systems, the key also has natural meaning, unlike auto-incremented IDs.

Insight — If a tree has no payload field, then useful info can only exist in the key. This is fairly common.

For a treemap or hashmap, the key/value pair can be seen as “key+payload”. My re_hash_table_LinearProbing.py implementation saves a key/value pair in each bucket.

A useful graph (including tree , linked list, but not hashset) can have payloads but no search keys. The graph nodes can hold pointers to payload objects on heap [1]. Or The graph nodes can hold Boolean values. Graph construction can be quite flexible and arbitrary. So how do you select a graph node? Just follow some iteration/navigation rules.

Aha — similar situation: linked list has well-defined iterator but no search key . Ditto vector.

[1] With pre-allocation, a static array substitutes for the heap.

Insight — BST, priorityQ, and hash tables need search key in each item.

I think non-search-TREES are rarely useful. They mostly show up in contrived interview questions. You can run BFT, pre|post-order DFT, but not BF S / DF S, since there’s nothing to “search”.

Insight — You may say search by payload, but some trees have Boolean payloads.

Advertisements

## same-complexity optimization in algo design

A lot of algorithm optimizations do not reduce the time/space complexity, but offer other benefits. I will use “ECO” to denote such optimizations. (E can stand for Equivalent.)

  • benefit — smaller data set
    • eg: tree pruning
    • eg: keep only peak+trough
  • benefit — fewer edge cases
  • benefit — easier to understand
  • benefit — easier to implement
  • benefit — easier to debug and investigate.
    • eg: RBTree has this advantage over priorityQ
  • — examples:
  • eg: yield-generator
  • eg: replace RBTree with priorityQ or sorted vector
  • eg: bidirectional BFS in https://leetcode.com/problems/word-ladder/solution/

Note memoization is more then ECO.

If you can convert a recursive solution, then it is often more than ECO.

efficient memoization: keyed by auto-increment id

Market Value of this knowledge — I feel this level of intricate knowledge is useful mostly in bigO coding interviews. If you get the bigO wrong there, you can lose major points. Versioned dict #indeed is one typical coding interview question, where the result of read(id) can be memoized to speed up subsequent reads.

Q: what’s the optimal time complexity of maintaining the memoization data structure? User requests can hit us with read(9), read(88), read(15), read(0), read(15) again…

Notation — N:= number of id values.

  • Option 0 (unusable): hash table — nearest-neighbor search impossible
  • Option 1 (sub-optimal): RBTree —  Lookup is O(logN). In general, insertion costs O(logN).

( Special case — If the read() id never decreases, then STL RBtree insert-with-hint is O(1). )

  • Option 2: vector — indexed by id [1]. Lookup is binary search O(logN). Insertion is always amortized O(1). Here’s why.

Eg: after read(9), we get read(88). We would need to null-fill the vector until position 88. This null-fill design looks sub-optimal.

But how is the id 88 created after 87 ? Probably in some write() operation. So write() can incrementally expand this vector 🙂

Actually, this incremental-insert design is not faster. I would rather leave write() alone as the null-fill design is a mass-insert and minimizes re-allocation.

[1] Is it common or lucky to have id values as auto-increment integers? I think it’s quite common in practice and in algo interviews. Auto-increment Integer id is light-weight and fast to generate.

%%approaches to classic generator problemS

* p2u in next_perm

* insert at each position of each array, in a growing collection to create new arrays for the collection. Optionally, all arrays are immutable.

Actually, only two approaches so far, though each of them can be adapted in many ways.

Note many (simple) classic generator algos are required in coding tests or (practical) algo problems

numPad problem: generator

Q (Leetcode problem 17)… Given a string containing digits from 2-9 inclusive, return all possible letter combinations (not permutations) that the number could represent.

2: abc
3: def
4: ghi
5: jkl
6: mno
7: pqrs
8: tuv
9: wxyz

Example:

Input: “23”
Output: [“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].

Output need not be sorted but I would aim to print each word as sorted and also print all words in ascending order

—–
Group all the er’s into bag2, then all the qi’s into bag7… Generate the strings for each bag independently. After that, problem becomes

Q2: given N (say 11) Sets of unique strings, pick one from each set and concate the N strings as one output. Generate all output. I feel this can’t use the cookbook recipe since input is not one “pool” string but n sets. I think iterative is fine.

idea: Loop variable to keep the N indices (iterators) into each set
idea (dp + yield): generate the output for N=2. save to a collection. then take in next Set.

–yield-generator redrawC() generates …
input “88” we have 6 combos? tt tu tv uu uv vv
input “888” we have 10 combos? ttt ttu ttv tuu tuv tvv uuu uuv uvv vvv

–we need good variable names.
For the 9 digits, every digit is immediately mapped to a name string like ‘2’ -> “er” and I hope not to use the digits any more.
Java would use enum

To minimize confusion, Create typedef LOB as alias for either vector<char> or the string form. Will have 8 const LOB instances. Java would use enum

struct Bundle{
set<vector<char>> clubOfWords;
size_t repeatOfThisButton;
LOB lob; //compile-time constant
};

The utility function would be
Bundle gen(vector<char> const & lob /*lettersOnOneButton*/ , int repeat). This function is fairly simple. for er_5, we have 3^5 possible words in the club

sort input into 222223444 then create map:
“er_5” -> a bundle
“san1” -> a bundle
“si_3” -> a bundle

A major Miletone is when the map is populated with the clubs. Now generate combos … better use “append” approach.

classic generator problems: non-trivial

classic generator problems (such as combination sum, combo with redraw, phonePad…) are not simple for most of us programmers. Even though these are classic and well-researched, most programmers can’t really master them .. cognitive barrier is formidable.

Our mind is not constructed to deal with such challenges. I have tried and failed many times to compare across various generator problems hoping to extract the gist like thick->thin 总结规律

Duplication in output —  is one of many tough challenges.

The recursion-in-loop magic is another “thingy” beyond our comprehension.

Many of them are DP problems —

  • A size-5 data set is easier to deal with than size-6
  • real challenge is to train our human brain to see through the “forest” and identify how size-5  RESULTS can help solve size-6

I believe these algos are building blocks of many coding problems, both real-world problems and quiz problems.

convert a recursive algo to iterative #inOrderWalk

Suppose you have just one function being called recursively. (2-function scenario is similar.) Say it has 5 parameters. Create a struct named FRAME (having 5 fields + possibly a field for lineNo/instructionPointer.)

Maintain a stack holding the Frame instances. Each time the recursive algorithm adds to the call stack, we add to our stack too.

Wiki page on inorder tree walk  has very concise recursive/iterative algos. https://github.com/tiger40490/repo1/blob/py1/py/tree/iterative_InOrderWalk.py is my own attempt that’s not so simple. Some lessons:

  • Differentiate between popping vs peeking the top.
  • For a given node, popping and printing generally happen at different times without any clear pattern.
    • the sequence of pop() is probably a pre-order tree walk
    • the sequence of print is an in-order tree walk

coin problem #all large-enough amounts are decomposable

This is not really a algo IV question, but more like brain teaser problem.

Based on https://en.wikipedia.org/wiki/Coin_problem — For example, the largest amount that cannot be obtained using only coins of 3 and 5 units is 7 units. The solution to this problem for a given set of coin denominations is called the Frobenius number of the set. The Frobenius number exists as long as the set of coin denominations has no common divisor.

Note if a common divisor exists as in {2,4} then all the odd amounts will be non-decomposable.

Q: why a very large amount is always decomposable ? Give an intuitive explanation for 2 coin values like 3 and 5.

Here’s an incomplete answer — 15 (=3*5), 16, 17 are all decomposable. Any larger number can be solved by adding 3’s .

In fact, it was proven that any amount greater than (not equal to) [xy-x-y] are always decomposable. So if we are given 2 coin values (like 4,5, where x is the smaller value) we can easily figure out a range

xy-x-y+1  to xy-y

are each decomposable. Note this range has x distinct values. So any higher amount are easily solved by adding x’s

Also note xy-y is obviously decomposable as (x-1)y.

 

next_perm@N color socks #complex #100%

A common IDE coding challenge — given x pairs socks of various colors, generate all the permutations, in ascending order. Each color has a value.

–Solution 1: std::next_permutation() and prev_permutation()

–solution 2: I can probably write my own next_perm(). Using This function we can generate an ascending sequence of permutations starting from the current content of a vector.

https://github.com/tiger40490/repo1/blob/cpp1/cpp/combo_permu/nextPerm.cpp is my iterative solution, but should use lower_bound()

https://github.com/tiger40490/repo1/blob/py1/py/combo_perm/nextPermOfNSocks.py is my python solution, overcoming the lower_bound problem.

relating my perm/comb algos

–next_perm: I have an iterative solution

–next perm 5C3: iterative algo, growing global collection

–next_combo 5C3: I have a (approx) 10-line recursive algo. (Iterative algo is non-ideal). Passing in two collections.

–next_abbreviation of any length: I have a (approx) 10-line recursive algo. Using global collection, this algo is simpler than next_combo

–So far, these algos are decent but have nothing in common.

 

next abbreviation@word with repeat char #2^N #100%

This is a real coding question at 10gen/mongoDB

https://github.com/tiger40490/repo1/blob/py1/py/combo_perm/abbrIterative.py is a simple iterative py solution. Not ascending.

Q1: Given a word with unique letter (like “abc”), Can you write c++ program to generate all abbreviations in any order?
Q2: same question, but don’t use any external storage beside character arrays.
Q3: same question, but output in ascending order? Expected output:

  1. a
  2. ab
  3. abc
  4. ac
  5. b
  6. bc
  7. c

It’s daunting to generate this sequence without recursion. https://github.com/tiger40490/repo1/blob/cpp1/cpp1/combo_permu/abbr_ascendRecursive.cpp is my recursive solution to Q3.

Q4: what if the word has non-unique letters, like “mongo”? The only solution I know relies on an external lookup device.

generate random line-up@Any combo@N boys #70%

A standard permutation/combination problem in some coding tests. You are often required to iterate all of them.

Given N cities, how many permutations of any combinations are there in total.

My iterative sum formula: answer(N)= N_choose_0 + N_choose_1 * 1! + N_choose_2 * 2! + … + N_choose_N * N!

N_choose_0 = 1 !

–recursive algo: use answer(N-1) to answer(N)

–iterative algo:

  • Suppose we have an iterative_next_perm(list) function already written.
  • suppose we have an iterative_next_combo(N, 3) that generates all combinations of 3 out of N distinct chars.

Then, here’s a solution — call

iterative_next_combo(N,1)
iterative_next_combo(N,2)
iterative_next_combo(N,3)…
iterative_next_combo(N,N), in a loop (of N iterations).

Suppose one of the N calls generated 221 combinations. Run a loop (of 221 iterations) each time pass one combination into iterative_next_perm(combo). So our main program has only 2 nested loops. Most of the complexities are encapsulated in iterative_next_perm() and iterative_next_combo()

next Combo@3,using5distinct chars,permitting redraw

Modified from Leetcode problem 17. Suppose there is nothing but one red button. and there are L (like 5) letters on it.

Q: With 4 (=C) draws from 3 (=L) letters (same phone pad button), how many permutations? L^C.
Q: With 4 (=C) draws from 3 (=L) letters, how many combinations?

For C=1, Ans=3
For C=2, Ans=6
For C=3, Ans=10= 6 + 3 + 1?
For C=4, Ans=15=10+(10-6)+1
For C=5, Ans=21=15+(15-10)+1

–My explanation of the count:

Key: Each combo is represented as a sorted vector (ascending). There’s one-to-one mapping between such a vector and a combo.

let’s say L=3 and C grows from 1 to 3 .. For C=2, I put all combos on 3 rows (3 vectors or lists)

  • aa ab ac #all that starts with a
  • bb bc #all that start with b
  • cc # lone wolf

For C=3, Ans

  • first container is populated by prepending ‘a’ to all 3 “old” containers of items
  • 2nd container is populated by prepending ‘b’ to 2nd-and-lower old containers
  • 3rd container is always a lone wolf

Both solutions below are simple, reusable and implemented in https://github.com/tiger40490/repo1/blob/cpp1/cpp/combo_permu/nextComboOf3redrawFrom5.cpp

–sol-1 efficient incremental solution — for C=3, given one combo as a string, find the “next” combo. For example after bbc, we should get bcc. Bonus feature — output is naturally sorted 🙂

–sol 2: append the next char ..

next split@N boys #51%

N boys are all unique “entities”, each identified by student id. Later we can look into “next split of N colored balls, having J unique colors”.

In a split, every boy belongs to exactly one group (minimum 1 member). We could rely on python’s default sort order, but for now let’s define a sort order between two groups AA and BB:

  1. sort by group size
  2. If same size, sort by the lowest student id in AA vs in BB.

Every “split” is recorded as a sorted list of groups. I will define a sort order between 2 splits:

  1. sort by list size
  2. if same size, sort by first group, the by 2nd group..

Q1: how many ways to split N boys?
%%A: First we line up N boys — there are N! line-ups. In each line-up, we have 2^(N-1) splits because there are N-1 slots to place a group-boundary. This is a way to iterate over ALL splits, but without uniqueness.

Q2: Write a program to generate all splits in some order. For example, with 3 boys h,i,j:

  1. h/i/j in a giant group…
  2. –3 split-of-2-groups: h, i/j
  3. i, h/j
  4. j, h/i…
  5. –1 split of 3 singular groups: h, i, j
  6. ==== total 5 distinct splits showing 10 group objects but not all distinct

With 3+1 boys h,i,j,k: First add k to each of 10 group objects:

  1. h/i/j/k
  2. h/k, i/j
  3. h, i/j/k
  4. i/k, h/j
  5. i, h/j/k
  6. j/k, h/i
  7. j, h/i/k
  8. h,i, j/k
  9. h,j, i/k
  10. i,j, h/… — so far, 10 splits. Now 5 more splits featuring k in its own singular group
  11. k, h/i/j
  12. h, k, i/j
  13. i, k, h/j
  14. j, k, h/i
  15. h,i,j,k

—- analysis: I don’t know how many splits there will be for N boys. An iterative function will probably work:

After I listed out exactly 5 splits of 3 boys, and I added another boy. So here’s the algo I used — For each of the 5 (existing) splits, add this boy to each of 10 group objects, or put himself as a new singular group.

next Perm@3boys out@5, non-recursive #complex

Latest -- https://github.com/tiger40490/repo1/blob/cpp1/cpp1/combo_permu/iterative_nextPerm3boysOf5.cpp


// Requirement: generate all permutations of C(like 3) chars
//from N(like 5). The count should be N!/(N-C)!
// Bonus: generate in ascending order, where 'ascending' is
//defined on the basis that within the original word, a char
//has lower value than any char on its right. This is more clear
//when the word itself is a sorted string, but actually it's
//not needed.
//
//global collection is simpler than stack variables. Easier to visualize
//and uses less memory
#include <iostream>
#include <sstream>
#include <vector>
#include <deque>
#include <algorithm>
#include <iomanip>
#include <assert.h>
using namespace std;

string _tmp="abcd"; vector<char> const pool(_tmp.begin(), _tmp.end());
vector<size_t> poolIndex;
size_t const C = 3, N = pool.size(); //wanted: all permutations of C, out of the pool of items

//global collection, to be updated in each recursive layer.
vector<vector<size_t> > coll;
// Note each item (like a char or a color or a studentId) is
// represented in the global collection by an unsigned integer.
// This is the positional index in the original "pool" of items.
// This scheme ensures the permutations produced is ascending

string show(vector<size_t> const & v, string headline="", bool isPrint=true){
  stringstream ss;
  for (int i=0; i<v.size(); ++i){
    ss<<setw(5)<<pool[v[i]];
  }
  if (isPrint) cout<<ss.str()<<" <-- "<<headline<<v.size()<<endl; return ss.str(); 
} 
void dump(string headline="", bool isAssert=true){ size_t const cnt = coll.size(); assert(cnt); size_t const len = coll[0].size(); size_t exp = 1; for (int t=N; t>N-len; --t) exp *= t; //loop len times
  assert(cnt == exp);

  stringstream ss;
  string last = "";
  for(int i=0; i<cnt; ++i){
    string item=show(coll[i], "", false);
    ss<<item<<endl;
    if (!isAssert) continue;
    assert(last<item && "should be strictly asending");
    last = item;
  }
  cout<<headline<<"\t size "<<cnt<<endl<<ss.str()<<endl;
}

//RVO should kick in to skip the copying upon return
vector<size_t> const find_unused(vector<size_t> const & perm, size_t const len){
      vector<size_t> tmp4set_diff(perm); //permutations are by defnition unsorted.
      sort(tmp4set_diff.begin(), tmp4set_diff.end());
      vector<size_t> unused(N-len);
      set_difference(poolIndex.begin(), poolIndex.end(), tmp4set_diff.begin(),tmp4set_diff.end(),unused.begin());
      //show(tmp4set_diff, "tmp4set_diff"); show(poolIndex, "poolIndex"); show(unused, "unused");
      return unused;
}

//RVO should kick in to skip the copying upon return
vector<size_t> const new_perm(vector<size_t> const & perm, size_t unused){
        vector<size_t> newPerm(perm);
        newPerm.push_back(unused);
        //show(newPerm, "newPerm");
        return newPerm;
}
//This algo is considerably more complex than many recursive algos
//we have written recently, largely due to the set_difference()
void next_perm_from_pool_iterative(){
  for(size_t loop=0;loop<9 /*useful during dev to control when to exit*/;++loop){
    if (coll.empty()){
      for(size_t j=0; j<pool.size(); ++j){
        coll.push_back(vector<size_t>(1, j));
        poolIndex.push_back(j);
      }
      // dump("^^^^ after initilization of coll ^^^^");
    }
    assert(!coll.empty());
    size_t const len=coll[0].size();
    assert(loop+1 == len);
    if (len == C) {
      cout<<"Done:)"<<endl;
      return;
    }
    vector<vector<size_t> > newcoll;
    for(int kk=0; kk<coll.size(); ++kk){
      vector<size_t> const & perm = coll[kk];
      vector<size_t> unused(find_unused (perm, len));

      //now unused contains the pool items not in the current perm.
      //Suppose there are 3 unused items, we will create 3 new permutations
      //by appending each one to the current perm
      for(vector<size_t>::iterator it=unused.begin(); it != unused.end(); ++it){
        newcoll.push_back(new_perm(perm, *it));
      }
    }
    coll = newcoll;
    dump("^^^^ end of iteration ^^^^");
  }
}

int main(){
  next_perm_from_pool_iterative();
}

next_Perm@3boys out@5 #80%

algo-practice: generate permutation@3, using5distinct chars

Such a skill might be needed in some coding IV sooner or later. Let’s write this in py or c++. Formally,

Q1: generate all permutations of 3, from 5 distinct chars, in any order.
Q2: generate all permutations of 3, from 5 distinct chars, in ascending order. You can sort the 5 chars first.
Q2b: once you have generated one permutation, how do you identify The next?

Note the same solution is a generalization of std::next_permutation(), so once you have this solution you have that solution.

How many? 5-choose-3 * 3! = 5!/(5-3)! = 5*4*3 = 60, denoted Answer(3). Paradoxically, Answer(4) == Answer(5) = 120

–algorithm 1 for Q1

  • 1st generate 5 single-char strings;
  • then for each generate 4 two-char strings. We get 20 strings.

–algorithm 1b for Q1: rec(5,3) will call rec(5,2). rec(5,2) has 20 items, each can generate 3 items for rec(5.3), because each item has 2 characters and a void to be filled by the 3 unused chars.

The 20 items returned should be a pair{vector of 2, vector of 3}

This produces a sorted collection:)

See my code  https://github.com/tiger40490/repo1/blob/py1/py/combo_perm/nextPerm%403boysFrom5.py

 

 

 

next_Combo@3 boys out@5 # 100%

Given, abcde, How many combinations of 3? 5-choose-3 = 10 standard formula, but let’s implement in py or c++.

It’s useful to define a score for a combination — sort the combination into a string. The string is the score. Now,

Q1: generate all combinations@3 from 5 distinct chars, in ascending score.
Q2 (more importantly) given any combination of 3, generate the next higher combination of 3.  Output each combination as a sorted string to keep things clean. Extremely effective constraint and simplification.

1) https://github.com/tiger40490/repo1/blob/py1/py/combo_perm/nextComboOf3from6boys.py is a decent recursive.

2) fixed-length abbreviation generator also generates exactly the same  sequence!

3) Perhaps we can modify the iterative generate random perm@3boys out@5 algorithm:

Key: Scan from end of string to identify position2upgrade. Compare current (i.e.last) position with the unused characters. If can’t upgrade me [eg abe], then move left which is guaranteed to be a lower character. Now compare the new “me” with only the unused characters (in this algo we don’t allow swap within the string) If can’t upgrade “me”, then move left.

If current position is upgradeable, then set it as p2u. Upgrade to the lowest unused character. Then reset all characters on my right and return.

  1. abc
  2. abd
  3. abe
  4. acd
  5. ace
  6. ade //last 2 letters are the max. p2u = 0
  7. bcd
  8. bce
  9. bde
  10. cde

 

next_Combo@3 boys out@5 #recursive descending

//This recursive version suffers from stack overflow
//but it's able to print out combinations in Descending order and
//maintains the relative positions between any 2 items
//
//This version reduces vector cloning by growing/shrinking the prefix vector
#include <iostream>
#include <sstream>
#include <vector>
#include <iomanip> //setw
#include <algorithm>  //sort
#include <assert.h>
using namespace std;
size_t calls=0, combos=0;
size_t const C=3; //how many in each combination
vector<char> emptyV;

template<typename T> void dump(vector<T> const & p, string const & s){
  cout<<"------------ "<<s<<" ------------ size = "<<p.size()<<endl;
  for(int i=0; i<p.size(); ++i) cout<<setw(5)<<p[i];
  if (p.size()) cout<<endl;
}
template<typename T> int show(vector<T> const * p, vector<T> const * v = NULL){
  ++ combos;
  stringstream ss;
  for(int i=0; i<p->size(); ++i) ss<<setw(5)<<(*p)[i];
  if (v){
    //cout<<",";
    for(int i=0; i<v->size(); ++i) ss<<setw(5)<<(*v)[i];
  }
  static string last("ZZZZZ");
  string combo=ss.str();
  cout<<"combo: "<<combo<<endl; assert(last >= combo);
  last = combo;
}

template<typename T> int recurs(vector<T> & prefix, vector<T> const & pool){// size_t const suffix ){
  ++calls;
  dump(prefix, "entering ... prefix"); dump(pool, "pool");
  if (prefix.size()            == C) return show(&prefix);
  if (prefix.size()+pool.size()== C) return show(&prefix, &pool);
  assert (!pool.empty());
  vector<T> const newPool(pool.begin()+1, pool.end());
  recurs(prefix, newPool);
  prefix.push_back(pool[0]);
  recurs(prefix, newPool);//this function returns only after all the layer are done
  prefix.pop_back();
}

int main() {
  string tmp = "abcde";
  vector<char> v(tmp.begin(), tmp.end());
  assert(C <= v.size());
  recurs(emptyV, v);
  cout<<calls<<"  calls to the recursive funcion to generate "<<combos<<endl;
}

next_Combo@3 boys out@5 #recursive

//This recursive version suffers from stack overflow but
//it's able to print out combinations in ascending order and
//maintains the relative positions between any 2 items
//
//This version reduces vector cloning by growing/shrinking
//global objects but with higher complexity
//
//However, global variables actually simplify the logic!
#include <iostream>
#include <sstream>
#include <deque>
#include <iomanip> //setw
#include <algorithm>  //sort
#include <assert.h>
//#define DEBUG
using namespace std;
size_t calls=0, combos=0;
size_t const C=3; //how many in each combination
string tmp = "abcde";
deque<char> pool(tmp.begin(), tmp.end());
deque<char> prefix;

template<typename T> void dumpDeque(deque<T> const & p, string const & headline){
  cout<<"-- "<<headline<<" -- size = "<<p.size()<<endl;
  for(int i=0; i<p.size(); ++i) cout<<setw(5)<<p[i];
  cout<<endl;
}
template<typename T> int showCombo(deque<T> const * p){
  ++ combos;
  stringstream ss;
  for(int i=0; i<p->size(); ++i) ss<<setw(5)<<(*p)[i];
  static string last;
  string combo=ss.str();
  cout<<"combo: "<<combo<<endl;
  assert(last <= combo && "should be ascending");
  last = combo;
}

template<typename T> int recurs(){
  ++calls;
#ifdef DEBUG
  cout<<"-------------\nentering "; dumpDeque(prefix, "prefix"); dumpDeque(pool, "pool");
#endif
  if (prefix.size() == C) return showCombo(&prefix);
  if (pool.empty()) return 0;
  T poolhead = pool.front(); pool.pop_front();

  prefix.push_back(poolhead); //add poolhead to prefix

  //this 1st recursive function call starts a rather deep call stack and prints
  //all combinations with the given (new longer) prefix
  recurs<T>();//use the longer prefix and the shorter pool
  prefix.pop_back();//restore prefix
  recurs<T>();
  pool.push_front(poolhead); //restore pool, needed by the 2nd call in the parent stack
#ifdef DEBUG
  cout<<"^^^^^^ restored before returning "; dumpDeque(prefix, "prefix"); dumpDeque(pool, "pool");
#endif
}

int main() {
  assert(C <= pool.size());
  recurs<char>();
  cout<<calls<<"  calls to the recursive function to generate "<<combos<<endl;
}

next_Combo@3 boys out@5 #iterative complex

//Without loss of generality, each combination is internally represented
//as a sorted vector (ascending).
//There's one-to-one mapping between such a vector and a combination
#include <iostream>
#include <vector>
#include <iomanip> //setw
#include <algorithm>  //sort
#include <assert.h>
using namespace std;
size_t changes=0, calls=0;
size_t const C=3; //how many in each combination

template<typename ITR> bool isAscending (ITR const b, ITR const end){
  for (ITR last = b, i = b; i!=end; ++i){
    if (*last > *i) {
      cout<<*last<<" should be lower (or equal) but is higher than "<<*i<<endl;
      return false;
    }
  }
  return true;
}
template<typename T> void dump(vector<T> & v,  bool isAssert = true){
  for(int i=0; i<v.size(); ++i) {
    cout<<setw(5)<<v[i];
    if (i == C-1) cout<<"  unused:";
  }
  cout<<endl;
  for(int i=0; i<v.size(); ++i){
    cout<<setw(5)<<i;
    if (i == C-1) cout<<"  unused:";
  }
  cout<<endl<<"---------------------------------"<<endl;
  if(isAssert){
    assert(isAscending(v.begin(), v.begin()+C) && "1st C elements should be ascending after next_combo (not next_perm)");
    assert(isAscending(v.begin()+C+1, v.end()) && "unused section should be ascending");
  }
}

template<typename T> bool reshuffle(vector<T> & v, int p2u){
//      cout<<"after swap"<<endl; dump(v);
        sort(v.begin()+p2u+1, v.end());
//      cout<<"after sorting everyting to the right of p2u"<<endl; dump(v);

        if (p2u == C-1){
                sort(v.begin()+C, v.end());
                ++changes;
                return true;
        }
        assert(p2u<C-1);
        //now reset everything to my right
        //now locate the best_man (next item after the new p2u) .. can use binary search
        for(int i=p2u+1; i<v.size() ; ++i){
          if (i==v.size()){ //p2u is highest possible!
                //cout<<"p2u is already highest"<<endl;
                sort(v.begin()+C, v.end());
                ++changes;
                return true;
          }
          if (v[p2u]<v[i]){
                //cout<<"best man = "<<i<<endl;
                for(int j=0; p2u+1+j<=C-1; ++j){
                  swap(v[p2u+1+j], v[i+j]);
                }
                sort(v.begin()+C, v.end());
                ++changes;
                return true;
          }
        }//for
        // now must return!

        assert(1==0 && "should never reach here");
        cout<<"after best_man search"<<endl; dump(v);
}

// reshuffles vector to the next higher combo
//Assuming 5-choose-3, the 1st 3 chars represent the combination,
//and the remaining characters at the end of the vector are
//unused in the current combination.
template<typename T> bool next_combo(vector<T> & v){
  ++calls;
  dump(v );
  if (v.size() == C) return false; // C-choose-C == 1 !

  for(int p2u=C-1; /*last position*/ p2u >=0 ;--p2u){
    for (int unusedItem=C; unusedItem<v.size(); ++unusedItem){ //scan the unused section of the array
        if (v[p2u] < v[unusedItem]) {
          assert(p2u<unusedItem);
          swap(v[p2u], v[unusedItem]);  //p2u should not change further
        //cout<<"identified "<<p2u<<" as position to upgrade... Will reset subsequent positions, and return"<<endl;
          return reshuffle(v, p2u);
        }
    }
    // no p2u identified yet. move p2u marker to the left
  }//for
  cout<<"no more higher combo. This is the end"<<endl;
  return false;
}
int main() {
//  vector<float> v{111,222,333,444,555,666};
  string tmp = "abcdefg";
  vector<char> v(tmp.begin(), tmp.end());
  assert(C <= v.size());
  for(; calls<9992; ){
        if (!next_combo(v)){
         cout<<changes<<" changes performed till the highest combo; next_combo() call count = "<<calls<<endl;
         return 0;
        }
  }
}

tail-recursion Fibonacci # tricky]python

Tail recursion is a “halo” skill in coding interviews. It turns out that most recursive functions can be reworked into the tail-call form, according to http://chrispenner.ca/posts/python-tail-recursion.

The same author also demonstrates

  1. python recursion stack depth is about 1000 only, so deep recursion is unpopular in python
  2. python doesn’t support tail recursion
  3. some decorator trick can simulate tail recursion in python

—————-

Easiest demo problem is factorial(N). For Fibonacci, https://stackoverflow.com/questions/22111252/tail-recursion-fibonacci has a very short python implementation (though I suspect python doesn’t optimize tail recursion). Let me rephrase the question:

Q: Given f(firstVal=0, secondVal=1, length=0) returns 0, f(0,1,1) returns 1, can you implement f(0,1,N) using recursion but in O(N) time and O(1) space? Note Fib(N) ==f(0,1,N)

Key points in the python solution:

  • Start with iterative algo, then convert it to tail recursion.
  • use 2 extra arguments to hold last two intermediate values like Fib(2) Fib(3) etc
  • We saw in the iterative solution that memory usage is O(1), a good sign that tail recursion might be possible.
  • if you observe the sequence of Fib() values computed in the blackbox, actually, you see Fib(2), Fib(3) … up to Fib(N), exactly like the iterative solution.
  • solution is extremely short but non-trivial

https://github.com/tiger40490/repo1/blob/cpp1/cpp1/FibTailRecurse.cpp is my very brief implementation

## insertion sort: phrasebook

  • nearly sorted — for nearly-sorted sample, beat all other sorts  including counting sort
  • small — for small sample, beats MSD radix sort and all comparison sort
    • switch — many comparison sort implementations switch to insertion-sort when the sub-array becomes small
  • poker — Intuitively, this is how players sort poker cards
    • shift — requires shifting part of the sorted portion.

to a novice programmer — the importance of data structures in financial IT systems

Data structure is essential and non-trivial to every programming language on wall street — java (collections), c++ (STL), python/perl (high-level data types)… A lot of algorithms (in the traditional, strict sense of the word) are created on or using classic data structures. There are a lot of jargons you need to grasp. Everyday programming requires you to be familiar with common operations on these data structures, but these are relatively straightforward. However, here are some of the non-trivial aspects of data structures and

algorithms

* sort python dict or tuple

* internals of hash table and ConcurrentHashMap

* STL container holding pointers

* STL pair

* STL stream iterators

* customize a sorted set/map for MyClass in C++, which is harder than java

* sort a map by value (real interview question) in java. Perl and python is easy.

* whiteboard-implement a blocking stack/queue (UBS)

* whiteboard-implement a basic hash table (MS)

* find top 99 in a large array (Barc) but no need to return them sorted

* choose array vs circular array vs linked list, in terms of memory efficiency (JPM).

* given 2 nodes in a binary tree, with no pointers except pointer-to-parent, find lowest common ancestor (Google)

* iterative tree walk (Barc)

* filtering iterator (MS)

* STL transform(), erase(), partition() etc

* STL allocators

* STL functors, binders

* STL iterator adaptors (back_inserter etc)



Posted By familyman to learning finance,c++,py… <http://bigblog.tanbin.com/2011/05/to-novice-programmer-importance-of-data.html> at 5/03/2011 07:34:00 PM

100-gunmen puzzle

Q: Suppose 100 gunmen stand in a big circle arranged by height, clockwise from #1 (lowest) to #100 (highest). In first shooting round, #1 starts off by shooting clockwise, so #2 gone. Then #3 shoots clockwise at #4, and so on.  How many rounds will there be and who will be the last standing?

Q2 (adapted from Q1): Before #1 gets shot or shoots again, first round ends, and the lowest among the remaining gunmen continues to shoot clockwise. In this case #1 will never die. No puzzle to solve.

Assume each gunmen stays in his spot, and his spot has his name.

Analysis –
Let me first clarify the terminology.
* Each round has a “starter” shooter. The round ends immediately before he shoots again or immediately before he gets shot.
* Each round has a InitialCount := number of gunmen at start of that round.

— my Solution —
Round 1: starter is #1. InitialCount=100. This is an even round, so the starter remains.
Round 2: starter is #1. InitialCount=50. This is an even round, so the starter remains.

End of Round 2 the remaining shooters are #1 #5 #9… #97. They are 4 (i.e. 2^2) stops apart.
Round 3: starter is #1. InitialCount = 25. This is an odd round, so starter will shift anticlockwise by 2^2 to #97. Why am I so sure? Since InitialCount is odd, the highest (among the 25) gunmen will NOT die and will become the next round’s starter.

End of Round 3 the remaining gunmen are 8 (i.e. 2^3) stops apart. Therefore, highest two are #89 #97.
Round 4: starter is #97. InitialCount = 13. This is an odd round, so starter will shift anticlockwise by 2^3 to #89.

End of Round 4, the starter (#97) is a “sitting duck” to be shot soon.
Round 5: starter is #89. InitialCount = 7. This is an odd round, so starter will shift anticlockwise by 2^4 to #73.

End of Round 5, #89 is a “sitting duck” to be shot soon.
Round 6: starter is #73. InitialCount = 4, which is a power of 2, so #73 will remain the starter for all subsequent rounds and therefore the last standing.

dynamic programming problems #first look

The concept was well defined by the inventor but is now a bit vague. http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf is the best I have seen, but also check out http://mat.gsia.cmu.edu/classes/dynamic/dynamic.html . Below are some hallmarks of DP —

[M=math]
[C=comp science]

* solve sub-problems before solving the bigger problem. This approach/strategy is quite general
* [M] Principle of optimality
* [C] optimal substructure
* [M] stochastic dynamic programming
* [M] tail problems
* [C] DAGs

A major category of DP problems involve decision-making at discrete-time stages. Without stochastic elements, all the “contingent” decision-making could be (brought forward and) optimized upfront with clinical precision, like a robot analyzing a maze. In that case the stages are artificial, even unnecessary.

Therefore I now feel _ u n c e r t a i n t y _ is the major differentiator among DP problems. With uncertainty at each stage, we have no choice but break up the problem into periods. Without uncertainty, we can break up the problem artificially by period, or by segment…

Therefore, here are my classification of 3 categories of common DP problems (commonly found in tutorials) —
1) with uncertainty
2) with time periods without uncertainty
3) without time period. You create artificial stages. Often the simplest DP illustrations.

dynamic poker game in Zhou Xinfeng book

Q: you are dealt the 52 cards in a random sequence.
Each red card earns you $360
Each black card costs you $360
Game ends at end of the 52 draws or any time you quit. How do you optimize your earning and how much is admission ticket worth?

Let’s denote the amount of money you take home as H, a random variable. Your net profit/loss would be H minus admission price. If 555 reasonable/intelligent people play this game, then there would be five hundred and fifty-five values of H. What’s the average? That would be the answer.

p or “+” denotes the # of positive cards earned so far
n or “-” denotes the # of negative cards suffered so far

Exp(H|p=25,n=26) = Exp(H|p=26,n=26) = $0.
There’s an intrinsic value in our hands, Defined as i=(p-n). The e-value or Extrinsic value Evaluated from Expectation, may be higher or lower. Whenever i-value > e-value, we should exit. This is our strategy/policy.

Whenever intrinsic value <$0, E(H) is out of the money but always non-negative because we can wait till maturity and get all 52 cards.

E(p24,n26) = p(next is p)E(p25,n26) = 100%E(p25,n26) = $0
E(p26,n25) = $360     because we will exit

E(p25n25) = Prob(next is p)E(p26,n25) + Prob(next card is n)E(p25,n26) = 50%$360+0 = $180
E(p24n25) = p(p)E(p25,n25) + p(n)E(p24,n26)= p(p)E(p25,n25)+$0 = 66%$180= $120
E(p25n24)= p(p)E(26,n24)+p(n)E(p25,n25)= 33%$360×2 + 66%$180= $360

E(p24,n24)= half of E(25,24)+E(24,25)= half of  $360+$120= $240
E(p23,n25)= p(p)E(24,25)
+ p(n)E(p23,n26) # $0
=3/4x$120= $90
E(p23,n24)= p(p)E(24,24)+p(n)E(23,25)= 3/5 .$240+2/5 .$90

practical sort algorithms in popular languages

Important for …. real world software, interviews..

# 1) mergesort — chosen as
– primary sorter of java,
– primary sorter of perl,
– primary sorter of python

#2) quicksort — chosen by
– primary sorter of dotnet’s List.sort()
– primary sorter of STL (in a modified form — introsort)

heapsort – used in embedded, also part of the market-leading introsort
[iv] counting sort? important to natural words and numbers?
radix sort — important to natural words and numbers

# eor
[iv] bubble sort — easiest to code in an interview:)
[iv] insertion sort — simple
[iv] bucket
[iv] counting
[iv] radix

[iv=interview]

difference between Set and List

* Fundamentally, a list is maintained in insertion order physically, whereas a Set can optionally maintain insertion order (such as LinkedHashSet).

* Because of the insertion order, List can be the basis of Queues (FIFO) and Stacks (LIFO). A Set can’t.

* A set can stay sorted (eg TreeSet), whereas a list is seldom sorted. The most useful List implementations don’t “like” to stay sorted.

* Look-up i.e. finding an element, is faster in Set than List.

* In terms of API, the primary difference is — Set won’t add an object if it is equal to any existing element (determined by equals() method).

recursive -> iterative — level 2

In this example, first call’s job need 2nd call’s result. We build up another stack while depleting the args stack. This emulates the recursive descend->ascend.

 static List elements = new ArrayList();
 static {
  elements.add('a');
  elements.add('b');
  elements.add('c');
  elements.add('d');
 }
 static List combinations = new LinkedList();
 static LinkedList> stack1 = new LinkedList>();
 static LinkedList stack2 = new LinkedList();

static void interativePrintCombinations() {
stack1.add(elements);
while (!stack1.isEmpty()) {
List chars = stack1.removeLast();
char firstChar = chars.get(0);

System.out.println(“stack2 = ” + stack2);

if (chars.size() == 1) {
combinations.add(“”);
combinations.add(“” + firstChar);
continue;
}
stack2.add(firstChar);
stack1.add(chars.subList(1, chars.size()));
}

while (!stack2.isEmpty()) {
append1CharToEveryString(stack2.removeLast());
System.out.println(combinations);
}

}

private static void append1CharToEveryString(char firstChar) {
List tmp = new LinkedList();
for (String s : combinations) {
tmp.add(s + firstChar);
}
combinations.addAll(tmp);
}

static void getCombinations(List letters) {
if (letters.size() == 1) {
combinations.add(“”);
combinations.add(“” + letters.get(0));
return;
}
getCombinations(letters.subList(1, letters.size()));

// here we absolutely need the nested call to complete before we proceed
List tmp = new LinkedList();
for (String s : combinations) {
tmp.add(s + letters.get(0));
}
combinations.addAll(tmp);

System.out.println(combinations);
}



			

java hash table taking in a new node

incoming “guest” — a key-value pair, to be stored. We attach a 3rd item — computed hash code or compressed index — to each guest.

Actually there are other “things” attached to each guest. These tend to distract you when you first study hash tables —

* a pointer. When storing data, we usually store pointers to original data. In Java, Original Keys and Values are always Objects never primitives, so they are always always stored as pointers.

* a bucket id ie the array slot

* a next-pointer since each node is in a linked list

additional space requirement of quicksort

In-place sorting like quicksort has low space requirement. O(log N) space complexity is considered low. I think it’s probably the minimum for comparison-sorts.
Iterative is an alternative to recursive. Iterative lets first call complete before starting 2nd call — no call stack. Recursive is characterized by a deep call stack (of depth log N). Think onion. Think LIFO.
For any resursive sort, you usually need O(s) space where s = stack-depth. Since most (?) well-known divide-and-conquer sorts involve log N divisions and log N nested calls, space complexity is presumably O(log N)?
Now what’s the constant factor in O(log N)? At least the number of local variables defined in the subroutine. Each call on the stack maintains that number of local variables.
“additional” means besides space for the N elements.

a couple of realistic sorting challenges

Update: [[algo in a nutshell]] written by professors, has practical problem-solving suggestions.
——–
Q: what if the storage system holding the long list doesn’t support random access, such as tape?
%%A: read into memory first, by chunk, then merge sort?

Q: what if there are too many items to hold in a computer’s RAM available within our budget? merge sort, but the bucket idea below is better.

Q: what if data is still arriving when we need to start sorting?
%%A: standard merge sort
%%A: if you know data is string and distribution is fairly uniform, you may want to create 26 (or 26+10) trees for A – Z, 0-9 and put incoming data therein. If data rate is too high, you can build 26 queues/circular arrays as the buffer in a producer/consumer pattern.
%%A: even with numeric input, you can do the same provided you know the distribution. In real system, use histogram to estimate the distribution.

I feel this is one case that needs real world experience. Designing a sorter without any idea of distribution is too academic and a waste of time.

bitwise operators, my summary

1 XOR an unknown bit among neighboring bits => TOGGLE the bit

1 AND an unknown bit among neighboring bits => SELECT the bit to examine.

0 AND an unknown bit among neighboring bits => RESET the bit to 0 and ignore it among the neighboring bits

1 OR an unknown bit among neighboring bits => SET the bit to 1

To test equality of 2 “trains” of bits, xor them. 0 means equal.