meh
BAN USER 4of 4 votes
AnswersGiven a current absolute path, e.g., "/usr/bin/mail", and a relative one, e.g, "../../../etc/xyz/../abc" return the absolute path created from the combination of the first two paths. In the example strings, the answer should be "/etc/abc".
 meh in United States Report Duplicate  Flag  PURGE
Facebook Software Engineer / Developer Algorithm  1of 1 vote
AnswersImplement a sorting algorithm for a single linked list.
 meh in United States Report Duplicate  Flag  PURGE
Software Engineer / Developer Sorting  2of 2 votes
AnswersGiven a mapping configuration such as:
 meh in United States
1:a
2:b
...
26:z
And a string like "12632", print the number of different ways you can map such string to alphabet characters.
For example, given "111" the answer is 3 because you can make "aaa", "ak" and "ka" different mappings. However, given "101" the answer is 1 because you can only make "ja" as a possible mapping (01 is not valid). Report Duplicate  Flag  PURGE
Software Engineer / Developer Dynamic Programming  3of 3 votes
AnswersPrint all paths of a binary tree from root to leaf.
 meh in United States
Later, extend the solution to work with graphs, careful attention to cycles which you should print as paths as well (without printing visited nodes twice). Report Duplicate  Flag  PURGE
Facebook Software Engineer / Developer Data Structures  0of 0 votes
AnswersImagine you're designing a Web Service for a phone application that returns a list of suggested Words that may complete a given string the user types.
 meh in United States
For example, if the user writes "ap", a list of suggested words may contain ["apple", "application", "aptitude", ...].
Assume English only words and no misspelling.
I gave a solution with tries and interviewer asked for an alternative solution (I was thinking something along the lines of hashing but time ran out and I couldn't put together anything concrete). I mentioned a couple ways I could optimize my idea, but felt short on that area. For example, ways to return smaller lists, ranking, caching, etc. Report Duplicate  Flag  PURGE
Amazon Software Engineer / Developer Application / UI Design  0of 0 votes
AnswersDetermine if a tree is a valid BST with no duplicated values. (This means that if the binary tree has a duplicated number it should return "invalid" even if it's an actual BST)
 meh in United States
I gave an O(n) solution and interviewer seemed happy with it. Report Duplicate  Flag  PURGE
Amazon Software Engineer / Developer Trees and Graphs
@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 substring 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 substring and it's safe to reset the current stats. Also, start index of substring 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 substring and update the start index so that the solution doesn't include it or forfeit the current substring 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 substring 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;
}

meh
March 24, 2014 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?
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...
<< watchoutwegotabadassoverherememe.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.
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.
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 rightmost 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 leftmost 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;
}

meh
March 23, 2014 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 substring.
After the forloop has ended, is safely to assume that no substring 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;
}

meh
March 23, 2014 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 subsolution 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 bookimplementations 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 :\
 meh March 23, 2014Overall 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 subsolution is visited more than once.
Repangelafiecke, Blockchain Developer at ASU
I am a Data processor at DGS VolMAX. I will also be a controller for the data I use for ...
RepEviePaul, Member Technical Staff at Abs india pvt. ltd.
I am a Studio camera operator from Florida USA.I love to relax n' chill. love when it's cloudy ...
Open Chat in New Window
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 nonobstacle spaces achievable.
Then, for each cell get the biggest of all possible rectangles created by all nonobstacle 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 maxrectangles 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:
 meh March 25, 2014