Amazon Interview Question
Software Engineer in TestsCountry: United States
Interview Type: Phone Interview
Hey, my frd, do you mind to take a look at the question about k-majority of A?
careercup.com/question?id=14507684
Isn;t the answer to the particular example - 0123.344?
One soln i can think of:
convert float to char array
save index of "." of char array
sort the array
insert index in position
One more step for your sol
if the first digit is 0, then search the array from left to right,until you hit a digit tat is not 0, then swap them.
eg: 103.00005 -->0000.0135-->1000.0035
it sounds like a good sol, but how will you convert a float to char array...I tried to use sprintf.
float a = 3912.415;
char buffer[50];
sprintf(buffer,"%f",a);
cout<< buffer<<endl;
the output is 3912.415039.. if I want to get the correct result, i need to write
sprintf(buffer,"%.3f",a);
so i am confused how can i get the number of bits that after the dot.
1. Get integer part of the data.& store in a int var.
2. Get Fraction part of the data & store in a float var
3. build a hashmap for digit 0 to 9
4.keep dividing the number till zero & inclement the count in the map.
5. Form a number by using the count of each digit such that it shld give give smallest integer...
6. add fraction to get float number...
Function signature says that argument should be 'float'
But converting float to string will face the storage problem.
In my computer .434 detects as .434082
So, to be specific a precision is required as argument. Otherwise we take the input as char array and returns it as char array to remove the storage problem.
Another thing is that if .00053 is the input then output should be the same.
If 1.00059 is the input then output should be the 1.00059. Because 0 in the most significant digit considered is not considered as significant.
float reversePoint(float num){
//returning 0 if number is zero
if(num == 0.0)return 0;
boolean intFlag = false;
boolean negFlag = false;
// checking if number is negative
if(num < 0){
num *= -1;
negFlag = true;
}
float num1=num;
int intNum=(int)num1;
float diff=num1-intNum;
//check if number doesn't have any number after decimal point i.e. it is like 2134.0
if(diff==0.0f)
intFlag=true;
int pos = 0;
//multiply number by zero till it becomes xxx.0 format...
if(!intFlag){
while(num%10 != 0){
num = num * 10;
pos++;
}
num = num / 10;
}
List<Integer> l = new ArrayList<Integer>();
//adding digits to list
while(num>10)
{
l.add((int)num%10);
num = num/10;
}
l.add((int)num);
if(num1 > 0 && num1 <1){
l.add(0);
}
pos = l.size() + 1 - pos;
System.out.println(pos);
//sort the list for negative decreasing order and for positive increasing order
if(negFlag){
Collections.sort(l, Collections.reverseOrder());
}else{
Collections.sort(l);
}
// skipping starting zeros in sorted list
int j = 0;
while(l.get(j) == 0){
j++;
}
//putting non-zero smallest number first
String res = ""+l.get(j);
//appending all zeroes
for(int i = 0; i <j ; i++){
if(res.length() == pos ) res += ".";
res += l.get(i);
}
//appending all d non-zeroes
for(int i = j+1; i < l.size() ; i++){
if(res.length() == pos ) res += ".";
res += l.get(i);
}
float result = Float.parseFloat(res);
if(negFlag){
result *= -1;
}
return result;
}
This code may not be efficient but it solves the problem....
int main()
{
float f=291.404;
int i=0;
cout<<f<<endl;
ostringstream s3;
s3<<f;
string s1=s3.str();
//cout<<s1.c_str();
istringstream s(s1);
string sf=s.str();
replace(sf.begin(),sf.end(),'.',' ');
istringstream stream(sf);
string a,b;
stream>>a>>b;
//cout<<a<<endl;
//cout<<b<<endl;
sort(a.begin(),a.end());
sort(b.begin(),b.end());
ostringstream ostream1;
ostream1<<a<<'.'<<b;
//cout<<ostream1.str().c_str()<<endl;
string sfinal=ostream1.str().c_str();
if(sfinal[0]=='0')
{
i=i;
while(sfinal[i++]=='0');
swap(sfinal[0],sfinal[i-1]);
}
cout<<sfinal.c_str()<<endl;
return 0;
}
here is java implementation
public static void main(String[] args) {
double val = 3012.434;
//System.out.println(String.valueOf(val));
String strVal = String.valueOf(val);
System.out.println("input "+strVal);
int pos = strVal.indexOf('.');
int len = strVal.length();
char []arr = new char[len-1];
int l = 0;
for (int i = 0; i < len; i++){
if (strVal.charAt(i) !='.'){
arr[l++] = strVal.charAt(i);
}
}
char[] outArr = merge_sort(arr);
char []smlArr = new char[len];
int m = 0;
for (int j=0; j < outArr.length; j++){
if (j == pos)
smlArr[m++] = '.';
smlArr[m++] = outArr[j];
}
System.out.println("smallest float ");
for (int k=0; k<outArr.length; k++)
System.out.print(smlArr[k]);
}
C# Solution:
string s = "3120.434";
char[] array = s.ToArray();
char[] numberPartArray = s.Substring(0, s.IndexOf('.')).ToCharArray();
char[] decimalPartArray = s.Substring(s.IndexOf('.') + 1, s.Length - s.IndexOf('.')-1).ToCharArray();
Array.Sort(numberPartArray);
Array.Sort(decimalPartArray);
String Result = new string(numberPartArray) + "." + new string(decimalPartArray);
#include <sstream>
#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;
int main( )
{
float val = 3.14507;
stringstream ss (stringstream :: in | stringstream :: out);
ss << val;
string test = ss.str();
cout << test << endl;
// initial 2 array for count sort
int HashInt1[10] = {0};
int HashInt2[10] = {0};
int i;
// count sort before the dot
for(i = 0; i < test.length() && test[i]!= '.'; i++ )
{
HashInt1[(int)test[i] - 48] ++ ;
}
// count sort after the dot
for(i = i + 1 ; i < test.length() && test[i] != '\0'; i++)
{
HashInt2[(int)test[i] - 48]++;
}
cout << " the sorted float number is" << endl;
// print the sorted flaot
for(int j = 1 ; j < 10; j++)
{
for(int k = 0; k < HashInt1[j]; k++)
cout << j;
}
cout << '.';
for(int j = 0; j < 10; j++)
{
for(int k = 0; k < HashInt2[j]; k++)
cout << j;
}
cout << endl;
return 0;
}
this code solve the problem that using the buffer may have the problem of extra 0, if there has any problem or any comments feel free to make any comments
thank you
Sorting complexity is nlogn.
- Naveen Reddy Mandadi August 22, 2012Convert the given number to string, say s.
Have an array a of size 10, each value holds the count of number of digits in the number before decimal which are same as the index of the array. That is a[0] will have number of 0s, a[1] will have number of 1s etc.
Also have another variable m which holds the minimum non zero value before decimal.
Loop through the string and update m and a accordingly until you get the decimal or end of string.
Now print m followed by indexes of a, each index repeated the number of times the value it holds.
Similarly do it for digits after decimal, in this case m is not required.
Complexity of this algorithm is O(n) as we are reading each digit only once.