Citigroup Interview Question Java Developers
Team: Risk Management/CMOT
Country: India
Interview Type: In-Person
Tried following with above algo. working fine for me.. :)
public class ArraySortPerformance {
//Array Length not specified in problem. Lets say n=50
private final static int ARRAY_LENGTH = 50;
public static void main(String[] args) {
//Prepare Input Data
int[] inputArray = new int[ARRAY_LENGTH];
Random random = new Random();
for(int i=0;i<50;i++){
inputArray[i] = random.nextInt(100);
}
//Create Temporary array
int[] tempArray = new int[101];
for(int i: inputArray){
tempArray[i]++;
}
//Sort Result based on temp
int[] resultArray = new int[ARRAY_LENGTH];
for(int i=1, j=0; i<=100;i++){
if(tempArray[i] == 0)
continue;
else{
for(int k=0; k<tempArray[i];k++){
resultArray[j] = i;
j++;
}
}
}
//Print input and output for verification
System.out.println("Input::");
for(int j: inputArray){
System.out.print(j+" ");
}
System.out.println("");
System.out.println("Result::");
for(int j: resultArray){
System.out.print(j+" ");
}
}
}
by using insertion sort.If the number we are inserting are not in reverse order ,then the time complexity is O(n).
Time Complexity : O(n)
Space Complexity : Input Range (works for only +ve numbers)
Data Structure Used : Hash table[1..100]
Algorithm :
1. Initialize Hash table[1...100] with 0.
2. Now Read values one by one in a variable index
// read----> index
3. Now increment the value in hash table at location of index
// hash_table[index]++;
4. If input is NOT over then go to step 2
else go to next step.
5. Now traverse the whole hash_table and print 'index' simultaneously wherever we get the value greater than 0.
6. STOP
//it will also keep the duplicates
If n >= 100, the problem can be solved in O(n) time and O(1) space by in-place counting. Java ode shown as below:
public void sort(int[] arr) {
int mod = 128;
int mask = mod - 1;
for (int i : arr) {
arr[(i & mask) - 1] += mod;
}
for (int i = 99, last = arr.length - 1; i >= 0; --i) {
int count = arr[i] / mod;
while (count-- > 0) {
arr[last--] = i + 1;
}
}
}
Approach:
- Ajith January 11, 20141. Numbers will be between 1 & 100. So, create an array of integers - tmp[] - of size 100
2. Array tmp[] keeps track of repetitions in the input array - input[].
3. Initialize each element of tmp[] to 0
3. Traverse input[], increment the corresponding index in tmp[]
4. Create an array of the same size as input array - input[]. Call it result[]
5. Traverse tmp[] and get 'count' for each.
6. If count == 0, continue
7. Else, add the 'index' those many times into result[]
8. Finally, return result[]