Interview Question for Software Engineer / Developers


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);
    }

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

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

- cristian.botau November 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- BoredCoder November 18, 2012 | Flag
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;
}

- czpete425 November 14, 2012 | Flag Reply
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);
		}
}

- Buzz_Lightyear November 14, 2012 | Flag Reply
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;

}


}


}

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

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

- Deep November 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- czpete425 November 15, 2012 | Flag
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.

- The Artist November 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Buzz_Lightyear November 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It shall be "bbbccc" for "abbbcccdccb".

- fz November 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- czpete425 November 15, 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