Facebook Interview Question SDE-2s
Country: United States
Interview Type: In-Person
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;
}
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
cache.add(str + pair.toString());
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;
}
}
#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;
}
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('')
}
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('')
}
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]]))
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;
list.add(indexes);
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];
result.add(swap(firstIndex,SecondIndex, ch));
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);
}
}
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?
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;
}
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;
tmpPermutations.add(tempStr);
//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;
permutations.addAll(tmpPermutations);
}
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
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<>();
pairs.add(new int[]{1,4});
pairs.add(new int[]{3,4});
pairs.add(new int[]{2,2});
pairs.add(new int[]{9,10});
pairs.add(new int[]{10,11});
pairs.add(new int[]{11,12});
pairs.add(new int[]{2,6});
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);
list.add(set);
} else if (set2 != null) {
// merge the sets
// remove second set
set1.or(set2);
list.remove(set2);
}
}
return list;
}
}
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<>();
pairs.add(new int[]{1,4});
pairs.add(new int[]{3,4});
pairs.add(new int[]{2,2});
pairs.add(new int[]{9,10});
pairs.add(new int[]{10,11});
pairs.add(new int[]{11,12});
pairs.add(new int[]{2,6});
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);
list.add(set);
} else if (set2 != null) {
// merge the sets
// remove second set
set1.or(set2);
list.remove(set2);
}
}
return list;
}
}
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;
}
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) });
System.out.println("answer: "+answer);
answer = findLargestLString("abdez", new Pair[] { new Pair(1,4), new Pair(3,4), new Pair(5,3) });
System.out.println("answer: "+answer);
}
}
class DisjointSet {
private final int[] parents;
DisjointSet(int size) {
this.parents = new int[size];
// Initially, there are `size` separate items having themselves as parents.
for (int i = 0; i < size; i++) {
this.parents[i] = i;
}
}
void connect(int a, int b) {
parents[getParent(b)] = getParent(a);
}
int getParent(int a) {
int parent = parents[a];
if (parent != a) {
parent = getParent(parent);
parents[a] = parent;
}
return parent;
}
}
static String next(String s, List<int[]> swaps) {
final int N = s.length();
// 1a. Extract separate graphs.
DisjointSet set = new DisjointSet(N);
for (int[] swap : swaps) {
set.connect(swap[0], swap[1]);
}
// 1b. Map the string’s characters to the appropriate vertices.
Map<Integer, List<Character>> graphs = new HashMap<>();
for (int i = 0; i < N; i++) {
int head = set.getParent(i);
List<Character> characters = graphs.computeIfAbsent(head, (dummy) -> new ArrayList<>());
characters.add(s.charAt(i));
}
// 2. Within each graph, sort the characters in **ascending** order.
for (List<Character> characters : graphs.values()) {
characters.sort(null);
}
// 3. Populate the output by taking the characters from the graph.
StringBuilder sb = new StringBuilder(N);
for (int i = 0; i < N; i++) {
// Since the lists are sorted in ascending order, take the last element.
// This is similar to pop_back() function of std::vector.
List<Character> characters = graphs.get(set.getParent(i));
char currentMax = characters.remove(characters.size() - 1);
sb.append(currentMax);
}
return sb.toString();
}
static String next(String s, List<int[]> swaps) {
final int N = s.length();
// 1a. Extract separate graphs.
DisjointSet set = new DisjointSet(N);
for (int[] swap : swaps) {
set.connect(swap[0], swap[1]);
}
Function<Integer, Queue<Character>> newDescendingQueue = (dummy) -> new PriorityQueue<>(
Comparator.reverseOrder());
// 1b. Map the string’s characters to the appropriate vertices.
Map<Integer, Queue<Character>> graphs = new HashMap<>();
for (int i = 0; i < N; i++) {
int head = set.getParent(i);
graphs.computeIfAbsent(head, newDescendingQueue).offer(s.charAt(i));
}
// 2. PriorityQueue guarantees the descending order when polling elements.
// 3. Populate the output by taking the characters from the graph.
StringBuilder sb = new StringBuilder(N);
for (int i = 0; i < N; i++) {
sb.append(graphs.get(set.getParent(i)).poll());
}
return sb.toString();
}
Consider indices as vertices.
- krbchd March 15, 2016Connect 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)