Facebook Interview Question Software Developers
Country: United States
Interview Type: In-Person
My simple recursive solution:
namespace {
typedef int64_t Num;
typedef unordered_set<uint64_t> NumSet;
bool check(Num n, int digitsLeft, NumSet &excludes) {
if (digitsLeft == 0) return n == 0;
if (digitsLeft == 1) return excludes.count(n) == 0 && n > 0 && n <= 59;
for (bool isTwoDigit: {true, false}) {
auto digit = isTwoDigit ? n % 100 : n % 10;
if (excludes.count(digit) == 0 && (isTwoDigit ? digit >= 10 && digit <= 59 : digit > 0)) {
auto m = isTwoDigit ? n / 100 : n / 10;
excludes.insert(digit);
bool result = check(m, digitsLeft - 1, excludes);
excludes.erase(digit);
if (result) return result;
}
}
return false;
}
}
bool isLotteryTicket(Num n) {
NumSet excludes;
return check(n, 7, excludes);
}
{public static void main(String[] args){
System.out.println(isLottery("1634616512"));
}
private static boolean isLottery(String number) {
int numberOfTwoDigit = number.length() - 7;
int numberOfSingleDigit = 7 - numberOfTwoDigit;
Integer[] positions = {0,1, 2, 3, 4, 5, 6};
List<Integer> positionsAvailable = Arrays.asList(positions);
return getPositions(new ArrayList<Integer>(), positionsAvailable, numberOfTwoDigit, number);
}
private static boolean getPositions(List<Integer> positions, List<Integer> positionsRemaining, int numberRequired, String inputNumber) {
boolean output = false;
if (numberRequired == 0) {
String number = inputNumber;
Set<Integer> numbersFromLottery = new HashSet<>();
for (int i = 0; i < 7; i++) {
if (positions.contains(i)) {
if (Integer.parseInt(number.substring(0, 2)) > 59) {
break;
}
numbersFromLottery.add(Integer.parseInt(number.substring(0, 2)));
number = number.substring(2);
} else {
numbersFromLottery.add(Integer.parseInt(number.substring(0, 1)));
number = number.substring(1);
}
}
if (numbersFromLottery.size() == 7) {
//System.out.println("true");
return true;
}
return false;
} else {
boolean currentoutput = false;
for (int i = 0; i < positionsRemaining.size(); i++) {
List<Integer> positionsLocal = new ArrayList();
positionsLocal.addAll(positions);
List<Integer> positionsRemainingLocal = new ArrayList<>();
positionsRemainingLocal.addAll(positionsRemaining);
int n = positionsRemainingLocal.get(i);
if (positionsLocal.isEmpty() || n > positionsLocal.get(positions.size() - 1)) {
positionsLocal.add(n);
positionsRemainingLocal.remove(i);
currentoutput = currentoutput || getPositions(positionsLocal, positionsRemainingLocal, numberRequired - 1, inputNumber);
} else {
continue;
}
}
return currentoutput||output;
}
}}
public class LotteryTickets {
public static void main(String[] args) {
for (int i = 0; i < args.length; i++) {
isValidLotteryTicket(args[i].toCharArray());
}
}
private static boolean isValidLotteryTicket(char[] s) {
// string must be between 7 (only single elements) and 14 (all double digit elements)
if (s.length == 0 || s.length < 7 || s.length > 14 || s[0] == '0') {
return false;
}
// transform input string into an array of integers - check for any invalid inputs such as negatives or non-numbers
int[] nums = new int[s.length];
try {
for (int i = 0; i < s.length; i++) {
nums[i] = Integer.parseInt(Character.valueOf(s[i]).toString());
if (nums[i] < 0) return false;
}
} catch (NumberFormatException nfe) {
return false;
}
int doubleDigitNums = nums.length - 7;
int singleDigitNums = 7 - doubleDigitNums;
return isValidLotteryTicket(nums, new ArrayList<>(), 0, singleDigitNums, doubleDigitNums);
}
private static boolean isValidLotteryTicket(int[] nums, List<Integer> numsUsed, int i, int singleDigitNums, int doubleDigitNums) {
if (i > nums.length || numsUsed.size() > 7) {
return false;
}
else if (i == nums.length) {
if (numsUsed.size() == 7) {
// stop condition check if all elements were used and lottery ticket has 7 elements.)
for (Integer n : numsUsed) {
System.out.print(n + " ");
}
System.out.println();
}
return true;
}
int num = nums[i];
if (num > 5) { // number can only be used as a single digit in ticket, such elements are 6,7,8,9
if (singleDigitNums <= 0 || numsUsed.contains(num)) {
return false;
}
numsUsed.add(num);
return isValidLotteryTicket(nums, new ArrayList<>(numsUsed), i + 1, singleDigitNums-1, doubleDigitNums);
} else {
// number can be used as a single digit or as a pair for a double digit number 10-59 try both possibilities
boolean valid = false;
boolean added = false;
// try it as single digit
if (singleDigitNums > 0 && !numsUsed.contains(num)) {
numsUsed.add(num);
added = true;
valid = isValidLotteryTicket(nums, new ArrayList<>(numsUsed), i + 1, singleDigitNums-1, doubleDigitNums);
}
// try it as double digit
if (!valid && i + 1 < nums.length && doubleDigitNums > 0) {
if (added) numsUsed.remove(numsUsed.size() - 1);
int doubleDigitNum = new Integer(num + "" + nums[i + 1]);
if (!numsUsed.contains(doubleDigitNum)) {
numsUsed.add(doubleDigitNum);
valid = isValidLotteryTicket(nums, new ArrayList<>(numsUsed), i + 2, singleDigitNums, doubleDigitNums-1);
}
}
return valid;
}
}
}
bool isLotteryNumber(string s, Stack<int> stack)
{
int val = 0;
if (s.Length > 0)
{
val = int.Parse(s.Substring(0, 1));
if(stack.Contains(val)) return false;
}
if (s.Length == 0 || stack.Count > 7)
{
stack.Dump();
return (stack.Count == 7);
}
val = int.Parse(s[0].ToString());
stack.Push(val);
var result = isLotteryNumber(s.Substring(1), stack);
if (!result && s.Length > 1)
{
stack.Pop();
val = int.Parse(s.Substring(0, 2));
if (val > 59) return false;
if (stack.Contains(val)) return false;
stack.Push(val);
result = isLotteryNumber(s.Substring(2), stack);
}
stack.Pop();
return result;
}
import java.util.HashSet;
import java.util.Set;
public class ValidLotterySize {
public static void main(String[] args) {
System.out.println(isValidLotterySize("4938532894754", 0, new HashSet<>()));
System.out.println(isValidLotterySize("1634616512", 0, new HashSet<>()));
System.out.println(isValidLotterySize("1234567", 0, new HashSet<>()));
}
public static boolean isValidLotterySize(String input, int index, Set<Integer> unqiue) {
if (index == input.length()) {
return unqiue.size() == 7;
}
if (index < input.length() && unqiue.size() >= 7) {
return false;
}
// case 0:
int currentValue = Integer.parseInt(input.substring(index, index+1));
if (!unqiue.contains(currentValue)) {
Set<Integer> newUnique = new HashSet<>(unqiue);
newUnique.add(currentValue);
boolean validLotterySize = isValidLotterySize(input, index + 1, newUnique);
if (validLotterySize) {
return true;
}
}
// case 1:
if (index < input.length() -1) {
int currentValuetwo = Integer.parseInt(input.substring(index, index+2));
if (!unqiue.contains(currentValuetwo)) {
Set<Integer> newUnique = new HashSet<>(unqiue);
newUnique.add(currentValuetwo);
boolean validLotterySize = isValidLotterySize(input, index + 2, newUnique);
if (validLotterySize) {
return true;
}
}
}
return false;
}
}
import java.util.HashSet;
import java.util.Set;
public class ValidLotterySize {
public static void main(String[] args) {
System.out.println(isValidLotterySize("4938532894754", 0, new HashSet<>()));
System.out.println(isValidLotterySize("1634616512", 0, new HashSet<>()));
System.out.println(isValidLotterySize("1234567", 0, new HashSet<>()));
}
public static boolean isValidLotterySize(String input, int index, Set<Integer> unqiue) {
if (index == input.length()) {
return unqiue.size() == 7;
}
if (index < input.length() && unqiue.size() >= 7) {
return false;
}
// case 0:
int currentValue = Integer.parseInt(input.substring(index, index+1));
if (!unqiue.contains(currentValue)) {
Set<Integer> newUnique = new HashSet<>(unqiue);
newUnique.add(currentValue);
boolean validLotterySize = isValidLotterySize(input, index + 1, newUnique);
if (validLotterySize) {
return true;
}
}
// case 1:
if (index < input.length() -1) {
int currentValuetwo = Integer.parseInt(input.substring(index, index+2));
if (!unqiue.contains(currentValuetwo)) {
Set<Integer> newUnique = new HashSet<>(unqiue);
newUnique.add(currentValuetwo);
boolean validLotterySize = isValidLotterySize(input, index + 2, newUnique);
if (validLotterySize) {
return true;
}
}
}
return false;
}
}
First, the split of 1634616512 in the example isn't valid because 6 is in there twice :) I approached this as a DP problem iteratively and it looks to me it can be solved almost greedily, where you try to get the 2 digit numbers as fast as possible. If the code runs into an issue however it must go back and see if another state can be broken up. Code in Python. Assuming input is a string but can be cast as that if necessary.
def checkValidLotto(numstr):
# The valid lengths are between 7 and 14.
# The number of double digits we need is then len - 7, i.e. we need 2 if length is 9 etc.
numdouble = len(numstr) - 7
if numdouble < 0 or numdouble > 7:
return False
numsingle = 7 - numdouble
found_double = set() # This is how we test for duplicates
found_single = set() # This is how we test for duplicates
i = 0
while i < len(numstr):
# We want to get double digits out of the way ASAP
one_digit = int(numstr[i])
two_digit = int(numstr[i:(i+2)])
if one_digit < 6 and two_digit not in found_double and numdouble > 0:
numdouble -= 1
i += 2
found_double.add(two_digit)
elif one_digit not in found_single:
# if numsingle is 0, we have run out of options
if numsingle == 0:
return False
numsingle -= 1
i += 1
found_single.add(one_digit)
elif one_digit < 6:
# Here we have to go back through and see if we can break one of the doubles up to make the solution work
resolved = False
for double in found_double:
if (double // 10 < 6
and double // 10 not in found_single
and double % 10 not in found_single
and two_digit not in found_double):
found_double.discard(double)
found_double.add(two_digit)
found_single.add(double // 10)
found_single.add(double % 10)
numsingle -= 2
i += 2
resolved = True
break
if resolved == False:
return False
else:
return False
# One last check to return true
if numdouble == 0 and numsingle == 0:
return True
else:
return False
print(checkValidLotto("1234567"))
print(checkValidLotto("1232347"))
print(checkValidLotto("123"))
print(checkValidLotto("66445571222222222"))
print(checkValidLotto("4938532894754"))
print(checkValidLotto("1122334"))
print(checkValidLotto("163461512"))
print(checkValidLotto("1634616512"))
public class LotteryNumber {
public static void main(String[] args) {
Assert.assertTrue(lotteryNumber.valid("4938532894754"));
Assert.assertTrue(lotteryNumber.valid("1634616512"));
Assert.assertFalse(lotteryNumber.valid("1122334"));
Assert.assertFalse(lotteryNumber.valid("1122334Y"));
Assert.assertFalse(lotteryNumber.valid("ABCDEFEFY"));
}
public boolean valid(String text) {
if (isEmpty(text)) {
return false;
}
return search(new HashSet<>(), text);
}
private boolean search(HashSet<Integer> numbers, String text) {
if (numbers.size() == 7) {
return true;
}
if (text == null || text.length() == 0) {
return false;
}
int size = text.length();
for (int i = 0; i < size; i++) {
String sub1 = text.substring(0, i + 1);
String sub2 = null;
if (i + 1 < text.length()) {
sub2 = text.substring(i + 1);
}
int tmp = toInt(sub1);
if (!numbers.contains(tmp) && 1 <= tmp && tmp <= 59) {
numbers.add(tmp);
if (search(numbers, sub2)) {
return true;
}
numbers.remove(tmp);
}
}
return false;
}
private int toInt(String text) {
int num = 0;
for (char c : text.toCharArray()) {
num = (num * 10) + Character.getNumericValue(c);
}
return num;
}
private boolean isEmpty(String text) {
if (text == null || text.length() == 0) {
return true;
}
return false;
}
}
This can be achieved with dynamic programming as to find if 1234567 is a valid lottery number of 7 count then we can say it is if 234567 is a valid lottery number with 6 count when considering 1 OR 34567 is a valid lottery number with 6 count when considering 12.
Basically when you combined the digits together the remaining string has to be a lottery number as well with a different count
public class Solution {
public boolean isLotteryNumber(String numberStr, int count) {
if(numberStr == null || numberStr.isEmpty() || count < 1) {
return false;
}
Map<Node, Boolean> countMap = new HashMap<>();
return this.isLotteryNumber(numberStr.toCharArray(), 0, count, countMap);
}
private boolean isLotteryNumber(Char[] array, int index, int count, Map<Node, Boolean> countMap) {
Node n = new Node();
n.index = index; n.count = count;
if(countMap.hasKey(n)) {
return countMap.get(n);
}
else if(index >= array.length || (array.length - index) < count || (array.length - index) > count*2) {
return false;
}
StringBuilder sb = new StringBuilder();
sb.append(array[index]);
boolean isValidLottery = false;
for(int i = index + 1; i < array.length; i++) {
if(!this.isValidNumber(sb.toString())) {
break;
}
isValidLottery = isValidLottery || this.isLotteryNumber(array, i, count - 1, countMap);
if(isValidLottery && index == 0) {
// There is atleast one valid lottery so returning true and stopping the code flow
// we arent interesting in all combinations but just to find if a valid combination exists
return true;
}
sb.append(array[i]);
}
countMap.put(n, isValidLottery);
return isValidLottery;
}
private boolean isValidNumber(String s) {
if(s == null || s.isEmpty()) {
return false;
}
try {
int v = Integer.parseInt(s);
return v >= 1 && v <= 59;
}
catch(NumberFormatException e) {
return false;
}
}
private class Node {
public int index;
public int count;
// Remember to override equals and hash method, skipping here for brevity
}
}
there was a bug in the code above so fixing it, but idea is same recursively figure out if substrings are lottery number as well with less count:
public class Solution {
public boolean isLotteryNumber(String numberStr, int count) {
if(numberStr == null || numberStr.isEmpty() || count < 1) {
return false;
}
Map<Node, Boolean> countMap = new HashMap<>();
return this.isLotteryNumber(numberStr.toCharArray(), 0, count, countMap);
}
private boolean isLotteryNumber(Char[] array, int index, int count, Map<Node, Boolean> countMap) {
Node n = new Node();
n.index = index; n.count = count;
if(countMap.hasKey(n)) {
return countMap.get(n);
}
else if(index >= array.length || (array.length - index) < count || (array.length - index) > count*2) {
return false;
}
StringBuilder sb = new StringBuilder();
sb.append(array[index]);
boolean isValidLottery = false;
for(int i = index + 1; i < array.length; i++) {
if(!this.isValidNumber(sb.toString())) {
break;
}
isValidLottery = this.isLotteryNumber(array, i, count - 1, countMap);
if(isValidLottery) {
break;
}
sb.append(array[i]);
}
countMap.put(n, isValidLottery);
return isValidLottery;
}
private boolean isValidNumber(String s) {
if(s == null || s.isEmpty()) {
return false;
}
try {
int v = Integer.parseInt(s);
return v >= 1 && v <= 59;
}
catch(NumberFormatException e) {
return false;
}
}
private class Node {
public int index;
public int count;
// Remember to override equals and hash method, skipping here for brevity
}
}
<?php
$string = "4938532894754";
$set = checkLot($string);
if($set) {
print_r($x);
die("OK");
}
else die("NO");
function checkLot($string,$i=0,$set=array()){
if(sizeof($set) > 7) return false;
if($i >= strlen($string)){
if(sizeof($set) == 7)
return $set;
else
return false;
}
//Check If $string[$i] is exists
if(!in_array($string[$i],$set)){
$currentSet = $set;
$currentSet[]=$string[$i];
$check = checkLot($string,$i+1,$currentSet);
if($check) return $check;
}
// same for two numbers
if($i <> strlen($string)-1){
$currentSet = $set;
$number = $string[$i].$string[$i+1];
if(!in_array($number,$set) && intval($number)<60){
$currentSet[]=$number;
$check = checkLot($string,$i+2,$currentSet);
if($check) return $check;
}
}
return false;
}
?>
It's recursion time!
#include <iostream>
using namespace std;
bool isLottery(string number, int index, int count)
{
if (index == number.length() && count == 7)
{
return true;
}
else if (index >= number.length())
{
return false;
}
char first = number[index];
char second = number[index + 1];
int value = (first - '0') * 10 + (second - '0');
if (first < '0'
|| first > '9'
|| second < '0'
|| second > '9')
{
return false;
}
if (isLottery(number, index + 1, count + 1)
|| (value >= 1
&& value <= 59
&& isLottery(number, index + 2, count + 1)))
{
return true;
}
return false;
}
int main()
{
cout << isLottery("4938532894754", 0, 0) << endl;
cout << isLottery("1634616512", 0, 0) << endl;
cout << isLottery("1122339988", 0, 0) << endl;
cout << isLottery("88", 0, 0) << endl;
cout << isLottery("55", 0, 0) << endl;
cout << isLottery("AABBCCDDEEFFGG", 0, 0) << endl;
cout << isLottery("ABCDEFG", 0, 0) << endl;
return 0;
}
public static boolean check(String str)
{
HashSet<Integer> unique = new HashSet<>();
return check(str, 0, unique);
}
private static boolean check(String str, int idx, HashSet<Integer> unique)
{
if(idx >= str.length())
{
return unique.size() == 7;
}
for(int i = 1; i <= 2 && idx + i <= str.length(); i++)
{
int thisPart = Integer.parseInt(str.substring(idx, idx+i));
if(thisPart >= 1 && thisPart <= 59 && !unique.contains(thisPart))
{
unique.add(thisPart);
if(check(str, idx + i, unique))
return true;
unique.remove(thisPart);
}
}
return false;
}
public static boolean check(String str)
{
HashSet<Integer> unique = new HashSet<>();
return check(str, 0, unique);
}
private static boolean check(String str, int idx, HashSet<Integer> unique)
{
if(idx >= str.length())
{
return unique.size() == 7;
}
for(int i = 1; i <= 2 && idx + i <= str.length(); i++)
{
int thisPart = Integer.parseInt(str.substring(idx, idx+i));
if(thisPart >= 1 && thisPart <= 59 && !unique.contains(thisPart))
{
unique.add(thisPart);
if(check(str, idx + i, unique))
return true;
unique.remove(thisPart);
}
}
return false;
}
The basic recursion works as follows: at each point you have a sequence from which you can take 1 or 2 elements (given the constraints). The Base case is when the given sequence of elements is empty, if the if set of numbers is equal to the lucky number (7 in this case) we return true; otherwise it is not a valid solution. Cost O(2^n) in this case we can't use dynamic programming to improve the complexity as we can't use any property to get the best option between any of the multiple ones (I think :P). In other words I haven't been able to find an optimal substructure to prune the recursion
Inputs:
s -> list of integers
n -> the number of numbers (7 in this case)
v -> must be set()
- Fernando June 09, 2017def isLotteryTicket(s, n, v): if len(s) == 0: return len(v) == n a = False; b = False if s[0] <= 5 and len(s) > 1: x = s[0] * 10 + s[1] if x not in v: a = isLotteryTicket(s[2:], n, v.copy().union([x])) if s[0] not in v: b = isLotteryTicket(s[1:], n, v.copy().union([s[0]])) return a or b