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 non-intersecting 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+k-1] where i + k <= j
s.t. a[i..i + k - 1] < a[j..j+k-1] or a[i..i + k - 1] > a[j..j+k-1]
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 single-word division:
- pavel.em in United States
i.e., you are given a long integer X having 'n' limbs (32-bit words) and you need to divide X by another 32-bit int 'b'
optimize your solution for time. Can you do this better if you know that 'b' divides 'X' exactly ?
what if 32-bit division on the target architecture is expensive ? try to minimize the # of integer '/' and '%' ops (e.g., using floating-point 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 double-precision 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 32-bit 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[n-1]*x^[n-1] + ... + 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 k-th 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 pre-order
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)
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;
}
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 quick-and-dirty 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][j-1] + 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][k-1];
printf("%d ", tmp);
}
printf("\n");
}
}
traverse(t->left, j+1);
traverse(t->right, j+1);
}
main() {
traverse(head, 0);
}
the idea is that applying n-1 times gray code function to an n-bit 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 n-1 times we do the following (for 32-bit 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 PAT-tree 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 high-order 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;
}
};
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;
}
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);
}
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;
}
this is so called gray-code 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(n-1, k, z);
if(k > 0) {
x[k] = n;
comb_gray(n-1, k-1, !z);
}
} else { // backward direction:
if(k > 0) {
x[k] = n;
comb_gray(n-1, k-1, !z);
}
comb_gray(n-1, k, z);
}
}
main() {
x = new int[N+1];
comb_gray(N, K, 1);
}
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);
}
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
}
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_total-1);
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);
}
ok, here comes some bit wizardy:
int prev(int n) {
int y = ~n;
y &= -y; // lowest zero bit
n &= ~(y-1); // 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;
}
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