How can you find all unbalanced parens in a string in linear time with constant memory?
$begingroup$
I was given the following problem during an interview:
Gives a string which contains some mixture of parens (not brackets or braces-- only parens) with other alphanumeric characters, identify all parens that have no matching paren.
For example, in the string ")(ab))", indices 0 and 5 contain parens that have no matching paren.
I put forward a working O(n) solution using O(n) memory, using a stack and going through the string once adding parens to the stack and removing them from the stack whenever I encountered a closing paren and the top of the stack contained an opening paren.
Afterwards, the interviewer noted that the problem could be solved in linear time with constant memory (as in, no additional memory usage besides what's taken up by the input.)
I asked how and she said something about going through the string once from the left identifying all open parens, and then a second time from the right identifying all close parens....or maybe it was the other way around. I didn't really understand and didn't want to ask her to hand-hold me through it.
Can anyone clarify the solution she suggested?
algorithms
$endgroup$
add a comment |
$begingroup$
I was given the following problem during an interview:
Gives a string which contains some mixture of parens (not brackets or braces-- only parens) with other alphanumeric characters, identify all parens that have no matching paren.
For example, in the string ")(ab))", indices 0 and 5 contain parens that have no matching paren.
I put forward a working O(n) solution using O(n) memory, using a stack and going through the string once adding parens to the stack and removing them from the stack whenever I encountered a closing paren and the top of the stack contained an opening paren.
Afterwards, the interviewer noted that the problem could be solved in linear time with constant memory (as in, no additional memory usage besides what's taken up by the input.)
I asked how and she said something about going through the string once from the left identifying all open parens, and then a second time from the right identifying all close parens....or maybe it was the other way around. I didn't really understand and didn't want to ask her to hand-hold me through it.
Can anyone clarify the solution she suggested?
algorithms
$endgroup$
$begingroup$
We may need some clarification from you first. Is the first parens or the second parens in "(()" considered unbalanced? Is the last parens or the second to last parens in "())" considered unbalanced? Or is it enough to identify any set of parens with least cardinality such that removing them will leave the remaining parens balanced? Or something else? Or is this part of the interview so that an answer can just put forward any justifiable specification?
$endgroup$
– Apass.Jack
4 hours ago
$begingroup$
I would say it doesn't matter, up to you. Remove any set that leaves the remainder balanced.
$endgroup$
– temporary_user_name
4 hours ago
2
$begingroup$
Then remove them all ;P
$endgroup$
– Veedrac
4 hours ago
add a comment |
$begingroup$
I was given the following problem during an interview:
Gives a string which contains some mixture of parens (not brackets or braces-- only parens) with other alphanumeric characters, identify all parens that have no matching paren.
For example, in the string ")(ab))", indices 0 and 5 contain parens that have no matching paren.
I put forward a working O(n) solution using O(n) memory, using a stack and going through the string once adding parens to the stack and removing them from the stack whenever I encountered a closing paren and the top of the stack contained an opening paren.
Afterwards, the interviewer noted that the problem could be solved in linear time with constant memory (as in, no additional memory usage besides what's taken up by the input.)
I asked how and she said something about going through the string once from the left identifying all open parens, and then a second time from the right identifying all close parens....or maybe it was the other way around. I didn't really understand and didn't want to ask her to hand-hold me through it.
Can anyone clarify the solution she suggested?
algorithms
$endgroup$
I was given the following problem during an interview:
Gives a string which contains some mixture of parens (not brackets or braces-- only parens) with other alphanumeric characters, identify all parens that have no matching paren.
For example, in the string ")(ab))", indices 0 and 5 contain parens that have no matching paren.
I put forward a working O(n) solution using O(n) memory, using a stack and going through the string once adding parens to the stack and removing them from the stack whenever I encountered a closing paren and the top of the stack contained an opening paren.
Afterwards, the interviewer noted that the problem could be solved in linear time with constant memory (as in, no additional memory usage besides what's taken up by the input.)
I asked how and she said something about going through the string once from the left identifying all open parens, and then a second time from the right identifying all close parens....or maybe it was the other way around. I didn't really understand and didn't want to ask her to hand-hold me through it.
Can anyone clarify the solution she suggested?
algorithms
algorithms
asked 5 hours ago
temporary_user_nametemporary_user_name
1526
1526
$begingroup$
We may need some clarification from you first. Is the first parens or the second parens in "(()" considered unbalanced? Is the last parens or the second to last parens in "())" considered unbalanced? Or is it enough to identify any set of parens with least cardinality such that removing them will leave the remaining parens balanced? Or something else? Or is this part of the interview so that an answer can just put forward any justifiable specification?
$endgroup$
– Apass.Jack
4 hours ago
$begingroup$
I would say it doesn't matter, up to you. Remove any set that leaves the remainder balanced.
$endgroup$
– temporary_user_name
4 hours ago
2
$begingroup$
Then remove them all ;P
$endgroup$
– Veedrac
4 hours ago
add a comment |
$begingroup$
We may need some clarification from you first. Is the first parens or the second parens in "(()" considered unbalanced? Is the last parens or the second to last parens in "())" considered unbalanced? Or is it enough to identify any set of parens with least cardinality such that removing them will leave the remaining parens balanced? Or something else? Or is this part of the interview so that an answer can just put forward any justifiable specification?
$endgroup$
– Apass.Jack
4 hours ago
$begingroup$
I would say it doesn't matter, up to you. Remove any set that leaves the remainder balanced.
$endgroup$
– temporary_user_name
4 hours ago
2
$begingroup$
Then remove them all ;P
$endgroup$
– Veedrac
4 hours ago
$begingroup$
We may need some clarification from you first. Is the first parens or the second parens in "(()" considered unbalanced? Is the last parens or the second to last parens in "())" considered unbalanced? Or is it enough to identify any set of parens with least cardinality such that removing them will leave the remaining parens balanced? Or something else? Or is this part of the interview so that an answer can just put forward any justifiable specification?
$endgroup$
– Apass.Jack
4 hours ago
$begingroup$
We may need some clarification from you first. Is the first parens or the second parens in "(()" considered unbalanced? Is the last parens or the second to last parens in "())" considered unbalanced? Or is it enough to identify any set of parens with least cardinality such that removing them will leave the remaining parens balanced? Or something else? Or is this part of the interview so that an answer can just put forward any justifiable specification?
$endgroup$
– Apass.Jack
4 hours ago
$begingroup$
I would say it doesn't matter, up to you. Remove any set that leaves the remainder balanced.
$endgroup$
– temporary_user_name
4 hours ago
$begingroup$
I would say it doesn't matter, up to you. Remove any set that leaves the remainder balanced.
$endgroup$
– temporary_user_name
4 hours ago
2
2
$begingroup$
Then remove them all ;P
$endgroup$
– Veedrac
4 hours ago
$begingroup$
Then remove them all ;P
$endgroup$
– Veedrac
4 hours ago
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Since we can just ignore all alphanumeric characters, we will assume the string contains only parentheses from now on. As in the question, there is only one kind of parenthesis, "()".
If we keep removing balanced parentheses until no more balanced parentheses can be removed, all remaining parentheses must look like like "))…)((…(", which are all unbalanced parentheses. This observation suggests that we should find first that turning point, before which we have unbalanced closing parentheses only and after which we have unbalanced opening parentheses only.
Here is the algorithm.
Let $arr$ be the string, whose size is $n$.
Set $p=0$, $m=0$, $c=0$. Iterate $j$ from 0 to $n-1$ inclusively. For each $j$ do the following.
- check the $j$-th character of $arr$. If it is opening parenthesis, subtract 1 from $c$; otherwise, add 1 to $c$.
- If $c$ is bigger than $m$, set $p=j$ and $m=c$.
Now $p$ is the index of the turning point.
Let us find all unbalanced closing parentheses. Reset $m=0$, $c=0$. Iterate $j$ from 0 to $p$ inclusively. For each $j$ do the following.
- check the $j$-th character of $arr$. If it is opening parenthesis, subtract 1 from $c$; otherwise, add 1 to $c$.
- If $c$ is bigger than $m$, set $m=c$. Output the $j$-th character of $arr$ as an unbalanced closing parenthesis.
Let us find all unbalanced opening parentheses. Reset $m=0$, $c=0$. Iterate $j$ from $n-1$ to $p+1$ inclusively. For each $j$ do the following.
- check the $j$-th character of $arr$. If it is closing parenthesis, subtract 1 from $c$; otherwise, add 1 to $c.$
- If $c$ is bigger than $m$, set $m=c$. Output the $j$-th character of $arr$ as an unbalanced opening parenthesis.
It is clear that the algorithm runs in $O(n)$ time and $O(1)$ auxiliary memory and $O(u)$ output memory, where $u$ is the number of unbalanced parentheses.
Exercise 1. Show that the above algorithm is correct.
Problem 1. Can we generalize the algorithm to the case when the string contains two kinds of parentheses such as "()"? We have to determine how to recognize and treat the new situation, the interleaving case, "([)]".
$endgroup$
$begingroup$
Lol, exercise 1 and problem 1, cute. The logic of the algorithm you've described is surprisingly hard to visualize. I would have to code this out tomorrow to get it.
$endgroup$
– temporary_user_name
1 hour ago
$begingroup$
It looks like I missed the rather obvious but most important explanation. The logic is, in fact, very simple. First, we output each extra opening parenthesis. Once we have passed the turning point, we output each extra closing parenthesis. Done.
$endgroup$
– Apass.Jack
1 hour ago
add a comment |
$begingroup$
Since this comes from a programming background and not a theoretical computer science exercise, I assume that it takes $O(1)$ memory to store an index into the string. In theoretical computer science, this would mean using the RAM model; with Turing machines you couldn't do this and you'd need $Theta(log(n))$ memory to store an index into a string of length $n$.
You can keep the basic principle of the algorithm that you used. You missed an opportunity for a memory optimization.
using a stack and going through the string once adding parens to the stack and removing them from the stack whenever I encountered a closing paren and the top of the stack contained an opening paren
So what does this stack contain? It's never going to contain ()
(an opening parenthesis followed by a closing parenthesis), since whenever the )
appear you pop the (
instead of pushing the )
. So the stack is always of the form )…)(…(
— a bunch of closing parentheses followed by a bunch of opening parentheses.
You don't need a stack to represent this. Just remember the number of closing parentheses and the number of opening parentheses.
If you process the string from left to right, using these two counters, what you have at the end is the number of mismatched closing parentheses and the number of mismatched opening parentheses.
If you want to report the positions of the mismatched parentheses at the end, you'll need to remember the position of each parenthesis. That would require $Theta(n)$ memory in the worst case. But you don't need to wait until the end to produce output. As soon as you find a mismatched closing parenthesis, you know that it's mismatched, so output it now. And then you aren't going to use the number of mismatched closing parentheses for anything, so just keep a counter of unmatched opening parentheses.
In summary: process the string from left to right. Maintain a counter of unmatched opening parentheses. If you see an opening parenthesis, increment the counter. If you see a closing parenthesis and the counter is nonzero, decrement the counter. If you see a closing parenthesis and the counter is zero, output the current index as a mismatched closing parenthesis.
The final value of the counter is the number of mismatched opening parentheses, but this doesn't give you their position. Notice that the problem is symmetric. To list the positions of mismatched opening parentheses, just run the algorithm in the opposite direction.
Exercise 1: write this down in a formal notation (math, pseudocode or your favorite programming language).
Exercise 2: convince yourself that this is the same algorithm as Apass.Jack, just explained differently.
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "419"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
var $window = $(window),
onScroll = function(e) {
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom)) {
StackExchange.using('gps', function() { StackExchange.gps.track('embedded_signup_form.view', { location: 'question_page' }); });
$window.unbind('scroll', onScroll);
}
};
$window.on('scroll', onScroll);
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f103018%2fhow-can-you-find-all-unbalanced-parens-in-a-string-in-linear-time-with-constant%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Since we can just ignore all alphanumeric characters, we will assume the string contains only parentheses from now on. As in the question, there is only one kind of parenthesis, "()".
If we keep removing balanced parentheses until no more balanced parentheses can be removed, all remaining parentheses must look like like "))…)((…(", which are all unbalanced parentheses. This observation suggests that we should find first that turning point, before which we have unbalanced closing parentheses only and after which we have unbalanced opening parentheses only.
Here is the algorithm.
Let $arr$ be the string, whose size is $n$.
Set $p=0$, $m=0$, $c=0$. Iterate $j$ from 0 to $n-1$ inclusively. For each $j$ do the following.
- check the $j$-th character of $arr$. If it is opening parenthesis, subtract 1 from $c$; otherwise, add 1 to $c$.
- If $c$ is bigger than $m$, set $p=j$ and $m=c$.
Now $p$ is the index of the turning point.
Let us find all unbalanced closing parentheses. Reset $m=0$, $c=0$. Iterate $j$ from 0 to $p$ inclusively. For each $j$ do the following.
- check the $j$-th character of $arr$. If it is opening parenthesis, subtract 1 from $c$; otherwise, add 1 to $c$.
- If $c$ is bigger than $m$, set $m=c$. Output the $j$-th character of $arr$ as an unbalanced closing parenthesis.
Let us find all unbalanced opening parentheses. Reset $m=0$, $c=0$. Iterate $j$ from $n-1$ to $p+1$ inclusively. For each $j$ do the following.
- check the $j$-th character of $arr$. If it is closing parenthesis, subtract 1 from $c$; otherwise, add 1 to $c.$
- If $c$ is bigger than $m$, set $m=c$. Output the $j$-th character of $arr$ as an unbalanced opening parenthesis.
It is clear that the algorithm runs in $O(n)$ time and $O(1)$ auxiliary memory and $O(u)$ output memory, where $u$ is the number of unbalanced parentheses.
Exercise 1. Show that the above algorithm is correct.
Problem 1. Can we generalize the algorithm to the case when the string contains two kinds of parentheses such as "()"? We have to determine how to recognize and treat the new situation, the interleaving case, "([)]".
$endgroup$
$begingroup$
Lol, exercise 1 and problem 1, cute. The logic of the algorithm you've described is surprisingly hard to visualize. I would have to code this out tomorrow to get it.
$endgroup$
– temporary_user_name
1 hour ago
$begingroup$
It looks like I missed the rather obvious but most important explanation. The logic is, in fact, very simple. First, we output each extra opening parenthesis. Once we have passed the turning point, we output each extra closing parenthesis. Done.
$endgroup$
– Apass.Jack
1 hour ago
add a comment |
$begingroup$
Since we can just ignore all alphanumeric characters, we will assume the string contains only parentheses from now on. As in the question, there is only one kind of parenthesis, "()".
If we keep removing balanced parentheses until no more balanced parentheses can be removed, all remaining parentheses must look like like "))…)((…(", which are all unbalanced parentheses. This observation suggests that we should find first that turning point, before which we have unbalanced closing parentheses only and after which we have unbalanced opening parentheses only.
Here is the algorithm.
Let $arr$ be the string, whose size is $n$.
Set $p=0$, $m=0$, $c=0$. Iterate $j$ from 0 to $n-1$ inclusively. For each $j$ do the following.
- check the $j$-th character of $arr$. If it is opening parenthesis, subtract 1 from $c$; otherwise, add 1 to $c$.
- If $c$ is bigger than $m$, set $p=j$ and $m=c$.
Now $p$ is the index of the turning point.
Let us find all unbalanced closing parentheses. Reset $m=0$, $c=0$. Iterate $j$ from 0 to $p$ inclusively. For each $j$ do the following.
- check the $j$-th character of $arr$. If it is opening parenthesis, subtract 1 from $c$; otherwise, add 1 to $c$.
- If $c$ is bigger than $m$, set $m=c$. Output the $j$-th character of $arr$ as an unbalanced closing parenthesis.
Let us find all unbalanced opening parentheses. Reset $m=0$, $c=0$. Iterate $j$ from $n-1$ to $p+1$ inclusively. For each $j$ do the following.
- check the $j$-th character of $arr$. If it is closing parenthesis, subtract 1 from $c$; otherwise, add 1 to $c.$
- If $c$ is bigger than $m$, set $m=c$. Output the $j$-th character of $arr$ as an unbalanced opening parenthesis.
It is clear that the algorithm runs in $O(n)$ time and $O(1)$ auxiliary memory and $O(u)$ output memory, where $u$ is the number of unbalanced parentheses.
Exercise 1. Show that the above algorithm is correct.
Problem 1. Can we generalize the algorithm to the case when the string contains two kinds of parentheses such as "()"? We have to determine how to recognize and treat the new situation, the interleaving case, "([)]".
$endgroup$
$begingroup$
Lol, exercise 1 and problem 1, cute. The logic of the algorithm you've described is surprisingly hard to visualize. I would have to code this out tomorrow to get it.
$endgroup$
– temporary_user_name
1 hour ago
$begingroup$
It looks like I missed the rather obvious but most important explanation. The logic is, in fact, very simple. First, we output each extra opening parenthesis. Once we have passed the turning point, we output each extra closing parenthesis. Done.
$endgroup$
– Apass.Jack
1 hour ago
add a comment |
$begingroup$
Since we can just ignore all alphanumeric characters, we will assume the string contains only parentheses from now on. As in the question, there is only one kind of parenthesis, "()".
If we keep removing balanced parentheses until no more balanced parentheses can be removed, all remaining parentheses must look like like "))…)((…(", which are all unbalanced parentheses. This observation suggests that we should find first that turning point, before which we have unbalanced closing parentheses only and after which we have unbalanced opening parentheses only.
Here is the algorithm.
Let $arr$ be the string, whose size is $n$.
Set $p=0$, $m=0$, $c=0$. Iterate $j$ from 0 to $n-1$ inclusively. For each $j$ do the following.
- check the $j$-th character of $arr$. If it is opening parenthesis, subtract 1 from $c$; otherwise, add 1 to $c$.
- If $c$ is bigger than $m$, set $p=j$ and $m=c$.
Now $p$ is the index of the turning point.
Let us find all unbalanced closing parentheses. Reset $m=0$, $c=0$. Iterate $j$ from 0 to $p$ inclusively. For each $j$ do the following.
- check the $j$-th character of $arr$. If it is opening parenthesis, subtract 1 from $c$; otherwise, add 1 to $c$.
- If $c$ is bigger than $m$, set $m=c$. Output the $j$-th character of $arr$ as an unbalanced closing parenthesis.
Let us find all unbalanced opening parentheses. Reset $m=0$, $c=0$. Iterate $j$ from $n-1$ to $p+1$ inclusively. For each $j$ do the following.
- check the $j$-th character of $arr$. If it is closing parenthesis, subtract 1 from $c$; otherwise, add 1 to $c.$
- If $c$ is bigger than $m$, set $m=c$. Output the $j$-th character of $arr$ as an unbalanced opening parenthesis.
It is clear that the algorithm runs in $O(n)$ time and $O(1)$ auxiliary memory and $O(u)$ output memory, where $u$ is the number of unbalanced parentheses.
Exercise 1. Show that the above algorithm is correct.
Problem 1. Can we generalize the algorithm to the case when the string contains two kinds of parentheses such as "()"? We have to determine how to recognize and treat the new situation, the interleaving case, "([)]".
$endgroup$
Since we can just ignore all alphanumeric characters, we will assume the string contains only parentheses from now on. As in the question, there is only one kind of parenthesis, "()".
If we keep removing balanced parentheses until no more balanced parentheses can be removed, all remaining parentheses must look like like "))…)((…(", which are all unbalanced parentheses. This observation suggests that we should find first that turning point, before which we have unbalanced closing parentheses only and after which we have unbalanced opening parentheses only.
Here is the algorithm.
Let $arr$ be the string, whose size is $n$.
Set $p=0$, $m=0$, $c=0$. Iterate $j$ from 0 to $n-1$ inclusively. For each $j$ do the following.
- check the $j$-th character of $arr$. If it is opening parenthesis, subtract 1 from $c$; otherwise, add 1 to $c$.
- If $c$ is bigger than $m$, set $p=j$ and $m=c$.
Now $p$ is the index of the turning point.
Let us find all unbalanced closing parentheses. Reset $m=0$, $c=0$. Iterate $j$ from 0 to $p$ inclusively. For each $j$ do the following.
- check the $j$-th character of $arr$. If it is opening parenthesis, subtract 1 from $c$; otherwise, add 1 to $c$.
- If $c$ is bigger than $m$, set $m=c$. Output the $j$-th character of $arr$ as an unbalanced closing parenthesis.
Let us find all unbalanced opening parentheses. Reset $m=0$, $c=0$. Iterate $j$ from $n-1$ to $p+1$ inclusively. For each $j$ do the following.
- check the $j$-th character of $arr$. If it is closing parenthesis, subtract 1 from $c$; otherwise, add 1 to $c.$
- If $c$ is bigger than $m$, set $m=c$. Output the $j$-th character of $arr$ as an unbalanced opening parenthesis.
It is clear that the algorithm runs in $O(n)$ time and $O(1)$ auxiliary memory and $O(u)$ output memory, where $u$ is the number of unbalanced parentheses.
Exercise 1. Show that the above algorithm is correct.
Problem 1. Can we generalize the algorithm to the case when the string contains two kinds of parentheses such as "()"? We have to determine how to recognize and treat the new situation, the interleaving case, "([)]".
edited 1 hour ago
answered 2 hours ago
Apass.JackApass.Jack
8,3311633
8,3311633
$begingroup$
Lol, exercise 1 and problem 1, cute. The logic of the algorithm you've described is surprisingly hard to visualize. I would have to code this out tomorrow to get it.
$endgroup$
– temporary_user_name
1 hour ago
$begingroup$
It looks like I missed the rather obvious but most important explanation. The logic is, in fact, very simple. First, we output each extra opening parenthesis. Once we have passed the turning point, we output each extra closing parenthesis. Done.
$endgroup$
– Apass.Jack
1 hour ago
add a comment |
$begingroup$
Lol, exercise 1 and problem 1, cute. The logic of the algorithm you've described is surprisingly hard to visualize. I would have to code this out tomorrow to get it.
$endgroup$
– temporary_user_name
1 hour ago
$begingroup$
It looks like I missed the rather obvious but most important explanation. The logic is, in fact, very simple. First, we output each extra opening parenthesis. Once we have passed the turning point, we output each extra closing parenthesis. Done.
$endgroup$
– Apass.Jack
1 hour ago
$begingroup$
Lol, exercise 1 and problem 1, cute. The logic of the algorithm you've described is surprisingly hard to visualize. I would have to code this out tomorrow to get it.
$endgroup$
– temporary_user_name
1 hour ago
$begingroup$
Lol, exercise 1 and problem 1, cute. The logic of the algorithm you've described is surprisingly hard to visualize. I would have to code this out tomorrow to get it.
$endgroup$
– temporary_user_name
1 hour ago
$begingroup$
It looks like I missed the rather obvious but most important explanation. The logic is, in fact, very simple. First, we output each extra opening parenthesis. Once we have passed the turning point, we output each extra closing parenthesis. Done.
$endgroup$
– Apass.Jack
1 hour ago
$begingroup$
It looks like I missed the rather obvious but most important explanation. The logic is, in fact, very simple. First, we output each extra opening parenthesis. Once we have passed the turning point, we output each extra closing parenthesis. Done.
$endgroup$
– Apass.Jack
1 hour ago
add a comment |
$begingroup$
Since this comes from a programming background and not a theoretical computer science exercise, I assume that it takes $O(1)$ memory to store an index into the string. In theoretical computer science, this would mean using the RAM model; with Turing machines you couldn't do this and you'd need $Theta(log(n))$ memory to store an index into a string of length $n$.
You can keep the basic principle of the algorithm that you used. You missed an opportunity for a memory optimization.
using a stack and going through the string once adding parens to the stack and removing them from the stack whenever I encountered a closing paren and the top of the stack contained an opening paren
So what does this stack contain? It's never going to contain ()
(an opening parenthesis followed by a closing parenthesis), since whenever the )
appear you pop the (
instead of pushing the )
. So the stack is always of the form )…)(…(
— a bunch of closing parentheses followed by a bunch of opening parentheses.
You don't need a stack to represent this. Just remember the number of closing parentheses and the number of opening parentheses.
If you process the string from left to right, using these two counters, what you have at the end is the number of mismatched closing parentheses and the number of mismatched opening parentheses.
If you want to report the positions of the mismatched parentheses at the end, you'll need to remember the position of each parenthesis. That would require $Theta(n)$ memory in the worst case. But you don't need to wait until the end to produce output. As soon as you find a mismatched closing parenthesis, you know that it's mismatched, so output it now. And then you aren't going to use the number of mismatched closing parentheses for anything, so just keep a counter of unmatched opening parentheses.
In summary: process the string from left to right. Maintain a counter of unmatched opening parentheses. If you see an opening parenthesis, increment the counter. If you see a closing parenthesis and the counter is nonzero, decrement the counter. If you see a closing parenthesis and the counter is zero, output the current index as a mismatched closing parenthesis.
The final value of the counter is the number of mismatched opening parentheses, but this doesn't give you their position. Notice that the problem is symmetric. To list the positions of mismatched opening parentheses, just run the algorithm in the opposite direction.
Exercise 1: write this down in a formal notation (math, pseudocode or your favorite programming language).
Exercise 2: convince yourself that this is the same algorithm as Apass.Jack, just explained differently.
$endgroup$
add a comment |
$begingroup$
Since this comes from a programming background and not a theoretical computer science exercise, I assume that it takes $O(1)$ memory to store an index into the string. In theoretical computer science, this would mean using the RAM model; with Turing machines you couldn't do this and you'd need $Theta(log(n))$ memory to store an index into a string of length $n$.
You can keep the basic principle of the algorithm that you used. You missed an opportunity for a memory optimization.
using a stack and going through the string once adding parens to the stack and removing them from the stack whenever I encountered a closing paren and the top of the stack contained an opening paren
So what does this stack contain? It's never going to contain ()
(an opening parenthesis followed by a closing parenthesis), since whenever the )
appear you pop the (
instead of pushing the )
. So the stack is always of the form )…)(…(
— a bunch of closing parentheses followed by a bunch of opening parentheses.
You don't need a stack to represent this. Just remember the number of closing parentheses and the number of opening parentheses.
If you process the string from left to right, using these two counters, what you have at the end is the number of mismatched closing parentheses and the number of mismatched opening parentheses.
If you want to report the positions of the mismatched parentheses at the end, you'll need to remember the position of each parenthesis. That would require $Theta(n)$ memory in the worst case. But you don't need to wait until the end to produce output. As soon as you find a mismatched closing parenthesis, you know that it's mismatched, so output it now. And then you aren't going to use the number of mismatched closing parentheses for anything, so just keep a counter of unmatched opening parentheses.
In summary: process the string from left to right. Maintain a counter of unmatched opening parentheses. If you see an opening parenthesis, increment the counter. If you see a closing parenthesis and the counter is nonzero, decrement the counter. If you see a closing parenthesis and the counter is zero, output the current index as a mismatched closing parenthesis.
The final value of the counter is the number of mismatched opening parentheses, but this doesn't give you their position. Notice that the problem is symmetric. To list the positions of mismatched opening parentheses, just run the algorithm in the opposite direction.
Exercise 1: write this down in a formal notation (math, pseudocode or your favorite programming language).
Exercise 2: convince yourself that this is the same algorithm as Apass.Jack, just explained differently.
$endgroup$
add a comment |
$begingroup$
Since this comes from a programming background and not a theoretical computer science exercise, I assume that it takes $O(1)$ memory to store an index into the string. In theoretical computer science, this would mean using the RAM model; with Turing machines you couldn't do this and you'd need $Theta(log(n))$ memory to store an index into a string of length $n$.
You can keep the basic principle of the algorithm that you used. You missed an opportunity for a memory optimization.
using a stack and going through the string once adding parens to the stack and removing them from the stack whenever I encountered a closing paren and the top of the stack contained an opening paren
So what does this stack contain? It's never going to contain ()
(an opening parenthesis followed by a closing parenthesis), since whenever the )
appear you pop the (
instead of pushing the )
. So the stack is always of the form )…)(…(
— a bunch of closing parentheses followed by a bunch of opening parentheses.
You don't need a stack to represent this. Just remember the number of closing parentheses and the number of opening parentheses.
If you process the string from left to right, using these two counters, what you have at the end is the number of mismatched closing parentheses and the number of mismatched opening parentheses.
If you want to report the positions of the mismatched parentheses at the end, you'll need to remember the position of each parenthesis. That would require $Theta(n)$ memory in the worst case. But you don't need to wait until the end to produce output. As soon as you find a mismatched closing parenthesis, you know that it's mismatched, so output it now. And then you aren't going to use the number of mismatched closing parentheses for anything, so just keep a counter of unmatched opening parentheses.
In summary: process the string from left to right. Maintain a counter of unmatched opening parentheses. If you see an opening parenthesis, increment the counter. If you see a closing parenthesis and the counter is nonzero, decrement the counter. If you see a closing parenthesis and the counter is zero, output the current index as a mismatched closing parenthesis.
The final value of the counter is the number of mismatched opening parentheses, but this doesn't give you their position. Notice that the problem is symmetric. To list the positions of mismatched opening parentheses, just run the algorithm in the opposite direction.
Exercise 1: write this down in a formal notation (math, pseudocode or your favorite programming language).
Exercise 2: convince yourself that this is the same algorithm as Apass.Jack, just explained differently.
$endgroup$
Since this comes from a programming background and not a theoretical computer science exercise, I assume that it takes $O(1)$ memory to store an index into the string. In theoretical computer science, this would mean using the RAM model; with Turing machines you couldn't do this and you'd need $Theta(log(n))$ memory to store an index into a string of length $n$.
You can keep the basic principle of the algorithm that you used. You missed an opportunity for a memory optimization.
using a stack and going through the string once adding parens to the stack and removing them from the stack whenever I encountered a closing paren and the top of the stack contained an opening paren
So what does this stack contain? It's never going to contain ()
(an opening parenthesis followed by a closing parenthesis), since whenever the )
appear you pop the (
instead of pushing the )
. So the stack is always of the form )…)(…(
— a bunch of closing parentheses followed by a bunch of opening parentheses.
You don't need a stack to represent this. Just remember the number of closing parentheses and the number of opening parentheses.
If you process the string from left to right, using these two counters, what you have at the end is the number of mismatched closing parentheses and the number of mismatched opening parentheses.
If you want to report the positions of the mismatched parentheses at the end, you'll need to remember the position of each parenthesis. That would require $Theta(n)$ memory in the worst case. But you don't need to wait until the end to produce output. As soon as you find a mismatched closing parenthesis, you know that it's mismatched, so output it now. And then you aren't going to use the number of mismatched closing parentheses for anything, so just keep a counter of unmatched opening parentheses.
In summary: process the string from left to right. Maintain a counter of unmatched opening parentheses. If you see an opening parenthesis, increment the counter. If you see a closing parenthesis and the counter is nonzero, decrement the counter. If you see a closing parenthesis and the counter is zero, output the current index as a mismatched closing parenthesis.
The final value of the counter is the number of mismatched opening parentheses, but this doesn't give you their position. Notice that the problem is symmetric. To list the positions of mismatched opening parentheses, just run the algorithm in the opposite direction.
Exercise 1: write this down in a formal notation (math, pseudocode or your favorite programming language).
Exercise 2: convince yourself that this is the same algorithm as Apass.Jack, just explained differently.
answered 15 mins ago
Gilles♦Gilles
32.8k791162
32.8k791162
add a comment |
add a comment |
Thanks for contributing an answer to Computer Science Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
var $window = $(window),
onScroll = function(e) {
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom)) {
StackExchange.using('gps', function() { StackExchange.gps.track('embedded_signup_form.view', { location: 'question_page' }); });
$window.unbind('scroll', onScroll);
}
};
$window.on('scroll', onScroll);
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f103018%2fhow-can-you-find-all-unbalanced-parens-in-a-string-in-linear-time-with-constant%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
var $window = $(window),
onScroll = function(e) {
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom)) {
StackExchange.using('gps', function() { StackExchange.gps.track('embedded_signup_form.view', { location: 'question_page' }); });
$window.unbind('scroll', onScroll);
}
};
$window.on('scroll', onScroll);
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
var $window = $(window),
onScroll = function(e) {
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom)) {
StackExchange.using('gps', function() { StackExchange.gps.track('embedded_signup_form.view', { location: 'question_page' }); });
$window.unbind('scroll', onScroll);
}
};
$window.on('scroll', onScroll);
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
var $window = $(window),
onScroll = function(e) {
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom)) {
StackExchange.using('gps', function() { StackExchange.gps.track('embedded_signup_form.view', { location: 'question_page' }); });
$window.unbind('scroll', onScroll);
}
};
$window.on('scroll', onScroll);
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
We may need some clarification from you first. Is the first parens or the second parens in "(()" considered unbalanced? Is the last parens or the second to last parens in "())" considered unbalanced? Or is it enough to identify any set of parens with least cardinality such that removing them will leave the remaining parens balanced? Or something else? Or is this part of the interview so that an answer can just put forward any justifiable specification?
$endgroup$
– Apass.Jack
4 hours ago
$begingroup$
I would say it doesn't matter, up to you. Remove any set that leaves the remainder balanced.
$endgroup$
– temporary_user_name
4 hours ago
2
$begingroup$
Then remove them all ;P
$endgroup$
– Veedrac
4 hours ago