Given a number, find the next minimal greater number with same number of set bits
int GetNextNumCountBits(int n)
{
int count = countBits(n)
for (int i =n+1; i < INT_MAX;i++)
    if (countBits(i) == count)
       return i;
return 0
}
int countBits(n)
{
int count = 0;
while(n)
{
if (n&0x1) count++;
n >>=1;
}
return count;
}

/*geeksforgeeks mentions the following but it doesn't seem to work */
This problem has an interesting bit pattern that can be exploited for optimization
Take
155 for example
int nextOne(int x)
{
int rightOne;
int nextHigherOneBit
int rightOnesPattern;
int next = 0;
if (x)                                                                 //10011011
{
rightOne = x & -(signed)x;                              //00000001
nextHigherOneBit = x  + rightOne;                 //10011100
rightOnesPattern = x ^ nextHigherOneBit       //00000111
rightOnesPattern = (rightOnesPattern) / rightOne  //0000011 // right adjust by shifting 1 sequence except for leftmost
rightOnesPattern >> = 2                                   //00000001 // I'm skipping the above statement
next = nextHigherOneBit | rightOnesPattern   //10011101
}
return next;
}
157

If we want to right shift a number, we essentially divide by 2
5 = 101
5/2 = 2  => 10
2/2 => 1


Find the transition point between 0 and 1 in an infinite sorted sequence of binary
Int GetTransition (stream seq)
{
Int index = - 1;
Int power = 1
Int size = math.pow (2,i);
var buffer = new Sequence (size);
While(seq.read (buffer) != - 1)
     Index = find_binary_chop (buffer, size);
     If (Index! = - 1)
       Return index;
}
Return index;
}

#search techniques

Find a node in skip graph with a given key

Void findOne(Node n, int searchOp, node startNode, int searchKey, int level) 

{ 

If (n.key == searchKey) then 

    Inform n to start_node 

If n.key < searchKey then 

    While level >= 0 do 

      If (nRlevel).key < searchKey then 

          Recursively call at nRlevel 

           Break; 

      Else level = level –1 

Else 

      While level >= 0 do 

       If (nLlevel).key  > searchKey then 

           Recursively call at nLlevel 

           Break; 

       Else level = level –1 

If (level < 0) then 

   Inform n to startNode  

} 

Void findallInrange(ref List<Node> result, int min, int max) 

{ 

// all the nodes at the lowest level between min and max are the candidates 

FindOne say at min 

Then binary chop between min and max at lowest level. 

}

#codingexercise

Find the distance between two nodes in a binary tree

distance = distance from root for first + distance from root for second - 2 * distance from root for LCA
Node getLCAAndDistance(Node root, int n1, int n2, int level, ref int d1, ref int d2, ref int dist)
{
if (root == null) return null;
if (root.key == n1){
d1 = level;
return root;
}
if (root.key == n2){
d2 = level;
return root;
}
var llca = getLCAAndDistance(root.left, n1, n2, level+1, ref d1, ref d2, ref dist);
var rlca = getLCAAndDistance(root.right, n1, n2, level+1, ref d1, ref d2, ref dist);
if (llca && rlca)
{
dist = d1+d2-2*level;
return root;
}

if (llca != null)

   return llca;

else

   return rlca;

}
Node getDistance(Node root, int n1, int n2)
{
int d1 = -1;
int d2 = -1;
int dist = -1;
var lca = getLCAAndDistance(root, n1, n2, 1, ref d1, ref d2, ref dist);
if (d1 == -1 && d2 == -1) return dist;
if (d1 == -1) {dist = findlevel(lca, n2, 0); return dist;}
if (d2 == -1) {dist = findlevel(lca, n1, 0); return dist;}
return -1;
}

#some more coding exercise
Convert a binary tree to binary search tree retaining the tree structure
Solution  copy the elements by inorder traversal
Sort the array
Copy the elements back by inorder traversal

void binaryTreeToBST(Node root)
{
if (root == null) return root;
var ret = new List<int>();
store(root, ret);
ret.sort();
int i =0;
copy(root, ret, ref i)
}
void copy(node root, list<int> ret, int i)
{
if (root==null) return;
copy(root.left, ret, i);
root.data = ret[i];
i++;
copy(root.right, ret, i);
}

Print all the nodes that are a distance k from leaf
void kDistanceFromLeaf(node root,ref List<int> ancestors, int len ref List<int> result, int k)
{
if (node==null) return;
ancestors[len] = node.data;
len++;
if (node.left == null && node.right == null && len - k -1 >= 0
&& result.contains(node.data) == false){
result.add(node.data);
return;
}
kDistanceFromLeaf(root.left, ref ancestors, len ref result, k);
kDistanceFromLeaf(root.right, ref ancestors, len, ref result, k);
}

#codingexercise
Check if a binary tree is a binary search tree
bool isBST(node root)
{
return IsBstHelper(root, INT_MIN, INT_MAX);
}

bool IsBstHelper(node root, int min, int max)
{
 if (root==null) return true;
 if (root.data < min || root.data> max) return false;
return IsBstHelper(root.left, min, root.data-1) &&
           IsBstHelper(root.right, root.data+1, max);
}

Find the largest binary tree

int GetMaxBST(node root)
{
 if (isBST(root)) return treesize(root);
 return max(GetMaxBST(root.left), GetMaxBST(root.right));
}

int GetMaxBST2(node root, ref int min, ref int max, ref int maxSize, ref bool isBST)
{
if (root == null) { isBST = true; return 0;}
int val = INT_MAX;
bool left = false;
bool right = false;
max = INT_MIN;
int lsize = GetMaxBST2(root.left, min, max, maxSize, isBST);
if (isBST && root.data > max)
    left = true;
int val = min
min = INT_MAX;
int rsize = GetMaxBST2(root.right, min,max, maxSize, isBST);
if (isBST && node.data < min)
    right = true;
if (val < min)
       min = val;
if (root.data < min)
       min = root.data;
if (root.data > max)
       max = root.data;
if (left && right)
 { if (lsize + rsize +1  > maxSize)
        maxSize = lsize+rsize+1;
    return lsize + rsize + 1;
 }
else{
   isBST = false;
   return 0;
}
}

Sample program to take a local backup file, upload it to S3 storage and inform an api

import boto
import boto.s3
import sys
from boto.s3.key import Key

AWS_ACCESS_KEY_ID = 'an_access_key_for_the_bucket'
AWS_SECRET_ACCESS_KEY = 'an_access_secret_for_the_bucket'

bucket_name = 'usersbackup'
conn = boto.connect_s3(AWS_ACCESS_KEY_ID,
AWS_SECRET_ACCESS_KEY)

bucket = conn.get_bucket(bucket_name, validate=False)

if (len(sys.argv)<= 1):
print('Usage: python backup.py <filename>')
sys.exit(0)

testfile = sys.argv[1]
print 'Uploading %s to Amazon S3 bucket %s' % \
(testfile, bucket_name)

def percent_cb(complete, total):
sys.stdout.write('.')
sys.stdout.flush()

def genCode():
import random
import string
return ''.join([random.choice(string.digits + string.ascii_uppercase) for x in range(0, 12)])

k = Key(bucket)
k.key = genCode()
k.set_contents_from_filename(testfile,
cb=percent_cb, num_cb=10)
sys.stdout.write('DONE')
sys.stdout.write('\n')
sys.stdout.flush()
import pycurl
from StringIO import StringIO
buffer = StringIO()
c = pycurl.Curl()
c.setopt(pycurl.POST, 0)
post_data = {'key': k.key}
from urllib import urlencode
postfields = urlencode(post_data)
c.setopt(c.POSTFIELDS, postfields)
c.setopt(c.URL, 'http://myapi/backup/v1/addbentry')

Convert a sorted array into a binary
search tree

Node makeBST (List <int> nums, int start, int end)
{
If start > end return null;
Int mid =(start+end)/2;
Node root = new node (nums [mid]);
Root.left = makeBST (nums, start, mid);
Root.right = makeBST (nums, mid+1, end);
Return root;
}

#codingexercise
(Yes some more)
Given a string and ing r that stands for rows, fill the columns and then print the string
Abcdefgh and r = 3 would mean
A d g
B e h
C f
Adgbehcf
String printoff ( string input, int r)
{
Stringbuilder ret;
Int count=0;
For  (int start =0; start < r; start++)
For (int I =0; start +I x r < input.length; i++)
{
ret [count] = input [start + I x r];
Count++;
}
Return ret.toString ();
}

In a BST, replace value of each node with the sum of itself and everything greater than itself.

void updateNode(node root, ref int sum)

{

if (root == null) return;

updateNode(root.right, ref sum);

sum = sum + root.data;

root.data = sum;

updateNode(root.left, ref sum);

}

int sum = 0

updateNode(root, ref sum);

Connect ropes of different lengths with minimum cost where cost = Sum of length of two ropes 
Int getmin (list <int> Len)
{
Int cost = 0
Heap h = build_heap(len)
While (h.size () >1)
{
First = extract_min (h)
Second = extract_min (h)
Cost += first + second
H.insert (first+second );
}
Return cost;
}

And one more
Clone a linked list with next and random pointers
Node clone (node root)
{
If (root == null) return root;
Node new = null;
Node prev = null;
For (node cur = root; cur; cur = cur.next)
{
Var n = cur.clone ();
If new == null new = n;
If (prev) prev.next = n;
Prev =n;
}
// point random link of all originals to correspond to new ones
//Point each random link of all new nodes to originals 
// point each random link of all new to random of random.
}

A self help portal for taking backups of VM instances. 

A cloud provider has valuable assets in the form of virtual machine instances. These instances need to be backed up to protect against disaster and to aid recovery. The backups should contain sufficient information to restore to original state. The cloud provider may have many datacenters one for each region from where the virtual machine instances can be loaned from.  These  virtual machine instances will be requested to be backed up on demand with the push of a button on the portal. The user may need to see the last few times the backups were taken for this virtual machine if any even if it means going through a pile of data of all inventory in a datacenter to come up with the backups. The schedule should include user description as well as time the backup was taken. The virtual machines should appear with the information on the backup contents such as the files included. Even if the backup is in the form of an encrypted tar ball that the user never sees or touches, he should be able to refer to it with a locating universal resource identifier and request basic management activities such as create, delete, detail and restore.  Before the next backup is taken, the VM should be found in the datacenter failing which the backup should not be honored. Incremental backup from last state should be the default if one full backup was taken. This can be overridden with a full backup if the user requests it. The backups should also be listed with the VMs they were taken from and the VM properties that may be relevant to the backup. All the backups should be shown against their VM only. This means the user wants to list the backups rolled up as Virtual Machines. Only when the user presses the detail on a Virtual machine does she see all the backups of the virtual machine. The backups should be taken regardless of the flavor of the operating system on the virtual machine. In addition any storage volumes associated with the virtual machine must also be backed up if they show up as mapped devices to the Virtual Machine. The Virtual machines can appear individually as requested from a cloud provider such as VMWare or it may appear in a group as in a cluster which may be requested from say Openstack. In all cases, the VM should be listed one by one together with their attributes of the cluster or group it is part of. The details page of each VM will show the memberships to clusters and other containers. The actions on each VM will be the same regardless of the virtual machine's identity. The actions may target the cloud provider of the region in which the virtual machines live. Consequently the VMs must be fetched from all regions and shown in flat table. The take backup control should be made visible for each virtual machine should the user wish to initiate it. Backups have status that shows whether the request was initiated, pending, complete or canceled. More states may need to be added if the user will benefit from seeing the state. If the states update asynchronously, the page should refresh automatically on periodic intervals. 

#coding exercises  (yes a few more continued)
find first occurrence of 1 in a sorted series of zeros and ones
int GetOne(List<int> digits)
{
for (int i = 0; i < digits.count; i++)
{
if (digits[i] == 1)
    return i;
}
//not found
return -1;
}
//binary search
int GetOneBinaryChop(List<int>digits, int start, int end)
{
if (start == end) {
    if (digits[start] == 1)
         return start;
    else
         return -1;
}
int mid = (start + end) / 2;
if (digits[mid] == 0)
    return GetOneBinaryChop(digits, mid+1, end);
else
   return GetOneBinaryChop(digits, start, mid);
}

Output nearest number greater than given number such that output is palindrome

int nextPalindrome(int n)

{

var digits = n.toDigits();

int len = digits.Count;

int mid = len/2;

if (len%2 == 0)

{

// new_number = the digits from mid+1 to len-1 should be reverse of 0 to mid

if (new_number > n) return new_number

// new_number = Add 1 to the number from 0 to mid with carryover and padding to the right

return nextPalindrome(new_number)

}else{

//new_number = the digits from mid+1 to len-1 should be reverse of 0 to mid -1

if (new_number > n) return new_number

// new_number = Add 1 to the number from 0 to mid with carryover and padding to the right

return nextPalindrome(new_number)

}

}

Void carryforward (ref list <int> digits, int index, int val)

{
Sum = digits[index] + val;
Carry = Sum - 10;
If (carry > 0){
Digits [index] =0;
If (index == 0){
Digits.insert (0, carry);
Return 
}
Carryforward ( ref digits, index - 1, carry)
}else  {
Digits [index] = sum;
}
}