CareerCup

Note that the trie is not even needed. The suffix can be calculated incrementally.

public static String reverse(String s) {
        return new StringBuilder(s).reverse().toString();
    }

    public static String getSuffix(Set<String> words) {
        String suffix = null;
        for (String word : words) {
            word = reverse(word);
            if (suffix == null) {
                suffix = word;
            } else {
                int suffixLength;
                for (suffixLength = 0; suffixLength < Math.min(word.length(), suffix.length()); ++suffixLength) {
                    if (word.charAt(suffixLength) != suffix.charAt(suffixLength)) {
                        break;
                    }
                }
                suffix = suffix.substring(0, suffixLength);
            }
        }
        return reverse(suffix);
    }

I think for longest common substring, a generalized suffix tree is good enough. The stamp boxes problem was confusing... Not sure what it means. But it sounds like the Knapsack problem? Could you give me an example? For the one with BST, what exactly is x1,x2 and etc in the output you demonstrated x1<x2>x3<x4>x5? The position I am interviewing for is SDE, but the questions should be similar to SET except for coming up with test scenarios I guess.

Why would we want to delete all nodes that are not being traversed and all successors? I don't follow here. May I ask what other two questions they asked you?

Do you think careercup is more helpful or glassdoor?

I think for longest common substring, a generalized suffix tree is good enough. The stamp boxes problem was confusing... Not sure what it means. But it sounds like the Knapsack problem? Could you give me an example? For the one with BST, what exactly is x1,x2 and etc in the output you demonstrated x1<x2>x3<x4>x5? The position I am interviewing for is SDE, but the questions should be similar to SET except for coming up with test scenarios I guess.

Yeah it's (almost like) the knapsack problem
For instance, the stamp denominations are -
7
11
15

If we want stamps amounting to 25 - We do 11 + 15 = 26 instead of 11 + 11 = 24 or 15 + 15=30
If we want stamps amounting to 20 - We do 7 + 7 + 7 = 21 instead of 7 + 15 = 22 or 11 + 11 = 22 or 11 + 7 = 18

x1, x2 etc are values of nodes in the BST. Basically, just print values of all nodes in the BST in that form. Does that make sense?

x1, x2 etc are values of nodes in the BST. So just do in-order traversal with < and > at the right place? Did you actually get asked the same question posted in here?

Yes, it may be simple, but this stamp problem and the x1, x2,.. problem were asked in my interviews. 100% certain about that :). I have hazy memories of other questions so I did not mention them here, but swear to god these are exactly what were asked. The x1,x2 one was not the only question in its interview, but the knapsack problem was the only question in its interview. There were testing questions after the coding for the knapsack one.

I am interviewing with amazon and google again very soon. Hope I won't get owned... You seem very knowledgeable. Should not be a problem.

wait, so if the BST looks like
5
/ \
3 7
/ \ /\
1 4 6 8
The output is 1<3>4<5>6<7>8 ?

I really doubt you will get owned. You seem like a very strong dev. In my 5 years at Microsoft, I have worked with some great developers and I can sense it when someone is good. You should be able to own them :). All the best! And thank you for your kind words.

Actually, this

8 1 7 3 6 4 5

I remember solving it by putting equal(or differing by one) number of elements into 2 queues and popping them one by one.

so for your example, my 2 queues were

1 3 4 5
8 7 6

pop them alternately. The second array can also be 6 7 8 depending on the way you traverse. so the popping would be from end in that case. This will work for unbalanced trees with equal number of nodes(or just 1 different) in each queue.

I think that's how I did it.

Hey wait, i think you can just use one array containing the inorder traversal of the bst and pop from each end at a time. wth. i think i just over complicated it in that solution.

Yeah, these questions were not very difficult. You can easily do these. It happens to me sometimes where I get asked an interview question and I overestimate the difficulty and complexity of the question. That's how I come up with non trivial solutions for trivial questions. I am trying to overcome that.

Yeah, that is what I would do too. Run two in-order traversals one in ascending order and one in descending order and put each node on a queue. Then pop one node at a time until reach to the root. But what if the left subtree and right subtree do not have the same height?

I think a simpler approach would be to just store the in-order traversal of the whole tree in one single array and pop one at a time from each side of the array.

I did the 2 array approach in the interview though. Not sure why I did that when I could have used just one array. May be I overestimated the question and tried to do something complicated. :)

But like you asked, when the tree is unbalanced, you will get one array smaller than the other. You just pop elements from the smaller to the larger array until they are even in size.

@bp Actually, why would the output be 8 < 1 > 7 < 3 > 6 < 4 > 5 ? All the < and > don't seem to make sense.

Shouldn't it be like 1<4>3<5>7<8>6 ?