whatevva'
BAN USERThe question asks for "maximum" number of duplets/triplets and also specifies that number included once cannot be used again. Considering this, I would modify the solution provided by "Westlake" as below:
Divide the numbers into 3 groups:
A = { x  x % 3 == 0}, P = A
B = { x  x % 3 == 1}, Q = B
C = { x  x % 3 == 2}, R = C
To maximize count, we should try to have as may duplets as possible:
Number of duplets from set A = int(P/2) ; combine pairs of elements of A
Number of duplets from Set B,C = min(Q, R) ; combine one element of B with one element of C
If Q>R, then there will be left over elements in Q and viceversa; These can be combined as triplets
Number of triplets = int(abs(QR)/3)
Any other left over elements of A, B, C cannot be combined to a multiple of 3 anymore.
Max count = int(P/2) + min(Q,R) + int(abs(QR)/3)

whatevva'
February 03, 2014 If we plot (i, arr[i]) on a graph and assuming that these points are collinear, then this solution works only if the slope of this line is >1. It does not consider the case when the slope of this line is positive but less than 1. The fact that the array is sorted in ascending order just says that the slope is positive .. it could be either >1 or < 1.
I think the code needs to be modified as follows:
public static int findIndex(int[] arr) {
int l = 0;
int r = arr.length  1;
while (l <= r) {
int m = l + (r  l) / 2;
if (arr[m] == m) {
return m;
}
if ( ((arr[r] > r) && (arr[m] > m)) 
((arr[r] < r) && (arr[m] < m)) ) {
r = m  1;
} else {
l = m + 1;
}
}
return 1;
}

whatevva'
February 03, 2014 Like Alexey mentioned below, this doesn't work. Downvoting so it doesnt show up as top voted result (which it currently does)
"a = new int[] { 1, 2, 3,4,5,7,8,9,10 };
b = new int[]{1,20,30,40,50,60,70,80,90,100};
doesnt work
Also, k can be up to n^2, so the first double loop can take n^2
 Alexey on December 18, 2013  Flag"
Solution in python
import re
def numVowels(line):
count = 0
for c in line:
if re.search("[aeiou]", c):
count += 1
return count
def bestScoreLine(fileName, scoreFunction):
f = open(fileName)
bestLine = None
bestScore = None
for line in f:
curScore = scoreFunction(line)
if bestLine is None:
bestLine = line
bestScore = curScore
elif curScore > bestScore:
bestLine = line
bestScore= curScore
return bestLine
## MAIN
print bestScoreLine("test.txt", numVowels)
print bestScoreLine("test.txt", len)
test.txt
abcdef
ab
abcdefghik
abcdefghkhllj
aeiouseiou
OUTPUT
aeiouseiou
abcdefghkhllj

whatevva'
December 18, 2013 Solution in Python. Essentially finding every combination of elements in the given list through a DFS Tree traversal ... finding sum at the leaf node and printing if sum==N
def combinationsDFS(myList, i, N, sumSoFar, ResultSoFar):
if i >= len(myList):
if (sumSoFar == N):
print [ i for i in range(len(myList)) if ResultSoFar[i]]
return
for child in [True, False]:
combinationsDFS(myList, i+1, N, sumSoFar+myList[i] if child is True else sumSoFar, \
ResultSoFar+[child])
return
## MAIN
combinationsDFS([1, 1, 2, 2, 4], 0, 4, 0, [])
## OUTPUT
[0, 1, 2]
[0, 1, 3]
[2, 3]
[4]

whatevva'
December 17, 2013 Actually, there are 4 matches for "sachin" and not 3 as the question says.
def DFS(M, x, y, s, MatchSoFar):
if x >= len(M) or y >= len(M[0]) or M[x][y] != s[0]:
return 0
## s[0] matched; if this is the only character in string
## then there is a word match
if len(s) == 1:
print MatchSoFar+[(x,y)]
return 1
## search in child nodes for rest of string match
num_matches = 0
for (X, Y) in [(x, y+1), (x+1, y), (x+1, y+1)]:
num_matches += DFS(M, X, Y, s[1:], MatchSoFar+[(x,y)])
return num_matches
## MAIN
M = [
['w' , 's' , 'r' , 't' , 'g' , 'g' ],
['a' , 'a' , 'c' , 'h' , 'i' , 'n' ],
['k' , 'c' , 'h' , 'u' , 'j' , 'j' ],
['o' , 'h' , 'i' , 'n' , 'y' , 'q' ],
]
num_matches = 0
for x in range(len(M)):
for y in range(len(M[0])):
num_matches += DFS(M, x, y, "sachin", [])
print num_matches
======
OUTPUT:
[(0, 1), (1, 1), (1, 2), (1, 3), (1, 4), (1, 5)]
[(0, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 3)]
[(0, 1), (1, 1), (2, 1), (2, 2), (3, 2), (3, 3)]
[(0, 1), (1, 1), (2, 1), (3, 1), (3, 2), (3, 3)]
4

whatevva'
December 16, 2013 1. add "0" to the MSB of the two strings so that their lengths match
2. iterate on the two strings one bit at a time starting with LSB and do bitwise addition and accumulate result
3. reverse the result
## INPUT STRING
str1 = "100011"
str2 = "100100"
## bit stuff the strings with "0" in MSB location
maxlen = max(len(str1), len(str2))
bitStuffedString1 = "0"*(len(str1)maxlen) + str1
bitStuffedString2 = "0"*(len(str2)maxlen) + str2
## bitwise add starting from LSB
cin = 0
result = ""
for (x, y) in zip(reversed(bitStuffedString1), reversed(bitStuffedString2)):
bitAddRes = int(x) + int(y) + cin
result += str(bitAddRes % 2)
cin = bitAddRes/2
result += str(cin)
## reverse the result so LSB is at the max index
result = result[::1]
print result

whatevva'
December 16, 2013 @psy, "until one node is left" doesn't mean that "we are always deleting the second one". It is possible that at the very end, there are two nodes left and k=5 for example .. in which case, you traverse the full cycle twice (cover 4 elements) and delete the "first" element in the third cycle traversal.
While it is true that "k" may be a constant, it doesn't have to be a constant "2" in this question.
Looks like I misunderstood the statement "Count the total number license numbers starting with ABC". I assumed we want the count of all license plates with keys "starting with ABC" including ABC and beyond such as ACC, MMM etc all the way to the end of the last key tag... and thats why i suggested traversing. But I guess the question asks for the count of plates with just one key.
Thanks @am for pointing it out.
Maintain a Hash table with "key" as the first 3 characters and the value being a "list" of the last three numbers of all the license plates with the same starting "key". It should be straight forward to get the "List all licenses starting with ‘MMM’ ".
Also mantain a Binary Search Tree where the node value is the "key" above and the "value" is the count of the license plate numbers with that key. Getting the "Count the total number license numbers starting with ABC" can be accomplished by searching for key "ABC" and doing inorder traversal from that node.
@Anonymous, what is wrong with Sunny's analysis? the algorithm is exactly the same ... its just a different way of doing the analysis. you iterate through "k" items before deleting the "k"th item. So, for every item that is deleted, you are touching "k" items. For a total of "n" items, you will be iterating/touching "n*k" items .. so, O(n*k) is the running time. This is O(n) only if "k" can be considered a constant.
 whatevva' June 28, 2013find the closest parent with given node in left subtree
keep track of distance from this parent to given node
search the parent's right subtree for the first child that matches the distance
if no child of the correct distance is found with this parent, reiterate by finding the next closest parent
pseudo code below
right_neighbor = Null
node = given_node
distance = 0
while(True):
# find closest parent with given node in its "left subtree"
# return parent and distance from parent to node
(parent, distance) = find_left_subtree_parent(NODE = node, start_distance = distance)
if (parent == Null)
{ return Null } ## reached root without finding right neighbor
else
{ right_neighbor = find_child_in_right_subtree(parent, distance) }
if(right_neighbor != Null)
{ return right_neighbor; }
else
{ ## the closest parent did not have the right neighbor
## keep traversing up to find next parent with given node in left subtree
node = parent
}

whatevva'
June 28, 2013 Your algoritm is correct but is not O (n). To get O (n), you should be performing each delete in constant time. As you remove more and more elements leaving null values intheir place, you will encounter more null values ... you will be touching linear nulls per delete (not constant)
 whatevva' June 28, 2013Total tosses = n
Given "k" tosses, probability that all "k" tosses have the same type of toss (or be a "Streak")
= probability of all heads in "k" tosses + probability of all tails in "k" tosses
= (1/2)^k + (1/2)^k = 2*(1/2)^k
Given "n" tosses, # of sets of subsequent "k" tosses
= (nk+1)
expected number of kstreaks
= number of subsequent "k" tosses * probability that one set of "k" tosses is a streak
= (nk+1)*2*(1/2)^k
you are assuming that the progression will always increase which is not necessarily the case (atleast in my interpretation of the question). So, working out the series wouldn't help.
For example, if the given string is "aababcXabcd", the partition would be (a, ab, abc, X, abcd) .. this doesnt follow a progression
sorry, formatting got screwed up ... looks like I cannot edit my response. What I meant to say was that in #3, instead of "until you reach the end from z. y then contains the kth node from end", it should read "until you reach the end from y. z then contains the kth node from end"
 whatevva' June 21, 2013def dec2bin(number):
## integer part:
int_number = int(number)
int_bin_str = ''
while int_number != 0:
(int_number, remainder) = divmod(int_number, 2)
int_bin_str = str(remainder) + int_bin_str
## fractional part
frac_number = number  int(number)
frac_bin_str = ''
count = 0
while( count < 4):
frac_bin_str += str(int(2.0 * frac_number))
frac_number = 2*frac_number  int(2*frac_number)
count += 1
return int_bin_str+"."+frac_bin_str
## MAIN ##
print dec2bin(10)
print dec2bin(2.22)
print dec2bin(0.876)

whatevva'
June 21, 2013 Use the Floyd's cyclefinding algorithm (tortoise and the hare).
def print_loop(head, next_ptr):
ptr_1x = head
ptr_2x = head
# first iteration until ptr_2x catches up with ptr_1x
while(True):
if (ptr_2x != None) and (next_ptr[ptr_2x] != None) and \
(next_ptr[next_ptr[ptr_2x]] != None):
ptr_2x = next_ptr[next_ptr[ptr_2x]]
else:
return False
ptr_1x = next_ptr[ptr_1x]
if ptr_1x == ptr_2x:
break
# second iteration  reset ptr_2x and go at 1x and
# continue ptr_1x from last location in first iteration
# to find start of loop
ptr_2x = head
while(ptr_2x != ptr_1x):
ptr_2x = next_ptr[ptr_2x]
ptr_1x = next_ptr[ptr_1x]
start = ptr_1x
# print loop
print start
ptr_1x = next_ptr[ptr_1x]
while(ptr_1x != start):
print ptr_1x
ptr_1x = next_ptr[ptr_1x]
## MAIN ##
next_ptr = {
1 : 2,
2 : 3,
3 : 4,
4 : 5,
5 : 6,
6 : 7,
7 : 8,
8 : 9,
9 : 5
}
print_loop(1, next_ptr)

whatevva'
June 21, 2013 Following is the code in python.
def preorder_depth(my_str, cur_node_index, parent_depth, max_depth_sofar):
if my_str[cur_node_index] == 'L':
if max_depth_sofar < ( parent_depth + 1 ):
max_depth_sofar = parent_depth + 1
return (cur_node_index+1, max_depth_sofar)
else:
# left child
(next_node_index, max_depth_sofar) = \
preorder_depth(my_str, cur_node_index+1, parent_depth+1, max_depth_sofar)
# right child
(next_node_index, max_depth_sofar) = \
preorder_depth(my_str, next_node_index, parent_depth+1, max_depth_sofar)
return (next_node_index, max_depth_sofar)
## MAIN ##
print preorder_depth("PPPLLLL", 0, 0, 0)
print preorder_depth("PPPLPLLLL", 0, 0, 0)

whatevva'
June 21, 2013 Following is the code in python. "phrase_list" is the list of phrases that the string is partitioned into. We start with the current phrase "cur_phrase" equal to the character pointed to by index. If the "cur_phrase" (single character) does not exist in the accumulated "phrase_list", we add it to the phrase list since p0 is given as empty. However, if the "cur_phrase" (single character) exists in the "phrase_list", we keep adding subsequent characters to the "cur_phrase" until it doesnt exist in phrase_list. After adding "cur_phrase", we reset "cur_phrase" from the next character and continue iterating.
def partition_string(my_str):
phrase_list = []
index = 0
while index < len(my_str):
cur_phrase = my_str[index]
while (index+1 < len(my_str)) and (cur_phrase in phrase_list):
cur_phrase += my_str[index+1]
index += 1
phrase_list.append(cur_phrase)
index += 1
return phrase_list
## MAIN
print partition_string("aababcabcd")

whatevva'
June 21, 2013 acknowledge the error in the code above .. following is the updated algo. The actul code is in the subroutine "actual"
def reference(A, B):
C0 = ((A & 0xff) + (B & 0xff))>>1
C1 = (((A>>8) & 0xff) + ((B>>8) & 0xff))>>1
C2 = (((A>>16) & 0xff) + ((B>>16) & 0xff))>>1
C3 = (((A>>24) & 0xff) + ((B>>24) & 0xff))>>1
C = C0 + (C1<<8) + (C2<<16) + (C3<<24)
return C
def actual(A,B):
## apply mask so that there is no carry that
## carries over from one byte to another byte
## .. we will lose information on the carry for
## for the lsb additions
A_p = (A & 0xfEfEfEfE) >> 1
B_p = (B & 0xfEfEfEfE) >> 1
C_p = A_p + B_p
## reclaim the carry information for the Lsb
## additions
A_pp = A & 0x01010101
B_pp = B & 0x01010101
C_pp = ((A_pp + B_pp)>>1) & 0x01010101
C = C_p + C_pp
return C
## MAIN
A=0x335577FF
B=0xFFDDBB99
print 'reference: %x' % reference(A,B)
print 'actual : %x' % actual(A,B)

whatevva'
June 20, 2013 lets say the N digits of A are: [An1, An2, ..., A1, A0]
Consider A' which is composed of the N1 most significant digits of A: [An1, An2, ..., A1]
So, A = {A', A0}
To find B:
compute B = {A'+1, A01}
If B ends up being more than N digits, then there is no solution.
 Use a queue implemented as a resizable array to store the timestamps of all new requests
 maintain head/tail pointers as usual
 Also maintain three pointers: ptr_last_1hr_from_tail, ptr_last_1min_from_tail, ptr_last_1sec_from_tail
Updates to the Queue:
everytime a new timestamp is enqueued (added to tail):
 continue dequeueing while(timstamp[head]timestamp[tail] > 1hour) . this ensures that we dont continue to keep storing timestamps we dont need.
 set ptr_last_1hr_from_tail = head
 decrement ptr_last_1min_from_tail until (timestamp[ptr_last_1min_from_tail] timestamp[tail] > 1min)
 decrement ptr_last_1sec_from_tail until (timestamp[ptr_last_1sec_from_tail]timestamp[tail] > 1sec)
Fetch counts from Queue:
On every new fetch request:
 for last 1 hour count: set fetch_1hr_ptr to ptr_last_1hr_from_tail and decrement fetch_1hr_ptr wile timestamp[fetch_1hr_ptr]fetch_timestamp > 1hr ;
 for last 1 min count: set fetch_1min_ptr to ptr_last_1min_from_tail and decrement fetch_1min_ptr wile timestamp[fetch_1min_ptr]fetch_timestamp > 1min;
 for last 1 sec count: set fetch_1sec_ptr to ptr_last_1sec_from_tail and decrement fetch_1sec_ptr wile timestamp[fetch_1sec_ptr]fetch_timestamp > 1sec ;
 req count in last 1hr = (fetch_1hr_ptrtail)
 req count in last 1min = (fetch_1min_ptrtail)
 req count in last 1sec = (fetch_1sec_ptrtail)
Depending on the nature of the request traffic, we could also use binary search when updating the various pointers instead of linear decrement.
Following is my code in python.
1. First the pattern string is converted into a pattern list of tuples.
A) a* becomes (a, True, 0) where True signifies that the # of occurence is "GREATER THAN EQUAL" to 0
B) a+ becomes (a, True, 1) where True signifies that the # of occurence is "GREATER THAN EQUAL" to 1
C) a with no */+ becomes (a, False, 1) meaning that there is no "GREATER THAN" condition but only "EQAUL" condition to 1
a+aabc => [('a', True, 1), ('a', False, 1), ('a', False, 1), ('b', False, 1), ('c', False, 1)]
2. Then the pat list simplified so that we accumulate contiguous occurences of the same character.
=> [('a', True, 3), ('b', False, 1), ('c', False, 1)]
3. Then the resulting pat list is expanded so that either we have exact matches or "*" matches .. there are no "+" matches
=> [('a', False, 1), ('a', False, 1), ('a', False, 1), ('a', True, 0), ('b', False, 1), ('c', False, 1)]
with the expanded pattern list consisting of exact matches and * matches, we iterate over the expanded pattern list and the match_string
def get_pat_list(pat_str, pat_list):
index=0
while index < len(pat_str):
char = pat_str[index]
if (index + 1) < len(pat_str):
if pat_str[index+1] == '*':
pat_list.append((char, True, 0))
index += 2
elif pat_str[index+1] == '+':
pat_list.append((char,True, 1))
index += 2
else:
pat_list.append((char, False, 1))
index += 1
else:
pat_list.append((char, False, 1))
index += 1
return
def simplify_pat_list(pat_list, simplified_pat_list):
#simplified_pat_list = list()
index = 0
while index < len(pat_list):
cur_char, acc_ge, acc_val = pat_list[index]
while ((index+1) < len(pat_list)) and (pat_list[index+1][0] == cur_char):
acc_ge = pat_list[index+1][1]
acc_val += pat_list[index+1][2]
index += 1
simplified_pat_list.append((cur_char, acc_ge, acc_val))
index += 1
return simplified_pat_list
def expand_pat_list(simplified_pat_list, expanded_pat_list):
#expanded_pat_list = list()
for char, ge, val in simplified_pat_list:
if not ge:
expanded_pat_list.append((char, ge, val))
elif val == 0 :
expanded_pat_list.append((char, ge, val))
else:
for i in range(1,val+1):
expanded_pat_list.append((char, False, 1))
expanded_pat_list.append((char, True, 0))
return expanded_pat_list
def match_pat(expanded_pat_list, match_str):
index_pat = 0;
index_mat = 0;
while (index_mat < len(match_str)) and (index_pat < len(expanded_pat_list)):
if expanded_pat_list[index_pat][1]:
while (index_mat < len(match_str) and expanded_pat_list[index_pat][0] == match_str[index_mat]):
#print "INFO0: "+expanded_pat_list[index_pat][0]+" =>" + match_str[index_mat]
index_mat += 1
#print "INFO2: "+expanded_pat_list[index_pat][0]+" =>" + match_str[index_mat]
index_pat += 1
elif expanded_pat_list[index_pat][0] == match_str[index_mat]:
#print "INFO1: "+match_str[index_mat]
index_mat += 1
index_pat += 1
else:
print "ERROR: pattern does not match\n"
return
if index_mat == len(match_str) and index_pat == len(expanded_pat_list):
print "MATCH\n"
elif index_mat == len(match_str) and index_pat < len(expanded_pat_list):
while index_pat < len(expanded_pat_list):
if not expanded_pat_list[index_pat][1]:
print "ERROR: pattern does not match\n";
index_pat += 1
print "Match\n"
else:
print "ERROR: pattern does not match\n"
## MAIN
pat_str = 'a+aabc'
mat_str = "aaaabc"
pat_list = list()
simplified_pat_list = list()
expanded_pat_list = list()
get_pat_list(pat_str, pat_list)
simplify_pat_list(pat_list, simplified_pat_list)
expand_pat_list(simplified_pat_list, expanded_pat_list)
print pat_str
print pat_list
print simplified_pat_list
print expanded_pat_list
print "\n\n";
match_pat(expanded_pat_list, mat_str)

whatevva'
June 14, 2013 have each engineer express his salary as a sum of two numbers.
Sa = Sa0 + Sa1
Sb = Sb0 + Sb1
Sc = Sc0 + Sc1
A will provide Sa0 to B
B will provide Sa0+Sb0 to C
C will provide Sa0+Sb0+Sc0 to A
A will provide Sa0+Sb0+Sc0+Sa1 to B
B will provide Sa0+Sb0+Sc0+Sa1+Sb1 to C
and C calculates avg = (Sa0+Sb0+Sc0+Sa1+Sb1+Sc1)/3
When you work out what information each engineer has regarding the numbers, following is what I came up with:
Person A knows the following : { Sa0, Sa1, Sb0+Sc0 , Sb1+Sc1 }
Person B knows the following: { Sb0, Sb1, Sa0, Sa1+Sc0, Sc1 }
Person C knows the following: { SC0, Sc1, Sa0+Sb0, Sa1+Sb1 }
This information is not sufficient for any one person to figure out the other persons salary
Sort the two lists first [O(nlogn) time]. Then do a variation of the merge step similar to what is done in mergesort with two separate pointers for each sorted list.
Python code below.
def lists_union_intersection(listA, listB):
## make a copy and sort the lists
sorted_listA = list(listA)
sorted_listB = list(listB)
sorted_listA.sort()
sorted_listB.sort()
## initialize
union_list = list()
intersection_list = list()
indexA=0;
indexB=0;
## merge step of two sorted arrays
while(True):
if indexA == len(sorted_listA): #check if no more elements in listA
if indexB != len(sorted_listB):
union_list.extend(sorted_listB[indexB:])
break
elif indexB == len(sorted_listB): #check if no more elements in listB
union_list.extend(sorted_listA[indexA:])
break
else:
a = sorted_listA[indexA]
b = sorted_listB[indexB]
if a < b:
union_list.append(a)
indexA += 1
elif a == b:
union_list.append(a)
intersection_list.append(a)
indexA += 1
indexB += 1
else:
union_list.append(b)
indexB += 1
return (union_list, intersection_list)
### MAIN ###
listA = [ 0, 2, 4, 5, 6]
listB = [ 1, 3, 5, 6]
(ulist, ilist) = lists_union_intersection(listA, listB)
print ulist
print ilist

whatevva'
June 13, 2013 Following is the code in python. Conceptually, we can think of the array being split into subarrays by elements that are "0" since the resulting max subarray will not straddle a "0" (unless the max product is < 0). So, [7 3 1 2 40 0 3 6 ] => [7 3 1 2 40], [3 6]
Now we try to find the max contiguous subarrays in each of the split subarrays. In order to do this we keep track of three products in each split subarray. For split subarray [7 3 1 2 40]:
1. total product = product( [7, 3, 1, 2, 40] )
2. product after first negative element = product([1, 2, 40])
3. product before the last negative element = product( [7, 3, 1, 2])
max product of split subarray is = max( product#1, product#2, product#3)
max product = max(max products of all split subarrays)
The code below implements the above logic in a single pass of the array, so it is not exactly as described above
def max_subarray_prod(num_list):
num_list.append(0)
number_of_allnums = 0
max_prod = None
prod_total = None
prod_to_last_negnum = None
prod_from_first_negnum = None
first_negative_num_encountered = False
for num in num_list:
if num == 0:
if number_of_allnums == 0:
continue
max_prod = max(max_prod, prod_total,\
prod_to_last_negnum, \
prod_from_first_negnum)
number_of_allnums = 0
prod_total = None
prod_to_last_negnum = None
prod_from_first_negnum = None
first_negative_num_encountered = False
else:
number_of_allnums += 1
prod_to_last_negnum = prod_total if num < 0 \
else prod_to_last_negnum
prod_total = num if prod_total is None else prod_total*num
if first_negative_num_encountered:
prod_from_first_negnum = num if prod_from_first_negnum \
is None else prod_from_first_negnum*num
if num < 0:
first_negative_num_encountered = True
return max_prod
print max_subarray_prod([ 7, 3, 1, 2, 40, 0, 3, 6])
print max_subarray_prod([ 3, 7, 2, 0, 5, 7, 2, 2, 2])

whatevva'
June 12, 2013 Following is my solution in python. First the given expression string needs to be parsed into an array of nested subexpressions. This parsing is the hardest part. An expression like "add(1,2)" gives an array ["add", "1", "2"]. Similarly, an expression like "add(1,mult(2,3))" will produce an array as follows: ['add', '1', ['mult', '2', '3']] Once the parsing is done, we evaluate the expressions recursively.
For the 'let' expression, we maintain a "context" dictionary to keep track of local variables.
CODE
def my_is_integer(s):
try:
int(s)
return True
except ValueError:
return False
def eval_exp(exp_list_or_str, context_dict):
if type(exp_list_or_str) is str:
if my_is_integer(exp_list_or_str):
return int(exp_list_or_str)
elif exp_list_or_str.isalnum():
return context_dict[exp_list_or_str]
else:
if exp_list_or_str[0] == 'ROOT':
return eval_exp(exp_list_or_str[1], context_dict)
elif exp_list_or_str[0] == 'add':
return eval_exp(exp_list_or_str[1], context_dict) \
+ eval_exp(exp_list_or_str[2], context_dict)
elif exp_list_or_str[0] == 'mult':
return eval_exp(exp_list_or_str[1], context_dict) \
* eval_exp(exp_list_or_str[2], context_dict)
elif exp_list_or_str[0] == 'div':
return eval_exp(exp_list_or_str[1], context_dict) \
/ eval_exp(exp_list_or_str[2], context_dict)
elif exp_list_or_str[0] == 'let':
context_dict[exp_list_or_str[1]] = eval_exp(exp_list_or_str[2], context_dict)
return eval_exp(exp_list_or_str[3], context_dict)
def parse_exp_str(exp_str, func_name, index):
exp_list = [func_name]
tmp_str=""
while(True):
if exp_str[index] == ')': ## encountered close of parenthesis
if tmp_str != "":
exp_list.append(tmp_str)
break
elif exp_str[index] == '(': ## encountered a sub expression which is a function
(tmp_list, index) = parse_exp_str(exp_str, tmp_str, index+1)
exp_list.append(tmp_list)
tmp_str = ""
if func_name == 'ROOT':
break
elif exp_str[index] == ',': ## acquired one argument
if tmp_str != "":
exp_list.append(tmp_str)
tmp_str = ""
index += 1
else: ##accumulate string
tmp_str += exp_str[index]
index += 1
return (exp_list, index+1)
### MAIN ###
exp_array = [
'add(1, 2)',
'add(1, mult(2, 3))',
'mult(add(2, 2), div(9, 3))',
'let(a, 5, add(a, a))',
'let(a, 5, let(b, mult(a, 10), add(b, a)))',
'let(a, let(b, 10, add(b, b)), let(b, 20, add(a, b)))'
]
for exp_str in exp_array:
exp_str = exp_str.replace(" ", "") #remove all spaces
#parse expression string into a nested array of subexpressions
(exp_list, tmp) = parse_exp_str(exp_str, "ROOT", 0)
#evaluate the parsed exp_list
result = eval_exp(exp_list, {})
print exp_list
print exp_str +" => "+ str(result)
print "\n\n"
OUTPUT
['ROOT', ['add', '1', '2']]
add(1,2) => 3
['ROOT', ['add', '1', ['mult', '2', '3']]]
add(1,mult(2,3)) => 7
['ROOT', ['mult', ['add', '2', '2'], ['div', '9', '3']]]
mult(add(2,2),div(9,3)) => 12
['ROOT', ['let', 'a', '5', ['add', 'a', 'a']]]
let(a,5,add(a,a)) => 10
['ROOT', ['let', 'a', '5', ['let', 'b', ['mult', 'a', '10'], ['add', 'b', 'a']]]]
let(a,5,let(b,mult(a,10),add(b,a))) => 55
['ROOT', ['let', 'a', ['let', 'b', '10', ['add', 'b', 'b']], ['let', 'b', '20', ['add', 'a', 'b']]]]
let(a,let(b,10,add(b,b)),let(b,20,add(a,b))) => 40

whatevva'
June 12, 2013 I believe the way "sum" is being calculated in this solution is not correct. The "sum" for a path is the sum of all nodes from root to the leaf node and this will not be known until you traverse all the way to the leaf node. while a leaf node will be part of only one path and so will have only 1 sum, a nonleaf node can be a part of multiple paths with different sums and you should delete it only if the max sum is less than K.
 whatevva' June 05, 2013Perfrom a Depth first search traversal passing in the sum from the root to the children. When you reach the leaf node, calculate the total sum of the path. If the leaf node total sum is less than K, delete it. return the total sum calculated. Each node gets a "left_sum" and "right sum" based on left and right subtrees. If the max(left_sum, right_sum) is less than K, then delete that node as well. Following is the code in python:
val_node = {'a' : 1, 'b' : 2, 'c' : 3, 'd' : 4, 'e' : 5, 'f' : 6, 'g': 7 }
left_child = { 'a' : 'b',
'b' : 'd',
'c' : 'f'
}
right_child = { 'a' : 'c',
'b' : 'e',
'c' : 'g'
}
def DFS(node, sum_from_root, K):
val = val_node[node] + sum_from_root
if (node not in left_child) and (node not in right_child):
print "leaf node: " + node + "\t sum: " + str(val)
if val < K:
print "deleting leaf node: " + node
del val_node[node]
return val #returning sum from leaf
if node in left_child:
left_sum = DFS(left_child[node], val, K)
if left_sum < K :
print "deleting left child reference of : " + node
del left_child[node]
if node in right_child:
right_sum = DFS(right_child[node], val, K)
if right_sum < K :
print "deleting right child reference of : " + node
del right_child[node]
if left_sum is None:
sumx = right_sum
elif right_sum is None:
sumx = left_sum
else:
sumx = max(left_sum, right_sum)
if sumx < K:
del val_node[node]
print "deleting node: " + node
return sumx
### MAIN
print "ORIGINAL TREE"
print val_node
print left_child
print right_child
DFS('a', 0, 9)
print "UPDATED TREE"
print val_node
print left_child
print right_child

whatevva'
June 04, 2013 do a Depth first search with "level" for the root element as '0'. Each node's "level" is 1 added to the parent's level. Each node receives a tuple of the (min leaf level, max leaf level) from the left and right subtree and evaluates its own (min, max) tuple. Once you return to the root, you compare min and max. following is the code in python:
nodes = ['a', 'b', 'c', 'd', 'e', 'f', 'g']
left_child = { 'a' : 'b',
'b' : 'd',
'c' : 'f'
}
right_child = { 'a' : 'c',
'b' : 'e',
'c' : 'g'
}
def DFS(node, level):
if (node not in left_child) and (node not in right_child):
print "leaf node: " + node + "\t level: " + str(level)
return (level, level) #returning (max leaf level, min leaf level)
if node in left_child:
max_left, min_left = DFS(left_child[node], level+1)
if node in right_child:
max_right, min_right = DFS(right_child[node], level+1)
if max_left is None:
maxx = max_right
elif max_right is None:
maxx = max_left
else:
maxx = max(max_right, max_left)
if min_left is None:
minx = min_right
elif min_right is None:
minx = min_left
else:
minx = min(min_right, min_left)
return (minx,maxx)
def equal_leaves():
minx, maxx = DFS('a',0)
return minx == maxx
### MAIN CALL
print equal_leaves()

whatevva'
June 04, 2013
This solution is acceptable in Java since Java supports the logical shift right ">>>" operation. However, this wouldn't work in C as it doesn't support this operation. Infact, a common interview question is to implement logical shift right operation in C.
 whatevva' February 04, 2014