Facebook Interview Question
SDE1sCountry: United States
Interview Type: Phone Interview
printOneEighty :: Int -> [String]
printOneEighty 0 = [""]
printOneEighty 1 = ["0","1","8"]
printOneEighty k = let temp = printOneEighty $ k - 2
in foldl appendDigits [] temp
where
appendDigits acc str = acc ++ added str
added str = [(show . fst $ pair) ++ str ++ (show . snd $ pair) | pair <- [(0,0),(1,1),(8,8),(6,9),(9,6)]]
main = do
putStrLn . show . printOneEighty $ 5
//prints ["00000","10001","80008","60009","90006","01010","11011","81018","61019","91016","08080","18081","88088","68089","98086","06090","16091","86098","66099","96096","09060","19061","89068","69069","99066","00100","10101","80108","60109","90106","01110","11111","81118","61119","91116","08180","18181","88188","68189","98186","06190","16191","86198","66199","96196","09160","19161","89168","69169","99166","00800","10801","80808","60809","90806","01810","11811","81818","61819","91816","08880","18881","88888","68889","98886","06890","16891","86898","66899","96896","09860","19861","89868","69869","99866"]
NUM_LIST = ["0", "1", "6", "8", "9"]
UPSIDE_DOWN = {
"0" : "0",
"1" : "1",
"6" : "9",
"8" : "8",
"9" : "6"
}
def get180(digits):
"""
Return numbers with specified digits that look the same upside down
"""
if digits == 0:
return ['']
if digits == 1:
return filter(lambda x: UPSIDE_DOWN[x] == x, NUM_LIST)
middle_list = get180(digits - 2)
result_list = []
for number in NUM_LIST:
for middle in middle_list:
result_list.append(number + middle + UPSIDE_DOWN[number])
return result_list
public class UpsideDownString {
private Map<String, String> reverseMap;
public UpsideDownString() {
reverseMap = new HashMap<>();
reverseMap.put("8", "8");
reverseMap.put("6", "9");
reverseMap.put("0", "0");
reverseMap.put("1", "1");
}
public ArrayList<String> solve(int n) {
if (n == 0) return new ArrayList<>();
if (n == 1) return new ArrayList<String>(Arrays.asList("8", "0", "1"));
if (n == 2) return new ArrayList<>(Arrays.asList("00", "11", "69", "96", "88"));
// we will solve sub problem with n-2 characters.
// after that we append 2 char onto left-most and right-most
ArrayList<String> upsideDownStrings = solve(n - 2);
ArrayList<String> res = new ArrayList<String>();
for (String str : upsideDownStrings) {
for (Map.Entry entry : reverseMap.entrySet()) {
String key = (String) entry.getKey();
String value = (String) entry.getValue();
String newReversible = key + str + value;
res.add(newReversible);
}
}
return res;
}
}
public class Solution{
static Map<String, String> map = new HashMap<String,String>();
static {
map.put("0", "0");
map.put("1", "1");
map.put("6", "9");
map.put("9", "6");
map.put("8", "8");
}
public static List<String> generate(int k){
if(k == 0) return new ArrayList<String>();
if(k == 1) return new ArrayList<String>(Arrays.asList("0","1","8"));
List<String> result = new ArrayList<String>();
List<String> subList = generate(k-2);
for(Entry<String, String> entry : map.entrySet()){
if(subList.isEmpty()){
String tmp = entry.getKey() + entry.getValue();
result.add(tmp);
}
for(String s : subList){
String tmp = entry.getKey() + s + entry.getValue();
result.add(tmp);
}
}
return result;
}
public static void main(String[] args){
System.out.println(generate(2));
}
}
- mche1987 March 27, 2018