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
just to add more explanations: containment is used when the outer object needs to modify the behaviour of the inner object.
for the second part of the question: when the outer object dies, the contained inner object is also destroyed (since its not exposed to the outer world)
while in case of aggregation, it's not necessarily true:
you just decrease a reference counter since same object can be aggregated by other objects as well
the point is we need to associate the coefficients at equal powers of 'x' of both polynomials. Suppose the input polynomials are given as maps:
'coeffs_f' and 'coeffs_g' of the form:
monomial_degree > coefficient
then polynomial addition can be done as follows:
// loop through all nonzero monomials of 'f'
foreach idx from coeffs_f do
res[idx] = coeffs[idx]
if coeffs_g.find(idx) then
res[idx] += coeffs_g[idx];
*mark* coeffs_g[idx]
end if
end do
// loop through the remaining nonzero monomials of 'g'
foreach idx from coeffs_g do
// skip if coeffs_g[idx] is already there
if *marked* coeffs_g[idx] then continue
res[idx] += coeffs_g[idx];
end do
Additionally, using a map is more convenient because with a linked list you do not have direct access to polynomial coefficients (need to scan the whole list first)
Abhishek is actually right: this technique is called "binary splitting": imagine if you wish to compute factorial of a large number, then performing arithmetic on balanced operands (ie of comparable size) is more efficient than computing x! in a usual way
also to give a hint how to reduce the # of muls, observe that we can remove the poweroftwo factors from the factorial expression and combine the remaining ones according to multiplicity:
e.g.: 10! = 2^8 * ( 1 * 3 * 1 * 5 * 3 * 7 * 1 * 9 * 5) =
2^8 * (3 * 5)^2 * 7 * 9
hence we need to perform 4 multiplications instead of 8..
when a matrix is nonsquare, we might run into loops when swapping the elements..
the following soln works:
1. assume matrix is stored as 1D array
2. for each element in the resulting (transposed) matrix, say its index is 'k', find the index of a corresponding element in the original matrix, say it's 'j'
3. if j > k then swap(a[j], a[k])
4. otherwise we should "follow the loop" since element in the location 'j' has
already been swapped
I hope my obscure explanations are understandable ))
here is the code:
// in: n rows; m cols
// out: n cols; m rows
void matrix_transpose(int *a, int n, int m) {
int i, j;
printf("\nin: %d x %d\n", n, m);
for(i = 0; i < n; i++) {
for(j = 0; j < m; j++)
printf("%d ", a[i*m + j]);
printf("\n");
}
for(int k = 0; k < n*m; k++) {
int idx = k;
do { // calculate index in the original array
idx = (idx % n) * m + (idx / n);
} while(idx < k);
std::swap(a[k], a[idx]);
}
printf("\nout: %d x %d\n", m, n);
for(i = 0; i < m; i++) {
for(j = 0; j < n; j++)
printf("%d ", a[i*n + j]);
printf("\n");
}
}
int main() {
int n = 2, m = 8; // n rows, m cols
int a[] = {1,1,1,1, 2,2,2,2, 3,3,3,3, 4,4,4,4};
matrix_transpose(a, n, m);
return 1;
}

111
January 28, 2012 preliminary version:
there is a onetoone correspondence between kpermutations of 'n' elements and falling factorial (FF) numbers with 'n1' digits
where only 'k' leading digits can be nonzero.
For example, an FFnumber X with 5
digits {a0, a1, a2, a3, a4} is defined as:
X = a0 + 5*a1 + 5*4*a2 + 5*4*3*a3 + 5*4*3*2*a4
subject to conditions:
a0 < 5, a1 < 4, a2 < 3, a3 < 2, a4 < 1
or, equivalently, this is a number in a mixed radix system where
the base vector is given by [5, 4, 3, 2, 1]
Then, to convert a permutation of 'n' elements to an FFnumber,
we do the following:
for each element a[i] of a permutation (except the last one) count the number of elements
with indices to the right of 'i' that are less
than a[i]
Example (permutations of 5 elements):
permutation > FFnumber
[5 3 2 1 4] > [4 2 1 0]
[1 2 5 3 4] > [0 0 2 0]
[2 4 3 5 1] > [1 2 1 1] etc.
Now, suppose we wish to generate 3permutations of [1 2 3 4 5 6]
in lexicographical order. For this we consider all FFnumbers with 5 digits
for which *only 3 leading digits can be nonzero*
We start with: [0 0 0 0 0] which corresponds to the first permutation:
[1 2 3 4 5 6] taking a length3 prefix of the latter one yields [1 2 3]
and continue in this way:
FFnumber > [3permutation][remaining part]
[0 0 0 0 0] > [1 2 3][4 5 6]
[0 0 1 0 0] > [1 2 4][3 5 6]
...
[2 1 2 0 0] > [3 2 5][1 4 6]
[2 1 3 0 0] > [3 2 6][1 5 6]
[2 2 0 0 0] > [3 4 1][2 5 6]
...
[5 4 2 0 0] > [6 5 3][1 2 4]
[5 4 3 0 0] > [6 5 4][1 2 3]

111
December 19, 2011 yeah that's what I mean: C(n,k) denotes the number of ways to choose a subset of 'k' elements out of 'n'
I can only show it on an example..
Suppose we have n = 5 and k = 3. Than we can encode any solution
of the above system as a particular subset of 5 elements out of 7
in the following way:
5 = 4 + 1 + 0 > 1111010
5 = 2 + 2 + 1 > 1101101
5 = 3 + 2 + 0 > 1110110
5 = 1 + 1 + 3 > 1010111
5 = 1 + 0 + 4 > 1001111
5 = 0 + 5 + 0 > 0111110
and so on, thus it should give C(n+k1,n) eventually
ps. your recurrence is definitely correct, it's easy to check
@Achintya: just to develop your idea further
1. remove integral part
2. use two arrays 'col_sums' and 'row_sums' to keep the sums of fractional parts along each column and row, resp.
in your example above:
row_sums = [1, 1, 2]
col_sums = [2, 1, 1]
now the problem reduces to finding a matrix A[i][j] of 0's and 1's where the column and row sums agree with the above arrays. There are many solutions possible.
For our example, we might have:
1 0 0 = 1
1 0 0 = 1
0 1 1 = 2

2 1 1
or
0 1 0 = 1
1 0 0 = 1
1 0 1 = 2

2 1 1
and so on. In fact we can put 1 at any position in the matrix as long as the row/col sums are preserved.
To make a deterministic algorithm out of this, we can use the following simple procedure (A[i][j] is the resulting matrix):
for(i = 0; i < n; i++) { // process each row
for(j = 0; j < row_sums[i]; ) { // place required # of 1's in row 'i'
if(col_sums[j] == 0) // all "slots" in this column are occupied
continue;
A[i][j] = 1;
col_sums[j]; j++;
}

111
December 18, 2011 the number of subsets of [1..n] whose sum is 's'
is given by the coefficient of x^s in the polynomial:
F:=(1+x)*(1+x^2)*...*(1+x^n).
Example: n = 5
F:= 1+3*x^5+2*x^4+3*x^9+2*x^3+3*x^8+
3*x^7+2*x^12+x^2+3*x^6+2*x^11+3*x^10+x^14+x+x^13+x^15
thus the # of subsets which
sum up to 3 is 2 (because F has a term 2*x^3)
sum up to 7 is 3 (F has a term 3*x^7)
sum up to 13 is 1 (F has a term x^13)
and so on..
we can compute the coeffs of F using 'shiftandadd'
approach, that is, start from (x + 1)
then shift this by 2 positions to the right and sum up
with the original coeffs: which is the same as multiplication by (x^2 + 1), and so on
I think it's not even needed to get rid of zero elements.
To check if two arrays are permutations of one another, we do the following steps:
1. find & compare min/max for arrays (if not equal we are done)
2. compare the sums: a[1]+...+a[n] and b[1]+...+b[n]
3. compare the sums of squares: a[1]^2+...+a[n]^2 and b[1]^2+...+b[n]^2
if all three conditions are fulfilled, the arrays are permutations
I'd appreciate if someone could find a counterexample
ok, folks, all your counterexamples contain zero element.
Do get rid of it, we can first count the # of zeros in each array,
if they are not equal, we are done.
If yes, we proceed with xor/add/mul tests as above where zero elements are not taken into account.
@Ashish Kaila: that's right if we assume to have an fp number with
very large mantissa (e.g., BigFloat).
Remember that, in floatingpoint format, any number is stored
in scientific format, i.e.:
sign * mantissa * 2^{exponent + bias}
each multiplication by 10 introduces some small error and
these errors tend to accumulate. Thus, comparing two fpnumbers
for equality is, in many cases, meaningless. Just try to run your
algorithm for n = 1.000002
you are right, sorry I've just chosen the wrong examples
but the rules are correct. It should be:
35721 > 35753 (mirror the upper half)
35762 > 35853 (increment the middle digit if given)
35972 > 36063 (increment and mirror the upper half)
99999 > 100001 (special case)
anyway it does not make the algorithm wrong
yeah there are basically 4 rules to find the next palindrome.
They can best be described using examples:
num > next palindrome
35721 > 35753 (mirror the upper half)
35762 > 35853 (increment the middle digit if given)
35911 > 36063 (increment and mirror the upper half)
99965 > 100001 (special case)
hence, what we need to do is just to check all of them in the order they listed above. The code is as follows:
// finds a smallest palyndrome number x2 > x
int next_palyndrome(int x) {
int digits[12], n, x2 = x;
for(n = 0; x2 != 0; n++) {
digits[n] = x2 % 10;
x2 /= 10;
}
int n2 = n / 2, n2p1 = n2 + (n & 1);
// first try replacing the lower digits with rev upper digits
int rev_hi = digits[n2p1], exp = 10;
for(int i = 1; i < n2; i++) {
rev_hi = rev_hi * 10 + digits[n2p1 + i];
exp *= 10;
}
int hi = x / exp, lo = x % exp; // extract lower and upper halves
x2 = hi * exp + rev_hi;
if(x2 > x) // CHECKING RULE 1
return x2;
hi += 1; // increment 'hi' and construct the number again
if(hi == exp) { // handle a special case when hi = '99...99'
if(n & 1) { // here we return: 100..001
x2 = hi * exp * 10 + 1;
} else {
x2 = hi * exp + 1;
}
return x2; // CHECKING RULE 4
}
int t = (n & 1) ? hi / 10 : hi; // divide out a middle digit if necessary
rev_hi = t % 10;
// calculate the reverse of 'hi' again
for(int i = 1; i < n2; i++) {
t /= 10;
rev_hi = rev_hi * 10 + (t % 10);
}
x2 = hi * exp + rev_hi;
return x2; // RULE 2 and 3 (together)
}
int main() {
int x = 4992734;
while(1) {
printf("next: %d\n", x);
int x2 = next_palyndrome(x);
if(x2 <= x) {
printf("FATAL: %d %d\n", x2, x);
break;
}
x = x2;
}
return 1;
}
sample output:
next: 4992734
next: 4992994
next: 4993994
next: 4994994
next: 4995994
next: 4996994
next: 4997994
next: 4998994
next: 4999994
next: 5000005
next: 5001005
next: 5002005
next: 5003005
next: 5004005
next: 5005005
next: 5006005
next: 5007005
next: 5008005
next: 5009005
next: 5010105
next: 5011105
next: 5012105
next: 5013105
next: 5014105
next: 5015105
next: 5016105
next: 5017105
next: 5018105
next: 5019105
next: 5020205
next: 5021205
next: 5022205
next: 5023205
next: 5024205
next: 5025205
here the point is what policy we use to define which appointments are conflicting.
there are at least two options:
1. minimize the time interval between two scheduled appointments
2. maximize the total number of scheduled appointments
I guess the last option is more "fair" in a sense that we prefer to have many short
appointments instead of just a few long ones
this problem can be solved by greedy alg in O(nlogn) time.
first sort the appointments by increasing finishing times:
suppose f[1] <= f[2] <= ... <= f[n]
then run the following alg:
A = {1} // the first appointment
j = 1;
for i = 2 to n do
if s[i] >= f[j] then
A = A + {i} // add appointment 'i'
j = 1
end if
end do
accordingly all conflicting are those that are not in A
there is also a variablebyte coding scheme where an integer
is represented in the following way:
7 least significant bits of each byte are taken from the original
integer, then the highest 8th bit is set to 1 if the number has
further nonzero bytes and is 0 otherwise
in such a way a 32bit integer '200' would occupy just 2 bytes instead of 4.
This method gives a good compression if numbers represented have different magnitudes and allows us to store variablelength integers
iterator design is rather simple: you define a concept which is basically the set of typenames custom iterators should provide
to be eligible as input iterators. Then you also define
iterator_traits to distinguish between Cstyle pointers and
iterator objects, smth like:
template <class T>
struct iterator_traits { // forward definitions from iterator type T
typedef typename T::data_type data_type;
typedef typename T::ref_type ref_type;
...
};
template <class T>
struct iterator_traits<T*> { // same for pointers
typedef T data_type;
typedef T& ref_type;
...
};
good algo @eugene ))
I think what you are doing is just sorting the array by bitreversal: indeed because first you partition mod 2
than mod 4 and so on. This can be done in a single pass, if the numbers are small, or using a conventional sort as follows:
struct cmp {
bool operator()(int a, int b) {
return (bitrev(a) < bitrev(b));
}
int bitrev(int x) {
int m = 0x55555555;
x = ((x & m) << 1)  ((x & ~m) >> 1);
m = 0x33333333;
x = ((x & m) << 2)  ((x & ~m) >> 2);
m = 0x0f0f0f0f;
x = ((x & m) << 4)  ((x & ~m) >> 4);
m = 0x00ff00ff;
x = ((x & m) << 8)  ((x & ~m) >> 8);
m = 0x0000ffff;
x = ((x & m) << 16)  ((x & ~m) >> 16);
return x;
}
};
int main()
{
int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
int n = sizeof(a) / sizeof(int);
// get a random shuffle first
std::random_shuffle(a, a + n);
for(int i = 0; i < n; i++) {
std::cout << a[i] << " ";
}
std::cout << "\n";
// now sort the array according to bit rev index
std::sort(a, a + n, cmp());
for(int i = 0; i < n; i++) {
std::cout << a[i] << " ";
}
std::cout << "\n";
return 0;
}
output: 1 9 5 3 11 7 8 4 12 2 10 6
 pavel.em November 11, 2011subtracting is not very efficient if the divisor much smaller than the dividend
you can adapt the binary search for this problem,e.g:
// computes a = b*q + r with 0 <= r < b
void divide(unsigned a, unsigned b, unsigned& quo, unsigned& rem) {
// suppose numbers are positive
if(a < b) {
quo = 0; rem = a;
return;
}
quo = 1;
while(quo*b*2 <= a) {
quo *= 2;
}
// here it holds that: quo*b <= a < quo*b*2
if(quo * b == a) {
rem = 0;
return;
}
unsigned ql = quo, qr = quo*2, mid;
while(1) {
mid = (ql + qr) / 2;
if(mid*b <= a && a < (mid+1)*b)
break;
if(mid*b < a) {
ql = mid+1;
} else {
qr = mid;
}
}
quo = mid, rem = a  quo * b;
}
int main() {
unsigned a = 2556721331, b = 13, q, r;
printf("correct: %d %d\n", a / b, a % b);
divide(a, b, q, r);
printf("test: quo: %d; rem: %d\n", q, r);
return 1;
}

pavel.em
October 22, 2011 nice algo! small improvement is that you also have to take care
of boundary cases, i.e.,
if you search for '2' in {5,4,3,2,1}, the index i can become
negative, this can be fixed as follows:
for (i=0; i<arr.length;)
{
if (arr[i]==p)
{found = 1;
break;
}
i += abs(p  arr[i]);
}

pavel.em
October 21, 2011 'id=9783960' it's a different problem.
Here it is asked to find a SUBARRAY (contiguous part) that can be transformed to a sequence of consecutive integers, i.e.:
a = {4,5,1,5,7,4,3,6,3,1,9}
the subarray is: {5,7,4,3,6} because these numbers can be arranged as: {3,4,5,6,7}
nope this is a brilliant idea ! you just needed to develop it further.
your logic is correct: what we need is to transpose an M x 3 matrix stored in a rowmajor manner using inplace algorithm.
The main difficulty is that inplace algorithm generates
loops during permutations..
Discussions be found here: en.wikipedia.org/wiki/Inplace_matrix_transposition
// merge sort: returns a pointer to the head of a sorted list
list *merge_sort(list *head) {
if(head == 0)
return 0;
list *p = head, *pp = p, *prev = 0
if(p>next == 0)
return head; // already sorted
// find a split in the middle using two ptrs
while(pp != 0 && pp>next != 0) {
prev = p, p = p>next;
pp = pp>next>next;
}
prev>next = 0; // cut the list in the middle
list *h1 = merge_sort(p),
*h2 = merge_sort(head); // sort the two parts
head = h1, prev = 0;
// merge the list 'h2' into 'h1' inplace
while(h2 != 0) {
if(h1 != 0 && h2>val >= h1>val) {
prev = h1; // just iterater through 'h1' list
h1 = h1>next;
} else { // insert 'h2' before 'h1'
list *t = h2>next; // save the 'next' pointer
if(prev == 0) { // insert a new head
h2>next = head;
head = h2;
} else {
prev>next = h2;
h2>next = h1;
}
prev = h2; h2 = t;
}
}
return head;
}

pavel.em
October 18, 2011 if I understand the problem correctly, we just need to count the number of turns (left / right) while traversing a binary tree. The solution with additional storage:
std::hast_map< int, int > vsums; // the hash containing vertical sums
void compute_vsums(node *t, int n) {
if(t == 0)
return;
// one turn to the left corresponds to n1
// turn to the right corresponds to n+1
vsums[n] += t>val;
compute_vsums(t>left, n1);
compute_vsums(t>right, n+1);
}
call compute_vsums(root, 0);

pavel.em
October 18, 2011 and if we do not have a parent node, then:
node *wanted; // the node whose successor we wish to find
node *find_rec(node *t, bool& found) {
if(t == 0) {
found = false;
return 0;
}
if(t == wanted) { // found the 'wanted' node
found = true; // in the traversal
return 0;
}
node *x = find_recurs(t>left, found);
if(found) {
if(x != 0)
return x; // the successor already found: just pass it by
return t; // this is a successor
}
return find_rec(t>right, found);
}
node *inorder_succ() {
if(wanted>right) {
... // proceed as in the above soln
return t;
}
bool found = false; // otherwise start the search from the root
return find_rec(root, found);
}

pavel.em
October 18, 2011 // infA[]  infinite array with '$' as a terminating character
bool binary_search(char *infA, char x) {
int l = 0, r = 1;
while(1) { // first phase: find the array bounds
char a = infA[r  1];
// here we either found the valid range or hit the end of the data:
// in any case we can reduce the search space to [l; r]
if(a == '$'  x < a) {
break;
}
if(x == a) // found the actual val
return true;
// otherwise we keep on moving the right boundary
l = r  1, r = r * 2;
}
printf("'x' can only lie between [%c; %c]\n", infA[l], infA[r]);
// second phase: run an ordinary binary search with account for
// the terminating symbol '$'
while(1) {
int mid = (l + r) / 2;
char a = infA[mid];
if(a == '$'  x < a) {
r = mid;
} else if(x > a) {
l = mid + 1;
} else // gotcha !!
return true;
if(l == r)
return false; // not found
}
}

pavel.em
October 18, 2011 suppose `hour' is in [0..11]
and `min' is in [0..59]
we do not take seconds into account for simplicity
compute_angle(int hour, int min) {
float ha = (float)(hour + min / 60.0f) * 360 / 12.0f; // position of hours hand
float ma = (float)min * 360 / 60.0f; // position of minutes hand
float a = std::abs(ha  ma);
if(a > 180)
a = 360  a;
return a; // return the angle difference
}

pavel.em
October 18, 2011 int max_so_far = 0;
// in each recursive call [low; up] specifies the valid range of node
// values to satisfy the BST property
int max_BST_subtree(node *t, int low, int up) {
if(t == 0) // found a leaf node
return 0;
// indicates that the BST property is broken
if(t>val <= low  t>val >= up)
return 1;
// count the number of BST nodes in subtrees
int s_left = max_BST_subtree(t>left, low, t>val);
int s_right = max_BST_subtree(t>right, t>val, up);
// take either left part, right part or both
if(s_left != 1 && s_right != 1)
s = s_left + s_right + 1; // take both subtrees + root node
else
s = max(s_left, s_right); // take on of subtrees
max_so_far = max(s, max_so_far);
return s; // return the number of nodes found (or 1 if no BST)
}
call max_BST_subtree(root, infty, +infty);

pavel.em
October 17, 2011 smth along these lines should work:
// A[n]  array containing preorder traversal of a BST
root = new node;
t = root, t>parent = 0;
t>val = A[0], split = t;
for(i = 1; i < n; i++) {
if(A[i] < t>val) {
add_left_child(t, A[i]);
split = t;
t = t>left;
continue;
}
// if split == 0 or A[i] < split>val then just add to the right
// child of the current node 't' otherwise find another 'split'
if(split != 0 && A[i] > split>val) {
t = split;
while(t>parent != 0) {
if(A[i] < t>parent>val)
break;
t = t>parent;
}
split = t;
}
add_right_child(t, A[i]);
t = t>right;
}

pavel.em
October 10, 2011 @anonymous: WOW!! thanks for visualizing the schoolbook division ))
Generating digits of decimal expansion can be done,
e.g., using the following simple algorithm:
void div_periodic(int num, int denom) {
int div = num / denom;
int mod = num % denom;
printf("%d.", div); // print integer part
num = mod;
int niters = 100;
std::vector< int > digits;
while(niters) {
num *= 10; // num is always smaller than denom
int n_zeros = 0;
while(num < denom) { // add the required number of zeros
num *= 10; n_zeros++;
digits.push_back(0);
}
div = num / denom; // div is always a single digit
mod = num % denom;
digits.push_back(div); // add the next digit
num = mod;
if(num == 0)
break;
}
}
However, now it comes to the two main problems:
how to find where the period starts ?
how to find the length of the period ?
I think interviewers that ask such questions do not really understand the problem themselves because there is a significant amount of math behind it.
Consuling wikipedia, we find out that whenever
a denominator has factors of the form 2^a*5^b,
the resulting reciprocal is eventually periodic
but has a nonrepeating sequence of digits of size max(a,b).
Now assume we know where the period starts.
The next problem is that a smaller period can be the part of larger
ones. For example, consider a decimal expansion of
1414147 / 999999999
which is 0.(001414147)
so there is no trivial way to detect it unless we know
what the maximal period of a fraction could be.
Again consulting wikipedia, we find that
the period of a reciprocal 1 / p is the order of 10 in Z/Zp,
given by Euler totient function, and is at most (p1).
This suggests that we have to compute the first (p1) digits
of decimal expansion of 1/p to find the period!!!
Is there another way ?
finally some good solution ))
I think you can do this even simpler:
given a number x = 1000111100
lo = x & x; // locate the lowest set bit: lo = 100
lz = (x + lo) & ~x; // locate the lowest zero above lo: lz = 1000000
x += lo; // flip the 'lz' bit: x = 1001000000
x = (lz / lo / 2); // add the rest number of ones: x = 1001000111

pavel.em
October 03, 2011
I think I partly understand what he wanted to say:
 111 February 03, 2012if the order of matrix multiplications is fixed, we can find an optimal factorization of the matrix product to minimize the # of arithm ops using DP algorithm:
h t t p://en.wikipedia.org/wiki/Chain_matrix_multiplication
though I am not sure how this relates to class diagrams / inheritance etc..