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)

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) + sortString(evenOdd);
}
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"};

// 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 = *26
mapeven =  * 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();

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  Bag for even indices ( 0 based indexing )
Odd  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"
]
}``````

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.