Google Interview Question
SDE1sCountry: United States
@Scavi: youre O(n) is O(n*k) because of the substring. Easy to solve. I had the same idea there.
Followup 2 is an instance of superstring-problem (known NP-hard problem). I think the order matters (besides deciding whether to extend left or right considering common prefix, suffix) with the brute force making it exponential in m=2^k. The naive greedy algorithm will look for the two elements that overlap the most. This already creates a better order.
Your described runtime is only exponential in k, but the original problem is exponential in m. Therefore the algorithm is most likely not correct. But it will find a shorter solution than the first approach.
I doubt anybody comes up with the approximation algorithm in 30 minutes if he hasn't just learned it.
I think that for k=2 it would be, 0,1,10,11. The binary string should be "1101" [decimal value 13], containing all the different values. Similarly for k=3 it would be 111001 [decimal value 57]. This is pretty open questions and would have multiple follow up questions.
Posting the code here with exponential complexity, based on the the above understanding. As ChrisK mentioned the complexity would be (n*2^n). Given the complexity this will not run with k more than 3. Would really love to see a better approach.
public static void main(String[] args) {
int n = 4;
StringBuffer sb = new StringBuffer();
for (int i = 0; i < 200; i++)
sb.append(" ");
StringBuffer sbin = new StringBuffer();
for (int i = 0; i < n; i++)
sbin.append("1");
String min = create(Integer.parseInt(sbin.toString(), 2), Integer.parseInt(sbin.toString(), 2), sbin.toString(), 0, 0, sb.toString(), new HashSet<>());
System.out.println("--------"+min + "=" + Integer.parseInt(min, 2));
}
public static String create(int nn, int n, String str, int indexPrim, int indexBin, String min, Set<String> set) {
if (n == -1) {
if (contains(str, nn) && str.length() < min.length()) {
min = new String(str);
}else if (str.length() < min.length()){
min = create(nn, nn, str, 0, 0, min, set);
}
return min;
}
String nb = Integer.toBinaryString(n);
if (str.contains(nb)) {
set.add(nb);
min = create(nn, n - 1, str, 0, 0, min, set);
} else {
char[] prim = str.toCharArray();
char[] bin = nb.toCharArray();
for (int i = indexPrim; i < prim.length; i++) {
for (int j = indexBin; j < bin.length; j++) {
if (prim[i] == bin[j]) {
min = create(nn, n, str, i + 1, j + 1, min, set);
} else if (i < prim.length) {
String s = str.substring(0, i);
String p = str.substring(i, str.length());
String t = s + bin[j] + p;
min = create(nn, n, t, i + 1, j + 1, min, set);
} else {
min = create(nn, n, str + bin[j], i + 1, j + 1, min, set);
}
}
}
}
return min;
}
public static boolean contains(String str, int n){
for(int i = n; i >= 0; i--){
if(!str.contains(Integer.toBinaryString(n)))
return false;
}
return true;
}
For k <= 64, we can have O(n) time solution (the code below).
Followup 2 sounds like "find the shortest string that contains all of the given words". We can start with a string containing k zeros, and for each next number string, if the cumulative string doesn't contain it, we try to merge it in all possible ways, and go to the next number recursively for each of the branches.
bool ContainsAllBinaryStrings(string const &s, int k)
{
if (k > 0 &&
k <= sizeof(uint64_t) * 8)
{
unordered_set<uint64_t> seen;
uint64_t val = 0;
int size = 0;
for (int i = 0; i < s.size(); ++i) {
if (s[i - k] == '0' ||
s[i - k] == '1')
{
if (i >= k) {
val -= (s[i - k] - '0') << (k - 1);
--size;
}
}
val <<= 1;
if (s[i] == '0' ||
s[i] == '1')
{
val += s[i] - '0';
++size;
}
if (size == k) {
seen.insert(val);
if (seen.size() == (1 << k)) {
return true;
}
}
}
}
return false;
}
recursion:
private List<String> allBinaryStrings(int k) {
char[] arr = new char[k];
List<String> res = new ArrayList<>();
StringBuilder initString = new StringBuilder();
for (int i = 0; i < k; i++){
initString.append("0");
}
allBinaryStringHelper(res, arr, 0, initString.toString());
return res;
}
private void allBinaryStringHelper(List<String> res, char[] arr, int index, String initString) {
if (index >= arr.length) {
StringBuilder t = new StringBuilder();
for (char c : arr) {
t.append(c);
}
res.add(t.toString());
return;
}
char current = initString.charAt(index);
char[] charSet = new char[]{'0', '1'};
if (current == '0') {
for (char aCharSet : charSet) {
arr[index] = aCharSet;
allBinaryStringHelper(res, arr, index + 1, initString);
}
}
if (current == '1') {
for (char aCharSet : charSet) {
arr[index] = aCharSet;
allBinaryStringHelper(res, arr, index + 1, initString);
}
}
}
The second followup is pretty neat! If somebody finds something better then (#shortestStringOfAllBin) it would be great (or if somebody points out that my solution is wrong ;-))
k = 1 => 2
k = 2 => 5
k = 3 => 10
k = 4 => 18
k = 5 => 37 (already takes ~4 seconds)
- Scavi November 24, 2017