Amazon Interview Question SDETs
Country: India
Interview Type: Phone Interview
The interviewer asked me to use hashMap.
I am able to count the number using HashMap but how will you print based on the count ?
Hi, Let me try
Lets assume the following:
Count of digit 0 is ----- x0
Count of digit 1 is ----- x1
Count of digit 2 is ----- x2
Count of digit 3 is ----- x3
Count of digit 4 is ----- x4
Count of digit 5 is ----- x5
Count of digit 6 is ----- x6
Count of digit 7 is ----- x7
Count of digit 8 is ----- x8
Count of digit 9 is ----- x9
Lenth of given number is --- n
Take a constant ---- k (I will explain why we needed)
So, the following is true for every digit :
x0<=n, x1<=n, x2<=n, x3<=n, x4<=n, x5<=n, x6<=n, x7<=n, x8<=n, x9<=n (Consider the count is positive integer only) --- > 0<=xi<=n
x0+x1+x2+x3+x4+x5+x6+x7+x8+x9 = n
Time complexity to access Hash Table:
Here there are two types of cells will be there in our hash table/hash map,
1) Cell of Hash table with zero counts
2) Cell of Hash table with Non-zero counts
Lets assume Number of accesses for each cell of hash table is “ai”
for 0th index ---- a0; 1<=a0<=n
For 1st index -- a1; 1<=a1<=n
…………….
And so on to --a9
So, the total accesses will be: a0+a1+a2+a3+………a9 >=n
Lets put it in this way:
a0+a1+a2+a3+………a9 =n+k
Here, n is to access cells with non-zero count of hash table, k is to access cells with zero count.
Lets take an example:
1) 999999999999999
Hash table = (0 0 0 0 0 0 0 0 0 15)
Accessing time = 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*15
= 15 + 9
= O (n + k), always k<=n
= O(n)
2) 999999998883210
Hash table = (1 1 1 1 0 0 0 0 3 8)
Accessing time = 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*3 + 1*8
= 15 + 4
= O(n + k), always k<=n
= O(n)
I know that It was lengthy, I Just tried to analyse :)
Correct me If I am wrong
Srinu
Hi, Let me try
Lets assume the following:
Count of digit 0 is -----> x0
Count of digit 1 is -----> x1
Count of digit 2 is -----> x2
Count of digit 3 is -----> x3
Count of digit 4 is -----> x4
Count of digit 5 is -----> x5
Count of digit 6 is -----> x6
Count of digit 7 is -----> x7
Count of digit 8 is -----> x8
Count of digit 9 is -----> x9
Lenth of given number is ---> n
Take a constant ----> k (I will explain why we needed)
So, the following is true for every digit :
x0<=n, x1<=n, x2<=n, x3<=n, x4<=n, x5<=n, x6<=n, x7<=n, x8<=n, x9<=n (Consider the count of each digit is positive integer only) --- > 0<=xi<=n
x0+x1+x2+x3+x4+x5+x6+x7+x8+x9 = n
Time complexity to access Hash Table:
Here there are two types of cells will be there in our hash table/hash map,
1) Cell of Hash table with zero counts
2) Cell of Hash table with Non-zero counts
Lets assume Number of accesses for ith cell of hash table is “ai”
i.e..., For 0th index ----> a0; 1<=a0<=n
For 1st index ----> a1; 1<=a1<=n
…………….
And so on upto --a9
So,
the total accesses will be: a0+a1+a2+a3+………a9 >=n
Lets put it in this way:
a0+a1+a2+a3+………a9 =n+k
Here, n is to access cells with non-zero count of hash table, k is to access cells with zero count.
Lets take an example:
1) 999999999999999
Hash table = (0 0 0 0 0 0 0 0 0 15)
Accessing time = 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*15
= 15 + 9
= O (n + k), always k<=n
= O(n)
2) 999999998883210
Hash table = (1 1 1 1 0 0 0 0 3 8)
Accessing time = 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*3 + 1*8
= 8 + 3 + 8
= 15 + 4
= O(n + k), always k<=n
= O(n)
Correct me If I am wrong, I Just tried to analyse
well, give me an example.
is it the following ????
input: -8754365
output: -3455678
if so, follow the same algo, print the numbers in the map from o'th index to last.
Instead of using a hashmap, you can just use an array of size 10, where array[i] is the count of the digit i.
Thanks, and I know that. Just given the answer with that so called Hash Table, so continued with it :) :P
def sort(value):
map = {}
result = ""
print "input", value
for i in value:
if i in map.keys():
map[i] += 1
else:
map[i] = 1
for i in range(9, -1, -1):
i = str(i)
while i in map.keys() and map[i] > 0:
result += i
map[i] = int(map[i]) -1
return result
result = sort("1244522398968")
print "output", result
public static int getMax(int num) {
String arr[] = new String[10];
Arrays.fill(arr, "");
int index = 0;
while (num > 0) {
index = num % 10;
arr[index] += index;
num = num / 10;
}
String result = "";
for (int i = arr.length - 1; i >= 0; i--) {
result += arr[i];
}
return Integer.parseInt(result);
}
Perhaps you can use a binary search tree and as you are doing an in order tree traversal push all the numbers into a queue. The number contained in the queue is the largest number.
// find maximum number using digits
public void maxNum(){
int input = 567443;
ArrayList inputList = new ArrayList();
String str = Integer.toString(input);
for(int i=0; i<str.length(); i++){
inputList.add(str.charAt(i));
}
Collections.sort(inputList);
String str1 = "";
for(int i=str.length()-1; i>=0; --i){
str1 += inputList.get(i);
System.out.println("str = "+str1);
}
System.out.println("output = "+str1);
}
// find maximum number using digits
public void maxNum(){
int input = 567443;
ArrayList inputList = new ArrayList();
String str = Integer.toString(input);
for(int i=0; i<str.length(); i++){
inputList.add(str.charAt(i));
}
Collections.sort(inputList);
String str1 = "";
for(int i=str.length()-1; i>=0; --i){
str1 += inputList.get(i);
System.out.println("str = "+str1);
}
System.out.println("output = "+str1);
}
Counting sort via array of counts seems the simplest solution and in O(n).
So you're on the right track thinking about merge/quicksort, however just need to keep in mind that there are certain faster sorting methods that can be applied in special situations (other popular ones include bucket and radix sort).
public static void main(String[] args) {
Map<Integer, Integer> mp = new HashMap<>();
mp.put(0, 0);
mp.put(1, 0);
mp.put(2, 0);
mp.put(3, 0);
mp.put(4, 0);
mp.put(5, 0);
mp.put(6, 0);
mp.put(7, 0);
mp.put(8, 0);
mp.put(9, 0);
String num = "78549203390";
for (char ch : num.toCharArray()) {
int i = Integer.valueOf(Character.toString(ch));
if (mp.containsKey(i)) {
int val = mp.get(i);
mp.put(i, ++val);
}
}
StringBuilder maxNum = new StringBuilder();
for (int key = 9; key >= 0; key--) {
if (mp.containsKey(key)) {
for (int i = 0; i < mp.get(key); i++) {
maxNum.append(key);
}
}
}
System.out.println(maxNum);
}
public static long MaxIntergerFromAlgarithmsIn(long x){
long tens = 1;
while(tens <= x)
{
tens*=10;
}
int[] hist = new int[10];
for(long t = tens; t>=1 ;t /=10){
hist[x/t]++;
x -= (x/t)*t;
}
long res = 0;
for(int j = 9 ; j>=0 ; --j){
while(hist[j]>0){
tens /=10;
res += tens*j;
hist[j]--;
}
}
return res;
}
int _tmain(int argc, _TCHAR* argv[])
{
unsigned long long num = 8754365;
cout << "Orig: " << num << endl;
cout << "Num: " << GetLargestNumber(num) << endl;
cout << "String: " << GetLargestNumberString(num) << endl;
return 0;
}
std::string GetLargestNumberString(unsigned long long num)
{
std::stringstream largestNumberString;
// Count the digit values
int digitArray[10] = {};
while (num > 0)
{
digitArray[num % 10]++;
num /= 10;
}
for (int arrayIndex = 9; arrayIndex >= 0; arrayIndex--)
{
for (int digitCount = 0; digitCount < digitArray[arrayIndex]; digitCount++)
{
if (digitArray[arrayIndex] > 0)
{
largestNumberString << arrayIndex;
}
}
}
return largestNumberString.str();
}
unsigned long long GetLargestNumber(unsigned long long num)
{
unsigned long long largestNumber = 0;
// Count the digit values
int digitArray[10] = {};
while (num > 0)
{
digitArray[num % 10]++;
num /= 10;
}
int power = 0;
for (int arrayIndex = 0; arrayIndex < 10; arrayIndex++)
{
for (int digitCount = 0; digitCount < digitArray[arrayIndex]; digitCount++)
{
if (digitArray[arrayIndex] > 0)
{
largestNumber += arrayIndex * pow(10, power);
power++;
}
}
}
return largestNumber;
}
public static int formLargestNum(int num) {
int[] numArray = new int[10];
while (num > 0) {
int rem = num % 10;
num = num / 10;
numArray[rem] += 1;
}
int output = 0;
for ( int i = 9; i >= 0; i--) {
int count = numArray[i];
while (count > 0) {
output *= 10;
output += i;
count--;
}
}
return output;
}
public static long findMaxNumber(long num)
{
long maxNumber = 0,placeValue=1;
long temp;int count=0;
int hashMap[] = new int[10];
temp = num;
while(temp!=0)
{
hashMap[(int)temp%10]++;
temp=temp/10;
}
for(int i=0;i<hashMap.length;i++)
{
count=hashMap[i];
while(count>0)
{
maxNumber=maxNumber+placeValue*i;
placeValue=placeValue*10;
count--;
}
}
System.out.println(maxNumber);
return maxNumber;
}
import java.util.Scanner;
import java.util.Arrays;
class Arrange
{
public static void main(String[] args)
{
System.out.println("Enter Any Number");
Scanner s=new Scanner(System.in);
String str=s.next();
byte b[]=str.getBytes();
Arrays.sort(b);
System.out.println("The maximum number formed by ur number is..");
String str2=new String(b);
StringBuilder sb=new StringBuilder(str2);
System.out.println(sb.reverse());
}
}
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package amazon.interview;
import java.io.IOException;
import java.util.Arrays;
/**
*
* @author Shrey
*/
public class AmazonInterview {
/**
* @param args the command line arguments
*/
public static void main(String[] args) throws IOException {
// TODO code application logic here
String number="6733465998723145";
String result="";
char array[] = number.toCharArray();
Arrays.sort(array);
for(int i=array.length-1;i>=0;i--){
result=result+array[i];
}
System.out.println(result);
}
}
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package amazon.interview;
import java.io.IOException;
import java.util.Arrays;
/**
*
* @author Shrey
*/
public class AmazonInterview {
/**
* @param args the command line arguments
*/
public static void main(String[] args) throws IOException {
// TODO code application logic here
String number="6733465998723145";
String result="";
char array[] = number.toCharArray();
Arrays.sort(array);
for(int i=array.length-1;i>=0;i--){
result=result+array[i];
}
System.out.println(result);
}
}
package com.javafries.number;
/**
* @author vishal.naik
*/
public class MaximumNumberProblem {
private static int findMaxNumberFromDigits(int num) {
int[] digits = getDigitsInSortedOrder(num);
int maxNum = 0;
for (int index = digits.length - 1; index >= 0; index--) {
int frequency = digits[index];
while (frequency > 0) {
maxNum = maxNum * 10 + index;
frequency--;
}
}
return maxNum;
}
private static int[] getDigitsInSortedOrder(int num) {
int[] digits = new int[10];
while (num > 0) {
// Get remainder
int index = num % 10;
digits[index]++;
num /= 10;
}
return digits;
}
public static void main(String[] args) {
int num = 38293367;
int maxNum = findMaxNumberFromDigits(num);
System.out.println("Maximum number : " + maxNum);
}
}
public class MaximumNumberProblem {
private static int findMaxNumberFromDigits(int num) {
int[] digits = getDigitsInSortedOrder(num);
int maxNum = 0;
for (int index = digits.length - 1; index >= 0; index--) {
int frequency = digits[index];
while (frequency > 0) {
maxNum = maxNum * 10 + index;
frequency--;
}
}
return maxNum;
}
private static int[] getDigitsInSortedOrder(int num) {
int[] digits = new int[10];
while (num > 0) {
// Get remainder
int index = num % 10;
digits[index]++;
num /= 10;
}
return digits;
}
public static void main(String[] args) {
int num = 38293367;
int maxNum = findMaxNumberFromDigits(num);
System.out.println("Maximum number : " + maxNum);
}
}
package com.javafries.number;
/**
* @author vishal.naik
*/
public class MaximumNumberProblem {
private static int findMaxNumberFromDigits(int num) {
int[] digits = getDigitsInSortedOrder(num);
int maxNum = 0;
for (int index = digits.length - 1; index >= 0; index--) {
int frequency = digits[index];
while (frequency > 0) {
maxNum = maxNum * 10 + index;
frequency--;
}
}
return maxNum;
}
private static int[] getDigitsInSortedOrder(int num) {
int[] digits = new int[10];
while (num > 0) {
// Get remainder
int index = num % 10;
digits[index]++;
num /= 10;
}
return digits;
}
public static void main(String[] args) {
int num = 38293367;
int maxNum = findMaxNumberFromDigits(num);
System.out.println("Maximum number : " + maxNum);
}
}
public class MaxNumberFromDigits{
public static void main(String[] args){
String s = "8754365";
int[] digits = new int[10];
char[] max = new char[s.length()];
for(int i=0; i<s.length(); i++){
int value = Character.getNumericValue(s.charAt(i));
System.out.println(value);
digits[value] += 1;
}
int digitsLen = digits.length;
int k=0;
for(int i=digitsLen-1; i>=0; i--)
for(int j=0; j<digits[i]; j++){
max[k++] = String.valueOf(i).charAt(0);
}
String maxS = new String(max);
System.out.println(maxS);
}
}
/*
* Given "input" digits, spits out the largest valued number that can be formed
* using those digits.
*/
int main()
{
int input;
int output = 0;
int arr[10];
int i;
printf("Enter the digits: ");
scanf("%d", &input);
for (i = 0; i < 10; i++) {
arr[i] = 0;
}
while (input != 0) {
arr[input % 10]++;
input /= 10;
}
for (i = 9; i >= 0; i--) {
while (arr[i] != 0) {
output = output * 10 + i;
arr[i]--;
}
}
printf("\nOutput: %d\n", output);
return 1;
}
/*
* Given "input" digits, spits out the largest valued number that can be formed
* using those digits.
*/
int main()
{
int input;
int output = 0;
int arr[10];
int i;
printf("Enter the digits: ");
scanf("%d", &input);
for (i = 0; i < 10; i++) {
arr[i] = 0;
}
while (input != 0) {
arr[input % 10]++;
input /= 10;
}
for (i = 9; i >= 0; i--) {
while (arr[i] != 0) {
output = output * 10 + i;
arr[i]--;
}
}
printf("\nOutput: %d\n", output);
return 1;
}
/*
* Given "input" digits, spits out the largest valued number that can be formed
* using those digits.
*/
int main()
{
int input;
int output = 0;
int arr[10];
int i;
printf("Enter the digits: ");
scanf("%d", &input);
for (i = 0; i < 10; i++) {
arr[i] = 0;
}
while (input != 0) {
arr[input % 10]++;
input /= 10;
}
for (i = 9; i >= 0; i--) {
while (arr[i] != 0) {
output = output * 10 + i;
arr[i]--;
}
}
printf("\nOutput: %d\n", output);
return 1;
}
int main()
{
int n,j = 0; int hashtab[10];
bool NEG_VAL = false;
printf("Enter the number = ");
scanf("%d", &n);
if(n < 0)
{
NEG_VAL = true;
n = n * -1;
}
for(j=0;j<10;j++)
{
hashtab[j] = 0;
}
while(n > 0)
{
j = n%10;
hashtab[j] = hashtab[j] + 1;
n = n/10;
}
if(NEG_VAL)
{
printf("Highest number formed = -");
for(j=1;j<=9;j++)
{
while(hashtab[j] > 0)
{
printf("%d", j);
--hashtab[j];
}
}
printf("\n");
}
else
{
printf("Highest number formed = ");
for(j=9;j>=0;j--)
{
while(hashtab[j] > 0)
{
printf("%d", j);
--hashtab[j];
}
}
}
printf("\n");
return 0;
}
import java.util.*;
class MaxNo1 {
static void findMax(int no)
{
String str="";
ArrayList<Integer> al=new ArrayList<Integer>();
int temp=0,count=0;
while(no>0)
{
temp=no%10;
no=no/10;
al.add(temp);
}
Collections.sort(al);
for(int a:al)
{
str=a+str;
}
System.out.println(str);
}
public static void main(String[] args)
{
int no=81098374; //9874310
findMax(no);
}
}
import java.util.*;
public class MaxNo {
static void findMax(int no)
{
LinkedHashMap<Integer,Integer> map=new LinkedHashMap<Integer,Integer>();
map.put(1,0);
map.put(2,0);
map.put(3,0);
map.put(4,0);
map.put(5,0);
map.put(6,0);
map.put(7,0);
map.put(8,0);
map.put(9,0);
map.put(0,0);
int temp=0,count=0;
while(no>0)
{
count=0;
temp=no%10;
no=no/10;
count=map.get(temp);
map.put(temp, ++count);
}
Set<Integer> set=map.keySet();
String str="";
for(int i:set)
{
count=0;
count=map.get(i);
while(count>0)
{
str=i+str;
--count;
}
}
}
public static void main(String[] args)
{
int no=123150;
findMax(no);
}
}
import java.util.*;
public class MaxNo {
static void findMax(int no)
{
LinkedHashMap<Integer,Integer> map=new LinkedHashMap<Integer,Integer>();
map.put(0,0);
map.put(1,0);
map.put(2,0);
map.put(3,0);
map.put(4,0);
map.put(5,0);
map.put(6,0);
map.put(7,0);
map.put(8,0);
map.put(9,0);
int temp=0,count=0;
while(no>0)
{
count=0;
temp=no%10;
no=no/10;
count=map.get(temp);
map.put(temp, ++count);
}
Set<Integer> set=map.keySet();
String str="";
for(int i:set)
{
count=0;
count=map.get(i);
while(count>0)
{
str=i+str;
--count;
}
}
}
public static void main(String[] args)
{
int no=123150;
findMax(no);
}
}
class SolutionMaximumNumberFormed {
public long solution(long num) {
if (num == 0) {
return 0;
}
long temp = num;
if(num < 0) {
temp = temp * -1;
}
int[] arr = new int[10];
while (temp != 0) {
System.out.print("TEMP: " + (int) (temp % 10) + "\t BEFORE: " + arr[(int) (temp % 10)]);
int x = (int) (temp % 10);
arr[x] = arr[x] * 10 + x;
System.out.print("\t AFTER: " + arr[x]);
System.out.println();
temp = temp / 10;
}
int start = arr.length - 1;
int end = 0;
if(num < 0) {
start = 0;
end = arr.length;
}
String out = "";
while(start != end) {
if (arr[start] != 0) {
out = out + arr[start];
}
if(num < 0) {
start++;
} else {
start--;
}
}
if(num < 0) {
return Long.parseLong(out) * -1;
}
return Long.parseLong(out);
}
}
public class MaximumNumberFromedFromDigits {
public static void main(String[] args) {
SolutionMaximumNumberFormed mSol = new SolutionMaximumNumberFormed();
System.out.println(mSol.solution(87543655));
System.out.println(mSol.solution(0));
System.out.println(mSol.solution(123456789));
System.out.println(mSol.solution(999999999));
System.out.println(mSol.solution(889922443));
System.out.println(mSol.solution(-889922443));
}
}
Sort the number in descending order.
public static int sortIntDescending(int num) {
String sort = "";
for (int l = 9; l >= 0; l--) {
int rem = num % 10;
int tx = num / 10;
while (tx != 0) {
if (rem == l)
sort+=String.valueOf(rem);
rem = tx % 10;
tx = tx / 10;
}
}
return Integer.valueOf(sort);
}
/*
* Given a Integer, find the maximum number that can be formed from the digits.
Input : 8754365
output : 8765543
I told solution in nlogn. He asked me optimize further.
*/
public class Amazon_SDET_maximum_number {
public static void main(String[] args) {
int[] array = new int[10];
int n = 866487256;
int temp = n;
int rem = 0;
while(temp > 0){
rem = temp%10;
temp = temp/10;
array[rem]++;
}
String result = "";
for(int i = array.length-1; i>=0; i--){
while(array[i] >= 1){
result = result + i;
array[i]--;
}
}
System.out.println(result);
}
}
We can use Hash Table to optimize further, --> O(n)
- Srinu Kolukuluri March 20, 2015Algorithm:
1. Take a hash table with size 10 (0 to 9).
2. Store the count of every digit from 0 to 9.
3. Print the index of the Hash table with respect to digit count in the reverse direction (from 9 to 0).
Example:
Hash table after digit count for 8754365 -> (0 0 0 1 1 2 1 1 1 0)
Print the index of the hash table with respect to their count in reverse order -> 8765543
Time Complexity : O(n)
Correct me if I am wrong.
thanks