Clay Schubiner
BAN USERYou're right; I forgot that we knew the size of the left and right subtrees. Without that information, my solution is optimal :)
 Clay Schubiner June 20, 2014Here'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

Clay Schubiner
June 20, 2014 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())

Clay Schubiner
June 19, 2014 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
 Clay Schubiner June 19, 2014Arrange 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[i1]:
ladduArr[i] = max(ladduArr[i1], 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

Clay Schubiner
June 19, 2014 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

Clay Schubiner
June 18, 2014 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, v1, index + v  1) or canCrossHelper(path, v, index + v):
return True
return False
def canCross(path):
return canCrossHelper(path, 1, 0)

Clay Schubiner
May 26, 2014
RepTristaRJohn, Reverse Engineering and System Developer at BT
I am an Ophthalmic medical assistant in bluefield USA, I assist in retinal exams and procedures. Referred patients to outside ...
RepTinaaJohn, Cloud Support Associate at AMD
Hi,Everyone.I am an art teacher at Woodson Institute.Foster and encourage critical thinking and analysis about art and ...
RepI am Ricky from the USA. I am 29 year old. I am doing a job. I am doing a ...
RepJenniferSRoe, Android test engineer at Accolite software
I am Jennifer from Dublin. I am Photographer, I have experienced in all different kinds of photography Strong aesthetic sense ...
Repjessicajbunting, Aghori Mahakal Tantrik at ABC TECH SUPPORT
Hi I am Jessica, from Houston USA. I am working as a manager in Incredible Universe company. I enjoy additional ...
Repkevinlmoses, Animator at Accenture
I am Experienced Building Manager who is an expert in public and industrial safety with a preventative mindset against fire ...
RepSherriMooney, Network Engineer at Arista Networks
I am not a model but as a photographer, I can't see how one could call it fun. Matter ...
Repjohnagragg0, cox customer service at Deloitte Consulting LLP
I am friendly, I am a hard worker, even through difficult circumstances, I want to know about How to identify ...
Repmitadwilson, Scientific Officer at Cleartrip.com
Hello, I am Mita from Dayton, I am working as a Systems programmer in Evans company, I have Experience of ...
Repmarisamsan7, Cloud Support Associate at ADP
Hi, I am Photoengraver from an CO,USA. I am a girl with a strong desire to travel the world ...
Repfloydmsnyder, Theoretical mathematician at STM Auto Parts
As a Theoretical Mathematician,I’m little more interested in the theory involved with mathematics. In my free time , I ...
Repannavhedge4, AT&T Customer service email at ABC TECH SUPPORT
Hi everyone, I am from Worcester,USA. I currently work in the Argus Tapes & Records as Scientific illustrator . I love ...
Open Chat in New Window
Here's a simple O(n) solution in Python:
 Clay Schubiner July 06, 2014