Facebook Interview Question for Java Developers


Country: United States




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

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 + " ");
        }
    }

- Yoshi3003 March 18, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

a1a2|a3a4 b1b2|b3b4 c1c2|c3c4
a1a2|b1b2|a3a4|b3b4|c1c2c3c4
a1a2|b1b2|a3a4|c1c2|b3b4c3c4
(a1a2b1b2c1c2)(a3a4b3b4c3c4)

- sumitgaur.iiita February 12, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//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)

- sgundumonu February 15, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Technically impossible to solve as the best known algorithm for in-place non square matrix transpose does not satisfy the two conditions.

- jayz February 26, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static void sortSpecialArray(String[] array) {
        sortSpecialArrayUtil(array);
        sortSpecialArrayUtil(array);

}

- Jitrapon March 18, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Paul April 25, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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()));
    }

}

- hans83 August 07, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

We can ignore the input and and re-populate the array using division and modulo by (array.length/nLetters).
If we don't know how many letters (#{a,b,c} = 3), we can first scan the input to find that out.

- Hagai C February 10, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

nknkl;khjkh;

- Anonymous February 11, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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;

	}

- Anonymous February 11, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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;

	}

- Itika February 11, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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));
    }

}

- {novice} February 12, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

resa = []
resb = []
resc = []
for indexi, i in enumerate(lista[::3]):
resa.append(i)
resb.append(lista[index+1])
resc.append(lista[index+2])

- Anonymous February 13, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

//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)

- Igor Novik February 14, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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));
  }
}

- Anonymous February 14, 2018 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

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.

Learn More

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.

Learn More