Amazon Interview Question for Software Engineer in Tests


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
8
of 8 vote

Sorting complexity is nlogn.
Convert 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.

- Naveen Reddy Mandadi August 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

yeap, counting sort

- Vincent August 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hey, my frd, do you mind to take a look at the question about k-majority of A?

careercup.com/question?id=14507684

- Vincent August 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

careercup.com/question?id=14507684 looks good generically for any k, but given the special case like this array is preferable to hash table. Though the get operation in hash table is O(1) it is only an ideal case, but array get by index is always O(1).

- Anonymous August 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- Gautam August 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Vincent August 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Evan August 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Java :String strAmount=String.valueOf(amount);

- Vincent August 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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...

- atul gupta August 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Evan, Best way is to take the input itself as string rather than float.

- Cerberuz August 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@atul gupta: can u elaborate ur explanation?

- programmer August 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Evan : function signature should not be changed.

- krish August 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Gautam
0 in the left should not be considered as significant. So the left most visit has to be a minimum of all the digits that appeared in the float except 0.

- Psycho August 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

- Psycho August 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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....

- Aniket August 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Abhishek August 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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]);
}

- mamtest August 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);

- Hemant August 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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

- Lisa March 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Its a c++ implementation

- Lisa March 08, 2013 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More