CareerCup

I agree with zr.roman, additionally we can speedup the search if we can precompute and store the number of nodes in the left and right subtrees for each node

Once we know the difference btw consecutive elements in the series we could try to sort the array, that is rearranging the elements according to their positions in the arithm series. If we fail to do this, this proves that the array is not sequence

In other words, an element ai goes to the position j = (ai - amin) / diff. That should work in a linear time

gdb firefox coredump

Your soln is based on the fact that no two producers have the same x-coordinate.

It is quite easy to extend it to the general case: indeed, after sorting the producers by x-coordinate, we can take only the one with the y coordinate closest to 0 and safely ignore all the other "covertical" producers

@Iuri Sitinschi: then probably all other solutions based on recursion or non-constant space will error out with out of memory much earlier than this one ;)

there are 32! combinations to print

@haroud,
P[-8] = 1/2 * (P[-7] + P[-9])
while P[-10] = 1/2 * (P[-9] + 0) since P[-11] == 0
Generally, it holds that:

P(i, x) = 1/2* (P(i-1, x-1) + P(i-1, x+1)) if |x| <= i
and P(i, x) = 0 otherwise

since we cannot move more that 'i' points away from the origin in 'i' steps

@emb's solution is correct
And here is a DP solution for those who does not believe in mathematics ;)

void probability() {
	const int N = 10; // number of steps
	float P[N+1][2*N+1]; // P[i][x] - probability to be at position 'x' 
						 // after 'i' steps (-N <= x <= N)
	memset(P, 0, sizeof(P));
	P[0][N + 0] = 1.0f;
	
	int i, x;
	for(i = 1; i <= N; i++) {
		for(x = -i; x <= i; x++) {
			float sum = (x == -N ? 0 : P[i-1][N + x-1]);
			if(x < N)
				sum += P[i-1][N + x+1];
			P[i][N + x] = sum / 2.0f;
		}
	}
	for(x = -N; x <= N; x++) {
		printf("Prob P[%d] = %.6f\n", x, P[N][x + N]);
	}
}

output:

Prob P[-10] = 0.000977
Prob P[-9] = 0.000000
Prob P[-8] = 0.009766
Prob P[-7] = 0.000000
Prob P[-6] = 0.043945
Prob P[-5] = 0.000000
Prob P[-4] = 0.117188
Prob P[-3] = 0.000000
Prob P[-2] = 0.205078
Prob P[-1] = 0.000000
Prob P[0] = 0.246094
Prob P[1] = 0.000000
Prob P[2] = 0.205078
Prob P[3] = 0.000000
Prob P[4] = 0.117188
Prob P[5] = 0.000000
Prob P[6] = 0.043945
Prob P[7] = 0.000000
Prob P[8] = 0.009766
Prob P[9] = 0.000000
Prob P[10] = 0.000977

@JonathanBarOr: no, I was talking about rezakakhki.RK's suggestion
your solution looks correct ;)

@rezakakhki.RK: I have also thought something about these lines. But the point is there is really *no way* to know when "no more turned-on light remain". So that we can go on in circles indefinetely

yes, you are right. This solution is based on Dijkstra's algorithm from "a discipline of programming".

Here is a basic version for 2 primes to help understanding the idea:

void print23() {
	// print 2^i*3^j increasing order
	int a[100];
	a[0] = 1;

  int i2 = 0, i3 = 0;
  for(int i = 1; i < 100; i++) {
    int a2 = a[i2] * 2, a3 = a[i3] * 3;
    if(a2 < a3) {
        a[i] = a2;
        i2++;
    } else {
        a[i] = a3;
        i3++;
        if(a2 == a3)
            i2++; // inc both indices in case of a tie
    }
    printf("%d ", a[i]);
  }
}

my solution below works in O(N * #of primes) time

here is O(N * #of primes) solution:

void num_generator() {
    int a[] = {2, 3, 7, 11};
    int as = sizeof(a) / sizeof(int);

    int *idx = new int[as];
    int *min_idx = new int[as];
    memset(idx, 0, sizeof(int)*as);
    
    int n = 100;
    int *x = new int[n];
    x[0] = 1;

    int i, j;
    for(i = 1; i < n; i++) {
        int min = x[idx[0]] * a[0], 
               nmins = 1; // # of primes giving the current minimal 
        min_idx[0] = 0;
        
        // iterate over prime factors: search for the minimal next number
        for(j = 1; j < as; j++) { 
            int xj = x[idx[j]] * a[j];
            if(xj <= min) {
                if(xj < min) {
                    min = xj;
                    nmins = 0;
                }
                // save a prime index giving the minimal next number
                min_idx[nmins++] = j;
            }
        }

        x[i] = min;
        for(j = 0; j < nmins; j++) {
            idx[min_idx[j]]++;
        }
        
        printf("x[%d] = %d\n", i, x[i]);
    }
    delete []x;
    delete []idx;
    delete []min_idx;
}

the output:

x[1] = 2
x[2] = 3
x[3] = 4
x[4] = 6
x[5] = 7
x[6] = 8
x[7] = 9
x[8] = 11
x[9] = 12
x[10] = 14
x[11] = 16
x[12] = 18
x[13] = 21
x[14] = 22
x[15] = 24
x[16] = 27
x[17] = 28
x[18] = 32
x[19] = 33
x[20] = 36
x[21] = 42
x[22] = 44
x[23] = 48
x[24] = 49
x[25] = 54
x[26] = 56
x[27] = 63
x[28] = 64
x[29] = 66
x[30] = 72
x[31] = 77
x[32] = 81
x[33] = 84
x[34] = 88
x[35] = 96
x[36] = 98
x[37] = 99
x[38] = 108
x[39] = 112
x[40] = 121
x[41] = 126
x[42] = 128
x[43] = 132
x[44] = 144
x[45] = 147
x[46] = 154
x[47] = 162
x[48] = 168
x[49] = 176
x[50] = 189
x[51] = 192
x[52] = 196
x[53] = 198
x[54] = 216
x[55] = 224
x[56] = 231
x[57] = 242
x[58] = 243
x[59] = 252
x[60] = 256
x[61] = 264
x[62] = 288
x[63] = 294
x[64] = 297
x[65] = 308
x[66] = 324
x[67] = 336
x[68] = 343
x[69] = 352
x[70] = 363
x[71] = 378
x[72] = 384
x[73] = 392
...

the formula is what @SK wrote below, i.e.: C(M + N, N) or C(M + N, M)

But apparently the problem is underdefined: it does not say that we can move only down and right. Otherwise, the number of ways is infinity ! (loops)

If I understand it correctly, a dot-product of two subarrays {a,b,c} and {d,e,f}
would be: a*d + b*e + c*f. So I think your algorithm is computing something else.

Indeed, why would the question mention (+ve & -ve) number if the signedness does not matter ?

@SK, these are combinations, i.e., C(M + N, N) or C(M + N, M)

indeed, since the order of instructions of one program is fixed, we denote
by 0's the instructions of the 1st program and by 1's - the instructions of the 2nd
Hence the problem reduces to computing the # of ways how to set M ones having M+N places which is combinations.

Example: M = 3, N = 2.
11100 -> Ma Mb Mc Na Nb
01101 -> Na Ma Mb Nb Mc
... etc

If we have O(1) space, I only came up with the solution using 2 passes (can it be improved ?)

the basic idea is: we need to choose some "junk" row and column to save the locations
of 0s in them. These junk row/col can be any that will be zeroed out anyway. Then in the 2nd pass, we just go over the whole matrix once again and zero out elements based on 0 pattern in our "junk" row/col:

#define NROWS 5
#define NCOLS 5

int A[NROWS][NCOLS] = {
    {1,1,1,0,1},
    {1,1,0,1,1},
    {1,1,1,1,1},
    {1,0,1,0,1},
    {1,1,1,1,1}};
    
void print_matrix() {
    printf("A = \n");
    for(int i = 0; i < NROWS; i++) {
        for(int j = 0; j < NCOLS; j++){
            printf("%d ", A[i][j]);
        }
        printf("\n");
    }
    printf("\n\n");
}
    
void compute() {
    // these row/col will be used to keep track of zeros in the matrix
    int junk_row = -1,
        junk_col = -1;
    
    for(int i = 0; i < NROWS; i++) {
        for(int j = 0; j < NCOLS; j++) {
            if(A[i][j] == 0) {
                // choose our junk row/col if they are not set yet
                if(junk_row == -1) {
                    junk_row = i;
                    junk_col = j;
                }
                // set markers where we need to zero out
                A[junk_row][j] = 0;
                A[i][junk_col] = 0;
            }
        }
    }

    if(junk_row != -1) {
        for(int i = 0; i < NROWS; i++) {
            for(int j = 0; j < NCOLS; j++) {
                // do not zero-out junk column/row !!
                if(j == junk_col || i == junk_row)
                    continue;
                A[i][j] &= (A[junk_row][j] & A[i][junk_col]);
            }
        }    
        // zero-out junk column/row
        for(int i = 0; i < NROWS; i++) 
            A[i][junk_col] = 0;
        for(int j = 0; j < NCOLS; j++) 
            A[junk_row][j] = 0;
    }
}


int main() {
    print_matrix();
    compute();
    print_matrix();
    return 1;
}

small correction:
if slope equals zero, this just indicates a vertical line
(anyway comparison of 'double' with 0 usually a bad thing)

So you should define a line as a triple: a*x + b*y + c = 0
where

a = (y2-y1), b = (x1 - x2) and c = (x2*y1 - x1*y2)

should be smth like this:

class Base {                 // base class for wrapper classes
    public:
      virtual ~Base() {}
};

template <class T>           // generic wrapper class
class Wrapper : public Base {  
    T object;
public:
    Wrapper(const T& obj) : object(obj) {
	}
	Wrapper(T&& obj) : object(std::move(obj)) {
	}
	
    Wrapper() {}
    operator T() { return object; }
};

class Collection {             
    std::vector < std::unique_ptr< Base >> v;
public:

	Collection() {}
	
	template < class T >
	void insert(const T& t) {
		v.push_back(std::unique_ptr< Base >(new Wrapper<T>(t)));
	}
	
	template < class T >
	void insert(T&& t) {
		using T2 = typename std::remove_reference<T>::type;
		v.emplace_back(new Wrapper< T2 >(std::forward<T>(t)));
	}
    
	// try to convert an i-th object to type 'T'
	template < class T >
	bool assign(T& t, unsigned idx) {
		if(idx >= v.size())
			return false;
		Wrapper<T>*  wp = dynamic_cast<Wrapper<T>*>(v[idx].get());
		if (wp == 0)
			return false;
		t = *wp;
		return true;
	}
};

struct YOYO {
};

int main(int argc, char* argv[]) {

	Collection c;
	YOYO yoyo;
	int aaa = 2;
	std::string xxx("123123");
	c.insert(12);
	c.insert(yoyo);
	c.insert(YOYO());
	c.insert(std::string("123123"));
	c.insert(xxx);
	
	int aaa;
	if(c.assign(aaa, 0)) {
		std::cerr << "got x value = " << aaa << "\n";
	}
	if(c.assign(yoyo, 2)) {
		std::cerr << "got YOYO value\n";
	}
	return 0;
}

1. you do not handle the situation when malloc returns NULL pointer
2. allocating (sizeInBytes + alignment) bytes right at the beginning could be inefficient if alignment is large. Suppose, sizeInBytes = 1024 and alignment = 1024. Then you'll waste 1024 bytes! While, it's quite likely that malloc already allocates an 1024-byte aligned chunk in this case.

Therefore, it probably makes sense:
- use some memory pool for allocations (to save on fragmentation)
- first issue 'malloc' with original size. Then if it's not properly aligned (or if the alignment is non-standard, e.g., like 127 bytes), use realloc with 'bytes + alignment' size

I guess you dont even need an additional space, i.e., maintain the two indices:
min_so_far computed from right to left in the orig. array
and
max_so_far computed from left to right

then in the loop you need to increment one of the indices to ensure that at any moment: a[min_so_far] <= a[max_so_far] until they meet at some point:

while(a[min_so_far]  <= a[max_so_far])
{  ...
}

this is a classical greedy algorithm on finding the largest set of nonoverlapping intervals

this is adapted from unbelievably mind-twisting STL lower/upper bound implemenetations:

void find_bounds(int *a, int n, int val) {
    
    int beg = 0, end = n-1;
    // searching upper bound
    while(beg < end) {
        int mid = (beg + end)/2;
        if(!(val<a[mid])) {
            beg = mid+1;
        } else {
            end = mid;
        }
    }
    int upper_bnd = beg;
    
    beg = 0, end = n-1;
    while(beg < end) {
        int mid = (beg + end)/2;
        if(a[mid] < val) {
            beg = mid+1;
        } else {
            end = mid;
        }
    }
    int lower_bnd = beg;
    
    printf("[%d; %d]\n", lower_bnd, upper_bnd);
}

please forget my previous comment

that's not working otherwise you would create a max heap with insert operation O(1)

what happens if you wish to read more data that is stored on your disk ?
will ReadFromDisk() just report some error or will it silently wrap around ?

Suppose, we are allowed to precompute & strore some info in the tree data struct.
Once done, we can handle many queries with O(logN) time.
We precompute the # of inorder successors for each node. This could be done
with postorder traversal:

struct node {
    int val;        // BST value
    int sum;        // # of inorder successors
    node *left;     // children
    node *right;
};

// returns # nodes in a subtree
//! for each node compute the number of inorder successors in the tree
int inorder_sum(node *x, int right_sum) {

    if(x == 0)
        return 0;
    int tmp = inorder_sum(x->right, right_sum);
    x->sum = tmp + 1 + right_sum;

    tmp += inorder_sum(x->left, x->sum);
    return tmp + 1;
}

inorder_sum(root, 0);

Then, for each "range query" we just need to find 2
nodes 'xleft' and 'xright' that mark the boundaries of the given interval [vmin; vmax]:

node *xleft = 0, *xright = 0;

void find_subtree(node *x, int vmin, int vmax) {

    if(x == 0)
        return;
    
    if(vmin <= x->val && x->val <= vmax) {
        // we know that this node lies within the interval =>
        // could improve the bounds if needed
        if(xleft == 0 || xleft->val > x->val)
            xleft = x;
            
        if(xright == 0 || xright->val < x->val)
            xright = x;
        
        find_subtree(x->left, vmin, x->val);
        find_subtree(x->right, x->val, vmax);
        
    } else if(x->val > vmax) { // no need to explore right subtree
        
        find_subtree(x->left, vmin, vmax);
    
    } else { // x->val < vmin => no need to expolore left subtree
        find_subtree(x->right, vmin, vmax);
    }
}

find_subtree(root, vmin, vmax);

if(xleft != 0 && xright != 0) {
     printf("# of nodes: %d\n",  
            xleft->sum - xright->sum + 1);
}

+1, use monte carlo algorithm,e.g. for pi computation

PS write-through cache is benefitial when moving large amounts of data from one place to another. If there is no cache hit on memory write, the data will be written directly to the backstore without preloading the corresponding cache line first. Hence that cache won't get "dirtied" as it would be the case for write-back cache

if it's really about the space, you can just store coordinates of the head and the rest of the snake store as a linked list containing the 2bit flag: UP/DOWN/LEFT/RIGHT

then, when you move the head up, you need to calculate a new position of each "limb" of the snake starting from the head and going down to the tail. Then if it happens that the new position of the head coincides with that of one of the limbs, game is over..Otherwise, you just update 2bit flags in your linked list according to new positions

the algo is very similar to the DP approach to inserting characters in
"thisisawesome".

dict[i][j] = true if str[i..j] is in the dictionary
word[i][j] = dict[i][j] OR (word[i][k] AND word[k+1][j] for some k)

the only difference is that words' characters are permuted. Thus we need another way to decide if str[i..j is in the dictionary

for that we use hash of size 26 to count and comparr the # of different chars in a dictionary word and in str[i..j]

ex.: str[i..j] = "omse" dict[k] = "some". Compare the no of diff chars to decide if str[i..j] is a permutation of dict[k]

use all available mem on the machine to store a very very large integer.
Then, starting from 0, increment this integer by 1 in each loop iteration until
we get 0xfffffff ... ffffffff at the end

as an example, if you use 4 words to represent an int,
incrementing by one can be realized as follows:

int w[4];
w[0] += 1;
w[1] += (w[0] == 0);
w[2] += (w[1] == 0);
w[3] += (w[2] == 0);

but the size of you hash is O(n) while there is a space restriction O(height of the tree)

I thought for this question for quite a while.. you probably right that there is no universal solution in O(n) time and O(1) space.

Yet the number of different combinations to try is practically infinite: for example, you can take sums modulo 2^n (to prevent overflow) combined with inverse grey code, popcount, bitreversal, etc. Besides there is a number of cryptographic hash functions like MD5 checksums that can be computed in O(n) time.. this would give a correct answer with high probability.

So my point is proving that O(n) time O(1) space is not possible in general is not easy while the reverse is also true..

@maverick you approach has a flaw:
suppose p1->data > p2->data but p1 has no left child than your algo will print p1->data
before p2->data which is obviously incorrect. However I find your idea quite original.. and tried to develop it further. I tested my approach on a number of examples, it seems to work fine. The pseudocode is below. Counterexamples are welcome)

struct node {
    int val;
    node *left;
    node *right;
};

node *append(node *parent, int which, int val) {
    node *x = new node;
    x->left = x->right = 0;
    x->val = val;
    //
    if(parent != 0) {
        if(which == 0)
            parent->left = x;
        else
            parent->right = x;
    }
    return x;
}

void traverse(node *t1, node *t2) {
    //
    if(t2 == 0) {
        if(t1 == 0)
            return;
        traverse(t1->left, 0);
        printf("%d ", t1->val);
        traverse(t1->right, 0);
        return;
    }
    //
    if(t1 == 0) {
        traverse(0, t2->left);
        printf("%d ", t2->val);
        traverse(0, t2->right);
        return;
    }
    //
    traverse(t1->left, t2->left);
    if(t1->val >= t2->val) {
        printf("%d ", t2->val);
        node *s = t1->left;
        t1->left = 0;
        traverse(t1, t2->right);
        t1->left = s;
    } else {
        printf("%d ", t1->val);
        node *s = t2->left;
        t2->left = 0;
        traverse(t1->right, t2);
        t2->left = s;
    }
}

void destroy_tree(node *root) {
    //
    if(root == 0)
        return;
    destroy_tree(root->left);
    destroy_tree(root->right);
    delete root;
}

int main(){
    node *x, *y;
    node *head = append(0, 0, 10);
    node *l = append(head, 0, 5),
         *r = append(head, 1, 25),
         *ll = append(l, 0, 3),
         *lr = append(l, 1, 7);
    append(lr, 0, 6);
    //
    node *head2 = append(0, 0, 7);
    l = append(head2, 0, 6);
    r = append(head2, 1, 11);
    ll = append(l, 0, 1);
    node *rr = append(r, 0, 9);
    traverse(head, head2);
    //
    destroy_tree(head);
    destroy_tree(head2);
}

huh you are right eugene, there is inherent problem with this approach when palindromes are multiply included in one another.. seems that this is not a trivial problem as it stands ))

@algogeek: you are right, for that matter I use a flag 'same_char' which remains 'true' until we get the first non-repeating character from the stream. please see the modified code

this is a modification of "Maximum size square sub-matrix with all 1s" DP problem
from www dot geeksforgeeks.org/archives/6257

In the pseudocode, S[i][j] is a size of the maximum square submatrix with all 1s with bottom-right corner (i;j). After computing S[i][j], we only need to remove those squares which are completely contained in large squares

#define R 6
#define C 5

int S[R][C];
int M[R][C] =  {
    {0, 1, 1, 0, 1},
    {1, 1, 0, 1, 0},
    {0, 1, 1, 1, 0},
    {1, 1, 1, 1, 0},
    {1, 1, 1, 1, 1},
    {0, 0, 0, 0, 0}};

void fillin(int r1, int c1) { // mark overlapping squares
    int sz = S[r1][c1], i, j;
    int r0 = r1 - sz + 1, c0 = c1 - sz + 1;
    for(i = r0; i <= r1; i++)
    for(j = c0; j <= c1; j++) {
        int s = S[i][j];
        if(i - s + 1 >= r0 && j - s + 1 >= c0)
           S[i][j] = 0;
    }
}

void printMaxSubSquare()
{
  int i,j;
  int max_of_s, max_i, max_j;
  /* Set first column of S[][]*/
  for(i = 0; i < R; i++)
     S[i][0] = M[i][0];
  /* Set first row of S[][]*/
  for(j = 0; j < C; j++)
     S[0][j] = M[0][j];
  /* Construct other entries of S[][]*/
  for(i = 1; i < R; i++)
  {
    for(j = 1; j < C; j++)
    {
      if(M[i][j] == 1)
        S[i][j] = std::min(std::min(S[i][j-1], S[i-1][j]), S[i-1][j-1]) + 1;
      else
        S[i][j] = 0;
    }
  }
    printf("Input:\n");
      for(i = 0; i < R; i++) {
    for(j = 0; j < C; j++) {
        printf("%d ", M[i][j]);
    }
    printf("\n\n");
    }
    int cnt = 0;
    for(i = R-1; i >= 0; i--)
    for(j = C-1; j >= 0; j--) {
        if(S[i][j] <= 0)
            continue;
        printf("%d: size: %d; bottom-right: (%d; %d)\n", ++cnt, S[i][j], i, j);
        fillin(i, j);
    }
    printf("\n");
}

int main()  {
   printMaxSubSquare();
}

some results:
Input:
1 1 0 0 1
1 1 1 1 0
1 1 0 1 1
1 1 0 0 1

1: size: 1; bottom-right: (3; 4)
2: size: 2; bottom-right: (3; 1)
3: size: 1; bottom-right: (2; 4)
4: size: 1; bottom-right: (2; 3)
5: size: 2; bottom-right: (2; 1)
6: size: 1; bottom-right: (1; 3)
7: size: 1; bottom-right: (1; 2)
8: size: 2; bottom-right: (1; 1)
9: size: 1; bottom-right: (0; 4)


Input:
0 1 1 0 1
1 1 0 1 0
0 1 1 1 0
1 1 1 1 0
1 1 1 1 1
0 0 0 0 0

1: size: 1; bottom-right: (4; 4)
2: size: 3; bottom-right: (4; 3)
3: size: 2; bottom-right: (4; 1)
4: size: 1; bottom-right: (1; 3)
5: size: 1; bottom-right: (1; 1)
6: size: 1; bottom-right: (1; 0)
7: size: 1; bottom-right: (0; 4)
8: size: 1; bottom-right: (0; 2)
9: size: 1; bottom-right: (0; 1)

logic is quite simple: in any given moment of time stream[cmp_pos] must match with the next incoming character stream[idx] to grow a current palindrome sequence. When 'cmp_pos' descends below 0, this indicates that we found a palindrome seq.

if stream[cmp_pos] does not match with stream[idx], we reset
cmp_pos either to 'idx' or 'idx-1' (ie the index of the last incoming character)

void add_char(char c) {
    // pointers to keep track of odd and even-length palindromes
    static int odd = 0, even = -1;
    static int idx = 0;     // current position in the stream
    static char stream[256];
    static bool same_char = true;
    stream[idx] = c;
    stream[idx+1] = '\0';

    if(same_char && idx > 0 && c != stream[idx-1]) {
        same_char = false;
    }
    if(same_char) 
        printf("palindrome: %s\n", stream);
    
    if(odd >= 0 && stream[odd] == c) {
        odd--;
        if(odd < 0) {
            printf("odd palindrome: %s\n", stream);
            odd = idx - 1;
        }
    } else
        odd = idx - 1;
    if(even >= 0 && stream[even] == c) {
        even--;
        if(even < 0) {
            printf("even palindrome: %s\n", stream);
            even = idx;
        }
    } else
        even = idx;
    idx++;
}

int main() {
    const char *s = "aaaaaabaaaaaa"; 
    for(int i = 0; s[i] != 0; i++)
        add_char(s[i]);
    return 0;
}

you are right, the only requirement is that one character maps to *one* digit but it is not necessary that one digit corresponds to one character.

This is a quite natural thing to assume because there are more characters (26) than digits (10). Otherwise some puzzles would not be solvable

sorry for confusion, I mean print all integer partitions of a given number in odd parts (not compositions, i.e. order does not matter).

for example, given n = 8:
we have 8 = 7 + 1, 8 = 5 + 3, etc.

good one, I agree on that: locks should be acquired in a particular order for *all* threads to prevent deadlocks.

btw, another common "deadlock pattern" is waiting on a semaphore while holding a mutex, e.g. consider the following:

thread1:
mutex.lock();
sem.wait();
// do some work
mutex.unlock();

thread2:
mutex.lock();
sem.signal();
mutex.unlock();

suppose semaphone 'sem' is initially set to '0'.
Then depending on the order of execution of threads,
it might happen that thread 1 acquires mutex first and hence the semaphore will never be signalled..

I suppose this solution is correct: ie. do simple bruteforce
approach (recursive), and count the number of runs
in each step. We do not need to explore the paths where the # of runs is greater than M.

here is the code, please correct me if I am wrong:

int total_count = 0;
int N = 5, M = 2, K = 6, L = 1;
std::vector< int > seq;

// n_placed: number of digits in a sequence being placed
// n_last: last digit placed (for comparison)
// n_runs: # of runs counted so far
// dir: current direction: decreasing(0), increasing(1) or undefined(-1)
void count_sequences(int n_placed, int n_last, int n_runs, int dir) {
    seq.push_back(n_last);
    if(n_placed == N) {
        if(n_runs == M) {
            total_count++;
            printf("%d: ", total_count);
            for(typeof(seq.begin()) i = seq.begin(); i != seq.end(); i++) {
                printf("%d ", *i);
            }
            printf("\n");
        }
        seq.pop_back();
        return;
    }
    
    for(int i = 1; i <= K; i++) {
        int diff = i - n_last;
        // difference between adjacent elements is too large
        if(ABS(diff) > L)
            continue;
        
        if(diff == 0) { // duplicate element: break the current sequence
            // have enough runs: no need to explore this path
            if(n_runs == M) 
                continue;
            count_sequences(n_placed+1, i, n_runs+1, -1);
        } else if(diff < 0) {
            if(dir == -1) { // start a new decreasing sequence
                count_sequences(n_placed+1, i, n_runs, 0);
            // current sequence is decreasing: continue this sequence
            } else if(dir == 0) {
                count_sequences(n_placed+1, i, n_runs, 0);
            // current sequence is increasing: break it
            } else { // dir == 1
                if(n_runs == M) // have enough runs already
                    continue;
                count_sequences(n_placed+1, i, n_runs+1, 0);
            }
        } else { // diff > 0

            if(dir == -1) { // start a new increasing sequence
                count_sequences(n_placed+1, i, n_runs, 1);
            // current sequence is increasing: continue this sequence
            } else if(dir == 1) {
                count_sequences(n_placed+1, i, n_runs, 1);
            // current sequence is decreasing: break it
            } else { // dir == 0
                if(n_runs == M) // have enough runs already
                    continue;
                count_sequences(n_placed+1, i, n_runs+1, 1);
            }
        }
    }
    seq.pop_back(); // pop the current element
}

int main() {
    for(int i = 1; i <= K; i++) {
        count_sequences(1, i, 1, -1);
    }
    return 1;
}

e.g., for N = 5, M = 2, K = 6, L = 1 we get:

1: 1 1 2 3 4
2: 1 2 2 3 4
3: 1 2 3 2 1
4: 1 2 3 3 2
5: 1 2 3 3 4
6: 1 2 3 4 3
7: 1 2 3 4 4
8: 2 1 1 2 3
9: 2 1 2 3 4
10: 2 2 3 4 5
11: 2 3 3 2 1
12: 2 3 3 4 5
13: 2 3 4 3 2
14: 2 3 4 4 3
15: 2 3 4 4 5
16: 2 3 4 5 4
17: 2 3 4 5 5
18: 3 2 1 1 2
19: 3 2 1 2 3
20: 3 2 2 3 4
21: 3 2 3 4 5
22: 3 3 4 5 6
23: 3 4 3 2 1
24: 3 4 4 3 2
25: 3 4 4 5 6
26: 3 4 5 4 3
27: 3 4 5 5 4
28: 3 4 5 5 6
29: 3 4 5 6 5
30: 3 4 5 6 6
31: 4 3 2 1 1
32: 4 3 2 1 2
33: 4 3 2 2 1
34: 4 3 2 2 3
35: 4 3 2 3 4
36: 4 3 3 2 1
37: 4 3 3 4 5
38: 4 3 4 5 6
39: 4 4 3 2 1
40: 4 5 4 3 2
41: 4 5 5 4 3
42: 4 5 6 5 4
43: 4 5 6 6 5
44: 5 4 3 2 2
45: 5 4 3 2 3
46: 5 4 3 3 2
47: 5 4 3 3 4
48: 5 4 3 4 5
49: 5 4 4 3 2
50: 5 4 4 5 6
51: 5 5 4 3 2
52: 5 6 5 4 3
53: 5 6 6 5 4
54: 6 5 4 3 3
55: 6 5 4 3 4
56: 6 5 4 4 3
57: 6 5 4 4 5
58: 6 5 4 5 6
59: 6 5 5 4 3
60: 6 6 5 4 3

if I get it correctly, this algo can still miss some solutions:
Ie. consider {2, 5, -6, 3, 7}
after the first pass you'd have: max_start = 0, max_end = 4, maxv = 11. And the second pass is not executed since range(max_start) = 0. While the correct answer should be: 17.

well, the idea is correct but it's not going to work that easy: Remember the numbers are written on a *circle*.
while Kadane's algo just computes a maximal contiguous subsequence. How'd handle when you subsequence wraps around ?

so in other words he wanted you to implement multi-precision arithmetic ?
it's not very hard to multiply two nos using schoolbook method, but there is certainly some technical hurdle..

you should've referred him to GNU multiprecision lib, ie gmplib.org ))

Aren't you assuming that there is a parent pointer for each node ?

if it's not the case, the following soln works:

char pre_order[];
int sz = sizeof(pre_order);
stack<node *> S;

note *root, *parent = 0;
for(int idx = 0; idx < sz; idx++) {
    node *t = new node;
    if(parent != 0) {
        if(parent->left == 0)
            parent->left = t;
        else
            parent->right = t;
    } else {
        root = t;
    }
    if(pre_order[idx] == 'N') {
        parent = t;
        S.push(t);
    } else if(!S.empty()) 
        parent = S.pop();
    }
}

// m semaphores (one for each thread)
semaphore sem[m];
// semaphores for all but 0th thread are initially blocked
sem[0].init(1);  
sem[1..m-1].init(0);
int word_count = 0;    // shared variable to keep the no of printed words so far

// parallel code
TID = thread_id(); // TID = 0..m-1
while(1) {
    sem[TID].wait(); // wait on semaphore
    if(word_count < n) {   // this code is guaranteed to execute by one thread
        print(word[word_count]); // hence no need for critical section
        word_count++;
    }
    sem[(TID+1)%m].signal(); // signal the next thread in a chain
    if(word_count == n)    // exit gracefully when all words are printed
        break;
}

if overflows is a concern, I propose the following soln:

1. calculate the sum of nos and subtract it from N*(N+1)/2
2. calculate the sum of squares and subtract it from
N*(N+1)*(2N+1)/6.

this gives us two equations of the form:
a - b = X
a^2-b^2 = Y
from which the missing no can be easily found, the code is below:

int a[] = {2,1,3,4,8,6,7,8,9,10};
    int N = 10;
    int sum = 0, sum_sq = 0;
    for(int i = 0; i < N; i++) {
        sum += a[i];
        sum_sq += a[i]*a[i];
    }
    int true_sum = N*(N+1)/2,
        true_sum_sq = N*(N+1)*(2*N+1)/6;
    int X = true_sum - sum,
        Y = true_sum_sq - sum_sq;
    int missing = (Y / X + X) / 2;

I suppose the idea was to do this in a single traversal and without additional space to save the tree nodes. Though i agree that the above solution is easier.

alternatively it can be done as follows:

void fill_inorder_succ(node *t, node *remote_parent) {
    if(t == 0)
        return;
    if(t->right != 0) {
        t->next = leftmost_child(t->right);
        find_inorder_suff(t->right, remote_parent);
    } else
        t->next = remote_parent;
    fill_inorder_succ(t->left, t);
}
fill_inorder_succ(root, 0);