Still working on the space most likely in east side (as usual).
As always, please RSVP and provide suggestions for what the agenda can be.
The breakout mode worked real well.
Join or login to comment.
To anyone in Eugene's group on the prefix tree:
I was trying to remember the code we wrote for traversing the tree and summing. All of the code that I have found for traversing trees looks more complicated than what we had. Did we have some simplifying assumptions to make it easier? Did anyone write down the code? Could you post it? I'd love to look at it.
0 · August 28, 2013
Hey Maria, The day after our meetup, i coded it up. here it is. http://pastebin.com/5...
Could you show any of the code samples you're looking at, Maria? We did, in a way, make some simplifying assumptions. We implemented the true in a space-inefficient way, and we also assumed a small fixed alphabet (a-z). If you have a large alphabet for which you cannot allocate a full array, or if you need to use a space-efficient implementation, the logic may be more complicated.
Thanks crime7. I don't think you actually implemented the part where we were trying to find the longest common prefix, though. So, my question is, in order to find the max, you need to keep track of the depth, so how do you keep track of this as you go down and back up the tree? In the code where you are looking for a match to your prefix, you can use recursion to go down the correct branch, since you know the letters you are looking for, and you don't need to go back up, but if you want to search the whole tree, this is clearly not enough. I believe it had to do with giving the whole alphabet as a search string, as well as having some sort of whose-my-parent sort of logic somewhere, but not sure about this. Eugene, I was just looking on wikipedia about searching trees generally.
Were you searching prefix trees specifically? There's a difference between binary search trees and prefix trees (tries). Binary search trees are generally much more complicated if they have logic for re-balancing to maintain a low tree height. Tries need no re-balancing.
Are you wondering about the logic to simply traverse a trie recursively, or the logic that we used in the problem we discussed to find the maximum payoff prefix once you already know the maximum cost?
Just trying to traverse and keep track of the depth at this point. Why would you re-balance a tree during a search? Wouldn't this just be something you would do during insert or removal? http://en.wikipedia.o...
I think it was we assumed that we had parent pointers, so this made it simpler.
Sounds interesting! Say...could someone post the problem you were solving, so those of us in the other groups could try it? ;-)
0 · August 29, 2013
Yes, re-balancing is done only when inserting or removing. I just thought you might have looked at a full implementation of binary trees.
To traverse and keep track of the depth, we just called the traversal recursively on each child tree with a depth parameter of depth+1. Our recursive traversal method explicitly took a depth parameter. So if we called the traversal method with parameters of (node, depth), we made calls to traversal (node.children[i], depth + 1). You do not need parent pointers simply to traverse the tree if you're willing to use recursion.
Now, upon finding a target node, how to recover the path to it is a little tougher. We ran out of time for this in the meetup and did not discuss this aspect fully. There are at least three possible ways to do it. One possibility is to, like you said, include parent pointers in each node. Then you can simply create an array of size "depth" and follow the path back to the root, storing the characters you encounter on this path into the array in reverse order.* Alternatively, you could have been maintaining an explicit stack during the traversal, and now you would just pop off all the elements in your stack into an array of size "depth" that you would fill in reverse order. A third possibility would be to do some tricks with recursion to do the same as the previous approach while not requiring an extra stack in addition to the call stack.
* I'm assuming you're including the character that the node represents in each node. If you're not (because that information is redundant and we did not include it in the meetup), then on the way up, you need to search each parent in turn for the child you just came from. This will reveal to you what position the child was in, and therefore what letter it represented.
@Pat: The problem was taken from here http://www.careercup.... . The problem is not stated very clearly, so I restated it in my answer posted on that page, giving it what I thought to be the most plausible interpretation. Read my (eugene.yarovoi) answer on that page for the clarified problem statement and a high-level overview of a solution that uses prefix trees. We discussed that solution in a lot more detail (and some code) in the meetup.
Thanks, Eugene!! And thanks for pointing out the careercup site!
Meetup was great! Special thanks to Eugene for explaining Tries extremely well.
0 · August 26, 2013
Excellant -- great group and white board discussions were most helpful.
Great collaboration on design questions from actual recent interviews.
0 · August 25, 2013
Good meetup. Thanksfor organizing!
I learned something, so that was good!
1 · August 25, 2013
Have you reserved a meeting room in Bellevue Regional Library? What's room number?
Room: Room 1Library: Bellevue LibraryDate(s: Sunday, August 25, 2013Time: 6:00 PM to 8:00 PM
>how to successfully answer questions related to current project problems during final round while making a lateral move.>How to break down a coding question into right datastructure/algorithm and use white board judiciously. >How to avoid complicating solutions.>What are the coding etiquette required while using whiteboard/collabedit>How to break down a OOPs question into a datamodel, software design which is simple as well.
0 · August 21, 2013
Thoroughly enjoyed previous event. Discussions were very technical and helped me a lot in understanding depth of problems as well as expectations of companies. Eagerly looking forward to the next event !! many many thanks to the organizers.
2 · July 30, 2013
Help support your Meetup
This is a Meetup Group to get together and solve interview questions, refine interview strategies and exchange tips to enable us to crack technical interviews.
We have a new website - http://www.seattletechinterviews.com/ please take a look to know more about us.
2,680 Android Developers
1,218 Web App Devs
935 Spark Enthusiasts
7,788 New Techies and Friends
Meetup has allowed me to meet people I wouldn't have met naturally - they're totally different than me.
— Allison, started Women's Adventure Travel
Meetup members, Log in