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 0-999 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 10-19, since you need not worry about ones place for them.
A segment tree can give you a log N solution; provided pre-computation 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, N-node->left->numNodes-1);
}
int EvalExp(int lVal, int rVal, char op){
switch(op){
case'+':
return (lVal+rVal);
case'-':
return (lVal-rVal);
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,i-1);
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,(end-start+1));
ss>>maxVal;
}
return maxVal;
}
void EvalMax(){
string str="2*3+5-3";
cout << "Maximum value: " << EvalMaxHelper(str,0,str.length()-1) << endl;
}
- 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 (n-1)-(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++) {
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,(q-p)+1);
if (H.find(subStr)) str.erase(p, (q-p)+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 pre-order and in-order traversal. If invalid then return false
- Get the post-order traversal for the above constructed tree, and see if it matches the given post-order 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))
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<=(end-start); i++) {
ch = expression[i];
switch (ch) {
case '+': operand = EvalExp(expression.substring(start,(i-start)+1));
result = operand + MaxEvalExp(expression, i+1, end, false);
if (isFull) && (result>maxValue) maxValue = result;
case '-': operand = EvalExp(expression.substring(start,(i-start)+1));
result = operand - MaxEvalExp(expression, i+1, end, false);
if (isFull) && (result>maxValue) maxValue = result;
case '*': operand = EvalExp(expression.substring(start,(i-start)+1));
result = operand * MaxEvalExp(expression, i+1, end, false);
if (isFull) && (result>maxValue) maxValue = result;
case '/': operand = EvalExp(expression.substring(start,(i-start)+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.length-1, true);
cout << "Maximum Value: " << maxValue;
return 0;
}
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)
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 flood-fill 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)
The question is to find minimum comparisons not complexity in terms of array size. With your quicksort approach if we continuously end-up with bad pivot we need (n-1)+(n-2)+(n-3)...+(n-n/2) comparisons.
- IntwPrep.MS December 27, 2013 Sort the string
For each index i, set its predecessorIndex as (i-1) if ary[i]=ary[i-1]; 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
In-place 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*n-k times
}
return min
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 grand-parent 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)
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 0-999 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 (y-axis as random number, x-axis as each attempt)