BST with node equals sum of all greater nodes

Given a BST, convert it so that each node has value equal to sum of all the nodes (including itself) which are greater than that node in the whole tree.

Binary Tree in cartesian plane

Assume that a binary tree is drawn over a Cartesian coordinate system (with X & Y axis) where the leftmost node is placed at point (0,0). So, we need to traverse the nodes and print in following manner:
For e.g., for this tree
a
b c
d e f g

Output should be:
d,0,0
b,1,1
e,2,0
a,3,2
f,4,0
c,5,1
g,6,0

Strategy:

You can easily note here that for any given node:
the x-coordinate is its cardinal (order) in an inorder traversal; and
the y coordinate is the number of levels in the tree rooted at that node;
Using these 2 pieces you can easily get the output shown above...

int print(node* n, int &count) {
    if (!n) return -1;
    int height = print(n->left, count) + 1;
    printf("%d,%d,%d", n->data, count++, height);
    print(n->right, count);
    return height;
}
print(root, 0);

kth smallest element in a sorted matrix

Assume you have a integer matrix (m x n) sorted over column wise & row wise. WAP to find the kth smallest element from the matrix.
E.g.
int[][] a =
2, 5, 8, 10
4, 7, 9, 12
6, 15, 20, 22
So 5th smallest element is: 7

Binary Tree Traversal-Modified

WAP to print the node values of a binary tree
- Even level starting from right to left
- Odd level starting from left to right
Assume that level of root is 1.
a
b c
d e f g
Output: a c b d e f g

Strategy:

Method 1:Two Stacks

static void print(Node root)
{
Stack<Node> odd = new Stack<Node>();
Stack<Node> even = new Stack<Node>();
odd.Push(root);
while (odd.Count != 0 || even.Count != 0)
{
while (odd.Count != 0)
{
Node node = odd.Pop();
if(node.left!=null)
even.Push(node.left);
if(node.right!=null)
even.Push(node.right);
Console.Write(node.data+" ");
}
Console.WriteLine();
while (even.Count != 0)
{
Node node = even.Pop();
if (node.right != null)
odd.Push(node.right);
if (node.left != null)
odd.Push(node.left);
Console.Write(node.data + " ");
}
Console.WriteLine();
}
}

Method 2:

 Breadth First Search with a stack can solve this problem.
1. Add the root node to the queue.
2. Get the head node of the queue and add its children to the queue.
3. If the node is in even level, print it. Otherwise, push it into the stack
4. When level of the head node has changed from odd to even,pop the stack and print the node
5. Repeat from 2 until all the node have been scaned

Mirror Puzzle !

Imagine you are standing in front of a mirror, facing it. Raise your left hand. Raise your right hand. Look at your reflection. When you raise your left hand your reflection raises what appears to be his right hand. But when you tilt your head up, your reflection does too, and does not appear to tilt his/her head down. Why is it that the mirror appears to reverse left and right, but not up and down?

Convert unknown base to decimal

Given an integer, write a program that converts the given number to a number (in base 10). The base of the given number is unknown.

Strategy:
The problem statement states that the base of the given number is unknown. Thus to proceed one must need to assume a base for the number. It is practically safe to assume that the digit with the maximum value in the number denotes the maximum that can be accounted in the unknown base. This a number if stated as, 254, it can be assumed that the number system consists of digits 0, 1, 2, 3, 4, 5 - or base 6. 

Working on this assumption, it becomes fairly simple to code a function that will return a number for the given string representation of the number. The following JAVA code sample does the same, extending the above assumption to include digits 0 to 9 and characters A to Z, where A represents 10, B represents 11 and so on.

Code:

public Double convertUnknownBaseNumberToBase10(String number) {
  // null check
  if(number == null || number.length() == 0) {
   return null;
  }
 
  // turn to upper case - so that our logic below is easy
  number = number.toUpperCase();

  // scan through the string to find out the maximum number or the character
  int maxAscii = 0;
  for(int i = 0; i < number.length(); i++) {
   int ascii = number.charAt(i);
   if(!(((ascii >= '0') && (ascii <= '9')) || ((ascii >= 'A') && (ascii <= 'Z')))) {
    System.out.println("Illegal number, can have only digits (0-9) and letters (A-Z)");
    return null;
   }
   maxAscii = Math.max(ascii, maxAscii);
  }
 
  // check if the number has letters or not
  double finalNumber = 0;
  int length = number.length();
  if(maxAscii >= 'A') {
   int maxNumber = maxAscii - 'A' + 10 + 1;
   for(int i = 0; i < length; i++) {
    int charCode = number.charAt(i);
    if(charCode >= 'A') {
     charCode = charCode - 'A' + 10;
    }
    int num = charCode;
    finalNumber = finalNumber + (num * Math.pow(maxNumber, (length - i - 1)));
   }
  } else {
   int maxNumber = maxAscii - '0' + 1;
   // just iterate over a normal loop
   for(int i = 0; i < length; i++) {
    int num = number.charAt(i) - '0';
    finalNumber = finalNumber + (num * Math.pow(maxNumber, (length - i - 1)));
   }
  }
 
  return finalNumber;
 }

Pairwise sum

If pairwise sums of 'n' numbers are given in non-decreasing order identify the individual numbers. If the sum is corrupted print -1
Example:
i/p:
4
4 5 7 10 12 13

o/p:
1 3 4 9

Strategy:

We will build A up from smallest element to largest. Suppose A and B are integer lists such that B gives the pairwise sums for A, where A[0] < A[1] < A[2] < ... and B[0] <= B[1] <= B[2] <= ... . Given B, we wish to find A. Suppose that we already know A[0]. Then, since P[0] is the smallest element in B, it can only arise as A[0] + A[1]. Similarly, P[1] must equal A[0] + A[2]. Therefore, if we know A[0], we can compute A[1] and A[2].

After that, however, this pattern breaks down. B[2] could either be A[0] + A[3] or A[1] + A[2] and without prior knowledge, we cannot know which one it is.

If we know A[0], we can compute A[1] and A[2] as described above, and then remove A[1] + A[2] from B. The next smallest element is then guaranteed to be A[0] + A[3], which allows us to find A[3].

Similarly, if we know A[0], A[1], A[2], and A[3], we can remove A{i}+A[j], 0 <= i < j <= 3, from B. The next smallest element of B will be A[0]+A[4], which allows us to compute A[4]. Repeating in this way, we can find all of A without ever backtracking.

Thus, once we know A[0], we can compute the rest of A. For this problem, we can now simply try every possibility for A[0]. We are given A contains only distinct non-negative integers, and A[1] > A[0], so A[0] must be an integer between 0 and B[0]/2 - 1 inclusive.

So whatever is the maximum value of B[0], we will have to try B[0]/2 possibilities for A[0].

Occurrence count for each Integer

Given a Integer array, we have to print the occurrence count for each Integer. What will be the optimal solution.

Strategy:
Best solution is to build a binary search tree...if while searching u come across a NULL ...insert that node there....if while searching u find that element increase the count...Then print each element in the tree by traversing it.

Note:

Hash table implementation is suitable when the integers are falling into a certain range say 0 to 100. We can take an array of 100 and the implementation is straight forward.
But say an array which contains only one element 100000. We can not take that much array size. Even if we take a smaller array and implement the hash algo there is always be a chance of collisions.

Nodes at same depth

Problem is to find print all the nodes at the same levels of a binary tree.Inputs given are root pointer and the pointer to the node (let it be A)whose level elements need to be printed.


Strategy:
Find the depth of the node A.
Then do a depth wise traversal of the tree by tracking the level u are at currently.
Now when u get a node of equal depth as A then print it and do a back traversal from there as other nodes from the current node will result in a higher depth. Thus we can find all the nodes at the current level.

Java Internals

Java Threading:
Thread, Concurrency, and Synchronization

Java Design Pattern: 
http://www.programcreek.com/category/design-patterns/
http://javarevisited.blogspot.in/2012/06/20-design-pattern-and-software-design.html
http://www.programcreek.com/java-design-patterns-in-stories/

Java Memory Model and Memory Leaks:

http://www.cubrid.org/blog/dev-platform/understanding-jvm-internals/

http://coding-geek.com/jvm-memory-model/

http://www.programcreek.com/2011/11/what-do-java-objects-look-like-in-memory/
http://www.programcreek.com/2013/04/what-does-a-java-array-look-like-in-memory/
http://www.programcreek.com/2011/10/how-java-compiler-generate-code-for-overloaded-and-overridden-methods/
http://www.programcreek.com/2013/10/the-introduction-of-memory-leak-what-why-and-how/
http://www.programcreek.com/2011/10/java-class-instance-initializers/

Java Garbage Collection:

https://www.interviewcake.com/concept/java/lazy

https://www.interviewcake.com/concept/java/slice?

https://www.interviewcake.com/concept/java/garbage-collection?

Java Advanced:

http://www.programcreek.com/advanced-topics/

Java Framework:

http://www.programcreek.com/2011/09/what-is-the-difference-between-a-java-library-and-a-framework/

http://www.programcreek.com/2011/09/how-to-design-a-java-framework/

http://www.programcreek.com/2011/07/build-a-java-library-for-yourself/

http://www.programcreek.com/2012/08/reflection-problem-on-java-framework/

Java Misc:

https://www.interviewcake.com/concept/java/mutable?

http://javarevisited.blogspot.in/2011/09/difference-hashmap-vs-hashset-java.html

Construct BST from preorder traversal

Given preorder traversal of a binary search tree, construct the BST.

For example, if the given traversal is {10, 5, 1, 7, 40, 50}, then the output should be root of following tree.

     10
   /   \
  5     40
 /  \      \
1    7      50

http://www.geeksforgeeks.org/construct-bst-from-given-preorder-traversa/
http://algorithms.tutorialhorizon.com/construct-binary-search-tree-from-a-given-preorder-traversal-using-recursion/
http://algorithms.tutorialhorizon.com/construct-binary-search-tree-from-a-given-preorder-traversal-using-stack-without-recursion/

Variation 1:
Given the Pre-order of the BST .check if each non-leaf node has only one child.Linear Time is expected.


Method 1 ( O(n^2) time complexity )
The first element of preorder traversal is always root. We first construct the root. Then we find the index of first element which is greater than root. Let the index be ‘i’. The values between root and ‘i’ will be part of left subtree, and the values between ‘i+1′ and ‘n-1′ will be part of right subtree. Divide given pre[] at index “i” and recur for left and right sub-trees.
For example in {10, 5, 1, 7, 40, 50}, 10 is the first element, so we make it root. Now we look for the first element greater than 10, we find 40. So we know the structure of BST is as following.

             10
           /    \
          /      \
  {5, 1, 7}       {40, 50}
We recursively follow above steps for subarrays {5, 1, 7} and {40, 50}, and get the complete tree.

Code:

#include <stdio.h>
#include <stdlib.h>

struct node
{
    int data;
    struct node *left;
    struct node *right;
};

struct node* newNode (int data)
{
    struct node* temp = (struct node *) malloc( sizeof(struct node) );

    temp->data = data;
    temp->left = temp->right = NULL;

    return temp;
}

struct node* constructTreeUtil (int pre[], int* preIndex,
                                int low, int high, int size)
{
    // Base case
    if (*preIndex >= size || low > high)
        return NULL;

    // The first node in preorder traversal is root. So take the node at
    // preIndex from pre[] and make it root, and increment preIndex
    struct node* root = newNode ( pre[*preIndex] );
    *preIndex = *preIndex + 1;

    // If the current subarry has only one element, no need to recur
    if (low == high)
        return root;

    // Search for the first element greater than root
    int i;
    for ( i = low; i <= high; ++i )
        if ( pre[ i ] > root->data )
            break;

    // Use the index of element found in postorder to divide postorder array in
    // two parts. Left subtree and right subtree
    root->left = constructTreeUtil ( pre, preIndex, *preIndex, i - 1, size );
    root->right = constructTreeUtil ( pre, preIndex, i, high, size );

    return root;
}

struct node *constructTree (int pre[], int size)
{
    int preIndex = 0;
    return constructTreeUtil (pre, &preIndex, 0, size - 1, size);
}

void printInorder (struct node* node)
{
    if (node == NULL)
        return;
    printInorder(node->left);
    printf("%d ", node->data);
    printInorder(node->right);
}

int main ()
{
    int pre[] = {10, 5, 1, 7, 40, 50};
    int size = sizeof( pre ) / sizeof( pre[0] );

    struct node *root = constructTree(pre, size);

    printf("Inorder traversal of the constructed tree: \n");
    printInorder(root);
    getchar();

    return 0;
}
Time Complexity: O(n^2)

Method 2 ( O(n) time complexity )
The idea used here is inspired from method 3 of this post. The trick is to set a range {min .. max} for every node. Initialize the range as {INT_MIN .. INT_MAX}. The first node will definitely be in range, so create root node. To construct the left subtree, set the range as {INT_MIN …root->data}. If a values is in the range {INT_MIN .. root->data}, the values is part part of left subtree. To construct the right subtree, set the range as {root->data..max .. INT_MAX}.

Code:

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

struct node
{
    int data;
    struct node *left;
    struct node *right;
};

struct node* newNode (int data)
{
    struct node* temp = (struct node *) malloc( sizeof(struct node) );

    temp->data = data;
    temp->left = temp->right = NULL;

    return temp;
}

struct node* constructTreeUtil( int pre[], int* preIndex, int key,
                                int min, int max, int size )
{
    // Base case
    if( *preIndex >= size )
        return NULL;

    struct node* root = NULL;

    // If current element of pre[] is in range, then
    // only it is part of current subtree
    if( key > min && key < max )
    {
        // Allocate memory for root of this subtree and increment *preIndex
        root = newNode ( key );
        *preIndex = *preIndex + 1;

        // Contruct the subtree under root

        // All nodes which are in range {min .. key} will go in left
        // subtree, and first such node will be root of left subtree.
        root->left = constructTreeUtil( pre, preIndex, pre[*preIndex],
                                        min, key, size );

        // All nodes which are in range {key..max} will go in right 
        // subtree, and first such node will be root of right subtree.
        root->right = constructTreeUtil( pre, preIndex, pre[*preIndex],
                                         key, max, size );
    }

    return root;
}

struct node *constructTree (int pre[], int size)
{
    int preIndex = 0;
    return constructTreeUtil ( pre, &preIndex, pre[0], INT_MIN, INT_MAX, size );
}

void printInorder (struct node* node)
{
    if (node == NULL)
        return;
    printInorder(node->left);
    printf("%d ", node->data);
    printInorder(node->right);
}

int main ()
{
    int pre[] = {10, 5, 1, 7, 40, 50};
    int size = sizeof( pre ) / sizeof( pre[0] );

    struct node *root = constructTree(pre, size);

    printf("Inorder traversal of the constructed tree: \n");
    printInorder(root);
    getchar();

    return 0;
}

Time Complexity: O(n)

Variation 1:
http://www.careercup.com/question?id=14453690

String Replacement / String Removal !

Replace all occurrence of the given pattern to ‘X’.
For example, given that the pattern=”abc”, replace “abcdeffdfegabcabc” with “XdeffdfegX”. Note that multiple occurrences of abc’s that are contiguous will be replaced with only one ‘X’.

Variation:
Remove all occurrences of the given pattern/string from another string.
for example:

 char str[]="absbdababad";
  char pattern[]="ab";
then our function should return  "sbdad"


Strategy:

We should take advantage that the replacement is only one character in length. Assume that the pattern is at least one character in length, then the replacement’s length will never exceed the pattern’s length. This means that when we overwrite the existing string with replacement, we would never overwrite characters that would be read next.
Two pointers are also used for an efficient in-place replacement, which traverses the string once without any extra memory.

Code:

bool isMatch(char *str, const char* pattern) {
  while (*pattern)
    if (*str++ != *pattern++)
      return false;
  return true;
}

void replace(char str[], const char *pattern) {
  if (str == NULL || pattern == NULL) return;
  char *pSlow = str, *pFast = str;
  int pLen = strlen(pattern);
  while (*pFast != '\0') {
    bool matched = false;
    while (isMatch(pFast, pattern)) {
      matched = true;
      pFast += pLen;
    }
    if (matched)
      *pSlow++ = 'X';
    // tricky case to handle here:
    // pFast might be pointing to '\0',
    // and you don't want to increment past it
    if (*pFast != '\0')
      *pSlow++ = *pFast++;  // *p++ = (*p)++
  }
  // don't forget to add a null character at the end!
  *pSlow = '\0';
}

Test cases:

Format is string, pattern = answer)
-----------------------------------
a, a = X
aa, aa = X
aa, a = X
aa, aaa = aa
abc, abc = X
abcabc, abc = X
abcabcabc, abc = X
abcaabcaabc, abc = XaXaX
abcaaabcaaabca, abc = XaaXaaXa
abcabcabababcabc, abc = XababX
abcabcabababcabcab, abc = XababXab
aabbaabbaaabbbaabb, aabb = XaXbX
aabbaabbaaabbbaabb, aaabb = aabbaabbXbaabb
aabbaabbaaabbbaaabb, aaabb = aabbaabbXbX
aabbaabbaaabbbaaabc, aaabb = aabbaabbXbaaabc
abcdeffdfegabcabc, abc = XdeffdfegX
abcdeffdfegabcabc, ab = XcdeffdfegXcXc
abcdeffdfegabcabc, a = XbcdeffdfegXbcXbc
abcdeffdfegabcab, abc = XdeffdfegXab
abcdeffdfegabcabcab, abc = XdeffdfegXab
abcdeffdfegabcaabcab, abc = XdeffdfegXaXab
abcdeffdfegabcaaaabcab, abc = XdeffdfegXaaaXab
aaaaaa, a = X
aaaaaa, aa = X
aaaaaa, aaaaaa = X
aaaaaa, aaaaaaa = aaaaaa
aabaababaaab, a = XbXbXbXb
aabaababaaa, a = XbXbXbX
aaaab, a = Xb
baaa, a = bX
aabaaabaab, aaa = aabXbaab
aabaaabaab, aa = XbXabXb
aabaaabaa, aa = XbXabX

Variation:

In the above program we can keep the slow pointer at its place and continue the loop if matched is true

Code:

#include <iostream>
using namespace std;

bool isMatch(char *str, const char* pattern) {
  while (*pattern)
    if (*str++ != *pattern++)
      return false;
  return true;
}

void replace(char str[], const char *pattern) {
  if (str == NULL || pattern == NULL) return;
  char *pSlow = str, *pFast = str;
  int pLen = strlen(pattern);
  while (*pFast != '\0') {
    bool matched = false;
    while (isMatch(pFast, pattern)) {
      matched = true;
      pFast += pLen;
    }
    if (matched)
      continue;
     // *pSlow++ = 'X';
    // tricky case to handle here:
    // pFast might be pointing to '\0',
    // and you don't want to increment past it
    if (*pFast != '\0')
      *pSlow++ = *pFast++;  // *p++ = (*p)++
  }
  // don't forget to add a null character at the end!
  *pSlow = '\0';
}

int main()
{
  char str[]="absbdababad";
  char pattern[]="ab";
  replace(str, pattern);
  printf("\n%s",str);

  getchar();
  return 0;

}

Find first occurrence of a string in another

Given two strings s1 and s2, find the first index of s2 in s1 in an efficient manner.

Strategy:
 
The problem has very typical solution, starting with each character in the source string start looking if the string being searched for, exists or not. However, the implementations may differ on the way they optimize. One good approach is to first look for the starting character of the string being searched for, in the string being searched. If found, then go ahead and look for other matches character by character.

We can optimize above implementation. As strings get longer in length, one may employ various mechanisms to check for equality. One such method being checking for the first character - if that results in a match, compare the last character. If that succeeds as well, go ahead and check the second and then second last character. This way one can zero down to matches to the center of the string being searched for. This particular approach considers that some words are used again and again in a string, but the longer the strings the probability of repetition of the letter at same index zero's down.

Code:

#include<iostream>
#include<string.h>

using namespace std;

int findStringInString(string stringToSearchIn, string stringToSearchFor)
{
  int lengthIn = strlen(stringToSearchIn);
  int lengthFor = strlen(stringToSearchFor);
  
  if(lengthFor > lengthIn) {
//   System.out.println("Sub-string candidate is larger than original string");
   return -1;
  }
  
  if(lengthFor == lengthIn) {
   for(int index = 0; index < lengthIn; index++) {
    if(stringToSearchIn[index] != stringToSearchFor[index]) {
     // no match found
     return -1;
    }
   }
   return 0;
  }
  // lengthFor < lengthIn
  for(int index = 0; index < (lengthIn - lengthFor); index++) {
   if(stringToSearchIn[index] == stringToSearchFor[0]) {
    boolean found = true;
    // first char match found
    // check if the string beyond this is equal
    for(int subIndex = 0; subIndex < lengthFor; subIndex++) {
     if(stringToSearchIn[index + subIndex] != stringToSearchFor[subIndex]) {
      // no match
      found = false;
      break;
     }
    }
    if(found) {
//     System.out.println("Match found at index: " + index + " in original string.");
//     System.out.println(stringToSearchIn.substring(index, index + lengthFor));
     return index;
    }
   }
  }
  
  return -1;
 }

int main()

( string str= "abcddercd";

string str2="cd";

int a=findStringInString(str, str2);

getchar();
return 0;

}

Concatenate N strings

Concatenate N strings with good optimization

You have n strings with their lengths. You are given an add(string s1,string s2) which would concatenate the string s2 with s1 and return s3. Optimize the cost of concatenation of all these strings into one big string.
Eg: 1,3,2 are the lengths of given strings.
1+3=4
4+2=6
total cost=10
Optimize this total cost?

Strategy:

Make a min heap out of the elements given.
Pop the smallest and the second smallest, add them and again insert that back to the heap.
Finally you will get the minimum cost 

OR
you can sort the array on the basis of length...and then just concatenate on the length of the string.

String Concepts

Strings are treated in C/C++ as character arrays terminated by NULL. They can be stored in either statically or dynamically allocated arrays. In either case, a string is represented by a char* pointer that points to the beginning of the string, and the string spans the memory from its beginning to the first NULL. Strings are not an innate data type of C/C++ and the language provides no means to deal with them

Swapping Strings:

Let us consider the below program.

#include<stdio.h>
void swap(char *str1, char *str2)
{
  char *temp = str1;
  str1 = str2;
  str2 = temp;
}

int main()
{
  char *str1 = "geeks";
  char *str2 = "forgeeks";
  swap(str1, str2);
  printf("str1 is %s, str2 is %s", str1, str2);
  getchar();
  return 0;
}

Output of the program is str1 is geeks, str2 is forgeeks. So the above swap() function doesn’t swap strings. The function just changes local pointer variables and the changes are not reflected outside the function.

Let us see the correct ways for swapping strings:

Method 1(Swap Pointers)
If you are using character pointer for strings (not arrays) then change str1 and str2 to point each other’s data. i.e., swap pointers. In a function, if we want to change a pointer (and obviously we want changes to be reflected outside the function) then we need to pass a pointer to the pointer.

#include<stdio.h>

/* Swaps strings by swapping pointers */
void swap1(char **str1_ptr, char **str2_ptr)
{
  char *temp = *str1_ptr;
  *str1_ptr = *str2_ptr;
  *str2_ptr = temp;
}

int main()
{
  char *str1 = "geeks";
  char *str2 = "forgeeks";
  swap1(&str1, &str2);
  printf("str1 is %s, str2 is %s", str1, str2);
  getchar();
  return 0;
}

This method cannot be applied if strings are stored using character arrays.

Method 2(Swap Data)
If you are using character arrays to store strings then preferred way is to swap the data of both arrays.

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

/* Swaps strings by swapping data*/
void swap2(char *str1, char *str2)
{
  char *temp = (char *)malloc((strlen(str1) + 1) * sizeof(char));
  strcpy(temp, str1);
  strcpy(str1, str2);
  strcpy(str2, temp);
  free(temp);
}

int main()
{
  char str1[10] = "geeks";
  char str2[10] = "forgeeks";
  swap2(str1, str2);
  printf("str1 is %s, str2 is %s", str1, str2);
  getchar();
  return 0;
}

This method cannot be applied for strings stored in read only block of memory.