Facebook Interview Question
Java DevelopersCountry: United States
Please check out my attempted solution for in-place sorting in Java.
Time: O(N), Space: O(1)
private static void sortSpecialArray(String[] array) {
sortSpecialArrayUtil(array);
sortSpecialArrayUtil(array);
}
/**
* Given an array with ['a1', 'a2', 'a3', ..., 'aN', 'b1', 'b2', 'b3', ...,'bN', 'c1'...'cN']
* sort the array to be a1, b1, c1...
*
* O(N) time complexity
* O(1) space complexity
*/
private static void sortSpecialArrayUtil(String[] array) {
// O(1) space complexity requires this function to sort the array in-place
// this can be done using a pointer that keeps track of where we are
// in the array. The idea is to swap the values in the array to get the element in the right place.
int n = stripNumber(array[array.length - 1]);
int charCount = array.length / n;
// start the loop at index = 1, up until index = array.length - 2
// ignore those two elements because they're already in the right place
int lastIndex = array.length - 2;
String element;
for (int i = 1; i <= lastIndex; i++) {
element = array[i];
swap(array, i, getCorrectIndex(charCount, element));
}
}
/**
* Assume that array's element is in format of something like "a1", where there can only be one 'letter' before the number
* extract number from the string
*
* This is done in time O(K), where K is the length of the String
*/
private static int stripNumber(String str) {
return Integer.parseInt(str.substring(1, str.length()));
}
private static int getCorrectIndex(int charCount, String element) {
char c = Character.toLowerCase(element.charAt(0));
int num = stripNumber(element);
// the correct index is found by the following formula: index = charDistance + (charCount * (num - 1))
int charDistance = c - 'a';
return charDistance + (charCount * (num - 1));
}
private static void swap(String[] array, int fromIndex, int toIndex) {
String temp = array[toIndex];
array[toIndex] = array[fromIndex];
array[fromIndex] = temp;
}
@Test
public void testSortArray() {
String[] testCase = new String[] { "a1", "a2", "a3", "a4", "a5", "b1", "b2", "b3", "b4", "b5", "c1", "c2", "c3", "c4", "c5", "d1", "d2", "d3", "d4", "d5" };
sortSpecialArray(testCase);
for (String s : testCase) {
System.out.print(s + " ");
}
}
//considering we were give the value of N and array of size 3N.
//input ['a1,'a2,'a3','b1','b2','b3','c1','c2','c3'], N= 3
//output ['a1,’b1,’c1,’a2’,’b2’,’c2’,’a3’,’b3’,’c3']
public String[] getStaggeredArray(String[] arry, int n) {
String[] result = new String[arry.length];
if ( (3*n) != arry.length) {
System.out.println("Something is wrong");
}
int counter = 0;
for(int i =0; i < n; i++) {
result[counter++] = arry[i];
result[counter++] = arry[(i+n)];
result[counter++] = arry[(i+(2*n))];
}
return result;
}
// Both time complexity and space complexity O(n)
function countSubarrays(values) {
var current = '';
var count = 0;
values.forEach((v, n) => {
if (current != v[0]) {
current = v[0];
count += 1;
}
});
return count;
}
function inplaceMove(values, moves) {
//console.log('[ ' + moves.join(' -> ') + ' ]');
if (moves.length <= 1 || moves.length === 2 && moves[0] === moves[1])
return;
if (moves.length === 3 && moves[0] === moves[2]) {
[values[moves[1]], values[moves[0]]] = [values[moves[0]], values[moves[1]]];
return;
}
var temp = values[moves[0]];
for (var i = moves.length - 1; i > 0; i -= 1) {
values[moves[i]] = values[moves[i - 1]];
}
values[moves[1]] = temp;
}
function inplaceStagger(values) {
var subarrays = countSubarrays(values),
groups = values.length / subarrays,
touched = {},
moves = [],
limit = values.length - 2;
for (var i = 1; i <= limit; i += 1) {
if (touched[i])
continue;
var src = i;
var dst = subarrays * (src % groups) + Math.floor(src / groups);
moves = [src, dst];
touched[src] = true;
if (src == dst) {
moves.length = 0;
continue;
}
while (dst !== i) {
src = dst;
dst = subarrays * (src % groups) + Math.floor(src / groups);
moves.push(dst);
touched[src] = true;
}
inplaceMove(values, moves);
moves.length = 0;
}
return values;
}
public class Main {
public static void main(String[] args) {
// write your code here
String[] tc = new String[] {
"a1", "a2", "a3", "a4", "a5", "a6", "a7", "a8", "a9", "a10", "a11",
"b1", "b2", "b3", "b4", "b5", "b6", "b7", "b8", "b9", "b10","b11",
"c1", "c2", "c3", "c4", "c5", "c6", "c7", "c8", "c9", "c10" , "c11",
"d1", "d2", "d3", "d4", "d5", "d6", "d7", "d8", "d9", "d10" , "d11",
};
sortArray(tc);
for (String s : tc) {
System.out.print(s + " ");
// a1 b1 c1 d1 a2 b2 c2 d2 a3 b3 c3 d3 a4 b4 c4 d4 a5 b5 c5 d5 a6 b6 c6 d6 a7 b7 c7 d7 a8 b8 c8 d8 a9 b9 c9 d9 a10 b10 c10 d10 a11 b11 c11 d11
}
}
private static void sortArray(String[] array) {
int n = getMaxNumber(array[array.length - 1]);
int charCount = array.length / n;
char[] chars = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'v', 'w', 'x', 'y', 'z'};
int index = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < charCount ; j++) {
array[index] = chars[j] + "" + i;
index++;
}
}
}
private static int getMaxNumber(String str) {
return Integer.parseInt(str.substring(1, str.length()));
}
}
struct less_than_key
{
inline bool operator()(const std::string& a, const std::string& b) {
int i = std::atoi(a.substr(1).c_str());
int j = std::atoi(b.substr(1).c_str());
if(i == j) {
return a[0] < b[0];
}
return i<j;
}
};
void sortSpecialArray(std::vector<std::string>& strings) {
std::sort(strings.begin(), strings.end(), less_than_key());
}
String[] staggerArrays(String[] input) {
String[] output = new String[input.length];
int j = 1;
for (int i = 0; i < input.length; i = i + 3) {
// The one in comments work too
// output[3*(j-1)] = input[i];
// output[3*(j-1) + 1] = input[i+1];
// output[3*(j-1) + 2] = input[i+2];
output[i] = "a" + j;
output[i + 1] = "b" + j;
output[i + 2] = "c" + j;
j++;
}
return output;
}
String[] staggerArrays(String[] input) {
String[] output = new String[input.length];
int j = 1;
for (int i = 0; i < input.length; i = i + 3) {
// The one in comments work too
// output[3*(j-1)] = input[i];
// output[3*(j-1) + 1] = input[i+1];
// output[3*(j-1) + 2] = input[i+2];
output[i] = "a" + j;
output[i + 1] = "b" + j;
output[i + 2] = "c" + j;
j++;
}
return output;
}
import java.util.Arrays;
public class StaggerArrays {
public static void main(String[] args) {
String array1[] = new String[]{"a1", "a2", "a3","a4"};
String array2[] = new String[]{"b1", "b2", "b3","b4"};
String array3[] = new String[]{"c1", "c2", "c3","b4"};
String[] staggerArray = new String[array1.length * 3];
for (int i=0,j =0;i < staggerArray.length; i+=3,j++) {
staggerArray[i] = array1[j];
staggerArray[i + 1] = array2[j];
staggerArray[i + 2] = array3[j];
}
System.out.println(Arrays.asList(staggerArray));
}
}
//var strArray = ["a1", "a2", "a3", "b1", "b2", "b3", "c1", "c2", "c3", "d1", "d2", "d3"]
var strArray = ["a1", "a2", "b1", "b2", "c1", "c2"]
func firstLetterOf(_ string: String) -> Character? {
return string.first
}
func sortArray(_ array: inout [String]) -> [String] {
guard !array.isEmpty,
let firstLetter = firstLetterOf(array[0]) else {
return array
}
// calculate number of letters in one group
var numberOfLettersInGroup = 0
for group in array {
guard let letter = firstLetterOf(group), letter == firstLetter else {
break
}
numberOfLettersInGroup += 1
}
// sorting algorithm
let numberOfGroups = array.count / numberOfLettersInGroup
var currentIndex = 0
var p = 0
for i in 0..<numberOfLettersInGroup-1 {
let multiplicator = numberOfLettersInGroup - i
for j in 0..<numberOfGroups {
let removingIndex = j * multiplicator + p
//
print("removing from: \(removingIndex)")
let element = array.remove(at: removingIndex)
//
print("inserting to: \(currentIndex)")
array.insert(element, at: currentIndex)
//
currentIndex += 1
print(array)
}
p = currentIndex
}
return array
}
sortArray(&strArray)
class Solution {
public static void main(String[] args) {
int n = 5;
String [] outputArray= new String[n*3];
for (int i = 0; i < n*3; i++) {
int j= (i / 3) + 1;
outputArray[i] ="a"+j;
outputArray[++i] ="b"+j;
outputArray[++i] ="c"+j;
}
System.out.println(Arrays.asList(outputArray));
}
}
a1a2|a3a4 b1b2|b3b4 c1c2|c3c4
- sumitgaur.iiita February 12, 2018a1a2|b1b2|a3a4|b3b4|c1c2c3c4
a1a2|b1b2|a3a4|c1c2|b3b4c3c4
(a1a2b1b2c1c2)(a3a4b3b4c3c4)