## Facebook Interview Question for Software Engineer / Developers

• 1

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

There is a O(n) solution:
1. Convert the array to a Linklist and build a Hashtable point to each Linklist nodes.
2. Create an array used to indicate the group number.
3. Take the head of the Linklist and mark its corresponding group number of the array as 1.
4. Assume the value of the Linklist head is n. set MIN= MAX= n.

5. Check if MIN-1 and MAX+1 is in the Hashtable. If yes, remove them from the Hashtable and mark the corresponding element as group 1. MIN = MIN -1 if (MIN-1) is there and MAX = MAX + 1 if MAX +1 is identified.
6. Continue step until both MIN and MAX cannot be identified.
7. add group number by 1 and go to Step 3, until there is no element in the LinkList.
8. now we have an array of group numbers with the same index as the original array and we can build the group.

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

neat solution. good use of hashtable.

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

neat

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

Interesting solution, But will it still be O(n) when you print the result also? You have to traverse the group array multiple times/ sort it.

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

it's not O(n). a sorting algorithm is at least O(nlogN)

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

hi, i find a flaw in your solution. see: 8 11 3 10 9 7 2 1. the desired final sequence is: 8 11 10 9 7 and 3 2 1. as your solution, when process first node 8, we will then process 7 and 9. and after that, we got 11.
but as the problem said before, we need to keep the subarray's original order.
may be i'm not fully understand your algorithm, but i think your algo pollute the subarray's original order

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

It is easy. You use a technique called "index sorting", C#, Java, etc. all have overloads of the sort call which can tandem sort two arrays. So essentially you have two arrays

int[] numbers = {5, 7, 8, 2, 9, 3} or whatever
int[] indices = {0, 1, 2, 3, 4, 5}

sort indices and numbers by the elements in numbers.

numbers = {2, 3, 5, 7, 8, 9}
indices = {3, 5, 0, 1, 2, 4}

Then divide numbers/indices into consecutive groups, which is easy.

Resort numbers/indices but sort by indices. Then just walk through numbers printing out the values.

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

this is a neat solution

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

neat solution, thx!

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

its cute. but sorting takes O(n*logn), with another pass of O(n). so it's no cheaper than the other more complex and less elegant solutions.

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

O(nlogn) runtime and O(n) space

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

May be a neat solution but this not solving the problem. By sorting you have lost the order. The problem clearly says the orginal order should be preserved.

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

Or you can also use an array of pair<int, int> and sort them by Key(number) and Value(index), if you don't have index sort

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

How are you dividing the numbers in to consecutive groups? There can be many groups present

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

The original order can be preserved because after first sorting the numbers, we can sort each group of consecutive numbers by their indices again.

After sorting, you can divide the consecutive numbers into groups by simply noting which element isn't followed by element+1. However, this solution didn't address the case when there are duplicates, which is the tricky part. For instance, given "789123789", the sorted list is "123778899", and you now have 2 groups of "789"...

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

My implementation of this idea. The code is fairly long even when I am assuming there are no duplicates :(

``````class Element implements Comparable<Element> {
int value;
int position;
public Element(int _value, int _position) {
value = _value;
position = _position;
}

public int compareTo(Element e2) {
return value - e2.value;
}
}

class ElementComparator implements Comparator<Element> {
public int compare(Element e, Element e2) {
return e.position - e2.position;
}
}

class ConsecutiveGroups {
// O(n) solution probably exists, but is troublesome
// instead, we will simply sort the numbers (along with their indices)
// identify the consecutive groups from the sorted list, and sort each
// group again by their indices
static ArrayList<ArrayList<Element>> group(int[] arr) {
int len = arr.length;
Element[] elements = new Element[len];
for(int i=0; i<len; i++) {
elements[i] = new Element(arr[i], i);
}

Arrays.sort(elements);
ArrayList<ArrayList<Element>> groups = new ArrayList<ArrayList<Element>>();
ArrayList<Element> group = new ArrayList<Element>();
for(int i=0; i<len; i++) {
Element element = elements[i];
if(i>0 && element.value != elements[i-1].value + 1) {
group = new ArrayList<Element>();
}
}

for(ArrayList<Element> aGroup : groups) {
Collections.sort(aGroup, new ElementComparator());
}
return groups;
}

public static void main(String[] args) {
ArrayList<ArrayList<Element>> groups = group(new int[]{8,2,4,7,1,0,3,6});
for(ArrayList<Element> group : groups) {
for(Element element : group)
System.out.print(" " + element.value);
System.out.println();
}
}
}``````

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

I think this question can be solved by using 2 priority queues.
Create data structure Node(VAL, INDEX). Index is the index value in the original array, VAL is its value for that index.BTW, the first priority queue compares elements by the its VAL value. And the second priority queue compares each other by its index value.

Step 1: Put all the nodes into the 1st priority queue.
Step 2: keep poping the node from 1st priority queue and push this node into 2nd priority queue if their value is consecutive. If not consecutive, pop and print all the elements in the 2nd priority queue.
Step 3: continue step 2 until the 1st priority queue is empty.

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

amazing, thanks

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

use an additional array to sort the numbers,
once numbers are sorted, O(nlogn)
linear scan to find the range,
within each range,
re-arrange the sorted array to reflect the original order, O(n2)
so it's a O(n2) in time and O(n) in space algorithm,
any better solutions?

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

it's a O(n*logn) in time and O(n) in space algorithm,

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

After getting the range, instead of re-arranging the sorted array to its original form, you select each element in the original array and use O(logn) time to identify its position in the sorted array. Use constant time to identify its range. Then, the overall time complexity is O(nlogn). The space needed is bigger, but still O(N).

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

In the initial eg, where are there 2 groups ? (why not 1 or 3 ?) I don't get the question - its vague.

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

above is a neat solution - thx!

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

for:8 2 4 7 1 0 3 6
ind:0 1 2 3 4 5 6 7

after sorting:
nos:0 1 2 3 4 6 7 8
ind:5 4 1 6 2 7 3 0

now how to proceed?????

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

Per some of the questions above - the original problem does not define how to divide the list into sub lists. However, to answer your question, split your list at any index. Then sort each of your resulting lists by the index.

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

something like sorting based off a pivot, right? like how quick sort does it? that is how i thought this can be done.

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

as per index sorting method mentioned above, since all numbers are in one range you will sort ALL of them according to the indices and end up with what you started which is the right solution. This could be the worst case for 'index sorting'.

Blackhat - the problem with quicksort is its not stable which is what we need here.

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

1. Identify range - One pass
2. Identify number of elements within each range - One pass
3. Fill destination array by maintaining starting positions of each range - One pass of source array.
O(n) time and O(n) space

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

Yea, I don't think you can identify range with one pass, or you could have sorted them within one pass( which is basically a bucket sort, and it's O(nk))

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

1. Identify range - One pass, how? We have to use sort

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

There is a O(n) solution:
1. Convert the array to a Linklist and build a Hashtable point to each Linklist nodes.
2. Create an array used to indicate the group number.
3. Take the head of the Linklist and mark its corresponding group number of the array as 1.
4. Assume the value of the Linklist head is n. set MIN= MAX= n.

5. Check if MIN-1 and MAX+1 is in the Hashtable. If yes, remove them from the Hashtable and mark the corresponding element as group 1. MIN = MIN -1 if (MIN-1) is there and MAX = MAX + 1 if MAX +1 is identified.
6. Continue step until both MIN and MAX cannot be identified.
7. add group number by 1 and go to Step 3, until there is no element in the LinkList.
8. now we have an array of group numbers with the same index as the original array and we can build the group.

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

I think this question asks partitioning algorithm of quicksort..someone above mentions quicksort is not stable, but being stable means whethe the same key are in the same order as original one...not exactly the question asks. Here's the O(N), inplace partitioning algorithm

int first_larger=0;
int pivot = N-1; (assuming pivot is at the end of array);

for(int i=0; i<pivot; i++)
{
if(array[i] < array[pivot])
swap(&array[i], array[first_larger++];
}
swap(&array[first_larger], &array[pivot]);

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

Solution 1: O(n)-time O(n)-space Hashtable
Solution 2: O(n^2)-time O(1)-space Brute force

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

This problem is not clear: how to seperate the group?
There must be a number x, the left group < x, and the right group >= x.
If x is given, the solution is:
1. Identify how many elements >= x, and get the first_large position;
2. Iteratively by each element, get the final position, and store to a position array;
3. Swap the elements according to the position array;
The complexity is O(N) in both time and space.

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

find min and max element in the array
say min and max
find the sum of all consecutive numbers from min to max
expected_sum=max(max+1)/2 - (min-1)(min)/2

Now sum the total elements in the array
Say actual_sum

We know the number of consecutive missing elements in the array by
missing= (max-min)- total_size of array

now the starting point of the missing sequence is

expected - total_sum = missing * pivot + (missing+1)*missing/2

we will get pivot by the above approach
Take O(n) extra space and use the quicksort technique.

Extra space since quicksort is not the stable sorting algorithm
somplexity O(n)time + o(n)space

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

``````#include<stdio.h>
#include<stdlib.h>
int sort(const void *x, const void *y) {
return (*(int*)x - *(int*)y);
}
main()
{
int N;
scanf("%d",&N);
int arr[N];
int arrsort[N];
int i;
for(i=0;i<N;++i)
{
scanf("%d",&arr[i]);
arrsort[i]=arr[i];
}

qsort(arrsort, N, sizeof(int), sort);
int range[N][2];
int l,h,c,d,count=0;
l=arrsort[0];c=l;h=l;
for(i=0;i<N;++i)
{
d=arrsort[i];
if(d==c+1||d==c) { h=d;c=d;}

else
{
range[count][0]=l;range[count][1]=h;count++;
l=d;c=d;h=d;
}
}
range[count][0]=l;range[count][1]=h;count++;
printf("  %d       ",count)	;
for(i=0;i<count;++i)
{
printf("\nl %d  h %d ",range[i][0],range[i][1]);
}
int group[count][N];

for(i=0;i<count;++i)
group[i][0]=0;

for(i=0;i<N;++i)
{
c=arr[i];d=0;
while(d<count)
{
if(c>=range[d][0]) ++d;
else break;
}
--d;
group[d][++group[d][0]]=c;
}

for(i=0;i<count;++i)
{
printf("\n");
for(h=1;h<=group[i][0];++h)
{
printf(" %d->",group[i][h]);
}
}

}``````

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

Here is the hashtable solution in Java. What I am doing is this:
1) put array elements as keys in hashtable with values (group numbers) 0.
2) Initialize group to 0.
3) Incrementing group and going through each array element and finding its key in hashtable. If value is 0 group hasn't been assigned and assign value to current group number. finding all elements arrayelement+-k which exist in hashtable and assign them the current group number too.
4) Separating out groups in O(n) time.

Can someone comment on complexity of step 3? I have a feeling that its more than O(n) because of the while loop but I am not sure.

``````import java.util.*;

public class StringCompare {

public static void printConsecutiveGroups(int[] arr) {

Hashtable<Integer,Integer> h = new Hashtable<Integer,Integer>();
int group=0;

for (int i=0;i<arr.length;i++){
h.put(arr[i], 0);
}

for (int i=1;i<arr.length;i++){
if (h.get(arr[i])==0)
{
group++;
h.put(arr[i],group);
int k=1;
while(h.get(arr[i]-k)!=null){
h.put(arr[i]-k,group);
k++;
};
k=1;
while(h.get(arr[i]+k)!=null){
h.put(arr[i]+k,group);
k++;
};

}
}

String[] groupStrings=new String[group];
Arrays.fill(groupStrings,"");
for (int i=0;i<arr.length;i++){
groupStrings[h.get(arr[i])-1]+=arr[i]+" ";
}
for (int g=0;g<group;g++){
System.out.println("{"+groupStrings[g]+"}");
}
}

public static void main(String[] args){
//		int[] arr={8, 2, 4, 7, 1, 0, 3, 6, 9,13};
int[] arr={8, 11, 3, 10, 9, 7, 2, 1};
printConsecutiveGroups(arr);
}
}``````

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

Please ignore the classname and excuse my english. I wrote it very fast

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

I don't understand what this question want, why 2,1,0 not grouped?

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

An O(lgn) solution. the result is like { 0 0 1 0 1 0 2 2 1 0 0}, means the elements with the same group number are in the same group.

{

public static int[] consecutiveGroup(int[] a)
{
int[] result = new int[a.length];
HashMap<Integer, Integer> hmap = new HashMap<Integer, Integer>();
for (int i=0; i<a.length; i++)
{
hmap.put(a[i], i);
}
Arrays.sort(a);
int groupNum = 0;
for (int i=0; i<a.length; i++)
{
result[hmap.get(a[i])] = groupNum;
if (i+1<a.length && a[i+1]>a[i]+1)
{
groupNum++;
}
}
return result;
}

}

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

how is this o(log(n)) when you do Arrays.sort(a) ? Wouldnt this be O(n*log(n)) ?

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

``````static int[] findConsecutiveLists(int[] list) {
int [] retList = new int[list.length];
HashMap<Integer, Group> reqMin = new HashMap<Integer, Group>();
HashMap<Integer, Group> reqMax = new HashMap<Integer, Group>();

for (int index = 0; index < list.length; index++){
if (reqMin.containsKey(list[index])){
Group myGroup = reqMin.get(list[index]);
reqMin.remove(list[index]);
if (reqMax.containsKey(list[index])){
Group newGroup = reqMax.get(list[index]);
reqMax.remove(list[index]);
myGroup.merge(newGroup);
reqMax.put(myGroup.keyMax +1, myGroup);
reqMin.put(myGroup.keyMin - 1, myGroup);
}
else {
reqMin.put(myGroup.keyMin - 1, myGroup);
}
} else if (reqMax.containsKey(list[index])){
Group myGroup = reqMax.get(list[index]);
reqMax.remove(list[index]);
reqMax.put(myGroup.keyMax +1, myGroup);
} else {
Group myGroup = new Group();
reqMax.put(myGroup.keyMax +1, myGroup);
reqMin.put(myGroup.keyMin - 1, myGroup);
}
}

int cntr = 0;
for (int key : reqMin.keySet()){
while (!reqMin.get(key).content.isEmpty())
retList[cntr++] = list[reqMin.get(key).content.poll()];
}
return retList;
}

static class Group {

PriorityQueue<Integer> content = new PriorityQueue<Integer>();
int keyMin = Integer.MAX_VALUE;
int keyMax = Integer.MIN_VALUE;

void merge(Group newg){
keyMin = Math.min(this.keyMin, newg.keyMin);
keyMax = Math.max(this.keyMax, newg.keyMax);
}

keyMin = Math.min(this.keyMin, item);
keyMax = Math.max(this.keyMax, item);
}
}``````

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

``````void divide(vector<int>& a)
{
if (a.size() == 0)
return ;
cout << a[0] << " ";
for (int i=1; i < a.size(); i++)
{
if (a[i] != a[i-1]) cout << endl;
cout << a[i] << " ";
}

}``````

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

You can convert this problem as a graph and solve it by bfs.

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

``````public static void main(String[] args){
int[] a={8,2,4,7,1,0,3,6};
solve(a);

}

static void solve(int[] a){
ArrayList<Integer> r=new ArrayList<>();

System.out.println("increment order start");
for(int i=0;i<a.length;i++){
int tmp=a[i];
tmp++;
for(int j=i+1;j<a.length;j++){
if(tmp==a[j]){
tmp++;
}
}
if(r.size()>=2){
for(int k:r){
System.out.print(k + " , ");
}

}
System.out.println("\r\n");
r.clear();
}

System.out.println("increment order end");

System.out.println("decrement order start");
for(int i=0;i<a.length;i++){
int tmp=a[i];
tmp--;
for(int j=i+1;j<a.length;j++){
if(tmp==a[j]){
tmp--;
}
}

if(r.size()>=2){
for(int k:r){
System.out.print(k + " , ");
}
}
r.clear();
System.out.println("\r\n");
}
System.out.println("decrement order end");

}``````

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

In Java:

``````public static void splitArray() {

ArrayList<Integer[]> result = new ArrayList<Integer[]>();

Integer[] array = new Integer[]{8,2,4,7,1,0,3,6};

ArrayList<Integer> list = new ArrayList<Integer>(Arrays.asList(array));

Arrays.sort(array);

HashMap<Integer, Integer> consecutives = new HashMap<Integer, Integer>();

consecutives.put(list.indexOf(array[0]), array[0]);

for (int i = 1; i < array.length; i++) {
if (array[i] != array[i -1] + 1) {
consecutives = new HashMap<Integer, Integer>();
}
consecutives.put(list.indexOf(array[i]), array[i]);

}

}``````

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

Step1: Make a pass on the entire array to find the min and max numbers, which is nothing but the range of numbers.
Step2: Use count sort to sort the entire range of numbers.
Step3: Make another pass on the count sorted array to identify the group of consecutive numbers.

O(1)+O(nK)=O(n) time and
O(number of elements in the input array) space required

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

This is method becomes expensive when the range is broad while the number of elements is few.

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

what is the count sort, BTW?

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

First, the question is too vague! What criteria to use for division into groups? Where should be the output ( i.e. each group in its own file, or in the another buffer, or one should use the same input buffer for output )? How many input rules we may expect? e t.c.
In particular, if we are getting groups using a range query, and each group correspond to each range, and we store selections in their own buffers, then we do NOT need sorting at all. We just iterate through the input, determine the group number ( comparing each input against all rules ) and output the input to the corresponding buffer... But this is too silly to consider :)

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

construct a BST from the given array. Then it becomes easier to construct the tree. Though the space complexity increases a bit but time complexity remains low.

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

1. Identify range - One pass
2. Identify number of elements within each range - One pass
3. Fill destination array by maintaining starting positions of each range - One pass of source array.
O(n) time and O(n) space

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.