CareerCup

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.

The 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(Q-R)/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(Q-R)/3)

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;
    }

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

6b'100011 | 6b'100100 != 7b'1000111

6b'100011 | 6b'100100 ==  6b'100111

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]

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

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

@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.

If there is no other node at the same level and to the right of the given node, I assumed that you would be returning NULL. That's what my pseudo code above does anyway.

By "immediate right neighbor", I understood that as right neighbor when you do level order traversal from root like in BFS .. except you are not supposed to use BFS .. and also you don't know root.

find 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, re-iterate 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
	}

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)

this question is known as the "Josephus problem" ... search on wikipedia

this doesnt address the case where some strings have all characters the same .. for example, if the given set of strings is [ab, bb, bbb, bbbb, ba]

the given set of strings is [ ab, ba, aac ]

if you consider the permutation ba-aac, this has the longest running character sequence "a-aa", so the answer is 3

Sunny, in the question p0 = '' (empty string). That is why (a, ab, abc, X, abcd) should work since X is a concatenation of p0 + X.

Total 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
= (n-k+1)

expected number of k-streaks
= number of subsequent "k" tosses * probability that one set of "k" tosses is a streak
= (n-k+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"

I think there is an error in #3 above. The correct description should be:
3.now in a loop make y=y->next and z=z->next until you reach the end from

y

.

z

then contains the kth node from end.

def 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)

Use the Floyd's cycle-finding 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)

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)

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")

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)

A = A3A2A1A0
B = B3B2B1B0

A' = (A & 0xf7f7f7f7) >> 2
B' = (B & 0xf7f7f7f7) >> 2

C = A' + B'

The solution I gave doesnt handle the "A->09999 B-> 18999" case. What does "next least N-digit number B" mean? clearly, B->18999 is not the next least digit after A->09999!

lets say the N digits of A are: [An-1, An-2, ..., A1, A0]
Consider A' which is composed of the N-1 most significant digits of A: [An-1, An-2, ..., A1]
So, A = {A', A0}

To find B:
compute B = {A'+1, A0-1}
If B ends up being more than N digits, then there is no solution.

Looks like a repeat of the following question -
question?id=19099663

Sounds like the solution is correct. What is the intuition or math behind this approach? Why does this work? Any links/references will be appreciated.

Can we assume that there are no other pieces on the board that might be in the way of the bishop movement?

- 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_ptr-tail)
- req count in last 1min = (fetch_1min_ptr-tail)
- req count in last 1sec = (fetch_1sec_ptr-tail)

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)

In PKTs example, B does not know that the total sum the first time around is 50L .. only C and A know that. So. As salary is still hidden from B.

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 merge-sort 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

Following is the code in python. Conceptually, we can think of the array being split into sub-arrays 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 sub-array is = max( product#1, product#2, product#3)
max product = max(max products of all split sub-arrays)

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])

Following is my solution in python. First the given expression string needs to be parsed into an array of nested sub-expressions. 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 sub-expressions
    (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

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 non-leaf 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.

def rec_powerset(my_str, prefix):
    if my_str is "":
        print prefix
        return
    
    rec_powerset(my_str[1:], prefix+my_str[0])
    rec_powerset(my_str[1:], prefix)

### MAIN
rec_powerset("abc", "")

what if a node has only a right sub-tree but no left-subtree (or vice-versa)?

Perfrom 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 sub-trees. 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

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 sub-tree 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()

Isn't the solution the "merge" step of the merge sort algorithm?

that is a good question .. my verbal descriptive solution assumes that we know what people are on what floor upfront.