DRW On-Site

Question 1

Find all unique path’s in a binary tree

Answer 1

public List binaryTreePaths(TreeNode root) {
List answer = new ArrayList();
if (root != null) searchBT(root, “”, answer);
return answer;
}
private void searchBT(TreeNode root, String path, List answer) {
if (root.left == null && root.right == null) answer.add(path + root.val);
if (root.left != null) searchBT(root.left, path + root.val + “->”, answer);
if (root.right != null) searchBT(root.right, path + root.val + “->”, answer);
}

Question 2

explain tree map

Answer 2

TreeMap is sorts its keys in ascending order. It is not synchronized

Question 3

Find ways to seat a family on a plane

Answer 3

…

Question 4

What is closure?

Answer 4

A stateful function. Gives you acces to an outer function’s scope from an inner function.

Question 5

How are elements in a hash table stored in memory?

Answer 5

They’re stored in an array. The hash function computes the index to store the value.

Question 6

Sorting questions

Answer 6

…

Question 7

Give an integer n find how many digits 11^N are ‘1’

Answer 7

def elevenToPowerOf(n):
    # Anything to the zero is 1.

if n == 0: return "1"

    # Otherwise, n  1:
        n = n - 1

    # Make multiply by eleven easy.

    ten = num + "0"
    num = "0" + num

    # Standard primary school algorithm for adding.

        newnum = ""
        carry = 0
        for dgt in range(len(ten)-1,-1,-1):
            res = int(ten[dgt]) + int(num[dgt]) + carry
            carry = res // 10
            res = res % 10
            newnum = str(res) + newnum
        if carry == 1:
            newnum = "1" + newnum

    # Prepare for next multiplication.

    num = newnum

# There you go, 11^n as a string.

return num

Question 8

Given a tree with each node holding an integer. Find the most unique number of any path

Answer 8

// A node of binary tree
struct Node {
    int data;
    struct Node *left, *right;
};

// A utility function to create a new Binary
// Tree node
Node* newNode(int data)
{
    Node* temp = new Node;
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}

int largestUinquePathUtil(Node* node, unordered_map m)
{
    if (!node)
        return m.size();

    // put this node into hash
    m[node->data]++;

int max_path = max(largestUinquePathUtil(node->left, m),
                   largestUinquePathUtil(node->right, m));

    // remove current node from path "hash"
    m[node->data]--;

// if we reached a condition where all duplicate value
// of current node is deleted
if (m[node->data] == 0)
    m.erase(node->data);

return max_path; }

// A utility function to find long unique value path
int largestUinquePath(Node* node)
{
    if (!node)
        return 0;

    // hash that store all node value
    unordered_map hash;

    // return max length unique value path
    return largestUinquePathUtil(node, hash);
}

Question 9

Given an integer. If that number was represented in binary. How many bits would be set to ‘1’

Answer 9

Convert this number to its string binary representation then loop through. Or if you cannot convert it to one.

Question 10

Write a function that gets the number of squares between two numbers

Answer 10

static int countSquares(int a, int b)
{
int cnt = 0; // Initialize result

        // Traverse through all numbers
        for (int i = a; i <= b; i++)

        // Check if current number 'i' is perfect
        // square
        for (int j = 1; j * j <= i; j++)
            if (j * j == i)
                cnt++;
    return cnt;
}

Question 11

Difference between hashtable and hashmap

Answer 11

Hashtable is synchronized. Better for multi threading. Does not allow null keys
HashMap is not synchronized. Better for non threaded applications. Allows one null key