Microsoft Interview Question
Software Engineer / Developers//Problem:
//================
//Reverse an integer array bitwise algorithm
//Example:
//================
//i/p : A[]{1,2,3,4,5}
//o/p: A[]{5,4,3,2,1}
//Process
////===============
//1. Declare Assumptions
//2. Explain algo
//3. take an Example
//4. give testcases
//5. 1st write the solution
//6. then add exception handels and try/catch/finally blocks
//7. Order
//ALGO:
//================
//check for even or odd
//using a swap method swap using XOR swap
//TEST CASES:
//================
//Functional:
//1. empty array
//2. odd/even array
//3. negative numbers
//4. large numbers[32767]
//5. characters
//Non-Functional:
//Performance
//1. same array used multiple time test for time complexity
//Memory
//2. same array tested for multiple time test for memory leakage
//Security
//3. test with array having escape characters
//4. test with array have special char or ASCII values
//Stress
//6. run multiple instance of the method and test for stress
//Load
//7. test with very large array
//Globalisation/localisation
//8. test with unicode char
//9. test with kanji char
//10. test with mix of both characters
//CodeCoverage
//Exception Handelling
//11. test whether exceptions are handelled.
//TEST HARNESS:
//================
using System;
namespace problem
{
public class answer
{
static void Main()
{
int[] A=new int[5]{1,2,3,4,5};
bitreverse(A);
Console.ReadLine();
}
//CODE:
//================
public static void bitreverse(int[] A)
{
try
{
int j=A.Length-1;
if(j%2==0)
{
for (int i=0;j-i>=1;i++)
{
A[i]=A[i]^A[j];
A[j]=A[i]^A[j];
A[i]=A[j]^A[i];
j--;
}
}
else
{
for (int i=0;j-i>0;i++)
{
A[i]=A[i]^A[j];
A[j]=A[i]^A[j];
A[i]=A[j]^A[i];
j--;
}
}
for(int i=0;i<A.Length;i++) //Printing the Array
{
Console.Write(A[i]);
}
}
catch(Exception ex)
{
Console.WriteLine(ex);
}
}
}}
//ORDER:
//================
//O(N)
What the hell...
asking such stupid questions does not determine the true capacity of the candidate.
Microsoft would ask such questions even for experienced candidates; often disappointing.
The only reason to join Microsoft is for the pay package.
There is better respectful work elsewhere.
While attending interview at Microsoft; do everything as stated above; often will land up impressing the person taking your interview.
1. Try to talk whatever is in your head
2. Ask questions to make everything clear - often questions are stupid; they expect you to ask fro clarifications
3. Think and discuss all the test cases first << this impresses
4. Think and discuss all the possible solutions
5. choose the best solution - for all test cases discussed
6. implement the solution in code
7. insert exception handling to finally impress
Done; -- get a 18+ lac package at Microsoft
get a horrible job; but who cares; one would be even ready to sweep at microsoft at that package
I have never liked Microsofts approach; they generally choose ppl whom they like - nothing to do with the experience and real-code-solving ability.
Its like asking someone questions related to "field-X" and hiring for some other "field-Y"
Never loose you cool; when confronted with stupid questions; remember its all about money; keep quite; behave like you are giving some school test and you will get through - guaranteed.
Why do you judge a question as if that is the only question ppl will ask in the interview and judge solely based on that?
If a candidate does not get this, this is an easy reject. Perhaps it was a phone screen question?
I think it is stupid to judge questions out of context.
Why the rant? Were you rejected by Microsoft at some point in time?
@Tarun - Not get into your code but the expected output is incorrect. This program didnt ask for reverse the array. It asked to reverse the bits as well.
I think the question is to reverse the array using bit wise operators. SO I think the approach used by Tarun is correct.
@Tarun
You have used an if condition to determine if the number of elements in the array. Based on that you run the loop to differently. Another option would be
i=0;
len= size of array -1;
while(i<=len)
{
//swap
//i++;
//len --;
}
Now the code is more compact
int* reverse(int* arr, int n)
{
if(n<0)
return arr;
else
{
int s = 0;
int e = n-1;
for(s=0;e>s;s++,e--)
{
arr[s] ^= arr[e];
arr[e] ^= arr[s];
arr[s] ^= arr[e];
}
return arr;
}
}
basically doing bitwise XOR operation, there by needing no temp to swap the numbers. bit faster than recursive though
Following function works fine for approach given above.
size is size of array and *in is starting address of integer array.
void reversebits2 (int *in, int size)
{
int x=0,m,n,z;
for (x=0;x< (size *32)/2 ;x++)
{
m= x/32;
z=(size*32)-1-x;
n=z/32;
if ((((*(in +m)) >>(x- 32*m)) & 1) ^ (((*(in+n)) >>(z-32*n)) & 1)) // check whether bits are different and need to be flipped
{
(*(in+n)) ^= (1<<(z -32*n));
(*(in +m)) ^= (1<<(x-32*m));
}
}
}
void Reverse(int * inputArray, int size){
- ankushbindlish March 14, 2010if(inputArray == null || size <0) throw new ArgumentException("Invalid input");
for(int i=0;i<size;i++)
inputArray[i] = Rotate(inputArray[i]);
Reverse(inputArray);
}
int Rotate(int num){
int result;
while(num){
result = (result << 1) || (num &1);
num >>=1;
}
return result;
}
void Reverse(int * inputArray, int size){
if(inputArray == null || size <0) throw new ArgumentException("Invalid input");
for(int i=0;i<size/2;i++)
Swap(&inputArray[i] , &inputArray[size-1-i]);
}
void Swap(int &a, int &b){
a = a+b;
b= a-b;
a= a-b;
}