Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Save anton-abyzov/7b106a499cc61894f551cddb70da426f to your computer and use it in GitHub Desktop.
Save anton-abyzov/7b106a499cc61894f551cddb70da426f to your computer and use it in GitHub Desktop.
- Assume most recent language standard are available (ES6)
- We expect good performance.
- if missing more requirements details, just make reasonable assumptions of
a your own.
- Solution must be simple and compact.
No defensive coding, no comments, no unrequested features.
Only one file 10-20 lines of code
- Work only inside Google Docs: no external editor/IDE/debugger, no copy-paste
to/from such an editor. We must see the flow of how you write the code.
Note: you have a total of 30 minutes for both questions!
(1)
Implement function verify(text) which verifies whether parentheses within text are
correctly nested. You need to consider three kinds: (), [], <> and only these kinds.
Examples:
verify("---(++++)----") -> 1
verify("") -> 1
verify("before ( middle []) after ") -> 1
verify(") (") -> 0
verify("<( >)") -> 0
verify("( [ <> () ] <> )") -> 1
verify(" ( [)") -> 0
My answer:
var verify = function(text) {
var stack = [];
var stackWasInitialized = false; // that’s to handle this test case -> verify(") (") -> 0
for (var i = 0; i<text.length; i++){
if (text[i] === "(" || text[i] === "[" || text[i] === "<" ) {
if (stack.length === 0 && stackWasInitialized ) {
return 0;
}
stack.push(text[i]);
stackWasInitialized = true;
}
if (text[i] === ")") {
var lastElem = stack.pop();
if (lastElem !== "(")
return 0;
}
if (text[i] === "]") {
var lastElem = stack.pop();
if (lastElem !== "[")
return 0;
}
if (text[i] === ">") {
var lastElem = stack.pop();
if (lastElem !== "<")
return 0;
}
}
if (stack.length > 0)
return 0;
return 1;
}
(2)
Problem
Simplify the implementation below as much as you can.
Even better if you can also improve performance as part of the simplification!
FYI: This code is over 35 lines and over 300 tokens, but it can be written in
5 lines and in less than 60 tokens.
Function on the next page.
function func(s, a, b)
{
var match_empty=/^$/ ;
if (s.match(match_empty))
{
return -1;
}
else
{
var i=s.length-1;
var aIndex=-1;
var bIndex=-1;
while ((aIndex==-1) && (bIndex==-1) && (i>=0))
{
if (s.substring(i, i+1) == a)
aIndex=i;
if (s.substring(i, i+1) == b)
bIndex=i;
i--;
}
if (aIndex != -1)
{
if (bIndex == -1)
return aIndex;
else
return Math.max(aIndex, bIndex);
}
else
{
if (bIndex != -1)
return bIndex;
else
return -1;
}
}
};
My answer:
var func = function(s, a, b) {
if (s.length == 0)
return -1;
var patternA = new RegExp(a);
var patternB = new RegExp(b);
var hasA = patternA.exec(s) !== null;
var hasB = patternB.exec(s) !== null;
if (hasA && hasB) {
return Math.max(patternA.exec(s).index, patternB.exec(s).index)
}
if (hasA) {
return patternA.exec(s).index;
}
if (hasB) {
return patternB.exec(s).index;
}
return -1;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment