At line 34 it seems like you have a bit of a conceptual issue that in the end doesn't matter, but might matter to interviewers. if pop removes the first item from the queue, then you would not want to remove it in the case that the close value does not match the open value. I believe this may result in your code marking a single open value as balanced, since it would be popped in the if statement. Also, your open and close array would be better as a dictionary, since they are key value pairs. this makes matches() O(1) rather than O(n), which reduces total complexity from O(n^2) to O(n).
Wouldn't be even more efficient to use a hashmap to check isOpenTerm and matches? You could have isOpenTerm to check if the key (the open term char) is in the hashmap. (would that bring that part to O(n)?) For matches could you then check what the predicated closing term was from checking the hashset for the closing term by using the openTerm from the stack to get it and then compare it to what closeTerm was?
I think it may be constructive to High Pass your video at around 80-100Hz. Whenever you type, the bass rattles significantly. Just a thought. Great Video by the way.
I think it may be destructive to boost the shit out of DAT BASS and make it a trap vid that you can bang your head to until you completely forget that you have an interview on monday
Exactly. You High pass at around 80-100Hz to cut out the bass frequencies. This is because the "bass rattles significantly" when she types. @TwstedTV still a great video btw!
This doesn't seem like the best solution, if you take time complexity into consideration. The isOpenTerm and matches both contain a for loop of 3 possible iterations. Therefore, for every n, there are six additional iterations. The time complexity of this solution is O(6n). It's been years since I've taken an algo class, so correct me if I'm wrong.
With php or perl, such a task is solved in three steps: 1) just in case we filter all characters except brackets 2) in a loop while the string is not empty, delete all '[]', '{}', '()' from the string, if the string has not changed after the deletion, return false 3) after the loop return true
This one is using stack and map but in cpp: #include #include #include using namespace std; bool isBalanced(string str) { int i = 0; stack st; map m; m['}']='{'; m[']']='['; m[')']='('; while(char ch = str[i++]) if(ch=='{' || ch=='[' || ch=='(') st.push(ch); else if(st.top()==m[ch]) st.pop(); else return false; return st.empty()?true:false; } int main() { string str; cin>>str; if(isBalanced(str)) cout
Another horrible interview question where if you know the trick you are fine, and if you don't, you are going down. I find it strange that she implemented isOpenTerm and matches (which modern languages have built in support for), but left the stack functions assumed.
Hey if I were to use simple counter (increment on opening and decrement on closing and check value at the end) instead of a stack what advantage would it have over this stack based approach?
para quem pediu o código em js, com a correção do primeiro item do array estar invertido let balancear = "{{{[[(({})()())]]}}}}" let object = {"{":"}","(":")","[":"]"} function isOpen(value){ return object[value]?true:false } function matches(finalFila,value){ const closed = object[finalFila] return closed && value==closed?true:false } function isBalanced(expression){ let stack=[] for (let i=0;i< expression.length;i++){ if(isOpen(expression[i])){ stack.push(expression[i]) }else{ if(i>0){ if(stack.length ==0 || !matches(stack.pop(), expression[i])){ return true } } } } return stack.length ==0 } console.log(isBalanced(balancear))
Probably but I think the point of a deque is that it can be used similarly to a stack (can pop from the front or rear), but for this demonstration I think the purpose was to help people understand the ways in which a stack ADS can be useful. No need to overwhelm people who are new to the concepts.
So this is how IDEs check if you properly closed off all your parenthesis, great video! thanks
These videos were a great cramming session! Very very well put together
Do more of these please!
@1:46 DJ Khaled would be proud
omg u da real mvp
I can't watch this video seriously anymore
At line 34 it seems like you have a bit of a conceptual issue that in the end doesn't matter, but might matter to interviewers. if pop removes the first item from the queue, then you would not want to remove it in the case that the close value does not match the open value. I believe this may result in your code marking a single open value as balanced, since it would be popped in the if statement.
Also, your open and close array would be better as a dictionary, since they are key value pairs. this makes matches() O(1) rather than O(n), which reduces total complexity from O(n^2) to O(n).
Wouldn't be even more efficient to use a hashmap to check isOpenTerm and matches? You could have isOpenTerm to check if the key (the open term char) is in the hashmap. (would that bring that part to O(n)?) For matches could you then check what the predicated closing term was from checking the hashset for the closing term by using the openTerm from the stack to get it and then compare it to what closeTerm was?
I think it may be constructive to High Pass your video at around 80-100Hz. Whenever you type, the bass rattles significantly. Just a thought. Great Video by the way.
I think it may be destructive to boost the shit out of DAT BASS and make it a trap vid that you can bang your head to until you completely forget that you have an interview on monday
80-100Hz are bass frequencies. I am a professional audio engineer and I nearly fell off my chair in laughter when I read this....LOL
Exactly. You High pass at around 80-100Hz to cut out the bass frequencies. This is because the "bass rattles significantly" when she types. @TwstedTV still a great video btw!
@@dima9917 wtf man, I'm crying 😂😂😂😂
Reading CTCI and watching this video series is very nice. Thank you ! p.s. There is a Korean book on the top stack of those books.. interesting
This doesn't seem like the best solution, if you take time complexity into consideration. The isOpenTerm and matches both contain a for loop of 3 possible iterations. Therefore, for every n, there are six additional iterations. The time complexity of this solution is O(6n). It's been years since I've taken an algo class, so correct me if I'm wrong.
You leave out the coefficient before n when describing time complexity. So the time complexity in this case. is still (just) O(n)
With php or perl, such a task is solved in three steps:
1) just in case we filter all characters except brackets
2) in a loop while the string is not empty, delete all '[]', '{}', '()' from the string, if the string has not changed after the deletion, return false
3) after the loop return true
Example code:
private static HashMap TOKENS;
public static void main(String[] args){
TOKENS = new HashMap();
TOKENS.put('(', ')');
TOKENS.put('{', '}');
TOKENS.put('[', ']');
System.out.println(isBalanced("{{{{[[(({})()())]]}}}}"));
}
public static boolean isBalanced(String expression){
Stack stack = new Stack();
for(char c: expression.toCharArray()){
if(TOKENS.containsKey(c))
stack.push(c);
else if(stack.isEmpty() || (int)c != (int)TOKENS.get(stack.pop()))
return false;
}
return stack.isEmpty();
}
yeah..the hashmap makes retrieving the value get done in unit time rather than traversing the entire array. Good job.
nice
How many languages does she speak. Korean book, Russian book, Spanish, and either japanese or chinese book in the background. Also English
She also speaks javascript
I believe this is missing a validation for when the input expression is empty. Returning stack.isEmpty() which is true and incorrect.
This one is using stack and map but in cpp:
#include
#include
#include
using namespace std;
bool isBalanced(string str) {
int i = 0;
stack st;
map m;
m['}']='{';
m[']']='[';
m[')']='(';
while(char ch = str[i++])
if(ch=='{' || ch=='[' || ch=='(') st.push(ch);
else if(st.top()==m[ch]) st.pop();
else return false;
return st.empty()?true:false;
}
int main()
{
string str;
cin>>str;
if(isBalanced(str)) cout
what is map stl please explain??
Another horrible interview question where if you know the trick you are fine, and if you don't, you are going down. I find it strange that she implemented isOpenTerm and matches (which modern languages have built in support for), but left the stack functions assumed.
Just beautiful!
Hey if I were to use simple counter (increment on opening and decrement on closing and check value at the end) instead of a stack what advantage would it have over this stack based approach?
The issue with a counter is that you still need to keep track of the order in which the open characters appear.
your approach accepts "{ [ } ]" which it shouldn't.
Keep up the good work :) Very helpful video
whats the complexity ?
Linear in time
o(n) because you're only going through the char array once if I am correct.
i understood! thanks so much
!
0:53 --- hint
para quem pediu o código em js, com a correção do primeiro item do array estar invertido
let balancear = "{{{[[(({})()())]]}}}}"
let object = {"{":"}","(":")","[":"]"}
function isOpen(value){
return object[value]?true:false
}
function matches(finalFila,value){
const closed = object[finalFila]
return closed && value==closed?true:false
}
function isBalanced(expression){
let stack=[]
for (let i=0;i< expression.length;i++){
if(isOpen(expression[i])){
stack.push(expression[i])
}else{
if(i>0){
if(stack.length ==0 || !matches(stack.pop(), expression[i])){
return true
}
}
}
}
return stack.length ==0
}
console.log(isBalanced(balancear))
Someone has the python equivalent code?
def check_balance(arr: List[str]) -> str:
""" Solution O(n)"""
closing_opening = {
"}": "{",
")": "(",
"]": "["
}
stack = []
for item in arr:
if item in closing_opening.values():
stack.append(item)
elif stack[-1] == closing_opening[item]:
stack.pop()
if len(stack) != 0:
return "Unbalanced"
else:
return "Balanced"
Anybody have a JavaScript Solution?
Interesting video but i would have used an ArrayDeque instead of a Stack^^
Probably but I think the point of a deque is that it can be used similarly to a stack (can pop from the front or rear), but for this demonstration I think the purpose was to help people understand the ways in which a stack ADS can be useful. No need to overwhelm people who are new to the concepts.
Thank you
Excellent video
"Squiggles"?! Don't you mean "braces"?
This should have been in Javascript. Not all of us remember Java
Python/Go
wow... that code is quite lovely
So this is basically a pushdown automata
dilemma resolved she reads skiena thats it
Could have been simpler.
kamusta mga pupians.