pavel.em
BAN USER 0of 0 votes
AnswersYou are given a set of functions:
int open_port(); opens a serial port and returns 0 if everything ok (or 1 if error) int read_port(char *buf, int buf_size) which reads data from a serial port and stores it to 'buf' of size 'buf_size' or blocks until the data is available and returns the number of bytes read (or 1 if error occurred) void close_port(); closes a serial port connection
Design a class:
class SerialConnection { public: using ByteHook = std::function<void(char)>; SerialConnection(ByteHook callback); .... };
which should read data from the serial port asynchronously and send it to the callback function ByteHook byte by byte (e.g., for decoding).
 pavel.em in United States
Note that if you don't call 'read_port' often enough, the underlying system buffer might get full and some bytes will get lost..
Which data structures / sync primitives you are going to use ? Report Duplicate  Flag  PURGE
Microsoft Software Engineer Coding  2of 2 votes
AnswersThere is a circular train (the head is connected to the tail) where each car of the train contains a light bulb. Initially, the bulbs are randomly switched on/off.
 pavel.em in Germany
You need to determine the size of the train (the number of cars)
by going from one car to another and switching the light bulbs Report Duplicate  Flag  PURGE
Yandex Software Engineer / Developer Algorithm  0of 0 votes
AnswersHow would you implement an LRU cache using just a *single* container ? i.e., map or unordered_map ?
 pavel.em in United States
The cache must support operations:
1. value_t find(key_t)  find a certain value in cache
2. insert(key_t, value_t)  insert a new value to the cache (with optionally deleting an LRU entry) Report Duplicate  Flag  PURGE
Software Engineer C++  4of 4 votes
AnswersGiven an array of integer nos. All numbers are distinct.
 pavel.em in United States
WAP to find the two longest nonintersecting continuous subarrays
of equal size s.t. *all* elements of one of them are smaller than that of the other subarray:
a[i..i + k  1] and a[j..j+k1] where i + k <= j
s.t. a[i..i + k  1] < a[j..j+k1] or a[i..i + k  1] > a[j..j+k1]
and k is maximal
Example: a = {1,2,3, 7, 9, 8} then we have: {1, 2, 3} and {7, 9, 8}
a = {6, 5, 4, 1, 3, 7} then we have:
{6, 5} and {4, 1} or
{6, 5} and {1, 3} or
{5, 4} and {1, 3} ... Report Duplicate  Flag  PURGE
Microsoft Software Engineer Algorithm  0of 0 votes
AnswersGiven a matrix of size n x m filled with 0's and 1's
 pavel.em in United States
e.g.:
1 1 0 1 0
0 0 0 0 0
0 1 0 0 0
1 0 1 1 0
if the matrix has 1 at (i,j), fill the column j and row i with 1's
i.e., we get:
1 1 1 1 1
1 1 1 1 0
1 1 1 1 1
1 1 1 1 1
complexity: O(n*m) time and O(1) space
NOTE: you are not allowed to store anything except
'0' or '1' in the matrix entries Report Duplicate  Flag  PURGE
Microsoft  0of 0 votes
Answersgiven an array of positive integers A and the numbers N and S. Determine the number subsets of A of size S which sum up to N.
 pavel.em in United States
e.g. A[] = {1,2,5,3,6}
N = 9, S = 3
then we have 2 subsets of size 3: 1+3+5 and 1+2+6 Report Duplicate  Flag  PURGE
Microsoft  0of 0 votes
Answersgiven three strings X, Y and Z. Find all solutions to a numeric puzzle: X + Y = Z where each character in a string corresponds to some digit.
 pavel.em in United States
For simplicity, you may assume that strings are of the same length.
e.g.: X = "abcd", Y = "dbcc", Z = "cdda"
hence we get: 2275 + 5277 = 7552 Report Duplicate  Flag  PURGE
 0of 0 votes
AnswersGiven two binary trees T1 and T2 which store character data, duplicates are allowed. Devise an algorithm to decide whether T2 is a subtree of T1. T1 has millions of nodes and T2 has hundreds of nodes.
 pavel.em in United States Report Duplicate  Flag  PURGE
Microsoft Algorithm  0of 0 votes
Answerstwo arrays a and b of size n+2 and n, resp. The array b is obtained from a by removing two distinct elements, say x and y, and randomly shuffling the remaining ones.
 pavel.em in United States
Given a and b, find the removed elements x and y. Do this in O(n) time and O(1) space. Report Duplicate  Flag  PURGE
Algorithm  0of 0 votes
AnswersCompute the factorial of an integer using minimum number of multiplications. assume no overflows
 pavel.em in United States Report Duplicate  Flag  PURGE
Algorithm  0of 0 votes
AnswersImplement a singleword division:
 pavel.em in United States
i.e., you are given a long integer X having 'n' limbs (32bit words) and you need to divide X by another 32bit int 'b'
optimize your solution for time. Can you do this better if you know that 'b' divides 'X' exactly ?
what if 32bit division on the target architecture is expensive ? try to minimize the # of integer '/' and '%' ops (e.g., using floatingpoint tricks) Report Duplicate  Flag  PURGE
Algorithm  0of 0 votes
AnswersFor those who get bored of sorting/hashing/string manipulation problems, here is the geometric one:
Given n lines in the plane (for simplicity assume no 3 lines intersect at one point). Count the total number of triangles in the plane created by these lines. Observe that smaller triangles may be part of larger ones.
Look here for example:
 pavel.em in United States
h t t p://farm8.staticflickr.com/7021/6465828833_15e7447992_z.jpg Report Duplicate  Flag  PURGE
Microsoft Algorithm  0of 0 votes
Answersconvert a doubleprecision number to rational, i.e.:
 pavel.em in United States
0.125 > 1/8
don't care about arithmetic overflow Report Duplicate  Flag  PURGE
Microsoft Algorithm  0of 0 votes
Answersoutput all dates "Fridays, 13th" in the format dd.mm.yyyy starting from 1st Jan 1900 (Monday)
 pavel.em in United States Report Duplicate  Flag  PURGE
Microsoft Algorithm  0of 0 votes
AnswersGiven a singly linked list with a loop. Find exact location (the element number) where the loop starts. Obviously, using O(1) space (this also means you are not allowed to associate any data with the list elements)
 pavel.em in  Report Duplicate  Flag  PURGE
Microsoft Algorithm  0of 0 votes
Answersgiven a 32bit integer x
find the smallest integer x0 > x
with the same number of ones in binary representation
Example:x = 76 x0 = 81
solution without loops and additional storage ?
 pavel.em in  Report Duplicate  Flag  PURGE
Microsoft Software Engineer / Developer Bit Manipulation  0of 0 votes
Answersgiven a polynomial f(x) of degree n, i.e.:
f(x) = f[n]*x^n + f[n1]*x^[n1] + ... + f[0]
propose an efficient algorithm to computing
the coefficients of g(x) = f(x+1), assume arithemtic overflow cannot occur.
 pavel.em in Example: f(x) = 5*x^2 + 3*x  1 g(x) = f(x+1) = 5*x^2 + 13*x + 7
 Report Duplicate  Flag  PURGE
Microsoft Software Engineer / Developer Algorithm  0of 0 votes
Answerswhat problems do you see in this piece of code (tell without compilation):
 pavel.em
template <class Custom = void>
struct Foo : public Custom {
};
template <>
struct Foo<void> {
template <class X>
struct rebind {
typedef Foo<X> Other;
};
};
template <class Base>
struct Derived : public Base::template rebind <Derived<Base> >::Other {
int foo() {
printf("here we are\n");
};
};
main() {
typedef Foo<> Foo_inst;
typedef Derived<Foo_inst> Derived_inst;
Derived_inst ii;
ii.foo();
} Report Duplicate  Flag  PURGE
Microsoft Software Engineer / Developer C  0of 0 votes
AnswersNow suppose you have 3 eggs and N stories building. If an egg drops from kth floor or about it will break. As before you need to minimize the number of egg drops to find k in the worst case
 pavel.em Report Duplicate  Flag  PURGE
Microsoft Software Engineer / Developer Algorithm
 0 Answers Google SW engineer salaries for PhDs
hello everyone,
 111 June 07, 2012
not sure if it's a right place for this question:
from what I found on the web, Google SW engineer salaries (at mountain view) start from 100k but this is for college graduates. I am wondering how much you can potentially get with a phd ?
thanks Flag  PURGE
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
Your soln is based on the fact that no two producers have the same xcoordinate.
It is quite easy to extend it to the general case: indeed, after sorting the producers by xcoordinate, we can take only the one with the y coordinate closest to 0 and safely ignore all the other "covertical" producers
@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(i1, x1) + P(i1, 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
 pavel.em November 08, 2015@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[i1][N + x1]);
if(x < N)
sum += P[i1][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

pavel.em
November 08, 2015 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]);
}
}

pavel.em
November 04, 2015 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
...

pavel.em
November 03, 2015 @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 zeroout junk column/row !!
if(j == junk_col  i == junk_row)
continue;
A[i][j] &= (A[junk_row][j] & A[i][junk_col]);
}
}
// zeroout 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;
}

pavel.em
October 03, 2015 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 ith 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;
}

pavel.em
October 01, 2015 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 1024byte 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 nonstandard, 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])
{ ...
}

pavel.em
June 15, 2015 this is adapted from unbelievably mindtwisting STL lower/upper bound implemenetations:
void find_bounds(int *a, int n, int val) {
int beg = 0, end = n1;
// 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 = n1;
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);
}

pavel.em
June 15, 2015 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);
}

111
May 06, 2015 PS writethrough 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 writeback cache
 111 February 20, 2013if 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);
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);
}

111
May 24, 2012 this is a modification of "Maximum size square submatrix 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 bottomright 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][j1], S[i1][j]), S[i1][j1]) + 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 = R1; i >= 0; i)
for(j = C1; j >= 0; j) {
if(S[i][j] <= 0)
continue;
printf("%d: size: %d; bottomright: (%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; bottomright: (3; 4)
2: size: 2; bottomright: (3; 1)
3: size: 1; bottomright: (2; 4)
4: size: 1; bottomright: (2; 3)
5: size: 2; bottomright: (2; 1)
6: size: 1; bottomright: (1; 3)
7: size: 1; bottomright: (1; 2)
8: size: 2; bottomright: (1; 1)
9: size: 1; bottomright: (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; bottomright: (4; 4)
2: size: 3; bottomright: (4; 3)
3: size: 2; bottomright: (4; 1)
4: size: 1; bottomright: (1; 3)
5: size: 1; bottomright: (1; 1)
6: size: 1; bottomright: (1; 0)
7: size: 1; bottomright: (0; 4)
8: size: 1; bottomright: (0; 2)
9: size: 1; bottomright: (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 'idx1' (ie the index of the last incoming character)
void add_char(char c) {
// pointers to keep track of odd and evenlength 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[idx1]) {
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;
}

111
May 21, 2012 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
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.
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();
}
}

111
February 06, 2012 // m semaphores (one for each thread)
semaphore sem[m];
// semaphores for all but 0th thread are initially blocked
sem[0].init(1);
sem[1..m1].init(0);
int word_count = 0; // shared variable to keep the no of printed words so far
// parallel code
TID = thread_id(); // TID = 0..m1
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;
}

111
February 05, 2012 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^2b^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;

111
February 05, 2012 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);

111
February 03, 2012 Open Chat in New Window
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
 pavel.em February 14, 2016