IntwPrep.MS
BAN USER 0of 0 votes
AnswersTest cases for int rand() which returns a random number between 0  999
 IntwPrep.MS in United States for Bing Report Duplicate  Flag  PURGE
Microsoft Senior Software Development Engineer  2of 2 votes
AnswersGiven a number give its english form
 IntwPrep.MS in United States for Bing
1> One
999 > Nine hundred and ninety nine
Max number is: 999, 999, 999 Report Duplicate  Flag  PURGE
Microsoft Senior Software Development Engineer  0of 0 votes
AnswersDesign a webservice which would take a word, and return all anagrams
 IntwPrep.MS in United States for Bing Report Duplicate  Flag  PURGE
Microsoft Senior Software Development Engineer  0of 0 votes
AnswersDesign a voicemail system. Would you use RDBMS or File system, provide rationale.
 IntwPrep.MS in United States for Bing Report Duplicate  Flag  PURGE
Microsoft Senior Software Development Engineer  0of 0 votes
AnswersAn application is crashing the moment it is opened, how would you test it.
 IntwPrep.MS in United States for Bing Report Duplicate  Flag  PURGE
Microsoft Senior Software Development Engineer
My answer:
Observation: each three digit number is spelled the same, the only difference is the magnitude (million, thousand, hundred). Hence write a utility function which processes a number from 0999 and call it for hundreds, thousands and millions.
Algorithm:
 create a HashMap<int, string> for the below values
0  zero
1  one
...
9  nine
10  ten
11  eleven
12  twelve
....
19  nineteen
20  twenty
30  thirty
40  fourty
...
90  ninety
100  one hundred
200  two hundred
...
900  nine hundred
 Now calculate ones, tens and hundreds place and form a string. Care should be taken to handle numbers from 1019, since you need not worry about ones place for them.

IntwPrep.MS
January 17, 2014 A segment tree can give you a log N solution; provided precomputation is allowed (to construct the segment tree
 IntwPrep.MS January 07, 2014Does the interviewer wants us to modify the given array so that we can find the longest such sequence? Or just print sequences (sets) to the given array?
 IntwPrep.MS January 06, 2014Assumption: each node holds the number of nodes present within its subtree rooted at that node. If not for this assumption log N is not possible
Node * FindNSmallest(TNode *node, int N) {
if(!node) return NULL;
if(node>left>numNodes+1 == N) return node;
if(node>left>numNodes>=N) return (FindNSmallest(node>left, N);
else return(FindNSmallest(node>right, Nnode>left>numNodes1);
}

IntwPrep.MS
January 05, 2014 int EvalExp(int lVal, int rVal, char op){
switch(op){
case'+':
return (lVal+rVal);
case'':
return (lValrVal);
case'*':
return (lVal*rVal);
case'/':
return (lVal/rVal);
}
}
int EvalMaxHelper(string str, int start, int end){
int maxVal;
int lVal,rVal;
int val;
const int NEG_INFINITY=99999;
stringstream ss;
maxVal=NEG_INFINITY;
for(int i=start; i<end; i++){
if(str[i]=='+'  str[i]==''  str[i]=='*'  str[i]=='/' ){
lVal=EvalMaxHelper(str,start,i1);
rVal=EvalMaxHelper(str,i+1,end);
val=EvalExp(lVal,rVal,str[i]);
if (val>maxVal)
maxVal=val;
}
}
if (maxVal==NEG_INFINITY){
ss<<str.substr(start,(endstart+1));
ss>>maxVal;
}
return maxVal;
}
void EvalMax(){
string str="2*3+53";
cout << "Maximum value: " << EvalMaxHelper(str,0,str.length()1) << endl;
}

IntwPrep.MS
January 04, 2014  create two arrays evenOrder  even numbers are placed to left; oddOrder  odd numbers are placed to left.
 Now copy even numbers from evenOrder to even numbers within oddOrder
 return oddOrder
Time O(N), space O(N)
If number is even:
if the second half of the number is less than the reverse of first half of number
return first half of number concatenated with the reverse of the first half
else
increment the 1st half by 1
return first half of number (after increment) concatenated with the reverse of the first half
If odd can repeat the same strategy by treating 1st half as the one excluding the middle element. However when incrementing we do consider the middle element.
 IntwPrep.MS December 30, 2013Why do we have (n1)(n/2) ?? Can someone explain (n/2)
 IntwPrep.MS December 30, 2013O(N) can not be achieved with O(1) space. Can be done with O(N) space.
 IntwPrep.MS December 30, 2013The inner for loop should be
for (; q<str.length; q++,p++) {

IntwPrep.MS
December 30, 2013 void RemoveDup(string str) {
int p,q;
HashMap<string,bool> H;
for (int i=0; i<str.length; i++) {
p=0; q=i;
H.clear(); //empty hash map
for (; q<str.length; q++) {
subStr = str.substring(p,(qp)+1);
if (H.find(subStr)) str.erase(p, (qp)+1); //erase subStr from string
else H.insert(subStr);
}
}
}
Time complexity O(N^3)
 IntwPrep.MS December 30, 2013Similar to Kadane's maximum subarray problem, the difference is we rotate the circle twice to cover starting from every node.
 IntwPrep.MS December 30, 2013 Construct a binary tree with preorder and inorder traversal. If invalid then return false
 Get the postorder traversal for the above constructed tree, and see if it matches the given postorder traversal
Assuming arrays are sorted
1) Initialize i,j an k to 0. i, j and k are indices for the three arrays
2) find the sum of differences of elements at indices i, j and k. If this is smaller than current minimum, update current minimum
3) Find the smallest of the elements present at index i, j, k and increment that index if you are not going out of bound
4) Goto step 2, until all three arrays are exhausted
5) Return stored minimum
0's can be handled by finding max product for subarrays split using 0 as delimiter. If the maximum product for each such subarray is negative then return 0. If not return the maximum product of the subarray
How to find maximum product of each subarray:
 For each index i, store a value which is the product of numbers till i (including i)
 Keep track of the following
 maximum product (positive) seen so far, say X
 maximum negative product seen so far, say Y
 least negative product seen so far, say Z
 Now if the final product (at last index) is positive return it
 If not return (X>(Z/Y)?X:(Z/Y))

IntwPrep.MS
December 30, 2013 Use recursion; algorithm
;assumption  every operand is single digit, code can be expanded easily to handle operands >9
int toVal(string); converts a string number into integer/double
int EvalExp(string); evaluates the expression from left to right without any precedence
double MaxEvalExp(string expression, int start, int end, bool isFull) {
char ch; int operand;
if (start==end) return toVal(expression);
for (int i=0; i<=(endstart); i++) {
ch = expression[i];
switch (ch) {
case '+': operand = EvalExp(expression.substring(start,(istart)+1));
result = operand + MaxEvalExp(expression, i+1, end, false);
if (isFull) && (result>maxValue) maxValue = result;
case '': operand = EvalExp(expression.substring(start,(istart)+1));
result = operand  MaxEvalExp(expression, i+1, end, false);
if (isFull) && (result>maxValue) maxValue = result;
case '*': operand = EvalExp(expression.substring(start,(istart)+1));
result = operand * MaxEvalExp(expression, i+1, end, false);
if (isFull) && (result>maxValue) maxValue = result;
case '/': operand = EvalExp(expression.substring(start,(istart)+1));
result = operand / MaxEvalExp(expression, i+1, end, false);
if (isFull) && (result>maxValue) maxValue = result;
}
}
}
int main() {
string expression;
cin >> expression;
MaxEvalExp(expression, 0, expression.length1, true);
cout << "Maximum Value: " << maxValue;
return 0;
}

IntwPrep.MS
December 29, 2013 Extract the decimal portion as:
double x = N/D;
double decimal = x  (int) x;
 Now convert this decimal portion into a string (this can be achieved by first converting it into an int (multiplying by sufficient power of 10), and then converting to string.
 Construct a suffix tree for this string
 Now the repeated portion is the node value (within the suffix tree) which is added when processing each index (suffix); and the repetition ends at index i for which you have to create a new node within the suffix tree after identifying a pattern.
For example consider 0.34567567567
We extract a string:
Index: 0 1 2 3 4 5 6 7 8 9 10 11 12 13
Value:3 4 5 6 7 5 6 7 5 6 7 5 6 7
Now starting from index 10, the only node that is newly added to suffix tree is '567'. This continues until we process index 1. Hence the result is 0.34 (567)

IntwPrep.MS
December 29, 2013 Why make it super complex when the entire decimal portion can be obtained as below:
double x = N/D;
double decimal = x  (int) x;
I think the main part of the problem is not how we extract the decimal portion, but rather how we can find a pattern within the decimal part. I think the easiest way to find the pattern is to rely on suffix trees; check my solution below.
Way to test a point (p,q) is within a triangle is by checking if the area of the triangle is equal to the sum of the three triangles formed with (p,q).
Now to return points within a triangle
 Get a point (p,q) which is within the triangle
 Use floodfill to generate next points by using the above mentioned condition
Good solution
 IntwPrep.MS December 28, 2013The best I can comeup with is 7.
 Need three to get three elements in order: x1 x2 x3
 Now need three more to order x2 x4 x5
 If x4 and x5 fall on either sides of x2 then x2 is median
 If x4 and x5 fall on the same side of x2 (both are greater or smaller then x2) then compare x4 (the element which is closer to x2) with x1 (if x4 is less than x2) or x3 (if x4 is greater than x2)

IntwPrep.MS
December 27, 2013 The question is to find minimum comparisons not complexity in terms of array size. With your quicksort approach if we continuously endup with bad pivot we need (n1)+(n2)+(n3)...+(nn/2) comparisons.
 IntwPrep.MS December 27, 2013 Sort the string
For each index i, set its predecessorIndex as (i1) if ary[i]=ary[i1]; if not set it as 1
During recursion only select index i, if its predecessorIndex (if present, which means it is not 1) is already listed
@Alex
Inplace means constant space, independent on the input size. In this case the hashmap can be a single integer irrespective of the input string length. Hence inplace.
If we are just talking about English characters, then a single integer variable can serve as our hashmap; with A to Z mapped to bits 0 to 25 within the integer.
 IntwPrep.MS December 20, 2013A O(K log K) algorithm
Logic: after ary[p][q], the next smallest element is either ary[p+1][q] or ary[p][q+1]
If K==1 return ary[0][0];
if k==m*n return ary[m][n];
if k<(m*n)/2 {
//create a minHeap H
//push triplet (ary[0][0],0,0) into minHeap
for (int i=0; i<k; i++) {
//extract root of heap, say (val, p, q)
min=val
//push ary[p+1][q], and ary[p][q+1]
//pop the top element
}
else {
//do the same as if block, except you start from bottom and use maxHeap and execute it m*nk times
}
return min

IntwPrep.MS
December 19, 2013 1) Find the node, and keep track of level (say target node is found on level L) time log N
2) Push each traversed node into a stack
3) When node is found
a) Pop the stack to remove the parent of the target node
b) If stack is empty then given node does not have a cousin; return
c) Do DFS from the right child of the current top of the stack (which is the grandparent of the target node) and return the first node at Level L
Time complexity is log N, space complexity log N
 IntwPrep.MS December 18, 2013This should work. But the actual process of getting subarray intervals can render this algorithm O(C(K,2)) where K is the maximum number of indices for a given sum.
 IntwPrep.MS December 17, 2013Why make it complicated; when most (if not all) of the solutions require you to scan the list twice why not just follow the normal LL deletion logic.
1) scan the list and delete target node
2) scan the list and make last node point to the middle node (can achieve this by using slow and fast pointers)
Say if we are to check for value N in round K, then we check from 1st round till Kth round. At each round we are interested in the index of N.
 Clearly when K=2 index of N is N itself (as nothing has been eliminated yet)
 When K=3 then index of N is N  (floor(N/2)); as floor(N/2) elements have been eliminated when K=2
Also in each round (say K) a number whose index is 'X' is eliminated if X%K=0
Therefore we start from 1st round and continue up and see if the number survives till Kth round.
bool isPresent(int N, int K) {
int curRound=2, curIndex=N;
while (curRound < K) {
if (curIndex%curRound==0) return false;
curIndex = curIndex  (floor(curIndex/curRound));
curRound++;
}
return true
}
Time complexity: O(K)
Space complexity: O(1)
Open Chat in New Window
My answer:
 IntwPrep.MS January 17, 2014 verify that the frequency is distributed evenly for all the possible numbers
 Verify that the distance between repititions is about the size of the set (1000) for each number
 Verify that the distance between consecutive random numbers is random in itself
 Verify that the numbers 0999 are only generated
 Verify that in each run you do not get the same sequence of random numbers. Seed it differently
 For visual identification of anomalies, plot the values (yaxis as random number, xaxis as each attempt)