## Google Interview Question for SDE1s

Country: United States

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

``````string max_substr(string str){
vector<pair<int,int>> vec;
char maxx = 'a';
for (int i = 0; i < str.size(); ++i){
maxx = max(maxx, str[i]);
}
vector<pair<int,int>> candidates;
for (int i = 0; i < str.size(); ++i){
if (str[i] == maxx){
candidates.push_back(make_pair(i, i));
}
}
while (candidates.size() > 1){
char maxx = 'a';
for (int i = 0; i < candidates.size(); ++i){
if (candidates[i].second + 1 < str.size()){
maxx = max(maxx, str[candidates[i].second + 1]);
}
}
vector<pair<int, int>> newcan;
for (int i = 0; i < candidates.size(); ++i){
if (candidates[i].second + 1 < str.size() && str[candidates[i].second + 1] == maxx){
newcan.push_back(make_pair(candidates[i].first, candidates[i].second + 1));
}
}
candidates = newcan;
}
return str.substr(candidates[0].first);
}``````

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

O(n) time complexity, O(1) space

``````#include <iostream>
using namespace std;

string FindLargestSubString(string s)
{
int length = s.length();
int i = 0;
int j = i+1;
while(j<length)
{
if(s[j] > s[i])
{
i = j;
j = j+1;
}
else if(s[j] < s[i])
{
j = j+1;
}
else
{
int k = i;
int l = j;
while(l < length)
{
if(s[k] > s[i])
{
i = k;
j = l;
break;
}
else if(s[l] > s[i])
{
i = l;
j = l+1;
break;
}
else if(s[k] > s[l])
{
j = l+1;
break;
}
else if(s[k] < s[l])
{
i = j;
j = l+1;
break;
}
else
{
l++;
k++;
}
}

if(l == length)
{
j = l;
break;
}
}
}
return s.substr(i);
}

int main() {
string s;
cin>>s;
cout<<FindLargestSubString(s);
}``````

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.