Google Interview Question for SDE1s


Country: United States




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

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)

// first question: O(2^k * k) space and runs in O(n) time (while n is the length of the input string)
    public boolean checkBinariesExisting(final String input, final int k) {
        if (input == null || k > input.length()) {
            return false;
        }
        Set<String> binary = new HashSet<>();
        for (int i = 0; i < 1 << k; ++i) {
            binary.add(createBinString(k, i));
        }
        String temp;
        for (int i = 0; i <= input.length() - k && !binary.isEmpty(); ++i) {
            temp = input.substring(i, i + k);
            if (binary.contains(temp)) {
                binary.remove(temp);
            }
        }
        return binary.size() == 0;
    }

    // first followup (lazy solution)
    public String stringOfAllBin(final int k) {
        if (k < 0) {
            return null;
        }
        int length = 1 << k;
        StringBuilder temp = new StringBuilder(length * k);
        for (int i = 0; i < length; ++i) {
            temp.append(createBinString(k, i));
        }
        return temp.toString();
    }

    // second followup:runs in O(2^ (k² - 2) ) * k  and uses constant space
    public String shortestStringOfAllBin(final int k) {
        if (k < 0) {
            return null;
        }
        int length = 1 << k;
        String current = createBinString(k, length - 1) + createBinString(k, 0);
        return shortestStringOfAllBin(current, k, length - 2);
    }


    private String shortestStringOfAllBin(final String current, final int k, final int i) {
        if (i <= 0) {
            return current;
        } else {
            String newBinary = createBinString(k, i);

            String result = null;
            // search pruning - the new binary exists already in the current string
            if (Pattern.compile(newBinary).matcher(current).find()) {
                result = shortestStringOfAllBin(current, k, i - 1);
            }
            // the current newBinary doesn't exist yet in the current
            else {
                String tempResult = null;
                for (int j = newBinary.length(); j > 0; --j) {
                    String binaryPart = newBinary.substring(0, j);
                    String overlapping = newBinary.substring(j, newBinary.length());

                    // try to add the current string part from the left side
                    if (j == newBinary.length() || current.startsWith(overlapping)) {
                        tempResult = shortestStringOfAllBin(binaryPart + current, k, i - 1);
                    }
                    result = result == null || result.length() > tempResult.length() ? tempResult : result;

                    // try to add the current string part from the right side
                    if (j == newBinary.length() || current.endsWith(overlapping)) {
                        tempResult = shortestStringOfAllBin(current + binaryPart, k, i - 1);
                    }
                    result = result == null || result.length() > tempResult.length() ? tempResult : result;
                }
            }
            return result;
        }
    }


    private String createBinString(final int k, final int i) {
        return String.format("%0" + k + "d", Integer.valueOf(Integer.toBinaryString(i)));
    }

- Scavi November 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think idea is to use state diagram ... Assume k =3 then If state is 110 and then two possible states are 1. State-4/100 if you append 0 to 110 and 2. State -101 if you append 1 to 110

Now shortest string is shortest path in state diagram that covers all states or nodes

- sameer November 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@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.

- Chris November 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@ChrisK You are correct with the runtime. Thanks for the correction :-)

- Scavi November 25, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	}

- sudip.innovates November 26, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Alex November 26, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
            }
        }
    }

- Hugh May 28, 2018 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More