Facebook Interview Question Software Engineer / Developers
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.
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
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.
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.
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.
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
How are you dividing the numbers in to consecutive groups? There can be many groups present
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"...
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) {
groups.add(group);
group = new ArrayList<Element>();
}
group.add(element);
}
groups.add(group);
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();
}
}
}
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.
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?
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).
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?????
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.
something like sorting based off a pivot, right? like how quick sort does it? that is how i thought this can be done.
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.
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
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.
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]);
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.
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
#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]);
}
}
}
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);
}
}
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;
}
}
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]);
myGroup.addItem(list[index], 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 {
myGroup.addItem(list[index],index);
reqMin.put(myGroup.keyMin - 1, myGroup);
}
} else if (reqMax.containsKey(list[index])){
Group myGroup = reqMax.get(list[index]);
reqMax.remove(list[index]);
myGroup.addItem(list[index],index);
reqMax.put(myGroup.keyMax +1, myGroup);
} else {
Group myGroup = new Group();
myGroup.addItem(list[index],index);
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);
content.addAll(newg.content);
}
void addItem(int item, int index){
keyMin = Math.min(this.keyMin, item);
keyMax = Math.max(this.keyMax, item);
content.add(index);
}
}
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];
r.add(tmp);
tmp++;
for(int j=i+1;j<a.length;j++){
if(tmp==a[j]){
r.add(tmp);
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];
r.add(tmp);
tmp--;
for(int j=i+1;j<a.length;j++){
if(tmp==a[j]){
r.add(tmp);
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");
}
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) {
result.add(consecutives.values().toArray(new Integer[consecutives.values().size()]));
consecutives = new HashMap<Integer, Integer>();
}
consecutives.put(list.indexOf(array[i]), array[i]);
}
result.add(consecutives.values().toArray(new Integer[consecutives.values().size()]));
}
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
comments/optimization are welcome
This is method becomes expensive when the range is broad while the number of elements is few.
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 :)
There is a O(n) solution:
- Anonymous January 18, 20101. 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.