CareerCup

As everyone else here, I'll assume the problem asks for the maximum rectangle (given by max area) found on the matrix. Also, my approach will only return the area of the max rectangle as opposed to returning the corner indexes (implementing this would be trivial based on my solution):

For each cell, determine the size of the largest row of non-obstacle spaces achievable.

Then, for each cell get the biggest of all possible rectangles created by all non-obstacle cells from the columns that start at the current cell and grow from bottom to top times the minimum of the largest row size (calculated before) of each row in the column.

Example:

0 0 1
0 1 1
1 1 1

Largest rows:
0 0 1
0 1 2
1 2 3

List of all possible max-rectangles per cell:
{ } { } { (1x1) }
{ } { (1x1) } { (2x1), (1x2) }
{ (1x1) } { (2x1), (1x2) } { (3x1), (2x2), (1x3) }

The maximum rectangle area is 4 because at cell (2,2) there exists a column of size 2 with widest achievable row of 2.

Time complexity: O(n^3) // Assuming board is nxn
Space complexity: O(n^2)

Code:

bool board [MAX_WIDTH][MAX_HEIGHT];
int max_rows [MAX_WIDTH][MAX_HEIGHT];

int rect_max_area(bool board [][MAX_HEIGHT], const int width, const int height)
{
    memset(max_rows, 0, width * height * sizeof(int));

    int max_area = 0;
    for (int row_index = 0; row_index < height; row_index++)
        for (int col_index = 0; col_index < width; col_index++)
            if (board[row_index][col_index])
            {
                max_rows[row_index][col_index] = 1;
                if (col_index > 0 && board[row_index][col_index - 1])
                    max_rows[row_index][col_index] +=
                        max_rows[row_index][col_index - 1];

                int height = 1;
                int local_max_area = 0;
                int h_index = row_index;
                int min_width = max_rows[row_index][col_index];
                while (h_index >= 0 && board[h_index][col_index])
                {
                    local_max_area = max(local_max_area, height * min_width);

                    height++;
                    h_index--;
                    min_width = min(min_width, max_rows[h_index][col_index]);
                }

                max_area = max(max_area, local_max_area);
            }

    return max_area;
}

@Mithya Thanks for your observation!! You're right, I totally missed that case. Please take a look at this other solution I'm proposing that doesn't require KMP and still achieves O(|b|) time complexity with O(1) space:

The idea is to keep an index of the start of the sub-string initially pointing to zero and while reading the search string from left to right check:

a) If the counter in origin_stats for the current character is zero that means that current element is not part of a valid sub-string and it's safe to reset the current stats. Also, start index of sub-string can be changed to index + 1.

b) Else if the counter in current_stats for the current character has become zero, then we need to either regain a character with the same value along the current sub-string and update the start index so that the solution doesn't include it or forfeit the current sub-string if we weren't able to find one.

c) Else just decrement the counter in current_stats and see if we have already found all required characters (this is unchanged from my previous solution).

Cool thing about this is that we're now able to determine the start of the valid sub-string whenever one exists. Here's the code:

inline void reset_stats(
    const char origin_stats [],
    const int origin_count,
	char target_stats [],
	int& target_count)
{
	for (int index = 0; index < 26; index++)
		target_stats[index] = origin_stats[index];

	target_count = origin_count;
}

bool is_substr(const string& pattern, const string& search_txt)
{
	if (pattern.length() == 0)
		return true;
	if (pattern.length() > search_txt.length())
		return false;

	int origin_count = pattern.length();

	char origin_stats [26] = { 0 };
	for (int index = 0; index < pattern.length(); index++)
		origin_stats[pattern[index] - 'a']++;

	int current_count;
	char current_stats [26] = { 0 };

	reset_stats(
		origin_stats, origin_count, current_stats, current_count);

    int substr_start = 0;
	for (int index = 0; index < search_txt.length(); index++)
	{
        if (origin_stats[search_txt[index] - 'a'] == 0)
        {
    		reset_stats(
				origin_stats, origin_count, current_stats, current_count);

            substr_start = index + 1;
        }
		else if (current_stats[search_txt[index] - 'a'] == 0)
        {
            while (search_txt[substr_start] != search_txt[index])
            {
                current_stats[search_txt[substr_start] - 'a']++;
                substr_start++;
                current_count++;
            }

            if (substr_start != index)
                substr_start++;
        }
		else
		{
			current_stats[search_txt[index] - 'a']--;
			current_count--;

			if (current_count == 0)
				return true;
		}
	}

	return false;
}

Nope, I remember the answer (which btw, is usually easier to remember the problem than the answer), I just wanted to share the problem with others so that any geek preparing for an interview or just wanting to have some fun solving technical problems has more material.

Does this make no sense now?

No, fortunately my memory can remember things that go beyond the day I'm currently living, so this interview question was from some time ago.

As someone else pointed out, I didn't clearly specify this on the problem statement, sorry about that. The mapping configuration I provided is the only one allowed, but it's definitely more interesting if the problem could allow multiple mappings, will try to adapt my solution for that!

Cheers.

wow, no need to get all crazy with your caps lock dude...
<< watch-out-we-got-a-badass-over-here-meme.png >>

Regarding your question, sorry I assumed everyone is able to "read my mind", that mapping configuration is the only one allowed, but you can definitely complicate the problem more by allowing multiple mappings.

The question is from an actual interview.

Better indentation

count(str): 
	if empty(str): 
		return 1

	result := 0
	if valid_map(str[-1]):
		result := result + count(str[:-1])
	if str.length > 1 and valid_map(str[-2]):
		result := result + count(str[:-2])
	return result

Btw, this is the recursive approach I used:

count(str):
if empty(str):
return 1
result := 0
if valid_map(str[-1]):
result := result + count(str[:-1])
if str.length > 1 and valid_map(str[-2]):
result := result + count(str[:-2])
return result

Based on this recursive formula, DP can be easily implemented by storing the last two previous solutions for n - 1 and n - 2 (like Fibonacci sequence) so that memory is constant and running time is linear.

typo of typo (shit):

Should return true.

typo:

Instead of

return parent->value;

It should be

predecessor = parent->value;
return false;

The question doesn't specify, but I'll assume that you receive a pointer to the root of the BST and a number whose predecessor wants to be found.

The idea is to try and search for the right-most child of the left branch of the node containing the given number (you'll have to search for that node first), if the node doesn't have a left branch, then you go up in the tree until you find the first parent node with smaller or equal value of the number. If no parent node meets that condition then there is no predecessor number which may happen iff the node containing the number is the left-most node of the tree.

Implementation is an iterative approach since recursive one needs to handle a few extra cases.

bool try_get_predecessor(TreeNode* root, int number, int& predecessor)
{
    if (root == NULL)
    	return false;

    stack<TreeNode*> previous;
    TreeNode* current = root;

    while (current != NULL)
    {
        if (current->value == number)
        {
            if (current->left == NULL)
            {
                if (previous.empty())
    				return false;

                TreeNode* parent = previous.top();
                while (!previous.empty() && parent->value > number)
                {
                    previous.pop();
                    parent = previous.top();
                }

                if (parent->value > number)
    				return false;

                return parent->value;
            }
            else
            {
                TreeNode* largest_pre = current->left;
                TreeNode* next_pre = largest_pre;
                while (next_pre != NULL)
                {
                    largest_pre = next_pre;
                    next_pre = next_pre->right;
                }

                return largest_pre->value;
            }
        }

        previous.push(current);

        if (current->value > number)
            current = current->left;
        else
            current = current->right;
    }

    return false;
}

Initialize an array of 26 slots each with the number of times every character appears on string a and then create a copy for such array.

For each character in string b, check if the count on the previously copied array is zero, if so reset the copied array to its original status. Otherwise, decrement the counter and check if all items in the array are now zero, if so, you've found a valid sub-string.

After the for-loop has ended, is safely to assume that no sub-string exists in b.

Time complexity: O(|b|)
Space complexity: O(1)

inline void reset_stats(
    const char origin_stats [],
	const int origin_count,
	char target_stats [],
	int& target_count)
{
	for (int index = 0; index < 26; index++)
		target_stats[index] = origin_stats[index];

	target_count = origin_count;
}

bool is_substr(const string& pattern, const string& search_txt)
{
	if (pattern.length() == 0)
		return true;
	if (pattern.length() > search_txt.length())
		return false;

	int origin_count = pattern.length();

	char origin_stats [26] = { 0 };
	for (int index = 0; index < pattern.length(); index++)
		origin_stats[pattern[index] - 'a']++;

	int current_count;
	char current_stats [26] = { 0 };

	reset_stats(
		origin_stats, origin_count, current_stats, current_count);

	for (int index = 0; index < search_txt.length(); index++)
	{
		if (current_stats[search_txt[index] - 'a'] == 0)
			reset_stats(
				origin_stats, origin_count, current_stats, current_count);
		else
		{
			current_stats[search_txt[index] - 'a']--;
			current_count--;

			if (current_count == 0)
				return true;
		}
	}

	return false;
}

I don't understand your question, however, I can say that { 0 : a } is an invalid mapping. Therefore "10" can only be mapped as the letter j given that zero maps to no character.

yeah... so?

Maybe I didn't understand your solution, but running your pseudocode for 101 doesn't work:

. First level of recursion x = 0
. Take out "10" from the original string and increment x by one plus the recursive solution of '1' which is 1, so x is now 2.
. Take out "1" and solve recursively for "01", this is an invalid sub-solution so you should prune the recursive branch at this time, however, your algorithm continues the search for '0' and '1' (given that '01' fails to be considered a valid mapping) yielding 3 as the answer to the first level of recursion.
. Since 3 > 2, your algo returns 3 as the answer.

As I mentioned in the problem statement, answer should be 1.

Also, base case should be 1. According to the interviewer the empty string should return 1 as it is by itself a valid mapping.

And if you meant "elsewhere" as in "this is a VERY generic / simple question whose answer could be found almost anywhere", again, sorry about that. I posted this question not because I needed an answer but just as a way to say "hey, they're still asking this kind of questions in the interviews, so you better take a quick look at them since most book-implementations of the sorting algorithms work on arrays". But maybe I should only post hard / interesting questions on this website to avoid swamping readers, so yeah... sorry about that :-\

My bad, I didn't check for duplicates before posting this, truly sorry. Don't know how to delete this question, though.

This was an actual interview I got and I wrote myself the problem statement, the fact that it's similar to another question you've seen is merely a coincidence.

And yet, at the end of the day you'll have to take my word for it... that's career cup's way.

Overall looks pretty good, thanks for this solution! Just a couple of questions:

In a1, shouldn't you also consider all i's that have pattern[j] == str[i]? Such as

k = i + 1
f(i, j) = f(i, j + 1)
while k < m and (pattern[j] == '.' or pattern[j] == str[i]):
f(i, j) = f(i, j) or f(k, j + 1)
k = k + 1

Which makes time complexity O(m^2 * n) without finding all occurrences.

and in 8, I'm not sure why 0 < len <= str.length() gives you all possible positions, I believe this value is within the order of O(m^2), i.e., all 0 <= i <= j < m for str[i:j], so for getting this particular answer it would require you O(m^4 * n) time, right?

Finally, I may be wrong on this, but I believe that for this problem you can do fine with just recursion and backtracking (no DP), since no sub-solution is visited more than once.