Monitor locks to acquire and release. A stack and set based question

Determine if there is a deadlock given order of starting and joining threads

questions were easy to solve 2d array question and classes-based callback function creation question. The follow-up questions were difficult. Optimal solution was answered but then the question was changed to cache topic and then I was asked how to optimize if we want to use cache. The question was 2d array in form of balanced binary tree and the last row decides if the root will be 1/0. If both children are 1 only then parent is 1 otherwise 0. For this cache was used later and I was asked to optimize it. We agreed till log(n) time complexity but the interviewer wanted something else.