OptionsCity Interview Question for Software Engineers

Country: United States
Interview Type: Written Test

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

``````int get_largest_num(int num)
{
int digit_counts[10] = {0};
while (num > 0)
{
++digit_counts[num % 10];
num /= 10;
}

int largest_num = 0;
for (int digit = 9; digit >= 0; --digit)
{
for (int i = 0; i < digit_counts[digit]; ++i)
{
largest_num = largest_num * 10 + digit;
}
}

return largest_num;
}``````

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

We basically need to perform a sort here, the result should be our greatest number.
Counting sort is a fit here.
The only additional space we need here is a bucket of size 10, which is technically still O(1) space. The time complexity will be O(n) where n is the number of digits.

``````public static int getGreatestNumber(int a)
{
if(a<=0)
return Integer.MIN_VALUE;

int[] bucket = new int[10];
int currentNumber = a;
int modNumber = 0;
int numberOfDigits = 0;

while(currentNumber>0)
{
modNumber = currentNumber % 10;
bucket[modNumber]++;
currentNumber=currentNumber/10;
numberOfDigits++;
}

int multiplier = (int) Math.pow(10, numberOfDigits-1);
int res = 0;
int temp = 0;

for(int i=9;i>=0;i--)
{
temp = bucket[i];
while(temp>0)
{
res += i*multiplier;
multiplier /=10;
temp--;
}
}
return res;
}``````

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

Not radix sort. Counting sort. But the requirement for O(n) time is a giveaway. Radix, counting or bucket are your options.

Comment hidden because of low score. Click to expand.
0

Yep. Counting solution was what I meant to say. <edited> :)

Comment hidden because of low score. Click to expand.
0

Good one!!

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

``````int get_largest_num(int num)
{
int digit_counts[10] = {0};
while (num > 0)
{
++digit_counts[num % 10];
num /= 10;
}

int largest_num = 0;
for (int digit = 9; digit >= 0; --digit)
{
for (int i = 0; i < digit_counts[digit]; ++i)
{
largest_num = largest_num * 10 + digit;
}
}

return largest_num;
}``````

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

/*A C# solution using Linq*/
string s = "9323923712999";
char[] ch = s.ToCharArray();
//IEnumerable<char> query = ch.OrderByDescending(n => n).Select(n=>n);
//OR
IEnumerable<char> query = from c in ch orderby c descending select c;
foreach (char c in query)
Console.Write(c);

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

/*Solution using C# Linq*/
string s = "9323923712999";
char[] ch = s.ToCharArray();
//IEnumerable<char> query = ch.OrderByDescending(n => n).Select(n=>n);
//OR
IEnumerable<char> query = from c in ch orderby c descending select c;
foreach (char c in query)
Console.Write(c);

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

``````from array import array

def maxdigits(num):
result = 0
bins = array('i', (0,) * 10)
while num:
bins[num % 10] += 1
num //= 10
for k in range(9, -1, -1):
while bins[k] > 0:
result = result * 10 + k
bins[k] -= 1
return result``````

O(1) space, O(n) time

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

Taking a look, I think to accomplish the expected time/space O(1), an approach it's to try solve the problem using bit operations. Suggestions?

Comment hidden because of low score. Click to expand.
0

I don't think so. It requires a minimum O(n) just to read the digits.

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

This can be done by counting the instances of each digit and then recombining it with the larger characters first. It will operate with O(1) memory, stores a 10 int array, and iterates over the ints to for a runtime complexity of O(n) where n is the number of digits in the array.

``````public static int maxFromDigits(int num){
//count the digits
int[] digits = new int[10];
while(num > 0){
digits[num % 10] ++;
num /= 10;
}
//compose the largest integer possible
for(int i = 9; i > -1; i--){
while(digits[i] > 0){
num *= 10;
num += i;
digits[i]--;
}
}
return num;
}``````

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

Count all the 1 bits in the number and make them Most SIgnificant Bits.

``````private int greatestPositiveInteger(int input)
{
int countOf1 = 0;
int countBits = 0;
while(input>0)
{
int bit = input%2;
if(bit==1)
countOf1++;
countBits++;
input/=2;
}

int toReturn = 0;
for(int i=0;i<countOf1;i++)
{
toReturn+=Math.pow(2, countBits-1);
countBits--;
}
}``````

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

Count the no. of 1 bits and make them MSBs

``````private int greatestPositiveInteger(int input)
{
int countOf1 = 0;
int countBits = 0;
while(input>0)
{
int bit = input%2;
if(bit==1)
countOf1++;
countBits++;
input/=2;
}

int toReturn = 0;
for(int i=0;i<countOf1;i++)
{
toReturn+=Math.pow(2, countBits-1);
countBits--;
}
}``````

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

#include<stdio.h>
main(){
int x,k,c=0,i,j,temp;
scanf("%d",&x);
int a[15];
while(x!=0){
k=x%10;
a[c]=k;
c++;
x=x/10;
}
for(i=c-1;i>=0;i--){
for(j=0;j<i;j++){
if(a[i]<a[j]){
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
//printf("-------After arranging---------\n");
for(i=c-1;i>=0;i--){
printf("%d",a[i]);
}
printf("\n");
}

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

#include<stdio.h>
main(){
int x,k,c=0,i,j,temp;
scanf("%d",&x);
int a[15];
while(x!=0){
k=x%10;
a[c]=k;
c++;
x=x/10;
}
for(i=c-1;i>=0;i--){
for(j=0;j<i;j++){
if(a[i]<a[j]){
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
//printf("-------After arranging---------\n");
for(i=c-1;i>=0;i--){
printf("%d",a[i]);
}
printf("\n");
}

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

Its simple sorting in descending order which cant be done in time/space o(1)

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

``````def find_greatest_positive_integer(str):
digits = []
for i in range(0,10):
digits.append(0)

for i in range(0, len(str)):
digits[ int( str[i]) ] = digits[ int(str[i]) ] + 1

result = 0
for i in reversed(range(10)):
for j in range(0, digits[i]):
result = result * 10 + i

return result

print find_greatest_positive_integer("123")
print find_greatest_positive_integer("1239900")``````

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

``````import java.util.Arrays;

public class CareerCupSolution {

public static void main(String[] args){
CareerCupSolution d = new CareerCupSolution();
d.solve();
}

private void solve(){
int n = 234432; // You can get input from standard input.
String number =  Integer.toString(n);
char []array = number.toCharArray();
Arrays.sort(array);
number = new String(array);
number = new StringBuilder(number).reverse().toString();
n = Integer.parseInt(number);
System.out.println(n);
}
}``````

Comment hidden because of low score. Click to expand.
0

That's pretty interesting!

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.

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.

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.

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.