Facebook Interview Question Front-end Software Engineers
Country: United States
Interview Type: Phone Interview
yes yours works sorry for spaming some solutions that don't have that 'while (B[tmp] != tmp)' check wont work.
cheers
Why do you need the while loop? Why not just:
public static void reorder(char [] A, int [] B){
for (int i = 0 ; i < B.length ; ++i) {
if (B[i] != i) {
swap(A, B[i], i);
swapIndex (B, B[i], i) ;
}
}
}
I admit the naming convention could have been difference for swapping chars and ints. Maybe swapCharacter or swapLetter instead of just swap.
Why is the while loop redundant? If you swap C with F in the first iteration of the loop in the example, F/1 is then stored at index 0. You need the outer loop pointer to stay in place until the correct element is in place (i.e. b[i] == i). Still O(n).
void swap(void* i, void* j, int size)
{
void* temp = malloc(size);
memcpy(temp,i,size);
memcpy(i,j,size);
memcpy(j,temp,size);
free(temp);
}
You can use this for generic swap, where size is sizeof(int) or sizeof(char) for this program
Isn't the data in array B getting mutated? Is there a way to solve this in O(n) time complexity and O(1) space without mutating the data of B array?
Implemented in Java. Runtime O(n), where n equals number of elements in array. Space O(1).
/**
* @throws NullPointerException if elements or indices are null
*/
public static void sort( String[] elements, int[] indices ) {
if ( elements.length != indices.length ) {
return;
}
for ( int i = 0; i < elements.length; i++ ) {
while ( indices[ i ] != i ) {
swap( elements, indices, i, indices[ i ] );
}
}
}
private static void swap( String[] elements, int[] indices, int fromIndex, int toIndex ) {
String element = elements[ fromIndex ];
int index = indices[ fromIndex ];
elements[ fromIndex ] = elements[ toIndex ];
indices[ fromIndex ] = indices[ toIndex ];
elements[ toIndex ] = element;
indices[ toIndex ] = index;
}
O(n)
public static void sortByIndex(char[] array, int[] indexes) {
if (array.length != indexes.length) return;
for (int i = 0; i < array.length; i++) {
// swap value
char temp = array[indexes[i]];
array[indexes[i]] = array[i];
array[i] = temp;
// swap index
int tInd = indexes[indexes[i]];
indexes[indexes[i]] = indexes[i];
indexes[i] = tInd;
}
}
I guess this problem is solved O(n) :-)
#include <iostream>
#include <utility>
void sort(char* a, int* b, int l) {
int startIndex = 0;
int matchCount = 0;
while(matchCount < l) {
if(b[startIndex] == startIndex) {
matchCount++;
startIndex++;
continue;
}
std::swap(a[b[startIndex]], a[startIndex]);
std::swap(b[b[startIndex]], b[startIndex]);
matchCount++;
}
}
int main() {
char a[] = {'C', 'D', 'E','F', 'G'};
int b[] = {3, 0, 4, 1, 2};
int length = sizeof(a)/sizeof(char);
sort(a, b, length);
for(int i=0; i<length; i++) {
std::cout << a[i] << "\t";
}
std::cout << std::endl;
return 0;
}
Solution at O(n) complexity w/o even an additional tmp variable.
- Start at the first position of the index array
- While the element at the current position is not in its proper slot
-- swap the elements in both the index and data arrays, thus putting the current element into its proper slot
-- if the element is in its proper slot, then increment the counter and continue
void sort_data(char A[], int B[], const int& size)
{
int i = 0;
while(i < size)
{
if (B[i] == i)
{
++i;
continue;
}
// swap the elements in both arrays
swap(A, B[i], i);
swap(B, B[i], i);
}
}
Solution at O(n) complexity w/o even an additional tmp variable.
- Start at the first position of the index array
- While the element at the current position is not in its proper slot
-- swap the elements in both the index and data arrays, thus putting the current element into its proper slot
-- if the element is in its proper slot, then increment the counter and continue
void sort_data(char A[], int B[], const int& size)
{
int i = 0;
while(i < size)
{
if (B[i] == i)
{
++i;
continue;
}
// swap the elements in both arrays
swap(A, B[i], i);
swap(B, B[i], i);
}
}
Solution at O(n) complexity w/o even an additional tmp variable.
- Start at the first position of the index array
- While the element at the current position is not in its proper slot
-- swap the elements in both the index and data arrays, thus putting the current element into its proper slot
-- if the element is in its proper slot, then increment the counter and continue
void sort_data(char A[], int B[], const int& size)
{
int i = 0;
while(i < size)
{
if (B[i] == i)
{
++i;
continue;
}
// swap the elements in both arrays
swap(A, B[i], i);
swap(B, B[i], i);
}
}
#include <iostream>
#include <vector>
#include <map>
using namespace std;
void sortArray(vector<char> & A, vector<int> & B) {
map<int, char> BMap;
for(int i = 0; i < B.size(); ++i) {
BMap[B[i]] = A[i];
}
int j = 0;
for(auto w: BMap) {
A[j] = w.second;
++j;
}
}
int main(int argc, const char * argv[]) {
int arrB[] = {3, 0, 4, 1, 2};
char arrA[] = {'C','D', 'E', 'F', 'G'};
vector<int> B(arrB, arrB+5);
vector<char> A(arrA, arrA + 5);
sortArray(A, B);
for(auto iter = A.begin(); iter!=A.end(); ++iter) {
cout << *iter << endl;
}
return 0;
}
#include <iostream>
#include <vector>
#include <map>
using namespace std;
void sortArray(vector<char> & A, vector<int> & B) {
map<int, char> BMap;
for(int i = 0; i < B.size(); ++i) {
BMap[B[i]] = A[i];
}
int j = 0;
for(auto w: BMap) {
A[j] = w.second;
++j;
}
}
int main(int argc, const char * argv[]) {
int arrB[] = {3, 0, 4, 1, 2};
char arrA[] = {'C','D', 'E', 'F', 'G'};
vector<int> B(arrB, arrB+5);
vector<char> A(arrA, arrA + 5);
sortArray(A, B);
for(auto iter = A.begin(); iter!=A.end(); ++iter) {
cout << *iter << endl;
}
return 0;
}
class Solution {
public static <T> void swap(T[] arr, int i, int j){
T temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void reindex(char[] chars, int[] indexes){
}
public static void main(String[] args) {
Character[] chars =
new Character[]{'C', 'D', 'E', 'F', 'G'};
Integer[] indexes = new Integer[]{ 3, 0, 4, 1, 2 };
Character[] target = new Character[]{'D', 'F', 'G', 'C', 'E'};
for(int i = 0; i < chars.length; i++){
while(i != indexes[i]){
swap(chars, i, indexes[i]);
swap(indexes, i, indexes[i]);
}
}
System.out.println( Arrays.toString(chars) );
}
}
Letter/number at each location should be moved to its destination. In the end everything will be in place
def move_to_destination(chars, numbers):
for idx in range(len(numbers)):
if numbers[idx] != idx:
swap(idx, numbers[idx], chars, numbers)
def swap(from_idx, to_idx, chars, numbers):
chars[from_idx], chars[to_idx] = chars[to_idx], chars[from_idx]
numbers[from_idx], numbers[to_idx] = numbers[to_idx], numbers[from_idx]
public static void sortArraybyIdx()
{
char[] A = {'C', 'D', 'E', 'F', 'G'};
int[] B = {3, 0, 4, 1, 2};//DFGCE
int currIdx = 0;
int shldbeIdx = 0;
int k = 0;
while(k < B.length)
{
shldbeIdx = B[shldbeIdx];//3
currIdx = k;//0
//
char temp = A[shldbeIdx];
A[shldbeIdx] = A[currIdx];
A[currIdx] = temp;
//
int tempInt = B[shldbeIdx];
B[shldbeIdx] = B[currIdx];
B[currIdx] = tempInt;
if(B[currIdx] == k)
k++;
}
for(char l : A)
{
System.out.print(l);
}
}
Implemented in Java. Runtime O(n), where n equals number of elements in array. Space O(1).
public class OrderArrayProblem {
public static void main( String[] args ) {
String[] elements = { "C", "D", "E", "F", "G" };
int[] indices = { 3, 0, 4, 1, 2 };
System.out.println( Arrays.asList( elements ) );
sort( elements, indices );
System.out.println( Arrays.asList( elements ) );
}
/**
* @throws NullPointerException if elements or indices are null
*/
public static void sort( String[] elements, int[] indices ) {
if ( elements.length != indices.length ) {
return;
}
for ( int i = 0; i < elements.length; i++ ) {
while ( indices[ i ] != i ) {
swap( elements, indices, i, indices[ i ] );
}
}
}
private static void swap( String[] elements, int[] indices, int fromIndex, int toIndex ) {
String element = elements[ fromIndex ];
int index = indices[ fromIndex ];
elements[ fromIndex ] = elements[ toIndex ];
indices[ fromIndex ] = indices[ toIndex ];
elements[ toIndex ] = element;
indices[ toIndex ] = index;
}
}
groovy
without creating a new array
class ArraySorting {
static void main(String... args) {
String[] elements = ["C", "D", "E", "F", "G"]
int[] indexes = [3, 0, 4, 1, 2]
if (elements.length == indexes.length) {
println(sort(elements, indexes))
}
}
static String[] sort(String[] elements, int[] indexes) {
for (int i = 0; i < indexes.length; i++) {
String tmp = elements[i]
elements[i] = elements[indexes[i]]
elements[indexes[i]] = tmp
int iTemp = indexes[i]
int iTempIndex = indexes.findIndexOf { it == i }
indexes[i] = i
indexes[iTempIndex] = iTemp
}
elements
}
}
runtime O(n).
A=['C', 'D', 'E', 'F', 'G']
B=[3, 0, 4, 1, 2]
dict = {}
for i in range(len(A)):
dict[i] = 0
count = 0
tmpA = A[0]
tmpB = B[0]
for i in range(len(A)):
tmpA2 = A[tmpB]
tmpB2 = B[tmpB]
dict[tmpB] = 1
A[tmpB] = tmpA
B[tmpB] = tmpB
tmpA = tmpA2
tmpB = tmpB2
if dict[tmpB] == 1:
for j in dict:
if dict[j] == 0:
tmpA = A[j]
tmpB = B[j]
print A
print B
var A = ['C', 'D', 'E', 'F', 'G'];
var B = [3, 0, 4, 1, 2];
sort(A, B);
// A is now [D, F, G, C, E];
function sort(){
var i = 0;
for(i=0;i<A.length;i++){
var pos = B[i];
var temp = A[pos];
if(i !== pos){
//Swap A
A[pos] = A[i];
A[i] = temp;
//Swap B
var temp1 = B[i];
B[i] = B[pos];
B[pos] = temp1;
}
}
console.log(A);
}
var b = [3,0,4,1,2];
var a = ['C','D','E','F','G'];
function bSort(b,a){
do {
var trigger = true;
for(var i=0,l=b.length;i<l;i++) {
if ((b[i] > b[i+1])) {
var temp = b[i];
var tempA = a[i];
b[i] = b[i+1];
a[i] = a[i+1];
b[i+1] = temp;
a[i+1] = tempA;
trigger = false;
}
}
} while (!trigger)
return a;
}
bSort(b,a);
var b = [3,0,4,1,2];
var a = ['C','D','E','F','G'];
function bSort(b,a){
do {
var trigger = true;
for(var i=0,l=b.length;i<l;i++) {
if ((b[i] > b[i+1])) {
var temp = b[i];
var tempA = a[i];
b[i] = b[i+1];
a[i] = a[i+1];
b[i+1] = temp;
a[i+1] = tempA;
trigger = false;
}
}
} while (!trigger)
return a;
}
bSort(b,a);
var b = [3,0,4,1,2];
var a = ['C','D','E','F','G'];
function bSort(b,a){
do {
var trigger = true;
for(var i=0,l=b.length;i<l;i++) {
if ((b[i] > b[i+1])) {
var temp = b[i];
var tempA = a[i];
b[i] = b[i+1];
a[i] = a[i+1];
b[i+1] = temp;
a[i+1] = tempA;
trigger = false;
}
}
} while (!trigger)
return a;
}
bSort(b,a);
Javascript solution.
If it's possible to make another array, it's easier. But here I just mutated array A.
var C={C:"C"}, D={D:"D"}, E={E:"E"}, F={F:"F"}, G={G:"G"};
var A = [C,D,E,F,G];
var B = [3,0,4,1,2];
sort(a,b);
// [D, F, G, C, E] 1, 3, 4, 0, 2
function sort1(x, y) {
for(var i=0; i< a.length-1; i++) {
for(var j =i+1; j < b.length; j++) {
if(y[i]>y[j]) {
var tempA = x[i];
x[i] = x[j];
x[j] = tempA;
var tempB = y[i];
y[i] = y[j];
y[j] = tempB;
}
}
}
}
console.log(a);
console.log(b);
public static void Sort(char[] A, int[] B)
{
// handle invalid cases
// A.len != B.len
// B[i] >= A.Length
// Depulicate entries in B
for (int i = 0; i < B.Length; i++)
{
if (i != B[i])
{
// A
var temp = A[i];
A[i] = A[B[i]];
A[B[i]] = temp;
// B
var temp2 = B[i];
B[i] = B[B[i]];
B[temp2] = temp2;
}
}
}
JavaScript solution O(n).
function reorderArray(array, newOrder) {
var i;
var itemToMove;
var itemToMoveIndex;
for (i = 0; i < newOrder.length; i++) {
while(newOrder[i] !== i) {
itemToMove = array[i];
itemToMoveIndex = newOrder[i];
array[i] = array[itemToMoveIndex];
newOrder[i] = newOrder[itemToMoveIndex];
array[itemToMoveIndex] = itemToMove;
newOrder[itemToMoveIndex] = itemToMoveIndex;
}
}
return array;
}
var A = ['C', 'D', 'E', 'F', 'G'];
var B = [3, 0, 4, 1, 2];
var swapShifter = 0;
for (var i = 0; i < B.length; i++) {
while(B[i] !== i){
var key = B[swapShifter];
if(key === i){
var temp = B[i];
var tempChar= A[i];
B[i] = B[swapShifter];
A[i] = A[swapShifter];
B[swapShifter] = temp;
A[swapShifter] = tempChar;
swapShifter=i;
}
else{
swapShifter++;
}
}
}
var A = ['C', 'D', 'E', 'F', 'G'];
var B = [3, 0, 4, 1, 2];
var swapShifter = 0;
for (var i = 0; i < B.length; i++) {
while(B[i] !== i){
var key = B[swapShifter];
if(key === i){
var temp = B[i];
var tempChar= A[i];
B[i] = B[swapShifter];
A[i] = A[swapShifter];
B[swapShifter] = temp;
A[swapShifter] = tempChar;
swapShifter=i;
}
else{
swapShifter++;
}
}
}
var A = ['C', 'D', 'E', 'F', 'G'];
var B = [3, 0, 4, 1, 2];
var swapShifter = 0;
for (var i = 0; i < B.length; i++) {
while(B[i] !== i){
var key = B[swapShifter];
if(key === i){
var temp = B[i];
var tempChar= A[i];
B[i] = B[swapShifter];
A[i] = A[swapShifter];
B[swapShifter] = temp;
A[swapShifter] = tempChar;
swapShifter=i;
}
else{
swapShifter++;
}
}
}
var A = ['C', 'D', 'E', 'F', 'G'];
var B = [3, 0, 4, 1, 2];
var swapShifter = 0;
for (var i = 0; i < B.length; i++) {
while(B[i] !== i){
var key = B[swapShifter];
if(key === i){
var temp = B[i];
var tempChar= A[i];
B[i] = B[swapShifter];
A[i] = A[swapShifter];
B[swapShifter] = temp;
A[swapShifter] = tempChar;
swapShifter=i;
}
else{
swapShifter++;
}
}
}
My answer:
import { expect } from 'chai';
var A = ['C', 'D', 'E', 'F', 'G'];
var B = [3, 0, 4, 1, 2];
// A is now [D, F, G, C, E];
function sort(aa, bb) {
const res = [];
bb.forEach((newIndex, index) => {
res[newIndex] = aa[index];
});
return res;
}
describe.only('leo: ', function() {
it(`array sort`, function() {
expect(sort(A, B)).to.deep.equal(['D', 'F', 'G', 'C', 'E']);
});
});
import { expect } from 'chai';
var A = ['C', 'D', 'E', 'F', 'G'];
var B = [3, 0, 4, 1, 2];
// A is now [D, F, G, C, E];
function sort(aa, bb) {
const res = [];
bb.forEach((newIndex, index) => {
res[newIndex] = aa[index];
});
return res;
}
describe.only('leo: ', function() {
it(`array sort`, function() {
expect(sort(A, B)).to.deep.equal(['D', 'F', 'G', 'C', 'E']);
});
});
Javascript solution, O(n) time, O(1) space
function swap(list, a, b) {
const temp = list[a];
list[a] = list[b];
list[b] = temp;
}
function sortIndexes(list, indexes) {
let start = 0;
while (start < list.length) {
if (indexes[start] !== start) {
swap(list, start, indexes[start]);
swap(indexes, start, indexes[start]);
} else {
start++;
}
}
return list;
}
const list = ['C', 'D', 'E', 'F', 'G'];
const indexes = [ 3, 0, 4, 1, 2 ];
console.log(sortIndexes(list, indexes));
{{ var A = ['C', 'D', 'E', 'F', 'G'];
var B = [3, 0, 4, 1, 2];
var c = [];
var tempVal;
var tempInd;
var i;
for(i = 0; i < A.length; i++) {
console.log(i);
tempVal = A[B[i]]; //set temp to index from B in A
tempInd = B[B[i]]
A[B[i]] = A[i]; //Swap the two values
B[B[i]] = B[i];
B[i] = tempInd;
A[i] = tempVal;
}
}}
First Brute-force solution using JS
function sortByIndex(list, indexes) {
if (list.length !== indexes.length ){
throw new Error("the list length must match the indexes length");
}
for (let i=0;i<list.length;i++){
const index= indexes[i];
const tmp = list[index];
list[index] = list[i];
list[i] = tmp;
const tmp2 = indexes[i];
indexes[i] = indexes[index];
indexes[index] = tmp2;
}
return list;
}
c++, implementation
struct Object {
char value;
Object(char v) {
value = v;
}
};
void solve(vector<Object>& A, vector<int> B) {
int from, to, i;
Object temp(' ');
if (A.size() != B.size()) return;
for (from = 0; from < A.size(); from++) {
to = B[from];
if (from == to) continue;
temp = A[from];
A[from] = A[to];
A[to] = temp;
i = from + 1;
while (i < A.size()) {
if (B[i] == from) {
B[i] = to;
break;
}
i++;
}
}
}
You can do it in O(n) time and O(n) space. For each index, swap the current index in A with the index specified in B. If the current index has been swapped to before, skip. The indices that were swapped to can be kept in a hash table for O(1) look up. Here's a c++ code for it.
include <stdlib.h>
#include <stdio.h>
#include <vector>
#include <set>
void sort(std::vector<char>& a, std::vector<int>& b){
std::set<int> swapped; //using a set, but ideally, a hash table for O(1) lookup
if(a.size() == b.size()){
for(unsigned int i = 0; i < a.size(); i++){
if(swapped.find(i) == swapped.end()){
char temp = a[b[i]];
a[b[i]] = a[i];
a[i] = temp;
swapped.insert(b[i]);
}
}
}
}
int main(){
std::vector<char> a;
a.push_back('C');
a.push_back('D');
a.push_back('E');
a.push_back('F');
a.push_back('G');
std::vector<int> b;
b.push_back(3);
b.push_back(0);
b.push_back(4);
b.push_back(1);
b.push_back(2);
sort(a, b);
for(unsigned int i = 0; i < a.size(); i++)
printf("%c, ", a[i]);
printf("\n");
return 0;
}
I do not make new array and do not change array size.
javascript, implementation, O(n) without indexOf
function sort(A, B) {
var temp, from, to, idx;
if (!(A instanceof Array) || !(B instanceof Array)) return;
if (A.length != B.length) return;
for (from = 0; from < A.length; from++) {
to = B[from];
if (from == to) continue;
temp = A[from];
A[from] = A[to];
A[to] = temp;
idx = B.indexOf(from);
if (idx > from) {
B[idx] = to;
}
}
}
how this algo is O(n) ???
here you are using "idx = B.indexOf(from);", this is library function it takes O(n).
so complexity of this code is O(n^2)
O(n) solution
public void reorder(char [] A, int [] B){ for (int i = 0 ; i < B.length ; ++i) { int tmp = i ; while (B[tmp] != tmp) { swap(A, B[tmp], tmp); swapIndex (B, B[tmp], tmp) ; tmp = B[tmp] ; } } } private void swap (char [] A, int i , int j){ char tmp = A[i] ; A[i] = A[j] ; A[j] = tmp ; } private void swapIndex (int [] A, int i , int j){ int tmp = A[i] ; A[i] = A[j] ; A[j] = tmp ;}
- Scott October 26, 2015