Google Interview Question for Software Engineer / Developers


Country: India




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

if we can use extra space create suffix tree and the right most suffix in that is the biggest suffix.

- jeff September 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 5 vote

1. find the biggest character in the string O(n)
eg: adecb -->e

2. build a boolean array, which has the length of the string and traverse the string, if the
character is biggest character then its corresponding boolean is true,otherwise false
eg: abcee
F,F,F,T,T

3. find the longest substring which only contains the biggest character O(n)
eg: abceeedcabeeecdd
eee eee
Notes: this step may return multiple substrings


4.compare the next character for the substrings we have in step 3

eg: abceeedcabeeecddeeemfefeeemk
eeed eeec eeem eeem
we compare 'd','c','m', 'm' and get the biggest, and continue to compare the next character
eg: compare 'f' with 'k'

we keep comparing until one of the following case is true

a. there is only one biggest substring
eg 1:
eeemeeekeeez
m k z
-->eeez is the answer
eg 2:eeemeee
m (empty or null)
-->eeem is not the answer, the answer is eeemeee, the returned substring must be a suffix.

c. one of the substrings we compared hits the biggest character

eeemeeemn
m m
since 'm'=='m' we compare the next,
the next character for eeem is 'e', which is the biggest, so we return eeemeeemn.

- vincent September 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I don't understand the boolean array in the second step.

- Anonymous September 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

of coz, you should not understand it, because I suppose to remove it. Sry about it.

- vincent September 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

eg 1:
eeemeeekeeez
m k z
-->eeez is the answer

...

yeah right

- Anonymous September 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice solution. But there is something I do not understand:

how do you compare the characters in step 4. I am asking since I can think of only O(n/2)log(n/2) complexity.
e.g. abanavacam

p.s
In non general case: If you have only 26 symbols you can simply use use an array cnt with size = 26 and keep the indexs of the first elements. This will be constant time and your approach will be O(n). But in general case it seems to me like O(nlogn)

- GKalchev October 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

In "c. one of the substrings we compared hits the biggest character", your result will be inconclusive if there are multiple places where the biggest character is hit. E.g. with "zzzbzzzbzzzbzzzazzzbzzzbzzz", we have multiple strings where zzz is followed by bz, so we have to keep looking at all of these, and keep repeating until we're down to one starting location under consideration, whether the new character in the strings we are considering is a new character or a repeat of the old character.

This means the "we keep comparing until..." step can be repeated O(n) times, making this an O(n^2) algorithm.

- anonymous December 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I am really confused here. How is eee the maximum element when the string contains m,k,z?

- Biru February 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

This is surely not a O(n) algo ...

- Kavish Dwivedi August 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

How about divide and conquer?

Assume the string has length n. Let the string be S. Look at S1 = S(0, \lfloor n/2 \rfloor) and S2 = S(\lfloor n/2 \rfloor + 1, n-1) ..Suffix of S2 = Suffix of S. Suffix of S1 + S2 = Suffix of S.

Find the largest suffix of S1 and S2. Note that the largest suffix will be unique since each suffix has different length. Add S2 to the largest suffix of S1 and compare this newly formed suffix of S with largest suffix of S2. This comparison can be done is O(n) time.

So, our time equation is

T_n = 2 T_n/2 + O(n)... This gives an O(n log n ) solution, Oh well..

- alphalpha October 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I dont think this works. Lets take "babbaa" as an example.

Correct answer should be : bbaa

Follow your algorithm:
1. break babbaa into bab baa
for bab, if we break it, the resulting two substrings are ba and b; thus we need to choose between the two largest suffix bab(ba+b) and b. bab is lexicographicaly larger, so we return bab;

similarly, the maximum suffix of baa is baa. now we compare babbaa and baa, the result is babbaa.

However, the correct answer should be bbaa.

- bg2d January 01, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

suffix array algorithm DC3 runs in O(n) can solve this problem.

- ChenH1989 October 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can someone tell me why this isn't correct?

public String run(String word) {
  String currentPrefix = "";
  String answer = "";

  for (int j = word.size() - 1; j >=0; j++) {
    currentPrefix = word.get(j) + currentPrefix;
    if (answer.isEmpty() || currentPrefix.compareTo(answer) > 0) {
      answer = currentPrefix;
    }
  }
  return answer;
}

- Anonymous September 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I screwed up the decrement of j. Force of habit when typing. Should be j--.

- Anonymous September 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Might be correct. But it is O(n^2).

- Anonymous September 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Search for Maximum Suffix problem on Yahoo and you will get some research papers for doing it in linear time.

- Neeraj Kumar Singh September 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Would they actually ask you to implement the algorithm to construct a suffix trie? Or is implementing the N^2 solution, then discussing the O(N) solution generally sufficient?

- Anonymous September 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

Scan from left to right and find the starting index of lexicographically largest string at each index. Interesting thing is that you could tell the lexicographically largest string at index i, based on the lexicographically greatest string at index i-1 with constant number of comparisons.

If A[i] is the current character and maxlex is the starting index of lexicographically largest string till A[i-1]. It gets a bit trickier when A[i]=A[maxlen].

Could be done in O(n) time and constant space.

- Epic_coder October 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

constant number of comparisons. ?? I don't think so. Can you please elaborate.

- damned November 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

can some one tell me what is "lexicographically largest suffix"

- DarkKnight October 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

If word Y comes after word X in dictionary then Y is lexicographically greater than X.

- Epic_coder October 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

This would work in O(n) time.
Key ideas are

- the answer should start with the largest character
- so search from right to left, remember the index where we encounter
the largest character so far as the running best(=starting point of the max substr)
- then it's all about tie-breaking. when tied, instead of updating the running
best, simply count the offset until tie is broken.
- while tie-breaking, if a even larger character is encountered, update the
running best right away. if the same character is encountered, we do
nothing as the current candidate is always larger.
- last, if tie is not resolved till the end, longer one beats so we can keep the
current best.

#include <stdio.h>
#include <stdlib.h>

void main( int argc, char** argv )
{
    char* s = argv[1];

    int answer = -1;
    int offset = -1;
    int i;
    for( i = 0; i < strlen( s ); i++ )
    {
        if( answer == -1 ||
            s[answer] < s[i] )
        {
            answer = i;
            offset = -1;
        }
        else if( offset >= 0 )
        {
            offset++;
            // we're tie-breaking
            if( s[answer+offset] < s[i] )
            {
                answer = i-offset;
                offset = -1;
            }
            else if( s[answer+offset] > s[i] )
            {
                offset = -1;
            }
        }
        else if( s[answer] == s[i] )
        {
            offset = 0;
        }
    }
    printf( "%d\t%s\n", answer, s+answer );
}

- anonyguru November 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Unless I am mistaken, this should incorrectly print "2 zazz" on input zazazz. If the beginning of the correct string occurs while we're in tie-breaking mode, we won't find it.

- anonymous December 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

map<char, int> m;
for (int i=str.length()-1; i>=0; i--)
      m[str[i]] = i;
int start_pos_of_largest_character = it = (m.end()-1)->second; // 
cout << str.substr(start_pos_of_largest_character) << endl;

- Anonymous August 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

coming from a paper: "A note on a simple computation of the maximal suffix
of a string.pdf" by Zbigniew Adamczyk , Wojciech Ryttera

int ComputeMaxSufPos(string &str)
{
int i = 0, j = 1;
size_t n = str.size();
string sub1, sub2;
while (j < n)
{
int k = 0;
//sub1 = = str.substr;;
//sub2 = str.substr;
while (j + k < n - 1 && str.substr(i + k) == str.substr(j + k))
{
k++;
}
if (str.substr(i + k) < str.substr(j + k))
{
i += (k / abs(j - i) + 1)*(j - i);
j = i + 1;
}
else
{
j = j + k + 1;
}
}

return i;
}

- liang March 31, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

There is a simple/beautiful an algorithm on this problem. Imagine in an interactive game, two opponents A and B work against each other, to find the max suffix of a given string s. Initially A picks suffix s[i..], and B picks suffix s[j..]

i: _____X
j: _____Y

A judge compares two suffix(by matching them) and find there is a mismatch at certain position, as shown in the fig above.

Without loss of generality, we assume X > Y, then B is lost in this round. So he has to improve his solution in order to beat A in next round. If B is smart, he will not pick any suffix at position j, j + 1, ..., until the mismatched position, because s[j..] is beaten by s[i..] and s[j+1..] is beaten by s[i+1..]. So next suffix B will come up is S[k..], k is the position after mismatch..

After couple rounds, either A or B will run out choices. When this happens, the current suffix that the winner holds is the max suffix.

Here is the algorithm in pseudo code:

int i = 0, j = 1, k;
while (i < s.size() && j < s.size()) {
    for (k = 0; i + k < s.size() && j + k < s.size() && s[i + k] == s[j +k]; ++k) { //judge
    }
    if (i + k == s.size()) return j; //A is finally lost
    if (j + k == s.size()) return i; //B is finally lost
    if (s[i + k] > s[j + k]) //B is lost in this round
        j = j + k + 1;
    else //A is lost in this round
        i = i + k + 1;
}

The algorithm is linear because after each round,k possible positions are eliminated from either A, or B.

- Anonymous September 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

There is a simple/beautiful an algorithm on this problem. Imagine in an interactive game, two opponents A and B work against each other, to find the max suffix of a given string s. Initially A picks suffix s[i..], and B picks suffix s[j..]

i: _____X
j: _____Y

A judge compares two suffix(by matching them) and find there is a mismatch at certain position, as shown in the fig above.

Without loss of generality, we assume X > Y, then B is lost in this round. So he has to improve his solution in order to beat A in next round. If B is smart, he will not pick any suffix at position j, j + 1, ..., until the mismatched position, because s[j..] is beaten by s[i..] and s[j+1..] is beaten by s[i+1..]. So next suffix B will come up is S[k..], k is the position after mismatch..

After couple rounds, either A or B will run out choices. When this happens, the current suffix that the winner holds is the max suffix.

Here is the algorithm in pseudo code:

int i = 0, j = 1, k;
while (i < s.size() && j < s.size()) {
    for (k = 0; i + k < s.size() && j + k < s.size() && s[i + k] == s[j +k]; ++k) { //judge
    }
    if (i + k == s.size()) return j; //A is finally lost
    if (j + k == s.size()) return i; //B is finally lost
    if (s[i + k] > s[j + k]) //B is lost in this round
        j = j + k + 1;
    else //A is lost in this round
        i = i + k + 1;
}

The algorithm is linear because after each round,k possible positions are eliminated from either A, or B.

- Xin Wang September 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Can you elaborate your question with an example?

- Anonymous September 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

The question required a O(n) algorithm so we can scan the input only constant times and it is reasonable to think to start the scan from the end. Here is sample code

public static String maxSuffix(String s) {
    if (s == null || s.length() < 2) {
        return s == null ? null : new String(s);
    }   

    char[] a = s.toCharArray();
    int[] M = new int[a.length];
    M[a.length - 1] = a.length - 1;

    for (int i = a.length - 2; i >= 0; i--) {
        if (a[i] >= a[M[i + 1]]) {
            M[i] = i;
        } else {
            M[i] = M[i + 1]; 
        }   
    }   

    return s.substring(M[0], s.length());
}

Where M[i] means the beginning index of the max suffix for sub-string starting at position i, 0 <= i < s.length.

- nixfish October 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is wrong because zazzb => zzb your code returns zazzb

That is, zzb is lexicographically largest suffix of the given string zazzb

- False October 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

I think you can use the failure function from the Knuth Morris Pratt algorithm for this

- Anonymous October 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think you can use a modification of Manacher's algorithm.

Statements like these are pointless. Especially if you yourself are unsure.

Why not put down exactly what you had in mind?

- Anonymous October 08, 2012 | 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