Facebook Interview Question
Software DevelopersCountry: United States
instead do like this
private static List<Integer> interleavedListSimple(List<List<Integer>> lists) {
List<Integer> interleaveList = new ArrayList<>();
int maxSize = 0;
for (List<Integer> list : lists)
maxSize = Math.max(maxSize, list.size());
int index = 0;
while (index < maxSize) {
for (int i = 0; i < lists.size(); i++) {
if (index < lists.get(i).size()) {
interleaveList.add(lists.get(i).get(index));
}
}
index++;
}
return interleaveList;
}
Solution in Scala using transpose:
object InterleaveArrays {
def main(args: Array[String]): Unit = {
val list1 = List(1,2,3)
val list2 = List(9,0)
val list3 = List(5)
val list4 = List(-4, -5, -2, -3, -1)
println(getInterleaved(list1, list2, list3, list4))
}
def transpose[A](xs: List[List[A]]): List[List[A]] = xs.filter(_.nonEmpty) match {
case Nil => Nil
case ys: List[List[A]] => ys.map{ _.head }::transpose(ys.map{ _.tail })
}
def getInterleaved(lists : List[Int]*) : List[Int] = {
transpose(lists.toList).flatten
}
}
// prints List(1, 9, 5, -4, 2, 0, -5, 3, -2, -3, -1)
$input = [[1,2,3], [9, 0], [5], [-4,-5,-2,-3,-1]];
$maxlength = 0;
$output = array();
foreach($input as $list){
if(count($list) > $maxlength){
$maxlength = count($list);
}
}
for($i = 0; $i < $maxlength; $i++){
for($k = 0; $k < count($input); $k++){
if(isset($input[$k][$i])){
$output[] = $input[$k][$i];
}
}
}
print_r($output);
<?php
$input = [[1,2,3], [9, 0], [5], [-4,-5,-2,-3,-1]];
$maxlength = 0;
$output = array();
foreach($input as $list){
if(count($list) > $maxlength){
$maxlength = count($list);
}
}
for($i = 0; $i < $maxlength; $i++){
for($k = 0; $k < count($input); $k++){
if(isset($input[$k][$i])){
$output[] = $input[$k][$i];
}
}
}
print_r($output);
private List<Integer> interleaved( List<List<Integer>> listOfLists ) {
List<Integer> list = new ArrayList<>();
int size = listOfLists.size();
int max = listOfLists.stream().mapToInt( s -> s.size() ).max().getAsInt();
for ( int j = 0; j < max; j++ ) {
for ( int i = 0; i < size; i++ ) {
if (listOfLists.get( i ).size() > j) {
list.add( listOfLists.get( i ).get( j ) );
}
}
}
return list;
}
private List<Integer> interleaved( List<List<Integer>> listOfLists ) {
List<Integer> list = new ArrayList<>();
int size = listOfLists.size();
int max = listOfLists.stream().mapToInt( s -> s.size() ).max().getAsInt();
for ( int j = 0; j < max; j++ ) {
for ( int i = 0; i < size; i++ ) {
if (listOfLists.get( i ).size() > j) {
list.add( listOfLists.get( i ).get( j ) );
}
}
}
return list;
}
vector<int> interleave(const vector<vector<int>>& input) {
vector<int> result;
int index = 0;
int maxSize = INT_MIN;
for (auto i : input) {
maxSize = max(maxSize, (int)i.size());
}
while (index < maxSize) {
for (int i = 0; i < input.size(); i++) {
if (index >= input[i].size())
continue;
result.push_back(input[i][index]);
}
index++;
}
return result;
}
private static int[] interleaveLists(List<List<Integer>> ll){
if(ll == null)
return null;
int listLength = 0;
int total = 0;
for(List<Integer> list : ll){
if(list == null)
continue;
listLength = Math.max(list.size(), listLength);
total += list.size();
}
int[] result = new int[total];
int index = 0;
for(int i = 0; i < listLength; ++i){
for(List<Integer> list : ll){
if(list == null)
continue;
if(i < list.size()){
result[index++] = list.get(i);
}
}
}
return result;
}
private static int[] interleaveLists(List<List<Integer>> ll){
if(ll == null)
return null;
int listLength = 0;
int total = 0;
for(List<Integer> list : ll){
if(list == null)
continue;
listLength = Math.max(list.size(), listLength);
total += list.size();
}
int[] result = new int[total];
int index = 0;
for(int i = 0; i < listLength; ++i){
for(List<Integer> list : ll){
if(list == null)
continue;
if(i < list.size()){
result[index++] = list.get(i);
}
}
}
return result;
}
//C++
void interleave(vector<vector<int>> grid)
{
int m = grid.size();
int n = 0;
for (int i = 0; i < m; i++)
n = max(n, grid[i].size());
vector<int> result;
result.reserve(m*n);
for (int j = 0; j < n; j++)
for (int i = 0; i < m; i++)
if (j < grid[i].size())
result.push_back(grid[i][j]);
for (auto i:result)
cout << i << " ";
}
public static List<Integer> mergeIntervals(final int[][] input) {
int max = 0;
final List<Integer> temp = new ArrayList<>();
for (final int[] array : input) {
if (array.length > max) {
max = array.length;
}
}
for (int k = 0; k < max; k++) {
for (int j = 0; j < input.length; j++) {
if (k < input[j].length) {
temp.add(input[j][k]);
}
}
}
return temp;
}
// using java
public static List<Integer> mergeIntervals(final int[][] input) {
int max = 0;
final List<Integer> temp = new ArrayList<>();
for (final int[] array : input) {
if (array.length > max) {
max = array.length;
}
}
for (int k = 0; k < max; k++) {
for (int j = 0; j < input.length; j++) {
if (k < input[j].length) {
temp.add(input[j][k]);
}
}
}
return temp;
}
I received this question in Feb 2018. I was told that there could be an undefined amount of arrays in the array so [1,[2,[3,4,5]],6,[7,8],9] was a possible input. Also that you didn't know the if the next element was a number so I wrote it in java as:
private ArrayList<Number> printList(ArrayList<Object> input){
ArrayList<Number> output = new ArrayList();
for(Object o: input){
if(o instanceof Number)
output.add(o);
else if (o instance of ArrayList)
output.addAll(printList(o));
}
return output;
}
Here is my solution
int[][] input = { { 1, 2, 3 }, { 0, 9 }, { 5 }, { 4, 6, 7, 8 } };
// expected out put is [1,0,5,4,2,9,7,3,7,8]
// int[] output = new int[];
ArrayList<Integer> output = new ArrayList();
int j = 0;
while (j < input.length) {
for (int i = 0; i < input.length; i++) {
int[] arrayAtindex = input[i];
if (j < arrayAtindex.length) {
output.add(arrayAtindex[j]);
}
}
j++;
}
System.out.println("output===>" + output);
private void getInterleaveList() {
int[][] input = { { 1, 2, 3 }, { 0, 9 }, { 5 }, { 4, 6, 7, 8 } };
// expected out put is [1,0,5,4,2,9,7,3,7,8]
// int[] output = new int[];
ArrayList<Integer> output = new ArrayList();
int j = 0;
while (j < input.length) {
for (int i = 0; i < input.length; i++) {
int[] arrayAtindex = input[i];
if (j < arrayAtindex.length) {
output.add(arrayAtindex[j]);
}
}
j++;
}
System.out.println("output===>" + output);
}
private void getInterleaveList() {
int[][] input = { { 1, 2, 3 }, { 0, 9 }, { 5 }, { 4, 6, 7, 8 } };
// expected out put is [1,0,5,4,2,9,7,3,7,8]
// int[] output = new int[];
ArrayList<Integer> output = new ArrayList();
int j = 0;
while (j < input.length) {
for (int i = 0; i < input.length; i++) {
int[] arrayAtindex = input[i];
if (j < arrayAtindex.length) {
output.add(arrayAtindex[j]);
}
}
j++;
}
System.out.println("output===>" + output);
}
class Solution {
public static void main(String[] args) {
// test case
int[][] input = {{1,2,3}, {9, 0}, {5}, {-4,-5,-2,-3,-1}};
int[] out = new int[input[0].length + input[1].length + input[2].length + input[3].length];
out = interleaveList(input);
for (int i = 0; i < out.length; i++)
System.out.print(out[i] + " ");
}
static public int[] interleaveList(int[][] in) {
// get max_len to cover all rows
int max_len = 0;
int size_all = 0; // size for all elements
for (int i = 0; i < in.length; i++) {
if (in[i].length > max_len)
max_len = in[i].length;
size_all += in[i].length;
}
int[] out = new int[size_all];
int k = 0;
// interleave in the loop
for (int i = 0; i < max_len; i++) {
for (int j = 0; j < in.length; j++) {
if (i < in[j].length) {
out[k++] = in[j][i];
}
}
}
return out;
}
}
public class InterleavedList {
static class Helper {
public int listIndex = 0;
public int selfIndex = 0;
public Helper(int listIndex) {
this.listIndex = listIndex;
}
@Override
public String toString() {
return "{" +
"listIndex=" + listIndex +
", selfIndex=" + selfIndex +
'}';
}
}
public static void main(String args[]) {
List<List<Integer>> input = new ArrayList<>();
List<Integer> one = new ArrayList<>();
one.add(1);
one.add(2);
one.add(3);
List<Integer> two = new ArrayList<>();
two.add(9);
two.add(0);
List<Integer> three = new ArrayList<>();
three.add(5);
List<Integer> four = new ArrayList<>();
four.add(-4);
four.add(-5);
four.add(-2);
four.add(-3);
four.add(-1);
input.add(one);
input.add(two);
input.add(three);
input.add(four);
System.out.println(interleavedList(input));
}
private static List<Helper> getIndexList(int totalLists) {
List<Helper> helpers = new ArrayList<>(totalLists);
for (int i = 0; i < totalLists; i++) {
helpers.add(new Helper(i));
}
return helpers;
}
private static List<Integer> interleavedList(List<List<Integer>> input) {
int totalLists = input.size();
//We use this list to iterate over input
List<Helper> helpers = getIndexList(totalLists);
int x = totalLists;
List<Integer> result = new ArrayList<>();
//We remove all the helper once their corresponding list exhaust
while (true) {
ListIterator<Helper> listIterator = helpers.listIterator();
while (listIterator.hasNext()) {
Helper h = listIterator.next();
//get the inner list by listIndex
List<Integer> inner = input.get(h.listIndex);
if (h.selfIndex < inner.size()) {
result.add(inner.get(h.selfIndex++));
} else {
//If all element traversed, remove it for next iteration
listIterator.remove();
}
}
if (helpers.isEmpty())
break;
}
return result;
}
}
This is very easy to understand; and has performance boost if one of the list size is >>> then other
Another version of easy code ;
private static List<Integer> interleavedListSimple(List<List<Integer>> lists) {
List<Integer> interleaveList = new ArrayList<>();
int maxSize = 0;
for (List<Integer> list : lists)
maxSize = Math.max(maxSize, list.size());
int index = 0;
while (index < maxSize) {
for (int i = 0; i < lists.size(); i++) {
if (index < lists.get(i).size()) {
interleaveList.add(lists.get(i).get(index));
}
}
index++;
}
return interleaveList;
}
Nearly optimal:
def merge_list_of_list( list_of_lists ){
iterators = list( list_of_lists ) as { $.o.iterator }
final_merge_list = list( )
added = true
while ( added ){
added = false
for ( it : iterators ){
added = it.hasNext
if ( added ){
final_merge_list += it.next // done
}
}
}
final_merge_list // return
}
List<Integer> interleave(List<List<Integer>> items){
if(items==null) return null ;
int size=items.size();
if(size==1) return items.get(0);
List<Integer> res = new ArrayList<>();
int idx=0;
boolean hasNext=true;
while(hasNext) {
hasNext=false;
for(List<Integer> list: items) {
if(idx <list.size() ) {
res.add(list.get(idx));
hasNext=true;
}
}
idx++;
}
return res;
}
and
public class InterleaveList {
/**
* Interleave list of lists in Java
* Example:
* input = [[1,2,3], [9, 0], [5], [-4,-5,-2,-3,-1,5,2,234,2,24,24,4]];
* output = [1,9,5,-4,2,0,-5,3,-2,-3,-1]
*/
private static int[] findInterleaveList(int[][] arr) {
List<Integer> interleaveList = new ArrayList<>();
boolean shouldVisit = true;
int index = 0;
while (shouldVisit) {
for (int i = 0; i < arr.length; i++) {
if (index < arr[i].length) {
interleaveList.add(arr[i][index]);
shouldVisit = true;
} else {
shouldVisit = false;
}
}
index++;
}
int[] list = new int[interleaveList.size()];
int position = 0;
for (Integer integer : interleaveList) {
list[position] = integer;
position++;
}
return list;
}
public static void main(String[] args) {
int[][] arr = {{1, 2, 3}, {9, 0}, {5}, {-4, -5, -2, -3, -1,5,2,234,2,24,24,4}};
int[] output = findInterleaveList(arr);
for (Integer interleave : output) {
System.out.print(interleave);
System.out.print("\t");
}
}
}
Code is wrong; this assume the last list is always greater then other list size;
try below input
[[1,2,3], [9,0],[5,9], [-4] ]
output you produce is
[1, 9, 5, -4, 2, 0, 9]
where as it should be
[1, 9, 5, -4, 2, 0, 9, 3]
here is the correct code
private static List<Integer> interleavedListSimple(List<List<Integer>> lists) {
List<Integer> interleaveList = new ArrayList<>();
int maxSize = 0;
for (List<Integer> list : lists)
maxSize = Math.max(maxSize, list.size());
int index = 0;
while (index < maxSize) {
for (int i = 0; i < lists.size(); i++) {
if (index < lists.get(i).size()) {
interleaveList.add(lists.get(i).get(index));
}
}
index++;
}
return interleaveList;
}
Using java, this code should work,
- PeyarTheriyaa April 19, 2018