## Interview Question for Tech Leads

Country: India

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

Varun,

My thoughts around this is:

2 Bits: 00,01,10,11 - In this the given set is 11,00 so the longest strings would be formed using 01 or 10. So it can be 101010101010....infinite or 01010101010101...infinite.

3 Bits: 000,001,010,011,100,101,110,111 - Among these elements the given set contains 101,111,00,110.....so any longest string that you form would be with remaining elements
like 010 or 000 or 011 or 100

Is this a kind of pattern that we found that what are the possible combination of string that you can form with X no of bits and subtract the given set would give us the longest strings.

Off course this is on an assumption that the strings are formed only with 1`s and 0`s.

Best Regards,
Sai

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

Sai,
yep under your assumption this looks ok, but
Length of all given string need not be same.
and they al might not have same characters
instance, 01, 12, 133

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

what is the size limit on the strings that we're given?

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

Max 20 for some reason was mentioned to me.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

What is the limits on the number of character. Your example is only binary character, but it can be anything ASCII or Unicode is that right

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

Yes, with longest given string length can at max be 20.
so we can have max 20 different letter in our alphabet

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

I believe graph algorithm will be good for this.
1. Assume there are M strings in the Set
2. Assume there are N characters
3. Assume the longest string in the Set, length = K

So,
1. you can construct nodes which value of string (length <= K) and does not contains any string in the Set.
2. try to construct the (segments) of the nodes
a. it includes the self loop links
b. the longest segments (concat string length > K), stop
3. Use graph search to find the longest path in the graph
a. if you find a loop, the answer is 'infinite'
b. otherwise, the longest path is what you have.

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

A simplified version for this is,
Just use the single char as node value, but you need construct a lot of restricted segments based on the Set.

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

Code not working correct for second case rite?
I copied and compiled this on my machine it I get
-1
000000
000001

Comment hidden because of low score. Click to expand.
-1
of 1 vote

It should but becareful to run with second case you should change 2 line (instead of 1 since the number of input is different)

std::string arr[] = {"101", "111", "00", "110"};
std::vector<std::string > ref(arr, arr + 4);

Comment hidden because of low score. Click to expand.
-1
of 1 vote

There're might be a potential error that I use .size() with the meaning of length(). I have fixed it. Could you please check to see if it is working on your machine now

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

My proposal can be devided in 2 main steps

1- From the input deduce the alphabet ( all the symbols that appear at least once in the items of the input list )
eg1 : 1ab, acg, 105, 11 ==> alphabet {1,a,b,c,0,5}
2- Using the alphabet try to generate words which lengths are equal to the maximum length of the strings ( here 3), but without any item of the input as substring. If this is not possible then the maximum length of the string will be inferior to the maximum of the input strings ( here < 3 ) otherwise continue the process to double the length of the words ( 6 )
eg2 :
1a1,1ac,1a0,1a5 etc.
then
eg 3 : 1a1 5cb

if it is possible to double the length of the word then the length will be infinite
otherwise ...

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Mine solution is for binary string but it can be extent to string with a set of character. The idea based on extending feasible level of a suffix tree. The infinity condition is based on the repeat of the substring, when substring repeat we can easily construct a solution with infinite length
@Edit: change .size() to .length() to get the length of the string

#include <iostream>
#include <string>
#include <vector>

bool check_contain(std::string& a, const std::vector<std::string > subs) {
for (int i=0; i< subs.size(); ++i) {
if (a.length() >= subs[i].length()) {
std::string s = a.substr(a.length() - subs[i].length(), subs[i].length());
if (s == subs[i])
return true;
}
}
return false;
}

bool check_repeat(std::string& a, int n) {
if (a.length() < 2 * n)
return false;
std::string s1 = a.substr(a.length() - n, n);
std::string s2 = a.substr(a.length() - 2 * n, n);
return s1.compare(s2) == 0;
}

int main(int argc, char** argv)
{
std::string arr[] = {"11", "00"};
//std::string arr[] = {"101", "111", "00", "110"};
std::vector<std::string > ref(arr, arr + 2);
int max_length = 0;
for (int i=0; i< ref.size(); ++i)
if (ref[i].length() > max_length)
max_length = ref[i].length();

std::vector<std::string > non_cover_set_prev;
std::vector<std::string > non_cover_set;

non_cover_set_prev.push_back(std::string(""));

bool repeat = false;
while (!repeat) {
non_cover_set.clear();
for (int i=0; i< non_cover_set_prev.size() && !repeat; ++i) {
std::string a0 = non_cover_set_prev[i] + '0';
std::string a1 = non_cover_set_prev[i] + '1';
if (!check_contain(a0, ref)) {
non_cover_set.push_back(a0);
repeat = repeat || check_repeat(a0, max_length);
}
if (!check_contain(a1, ref)) {
non_cover_set.push_back(a1);
repeat = repeat || check_repeat(a1, max_length);
}
}

if (non_cover_set.size() == 0)
break;
non_cover_set.swap(non_cover_set_prev);
}

if (repeat) {
std::cout << -1 << std::endl;
}
for (int i=0; i< non_cover_set_prev.size(); ++i) {
std::cout << non_cover_set_prev[i]  << std::endl;
}
return 0;
}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Result on the second test is 010 and 011

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

Can u please elaborate the logic.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

The main logic of the problem is based on DP and tree traversal

- DP: if a string satisfy the conditions then all of its substrings are. That mean
if you have a string with length l, then the one with length l -1 (without the last character) also satisfy the condition of the problem

- The feasible sets is a tree, and the length of the string indicate the level of the tree, the next level will cover all the length + 1 strings. We can build the tree from the top (level 0), each step we add the leave at the level with with a single character in the set (0, 1 in the binary tree). We then check the feasibility of the node.

- The infinite condition is when we see repeat pattern

if SS exist in the feasible set then SSS, SSSS ... also feasible so we have to check the repeat pattern if any.

Please correct if my intuition is wrong

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.