## Google Interview Question for Software Engineer / Developers

• 1
of 1 vote

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

I think the answer is simple, unless i missed something really big:

``````quick sort the input BUT
while comparing two inputs A and B
instead of doing the regular A > B, DO THIS
if(ToInt('AB') > ToInt('BA')) return 1
else -1;``````

Example:
The idea is why would you chose '9' over '94'. All I have to check is whether '994' is greater than '949'. I hope that is clear. Once you sort them by this fashion, you have the sorted list. Just concatenate to get the answer.

I tried on few inputs. Let me know if this does not work or needs tweaking.

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

Again just to prove my earlier algorithm, if you check the sorted array in the example [9,94,4,14,1], you can see that

9 > 94 (when you try it as 994 > 949)
94 > 4 (because 944 > 494)
4 > 14 (because 414 > 144)
14 > 1 (because 141 > 114)

Done!!

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

okay given an array like this
9009, 664, 64, 19, 7, 9, 24, 964, 99
@Kishore:
can u demonstrate the answer with ur algo

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

@Kishore : nice

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

@blueskin:
I did not write the code to execute and give you an answer.
You can do it yourself as all u need is a 10 line quicksort program.
If you find an error in my logic, you can dispute it by giving an example. To dispute a logic you just need 2-3 input numbers.
Please don't get me wrong as i don't want to take the pain of writing code.

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

@ Kishore:
Just a sample...what if i have a number in the list which has the maximum no: of digits an int can hold?I mean 31st bit of that number set to 1 if int size is 32 bits.

Comment hidden because of low score. Click to expand.
2
of 4 vote

I'd try using a trie-based approach.

``````For input: 9,94,4,14,1
root has 3 edges {9,4,1}
9 has two edges {\$,4}
1 has two edges {4,\$}

which is something like
/|\
/ | \
9  4  1
/ \   / \
\$   4  4  \$
leaves are: 9, 94, 4, 14, 1
concatenated string: 9944141``````

the only trick seems to define order of \$. As edge (4) is smaller than preceding value (i.e. 9), \$ comes to left of 4. In the other case, \$ comes after 4 (for 1).

report any flaw that you could catch here. thanks.

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

lol

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

Very good idea.

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

8,89
yours gives 8,89
correct ans is 89,8

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

Jinxed, I think you are wrong. According to the algorithm mentioned above 9>8 so 89 comes first then 8 comes next

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

How about (1) 787# and 78778 (2) 787# and 78772 ?
The # in the first case should be in the right,
but the # in the second case should be in the left.
How do you distinguish them?

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

Couple of days ago, same question was asked on stackoverflow.

I also posted a working solution to this problem. Its recursion based.

Google for "Array manipulation interview question StackOverflow"
(upvote if you think my submission is correct)

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

Hi,

Group the elements based on their MSB, sort the elements within each group (as well sort the groups also based on MSB)
Now start concatenating of two elements within group (u can always check the value also while concatenating that which one is bigger) do the same with elements of out side the groups

ex: 9,100
{9},{100} (since MSB of 100 is 1)
so final element will be 9100

ex: 9,99,91,5,59,8,81,4,44,21

goup {9,91,99} ,{8,81} ,{5,59} ,{4,44} ,{21}

start concatenating
991 >919 so 991
99199 < 99991 so 99991
similarly in second group 881
in third 595
in fourth 444
in fifth 21
so final 9999188159544421

u r comment is always welcome let me know if i am missing something...

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

here is the tcl coding

proc group { data key } {
set final ""
for { set i 0 } { \$i < [ llength \$data ] } { incr i } {
set temp [ lindex \$data \$i ]
set pre \$temp
while { \$temp > 0 } {
set pre \$temp
set temp [ expr { \$temp / 10 } ]
}
if { \$pre == \$key } {
lappend final [ lindex \$data \$i ]
}
}
return \$final
}

proc gather { data } {

while { [ llength \$data ] != 1 } {
set final ""
set temp "[ lindex \$data 0 ][ lindex \$data 1 ]"

lappend final \$temp
for { set i 2 } { \$i < [ llength \$data ] } { incr i } {
lappend final [ lindex \$data \$i ]
}
set data [ lsort \$final ]
}
return \$data
}

set data "100 9"
set result ""
for { set i 1 } { \$i < 10 } { incr i } {

set temp_group [ group \$data \$i ]
if { [ lindex \$temp_group 0 ] != "" } {
lappend result [ gather [ lsort \$temp_group ] ]
}

}
set result [ lsort -decreasing \$result ]

puts [ join \$result "" ]

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

not good for {9,97,989}
997>979 so select 997
997989 > 989997 so select 997989

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

``````public static void concateMaxValue(int[] data, int left, int right) {
if(left < right) {
int part = partition(data,left,right);
concateMaxValue(data, left, part);
concateMaxValue(data, part + 1, right);
}
}

private static int partition(int[] data, int left, int right) {
int mid = (left+right)>>1;
int i = left;
int j = right;
String value1, value2;
while (true) {
while (i < right){
value1 = Integer.toString(data[mid])+Integer.toString(data[i]);
value2 = Integer.toString(data[i])+Integer.toString(data[mid]);
if (Integer.valueOf(value1)< Integer.valueOf(value2)){
i++;
} else {
break;
}
}
while (j > left) {
value1 = Integer.toString(data[mid])+Integer.toString(data[j]);
value2 = Integer.toString(data[j])+Integer.toString(data[mid]);
if (Integer.valueOf(value1)> Integer.valueOf(value2)){
j--;
} else {
break;
}
}
if (i < j){
swap(data, i, j);
i++;
j--;
}
else {
return j;
}
}
}

private static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}``````

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

K rounds where is the maximum number of digits in any number in array.
k=0;

For each rounds
1. Sort the array based on the Kth (from left or MSB) digit.
2. In case of comparison like 8 and 89 where k=2, if the kth digit is greater than (k-1)th digit(i.e. 9>8 in 89),put 89 first otherwise 8.
3. k++

I don't know if this would work fine...this is the first thing which came to my mind instantly, so i shared it

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

Never mind..last one was a blaster..completely wrong..

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

But the idea, here is to use something like radix sort.

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

yea..i thought the same..except in 94 and 9, 9 is the LSD and 0 is the MSD

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

1. Sort in lexicographically decreasing . Using radix sort base 10. With constraint if number is having only one digit then if second digit of first element of corresponding sorted list is less than the current number then append that number at first position and after that this number of this array wont take part in sorting.
2. Now concatenate all starting from 9.

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

Sorry, I meant bucket sort above.

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

1. For MSB sort lexicographocally (9 above to 8 etc)
2. For kth digit, if both number have digit do normal comparision
else do it with (k+1)degit
3. do step 2 untill all digit

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

Let's compare these two numbers (letters represent digits): xyzab and xyz
the two possibilities are:
xyzabxyz
xyzxyzab

if a=x then we continue the comparison
if b=y -- || --
now we have to compare x to z then y to a...
I am afraid none of the solutions above works for such cases.

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

I tried to work my approach with the case you mentioned. Here's two examples:

``````input: 123, 12312
as the digit after 123 is "1" which is less than 3, the concatenation would be 12312312, which is bigger than 12312123
input: 123, 12341
as the digit after 123 is "4" which is bigger than 3, the concatenation would be 12341123, which is bigger than 12312341``````

pls, give an example where you think my above approach fails. thanks.

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

I got the catch. It fails for such input:
123, 12315

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

Hi,
I posted the answer below. I guess it works for all cases and is simple. Can you check and let me know if you see issues.

I am copying it again here:
++++++++++++++++++++++++++++++++++++++++
quick sort the input BUT
while comparing two inputs A and B
instead of doing the regular A > B, DO THIS
if(ToInt('AB') > ToInt('BA')) return 1

Example:
The idea is why would you chose '9' over '94'. All I have to check is whether '994' is greater than '949'. I hope that is clear. Once you sort them by this fashion, you have the sorted list. Just concatenate to get the answer.
+++++++++++++++++++++++++++++++++++++++

else -1;

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

Your approach works fine for all cases I tried. I assumed all inputs are strings (because there is no specification), and quicksort gives O(nm logn) solution where n is size of input, m = length of final result (i.e. summation of inputs' length).

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

Kishore's claim is so obvious and shopno take a careful look at the question again..."Given an integer array...

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

Heres the approach
if i and j are the 2 numbers...count the number of continuous ones at the front and back of i and j...let them ifrnt,iback,jfrnt,jback...
if(iback+jfrnt)>(jback+ifrnt)
i should come before j
else
j should come before i

eg:12315,123--->123 is 1111011--->front=4,back=2
12315 is 11000000011011--->front=2,back=2...so 12315 should come before 123

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

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

Take another array ,size same as the number of numbers of the previous array.Get the average of the digits of the previous array elements.Put them into the second array after sorting these averages .Print the array elements of the previous one according the array order.
e.g: [4, 94, 9, 14, 1]

second array contains:[4,6.5,9,2.5,1]after sorting (non increasing)[9,6.5,4,2.5,1]
so print..
9,94,4,14,1
one thing to remember you must have to put a mark whether this number is from two or three or.. or one give priority one>two>three...
please give comment if i am wrong

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

won't wrk for 44, 4439 from your logic output will be 443944
but is shd be 444439

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

In support of Kishore 's argument ::

public class quicksort_modified {

static int cnt;

public static int addup(int a,int b)
{
String s1,s2;
s1= Integer.toString(a);
s2= Integer.toString(b);
return (Integer.parseInt((s1+s2)));

}

public static int lng(int a)
{
int ln=0;
while(a!=0)
{
ln++;
a=a/10;

}
return ln;
}

public static int partition(int a[],int l, int h)
{
int x=a[h],temp;
int i=l-1,j;
for (j=l;j<h;j++)
{

if(lng(a[j]) == lng(x))
{
if (a[j]>=a[h])
{
cnt++;
i++;
temp=a[i];
a[i]=a[j];
a[j]=temp;
}

}
{
cnt++;
i++;
temp=a[i];
a[i]=a[j];
a[j]=temp;
}

}
temp=a[i+1];
a[i+1]=a[h];
a[h]=temp;

return i+1;
}

public static void quicksort(int a[],int l,int h)
{
if (l<=h)
{
int pivo=partition(a,l,h);
quicksort(a,l,pivo-1);
quicksort(a,pivo+1,h);
}

}

public static void main(String[] args)
{

int[] a={4,94,9,14,1},i;
quicksort(a,0,4);

/*for(i=0;i<5;i++)
System.out.println("\n %d"+a[i]);*/
StringBuffer sb = new StringBuffer();
for (int j = 0; j < a.length; j++) {
sb.append(a[j]);

}

System.out.println(sb);

System.out.println("\n Number of comparisons : "+cnt);

}

}

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

``````package simple;

import java.util.Arrays;

public class arrComp {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub

Integer[] arr= {90,9,19,0,5};
printArray(arr);
Arrays.sort(arr,new intComp());
printArray(arr);

}

private static void printArray(Integer[] arr) {
// TODO Auto-generated method stub

String result = "";
for( Integer a: arr){
//System.out.print(a+" ");
String temp=Integer.toString(a);
result+=temp;

}

System.out.println("Result= "+ result);
}

}``````

``````package simple;

import java.util.Comparator;

public class intComp implements Comparator<Integer> {

@Override
public int compare(Integer o1, Integer o2) {
// TODO Auto-generated method stub

String firstNum =Integer.toString(o1);
String secNum =Integer.toString(o2);

String firstSec=firstNum+secNum;
String secFirst=secNum+firstNum;

Integer fs=	Integer.parseInt(firstSec);
Integer sf=Integer.parseInt(secFirst);

return (-fs.compareTo(sf));

}

}``````

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

A similar question with explanation is :

coders-stop.blogspot.com/2011/01/lexicographically-smallest-string.html

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

We could sort for each digit keeping the rule that:

1. Sort all digits in ascending order if the digits are less than previous digit.
2. Sort all digits in descending order if the digits are greater than previous digit.

Eg. we have two digits XYZ, ABC, XD

First sort on X and A
Next for all X based digits sort for Y, D (using the above rules).

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

1. please find my code below. it is compiled and executable code.

2. API: int IsGreater(int a, int b) takes two integers.

return 1 if a > b ( i.e a's value is lexicographically greater than b's value )
return 0 if a > b ( i.e a's value is lexicographically less than b's value )

Example 1: a = 8, b=89 then a < b
Exmaple 2: a = 7, b = 76 then a > b
Example 3: a=7 b=778 then a<b

3. I used selection sort to sort the array lexicographically.

4. I am achiebing lexicographical order by using IsGreater() API.

5. Time complexity O(n^2);

``````#include<stdio.h>
#include<stdlib.h>
#include<string.h>

void reverse(char *str,int len) {
int i=0;
char ch;
for(i=0;i<=(len-1)/2;i++) {
ch=str[i];
str[i]=str[len-1-i];
str[len-1-i]=ch;
}
}

char* itoa(int number) {
char *str= (char * ) malloc(sizeof(char)*20);
int negFlag=0,pos=0;
if(number<0) {
negFlag=1;
number=-number;
}
while(number>0) {
str[pos++]='0'+number%10;
number=number/10;
}
if(negFlag) {
str[pos++]='-';
}
str[pos]='\0';
reverse(str,pos);
return str;
}
int IsGreater(int a, int b)
{
char *str1 = itoa( a ) ;
char *str2 = itoa( b ) ;

int len1 = strlen(str1);
int len2 = strlen(str2);

//      printf("\n str1 = %s str2 = %s \n", str1, str2 );
int i =0;
int j =0;

while( i< len1 && i < len2 )
{
if( str1[i] > str2[i] )
{
return 1;
}
else if( str1[i] < str2[i] )
{
return 0;
}
else
{
i++;
}

}

j = i;
i--;

while( j< len1 || j < len2 )
{
if( len1 < len2 )
{

if( str1[i] > str2[j] )
{
return 1;
}
else if( str1[i] < str2[j] )
{
return 0;
}
else
{
j++;
}

}
else
{
if( str1[j] > str2[i] )
{
return 1;
}
else if( str1[j] < str2[i] )
{
return 0;
}
else
{
j++;
}

}
} // end of while

}

void Swap( int data[], int i, int j )
{
if( i != j)
{
data[i] = data[i] ^ data[j] ;
data[j] = data[i] ^ data[j] ;
data[i] = data[i] ^ data[j] ;
}
}

int main()
{
int data[] = {4,94, 9,14,1,8,89,7,76,778} ;
int data_size = sizeof(data) / sizeof(int)  ;
int i = 0;
int j;
int max_index;

while( i <  data_size )
printf("\t %d , ", data[i++] );
printf("\n \n ");
/* Selection Descending order sort */
for( i = 0 ; i < data_size ; i++ )
{
max_index = i;

for( j= data_size ; j > i ; j-- )
{
if( IsGreater( data[j], data[max_index] ))
{
//                              printf("\n  j = %d  max_index = %d \n", j, max_index );
max_index = j;
}
}
Swap( data, max_index, i );
}
i = 0;
while( i <  data_size )
printf("\t %d , ", data[i++] );
return 0;
}``````

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

Go brute force. Use backtracking

``````public static void main(String[] args) {
int[] array = { 4, 94, 9, 14, 1 };
System.out.println(findMax(array));
}

public static int findMax(int[] array) {
boolean[] used = new boolean[array.length];
return doFindMax(array, used, 0, 0, 0);
}

private static int doFindMax(int[] array, boolean[] used, int count,
int current, int max) {
if (count == array.length) {
return (current > max) ? current : max;
}

for (int i = 0; i < array.length; i++) {
if (!used[i]) {
used[i] = true;
int newValue = Integer.valueOf(current + "" + array[i]);
int t = doFindMax(array, used, count + 1, newValue, max);
if (t > max) {
max = t;
}
used[i] = false;
}
}

return max;
}``````

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

Pretty simple solution:
1)Parse the array, if the integer length is greater that 1, find the quotient and remainder by dividing it by 10, i.e. if it is 94%10 is we get 9,4. Like wise split the elements as follows 4,9,4,9,1,4,1. Sort this array you will get the maximum value.
2) if the integer length is greater than split it recursively by dividing it with 100 and then with 10, (applies for all cases).

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

``````bool GreaterCombined(const int& a, const int& b) {
stringstream ssab, ssba;
ssab << a << b;
ssba << b << a;
int ab, ba;
ssab >> ab;
ssba >> ba;
return ab > ba;
}

int main(int argc, char** argv) {
int array = {4, 94, 9, 14, 1};
vector<int> input(array, array+5);

sort(input.begin(), input.end(), GreaterCombined);

for (int i = 0; i < 5; ++i)
cout << input[i] << " ";
cout << endl;
}``````

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

for (int i=0;i<n;i++) {
for(int j=i;j<n;j++) {
if(Integer.Valueof(a[i]).CharAt(0) < Integer.Valueof(a[i+1]).CharAt(0)) {
swap(a[i],a[i+1]);Lo
}else if(Integer.Valueof(a[i]).CharAt(0) == Integer.Valueof(a[i+1]).CharAt(0)) {
if(strlen(Integer.Valueof(a[i]) < strlen(Integer.Valueof(a[i+1]) ) {
swap(a[i],a[i+1]);
}

}
}
}

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

Above solution uses Bubbule sort, if the comparison can also be done under QuickSort mechanism

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

The logic behind this is that we have to check that ab and ba for two integers a & b . Suppose a = 9 and b = 94. So, ab = 994 && ba = 949 thus, ab > ba. hence order will be 9, 94. This can be done by implementing our own comparator.

``````import java.io.BufferedReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.Comparator;

class Sort implements Comparator<Integer> {

public int compare(Integer a, Integer b) {
String first = a.toString();
String second = b.toString();
return (first+second).compareTo(second+first);
}
}

public class ComparatorSort {

public static void main(String[] args) throws NumberFormatException, IOException {
Integer [] inputArray = new Integer[n];
for(int i=0;i<n;i++)
Arrays.sort(inputArray, new Sort());
for(int i=n-1;i>=0;i--)
System.out.print(inputArray[i] + " ");
System.out.println();
}
}``````

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

Sort the string array of numbers by comparing the two strings in the custom compare function.

``````bool compare(const string x,const string y)
{
return (atoi((x+y).c_str))<(atoi((y+x).c_str));
}``````

call it as sort(array.begin(),array.end(),compare);

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

It's a well known solution. I wish to ask if you could formally prove it as well. It seems giving a ready-made solution may not be too much impressive over a concrete explanation (if it's been asked). Thanks.

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

When u r considering two strings, you are arranging it in such a way that it leads to the largest number possible.
Now, why it works for the complete array.
Just consider an analogy for sorting numbers.U compare and sort two numbers at a time and the sort algorithm make it valid over the complete array. Similarly, here we are comparing and making maximum value out of two numbers at a time and the sort algorithm is making the same valid over the complete array.

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

how do you prove if(compare(a, b) && compare(b, c)) then compare(a, c) == true? thank you

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

If you use atof instead of atoi, you can account for the case of 989 9 97, so that you get 998997 instead of 989997. Basically you are comparing floats instead of ints.

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

this would work as it is not necessary that
A>B & B>C implies A>C
here we need to use dynamic programming

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

Sort the numbers in decreasing lexicographic order

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

Yup I also think the same..

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

lexicograhic sort of numbers ...

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

it wont work try a={9,97,1}if u r sorting in lexicographically decreasing order u wud get 9791 if increasing 1997.
u have to traverse the array once and bring all the numbers which have only 9's to the front and then sort the remaining portion in lexicographically decreasing order

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

This again applies to each digit .. so won't work that easily .

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

Surely Radix Sort? Let me work on some implementation for it...

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

here is a recursive solution for this problem

public static void main(String[] args)
{
int arr[] = {9, 97, 1};
StringBuffer buf = new StringBuffer();
for(int i = 0; i < arr.length; i++) {
buf.append(arr[i]);
}
extractLargeNumber("", buf.toString());
}

public static void extractLargeNumber(String st, String chars)
{
if (chars.length() <= 1)
{
value = Integer.parseInt(st + chars);
if(value > max) max = value;
}
else
{
for (int i = 0; i < chars.length(); i++)
{
try {
String newString = chars.substring(0, i) + chars.substring(i + 1);
extractLargeNumber(st + chars.charAt(i), newString);
} catch (Exception e) {
e.printStackTrace();
}
}
}
}

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

it would be nice if you could post algorithm as well

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

This might work...
logic is to extract a max no with two integers in the array in each iteration then add it to the global optNo to make it max
which will contains the final max no.

``````#include<iostream>
#include<string>
#include<stdio.h>
#include<stdlib.h>

std::string optNo;

bool
cmp(const std::string f, const std::string s)
{
if( atoi(f.c_str()) > atoi(s.c_str()) )
return true;
else
return false;
}

std::string
GetOptByCmp(const std::string f, const std::string s) {

if(cmp(f+s,s+f))
return f+s;

else
return s+f;
}

int
main()
{

int a[]={0, 10, 9, 100, 6};
int n=5, s;
char buf, buf1;
std::string tmp,ltmp;

unsigned char c;
for(int i=0; i<n; i++)
{
if(a[i] <0)
continue;

sprintf(buf, "%d", a[i]);
tmp=buf;

for(int k=0; k<n; k++)
{
if(k==i || a[k]<0)
continue;

sprintf(buf1, "%d", a[k]);

if( cmp(ltmp=GetOptByCmp(buf, buf1), tmp) )
{
tmp= ltmp; s= k;
}
}

a[i] = -1;
a[s] = -1;

optNo=GetOptByCmp(optNo, tmp);
}

std::cout << "Max No: " << optNo << std::endl;

}
return 0;
}``````

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

Convert to a String array and use custom comparator

``````@Override
public int compare(String aStr, String bStr) {
int aLen = aStr.length();
int bLen = bStr.length();

if (aLen == 1 && bLen > 1) {
String bFirst = bStr.substring(0, 1);
if (aStr.equals(bFirst)) {
return -1;
}
}

if (aLen > 1 && bLen == 1) {
String aFirst = aStr.substring(0, 1);
if (bStr.equals(aFirst)) {
return 1;
}
}

int compare = aStr.compareTo(bStr);
if (compare > 0) {
return -1;
} else if (compare < 0) {
return 1;
} else {
return 0;
}
}``````

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

If my understandings is correct, so you have to sort your given array by descending mode only. Current sorted array will be your maximum number.

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

If my understandings is correct, so you have to sort your given array by descending mode only. Current sorted array will be your maximum number.

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

``````#include<stdio.h>

int compare(char *s1,char *s2)
{
if(s1 == NULL && s2 == NULL)
return 0;
if(s1 == NULL)
return -1;
if(s2 == NULL)
return 1;
while(*s1 && *s2)
{
if(*s1 < *s2)
return -1;
if(*s1 > *s2)
return 1;
s1++;
s2++;
}
if(*s1)
return 1;
if(*s2)
return -1;
return 0;
}

char *itoa(char *str,int a)
{
char *result=str,*start=str,*end;
int mod=0;
if(a<0)
{
*str = '-';
start++;
str++;
a=-a;
}
while(a >= 10)
{
mod = a%10;
a = a/10;
*str = 48 + mod;
str++;
}
*str = 48 + a;
end=str;
*(str+1)='\0';

while(start < end)
{
*start = *start ^ *end;
*end = *start ^ *end;
*start = *start ^ *end;
start++;
end--;
}
return result;
}

char* concat(char *s1,char *s2)
{
if(s1 == NULL && s2 == NULL)
return NULL;
if(s1 == NULL)
return s2;
if(s2 == NULL)
return s1;
char *result=s1;
while(*s1)
{
s1++;
}
while(*s2)
{
*s1=*s2;
s1++;
s2++;
}
*s1=*s2;
return result;
}

void sort(int a[],int n)
{
int i=0,j=0;
char *s1=(char*)malloc(1024);
char *s2=(char*)malloc(1024);
char *s3=(char*)malloc(1024);
char *s4=(char*)malloc(1024);
for(i=0;i<n-1;i++)
{
for(j=i+1;j<n;j++)
{
if(compare( concat(itoa(s1,a[i]),itoa(s2,a[j])), concat(itoa(s3,a[j]),itoa(s4,a[i])) )==-1)
{
a[i] = a[i]^a[j];
a[j] = a[i]^a[j];
a[i] = a[i]^a[j];
}
}
}
}

int main()
{
int a[]={10,9};
int n=2,i=0;

sort(a,n);
for(i=0;i<n;i++)
{
printf("%d",a[i]);
}

return 0;
}``````

Feedbacks are welcome.

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

In question it is given that :
2 3 5 78
ans: 78532
Infcat answer should be 87532 right ?

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

In question it is given that :
2 3 5 78
ans: 78532
Infact answer should be 87532 right ?

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

No. the numbers are 2,3,4,78. U have to use the numbers and not the digits of the numbers to form that big number. :)

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

Can't we create max heap from it (i guess array is of numbers) and then extract root from it one by one

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

1. find the elements which are single digit and sort it
2. compare the highest element in step #1 with first digit of the 2 digit #
2.a. if it's higher place all 1 digit numbers followed by the 2 digit
2.b. else, place 2 digit # first followed by 1 digit numbers

this works in array having many 1 digit numbers and only 1 two digit number

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

just to follow up with the above answer, if we an array containing variation of numbers like: 5, 6, 70, 80, 900, 950 (numbers of different digits)

all we need to do is find out the largest number we can generate for 1 digit, 2 digit, 3 digit. and then sort those sub-problem answers based on the first digit.

for array 5,6,70,80,900,950

1 digit: 65 [1st digit is 6]
2 digit: 8070 [1st digit is 8]
3 digit: 950900 [1st digit is 9]

now look at the 1st digit of the above sub-problem answer and then sort them to get final answer:

950900807065
- - -

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

anandtechblog.blogspot.com/2011/06/arrays.html

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

such a horrible solution. If u r trying to promote your blog at least have the content on your blog correct

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

They are many valuables points in the Solution that he described., I found a solution based on his idea. Thanks Anand for the solution.

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

The following code does it. It sorts the list based on a custom comparator. The code is quiet self explanatory.

/* The class name doesn't have to be Main, as long as the class is not public. */
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.TreeSet;

class MyComp implements Comparator<Integer> {
public int compare(Integer a1, Integer b1) {
String a = a1.toString();
String b = b1.toString();
int min = Math.min(a.length(),b.length());
for(int i = 0;i<min;i++) {
if(a.charAt(i) > b.charAt(i))
return -1;
}
if(a.length() > b.length()) return 1;
return -11;
}
}

class LexicographicSortOfNumbers {

LexicographicSortOfNumbers() {
}

static void main(String args[]) {
int arr[] = {1,9,98};
TreeSet<Integer> ts = new TreeSet<Integer>(new MyComp());
for (Integer element : ts) {
System.out.print(element + " ");
}
}

}

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

The following code does it. It sorts the list based on a custom comparator. The code is quiet self explanatory.

``````/* The class name doesn't have to be Main, as long as the class is not public. */
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.TreeSet;

class MyComp implements Comparator<Integer> {
public int compare(Integer a1, Integer b1) {
String a = a1.toString();
String b = b1.toString();
int min = Math.min(a.length(),b.length());
for(int i = 0;i<min;i++) {
if(a.charAt(i) > b.charAt(i))
return -1;
}
if(a.length() > b.length()) return 1;
return -11;
}
}

class LexicographicSortOfNumbers {

LexicographicSortOfNumbers() {
}

static void main(String args[]) {
int arr[] = {1,9,98};
TreeSet<Integer> ts = new TreeSet<Integer>(new MyComp());
for (Integer element : ts) {
System.out.print(element + " ");
}
}

}``````

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

Its right on line, but seems it fails in edge cases. It fails for a=98 b = 989 making number as 98989 rather than 98998

the comparator will tell us that 98>989 while actually 989 should be greater than 98

Also, the comparator never returns zero(0).

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

Run through the array and select only the elements that have the largest leftmost digit. These elements are possible candidates to lead off the largest number. Imagine left-aligning all these elements. Now look at the next leftmost digit. If an element does not have a next leftmost digit, append an unused element to it in all possible ways, thereby expanding the list. Once all the candidates have at least a next leftmost digit, run through the list again and select only the elements that have the largest next leftmost digit. You can see where this is going: at each step we are figuring out the next leading digit for the largest number, appending with elements whenever needed to make sure we can make a selection from the list of possible candidates. The list of candidates will expand as we append elements and shrink as we eliminate them as being prefixes for the largest number. The prefixes themselves will grow in a jagged way but at the very end we will arrive at one number (or list of identical numbers), which will be largest possible.

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

use radix sort on the left most digit and then just print the number.

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

<pre lang="" line="1" title="CodeMonkey22622" class="run-this">import java.util.Arrays;
import java.util.Comparator;

/**
* @author jk
* Given an integer array, sort the integer array such that the concatenated
* integer of the result array is max. e.g. [4, 94, 9, 14, 1] will be sorted to [9,94,4,14,1]
* where the result integer is 9944141
*/
public class G61SortArrayForMaxValue {

/**
* @param a
* @returns the sorted integer
*/
public static Integer[] sortArrayForMaxValue(Integer[] a) {
// lexicographically comparator
final Comparator<Integer> c = new Comparator<Integer>() {
public int compare(Integer v1, Integer v2){
return v2.toString().compareTo(v1.toString());
}
};
Arrays.sort(a, c);
return a;
}

public static void main(String[] args) {
Integer[] a = {4, 94, 9, 14, 1};
Integer[] r = sortArrayForMaxValue(a);
for (int i = 0; i < r.length; i++) {
System.out.printf("%d ", r[i]);
}
}
}

</pre><pre title="CodeMonkey22622" input="yes">
</pre>

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

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;

void swap(int *a, int *b)
{
*a = *a + *b;
*b = *a - *b;
*a = *a - *b;
}

void concatinate(int a[], int n)
{
char s;
int t1, t2;
for(int i = 0; i < n; i++)
{
for(int j = i + 1; j < n; j++)
{
sprintf(s, "%d%d",a[i],a[j]);
t1 = atoi(s);
sprintf(s, "%d%d",a[j],a[i]);
t2 = atoi(s);

if(t1 < t2)
swap(&a[i], &a[j]);
}
}
}

int main(void)
{
int a[] = {4, 94, 9, 14, 1};
concatinate(a, 5);
for(int i = 0; i < 5; i++)
{
cout << a[i];
}
cout << endl;
}

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

Traverse the integer array. While traversing find out number of 9s, 8s, 7s and so on. Finally print a string with number of 9s found + number of 8s found and so on

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

Java code

void printLargetNumber(int[] array) {
String[] numbers = new String;

for (int i=0; i<array.length; i++) {
String number = array[i] + "";
for (int j=0; j<number.length(); j++) {
numbers[number.charAt(j) - '0'] += number.charAt(j) + "";
}
}

for (int i=9; i>=0; i--) {
if (numbers[i].length() > 0)
System.out.print(numbers[i]);
}
}

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

I think we can adopt this solution:
First, we extend the number in the array into a N digit number. The “extend” way is like this, say N=3,
78, MSB=7, extend(78)=788; // we put MSB at the end
3, MSB=3, extend(3) =333;
101 MSB=1, extend(101)=101;
Then we can simply sort the array by the extended value of the array element, then print them out;
The code is like this:
int extend( int A, int N)
{
int temp=A;
int digit=1;
while(A/10) {A=A/10;digit++;}
int MSB= A;
int base=1;
int z=N-digit;
while(z--)
{
temp= temp*10+MSB;
}
return temp;
}

void specialsort( int* m, int n)
{
for(int i=0;i<n-1;i++)
for(int j=n-1;j>i;j--)
{
if( extend(m[i],3)<extend(m[j],3) )
{
m[i]= m[i]^m[j];
m[j]= m[i]^m[j];
m[i]= m[i]^m[j];
}
}
}
void showtable( int *m, int n)
{
for(int i=0;i<n;i++)
cout<<m[i];
cout<<endl;
}

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

I think we can adopt this solution:
First, we extend the number in the array into a N digit number. The “extend” way is like this, say N=3,
78, MSB=7, extend(78)=788; // we put MSB at the end
3, MSB=3, extend(3) =333;
101 MSB=1, extend(101)=101;
Then we can simply sort the array by the extended value of the array element, then print them out;
The code is like this:
int extend( int A, int N)
{
int temp=A;
int digit=1;
while(A/10) {A=A/10;digit++;}
int MSB= A;
int base=1;
int z=N-digit;
while(z--)
{
temp= temp*10+MSB;
}
return temp;
}

void specialsort( int* m, int n)
{
for(int i=0;i<n-1;i++)
for(int j=n-1;j>i;j--)
{
if( extend(m[i],3)<extend(m[j],3) )
{
m[i]= m[i]^m[j];
m[j]= m[i]^m[j];
m[i]= m[i]^m[j];
}
}
}
void showtable( int *m, int n)
{
for(int i=0;i<n;i++)
cout<<m[i];
cout<<endl;
}

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

Sort the array with a new comparator that when comparing two integers, concat them as strings in different order before comparing. For example, compare 9 and 91 becomes comparing "991" and "919" and thus 9 is great than 91. Java code below:

``````public int compare(Integer a, Integer b) {
String s1 = a.toString() + b.toString();
String s2 = b.toString() + a.toString();
int c = s1.compareTo(s2);
return -c;
}``````

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

given two number x, y. we should find the first digits from left to right which i.digit is different from y.digit.

here is the code.

``````#include <iostream>
#include <algorithm>

using namespace std;

bool cmp(int i, int j)
{
int a;
int b;
int n1, n2;
if (i == 0)
{
a = 0;
n1 = 1;
}
else
{
for (n1 = 0; i; ++n1)
{
a[n1] = i % 10;
i /= 10;
}
}
if (j == 0)
{
b = 0;
n2 = 1;
}
else
{
for (n2 = 0; j; ++n2)
{
b[n2] = j % 10;
j /= 10;
}
}
for (--n1, --n2; n1 >= 0 && n2 >= 0; --n1, --n2)
{
if (a[n1] != b[n2])
{
break;
}
}
int s1, s2;
if (n1 >= 0 && n2 >= 0)
{
s1 = a[n1];
s2 = b[n2];
}
else if (n1 < 0 && n2 >= 0)
{
while (n2 >= 0)
{
if (a == b[n2])
{
--n2;
}
else
{
break;
}
}
if (n2 >= 0)
{
s1 = a;
s2 = b[n2];
}
else
{
s1 = a;
s2 = b;
}
}
else if (n1 >= 0 && n2 < 0)
{
while (n1 >= 0)
{
if (a[n1] == b)
{
--n1;
}
else
{
break;
}
}
if (n1 >= 0)
{
s1 = a[n1];
s2 = b;
}
else
{
s1 = a;
s2 = b;
}
}
else
{
s1 = a;
s2 = b;
}
return s1 > s2;
}

void reorder(int *array, int n)
{
sort(array, array + n, cmp);
for (int i = 0; i < n; ++i)
{
cout << array[i];
}
cout << endl;
}

int main()
{
int n;
cin >> n;
int array;
for (int i = 0; i < n; ++i)
{
cin >> array[i];
}
reorder(array, n);
return 0;
}``````

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

Lexicographical Sort :

#include<stdio.h>
#include<string.h>

char a[]={"9","99","91","5","59","8","81","4","44","21"};

void swap(int i,int j)
{
char temp;
strcpy(temp,a[i]);
strcpy(a[i],a[j]);
strcpy(a[j],temp);
}

void quicksort(int beg,int end)
{
char pivot;
int i,j;
strcpy(pivot,a[beg]);

if(beg<end)
{
i=beg;
j=end+1;

while(i<j)
{
while(i<end)
{
++i;
if(strcmp(a[i],pivot)>0)
break;
}
while(j>beg)
{
--j;
if(strcmp(a[j],pivot)<0)
break;
}
if(i<j)
swap(i,j);
}
swap(j,beg);
quicksort(beg,j-1);
quicksort(j+1,end);
}
}

int main()
{
int i;
quicksort(0,9);
for(i=9;i>=0;i--)
printf("%s",a[i]);
return 0;
}

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

``````#include<stdio.h>
#include<conio.h>
#include<string.h>

char a[]={"9","99","91","5","59","8","81","4","44","21"};

void swap(int i,int j)
{
char temp;
strcpy(temp,a[i]);
strcpy(a[i],a[j]);
strcpy(a[j],temp);
}

void quicksort(int beg,int end)
{
char pivot;
int i,j;
strcpy(pivot,a[beg]);

if(beg<end)
{
i=beg;
j=end+1;

while(i<j)
{
while(i<end)
{
++i;
if(strcmp(a[i],pivot)>0)
break;
}
while(j>beg)
{
--j;
if(strcmp(a[j],pivot)<0)
break;
}
if(i<j)
swap(i,j);
}
swap(j,beg);
quicksort(beg,j-1);
quicksort(j+1,end);
}
}

int main()
{
int i;
quicksort(0,9);
for(i=9;i>=0;i--)
printf("%s",a[i]);
getch();
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote
This Of course will work also with a Integer comaparator checking the most significant digit each time but this code is easier to understand {{{ private static Comparator<String> conComp = new Comparator<String>() { @Override public int compare(String one, String two) { int l1 = one.length(); int l2 = two.length(); int i =0; if (one.equals(two)) return 1; while (i < l1 && i < l2 && one.charAt(i) == two.charAt(i)) { i++; } if (l1 > i && l2 > i) return two.charAt(i) - one.charAt(i); if (i < l2) { return one.charAt(0)- two.charAt(i); } return one.charAt(0)- one.charAt(i); } }; private static int[] largestCon(int[] a) { ArrayList<String> test = new ArrayList<String>(); for (int i = 0; i < a.length; i++) test.add(String.valueOf(a[i])); Collections.sort(test, conComp); int ret[] = new int[a.length]; int counter = 0; for (String s : test) ret[counter++] = Integer.valueOf(s); for (int i = 0; i < ret.length; i++) { System.out.print(" " +ret[i]); } System.out.println(""); return ret; }
Comment hidden because of low score. Click to expand.
0
of 0 vote

Java Code

``````public static void quickSort(int a[]){
if(a==null||a.length<2)return;
quicksort(a,0,a.length-1);
}

private static void quicksort(int a[],int start, int end){
if(end<=start)return;
int j = partition(a, start, end);
quicksort(a,start,j-1);
quicksort(a,j+1,end);
}

private static int partition(int a[],int start,int end){
int i = start;
int j = end+1;
int pivot = a[start];
while(true){
while(compareMax(a[++i],pivot)<0)
if(i==end)break;
while(compareMax(pivot,a[--j])<0)
if(j==start)break;
if(i>=j)break;
swap(a,i,j);
}
//put pivot in the correct position;
swap(a,start,j);
return j;
}

private static int compareMax(int i,int j){
int ij = Integer.valueOf(String.valueOf(i).concat(String.valueOf(j)));
int ji = Integer.valueOf(String.valueOf(j).concat(String.valueOf(i)));
if(ij<ji)
return 1;
if(ij==ji)return 0;
return-1;
}``````

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

``````def cmplt(a, b):
sa = str(a)
sb = str(b)
return int(sa+sb) < int(sb+sa)

def mins(a, s):
currmin = 0
for i in range(s):
if cmplt(a[i], a[currmin]):
currmin = i
return currmin

def arrange(a):
for i in range(len(a), 0, -1):
m = mins(a, i)
t = a[i-1]
a[i-1] = a[m]
a[m] = t
return a``````

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

its basically selection sort and the comparison between two elements is by converting them to string and then comparing the arrangement of the strings
ie
cmplt(9, 94) ==> '994' < '949' ==> False

>>> arrange([94,9,7,84,9])
[9, 9, 94, 84, 7]

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

Just do a radix sort :-

Ex :- 9,94
First 9 is greater then 4 so first number will come before 94

so 994

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

Here is my approach :-
1. Sort array according to the first digit of each number
(for given input, it should be - 94, 9, 4, 1, 14, keeping order is not necessary)
2. Now run a loop from i=0 to n-1 elements , pick pair each time (like 0, 1 then 1, 2....)
if(no. of digits of a and b are equal)
continue
else // formNum(a, b) - form a number eg, formNum(74, 23) - 7423
if(formNum(a, b) < formNum(b, a)
swap(a, b);

Now just print that array, we get the largest number.

Here's the code

``````/*
Given an integer array, sort the integer array such that the concatenated
integer of the result array is max. e.g. [4, 94, 9, 14, 1] will be sorted
to [9,94,4,14,1] where the result integer is 9944141
*/

#include<iostream>
using namespace std;

int digits(int num)
{
if(!num)
return 0;
int count = 0;
while(num)
{
num /= 10;
count++;
}
return count;
}

int formNum(int a, int b)
{
int digA = digits(a);
int digB = digits(b);
int factor = 1;
for(int i=0;i<digB;i++)
factor = 10*factor;
return (a*factor + b);
}

int MSB(int num)
{
if(num<=9)
return num;
else
{
while(num>=10)
num /= 10;
}
return num;
}

void function(int arr[], int size)
{
for(int i=0;i<size;i++)
{
for(int j=i+1;j<=size;j++)
{
if(MSB(arr[i]) < MSB(arr[j]))
swap(arr[i], arr[j]);
}
}
for(int i=0;i<size;i++)
{
if(digits(arr[i]) == digits(arr[i+1]))
continue;
else
{
if(formNum(arr[i], arr[i+1]) < formNum(arr[i+1], arr[i]))
swap(arr[i], arr[i+1]);
}
}

cout<<"  Number is :- ";
for(int i=0;i<=size;i++)
cout<<arr[i];
cout<<endl;
}

int main()
{
int arr[] = {9,99,91,5,59,8,81,4,44,21};
int size = sizeof(arr)/sizeof(*arr);

function(arr, size-1);

system("PAUSE");
return 0;
}``````

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

``````a = [4, 94, 9, 14, 1]

def compare(a, b):
if (int(str(a)+str(b)) > int(str(b)+str(a))):
return -1
elif (int(str(a)+str(b)) == int(str(b)+str(a))):
return 0
else:
return 1

print sorted(a, cmp = compare)``````

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

Just sort them lexicographically

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

indeed

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

9, 8 ,94

will this work?

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

Sort them lexicographically can yield a wrong result. So to say "14" is greater than "1" so if we sort from high to low then we will put "14" followed by "1". To solve this is to write a special class which implements Comparable. In compareTo() we need to do the following.

``````public static class wiredInt implements Comparable{
String val;
public wiredInt(int v){ val = ""+v;}
@Override
public int compareTo(Object arg0) {
String other = ((wiredInt) arg0).val;
for(int i=0;i<val.length();i++){
if(i == other.length()) return 1;
if(val.charAt(i) < other.charAt(i))	return  1;
if(val.charAt(i) > other.charAt(i))	return  -1;
}
return 1;
}
public String toString(){return val;}
}//end class``````

After that, simply cast the int array to this class and simply use sort it. (see below)

``````/**
* Sort the integer array such that the concatenated integer of the
* result array is max. e.g. [4, 94, 9, 14, 1] will be sorted to
* [9,94,4,14,1] where the result integer is 9,944,141
* @param intarray
*/
public static void wiredSort(int[] intarray){
Vector<wiredInt> intArray_ = new Vector<wiredInt>();
for(int i=0;i<intarray.length;i++)
java.util.Collections.sort(intArray_);
for(int i=0;i<intarray.length;i++)
System.out.print(intArray_.get(i));
}``````

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

Logic in descending order quick sort with compartor
Am working on the radix sort MSB thingy, any smarter ideas

``````bool is_lesser(int* A, int i, int j)
{
std::stringstream str1;
str1 << A[i] << A[j];
std::stringstream str2;
str2 << A[j] << A[i];
return atoi(str1.str().c_str()) > atoi(str2.str().c_str());
}

// descending order
//  greater ... pivot .. lesser
// 7, 8, 98, 979, 40, 14, 4, 99
// 8, 7
int partition(int *A, int p, int q)
{
if(p>=q)
{
return p;
}

int pivot = A[p], i = p, j = p+1;

while(j<=q)
{
if(is_lesser(A, p, j))
{
j++;
}
else
{
swap_(A, i+1, j);
j++; i++;
}
}
swap_(A, p, i);
return i;
}

void quicksort(int *A, int p, int q)
{
if(p >= q)
return;
int r = partition(A, p, q);
if(r > q)
return;
quicksort(A, p, r-1);
quicksort(A, r+1, q);
}

int main(int argc, char* argv[])
{
static const int N = 8;
int A[N] = {99, 87, 77, 14, 4, 43, 98, 9};

std::cout << "initial array  ";
for(int i=0; i<N; ++i)
std::cout << A[i] << " ";
std::cout << std::endl;

quicksort(A, 0, N-1);
for(int i=0; i<N; ++i)
std::cout << A[i] << " ";
std::cout << std::endl;
return 0;
}``````

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.