CareerCup

Here's a simple O(n) solution in Python:

def highestPosProduct(arr):
    if len(arr) < 3: return None
    a = quickselect(arr, len(arr) - 1)
    b = quickselect(arr, len(arr) - 2)
    c = quickselect(arr, len(arr) - 3)
    d = quickselect(arr, 1)
    e = quickselect(arr, 0)
    return max(a * b * c, a * b * e, a * d * e)

You're right; I forgot that we knew the size of the left and right subtrees. Without that information, my solution is optimal :)

Here's a simple solution in Python. Runs in O(n) time, which is asymptotically optimal.

def numNodesBetweenValues(root, lowVal, highVal):
    if root is None:
        return 0

    ret = 0
    if lowVal < root.val:
        ret += numNodesBetweenValues(root.left, lowVal, highVal)

    if lowVal <= root.val and highVal >= root.val:
        ret += 1

    if highVal > root.val:
        ret += numNodesBetweenValues(root.right, lowVal, highVal)

    return ret

True. Added memoization:

def canCrossHelper(path, vp, answersArr):
    if vp[1] >= len(path):
        return True
    if vp[0] <= 0:
        return False
    if path[vp[1]] == False:
        return False

    tup = (vp[0] + 1, vp[1] + vp[0] + 1)
    if tup not in answersArr:
        answersArr[tup] = canCrossHelper(path, tup, answersArr)

    tup2 = (vp[0], vp[1] + vp[0])
    if tup2 not in answersArr:
        answersArr[tup2] = canCrossHelper(path, tup2, answersArr)

    tup1 = (vp[0] - 1, vp[1] + vp[0] - 1)
    if tup1 not in answersArr:
        answersArr[tup1] = canCrossHelper(path, tup1, answersArr)

    if answersArr[tup] or answersArr[tup1] or answersArr[tup2]:
        return True
    return False

def canCross(path):
    return canCrossHelper(path, (1,0), dict())

No. If you arrange 1,2,3 as 1, 3, 2 then you can give them 1, 2, 1 laddu, so 4 total.

5,1,2,1,5 can be arranged as 1, 5, 1, 5, 2. You'd give them 1,2,1,2,1 laddu, so 7 total.

5,0,2,1,5,6 can be arranged as 0, 6, 1, 5, 2, 5. You'd give them 1, 2, 1, 2, 1, 2 laddu, so 9 total.

This is still incorrect. You can arrange 1, 3, 7, 5 as 1, 7, 3, 5 and give them 1, 2, 1, 2 laddu, so 6 laddu total. My python solution above works for this input; check it out

Arrange students by putting the lowest ranked one first, then the highest, then the second lowest, then the second highest, and so on.

# Input is an array of the children's rankings
def getNumLaddus(arr, numStudents):
    arr = sorted(arr)

    first = arr[:numStudents/2]
    second = list(reversed(arr[numStudents/2:]))
    arr = list()
    for i in xrange(numStudents):
        if i % 2 == 0 and i/2 < len(first):
            arr.append(first[i/2])
        else:
            arr.append(second[i/2])

    ladduArr = [1] * numStudents
    for i in xrange(1, numStudents - 1):
        if arr[i] > arr[i+1] or arr[i] > arr[i-1]:
            ladduArr[i] = max(ladduArr[i-1], ladduArr[i+1]) + 1
    if arr[0] > arr[1]: ladduArr[0] = ladduArr[1] + 1
    if arr[-1] > arr[-2]: ladduArr[-1] = ladduArr[-2] + 1

    return sum(ladduArr)

print getNumLaddus([1,2,2], 3) # Outputs 4
print getNumLaddus([1,2,3], 3) # Outputs 4
print getNumLaddus([5,1,2,1,5], 5) # Outputs 7
print getNumLaddus([5,0,2,1,5,6], 6) # Outputs 9

This doesn't work exactly.

With your solution, students ranked 1, 2, 2 will be arranged as 2,1,2, which means we'd have to use 5 laddu to satisfy the requirement.

You'll find my answer in a comment below. Let me know what you think

Not too hard. Using Python and simple set intersection, we arrive at the optimal O(k) answer where k is the total length of all of the strings.

from sets import Set
def getCommonCharCount(arr):
    s = Set(arr[0])
    for str in arr:
        s = s & Set(str)
    return len(s)

print getCommonCharCount(['aghkafgklt', 'dfghako', 'qwemnaarkf']) #outputs 3

Here's a solution is python. Pretty easy to understand

def canCrossHelper(path, v, index):
    if index >= len(path):
        return True
    if v <= 0:
        return False
    if path[index] == False:
        return False
    if canCrossHelper(path, v+1, index + v + 1) or canCrossHelper(path, v-1, index + v - 1) or canCrossHelper(path, v, index + v):
        return True
    return False

def canCross(path):
    return canCrossHelper(path, 1, 0)