## Facebook Interview Question for Software Engineers

Country: United States
Interview Type: In-Person

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

calculate even, odd sum(ascii) and compute a hash for it. Answer will the number of different hashes generated.

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

I'm not convinced this is correct. Imagine you had a character alpha with ascii value 1; beta with ascii = 5, and gamma with ascii = 2
gamma,gamma,gamma,gamma = 8
alpha, alpha, alpha, beta = 8

Clearly these cannot be swapped to be the same.

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

I agree with the comment. then we can concatenate sorted even characters + sorted odd characters and compute hash in a hashset and return the size of the set. For example
"abcd" --> acbd
"aabc"->abac

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

Check my comment below to generate Hash. That will solve ur doubt

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

``````from collections import Counter
def count(arr):
fs = [(tuple(Counter(x[::2]).items()),
(tuple(Counter(x[1::2]).items())))
for x in arr]
return sum(z for (x,z) in Counter(fs).items() if z>1)

print count(["abcd", "acbd", "adcb", "cdba",

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

``````class SpecialEquivalient {

private int count = 0;

SpecialEquivalient (String[] input) {
Set<String> outputSet = new HashSet<String>();;
for(String str : input) {
String[] evenOdd = splitEvenOdd(str);
String sortedString = sortString(evenOdd[0]) + sortString(evenOdd[1]);
}
count = outputSet.size();
}

String[] splitEvenOdd(String str) {
char[] chars = str.toCharArray();
String odd = new String();
String  even = new String();
for (int i=0; i<str.length(); i++) {
if (i % 2 == 1) {
odd += chars[i];
} else {
even += chars[i];
}
}
return new String[] {odd, even};
}

String sortString(String str) {
char[] charArray = str.toCharArray();
Arrays.sort(charArray);
return new String(charArray);
}

public int uniqueCount() {
return count;
}
}``````

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

``````public class Main {

public static void main(String[] args) {

// test set
//        String[] arr = {"abcd", "cbad", "bacd"};
String[] arr = {"abcd", "acbd", "adcb", "cdba", "bcda", "badc"};

// convert ArrayList form as it is beneficial to handle
ArrayList<String> input = new ArrayList<String>();
for (int i = 0; i <arr.length; i++) {
}

// main loop
for (int i = 0; i < input.size()-1; i++) {

for (int j = i+1; j < input.size(); j++) {

// Question here: any possibility that identical strings exist? (assuming no for now)

// check with swapEven
if (input.get(i).equals(swapEven(input.get(j)))) {
// remove if equivalent
input.remove(j);
j--;
// go back to loop
continue;
}

// check with swapOdd
if (input.get(i).equals(swapOdd(input.get(j)))) {
// remove if equivalent
input.remove(j);
j--;
// go back to loop (no need as this is end of loop)
//continue;
}
}

}

System.out.println("length: " + input.size());
}

// swap a character at even-numbered index
// assuming string length is 4
static String swapEven(String in) {

char data[] = {in.charAt(2), in.charAt(1), in.charAt(0), in.charAt(3)};
String out = new String(data);

return out;
}

// swap a character at odd-numbered index
// assuming string length is 4
static String swapOdd(String in) {

char data[] = {in.charAt(0), in.charAt(3), in.charAt(2), in.charAt(1)};
String out = new String(data);

return out;
}
}``````

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

#!/usr/bin/env python
import collections

class Soln(object):
def encode(self, s):
print s

mapodd = [0]*26
mapeven = [0] * 26
encodestr = ""

for i in range(len(s)):
c = s[i]
if i&1:
mapodd[ord(c) - ord('a')] += 1
else:
mapeven[ord(c) - ord('a')] += 1

for i in range(26):
encodestr += str(mapeven[i])
encodestr += str(ord('-'))
encodestr += str(mapodd[i])
encodestr += str(ord('-'))

print encodestr
return encodestr

def distictWords(self, words):
lw = len(words)
if lw == 0:
return 0
ordset = collections.defaultdict(int)
for i in range(lw):
encodestr = self.encode(words[i])
ordset[encodestr] += 1

print ordset
return len(ordset)

soln = Soln();
print soln.distictWords(["abcd", "cbad", "dbac"])
print soln.distictWords(["abcd", "acbd", "adcb", "cdba", "bcda", "badc"])

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

For each string, sort all even characters among themselves. For each string, sort all odd characters among themselves. Then start putting the strings in a hashmap. For example, if String s1 after sorting matches string s2, s1 is key and s2 is part of a list which is value of s1. Repeat for any strings which do not match.

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

This is typical example of hashing with user defined Hash function.

Just generate a hash based on index and then count distinct string by Hash.

``````static String encodeString(char[] str) {
// hashEven stores the count of even indexed character
// for each string hashOdd stores the count of odd
// indexed characters for each string
int hashEven[] = new int[MAX_CHAR];
int hashOdd[] = new int[MAX_CHAR];

// creating hash for each string
for (int i = 0; i < str.length; i++) {
char c = str[i];
if ((i & 1) != 0) // If index of current character is odd
hashOdd[c-'a']++;
else
hashEven[c-'a']++;

}

// For every character from 'a' to 'z', we store its
// count at even position followed by a separator,
// followed by count at odd position.
String encoding = "";
for (int i = 0; i < MAX_CHAR; i++) {
encoding += (hashEven[i]);
encoding += ('-');
encoding += (hashOdd[i]);
encoding += ('-');
}
return encoding;
}``````

A hash function.

Just iterate and convert to hash, put in set if not present then increase count otherwise skip

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

``````/*
Problem is that:
swap_even() can permutate only even indices.
swap_odd() can permutate only odd indices.
That means that if someone breaks down the word into
two bag of characters with
Even [0] Bag for even indices ( 0 based indexing )
Odd [1] Bag of odd indices
Then, two words are equivalent if
for word w1 and w2
the bags ( Even and Odd ) are comprise of exact same
characters with exact same frequencies
that is the tuple ( char , count ) must be same
But on introspection, we can not compare this dictionary tuples.
So, what we do is create a sorted charset and then put a delimiter
to ensure that sorted_even_chars # sep # sorted_odd_chars
acts as key

Thus, we can create a hash function that is entirely reliant on that.
*/

def special_equivalent_hash_function( string ){
#(even, odd) = partition( string.toCharArray ) where { 2 /? \$.i }
sorted_evens = str( sorta(even), '')
sorted_odds = str( sorta(odd), '')
sorted_evens + "#" +  sorted_odds // return
}

def find_all_special_equivalents( list_of_strings ){
mset( list_of_strings ) as {
special_equivalent_hash_function( \$.o )
}
}

res = find_all_special_equivalents( ["abcd", "cbad", "bacd" ] )
println( jstr(res,true) )``````

Produces :

``````{
"ac#bd":[
"abcd",
],
"bacd"
]
}``````

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

``````def main():
strAr = ["abcd", "cbad", "efgh", "cdab"]

searchAr = strAr.copy()

count = 0
countEven, countOdd = 0,0
total = 0

for str in strAr:
l1 = list(str)
searchAr = strAr.copy()
searchAr.remove(str)
countEven = search(l1,searchAr, count, 0)
countOdd = search(l1,searchAr, count, 1)

total += countEven + countOdd

print ("total : ", total)

def search(l1, searchAr, count, start):

total = 0

i = start

for i in range(0,len(l1)-1,2):
for j in range (i+2,len(l1)-1,2):
s = l1[i]
l1[i] = l1[j]
l1[j] = s
count = getCount(l1, searchAr, count)
total += count

def getCount(l1, searchAr, count):

s1 = "".join(l1)

print("getCount")
print(s1)
print(searchAr)

for s in searchAr:
if (s1 == s):
count += 1

print(count)

return count

main()``````

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

Just split one Stirng (a1b1a2b2a3b3.....) to two sets of odd and even (a1, a2, a3 ...) and (b1, b2, b3...). Sort them and put the two sorted together.

Count the unique strings as processed above.
Based on the theory that for a given sequence (a1, a2, a3 .... an)
ALL n! permutations can be get by exchange ax and ay (1<=x<=y<=n). This can be easily proven by Mathematical Induction.

code:

``````public class TwoSwapString {

public static void main(String[] arug) {
int n = 0;
n = count(new String[]{"abcd","cbad","bacd"});
System.out.println(n);
n = count(new String[]{"abcd", "acbd", "adcb", "cdba","bcda", "badc"});
System.out.println(n);
}

private static int count(String[] strings) {
HashSet<String> result = new HashSet<>();
for (int i=0; i<strings.length; i++) {
String s = strings[i];
String even = "";
String odd = "";
for (int j=0; j<s.length(); j++) {
if (j % 2 == 0) {
even += s.charAt(j);
} else {
odd += s.charAt(j);
}
}
even = toString(even.toCharArray());
odd = toString(odd.toCharArray());
result.add(even + "," + odd);
}

System.out.println(result);

return result.size();
}

private static String toString(char[] chars) {
Arrays.sort(chars);
return new String(chars);
}
}``````

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.