naraink@andrew.cmu.edu
BAN USERS = string containing dir list
L = S.split('\n')
answer = 0
ancestor_list = []
prev_indents = 0
for line in L:
if (line.numIndents() < prev_indents){
ancestor_list = first line.numIndents() elements of ancestor_list
}
if (line is an image file){
answer += (total combined length of all stings in ancestor_list % 1000000007)
}
add ("/" + line.getTextWithoutIndents) to ancestor_list
prev_indents = line.numIndents()
return answer
//Note: there are many different ways to check the total combined length of the strings in ancestor_list that are O(1), such as storing the partial length sums in a separate array.
S is the string of numbers
best = what you get when you replace first two digits with highest
for i in xrange(0, len(S) - 1):
x = what you get when replace i and i+1th digit with highest
if (x < best): best = x
return best
At each node in the BST, store the order value at that node ( the 4th smallest node in the tree stores 4, the smallest stores 1, etc.) according to the ordering on the BST. Then, for a interval range (i,j), i <= j, navigate to the smallest element great than i. Let this element's order value be A. Navigate to the largest element less than j and let it's order value be B. Return B - A.
- naraink@andrew.cmu.edu August 05, 2016Note: If we use a balanced BST (Treap, AVL Tree) this solution is O(log(n)). Otherwise the solution is O(n).