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)

- krbchd March 15, 2016 | Flag Reply
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;
}

- kyduke March 15, 2016 | Flag Reply
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
        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;
        }
    }

- Coder April 10, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

d

- x March 15, 2016 | Flag Reply
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;
}

- ms March 15, 2016 | Flag Reply
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('')
}

- Javascripter March 15, 2016 | Flag Reply
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('')

}

- Javascripter March 15, 2016 | Flag Reply
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]]))

- Anonymous March 15, 2016 | Flag Reply
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;
				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);
	}
}

- shashi Singh March 17, 2016 | Flag Reply
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.

- kamrultopu March 24, 2016 | Flag Reply
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?

- Sean Locke April 08, 2016 | Flag Reply
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;
}

- GOKU April 26, 2016 | Flag Reply
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;
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

- jcgarciarojas May 05, 2016 | Flag Reply
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<>();
    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;
  }
}

- 0Kelvin June 22, 2016 | Flag Reply
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<>();
    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;
  }
}

- 0Kelvin June 22, 2016 | Flag Reply
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;
}

- Anonymous September 28, 2016 | Flag Reply
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) });
		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);
	}
}

- Anonymous January 14, 2017 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More