Binary tree to double linked list from spiral level order traversal

Spiral level order traversal is level order traversal in zig-zag fashion
Look at  http://www.geeksforgeeks.org/archives/3758

#!/usr/bin/env python

#This function converts each level into a double linked list and stores them in "l"
#left is prev and right is next
#we traverse the nodes in a level in left to right fashion,
#so the node in "l" is always left one
#Finally "l" have all the rightmost nodes of the all levels

def levelList(t, l, level, ltr):

if t:
left, right = t['left'], t['right']
t['left'], t['right'] = None, None

if len(l) > level:
#This level already started link this node
node = l[level]
if ltr:
t['left'], node['right'] = node, t
else:
t['right'], node['left'] = node, t

l[level] = t

else:
l.append(t)

ltr = not ltr

levelList(left, l, level + 1, ltr)
levelList(right,l, level + 1, ltr)


def spiralDoubleLinkedList(t):
l = []

levelList(t, l, 0, True)

#The following loop links the double linked lists of the levels
for i in range(len(l) - 1):
left, right = l[i], l[i+1]

while right['left']:
right = right['left']

while left['right']:
left = left['right']

left['right'] = right

return l[0]


def printList(d):
while d:
print d["d"],
d = d["right"]


t = {
"d" : 4,
"left" : {
"d" : 6,
"left" : {
"d" : 7,
"left" : None,
"right" : {
"d" : 13,
"left" : {
"d" : 14,
"left" : None,
"right" : None
},
"right" : {
"d" : 15,
"left" : None,
"right" : None
}
}
},
"right" : {
"d" : 8,
"left" : None,
"right" : None
}
},
"right" : {
"d" : 5,
"left" : {
"d": 9,
"left" : None,
"right" : None
},

"right" : {
"d" : 10,
"left" : {
"d" : 12,
"left" : None,
"right" : None
},
"right" : {
"d" : 11,
"left" : None,
"right" : None
}
}

}
}

printList(spiralDoubleLinkedList(t))

To print immediate Higher of all elements of a list

Given a list, print the Next Greater Element (NGE) for every element. The Next greater Element for an element x is the first greater element on the right side of x in list.
Elements for which no greater element exist, consider next greater element as -1.


Assume last element of list is -1

Lets define function f(i) which will give the next higher of element at index i

Then we can define f(i) as

f(i) = i + 1,  if l[i+1] > l [i]
f(i) = f(j),  i + 1 <= j < n

  
Solution: 

def nextHigher(l):
higher = {}

ln = len(l) - 1
higher[l[ln]] = -1 # last element of the list

for i in range(ln - 1, -1, -1): #start from the last two element of the list
c, n = l[i] , l[i+1]

if c >= n:
n = higher[n]
while n != -1 and n < c: #iterate through higher till find or
n = higher[n] #end of linked list(-1)

higher[c] = n

return higher


l = [13, 7, 6, 12, 14, 5, 20, 30]

print nextHigher(l)

Vertical sums of a binary tree

The problem is to print the vertical sums of a binary tree 
for example
|      |       5        |     |
| | / | \ | |
| | / | 8 |
| | / | / | \|
| 4 | / | 10
| / | \ 9 | |
| / | \ | |
7 | 6 |
| | | | |
| | | | |
-----------------------------
7 4 20 8 10


from collections import defaultdict
from operator import itemgetter

verticalSum = defaultdict(int)

def findVerticalSum(t, v):

if t:
verticalSum[v] += t["d"]
findVerticalSum(t["left"], v - 1)
findVerticalSum(t["right"], v + 1)



t = {
"d" : 5,
"left" : {

"d" : 4,
"left" : {
"d" : 7,
"left" : None,
"right" : None

},
"right" : {
"d" : 6,
"left" : None,
"right" : None
}
},
"right" : {
"d" : 8,
"left" : {
"d": 9,
"left" : None,
"right" : None
},

"right" : {
"d" : 10,
"left" : None,
"right" : None
}

}
}

findVerticalSum(t, 0)

print [a[1] for a in sorted(verticalSum.items(), key=itemgetter(0))]

Efficient Grouping of a phone number for better memoriazation

Problem: http://geeksforgeeks.org/forum/topic/google-interview-question-for-software-engineerdeveloper-about-algorithms-76


You are given a phone number.  To help you memorize the number, you want to divide it into groups of contiguous digits. Each group must contain exactly 2 or 3 digits. There are three kinds of groups:
• Excellent: A group that contains only the same digits. For example, 000 or 77.
• Good: A group of 3 digits, 2 of which are the same. For example, 030, 229 or 166.
• Usual: A group in which all the digits are distinct. For example, 123 or 90.



The quality of a group assignment is defined as 2 × (number of excellent groups) + (number of good groups)
Divide the number into groups such that the quality is maximized.



For example given a phone number 123354401099


Can be grouped as (12)(33)(544)(010)(99) or (12)(335)(44)(010)(99) whose quality score is 6.
We can define a function f which will give the quality score of a grouping as below, 


Where Sn is Phone number of length n and S[n] is the nth digit of phone number S 

Solution:
#include <stdio.h>
#include <string.h>
#include <string>

using namespace std;

struct Score{
int numBest, numGood;
string group;
};

Score scoreOf3(const char *str){
Score r = {0, 0, ""};

if(str[0] == str[1]){
if(str[1] == str[2]){
r.numBest = 1;
}else{
r.numGood = 1;
}
}else if(str[0] == str[2]){
if(str[1] == str[2]){
r.numBest = 1;
}else{
r.numGood = 1;
}
}else if(str[1] == str[2]){
r.numGood = 1;
}

r.group = string("(") + str[0] + str[1] + str[2] + ")";
return r;
}


Score maxScoredGroup(const char *str){

Score r = {0, 0, ""};

int len = strlen(str);

if(len == 0){
;
}else if(len == 1){
//invalid
r.numBest = r.numGood = -1;
}else if(len == 2){
r.numBest = str[0] == str[1];
r.group = string("(") + str + ")";
}else if(len == 3){
r = scoreOf3(str);
}else{
Score r1 = maxScoredGroup(str + 2);
Score r2 = maxScoredGroup(str + 3);
Score r3 = scoreOf3(str);

if(r1.numBest != -1){
r1.numBest += str[0] == str[1];
r1.group = string("(") + str[0] + str[1] + ")" + r1.group;
}

if(r2.numBest != -1){
r2.numBest += r3.numBest;
r2.numGood += r3.numGood;
r2.group = r3.group + r2.group;

}

int s1 = r1.numBest == -1 ? -1 : 2 * r1.numBest + r1.numGood;
int s2 = r2.numBest == -1 ? -1 : 2 * r2.numBest + r2.numGood;

r = s1 >= s2 ? r1 : r2;
}

return r;
}

int main(){

char phone[] = "123354401099";

Score s = maxScoredGroup(phone);

printf("Group = %s\nScore = %d", s.group.c_str(), s.numBest == -1 ? -1 : 2 * s.numBest + s.numGood);
return 0;
}

Compact and efficient JavaScript encapsulation

Here is one more Javascript encapsulation implementation. The idea followed is from the link published in hacker news.  The implementation is more compact and efficient.

function class(options){
var constructor = options.constructor,
public = options.public,
private = options.private,
key;


function hiddenClass(){}

var hp = hiddenClass.prototype = {};

function publicClass(){
var obj = new hiddenClass();
constructor && constructor.apply(obj, arguments);
Object.defineProperty(this, 'obj', {value : obj});
}

var pp = publicClass.prototype = {};

for(key in private){
if(private.hasOwnProperty(key)){
hp[key] = private[key];
}
}

for(key in public){
if(public.hasOwnProperty(key)){
var val = public[key];
hp[key] = pp[key] = val;

if(typeof val === 'function'){
pp[key] = function(){
return hiddenClass.prototype[key].apply(this.obj, arguments);
}
}
}
}

return publicClass;
}

Here is the example of using “class” function

var c = class({

constructor : function(a, b){
this.a = a;
this.b = b;
},

private: {
helpMe : function(){
console.log(this.a);
}
},

public: {

c : 30,
help : function(){
console.log('Hello');
},
print : function(){
this.help();
this.helpMe();
console.log(this.b);
console.log(this.c);
}
}

});

var o = new c(10, 20);

o.print();

To find all the expressions of a given sequence which evaluate to a given value k

Please look at the following link for the problem
http://geeksforgeeks.org/forum/topic/yahoo-interview-question-for-software-engineerdeveloper-fresher-about-algorithms-9

#!/usr/bin/env ruby

#The recursive function to find out all the expressions which evaluate to a given value
#The technique used is "backtracking"

def findExpr(s, expr, k)
if s.length != 0
expr += s[0].chr
val = eval(expr)

if val == k && s.length == 1
print expr, "\n"
elsif val < k
            #The operations supported are '*', '+' and '.'
            #where '.' is simple concatenation of the digits
findExpr(s[1..-1], expr + '*', k)
findExpr(s[1..-1], expr + '+', k)
findExpr(s[1..-1], expr, k)
end
end
end

findExpr("123456789", "", 2097)