Dobuki Studio Interview Question
Game ProgrammersCountry: United States
public static String findSubstring(String input){
String substring="";
for(int i=0; i<input.length(); i++){
String possibleSubstring="";
char c=input.charAt(i);
int j=input.indexOf(c,i+1);
if( j>0){
int k=0;
while(j+k<input.length() && input.charAt(i+k)==input.charAt(j+k) ){
possibleSubstring+=input.charAt(i+k++);
}
}
if( possibleSubstring.length()>substring.length() ){
substring=possibleSubstring;
}
}
return substring;
}
Nice one but
int j=input.indexOf(c,i+1);
returns the first substring occurrence
so for example "Today is a good day to sing and toddle" wouldn't work because 'T' of "Today" looks at 't' of "to" and not 't' of "toddle"
@manuelcastroh, I have updated your method
public static String findSubstring(String input){
String substring="";
for(int i=0; i<input.length(); i++){
String possibleSubstring="";
char c=input.charAt(i);
int j=input.indexOf(c,i+1);
while( j>0){
int k=0;
while(j+k<input.length() && input.charAt(i+k)==input.charAt(j+k) ){
possibleSubstring+=input.charAt(i+k++);
}
if( possibleSubstring.length()>substring.length() ){
substring=possibleSubstring;
//System.out.println(substring);
}
possibleSubstring="";
j=input.indexOf(c,j+1);
}
}
return substring;
}
function longestSubstring($S) {
$L = [];
$z = 0;
$ret = [];
$m = strlen($S) - 1;
$n = strlen($S);
for($i=0; $i< $m; ++$i) {
for($j=$i+1; $j< $n; ++$j) {
if($S[$i] === $S[$j]) {
if($i === 0 || $j === 0) {
$L[$i][$j] = 1;
} else {
$L[$i][$j] = $L[$i-1][$j-1] + 1;
}
if($L[$i][$j] >= $z) {
if($L[$i][$j] > $z) {
$z = $L[$i][$j];
$ret = [];
}
$ret[] = substr($S,$i-$z+1,$z);
}
} else {
$L[$i][$j] = 0;
}
}
}
//print_r($L);
return $ret;
}
var_dump(longestSubstring("hello, mr. yellow")); // "ello"
var_dump(longestSubstring("today is a good time to sing and toddle")); // "tod", "d t", " to"
Finds *all* the longest substrings.
O(n^2). I don't think you can solve it any faster than that.
If you just did it brute force it would take you O(n^3) but you can do better.
Looks like a job for dynamic programming. Its dynamic and its programming and it seems to be what employers want candidates to demonstrate a mastery of, though I don’t think it rarely if ever gets used in my experience. Dynamic programming should take O(n^2) + O(n) space;
Let's consider a matrix m[x][y] let it be the number of matches you get starting when s[x] is aligned with s[y] going backward in the strings. If x == y everything matches back to the start of the string and this does not count. The case where x1 == y1 is the same as y1 == x2 so we need not consider both the cells above the diagonal or below it. Just choose one triangle to consider;
If(s[x] == s[y]) then m[x][y] = m[x-1][y-1] + 1;
Else m[x][y] = 0 ;
If we compute it in the right order, we can reuse matrix rows, only keeping 2 of them.
We there for index like so: m[x][y] -> m[x][y%2]
So we get something like this:
#include <cstdlib>
using namespace std;
#include <string.h>
template<class DATA> // this is a handy little class for 2 d matrixes
class Two_D_MTX
{
public:
Two_D_MTX(int x,int y)
{
data = new DATA[x*y];
max_x = x;
max_y = y;
}
~Two_D_MTX()
{
delete[] data;
}
DATA *operator[](int x)
{
return &data[x * max_y];
}
private:
DATA *data;
int max_x;
int max_y;
};
int dynamic_repetition(char * s)
{
int l = strlen(s);
if(l < 2) return 0;
if(1 == 2) return s[0] == s[1]? 1:2;
Two_D_MTX<int> m(l,2);
int best = 0;
for(int y = 1; y < l; y++)
{
m[0][y%2] = (s[0] == s[y])?1:0;
for(int x = 1; x < y; x++)
{
if(s[x] != s[y])
{
m[x][y%2] = 0;
}
else // s[x] == s[y]
{
int temp = 1 + m[x-1][(y-1)%2];
m[x][y%2] = temp;
best = (temp > best)? temp: best; // max(temp,best);
}
}
}
return best;
}
int main(int argc, char** argv) {
char s[] = "abcabdsetgddfgsfdgsabcsd";
int out = dynamic_repetition(s);
return 0;
}
You might be able to do better sorting something called a prefix array though I am not quite sure how to analyze this.
I will try this out with some big examples and get back to you all.
Actually I meant suffix array though prefix array might do as well. While I am still uncertain if the big O time for constructing a properly sorted suffix array would be n log n or n^2 log n it looks like the search to find the longest match would take O(n^2) so why bother.
Still you might want to check out suffix and prefix arrays for future reference.
In Java:
- Minghao Liu May 20, 2015