Detailed feedback on refdash website:
Coding summary (3.5/4.0):
Very solid coding skills. The candidate was able to independently code 3 solutions in one hour. They paid especial attention to detail and made sure to not miss any edge case. They tested their code which is very appreciated.

During the first problem (Longest Palindromic Substring) their solution was a little bit messy but they were able to simplify it once pointed out.

Algorithm and Data Structures summary (3.6/4.0):
The candidate showed an outstanding understanding of data structures and algorithms. They asked very relevant clarification questions and were able to walk through the three problems, proposing various solutions and correctly articulating their trade offs. The candidate accurately described the time and space complexity for every approach. They even went into describing how to solve the last problem using a variation of a Segment Tree data structure, called Heavy Light Decomposition. Outstanding!

Overall summary (3.5/4.0):
Excellent performance overall. The candidate independently solved 3 problems in a one hour frame. Their code was mostly clean and their communication was clear and consistent through the interview.


// Interview board starts here
Martin Copes
mcopes73@gmail.com

Yelp
Palantir


            10
      4     5      6
    1    2         7

public class SecurityTree{

    void grantAccess(TreeNode n);
    void revokeAccess(TreeNode n);
    boolean hasAccess(TreeNode n);
}
grantAccess(10)
revokeAccess(4)
hasAccess(1) <-- false


Another solution:
Heavy-Light Decomposition
    2->10
    segment tree on a path, [1, 4, 10]
             max query INT_MIN, 1, 2
                                    ^
                            O(log (number of nodes) * log(path length))

initially all nodes are woth access denied.

revokeAccess(4)
grantAccess(10)

int currentTime = 3
bool access = 0;
int updateAt;
[1].access=0, updatedAt = INT_MIN
[4].access=0, updatedAt = 1, currentUpdatedTime = 1
[10].access=1, updatedAt = 2, updatedAt > currentUpdatedTime

grantAccess(10)
revokeAccess(4)

[1].access=0, updatedAt = INT_MIN
[4].access=0, updatedAt = 2
[10].access=1, updatedAt = 1

grantAccess O(1)
revokeAccess O(1)
hasAccess O(h)

struct TreeNode {
    bool hasAccess = false;
    TreeNode *parent;
    int updatedAt = INT_MIN;
};

int currentTime = 0;

void grantAccess(TreeNode *root) {
    root->hasAccess = true;
    updatedAt = currentTime++;
}

void revokeAccess(TreeNode *root) {
    root->hasAccess = false;
    updatedAt = currentTime++;
}

bool hasAccess(TreeNode *root) {
    int latestUpdate = INT_MIN;
    bool access = false;
    while(root!=NULL) {
        if(root->updatedAt > latestUpdate) {
            latestUpdate = root->updatedAt;
            access = root->updatedAt;
        }
        root = root->parent;
    }
    return access;
}

Given a Binary Search Tree that contains positive integers,
return the length of the longest path from root to a leaf
such that the leaf is a dead end.

A leaf is considered a dead end
if and only if we are not able to insert any element after that node
without causing a duplicate in the tree.


                10
        8                15
            9

Ans ---> 3


                10
        8                15
    5       9
  1

  node, lowerbound, upperbound, depth
  10, INT_MIN, INT_MAX, 1
  8, INT_MIN, 10, 2
  5, INT_MIN, 8, 3
  1, INT_MIN, 5, 4

  9, 8, 10, 3 <-- max = 3

  Time Complexity: O(n)
  Space Complexity: O(maxiumHeight)

int maximumHeight = 0;

void findLongestPathHelper(TreeNode *root, int lowerBound, upperBound, int depth) {
    /*
        1. Check if it is a leaf, check if it's also a dead-end node
        2. Traverse left
        3. Traverse right
    */
    if(root == NULL) return;

    if(root->left == NULL && root->right == NULL) {
        // this is a leaf
        if(upperBound-lowerBound == 2) {
            // this is a dead-end node
            maximumHeight = max(maximumHeight, depth);
        }
        return;
    }

    findLongestPathHelper(root->left, lowerBound, root->value, depth+1);
    findLongestPathHelper(root->right, root->value, upperBound, depth+1);
}

int findLongestPath(TreeNode *root) {
    maximumHeight = 0;
    findLongestPathHelper(root, INT_MIN, INT_MAX, 1);
    return maximumHeight;
}

daadbc

dadbc ---> dad
  ^
    left = i, right = i+1



pair<int,int> expand(string &str, int left, int right) {
    // while str[left] == str[right], expand

    while(left >= 0 && right < str.size() && str[left]==str[right]) {
        left--;
        right++;
    }
    return make_pair(left+1, right-1);
}

string findLongestPalindrome(string &str) {
    if(str.empty()) return str;
    /*
        1. for every index i,
        2. set left and right to i // for odd length
        3. or set left to i and right to i+1 // for even length
        4. expand around the center
        5. keep storing the max
    */
    int longetPalindrome = 0, startIndex, endIndex;

    for(int i = 0; i < str.size(); i++) {
        // odd length
        int left = i, right = i;
        pair<int, int> palindromeBoundary = expand(str, left, right);
        int lengthOfPalindrome = palindromeBoundary.second - palindromeBoundary.first + 1;
        if(lengthOfPalindrome > longestPalindrome) {
            longestPalindrome = lengthOfPalindrome;
            startIndex = palindromeBoundary.left;
            endIndex = palindromeBoundary.right;
        }

        // even length
        left = i, right = i+1;
        palindromeBoundary = expand(str, left, right);
        lengthOfPalindrome = palindromeBoundary.second - palindromeBoundary.first + 1;
        if(lengthOfPalindrome > longestPalindrome) {
            longestPalindrome = lengthOfPalindrome;
            startIndex = palindromeBoundary.left;
            endIndex = palindromeBoundary.right;
        }
    }

    // build the palindrome string
    string palindrome;
    for(int i = startIndex; i <= endIndex; i++) palindrome += str[i];
    return palindrome;
}

daadbc
i = 0
left = 0, right = 0
left = -1, right = 1, left = 0, right = 0, return {0, 0}
left = 0, right = 1, return {1, 0}, length = 0-1+1 == 0

i = 1
left = 1, right = 1
left = 0, right = 2, left = 1, right = 1 return {1, 1}, length = 1

left = 1, right = 2
left = 0, right = 3,
left = -1, right = 4, left = 0, right = 3, return {0, 3}, length = 4