In place sort of an array of numbers by zero

Problem:

  Given an array that has positive numbers and negative numbers and zero in it. 

 You need to seperate the negative numbers and positive numbers in such a way that 

 negative numbers lies to left of zero 

  and positive numbers to the right and the original order of elements should be maintained

This essentially is insertion sort algorithm with different comparison criterion. 

public static void orderByZero(int[] num){

for(int i = 1 ; i< num.length; i++){

int j = i ;

while(j>0){

if((num[j]<0 && num[j-1]>=0) || (num[j]==0 && num[j-1]>0)){

int t = num[j];

num[j] = num[j-1];

num[j-1] = t;

j--;

}else{

break;

}

}

}

}

Output of binary tree in zig-zag manner

The problem can be asked in different ways:

1. Given a binary tree and each node has an extra next pointer apart from left and right. Connect all the nodes using next pointer in Zig-Zag Manner.

2. Given a binary tree and each node has an extra next pointer apart from left and right. Print out all node in Zig-Zag Manner.

They are all coming down to how to traverse the binary tree in zig-zag manner. The key is to use two stacks, main stack and temporary stack. The main stack is used to traverse each layer, while put the children under the layer into temporary stack, also be careful with if we need to go left to right or right to left. 

public static void zigZag(Node root){

Stack<Node> s = new Stack<Node>();

s.add(root);

int level = 0;

Node pre = null;

while(!s.isEmpty()){

Stack<Node> t = new Stack<Node>();

while(!s.isEmpty()){

Node curr = s.pop();

if(pre==null)

pre = curr;

else{

pre.next = curr;

pre = curr;

}

if(level%2==0){

if(curr.left!=null)

t.add(curr.left);

if(curr.right!=null)

t.add(curr.right);

}else{

if(curr.right!=null)

t.add(curr.right);

if(curr.left!=null)

t.add(curr.left);

}

}

s = t;

level++;

}

}

Convert Binary Search Tree to Sorted Doubly-linked list

This is very interesting problem. And most of solutions are recursive approach which will cause stack overflow.

The below is my solution, which does in-place and iteratively.

The idea is to in-order traverse the tree and use head pointer referencing the head of the linked list and pre pointers referencing the previous node during traverse.

public static Node isBSTAndTreeToDLL(Node root){

if(root==null)

return null;

Stack<Node> s = new Stack<Node>();

Node head = null;

Node n = root;

Node pre = null;

while(!s.isEmpty() || n!=null){

if(n!=null){

s.push(n);

n = n.left;

}

else{

Node p = s.pop();

//this is the left most node

if(head == null)

head = p;

if(pre!=null){

pre.right = p;

p.left = pre;

}

pre=p;

n = p.right;

}

}

//handle the last node

pre.right = head;

head.left = pre;

return head;

}

Find Longest Common Subsequence Length of two strings

Problem:
Given two strings: "AGGTAB", "GXTXAYB", find the length of the longest common subsequence.

The answer for the two strings is 4, "GTAB". Note subsequence is the substring of string with the characters appears in the order as they are in the string but not necessary contiguously.

Solution 1. 

Do it recursively

 /* do it recursively

* @param s1

* @param s2

* @return

*/

public static int findLongestCommonSubsequence(String s1, String s2){

if(s1.isEmpty() || s2.isEmpty())

return 0;

String substring1 = s1.substring(0, s1.length()-1);

String substring2 = s2.substring(0, s2.length()-1);

if(s1.charAt(s1.length()-1) == s2.charAt(s2.length()-1)) {

return 1+StringQ.findLongestCommonSubsequence(substring1, substring2);

} else{

return Math.max(StringQ.findLongestCommonSubsequence(s1, substring2), StringQ.findLongestCommonSubsequence(substring1, s2));

}

} 

Solution 2.

Do it iteratively:

       public static int findLongestCommonSubsequence2(String s1, String s2){

char[] cArray1 = s1.toCharArray();

char[] cArray2 = s2.toCharArray();

int[][] lcs = new int[s1.length()+1][s2.length()+1];

for(int i=0; i<cArray1.length; i++){

for(int j=0; j<cArray2.length; j++){

if(cArray1[i] == cArray2[j])

lcs[i+1][j+1] = lcs[i][j] + 1;

else

lcs[i+1][j+1] = Math.max(lcs[i+1][j], lcs[i][j+1]);

}

}

return lcs[s1.length()][s2.length()];

}

Longest Arithmetic Progression

Problem: 

 Given a set of numbers, find the Length of the Longest Arithmetic Progression (LLAP) in it.

The solution is to that using difference between two numbers in the list as key to store the maximum length for each difference. If the difference is already met before, then we can skip it.

Complexity: O(n^2) since there is n*(n-1) differences between the numbers in a list

public static List<Integer> findMaxArithmeticsSeq(int[] num){

int maxL = 0;

List<Integer> result = new ArrayList<Integer>();

//the difference between two numbers in the list defines the maxL of the sequence

//store the mapping will help to reduce the number of the iterations

Map<Integer, Integer> diff2Length = new HashMap<Integer, Integer>();

for(int i=0; i<num.length-1; i++){

for(int j=i+1; j<num.length; j++){

int diff = num[j]-num[i];

//we don't need to continue since max Length for this difference is already found

if(diff2Length.containsKey(diff))

continue;

List<Integer> found = new ArrayList<Integer>();

found.add(num[i]);

int pre = num[i];

for(int k=j; k<num.length; k++){

if(num[k] - pre == diff){

found.add(num[k]);

pre = num[k];

}

}

diff2Length.put(diff, found.size());

if(found.size() > maxL){

maxL = found.size();

result = found;

}

}

}

return result;

}

Permutations of list of numbers

Given a collection of numbers, return all possible permutations.

Problem description:

Input:
list of numbers: [8, 4, 13]

Output:
all permutations of the numbers in the list

[8, 4, 13]

[4, 8, 13]

[4, 13, 8]

[8, 13, 4]

[13, 8, 4]

[13, 4, 8]

Solution 1:

/**
* do it iteratively
*/

public static ArrayList<ArrayList<Integer>> getPermutations(int[] nums){
ArrayList<ArrayList<Integer>> result = new ArrayList<>();

  //start with an empty list
  result.add(new ArrayList<Integer>());
 
  for(int i=0; i<nums.length; i++){
ArrayList<ArrayList<Integer>> temp = new ArrayList<>();

//go through the list from previous round and add the number into the list
   for(ArrayList<Integer> each : result){
for(int index = 0; index<=each.size(); index++){
ArrayList<Integer> dest = new ArrayList<>(each); //make a copy of original list
dest.add(index, nums[i]); //insert the number into all possible positions
temp.add(dest);
}
}
  
// switch over to prepare for the next round
 result = temp;
}
return result;
}

Solution 2:

/**

 *  do it recursively

**/

public static List<List<Integer>> getPermutations(List<Integer> nums){

List<List<Integer>> result = new ArrayList<>();

if(nums.size()==0){

result.add(new ArrayList<Integer>());

return result;

}

Integer n = nums.remove(0);

List<List<Integer>> subResult = getPermutations(nums); //get the permutation for sub list

for(List<Integer> each : subResult){

for(int index = 0; index<=each.size(); index++){

ArrayList<Integer> dest = new ArrayList<>(each); //make a copy of original list

dest.add(index, n); //insert the number into all possible positions

result.add(dest);

}

}

return result;

}

IBM Corporate Service Corps Team Nigeria 7 Google Map

This is the brief introduction about IBM's unique global program called Corporate Service Corps.

"The Corporate Service Corps was launched in 2008 to help provide IBMers with high quality leadership development while delivering high quality problem solving for communities and organizations in emerging markets. The Corporate Service Corps was launched in 2008 to help provide IBMers with high quality leadership development while delivering high quality problem solving for communities and organizations in emerging markets. The program empowers IBM employees as global citizens by sending groups of 10 - 15 individuals from different countries with a range of skills to an emerging market for four week community-based assignments. During the assignment, participants perform community-driven economic development projects working at the intersection of business, technology, and society. "


I am lucky enough to be selected as a team of IBMers who comes from different part of the world and never met before to be sent to Nigeria. The following is map of all of 12 IBMers' location.

CSC Team Nigeria 7 Map

And here is the link to it so you can edit: Nigeria 7 Google Map