Facebook Interview Question SDE1s
Country: United States
// ZoomBA.
// Basic trick, iterate over permutations, and collect elements
s = 'abcdc'
len = size(s)
sa = s.toCharArray
sorta(sa) // the base template
// iterate and select over all permutation indices
// specify the collector - classic example of from syntax
deranged = from ( perm( [0:len].asList ) , set() ) :: {
// when no element exists such that there is same char in place
!exists( $.o ) :: { sa[ $.o ] == s[ $.i ] }
// finally map permutation index back to the string
} -> { str( $.o ,'' ) -> { sa[ $.o ] } }
println( deranged )
unordered_map<char, int> M;
void
GetDearrangments(const std::string &str, int start, std::string &Temp, vector<string> &Result)
{
if (start == str.size())
{
if (Temp.empty() == false)
{
Result.push_back(Temp);
}
return;
}
char Curr = str[start];
for (int i = 0; i < str.size(); ++i)
{
if (i != M[Curr] && Temp[i] == '0')
{
Temp[i] = Curr;
GetDearrangments(str, start + 1, Temp, Result);
Temp[i] = '0';
}
}
}
vector<string>
GetDearrangments(const std::string &str)
{
vector<string> Result;
if (str.empty())
{
return Result;
}
string Temp(str.size(), '0');
for (int i = 0; i < str.size(); ++i)
{
M[str[i]] = i;
}
GetDearrangments(str, 0, Temp, Result);
return (Result);
}
A recursive solution can be pretty straight forward for this. Basically use the normal recursive way to compute all the permutations of a string but skip the ones where the char would be at its original position.
def derangements_rec chars, remaining, permutation = ""
return permutation if remaining.empty?
remaining
.each_with_index
.reject { |char, _| chars[permutation.size] == char } # don't allow char at the original position
.flat_map { |char, index| derangements_rec(chars,
# remaining without the currently processed one
remaining.dup.tap { |r| r.delete_at(index) },
permutation + char) }
end
def derangements input
chars = input.chars
derangements_rec chars, chars
end
You can store in set the result to avoid duplicate values:
public static void permutation(String str) {
Map<Character, List<Integer>> map = new HashMap<>();
int i = 0;
for (Character ch : str.toCharArray()) {
if (map.containsKey(ch))
(map.get(ch)).add(++i);
else {
List<Integer> list = new ArrayList<>();
list.add(++i);
map.put(ch, list);
}
}
permutation("", str, map);
}
private static void permutation(String prefix, String str, Map<Character, List<Integer>> map) {
int n = str.length();
if (n == 0) {
if (check(prefix, map))
System.out.println(prefix);
} else {
for (int i = 0; i < n; i++) {
permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1, n), map);
}
}
}
private static boolean check(String prefix, Map<Character, List<Integer>> map) {
int i = 1;
for (Character ch : prefix.toCharArray()) {
if (map.get(ch).contains(i++))
return false;
}
return true;
}
object Solution {
def readInput(): String = {
val sc = new java.util.Scanner(System.in)
sc.next
}
def getDerangements(str: String): List[String] = {
def getIndex(str: String): Set[(Char, Int)] = {
str.zipWithIndex.toSet
}
def permutate(ch: Char, str: String): List[String] = {
(for (i <- 0 to str.length) yield {
val (first, second) = str.splitAt(i)
first + ch + second
}).toList
}
def permutations(s: String): List[String] = {
if (s.isEmpty) Nil
else {
val ch = s.head
val rest = s.tail
permutations(rest) match {
case Nil => List(ch.toString)
case d: List[String] => d.flatMap(permutate(ch, _))
}
}
}
def isDerangement(s: String, index: Set[(Char, Int)]): Boolean = {
val ind = getIndex(s)
!(ind & index).isEmpty
}
val index = getIndex(str)
permutations(str).filter(!isDerangement(_, index)).toSet.toList
}
def main(args: Array[String]) {
val str = readInput()
getDerangements(str).foreach(println(_))
}
}
import java.util.ArrayList;
import java.util.List;
public class Main
{
public static List<String> get_dearrangements(String str, String original, int depth)
{
if(str.length() == 1)
{
List<String> list = new ArrayList<String>();
list.add(str);
return list;
}
List<String> all_dearrangements = new ArrayList<String>();
for(int i=0; i<str.length(); i++)
if(str.charAt(i) != original.charAt(depth))
{
char c = str.charAt(i);
List<String> dearrangements = get_dearrangements(remove_char_at(str, i), original, depth+1);
for(String s : dearrangements)
all_dearrangements.add(c + s);
}
return all_dearrangements;
}
public static String remove_char_at(String str, int index)
{
StringBuilder sb = new StringBuilder(str);
sb.deleteCharAt(index);
return sb.toString();
}
public static void main(String args[])
{
System.out.println(get_dearrangements("ABCDE", "ABCDE", 0));
}
}
Result:
[BADCE, BADEC, BAECD, BCAED, BCDAE, BCDEA, BCEAD, BDACE, BDAEC, BDEAC, BDECA, BEACD, BEDAC, BEDCA, CABED, CADBE, CADEB, CAEBD, CDABE, CDAEB, CDBAE, CDBEA, CDEAB, CDEBA, CEABD, CEBAD, CEDAB, CEDBA, DABCE, DABEC, DAEBC, DAECB, DCABE, DCAEB, DCBAE, DCBEA, DCEAB, DCEBA, DEABC, DEACB, DEBAC, DEBCA, EABCD, EADBC, EADCB, ECABD, ECBAD, ECDAB, ECDBA, EDABC, EDACB, EDBAC, EDBCA]
import java.util.ArrayList;
import java.util.List;
public class Main
{
public static List<String> get_dearrangements(String str, String original, int depth)
{
if(str.length() == 1)
{
List<String> list = new ArrayList<String>();
list.add(str);
return list;
}
List<String> all_dearrangements = new ArrayList<String>();
for(int i=0; i<str.length(); i++)
if(str.charAt(i) != original.charAt(depth))
{
char c = str.charAt(i);
List<String> dearrangements = get_dearrangements(remove_char_at(str, i), original, depth+1);
for(String s : dearrangements)
all_dearrangements.add(c + s);
}
return all_dearrangements;
}
public static String remove_char_at(String str, int index)
{
StringBuilder sb = new StringBuilder(str);
sb.deleteCharAt(index);
return sb.toString();
}
public static void main(String args[])
{
System.out.println(get_dearrangements("ABCDE", "ABCDE", 0));
}
}
output:
[BADCE, BADEC, BAECD, BCAED, BCDAE, BCDEA, BCEAD, BDACE, BDAEC, BDEAC, BDECA, BEACD, BEDAC, BEDCA, CABED, CADBE, CADEB, CAEBD, CDABE, CDAEB, CDBAE, CDBEA, CDEAB, CDEBA, CEABD, CEBAD, CEDAB, CEDBA, DABCE, DABEC, DAEBC, DAECB, DCABE, DCAEB, DCBAE, DCBEA, DCEAB, DCEBA, DEABC, DEACB, DEBAC, DEBCA, EABCD, EADBC, EADCB, ECABD, ECBAD, ECDAB, ECDBA, EDABC, EDACB, EDBAC, EDBCA]
My idea is to generate permutations (with duplicated characters allowed), but while the process to check if the particular character is forbidden to take the particular place or not.
vector<string> Dearrangements(string s,
set<pair<char, int>> const &forbidden_positions, int pos = 0)
{
vector<string> dearrangements;
if (s.empty()) {
if (pos != 0) {
dearrangements.push_back("");
}
return dearrangements;
}
for (int i = 0; i < s.size(); ++i) {
if (i > 0 &&
s[i - 1] == s[i])
{
continue;
}
if (forbidden_positions.find(pair<char, int>(s[i], pos)) !=
forbidden_positions.end())
{
continue;
}
string remainder = s;
remainder.erase(remainder.begin() + i);
vector<string> sub_dearrs = Dearrangements(remainder, forbidden_positions, pos + 1);
for (auto const &sub_dearr : sub_dearrs) {
dearrangements.push_back(s[i] + sub_dearr);
}
}
return dearrangements;
}
vector<string> Dearrangements(string s)
{
set<pair<char, int>> forbidden_positions;
for (int i = 0; i < s.size(); ++i) {
forbidden_positions.insert(pair<char, int>(s[i], i));
}
sort(s.begin(), s.end());
return Dearrangements(s, forbidden_positions);
}
Saloni has two sets A and B, both of having N distinct elements. Sets A and B have exactly N - K same elements (K <= N). Therefore, exactly K elements differ in sets A and B. Now you insert both the sets into two lists C and D.
Now Saloni loves the scenario when C[i] != D[i] for any value of i from 1 to N.
You are allowed to permute both the arrays C and D. Find the number of ways in which Saloni loves the permutation of the two arrays. (The total number of ways to permute both arrays = N! * N! )
As the answer can be huge, find it modulo 109 + 7.
Input
The first line of input contains an integer Q, denoting the number of queries.
The next Q lines contain two integers N and K.
Constraints
1 <= Q <= 100000
1 <= N <= 10000
0 <= K <= N
Saloni has two sets A and B, both of having N distinct elements. Sets A and B have exactly N - K same elements (K <= N). Therefore, exactly K elements differ in sets A and B. Now you insert both the sets into two lists C and D.
Now Saloni loves the scenario when C[i] != D[i] for any value of i from 1 to N.
You are allowed to permute both the arrays C and D. Find the number of ways in which Saloni loves the permutation of the two arrays. (The total number of ways to permute both arrays = N! * N! )
As the answer can be huge, find it modulo 109 + 7.
Input
The first line of input contains an integer Q, denoting the number of queries.
The next Q lines contain two integers N and K.
Constraints
1 <= Q <= 100000
1 <= N <= 10000
0 <= K <= N
Not compiled, not done any allocations, but this logic should work.
int derangement(int start, int end, int *arr)
{
int count = 0;
if (start == end) {
putchar(arr[start] + 'a');
return 1;
}
for (int i=start; i < end; i++) {
if (i==arr[start]) {
continue;
}
swap(arr[start], arr[i]);
count += derangement(start+1, end, arr);
}
return count;
}
int main()
{
int count = 0;
// For current example(ABCDE) using length as 5.
int len = 5;
int *arr = malloc(len*sizeof(int));
// generate an array.
for (int i=0; i<len; i++) {
arr[i] = i;
}
count = derangement(0, len, arr)
printf ("Total combination = %d", count);
}
/** * Store the initial position of elements in the hashmap< index,character> * during permutation you only swap i with j * if element at index j element[j] != hashMap.get(i) */ public List<char[]> getDerragement(char[] chars){ List<char[]> result = new ArrayList<char[]>(); if(chars == null || chars.length == 0){ return result; } Map<Integer,Character> indexCharacterMap = new HashMap<Integer,Character>(); int i = 0; for(char c:chars){ indexCharacterMap.put(i,c); i++; } permute(chars,indexCharacterMap,0,result); return result; } private void permute(char[] chars,Map<Integer,Character> indexCharacterMap,int start,List<char[]> result){ if(start>=chars.length){ result.add(Arrays.copyOf(chars,chars.length)); return; } for(int i = start;i<chars.length;i++){ if(indexCharacterMap.get(i)!=chars[start]){ swap(chars,i,start); permute(chars,indexCharacterMap,start+1,result); swap(chars,i,start); } } } private void swap(char[] chars,int i,int j){ char temp = chars[i]; chars[i] = chars[j]; chars[j] = temp; } public static void main(String argsp[]){ Dearrangements dearrangements = new Dearrangements(); char[] chars = {'A','B','C','D','E'}; List<char[]> result = dearrangements.getDerragement(chars); for(char[] items : result){ for(char item:items){ System.out.print(" "+item); } System.out.println(); } }Result :
- nilesh.d.agrawal April 11, 2017B A D E C
B A E C D
B C A E D
B C D E A
B C E A D
B D A E C
B D E A C
B D E C A
B E D C A
B E D A C
B E A C D
C A B E D
C A D E B
C A E B D
C D A E B
C D B E A
C D E B A
C D E A B
C E A B D
C E D A B
C E D B A
C E B A D
D C B E A
D C A E B
D C E A B
D C E B A
D A B E C
D A E B C
D A E C B
D E A C B
D E A B C
D E B A C
D E B C A
E C B A D
E C D B A
E C D A B
E C A B D
E D B C A
E D B A C
E D A B C
E D A C B
E A D C B
E A D B C
E A B C D