Good morning! Here's your coding interview problem for today.
This problem was asked by Facebook.
Given a string of round, curly, and square open and closing brackets, return whether the brackets are balanced (well-formed).
For example, given the string "([])[]({})", you should return true.
Given the string "([)]" or "((()", you should return false.
I'll post my solution when I wake up.
Use a stack.
While iterating through the characters, do the following:
- for an opening brace, push it onto the stack
- for a closing brace, immediately return false if the stack is empty or the character at the top is not the matching opening brace; otherwise remive the character at the top of the stack
Post iteration, return true on whether the stack is empty.
public static boolean is_balanced(String brackets) {
Stack s = new Stack();
try {
for (int i = 0; i < brackets.length(); i++) {
switch (brackets.charAt(i)) {
case ')':
if (s.pop() != '(') {
return false;
}
break;
case ']':
if (s.pop() != '[') {
return false;
}
break;
case '}':
if (s.pop() != '{') {
return false;
}
break;
case '(':
s.add('(');
break;
case '[':
s.add('[');
break;
case '{':
s.add('{');
break;
default:
break;
}
}
} catch (EmptyStackException e) {
return false;
}
return s.isEmpty();
}
Basically this. Tomake a small improvement; return immediately false if the amount of symbols is an uneven number.
function brackets(string){
const stack = [];
const valid = {
'{' : '}',
'}' : -1,
'[' : ']',
']' : -1,
'(' : ')',
')' : -1,
}
for(let i = 0; i < string.length; i++){
const v = string[i];
if( valid[v] && valid[v] != -1){
stack.unshift( valid[v] )
}else if( valid[v] == -1){
const res = stack.shift();
if( res != v )
return false
}
}
return stack.length == 0 ? true : false
}
console.log(
brackets("([{}])")
)
[/Code]
function balanced(s){
while(s != (s = s.replace(/\(\)|\[\]|\{\}/,"")));
return s == '';
}
>catch (EmptyStackException e)
#include
int main(const int argc, const char** argv)
{
int sum = 0;
char *ptr = argv[1];
while (*ptr++ != '\0') sum += (int)(*ptr);
if ((sum >> 1) & 1) printf("Not balanced\n");
else printf("Balaned\n");
return 0;
}
fails on ([)], retard
well im not supposed to do your homework now am i
This and this problem is legit high school introductory to CS tier difficulty
>here's your 300k starting salary to work at a college campus for 3 hours a day
unreal
That's not an improvement unless they said fastest execution time. You get bonus points for simplicity/elegance in your solution.
#!/usr/bin/env python3
import sys
pairs = {'(':')', '[':']', '{':'}'}
def ops_homework(s):
while len(s) > 0 and s[0] in pairs:
p = pairs[s[0]]
if s[1] == p:
s = s[2:]
continue
s = ops_homework(s[1:])
if len(s) < 1 or s[0] != p:
return 'XXX'
s = s[1:]
return s
def ops_homework_wrapped(s):
return ops_homework(s) == ''
for line in sys.stdin:
print(ops_homework_wrapped(line.strip()))
Imagine he turns it in with "ops_homework" func name in it
Too tired to write down a nice solution but this works
(defn balanced?
[cs]
(let [m (apply assoc {} (mapcat reverse (partition 2 "{}[]()")))]
(loop [stack ()
cs cs]
(if (empty? cs) true
(if-let [opening (get m (first cs))]
(if (not= opening (first stack)) false
(recur (rest stack) (rest cs)))
(recur (cons (first cs) stack) (rest cs)))))))
> using type stack for a problem I'd solve with just an integer
One of us is doing it wrong.
i tried...
class Program
{
static void Main(string[] args)
{
Console.WriteLine("({}([]))".HasClosedBracket());
}
}
public static class A
{
static Dictionary brackets = new Dictionary { { '(', ')' }, { '[', ']' }, { '{', '}' } };
public static bool HasClosedBracket(this string s)
{
if (s.Length > 1 && IsOpenBracket(s[0]))
{
int i = 0;
return HasClosedBracket(s, ref i) && i == s.Length - 1;
}
return false;
}
static bool IsOpenBracket(char c) => c == '(' || c == '{' || c == '[';
static bool HasClosedBracket(string s, ref int i)
{
var match = brackets[s[i]];
for (i++; i < s.Length; i++)
{
if (s[i] == match)
return true;
if (IsOpenBracket(s[i]) && (s.Length < i + 1 || !HasClosedBracket(s, ref i)))
return false;
}
return false;
}
}
You tried
#!/usr/bin/env python3
import sys
BRACKETS = {'(': ')', '[': ']', '{': '}'}
def isWellFormed(bracketString):
"""
Given a string of round, curly, and square open and closing brackets,
return whether the brackets are balanced (well-formed).
"""
stack = []
for el in bracketString:
# do brackets open?
if el in BRACKETS:
stack.append(BRACKETS[el])
# do the matching brackets close?
elif (not stack) or stack.pop() != el:
return 0
return len(stack) == 0
if __name__ == "__main__":
# read in the expression and strip whitespaces
bracketString = sys.stdin.read().strip()
print(isWellFormed(bracketString))
>This problem was asked by Facebook.
Stopped reading.
it's not my home work. It's actual code challenges I've been taking. I'll try to post whenever I can. I'll post the challenge and later I come back and post my solution.
-module(balanced).
-define(is_opening(C), C =:= 40 orelse C =:= 91 orelse C =:= 123).
-export([balanced/1]).
balanced(S) ->
balanced(S, []).
balanced([C|Rest], Stack) when ?is_opening(C) ->
balanced(Rest, [C|Stack]);
balanced("]" ++ Rest, "[" ++ Stack) ->
balanced(Rest, Stack);
balanced(")" ++ Rest, "(" ++ Stack) ->
balanced(Rest, Stack);
balanced("}" ++ Rest, "{" ++ Stack) ->
balanced(Rest, Stack);
balanced([], []) ->
true;
balanced(_, _) ->
false.
%%%%%
14> balanced:balanced("([])[]({})").
true
15> balanced:balanced("([)]").
false
16> balanced:balanced("((()").
false
That's really what the whiteboard questions are like. It's why it's so funny when people complain about them.
This is fizzbuzz tier
i would just like to point out that any balanced string must have a "{}", "[]" or "()" substring somewhere in it so recursively remove the above substrings until you have nothing left (return true) or there are no such substrings left to remove (return false)
but that's an O(whatever the fuck n) operation because you're going through the string however many times depending on how long it is
don't call us, we'll call you
Ez Pz
Have a counter
Iterate through the string by characters
Increase counter when '{' is encountered
Decrease the counter when '}' is encountered
If the counter is not 0 at the end, it's malformed.
If the counter goes below 0 at any time, then it's malformed.
read the instructions. it's three different kinds of brackets. counters are not enough here.
don't you need 3 counters? one for each type?
"([)]" should return false. yours return true
upgrade your PC bro
It's the same problem but for whatever you want to count. Have separate counter for each kind of bracket.
Yes, you would need a separate counter for each. There might be a way to do it via one counter, but this is the simplest naive solution which seems ok by me.
Stack definitely makes the most sense here
"([)]" should return false. yours return true
don't call us...
([)]
>Use a stack
Stack overflow
Ah, couldn't read it properly from the Jow Forums formatting. Code tags actually made it legible.
Yeah, it would break in that case.
Stack is simpler than counters
only acceptable solution ITT
You make counters that increase for each opening and decrease for each closing
One for (), one for [] and one for {}
Then you move from the beginning of the string to the end and increment or decrement the counters
If the string has an odd number of chars at the start, you by default return false
If any of your counters is not 0 you return false
Otherwise true
...
what compels you to write such hard to read code?
I think you can still keep using counters but somehow you have to keep track of what was counted beforehand and where it does go below the beforehand counter.
fn main() {
println!("{}", check_balance("([])[]({})"));
println!("{}", check_balance("([)]"));
println!("{}", check_balance("((()"));
}
fn check_balance(s: &str) -> bool {
let mut s: Vec = s.chars().collect();
while !s.is_empty() {
for (num, c) in s.clone().iter().enumerate() {
let scpy = s.clone();
let next_c = scpy.get(&num+1);
if next_c.is_none() {
return false // EOL
}
let next_c = next_c.unwrap().to_string();
match c {
'{' => {
if next_c.contains('}') {
s.drain(num..num+2);
break
}
}
'(' => {
if next_c.contains(')') {
s.drain(num..num+2);
break
}
}
'[' => {
if next_c.contains(']') {
s.drain(num..num+2);
break
}
}
_ => (),
}
}
}
true
}
bit ugly but can't be bothered to make it more pretty
As it should, dumb ass
Hey Jow Forums I legit got this question in an interview and they gave me 15 minutes to write out code on a whiteboard to solve if it's balanced. They had the starting strings:
string a1 = "({a[b]c})";
string a2 = "{a[b]]}";
string a3 = "[a{{}]";
char[] checkstart = '{', '[', '(';
char[] checkend = '}', ']', ')';
After about 15 minutes I had put up something like:
public static bool Check(string s)
{
bool balanced = true;
string reversed = s.Reverse();
try{
for(int bracketIndex = 0; bracketIndex < checkstart.Length, bracketIndex++){
for(int i = 0; i < s.Length; i++){
string checkPartStart = s.Substring(0, s.IndexOf(checkstart[bracketIndex]));
string checkPartEnd = reversed.Substring(0, reversed.Substring(0, reversed.IndexOf(checkend[bracketIndex])
foreach(char c in checkstart)
{
if(c != checkstart[bracketIndex])
{
if(checkPartStart.Contains(c) return balanced = false;
if(checkPartEnd.Contains(c) return //time limit hit
}
}
}
}
}
catch(Exception e) { balanced = false; }
return balanced;
}
I hit the time limit and the IT lead said they didn't need someone who couldn't find a O(1) solution to the problem. Nor do they need liars as I said I was an expert in C# and somehow thought "string reversed = s.Reverse();" was compilable code, they had been typing along in Visual Studio and it clearly wasn't.
I've been beating myself up because now I've been unemployed for 2 months since the last company I worked for went out of business, and now I'm really starting to feel the pain. So Jow Forums, I know that the answers were wrong, but do I really deserve to be unable to find even minimum wage programming work? I'd kill to get a programming job at this rate, but do I even deserve minimum wage if I'm this much of a failure?
The easiest solution is usually the least verbose and most correct one:
fn balanced(string):
for char in string:
if (char in []):
balance += 1
if (char in []):
balance -= 1
balance == 0 ? true : false
Note: This is partly pseudocode, i don't remember how to tokenize a string.
How can it be a O(1) problem? If anything it would be O(n) where n is the number of characters in the string.
>O(1) solution
not possible
>dumb mistake in C# while under stress
>"do i even deserve minimum wage if i'm this much of a failure"
come the fuck on mate it's not that bad, your life isn't over because you fucked an interview
This would return true for "([)]"
Basically the stack method would be your best bet.
Have a stack meant for characters or pairs of brackets(orwhateveryoucallit)
Iterate through the string character by character
Push onto the stack when you encounter opening characters
Every time you come across a closing character, pop the stack, if the popped element doesn't match its corresponding closing character, then return false
If the stack size is not 0 by the end, return false
Return true
Or you can the stack meant for closing characters only where you compare the popped character against the closing character you came across. And when you come across opening characters, you push its corresponding closing character onto the stack.
By the sound of that I would say the guy that interviewed you is a fucking psycopath
user there are lots of "seniors" and "leads" that don't deserve the title, don't beat yourself up and just keep trying
bool testBalancedBrackets(char* str){
int bracketsNormal = 1;
int bracketsSquare = 1;
int bracketsCurvy = 1;
do{
switch(*str){
case '(' : ++bracketsNormal; break;
case ')' : --bracketsNormal; break;
case '[' : ++bracketsSquare; break;
case ']' : --bracketsSquare; break;
case '{' : ++bracketsCurvy; break;
case '}' : --bracketsCurvy; break;
defualt: break;
}
if (!(bracketsNormal && bracketsSquare && bracketsCurvy))
return false;
}while(++str != '\0');
if ( (bracketsNormal == 1) && (bracketsSquare == 1) && (bracketsCurvy == 1))
return true;
return false;
}
fuck, missed this ([)] case, but now it's fixed:
bool testBalancedBrackets(char* str){
char bracketBuffer[512];
char* bracketIterator = bracketBuffer;
do{
switch(*str){
case '(' :
case '[' :
case '{' :
*(bracketIterator++) = *str;
break;
case ')' :
if ( bracketIterator == bracketBuffer || *(--bracketIterator) != '(' )
return false;
case ']' :
if ( bracketIterator == bracketBuffer || *(--bracketIterator) != '[' )
return false;
case '}' :
if ( bracketIterator == bracketBuffer || *(--bracketIterator) != '{' )
return false;
defualt: break;
}
}while(++str != '\0');
if ( bracketIterator == bracketBuffer )
return true;
return false;
}
This should be very fast also, but it only works for a maximum of 512 open brackets, lol.
bool testBalancedBrackets(char* str){
char bracketBuffer[512];
char* bracketIterator = bracketBuffer;
do{
switch(*str){
case '(' :
case '[' :
case '{' :
*(bracketIterator++) = *str;
break;
case ')' :
if ( (bracketIterator == bracketBuffer) || (*(--bracketIterator) != '(') )
return false;
break;
case ']' :
if ( (bracketIterator == bracketBuffer) || (*(--bracketIterator) != '[') )
return false;
break;
case '}' :
if ( (bracketIterator == bracketBuffer) || (*(--bracketIterator) != '{') )
return false;
break;
defualt: break;
}
}while(*(++str) != '\0');
if ( bracketIterator == bracketBuffer )
return true;
return false;
}
ok, now its also fixed to compile correctly and no more bugs...
Do I get hired?
feel free to tell me what you would improve about
oh i shat myself. this is failed on "()()"
sorry, here is the fixed solution
static Dictionary brackets = new Dictionary { { '(', ')' }, { '[', ']' }, { '{', '}' } };
public static bool IsBalancedBrackets(string s)
{
for (int i = 0; i < s.Length; i++)
if (!IsOpenBracket(s[i]) || !HasClosedBracket(s, ref i))
return false;
return true;
}
static bool IsOpenBracket(char c) => c == '(' || c == '{' || c == '[';
static bool HasClosedBracket(string s, ref int i)
{
var match = brackets[s[i]];
for (i++; i < s.Length; i++)
{
if (s[i] == match)
return true;
if (IsOpenBracket(s[i]) && !HasClosedBracket(s, ref i))
return false;
}
return false;
}
import collections
def balanced(s):
counter = collections.Counter()
cs = set(list('{}[]()'))
for c in s:
if c not in cs:
continue
counter[c] += 1
return (
counter['('] == counter[')'] and
counter['{'] == counter['}'] and
counter['['] == counter[']'])
print(balanced('{hel[l]o}'))
true
they probably just wanted to get rid of him quickly
My mistake, they said O(n), I recall them saying I was going for a new record with O(n*4) or something like that.
I've had 2~ interviews a week for a couple months now. Literally sitting down in offices where there's 12~ people around the table and they're doing "group interviews." We're all sitting around the table doing personality tests and competency tests, and having to grab answers from other people like "What did group H person 5 put for their question #6? Do you think it's correct, and write how you would help them get to a better answer." It's hell, the competition for minumum wage has never ever been like this, not since they raised minimum wage to $15/h in Alberta.
(Also we were all referred to as group H, implying they get 100~ people for positions like this. This was for a job posting where they said they had 3 openings.)
It's hard to say maybe I'm OK when the objective evidence is me facing a huge rejection rate. The only thing that makes me reconsider is that I applied with my Resume to some places in Maryland and got invited to interviews for jobs around $140k/yr USD with the exact same skillset as what I'm fighting against other people for $20k/yr USD in Alberta. Then I have to tell them I'm a remote-only worker and they pass me over for an American. Happens every time, even though I incorporated alongside a bunch of my friends who are moving out of Canada for work.
Also acceptable. Probably better than mine I like the use of hashmap
Vim and terminal settings?
which is still balanced :^)
no
>({)}
Read OP's post in it's entirety.
checked. pretty much my solution to the problem as well
why would that work?
He means it returns true when it should return false IE his function failed
Seems easy to solve with a stack if I'm not mistaken. Process the string sequentially, push any open bracket to the stack. When you encounter a closing bracket, pop an element from the stack. If there's nothing to pop or you get an open bracket of a different type, return false immediately. If you manage to go through the whole string, return true since it means the string is balanced.
If you manage to go through the whole string, return true since it means the string is balanced.
Only if the stack is empty at the end.
((((((((((((((()))
Actually, that's not right. After the loop you'd have to check whether the stack is empty. The string is only balanced if it is, otherwise you have more opening brackets than closing.
Yeah, I realized that.
lmao this would never pass code review
sounds like they were dicks, just keep applying to jobs dude
Fancypants optimizations if you're trying to show off:
When you encounter an opener, push the matching closer onto the stack, not the opener. Why? It saves a couple lines later, that's all. (next iteration, if the top of the stack and the new input character match, you can just pop and move on without actually checking what the new character is)
If you're using an array as a stack, it only needs to be half the length of the input; if the stack fills up, you can immediately return false, because you already know there aren't enough closing brackets.
Likewise, keep track of your stack depth and the remaining length of the input; if the stack is ever deeper than the remaining string, you can immediately return false, because you already know there aren't enough closing brackets.
what if you just did a reverse string check like the ones for checking string palindromes but with the condition that the character checks are not equals but equals to ascii value plus 2 cause ascii goes {, |, } and [,\,]
You could use a stack, but why not just a counter for each type that increments on open brackets, deincrements and closed brackets, and is checked if it's 0 at the end of the string?
Because using counters would fail on strings like "([)]" which isn't correct but still has the same number of opening and closing brackets of each type.
I said a counter for each type
Yes, I know. It still doesn't help.
oh, mb, I'm a retard. I see the problem.
seriously though is there any best website for these dumb challenges? I'm tired of ranking bullshit and subscriptions, I just want the questions and then example solutions
hackerrank
Leetcode. Hackerrank is a close 2nd but it is nissing some features Leetcode had for ages and its interview prep questions are better.
public int solution(string S)
{
if(string.IsNullOrEmpty(S))
return 1;
if(S.Length % 2 != 0)
return 0;
char firstChar = S[0];
char lastChar = S[S.Length-1];
if(lastChar == '{' || lastChar == '(' || lastChar == '[')
return 0;
Stack charStack = new Stack();
foreach(char CRC in S)
{
if(CRC == '{' || CRC == '(' || CRC == '[')
charStack.Push(CRC);
else if(charStack.Count() == 0)
return 0;
else
{
char topMostChar = charStack.Pop();
if(topMostChar == '{' && CRC == '}')
continue;
if(topMostChar == '(' && CRC == ')')
continue;
if(topMostChar == '[' && CRC == ']')
continue;
return 0;
}
}
if(charStack.Count() == 0)
return 1;
else
return 0;
}
Why it hangs like that only in Codility's platform?
Because the order of closing bracket types matters, so you have to preserve the order as you go.
Is my C okay?
#include
#include
#include
int is_balanced(char *input);
int main(int argc, char **argv)
{
int i;
(void)argc;
for(i = 1; argv[i]; i++)
{
puts(is_balanced(argv[i]) ? "true" : "false");
}
return 0;
}
struct item {
char val;
struct item *past;
struct item *next;
};
int is_balanced(char *input)
{
int pos;
char c;
struct item *latest;
pos = 0;
latest = NULL;
while((c = input[pos++]))
{
if(!latest)
{
latest = (struct item*)malloc(sizeof(struct item));
memcpy(&latest->val, &c, sizeof(c));
}
else if (
(c == ']' && latest->val == '[') ||
(c == '}' && latest->val == '{') ||
(c == ')' && latest->val == '(')
)
{
latest = latest->past;
}
else {
latest->next = (struct item*)malloc(sizeof(struct item));
memcpy(&latest->next->val, &c, sizeof(c));
latest->next->past = latest;
latest = latest->next;
}
}
return latest == NULL;
}
private static final Map brackets = new HashMap() {{
put('(', ')');
put('{', '}');
put('[', ']');
}};
static boolean isBracket(char c) {
return isLeft(c) || isRight(c);
}
static boolean isLeft(char c) {
return brackets.keySet().contains(c);
}
static boolean isRight(char c) {
return brackets.values().contains(c);
}
static boolean areOpposite(char a, char b) {
return Objects.equals(brackets.get(a), b);
}
static boolean canFollow(char c, char prev) {
if (isRight(prev)) return true; // anything can follow and opening bracket
return isLeft(c) || areOpposite(prev, c); // a right paren can not follow a left square bracket
}
static boolean balanced(String str) {
Stack stack = new Stack(); // only push never pop
int openBrackets = 0;
for (int i = 0; i < str.length(); i++) {
final char c = str.charAt(i);
if (!isBracket(c)) continue;
if (isLeft(c)) openBrackets++;
if (isRight(c)) openBrackets--;
if (stack.empty()) {
stack.push(c);
continue;
}
char prev = stack.peek();
if (!canFollow(c, prev)) return false;
stack.push(c);
}
return openBrackets == 0;
}
this is probably the only correct solution ITT
>C
No one uses this @ facebook.
You responded to the wrong user but also no shit
Based and erlangpilled.
No time to code, but I figure you'd push the opening symbols ( { [ on a stack, and if a closing one appears ) } ] you pop the top of the stack.
If it doesn't match the same type it's not balanced, right?
you cant pop because the opening bracket could be anywhere in the stack
That was my solution too fren
import balanced.isBalanced as myFunc
EXAMPLE = "(()()[])"
print(myFunc(EXAMPLE))
just realized that the single counter allows a square bracket to close a paren which makes "( [ ] ]" return true
idiot