谷歌 New Grad 店面

  • Google New Grad
  • Less than 1 year of exp

I got a phone screen question like this.
Some constraints:

  • Board could be any size
  • words must be 3 or more letters
  • may move to any 8 adjacent letters

I solved with the first solution https://www.geeksforgeeks.org/boggle-find-possible-words-board-characters/

Follow-up with Trie but only verbal. No code needed. https://www.geeksforgeeks.org/boggle-set-2-using-trie/

I was confused about time & space complexity.
I said time : O(cols * rows) ^ max(len(word)) where word is in dictionary.
space : O(cols * rows).

Not sure if it’s correct.

Can you guys please correct me? Thanks!

where is the question?

这个吧

leetcode的word search

补充一个:

Given a complete(virtual) binary tree, return true/false if the given target node exists in the tree or not.
Here, the “virtual” means the tree nodes are numbered assuming the tree is a complete binary tree.

For example:

                1
		    /        \ 
		 2              3
       /   \           /  \ 
     4   (5)nil      6  (7)nil

//function signature
// bool doesNodeExist(root *TreeNode, target int)
doesNodeExist(root, 4) -> true
doesNodeExist(root, 7) -> false, Given the node on #7 is a nil node.

//Level order traversal solution, numbering the left(2n+1) and right(2n+2) children node is a trivial solution(time O(n)/O(target) and space O(n)/O(target)).
//Think of a better solution.

My solution using binary string:
Binary String represents the path from root to the node, where ‘1’ means going right and ‘0’ means going left.
For example, 4 = “100”, starting from the index 1, we go from root = 1, going left --> 2, going left --> 4;
7 = “111”, starting from index 1, we go from root = 1, going right --> 3, going right --> 7.

    public boolean doesNodeExist(TreeNode root, int id) {
        if (id <= 0) return false;
        char[] binary = Integer.toBinaryString(id).toCharArray();
        for (int i = 1; i < binary.length; i++) {
            if (root == null) return false;
            if (binary[i] == '0') root = root.left;
            else root = root.right;
        }
        return root != null;
    }