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
a solution using additional space: i.e., traverse the tree in preorder
and keep the partial sums in a hash
after traversing left and right children, merge the hashes into one as well as add the value
of a root node to the hash, return it
here the required additional space is O(n) where n is the number of nodes in the tree
since we do not need to store all partial sums in a hash
well, hash is needed just to avoid duplicates, a simple array should also work
bool has_sum(node *t, hash& h) {
if(t == 0)
return false;
if(t>value == sum)
return true;
hash h_l, h_r;
if(has_sum(t>left, h_l))
return true;
if(has_sum(t>right, h_r))
return true;
h.add(t>value);
forall x in h_l do
x += t>value;
if(x == sum)
return true;
h.add(x)
}
forall x in h_r do
x += t>value;
if(x == sum)
return true;
h.add(x)
}
return false; // no found yet
}
hash h;
has_sum(root, h)

pavel.em
October 02, 2011 node *construct(int *inorder, *int preorder, int sz) {
if(sz == 0)
return 0;
int root = preorder[0];
node *head = new node;
int split = 0;
while(root != inorder[split])
split++;
// split points to the root in inorder traversal
head>left = construct(inorder, preorder + 1, split);
head>right = construct(inorder + split + 1,
preorder + split + 1, sz  split  1);
return head;
}

pavel.em
June 16, 2008 brilliant idea, Anish ;)
looks like it really works: indeed one needs only one pass over the tree structure to find all
sums. Implementation is a bit quickanddirty but I hope quite understandable:
struct node {
int val;
node *left;
node *right;
};
int A[20][20]; // A[i][j] stores sum of path from level i to level j
int sum = 12; // the sum we are looking for
// j is the current level
void traverse(node *t, int j) {
if(t == 0)
return;
if(t>val == sum)
printf("%d\n", sum);
A[j][j] = t>val;
for(int i = 0; i < j; i++) {
A[i][j] = A[i][j1] + t>val;
if(A[i][j] == sum) {
for(int k = j; k >= i; k) {
int tmp = A[i][k];
if(k > i)
tmp = A[i][k1];
printf("%d ", tmp);
}
printf("\n");
}
}
traverse(t>left, j+1);
traverse(t>right, j+1);
}
main() {
traverse(head, 0);
}

pavel.em
June 16, 2008 the idea is that applying n1 times gray code function to an nbit integer gives the inverse gray code,
note also that: applying gray code 2 times is: x ^ (x >> 2), this can be easily verified: y = x ^ (x >> 1), z = y ^ (y >> 1) = (x ^ (x >> 1)) ^ ((x ^ (x >> 1)) >> 1) = x ^ (x >> 1) ^ (x >> 1) ^ (x >> 2) = x ^ (x >> 2).
That is, to apply gray code n1 times we do the following (for 32bit ints):
inverse_gray_code(int x) {
x ^= (x >> 1);
x ^= (x >> 2);
x ^= (x >> 4);
x ^= (x >> 8);
x ^= (x >> 16);
return x;
}
yes, I also think PATtree is the most appropriate here: due to storage efficiency (one doesn't need to store all common prefixes) in contrast to hash tables as well as performance issues due possible hash conflicts. Additionaly, we need to store word frequencies in leaf nodes to maintain the heap of k most frequent ones.
 pavel.em June 14, 2008here is the clue how to do this:
(refer to gmplib.org for mature implementations)
// basic data type
typedef unsigned long limb;
class BigInt {
limb *data; // stores digits
int n_limbs; // # of limbs (radix 2^32 digits)
int n_allocated; // # of limbs allocated
bool sign; // sign
public:
BigInt() :
data(0), n_limbs(0), n_allocated(0), sign(0) {
}
// constructs bigint from string
BigInt(const char *str);
// from integer
BigInt(int x) :
n_allocated(0), data(0) {
alloc_limbs(1);
data[0] = abs(x);
sign = (x < 0);
}
// adds to bigints: need special handling for signed operands
friend BigInt operator +(const BigInt& a, const BigInt& b) {
BigInt res;
int na = a.n_limbs, nb = b.n_limbs;
limb *pl = a.data, *ps = b.data, maxn = na, minn = nb;
if(nb > na) {
swap(pl, ps);
swap(maxn, minn);
}
res.n_limbs = maxn + 1;
res.alloc_limbs(res.n_limbs);
limb *pc = res.data;
int carry = 0;
for(int i = 0; i < minn; i++) {
limb x = *pl++, c = x + *ps++;
carry = (c < x) + carry; // adjust for carry
c += carry;
carry = (c < carry); // overflow if sum < summands
*pc++ = c;
}
// iterate over the highorder digits to update carry flag
for(int i = 0; i < maxn  minn; i++) {
limb c = carry + *pl++;
carry = (c < carry);
*pc++ = c;
}
*pc = carry; // add the leading carry
}
private:
// allocates space enough to store n limbs
void alloc_limbs(int n) {
if(n_allocated >= n)
return;
data = (limb *)malloc(n);
n_allocated = n;
}
};

pavel.em
June 12, 2008 1. facility testing (test whether program is doing what it is indended to do): i.e., whether func is indeed called
2. usability testing: check that the function outputs (if any) are meaningful, nonabusive;
error messages are straightforward
3. security: check that 'setTime' cannot invoke a function residing in a privileged region if current user privileges are not enough (i.e., it does not break privilege rules)
4. compatibility: check whether this function works with older operating systems
clear solution
node *remove(node *root, node *z) {
if(z == 0)
return root;
node *del = z>right;
if(del != 0 && z>left != 0) {
// here z has both children: find it's inorder successor
while(del>left != 0)
del = del>left;
z>key = del>key; // rewrite it's key
} else
del = z;
// del is a node to be removed (has at most 1 child)
node *p = del>parent, *child = del>left;
if(child == 0)
child = del>right;
if(child != 0)
child>parent = p;
if(p != 0) {
if(del == p>left)
p>left = child;
else
p>right = child;
} else
root = child;
delete del;
return root;
}

pavel.em
June 10, 2008 part A:
// initialize 2 semaphores:
sem A_done(0);
sem B_done(0);
//let's say methods are declared as follows:
Foo::A() {
create_thread(func_A);
}
Foo::B() {
create_thread(func_B);
}
Foo::C() {
create_thread(func_B);
}
// add the following sync code to thread functions:
func_A() {
/* body */
A_done.signal(); // increments semaphore variable by 1
// (and unblocks one thread out of those waiting on this semaphore)
}
func_B() {
A_done.wait(); // waits on semaphore
/* body */
B_done.signal();
}
func_C() {
B_done().wait();
/* body */
}
part B:
// declare 3 semaphores:
sem A_done(0), B_done(0), C_done(1);
// function bodies:
func_A() {
C_done.wait();
/* body */
A_done.signal(); // increments semaphore variable by 1
// (and unblocks one thread out of those waiting on this semaphore)
}
func_B() {
A_done.wait(); // waits on semaphore
/* body */
B_done.signal();
}
func_C() {
B_done().wait();
/* body */
C_done.signal();
}
part C 3) didn't quite understand the question
 pavel.em June 09, 2008nope, man...
first, it's not said that tree structure has 'parent' pointers,
second, your solution only works if leaf nodes have the same depth (which is not true even if the tree were balanced).
here is a simple recursive solution:
node *p1, *p2;
node *common = 0;
bool common_ancestor(node *t) {
if(t == 0)
return false;
if(t == p1  t == p2) // match found
return true;
bool hit1 = common_ancestor(t>left);
if(common != 0) // already found
return false;
bool hit2 = common_ancestor(t>right);
if(hit1 & hit2) {
common = t;
return false;
}
return (hit1  hit2);
}
main() {
// assign p1 and p2 to some leaf nodes
common_ancestor(root);
}

pavel.em
June 09, 2008 the simpler the better ;)
list *kreverse(list *head, int k) {
if(k <= 1) // nothing to reverse
return head;
list *p = head, *tail = 0;
while(p != 0) {
// remember where we start this piece
list *start = p, *prev = 0, *temp;
int c = k;
while(p != 0 && c > 0) { // do usual reverse
temp = p>next;
p>next = prev;
prev = p;
p = temp;
}
if(tail != 0) // link reversed pieces
tail>next = prev;
else // indicates the first piece
head = prev;
tail = start;
// here p points to the next part being processed
}
return head;
}

pavel.em
June 07, 2008 this is so called graycode combinations, don't ask me why it works
personally I don't understand it completely, it's magic ;))
int N = 7; // number of bits in words
int K = 3; // number of bits in words
int *x; // elements in combination at x[1] ... x[k]
void visit() // prints out one combination
{
for(int j = 1; j <= K; j++)
printf("%d ", x[j]);
printf("\n");
}
void comb_gray(int n, int k, bool z)
{
if(k == n) {
for(int j=1; j<=k; ++j)
x[j] = j;
visit();
return;
}
if(z) {// recurse in forward direction
comb_gray(n1, k, z);
if(k > 0) {
x[k] = n;
comb_gray(n1, k1, !z);
}
} else { // backward direction:
if(k > 0) {
x[k] = n;
comb_gray(n1, k1, !z);
}
comb_gray(n1, k, z);
}
}
main() {
x = new int[N+1];
comb_gray(N, K, 1);
}

pavel.em
June 06, 2008 right, one needs special handling for cyclic data structures, for instance using
additional container to store a set of processed addresses:
std::hash_set<int> processed;
struct node {
int data;
x *p1;
x *p2;
};
node *deep_copy(node *x) {
if(x == 0)
return 0;
// found a loop
if(processed.find((int&)x) != processed.end())
return x;
processed.insert((int&)x); // mark x as already processed
node *p = new node;
p>data = x>data;
p>p1 = deep_copy(x>p1);
p>p2 = deep_copy(x>p2);
return p;
}
main() {
node *clone = deep_copy(x);
}

pavel.em
June 06, 2008 bullsh*t: if binary tree is not BST then the whole problem does not make any sense:
it's just "find the next biggest value in an array"
@anonymous: what if the tree structure does not provide a 'parent pointer' ?
here is a simple solution:
struct bin_tree {
bin_tree *left;
bin_tree *right;
int n;
};
int next_biggest(bin_tree *t, int val) {
if(t == 0)
return 1;
if(val < t>n) {
c = next_biggest(t>left, val);
if(c != 1)
return c;
return t>n;
}
return next_biggest(t>right, val);
}
compact solution:
list *build_list(node *t, list *curr) {
if(t == 0)
return curr;
curr = build_list(t>left, curr);
curr>next = new list;
curr = curr>next;
curr>d = t>d;
return build_list(t>right, curr);
}
main() {
list head;
list *last = build_list(t, &head);
last>next = 0;
// head.next is the head of the new list
}

pavel.em
June 05, 2008 recursive solution without any crapy character arrays
(works for # of parenth < 32, I bet no one can enumerate
all combinations with more than 32 pars):
int n_total = 6; // total number of parenthesis
char par[] = {')','('};
void parenth(int n_open, int n_closed, int num) {
if(n_closed == n_total) {
int mask = 1 << (2*n_total1);
while(mask) {
putchar(par[num & mask ? 1 : 0]);
mask >>= 1;
}
putchar('\n');
return;
}
num *= 2;
if(n_closed < n_open) // closing parenth encoded as 0
parenth(n_open, n_closed + 1, num);
if(n_open < n_total) // opening parenth as 1
parenth(n_open + 1, n_closed, num + 1);
}
main() {
parenth(0, 0, 0);
}

pavel.em
June 05, 2008 ok, here comes some bit wizardy:
int prev(int n) {
int y = ~n;
y &= y; // lowest zero bit
n &= ~(y1); // reset all bits below y
int z = n & n; // lowest set bit
n &= ~z; // clear z bit
n = (z  z / (2*y)); // add requried number of bits below z
return n;
}
int next(int n) {
int lo = n & n; // lowest one bit
int lz = (n + lo) & ~n; // lowest zero bit above lo
n = lz; // add lz to the set
n &= ~(lz  1); // reset bits below lz
n = (lz / lo / 2)  1; // put back right number of bits at end
return n;
}

pavel.em
June 05, 2008
Nope I think this is wrong: a path may or may not start from the root, while you consider only the paths from the root. Otherwise the question is trivial ))
 pavel.em October 02, 2011