Microsoft Technical Paper

# Microsoft Technical Paper Notes | Study Placement Papers - Technical & HR Questions - Quant

## Document Description: Microsoft Technical Paper for Quant 2022 is part of Placement Papers - Technical & HR Questions preparation. The notes and questions for Microsoft Technical Paper have been prepared according to the Quant exam syllabus. Information about Microsoft Technical Paper covers topics like and Microsoft Technical Paper Example, for Quant 2022 Exam. Find important definitions, questions, notes, meanings, examples, exercises and tests below for Microsoft Technical Paper.

Introduction of Microsoft Technical Paper in English is available as part of our Placement Papers - Technical & HR Questions for Quant & Microsoft Technical Paper in Hindi for Placement Papers - Technical & HR Questions course. Download more important topics related with notes, lectures and mock test series for Quant Exam by signing up for free. Quant: Microsoft Technical Paper Notes | Study Placement Papers - Technical & HR Questions - Quant
 1 Crore+ students have signed up on EduRev. Have you?

Q1. Give a very good method to count the number of ones in a n (e.g. 32) bit number.

ANS: Given below are simple solutions, find a solution that does it in log (n) steps.

Iterative

function iterative count (unsigned int n)

begin

int count=0;

while (n)

begin

count += n & 0x1 ;

n >>= 1;

end

return count;

end

Sparse Count

function sparse count (unsigned int n)

begin

int count=0;

while (n)

begin

count++;

n &= (n-1);

end

return count ;

end

Q2. In a Xs and 0s game (i.e. TIC TAC TOE) if you write a program for this give a fast way to generate the moves by the computer. I mean this should be the fastest way possible.

ANS: The answer is that you need to store all possible configurations of the board and the move that is associated with that. Then it boils down to just accessing the right element and getting the corresponding move for it. Do some analysis and do some more optimization in storage since otherwise it becomes infeasible to get the required storage in a DOS machine.

iterative loop

curr->next = prev;

prev = curr;

curr = next;

next = curr->next

endloop

recursive reverse(ptr)

if (ptr->next == NULL)

return ptr;

temp = reverse(ptr->next);

temp->next = ptr;

return ptr;

end

Q4. Given an array of integers, find the contiguous sub-array with the largest sum.

ANS: Can be done in O(n) time and O(1) extra space. Scan array from 1 to n. Remember the best sub-array seen so far and the best sub-array ending in i.

Q5. Given an array of length N containing integers between 1 and N, determine if it contains any duplicates.

ANS: [Is there an O(n) time solution that uses only O(1) extra space and does not destroy the original array?]

Q6. Sort an array of size n containing integers between 1 and K, given a temporary scratch integer array of size K.

ANS: Compute cumulative counts of integers in the auxiliary array. Now scan the original array, rotating cycles! [Can someone word this more nicely?]

Q7. An array of size k contains integers between 1 and n. You are given an additional scratch array of size n. Compress the original array by removing duplicates in it. What if k << n?

ANS: Can be done in O(k) time i.e. without initializing the auxiliary array!

Q8. An array of integers. The sum of the array is known not to overflow an integer. Compute the sum. What if we know that integers are in 2s complement form?

ANS: If numbers are in 2s complement, an ordinary looking loop like for(i=total=0;i< n;total+=array[i++]); will do. No need to check for overflows!

Q9. An array of characters. Reverse the order of words in it.

ANS: Write a routine to reverse a character array. Now call it for the given array and for each word in it.

Q10. An array of integers of size n. Generate a random permutation of the array, given a function rand_n() that returns an integer between 1 and n, both inclusive, with equal probability. What is the expected time of your algorithm?

ANS: Expected time should ring a bell. To compute a random permutation, use the standard algorithm of scanning array from n down to 1, swapping i-th element with a uniformly random element <= i-th. To compute a uniformly random integer between 1 and k (k < n), call rand_n() repeatedly until it returns a value in the desired range.

The document Microsoft Technical Paper Notes | Study Placement Papers - Technical & HR Questions - Quant is a part of the Quant Course Placement Papers - Technical & HR Questions.
All you need of Quant at this link: Quant

## Placement Papers - Technical & HR Questions

85 docs|57 tests
 Use Code STAYHOME200 and get INR 200 additional OFF

## Placement Papers - Technical & HR Questions

85 docs|57 tests

Track your progress, build streaks, highlight & save important lessons and more!

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

;