|
Thread Rules
1. This is not a "do my homework for me" thread. If you have specific questions, ask, but don't post an assignment or homework problem and expect an exact solution.
2. No recruiting for your cockamamie projects (you won't replace facebook with 3 dudes you found on the internet and $20)
3. If you can't articulate why a language is bad, don't start slinging shit about it. Just remember that nothing is worse than making CSS IE6 compatible.
4. Use [code] tags to format code blocks. |
Hey guys, I'm looking into finding a job in the near future, so doing some prep. Currently working through tree and graph problems and such.
The current problem I'm working on is: Find the First Common Ancestor (FCA) given two tree nodes (binary tree).
Two assumptions I've made:
- Neither of the 2 given nodes can be the FCA, or else technically they wouldnt be an "ancestor".
- The 2 given nodes are part of the same tree (ie my implementation will always find a FCA unless one or both the nodes are the root of the tree)
I've implemented it, there's probably a better way to do this. I haven't checked the solutions yet (this is from Cracking the Coding Interview). However, I've been struggling in understanding how to determine the run times and space complexities of certain algorithms. Wondering if any of you guys that know this stuff well could help me analyze it.
My algorithm breakdown:
- Start by determining which of the two nodes is higher up on the tree
- Then, starting with that node's parent, we'll continue walking up using the parent pointers
- For each time we step up, we walk up the lower node, checking to see if it's the same as the current higher node.
- By the time the higher node has reached the root, if we still haven't found the FCA, the root is the FCA.
Below is my implemantation. I'm using C#, and "distanceFromRoot" is a local helper function (similar to how you can create local functions inside another function in javascript).
public class TreeNode
{
public TreeNode Left { get; set; }
public TreeNode Right { get; set; }
public TreeNode Parent { get; set; }
}
public static TreeNode FindFirstCommonAncestor(TreeNode a, TreeNode b)
{
int distA = distanceFromRoot(a);
if (distA == 0) return null;
int distB = distanceFromRoot(b);
if (distB == 0) return null;
TreeNode higher = distA <= distB ? a.Parent : b.Parent;
TreeNode lower = higher == a.Parent ? b.Parent : a.Parent;
while (higher.Parent != null)
{
TreeNode currLower = lower;
while (currLower != null)
{
if (currLower == higher) return currLower;
currLower = currLower.Parent;
}
higher = higher.Parent;
}
return higher;
// local functions
int distanceFromRoot(TreeNode n)
{
if (n.Parent == null) return 0;
return 1 + distanceFromRoot(n.Parent);
}
}
My (probably) wrong analysis of runtime and space:
From what I've seen and read, I believe that when you're working with trees, the input n used in big O represents the total number of nodes in the tree. So, if you were to walk up the entire tree once, starting at one of the leaves, this would be O(log n) right?
But that's only walking up the tree once. My algorithm has nested while loops, with the inner one potentially walking up the entire tree for each step of the outer loop. So, does that mean that my runtime is O(log n) x O(log n)?
I understand the simplest examples, such as having two nested loops walk through the same array. That gives a runtime of O(n^2). Does using that kind of logic make any sense in my example?
Also, if it is indeed O(log n) x O(log n), I assume that would be a worst-case analysis.
For space, I think it's just a constant of O(1) since the allocation of variables doesn't change while walking through the loops. It also doesn't use any external/auxiliary data structures which leads me to believe it has a constant space complexity.
I'm having a good time prepping, but analyzing this stuff has been a bit frustrating. I'm hoping it just becomes more intuitive as I do more problems, and maybe even reach a aha moment.
Thanks for any help!
|
Didn't check over your analysis or code, but given your description, it's inefficient. Why not just extract both paths to the root, and then find the last node that these paths are equal? That's O(log n).
|
> The current problem I'm working on is: Find the First Common Ancestor (FCA) given two tree nodes (binary tree).
Two assumptions I've made:
- Neither of the 2 given nodes can be the FCA, or else technically they wouldnt be an "ancestor".
- The 2 given nodes are part of the same tree (ie my implementation will always find a FCA unless one or both the nodes are the root of the tree)
Your first assumption should be incorrect, though fair game if stated. Your algorithm should be able to return the inputs as ancestors.
Because your first assumption is incorrect, "unless one or both the nodes are the root of the tree" should be handled as well.
From what I've seen and read, I believe that when you're working with trees, the input n used in big O represents the total number of nodes in the tree. So, if you were to walk up the entire tree once, starting at one of the leaves, this would be O(log n) right?
No, the input n in Big O would usually be the number of nodes traversed in the algorithm, assuming that the node contains the most costly operation (generally accessing node.data).
No, if you walk up the entire tree, your worst case is O(n), where your tree is completely unbalanced.
But that's only walking up the tree once. My algorithm has nested while loops, with the inner one potentially walking up the entire tree for each step of the outer loop. So, does that mean that my runtime is O(log n) x O(log n)?
No, the height of a perfectly balanced tree is essentially log(n), where n is the number of elements in the tree, and thus the worst case traversal from leaf to root in a perfectly balanced tree is O(log(n)). But Big O is about worst case analysis, and a perfectly balanced tree isn't the worst case. In your algorithm's worst case, the tree is unbalanced on both sides, meaning lower and higher are at the same height, n / 2. This means in the worst case your algorithm will traverse the inner loop n/2 times, and then other loop n/2 times, which ends up being n^2/4, or O(n^2).
For space, I think it's just a constant of O(1) since the allocation of variables doesn't change while walking through the loops. It also doesn't use any external/auxiliary data structures which leads me to believe it has a constant space complexity.
This is an easy thing to overlook. Your distanceFromRoot function runs recursively, so you use up a new stack frame every function call, and since trees can be completely unbalanced, that means you've allocated n nodes on the stack to determine the height of the tree, a space complexity of O(n).
untested rusty C++ attempt
* returns null if there's no solution,
* runs in exactly 2*( height(ancestor) - height(a) ) or 2*( height(ancestor) - height(b) ), whichever is higher
* worst case of O(n)
+ Show Spoiler +
public Node* findFirstCommonAncestor(Node* a, Node* b) {
set<Node*> a_ancestors = { a };
set<Node*> b_ancestors = { b };
while (a != nullptr || b != nullptr) {
if (a != null && b_ancestors.count(a) != 0) {
return a;
}
if (b != null && a_ancestors.count(b) != 0) {
return b;
}
if (a != nullptr && a->parent != nullptr) {
a_ancestors.insert(a->parent);
a = a->parent;
}
if (b != nullptr && b->parent != nullptr) {
b_ancestors.insert(b->parent);
b = b->parent;
}
}
return nullptr;
}
|
Fuck me. Trying to introduce OAuth flow into REST only API is a fucking nightmare (and it has to support mobiles too).
|
On August 16 2017 23:04 Manit0u wrote:
Fuck me. Trying to introduce OAuth flow into REST only API is a fucking nightmare (and it has to support mobiles too).
What are you having problems with? It's pretty straight forward once you get the hang of it.
|
On August 17 2017 03:44 Blucan wrote:Show nested quote +On August 16 2017 23:04 Manit0u wrote:
Fuck me. Trying to introduce OAuth flow into REST only API is a fucking nightmare (and it has to support mobiles too). What are you having problems with? It's pretty straight forward once you get the hang of it.
I'm not entirely sure where to redirect to after logging in to the IP since we have the authorization code grant flow. So mobile/web redirects to IP -> IP redirects it somewhere else -> web/mobile gets auth code -> it logs in to the API with the auth code. That's plenty of shit to do.
|
On August 17 2017 04:34 Manit0u wrote:Show nested quote +On August 17 2017 03:44 Blucan wrote:On August 16 2017 23:04 Manit0u wrote:
Fuck me. Trying to introduce OAuth flow into REST only API is a fucking nightmare (and it has to support mobiles too). What are you having problems with? It's pretty straight forward once you get the hang of it. I'm not entirely sure where to redirect to after logging in to the IP since we have the authorization code grant flow. So mobile/web redirects to IP -> IP redirects it somewhere else -> web/mobile gets auth code -> it logs in to the API with the auth code. That's plenty of shit to do.
Are you guys the oauth provider as well? Also, are you able to do any of the flows other than auth code flow?
How are you trying to use oauth? Are you trying to call into a rest api that will then use oauth to access another resource? Or are you using oauth to protect the rest resource itself?
|
On August 17 2017 08:13 berated- wrote:Show nested quote +On August 17 2017 04:34 Manit0u wrote:On August 17 2017 03:44 Blucan wrote:On August 16 2017 23:04 Manit0u wrote:
Fuck me. Trying to introduce OAuth flow into REST only API is a fucking nightmare (and it has to support mobiles too). What are you having problems with? It's pretty straight forward once you get the hang of it. I'm not entirely sure where to redirect to after logging in to the IP since we have the authorization code grant flow. So mobile/web redirects to IP -> IP redirects it somewhere else -> web/mobile gets auth code -> it logs in to the API with the auth code. That's plenty of shit to do. Are you guys the oauth provider as well? Also, are you able to do any of the flows other than auth code flow? How are you trying to use oauth? Are you trying to call into a rest api that will then use oauth to access another resource? Or are you using oauth to protect the rest resource itself?
Our primary use case will be SSO since the customer already has all their employees registered at Okta (the IP). We want to use that to grab user info from there and create users within the API based on that. Auth code flow seemed the easiest to implement initially but I'm starting to have my doubts.
I mean, I've got everything handled on the API side (got an endpoint for auth codes which we exchange with IP for user info basically and then return our own token to services that use it). The problem is now getting web, desktop and mobile clients to get the code from the IP. Any suggestions? Do I have to put up some sort of auth server, to where I'll redirect users after logging in to the IP so it can return the code to the client as necessary?
It's generally one big API and all the other apps are pretty much different kinds of front-end for it and everything is using REST to communicate.
|
On August 17 2017 08:36 Manit0u wrote:Show nested quote +On August 17 2017 08:13 berated- wrote:On August 17 2017 04:34 Manit0u wrote:On August 17 2017 03:44 Blucan wrote:On August 16 2017 23:04 Manit0u wrote:
Fuck me. Trying to introduce OAuth flow into REST only API is a fucking nightmare (and it has to support mobiles too). What are you having problems with? It's pretty straight forward once you get the hang of it. I'm not entirely sure where to redirect to after logging in to the IP since we have the authorization code grant flow. So mobile/web redirects to IP -> IP redirects it somewhere else -> web/mobile gets auth code -> it logs in to the API with the auth code. That's plenty of shit to do. Are you guys the oauth provider as well? Also, are you able to do any of the flows other than auth code flow? How are you trying to use oauth? Are you trying to call into a rest api that will then use oauth to access another resource? Or are you using oauth to protect the rest resource itself? Our primary use case will be SSO since the customer already has all their employees registered at Okta (the IP). We want to use that to grab user info from there and create users within the API based on that. Auth code flow seemed the easiest to implement initially but I'm starting to have my doubts. I mean, I've got everything handled on the API side (got an endpoint for auth codes which we exchange with IP for user info basically and then return our own token to services that use it). The problem is now getting web, desktop and mobile clients to get the code from the IP. Any suggestions? Do I have to put up some sort of auth server, to where I'll redirect users after logging in to the IP so it can return the code to the client as necessary? It's generally one big API and all the other apps are pretty much different kinds of front-end for it and everything is using REST to communicate.
If it's with something like Okta (which full disclaimer, I know nothing about) , it seems like resource owner password is probably out of the question. If I was a user I wouldn't trust typing in my Okta creds into a third party app.
For any of the web clients, auth code flow sounds best as you said. There is definitely the ability to just redirect to their stuff and have it come back to yours.
It sounds like you're going towards where we ended up going for ours. If you are already generating a separate token to make future rest calls with, is it possible that they could acquire that through the web application as a pre-requisite? It would give you the ability to use oauth with the web client and then generate an api key that is associated with the user you created from the auth code flow.
As for desktop and mobile, my 5 minute search shows that okta has native clients for both of those. Can you leverage those some how?
|
On August 17 2017 12:06 berated- wrote:Show nested quote +On August 17 2017 08:36 Manit0u wrote:On August 17 2017 08:13 berated- wrote:On August 17 2017 04:34 Manit0u wrote:On August 17 2017 03:44 Blucan wrote:On August 16 2017 23:04 Manit0u wrote:
Fuck me. Trying to introduce OAuth flow into REST only API is a fucking nightmare (and it has to support mobiles too). What are you having problems with? It's pretty straight forward once you get the hang of it. I'm not entirely sure where to redirect to after logging in to the IP since we have the authorization code grant flow. So mobile/web redirects to IP -> IP redirects it somewhere else -> web/mobile gets auth code -> it logs in to the API with the auth code. That's plenty of shit to do. Are you guys the oauth provider as well? Also, are you able to do any of the flows other than auth code flow? How are you trying to use oauth? Are you trying to call into a rest api that will then use oauth to access another resource? Or are you using oauth to protect the rest resource itself? Our primary use case will be SSO since the customer already has all their employees registered at Okta (the IP). We want to use that to grab user info from there and create users within the API based on that. Auth code flow seemed the easiest to implement initially but I'm starting to have my doubts. I mean, I've got everything handled on the API side (got an endpoint for auth codes which we exchange with IP for user info basically and then return our own token to services that use it). The problem is now getting web, desktop and mobile clients to get the code from the IP. Any suggestions? Do I have to put up some sort of auth server, to where I'll redirect users after logging in to the IP so it can return the code to the client as necessary? It's generally one big API and all the other apps are pretty much different kinds of front-end for it and everything is using REST to communicate. If it's with something like Okta (which full disclaimer, I know nothing about) , it seems like resource owner password is probably out of the question. If I was a user I wouldn't trust typing in my Okta creds into a third party app. For any of the web clients, auth code flow sounds best as you said. There is definitely the ability to just redirect to their stuff and have it come back to yours. It sounds like you're going towards where we ended up going for ours. If you are already generating a separate token to make future rest calls with, is it possible that they could acquire that through the web application as a pre-requisite? It would give you the ability to use oauth with the web client and then generate an api key that is associated with the user you created from the auth code flow. As for desktop and mobile, my 5 minute search shows that okta has native clients for both of those. Can you leverage those some how?
The problem I'm currently having is that I'm not sure how to configure the apps to redirect to the right places. After logging in to Okta you're supposed to be redirected to the target web page (where Okta sends the user auth code) but our API does not have any front-end of its own so we can't do that (can't redirect from html to json seemlessly) and I'm not sure how to handle that. Any ideas?
If you are already generating a separate token to make future rest calls with, is it possible that they could acquire that through the web application as a pre-requisite?
No. The only way to acquire our token is to either log in as an existing API user or through Okta auth code. If you don't have API account and only Okta one you should be able to sign in using Okta (but we can't give you the token without first getting the auth code).
|
On August 17 2017 20:18 Manit0u wrote:Show nested quote +On August 17 2017 12:06 berated- wrote:On August 17 2017 08:36 Manit0u wrote:On August 17 2017 08:13 berated- wrote:On August 17 2017 04:34 Manit0u wrote:On August 17 2017 03:44 Blucan wrote:On August 16 2017 23:04 Manit0u wrote:
Fuck me. Trying to introduce OAuth flow into REST only API is a fucking nightmare (and it has to support mobiles too). What are you having problems with? It's pretty straight forward once you get the hang of it. I'm not entirely sure where to redirect to after logging in to the IP since we have the authorization code grant flow. So mobile/web redirects to IP -> IP redirects it somewhere else -> web/mobile gets auth code -> it logs in to the API with the auth code. That's plenty of shit to do. Are you guys the oauth provider as well? Also, are you able to do any of the flows other than auth code flow? How are you trying to use oauth? Are you trying to call into a rest api that will then use oauth to access another resource? Or are you using oauth to protect the rest resource itself? Our primary use case will be SSO since the customer already has all their employees registered at Okta (the IP). We want to use that to grab user info from there and create users within the API based on that. Auth code flow seemed the easiest to implement initially but I'm starting to have my doubts. I mean, I've got everything handled on the API side (got an endpoint for auth codes which we exchange with IP for user info basically and then return our own token to services that use it). The problem is now getting web, desktop and mobile clients to get the code from the IP. Any suggestions? Do I have to put up some sort of auth server, to where I'll redirect users after logging in to the IP so it can return the code to the client as necessary? It's generally one big API and all the other apps are pretty much different kinds of front-end for it and everything is using REST to communicate. If it's with something like Okta (which full disclaimer, I know nothing about) , it seems like resource owner password is probably out of the question. If I was a user I wouldn't trust typing in my Okta creds into a third party app. For any of the web clients, auth code flow sounds best as you said. There is definitely the ability to just redirect to their stuff and have it come back to yours. It sounds like you're going towards where we ended up going for ours. If you are already generating a separate token to make future rest calls with, is it possible that they could acquire that through the web application as a pre-requisite? It would give you the ability to use oauth with the web client and then generate an api key that is associated with the user you created from the auth code flow. As for desktop and mobile, my 5 minute search shows that okta has native clients for both of those. Can you leverage those some how? The problem I'm currently having is that I'm not sure how to configure the apps to redirect to the right places. After logging in to Okta you're supposed to be redirected to the target web page (where Okta sends the user auth code) but our API does not have any front-end of its own so we can't do that (can't redirect from html to json seemlessly) and I'm not sure how to handle that. Any ideas? Show nested quote +
If you are already generating a separate token to make future rest calls with, is it possible that they could acquire that through the web application as a pre-requisite?
No. The only way to acquire our token is to either log in as an existing API user or through Okta auth code. If you don't have API account and only Okta one you should be able to sign in using Okta (but we can't give you the token without first getting the auth code).
Have you researched openid connect with okta?
Edit: Maybe that's the wrong way, trying to read.
The problem is that I think it just doesn't work. What i was trying to suggest is generating some new token , a bearer token, or something that is not the oauth token. The issue here is you are trying to establish (or it sounds like) identification , not authorization.
Edit 2: Is this getting closer? https://security.stackexchange.com/questions/129928/oidc-flow-for-spa-and-restful-api
|
On August 18 2017 10:30 berated- wrote:Show nested quote +On August 17 2017 20:18 Manit0u wrote:On August 17 2017 12:06 berated- wrote:On August 17 2017 08:36 Manit0u wrote:On August 17 2017 08:13 berated- wrote:On August 17 2017 04:34 Manit0u wrote:On August 17 2017 03:44 Blucan wrote:On August 16 2017 23:04 Manit0u wrote:
Fuck me. Trying to introduce OAuth flow into REST only API is a fucking nightmare (and it has to support mobiles too). What are you having problems with? It's pretty straight forward once you get the hang of it. I'm not entirely sure where to redirect to after logging in to the IP since we have the authorization code grant flow. So mobile/web redirects to IP -> IP redirects it somewhere else -> web/mobile gets auth code -> it logs in to the API with the auth code. That's plenty of shit to do. Are you guys the oauth provider as well? Also, are you able to do any of the flows other than auth code flow? How are you trying to use oauth? Are you trying to call into a rest api that will then use oauth to access another resource? Or are you using oauth to protect the rest resource itself? Our primary use case will be SSO since the customer already has all their employees registered at Okta (the IP). We want to use that to grab user info from there and create users within the API based on that. Auth code flow seemed the easiest to implement initially but I'm starting to have my doubts. I mean, I've got everything handled on the API side (got an endpoint for auth codes which we exchange with IP for user info basically and then return our own token to services that use it). The problem is now getting web, desktop and mobile clients to get the code from the IP. Any suggestions? Do I have to put up some sort of auth server, to where I'll redirect users after logging in to the IP so it can return the code to the client as necessary? It's generally one big API and all the other apps are pretty much different kinds of front-end for it and everything is using REST to communicate. If it's with something like Okta (which full disclaimer, I know nothing about) , it seems like resource owner password is probably out of the question. If I was a user I wouldn't trust typing in my Okta creds into a third party app. For any of the web clients, auth code flow sounds best as you said. There is definitely the ability to just redirect to their stuff and have it come back to yours. It sounds like you're going towards where we ended up going for ours. If you are already generating a separate token to make future rest calls with, is it possible that they could acquire that through the web application as a pre-requisite? It would give you the ability to use oauth with the web client and then generate an api key that is associated with the user you created from the auth code flow. As for desktop and mobile, my 5 minute search shows that okta has native clients for both of those. Can you leverage those some how? The problem I'm currently having is that I'm not sure how to configure the apps to redirect to the right places. After logging in to Okta you're supposed to be redirected to the target web page (where Okta sends the user auth code) but our API does not have any front-end of its own so we can't do that (can't redirect from html to json seemlessly) and I'm not sure how to handle that. Any ideas?
If you are already generating a separate token to make future rest calls with, is it possible that they could acquire that through the web application as a pre-requisite?
No. The only way to acquire our token is to either log in as an existing API user or through Okta auth code. If you don't have API account and only Okta one you should be able to sign in using Okta (but we can't give you the token without first getting the auth code). Have you researched openid connect with okta? Edit: Maybe that's the wrong way, trying to read. The problem is that I think it just doesn't work. What i was trying to suggest is generating some new token , a bearer token, or something that is not the oauth token. The issue here is you are trying to establish (or it sounds like) identification , not authorization. Edit 2: Is this getting closer? https://security.stackexchange.com/questions/129928/oidc-flow-for-spa-and-restful-api
I've managed to implement auth code flow described in the answer to that stack overflow question pretty much exactly. The only problem I'm having is that I will now have to introduce a front-end endpoint in the API (I don't like it one bit) because I can't redirect users to the SPA after login (our SPA front doesn't have any real backend, it's pure JS/HTML with React so the API has to handle all of it, and obviously there's no way to redirect mobiles back to themselves).
|
Guys, have any of you worked in Denmark/are currently working there?
I've got a job offer from Copenhagen and I'm seriously considering it...
|
On August 23 2017 04:16 Manit0u wrote:
Guys, have any of you worked in Denmark/are currently working there?
I've got a job offer from Copenhagen and I'm seriously considering it...
I've never worked in Denmark but I did just accept my second job, 9 yrs at job one and now moving on. Feels like as good of a time as any!
|
On August 23 2017 04:16 Manit0u wrote:
Guys, have any of you worked in Denmark/are currently working there?
I've got a job offer from Copenhagen and I'm seriously considering it...
Beer is REALLY expensive in those countries. (Scandinavian) So watch out for that, otherwise why the hell would you not take this job?
|
On August 23 2017 07:31 IyMoon wrote:Show nested quote +On August 23 2017 04:16 Manit0u wrote:
Guys, have any of you worked in Denmark/are currently working there?
I've got a job offer from Copenhagen and I'm seriously considering it... Beer is REALLY expensive in those countries. (Scandinavian) So watch out for that, otherwise why the hell would you not take this job?
Such decisions are not that easy once you're married with children. There's a gazillion things I have to think about now...
|
|
|
On August 23 2017 15:25 Nesserev wrote:Show nested quote +On August 23 2017 08:43 Manit0u wrote:On August 23 2017 07:31 IyMoon wrote:On August 23 2017 04:16 Manit0u wrote:
Guys, have any of you worked in Denmark/are currently working there?
I've got a job offer from Copenhagen and I'm seriously considering it... Beer is REALLY expensive in those countries. (Scandinavian) So watch out for that, otherwise why the hell would you not take this job? Such decisions are not that easy once you're married with children. There's a gazillion things I have to think about now... So, what are some of the aspects that make you 'consider' it? All I can say is: Write down the positives and the negatives; weigh them, and compare them, don't be too limiting and always be honest to yourself and your family.
I did just that. The only real problem is that for this particular job I have to decide within a week and I simply can't do that (it'll take me more than that to leave my current job if I want to do it properly) so it's a no go for now. Maybe in the near future...
![[image loading]](http://asset-d.soupcdn.com/asset/13763/2020_d500_600.jpeg)
|
|
|
Looking to do a bit of GUI programming in python, any recommended frameworks?
|
|
|
|
|
|
EPT
