## Facebook Interview Question for SDE-2s

Country: United States
Interview Type: In-Person

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

Consider indices as vertices.
Connect two vertices with an edge if swapping is allowed between them

Now for each connected component in graph sort the characters represented by the indices(vertex) and place them from highest value to lowest value in those indices.

Result would be a lexicographically largest string.

Example :-

"acxrabdz"
Swaps allowed(0 based index) :-
(0,2)(5,7)(2,7),(1,6)

There are two connected components
(0,2,5,7) and (1,6)
Sort (0,2,5,7) values that is a,x,b,z you get zxba place them in respective indices (z->0,x->2,b->5,a->7)
Similarly sort (1,6) -> c,d - > d,c

final output :- "zcxrabca" lexicographically sorted string

finding each connected components(using dfs) - O(n + no of swapping entries given)
Sorting )(nlgn)

overal complexity - O(nlgn + noOfSwappingEntries)
if no of swapping entires are ~ n then it becomes O(n)

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

C++, implementaion, O(n log n)

``````string swapLexOrder(string str, vector<pair<int, int>> pairs) {
string result;
queue<pair<int, int>> q;
set<int> s;
set<int>::iterator it;
vector<char> c;
int i, l, a, b;

result = str;

for (i = 0; i < pairs.size(); i++) {
q.push(pairs[i]);
}

while (!q.empty()) {
l = q.size();
s.clear();
while (l--) {
a = q.front().first;
b = q.front().second;
q.pop();
if (s.size() == 0 || s.find(a) != s.end() || s.find(b) != s.end()) {
s.insert(a);
s.insert(b);
l = q.size();
continue;
}

q.push(make_pair(a, b));
}

c.clear();
for (it = s.begin(); it != s.end(); it++) {
c.push_back(result[*it - 1]);
}
sort(c.begin(), c.end(), greater<char>());
i = 0;
for (it = s.begin(); it != s.end(); it++) {
result[*it - 1] = c[i];
i++;
}
}

return result;
}``````

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

In principal, every pair has the option to be part of the pair swap operation tree or not. We build an operation tree with and without a pair, then return the largest lexicographical string result. We continue doing so until we come across a combination of (pair+string) in the cache.

This is a brute force solution, but possibly acceptable for a 45 minute interview session.

``````private static String getLargestLexicographicalString(String str, ArrayList<Pair> pairs) {
return getLargestLexicographicalString(str, pairs, 0, new HashSet<>());
}

private static String getLargestLexicographicalString(String str, ArrayList<Pair> pairs, int index, HashSet<String> cache) {

// reset if index reaches pairs list size as we will
// keep trying until we get the highest lexicographical
// possible string (pair swapping can be reused).
if (index == pairs.size())
index = 0;

Pair pair = pairs.get(index);

// return if (string + pair) has been processed before
if (cache.contains(str + pair.toString()))
return str;

String swappedString = swap(str, pair);

// mark (string + pair) as visited

String withSwap = getLargestLexicographicalString(swappedString, pairs, index + 1, cache);

String withOutSwap = getLargestLexicographicalString(str, pairs, index + 1, cache);

return withSwap.compareTo(withOutSwap) > 0 ? withSwap : withOutSwap;
}

private static String swap(String s, Pair pair) {
char[] str = s.toCharArray();
char temp = str[pair.x];
str[pair.x] = str[pair.y];
str[pair.y] = temp;
return new String(str);
}

static class Pair {
int x, y;

public Pair(int x, int y) {
this.x = x;
this.y = y;
}

@Override
public String toString() {
return "x=" + x + ", y=" + y;
}
}``````

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

d

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

``````#include<iostream>
#include<string>
#include<vector>
using namespace std;

void my_swap(string &str, int a, int b)
{
--a;
--b;
char temp = str[a];
str[a] = str[b];
str[b] = temp;
}
void lex_larger(string &str, vector<pair<int, int>> p)
{
char max = str[0];
for (int i = 1; i < str.size(); i++)
{
if (max < str[i])
max = str[i];
}

vector<pair<int, int>>::iterator it;
while (str[0] != max)
{
for (it = p.begin(); it != p.end(); it++)
my_swap(str, it->first, it->second);
}

}

int main()
{
string s ="abdc";
vector<pair<int, int>> v;
v.push_back(make_pair( 1, 4));
v.push_back(make_pair(3, 4));
lex_larger(s, v);
return 0;
}``````

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

Javascript, O(nlogn)

``````function biggestPermutation(string, indices) {
var permutations = [string]
var indexToGenerateFrom = 0
while (indexToGenerateFrom <= permutations.length - 1) {
for (var i = 0; i < indices.length; i++) {
var permutation = applyPermutation(permutations[indexToGenerateFrom],indices[i])
if (permutations.indexOf(permutation) === -1) {
permutations.push(permutation)
}
}
indexToGenerateFrom++
}
return permutations.sort().pop()
}

function applyPermutation(string, indices) {
var array = string.split('')
var temp = array[indices[0]-1]
array[indices[0]-1] = array[indices[1]-1]
array[indices[1]-1] = temp
return array.join('')
}``````

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

Javascript, O(nlogn)

``````function biggestPermutation(string, indices) {
var permutations = [string]
var indexToGenerateFrom = 0
while (indexToGenerateFrom <= permutations.length - 1) {
for (var i = 0; i < indices.length; i++) {
var permutation = applyPermutation(permutations[indexToGenerateFrom],indices[i])
if (permutations.indexOf(permutation) === -1) {
permutations.push(permutation)
}
}
indexToGenerateFrom++
}
return permutations.sort().pop()
}

function applyPermutation(string, indices) {
var array = string.split('')
var temp = array[indices[0]-1]
array[indices[0]-1] = array[indices[1]-1]
array[indices[1]-1] = temp
return array.join('')``````

}

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

``````function biggestPermutation(string, indices) {
var permutations = [string]
var indexToGenerateFrom = 0
while (indexToGenerateFrom <= permutations.length - 1) {
for (var i = 0; i < indices.length; i++) {
var permutation = applyPermutation(permutations[indexToGenerateFrom],indices[i])
if (permutations.indexOf(permutation) === -1) {
permutations.push(permutation)
}
}
indexToGenerateFrom++
}
return permutations.sort().pop()
}

function applyPermutation(string, indices) {
var array = string.split('')
var temp = array[indices[0]-1]
array[indices[0]-1] = array[indices[1]-1]
array[indices[1]-1] = temp
return array.join('')
}
console.log(biggestPermutation("abcde", [[1,4], [3,4]]))``````

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

``````Java:-
package strings.examples;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;

public class LexicographicalString {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);
System.out.println("Enter a String :- ");
String word = sc.nextLine();
char[] ch= word.toCharArray();
System.out.println("Enter how many indexes you want to create :- ");
int[] indexes;
List<int[]> list = new ArrayList<int[]>();
int length =sc.nextInt();
for(int k=0 ; k<length;){
indexes=new int[2];
System.out.println("Enter"+ k +" value of i :- ");
Integer i=sc.nextInt();
System.out.println("Enter"+ k +" value of j :- ");
Integer j=sc.nextInt();
if(i!=j && 1<j){
indexes[0]=i;
indexes[1]=j;
k++;
}else{
System.out.println("The value of i and j could not be same and i could not be greater than j, Please enter different values.");
}
}

Set<String> result = new TreeSet<String>();
int previousUsedIndex = -1;
int currentUsedIndex=-1;
for (int i = 0; (i < factorial(word.length()) || i<length); i++) {
Random r = new Random();
currentUsedIndex=	r.nextInt(((list.size()-1) -0) + 1) + 0;
if((previousUsedIndex != currentUsedIndex) && (currentUsedIndex>=0 || currentUsedIndex<2)){
System.out.println("currentindex:- "+currentUsedIndex +" , previousIndex :-" +previousUsedIndex);
int firstIndex =list.get(currentUsedIndex)[0];
int SecondIndex =list.get(currentUsedIndex)[1];
previousUsedIndex = currentUsedIndex;
currentUsedIndex=-1;
}

}

List<String> resultedList = new ArrayList<String>(result);

System.out.println("Greatest String :- "+resultedList.get(resultedList.size()-1));

}

public static String swap(int i,int j, char[] ch){
char temp = ch[i-1];
ch[i-1]=ch[j-1];
ch[j-1]=temp;
return String.valueOf(ch);
}

public static int factorial(int n){
if(n<=0)
return 1;
else
return n*factorial(n-1);
}
}``````

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

can you check your answer for this example? I got zdxrabca as a final output , if we swap (2,7) , (0,2) and (1,6) we got d in the position 1. so zd in the first two position seem lexicographical bigger.

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

It looks to me that it would be solvable using graph, because swapping indices represent the connection between nodes. But, no clue how to use this graph ...

The best solution I think is: recursively apply N rules to generate new strings and it will be a tree from the original string. The branch will be cut if the string appears before. So,

1. a hashMap to track all strings have been generated
2. the lexic largest string so far
3. a queue to track all candidate strings (leaves of the tree)

Alg:
1. recursive apply N rules to all strings in the queue until the queue is empty
2. if a new string generated by applying a rule, push it into the queue; otherwise discard

It seems not efficient ... any better idea?

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

O(nlogn) using disjoint sets and merges sort

``````#include<bits/stdc++.h>
using namespace std;

#define MAX 10005

int parent[MAX],rank[MAX];
vector<char> graph[MAX];

int findParent(int idx)
{
if(parent[idx]==idx)
return idx;
return parent[idx] = findParent(parent[idx]);
}

void Union(int a,int b)
{
int id1 = findParent(a);
int id2 = findParent(b);

if(id1==id2)
return;

if(rank[id1]>rank[id2])
parent[id2] = id1;
else
parent[id1] = id2;

if(rank[id1]==rank[id2])
rank[id2]++;
}
string s;

int main()
{

cin>>s;

for(int i = 0;i<s.size();i++)
{
parent[i] = i;
rank[i]  =0;
}

int m,x,y;
cin>>m;

while(m--)
{
//one based indexing
cin>>x>>y;

x--;
y--;
Union(x,y);
}

for(int i = 0;i<s.size();i++)
graph[findParent(i)].push_back(s[i]);

for(int i = 0;i<s.size();i++)
sort(graph[i].begin(),graph[i].end());

for(int i = 0;i<s.size();i++)
{
int idx = findParent(i);
s[i] = graph[idx].back();
graph[idx].pop_back();
}

cout<<s<<endl;

return 0;
}``````

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

public String swap(Pair index, String str) {
char [] charArray = str.toCharArray();
char temp = charArray[index.y];
charArray[index.y] = charArray[index.x];
charArray[index.x] = temp;
return String.valueOf(charArray);
}

public String permutations(List<Pair> indexes, String initialStr) {
System.out.println("initialStr "+initialStr);
int numberPermuations = indexes.size();
String resultStr = initialStr;
HashSet<String> permutations = new HashSet<String>();

String tempStr = initialStr;
while (true) {
List<String> tmpPermutations = new ArrayList<String>();
for (Pair p: indexes) {
tempStr = swap(p, tempStr);
if (initialStr.equals(tempStr) || permutations.contains(tempStr))
break;

//get greater lexicographic element
if (tempStr.compareTo(resultStr) > 0)
resultStr = tempStr;
}
//if expected number of permutations not perform then exit;
if (tmpPermutations.size() < numberPermuations)
break;
}
System.out.println(permutations);
System.out.println("resultStr "+resultStr);
return resultStr;
}

output
=====
initialStr abdc

[cbda, dbca, cbad, dbac] ==> this doesn't come in order of addition due to it is a HashSet. But HashSet is based on HashMap so it is better to use it than a list.

resultStr dbca

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

Pair-swaps can be combined together (a set) if they share an index. By induction you can prove that any index can be swapped to another other index in the shared set. Sort each set of indices.

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

/*
* To execute Java, please define "static void main" on a class
* named Solution.
*
* If you need more classes, simply define them inline.
*/

class Solution {
public static void main(String[] args) {

List<int[]> pairs = new ArrayList<>();

String str = "abcdefuwqeuidscnbsdf";

Collection<BitSet> list = generateSets(pairs);
String result = rearrangeString(list, str);

System.out.println("result:"+result);

}

static String rearrangeString(Collection<BitSet> list, String str) {

char[] result = str.toCharArray();
for (BitSet set : list) {

char[] chars = new char[set.cardinality()];
int i = -1;
int j = 0;
while ((i = set.nextSetBit(i+1)) >= 0) {
chars[j] = str.charAt(i-1);
j++;
}
Arrays.sort(chars);
i = -1;
j = 1;

while ((i = set.nextSetBit(i+1)) >= 0) {
result[i-1] = chars[chars.length-j]; //
j++;
}

}
return new String(result);
}

static Collection<BitSet> generateSets(List<int[]> pairs) {

Set<BitSet> list = new HashSet<>();

for (int[] pair : pairs) {
BitSet set1 = null;
BitSet set2 = null;
for (BitSet set : list) {
if (set.get(pair[0]) || set.get(pair[1])) {
if (set1 == null) {
set1 = set;
} else {
set2 = set;
}
set.set(pair[0], true);
set.set(pair[1], true);

}
}

if (set1 == null) {
// there was no matching set
// create a new one
BitSet set = new BitSet();
set.set(pair[0],true);
set.set(pair[1],true);

} else if (set2 != null) {
// merge the sets
// remove second set
set1.or(set2);
list.remove(set2);
}
}

return list;
}
}``````

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

By induction, multiple pairs of indices can be combined into a set of indices if they form a graph.Sort the indices in each set.

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

/*
* To execute Java, please define "static void main" on a class
* named Solution.
*
* If you need more classes, simply define them inline.
*/

class Solution {
public static void main(String[] args) {

List<int[]> pairs = new ArrayList<>();

String str = "abcdefuwqeuidscnbsdf";

Collection<BitSet> list = generateSets(pairs);
String result = rearrangeString(list, str);

System.out.println("result:"+result);

}

static String rearrangeString(Collection<BitSet> list, String str) {

char[] result = str.toCharArray();
for (BitSet set : list) {

char[] chars = new char[set.cardinality()];
int i = -1;
int j = 0;
while ((i = set.nextSetBit(i+1)) >= 0) {
chars[j] = str.charAt(i-1);
j++;
}
Arrays.sort(chars);
i = -1;
j = 1;

while ((i = set.nextSetBit(i+1)) >= 0) {
result[i-1] = chars[chars.length-j]; //
j++;
}

}
return new String(result);
}

static Collection<BitSet> generateSets(List<int[]> pairs) {

Set<BitSet> list = new HashSet<>();

for (int[] pair : pairs) {
BitSet set1 = null;
BitSet set2 = null;
for (BitSet set : list) {
if (set.get(pair[0]) || set.get(pair[1])) {
if (set1 == null) {
set1 = set;
} else {
set2 = set;
}
set.set(pair[0], true);
set.set(pair[1], true);

}
}

if (set1 == null) {
// there was no matching set
// create a new one
BitSet set = new BitSet();
set.set(pair[0],true);
set.set(pair[1],true);

} else if (set2 != null) {
// merge the sets
// remove second set
set1.or(set2);
list.remove(set2);
}
}

return list;
}
}``````

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

``````int group(int c, unordered_map<int, int> & disjoint_set) {
int parent = disjoint_set[c];
if (c == parent) {
return c;
}
disjoint_set[c] = group(parent, disjoint_set);
return disjoint_set[c];
}

string largest_swap(string input, vector<pair<int, int>> const & pairs) {
unordered_map<int, int> disjoint_set;
unordered_map<int, vector<char>> char_group;
for (auto const & swap_pair : pairs) {
int a = swap_pair.first - 1;
int b = swap_pair.second - 1;
char x = input[a];
char y = input[b];
if (disjoint_set.find(a) == disjoint_set.end()) {
if (disjoint_set.find(b) == disjoint_set.end()) {
disjoint_set[a] = a;
disjoint_set[b] = a;
char_group[a].push_back(x);
char_group[a].push_back(y);
} else {
disjoint_set[a] = group(b, disjoint_set);
char_group[disjoint_set[a]].push_back(x);
}
} else {
if (disjoint_set.find(b) == disjoint_set.end()) {
disjoint_set[b] = group(a, disjoint_set);
char_group[disjoint_set[b]].push_back(y);
} else {
disjoint_set[group(b, disjoint_set)] = group(a, disjoint_set);
auto & group_x = char_group[disjoint_set[a]];
auto & group_y = char_group[disjoint_set[b]];
group_x.insert(group_x.end(), group_y.begin(), group_y.end());
}
}
}

for (auto & group_by_char : char_group) {
sort(group_by_char.second.begin(), group_by_char.second.end());
}

for (int i = 0; i < input.length(); ++i) {
if (disjoint_set.find(i) == disjoint_set.end()) {
continue;
}
int group_i = group(i, disjoint_set);
auto & char_set = char_group[group_i];
input[i] = char_set.back();
char_set.pop_back();
}
return input;
}``````

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

What about a stupid algorithm ? 10 mins algorithm for fun and pleasure!
Brute brute force baby!

``````public class LexicographicalLargestString {
static class Pair {
int idx1;
int idx2;
public Pair(int idx1, int idx2) {
this.idx1 = idx1-1;
this.idx2 = idx2-1;
}
public String toString() {
return "("+idx1+","+idx2+")";
}
}

static HashMap<String, Boolean> map = new HashMap<String,Boolean>();

static String swap(char a[], Pair pair) {
if(pair.idx1 < 0 || pair.idx2 < 0 || pair.idx1 >= a.length || pair.idx2 >= a.length)
throw new IllegalArgumentException("pair");
char tmp = a[pair.idx1];
a[pair.idx1] = a[pair.idx2];
a[pair.idx2] = tmp;
return new String(a);
}

static String findLargestLString(String s, Pair pairs[]) {
char a[] = s.toCharArray();
while(true) {
int counter = 0;
for(Pair p: pairs) {
String swapped = swap(a, p);
if(map.containsKey(swapped))
continue;
map.put(new String(a), true);
counter++;
}
if(counter == 0)
break;
}
// System.out.println("possibilities: "+map.keySet());
List<String> list = Arrays.asList(map.keySet().toArray(new String[0]));
map.clear();
Collections.sort(list);
return list.get(list.size()-1);
}

public static void main(String args[]) {
String answer = findLargestLString("abdc", new Pair[] { new Pair(1,4), new Pair(3,4) });

answer = findLargestLString("abdez", new Pair[] { new Pair(1,4), new Pair(3,4), new Pair(5,3) });
}
}``````

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.