## Interview Question for Software Engineer / Developers

• 0

Country: United States
Interview Type: Phone Interview

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

``````private static String getLongestSubstringWithNRepeatableChars(String str, int n) {
int startIdx = 0, count = 1;
int bestSize = Integer.MIN_VALUE;
int bestStartIdx = 0;
int bestEndIdx = 0;
int[] arr = new int[256];
for (int i = 0; i < arr.length; i++) {
arr[i] = 0;
}
arr[str.charAt(0)]++;
for (int endIdx = 1; endIdx < str.length(); endIdx++) {
if (arr[str.charAt(endIdx)] == 0) {
count++;
if (count > n) {
char idx = str.charAt(startIdx);
while (count != n) {
arr[str.charAt(startIdx)]--;
startIdx++;
if (arr[idx] == 0) {
count--;
}
}
}
}
arr[str.charAt(endIdx)]++;
int currSize = endIdx - startIdx + 1;
if (currSize >= bestSize) {
bestSize = currSize;
bestStartIdx = startIdx;
bestEndIdx = endIdx;
}
}
return str.substring(bestStartIdx, bestEndIdx + 1);
}``````

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

Like your algorithm: simple, concise and general. However, no vote for you until you put a proper brief description in words of the algorithm.

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

Thanks for the comment. I am lazy and not good in writing a description but I am trying my best:
The algo maintains a sliding window substring that advances from left to right using pointers. The window always maintain the constraint: Only n distinct characters should be present (can repeat and can be in any sequence). The right pointer is always ahead and discovers new chars and increases count. It moves ahead as long as count is less than n since the constraint is valid and the window size is updated. The moment it adds a new char and count is more than n, then the constraint becomes invalid, and we need to move the left pointer to bring it to a valid state. We do this by removing all the chars pointed by the initial state of the left pointer by gradually advancing the left pointer till we get rid of all the chars seen till now and decreases the count pointer. At this point, the constraint is satisfied again since count == n and there are only n type of chars in the window. We again update the window size and the process repeats till we scan the entire length. The left pointer always sees new chars and keeps a count of them and the right pointer erases them and reduces the count and thereby helping to detect the window where the constraint is satisfied. The time complexity is linear since there are two linear sweeps by the left and right pointers. This kind of idea can be applied to the class of problems where it is required to find a longest/shortest substring with specified number and type of chars without considering their sequence of appearance.

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

Pretty straightforward algorithm - keep walking the string, checking for max substring. Each time there's character change, cache that info into temp variable (spNext) so that you can use it later. Running time is O(n).

``````// Max2CharSubstring.cpp
//
// Find the longest sub-string containing at most 2 different
// characters
/////////////////////////////////////////////////////////////
#include <iostream>
#include <string>
using std::cout;
using std::endl;
using std::string;
//
typedef string::size_type sz_type;
//
// Structure to keep track of a starting point of a sub-string
// together with info about which 2 characters it contains
struct StartPoint
{
sz_type index;	// Index in the given string
char cFirst;	// Value of the first character
char cSecond;	// Value of the second character
};
//
//
int main()
{
const string str = "aaaabbbbbaaaaaacccccccccccccccccccccccccccc";
const sz_type n = str.length();
// Error checks
if (n == 0)
{
cout << "Empty string! Exiting ...";
return 1;
}
// Find a character different from the first
char ch = str[0];
sz_type i = 1;
while (i < n && str[i] == ch)
++i;
// Degenerate case
if (i == n)
{
cout << "String contained only one character." << endl;
cout << "\tStarting index =    0" << endl;
cout << "\tSubstring length = " << n << endl;
cout << "\tCharacter = \'" << ch << "\'" << endl;
return 0;
}
// Initialize starting max value to something reasonable
// We use the max value to be a string of lenght 1.
sz_type maxLength = 1;		// Length of the max substring
StartPoint spMax;			// Info about the max substring
spMax.index = 0;
spMax.cFirst = str[0];
// Starting point of the current candidate
StartPoint spCur;
spCur.index = 0;
spCur.cFirst = ch;
spCur.cSecond = ch = str[i];
// Possible starting point of the next candidate
StartPoint spNext;
spNext.index = i;
spCur.cSecond = ch;
//
// Done with initial set up
//
// Loop invariants:
//	ch - value of the previous character
//	spCur  - starting point of the current candidate
//           for max substring
//	spNext - (possible) starting point of the next
//           candidate for max substring
for (++i; i < n; ++i)
{
if (str[i] == ch)
{
// Current substring continues with the same character
// No need to do anything
continue;
}
// Found a different character
ch = str[i];
if (ch == spCur.cFirst || ch == spCur.cSecond)
{
// Current substring continues with the other character
// Only need to update spNext (done below)
}
else
{
// Found a 3rd character => current substring finished
// Check if current sub-string is longer than max
if (i - spCur.index > maxLength)
{
maxLength = i - spCur.index;
spMax = spCur;
}
//
// Start a new current substring from spNext
spCur = spNext;
spCur.cSecond = ch;
}
// Update spNext
spNext.index = i;
spNext.cFirst = ch;
}
// i == n
// Check if current sub-string is longer than max
if (n - spCur.index > maxLength)
{
maxLength = n - spCur.index;
spMax = spCur;
}
cout << "String: " << str << endl;
cout << "\tStarting index = " << spMax.index << endl;
cout << "\tMax sub-string length = " << maxLength << endl;
cout << "\tCharacters = \'" << spMax.cFirst;
cout << "\' and \'" << spMax.cSecond << "\'" << endl;
return 0;
}``````

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

``````import javax.swing.JOptionPane;

public class LongestSubString {

public static void main(String []args)
{
new LongestSubString().displayLongestSubString(JOptionPane.showInputDialog("Enter input String :"));
}

public void displayLongestSubString(String main)
{
StringBuffer sub = new StringBuffer();
StringBuffer max = sub;

for(int i = 0;i < main.length();i++)
{
int []bool = new int[256];
for(int k = 0;k < 256;k++)
bool[k] = 0;
for(int j = i;j < main.length();j++)
{
if(bool[main.charAt(j)] < 2)
{
sub.append(main.charAt(j));
bool[main.charAt(j)]++;
}
else
{

break;
}
}

if(sub.length() > max.length())
max = sub;

sub = new StringBuffer();
}

System.out.println("Longest sub string without any alphabet repeating not more than twice : " + max);
}
}``````

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

int a = 0;
char c ;
StringBuffer sb = new StringBuffer();
loop to iterate the array
for(i= 0 --> length of array)
{
if(i==0)
if(arr[i]==arr[i+1] && arr[i+1]!=arr[i+2])
{
c = arr[i];.
while(i!= arr.length())
{
if(arr[i]!=c)
sb.append(new String(arr[i]));
else
return sb;
}

}
else if((i>0 && (arr[i]==arr[i-1]) || (i>0 && arr[i]==arr[i+1]) ))
{
if(arr[i] == arr[1+1]==arr[i-1] )
a = i+2;
else
{
if(arr[i]!=c)
sb.append(new String(arr[i]));
else
return sb;

}

}

}

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

Dive the whole algorithm in three part first for starting condition and then for the middle values i.e. i+1 ----------> i+n-2 and for the last condition i == length of the array

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

@Deep: It's really hard to read your code without proper formatting. Can you click "Edit" below your post and add "{ { {" before and "}}}" after your code? Also, I recommend replacing tabs with spaces.

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

i do not quite understand the question...what will be the output for abbbccc? bbbccc or bbcc? what abt abbbcccdccb? will it still be bbbccc? if yes then do something like this for 2nd string a=1, b=3, c=3, d=1, c=2, b=1. the two consecutive chars with maximum sum will be the answer.

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

Question is : Find longest sub string without any alphabet repeating not more than twice.

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

It shall be "bbbccc" for "abbbcccdccb".

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

For "abbbcccdccb" there are 2 possible answers -
"bbbccc" or "cccdcc". Essentially the longest substring consisting of 1 or 2 characters.

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.