Microsoft Interview Question Software Engineer / Developers
Team: Bing
Country: India
Interview Type: In-Person
@ric: As abhishekatuw corrected it is actually 8*sizeof(int). But if are talking about total number of bits, you may add the code for bounds checking, because if k > sizeof(int)*8, all bits will be tossed out of the number.
if k is greater than 32, then after each 32 shift operations you will be left with the same number.
do something like
if(k > 32)
k %= 32;
if(k == 0) return num;
else
//do what cooldaa did
if k > 8*sizeof(int), expression (8*sizeof(int) - k) will become negative. The compiler will then flag runtime error as the right operand of shift operators has to be a positive integral quantity.
in here,
(num << k) | (num >> (sizeof(int) - k));
when u do num << k, then aren't yo u already loosing the k bits ? since, it will pad them with 0's. So when it reaches (num >> (sizeof(int) - k), num is changed already, with k bits lost ! So,, wont be a cyclic shift.
Am I missing something ?
int circular_shift(int num, int k, char dir) {
int n = 1;
if (dir) //assume dir = 1 for left shift
n = ~n; // for left shift, n will hold 1 in the highest bit position
while(k--) {
if(dir) {
if(num&n) //if highest bit holds 1;
num = num<<1 + 1; //then add 1 to the left shift
else num = num<<1; //otherwise, just simply shift
} else {
if(num&n) //if lowest bit holds 1
num = (num>>1) | ~n; //add 1 to highest bit
else num = num>>1; //otherwise just make simple right shift
}
}
}
#include <iostream>
#include <cstdlib>
#include <intrin.h>
#pragma intrinsic(_rotr8, _rotr16)
int main()
{
int inputInteger = 376;
unsigned int offset = 3; // bits to roate
std::cout << " Original Number: " << inputInteger << "\n";
inputInteger = _rotr16(inputInteger, offset);
//inputInteger = _rotl16(inputInteger, offset); // for left rotate
std::cout << " Rotated Number: " << inputInteger << "\n";
getchar();
return 0;
}
/**
@shpos - how many positions to shift (left or right)
@dir - left (-1) or right(1) shift
*/
int cyclic_shift(int num, int shpos, int dir)
{
int retv;
if ((0 == shpos) || (sizeof(int) * CHAR_BIT == shpos))
return num;
/* Prevent losing any bit of the original value */
shpos = shpos % (sizeof(int) * CHAR_BIT);
if (dir > 0) // the right cyclic shift
retv = (num >> shpos) | ( num << (sizeof(int) * CHAR_BIT - shpos));
else // the left cyclic shift
retv = (num >> ( sizeof(int) * CHAR_BIT - shpos )) | (num << shpos);
return retv;
}
def maximizeProfit(input):
maxDiff = float("-inf")
currentDiff = float("-inf")
bottom = input[0]
max = 0
for index in range(1,len(input)):
currentDiff += input[index] - input[index-1]
if (currentDiff > maxDiff):
maxDiff = currentDiff
max = input[index]
if (bottom > input[index]):
print(currentDiff)
bottom = input[index]
currentDiff = 0
print("buy at :"+str(max - maxDiff)+ " Sell at: "+str(max))
- cooldaa January 22, 2012circular_shift(int num, int k, int dir) { if(dir) //assume dir = 1 for left shift return (num << k) | (num >> (sizeof(int) - k)); else return (num >> k) | (num << (sizeof(int) - k)); }