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

- fat0ss August 29, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

There a linear-time algorithm using suffix trees.

- Anonymous June 03, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- gevorgk June 05, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

And your code doesn't fit on a whiteboard.

- Anonymous June 05, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous June 05, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

D_MN straight.. all talk and no code = zippo

- Anonymous June 11, 2010 | Flag
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))
}

- netappreject June 05, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

the above solution will not work

- Anonymous June 05, 2010 | Flag Reply
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 "";
}

- Anonymous June 05, 2010 | Flag Reply
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 "";
}

- gevorgk June 05, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

can you explain your logic

- Anonymous June 08, 2010 | Flag
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.

- Anonymous June 11, 2010 | Flag Reply
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>

- Anonymous June 13, 2010 | Flag Reply
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;
}
}

- Anonymous July 11, 2010 | Flag Reply
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

- fat0ss August 29, 2010 | Flag Reply
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)

- Hinax September 21, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Poonam Pandey November 14, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- kr.ayush998 August 05, 2019 | Flag Reply
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

- Ravi June 03, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous June 04, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)

- Ravi June 04, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous June 11, 2010 | Flag


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