## Deshaw Inc Interview Question for Software Engineer / Developers

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

One simplest solution I can think of find longest common substring between S and Reverse (S) and this can be find by using suffix tree in O(n) and O(n^2) from dynamic programming

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

There a linear-time algorithm using suffix trees.

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

It's easy to just say "Suffix tree", O(n), etc. bla-bla-bla. Could you please wirte WORKING solution using Suffix tree ? And please think that you have to do it during interview in 10-15 minutes...

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

And your code doesn't fit on a whiteboard.

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

Even if you wrote really small, you fucked up the first time.

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

D_MN straight.. all talk and no code = zippo

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

Simple soln is :
isPalindrome(char a[], int l, int u){
if(l>u)return 0;
if(a[l] == a[u]
return(palindrome(a, l+1, u-1) + 2)l
else
return max(palindrome(a, l, u-1), palindrome(a, l+1, u))
}

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

the above solution will not work

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

``````std::string largestPalindrome(const std::string& in)
{
using namespace std;

//every element contains length of palindrome
// ending at this index
vector<int> a;
a.resize(in.size());
std::fill(a.begin(), a.end(), 1);

if(in[0] == in[1])
a[1] = 2;
//initialized to 1
for(int i=2; i < a.size();i++)
{
if(in[i]==in[i-1])
a[i]=2;

if(in[i]==in[i-2])
a[i]=3;

if(i-a[i-1]-1 >=0)
if(in[i]==in[i-a[i-1]-1])
a[i]=a[i-1]+2;
}

int pos = 0, max = 0;

for(int i = 0; i < a.size(); ++i )
{
if( a[i] > max )
{
max = a[i];
pos = i;
}
}

if( max > 1 )
{
return in.substr(pos-max+1, max);
}

return "";
}``````

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

``````/// finds largest palindrome which occures in given string
std::string largestPalindrome(const std::string& in)
{
using namespace std;

//every element contains length of palindrome
// ending at this index
vector<int> a;
a.resize(in.size());
std::fill(a.begin(), a.end(), 1);

if(in[0] == in[1])
a[1] = 2;
//initialized to 1
for(int i=2; i < a.size();i++)
{
if(in[i]==in[i-1])
a[i]=2;

if(in[i]==in[i-2])
a[i]=3;

if(i-a[i-1]-1 >=0)
if(in[i]==in[i-a[i-1]-1])
a[i]=a[i-1]+2;
}

int pos = 0, max = 0;

for(int i = 0; i < a.size(); ++i )
{
if( a[i] > max )
{
max = a[i];
pos = i;
}
}

if( max > 1 )
{
return in.substr(pos-max+1, max);
}

return "";
}``````

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

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

possible scenarios in a string:
1) word word word aaabbbccbbbaaa word word otherpalid word shortestpalindrome
2) wordwordwordaaabbbccbbbaaawordwordotherpalidwordshortestpalindrome
3) wordwordwordworDshortestpalindromewordotherpalidwordaaabbbccbbbaaa

Find aaabbccbbbaaa.

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

<pre lang="java" line="1" title="CodeMonkey86418" class="run-this">class LongestPalindrom {
public static void main(String args[]){
String str = "exaaxamsimpleelpmisle";
char[] a = str.toCharArray();
int low=Integer.MAX_VALUE;
int upper=Integer.MIN_VALUE;
for(int i=0;i<str.length();i++){
int start=i;
int end =i;
while(start>=0 && end < str.length()){
if(a[start]==a[end]){
if(end-start>upper-low){
upper=end;
low=start;
}
end++;
start--;
}else{
break;
}

}

}
for(int i=0;i<str.length();i++){
int start=i;
int end =i+1;
while(start>=0 && end < str.length()){
if(a[start]==a[end]){
if(end-start>upper-low){
upper=end;
low=start;
}
end++;
start--;
}else{
break;
}
}

}
for(int i=low;i<=upper;i++){
System.out.print(a[i]);
}
}

}
</pre><pre title="CodeMonkey86418" input="yes">1
2
10
42
11

</pre>

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

LongestPalindrome(char[] input, int len)
{
Int left, right, l, r;
Left = right =l = r = -1;

If(l<2) return;

For(int i=1; i<n;n++)
{
If (input[i] == input[i-1])
{
L = i-1; r=I;
}
Else if(input[i] == input[i-2])
{
l=i-2; r=I;
}

If (l!=-1)
{
While (l >=0 && r <n && a[l]==a[r])
{
l--; r++;
}
}
l++; r--;
If (r-l > right-left)
{
right = r;
left = l;
}
L = r = -1;
}
}

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

One simplest solution I can think of find longest common substring between S and Reverse (S) and this can be find by using suffix tree in O(n) and O(n^2) from dynamic programming

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

Here is my take: The smallest palindrome follows two conditions either a[i] == a[i-1](AA scenario) or a[i] == a[i-2](ABA scenario).
First using the above conditions we can find a minimal size palindrome. expand it on both sides till it follows palindrome property. Compare this expanded palindrome with the global largest palindrome variable, and update the largest palindrome.
Now we can optimise it further by taking analogy from pattern matching. We can calculate the next jump (from where we will start the next find minimal palindrome) while expanding the minimal palindrome itself.
Time-o(nlogn)

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

Use R findPalindrome() fucntion defined in the package BioString.R

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

Can be done in O(n) using Manacher's algorithm.

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

See the code here. .Its a DP solution.. Output comes pretty fast.

``ideone.com/ROMXv``

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

algorithm doesn't look like it's DP. It looks recursive with exponential runtime.

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

It is DP. And it is O(n^2). There are two variables in the recursion which go from 0-n/2 and n/2 to end.. Worst case is n/2 X n/2 which makes it O(n^2)

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

also, you won't be writing that on a whiteboard. It's too much code for even the interviewer to know if the code is right

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.