Bloomberg LP Interview Question
InternsCountry: United States
Interview Type: Phone Interview
You have to use related subtraction... that is the way to get the 5 ... I wrote a simple code below showing it ..
public void test() {
int i = 123456789;
int r = reverse(i);
System.out.println(r);
}
private int reverse(int i) {
int r = 0;
int d = 10;
int s = 0;
while(i > 0){
int remainder = i % 10;
r = (r * 10) + remainder;
s = 0;
while(i > 10){
i -= d;
s++;
}
i = s;
}
return r;
}
/* Here is the code without using / and & operators...
Complexity is O(d) where d is the number of digits.
Since for every digit the inner for loop can take atmost 10 units of time which is constant */
int revInt(int in) {
int ten = 10, ans = 0, prevDigit = 0, i = 0, nTen, sTen = 1;
while (sTen < in) {
nTen = (in % ten) - prevDigit;
for (i = 0; nTen > 0; i++, nTen -= sTen);
ans = ans * 10 + i;
prevDigit = (in % ten);
ten = ten * 10;
sTen = sTen * 10;
}
return ans;
}
1. Convert it to a string.
2. Read the string character-wise and push each character on the stack
3. Pop the stack and print the answer (reversed string)
how do u convert to a string ..prolly using "/" and "%"...so not sure if this is the way
I think the key is how to get the every digits in the number. eg. how we get 5 in 756. We could use this way:
756%10 = 6 => 756-6 = 750 => 750%100=50 => and then we get 5 to use operator +
int k = 0;
int n = 0;
while(n<50){n+=10;k++}
At the end , k will be 5.
We could use the same method to get 7...
int main()
{
int inumber,i;
scanf("%d",&inumber);
char pNumber[10];
printf(" Number:%d",inumber);
sprintf(pNumber, "%d", inumber);
int iLength=strlen(pNumber);
char temp;
for(i=0;i<iLength;i++)
{
temp=pNumber[i];
pNumber[i]=pNumber[iLength-1];
pNumber[iLength-1]=temp;
iLength--;
}
inumber=atoi(pNumber);
printf("\n\nReverse no is %d",inumber);
return 0;
}
#include<stdio.h>
int main()
{
int a;
printf("Enter the number to be reversed:");
scanf("%d",&a);
int c_mod=0,k=10,b=0,flag=0;
float j=0.1,i=10,temp;
while(a)
{
flag=0;
j=0.1;
c_mod=a%k;
j=j*k;
i=j;
temp=i;
if(i<c_mod)
{
while(i<c_mod)
{
i+=j;
flag++;
}
}
if(c_mod == temp)
{
b=(b*10)+1;
a = a - c_mod;
if(!a)
break;
}
else if(flag)
{
b=(b*10)+(flag+1);
a = a - c_mod;
}
else
{
b=(b*10)+c_mod;
a = a - c_mod;
}
k=k*10;
}
printf("The reversed disgit is:%d\n",b);
}
#include<stdio.h>
#include<conio.h>
#include<string.h>
int main(){
int num;
char str[10];
char str1[10];
int i;
printf("\n Enter the number");
scanf("%d",&num);
sprintf(str, "%d", num);
int len = strlen(str);
printf("\n %s",str);
for(i=0;str[i]!='\0';i++){
str1[i]=str[len-1-i];
}
str1[i]='\0';
printf("\n %s",str1);
getch();
return 0;
}
# include <iostream>
# include <sstream>
# include <stack>
using namespace std;
int reverse_number(int number) {
stack<char> charStack; string str;
string strText = static_cast<ostringstream*>( &(ostringstream() << number) )->str();
for(int i = 0; i< strText.size(); ++i) charStack.push(strText[i]);
while(!charStack.empty()) { str+=charStack.top(); charStack.pop(); }
int result; istringstream(str) >> result;
return result;
}
int main() {
int number = 756;
cout << reverse_number(number);
return 0;
}
None of the above answers are correct. Convert to string, reverse the characters and then convert back to value is not allowed. Repeatedly subtracting 10 is not efficient.
The correct answer is that although you are not allowed to divide by 10, you are allowed to right shift bits, which is equivalent to divide. So consider that
X / 10 = X * (1/10) = X*(2^N/10)/2^N = (X*(2^N/10))>>N
Pick a reasonable N, like N=9. The calculation becomes:
X/10 = (X*(512/10))>>9 ~= (X*51)>>9
This is only approximately but gets you pretty much close to using divide directly.
So original number is 756:
(756*51)>>9 = 38556>>9 = 75 which is the quote.
We check the remainder:
756 - 75*10 = 6, which is within expected range 0 to 9. If it is not you increment the quote and try again. In this case we successfully split 756 into 75x10 + 6.
Next (75*51)>>9 = 7, the quote,
and the remainder is:
75 - 7x10 = 5, which looks good.
This is a powerful technique to convert expensive division to merely multiplication and shift right. I use this trick a lot.
since "/" is not allowed, first convert the number to a string, then iterate the string from last to first character. In java, the code should be like:
int result = 0;
for(int i = str.length() - 1; i >= 0; i--){
result = result * 10 + str.charAt(i) - '0';
}
We should consider the overflow situation as the reversed number may be larger than the max value of integer.
With Given Constraints.. the only Solution is the pointer.
1> Point to given integer.
2> Read value from the pointer and advance to next after putting the value to the Link List.
3> Reverse the list.
4> Read the value of the list and put it into the integer.
If you read value from an integer pointer you get the entire number .. How are you getting the individual digits out??
Don't need to convert to String .. do it using %, * and + operators :)
- marcelovox2 January 23, 2013Keep in mind -> 756 %10 = 6 .. (6 * 10) + 5 = 65 ... so you can come up with the algorithm :)