You have to write a function checkRegex() which takes two strings as input, one string represents a regex expression and other is an input string to match with the regex expression passed as the other parameter. Return true if it matches, else false.

I found this question on one of the forum

Regex may contain characters ‘a-z’, ‘.’ and ‘*’ where ‘.’ matches any character and ‘*’ means 0 or more occurrences of the previous character preceding it.

Examples:
1) a*b matches b,ab,aab
2) a.b matches aab, abb, acb,…, azb
3) .* matches all the valid strings formed by using the lowercase letters


Status: Solved

Algorithm:Recursion



Time Complexity O(2^n)
Space Complexity O(1)

Given a php source file which contains a few classes defined in it. ,print the class hierarchy in the given desired format.

In PHP, there is concept of single class inheritance i.e. a new class can extend an existing class. You are given a php source file which contains a few classes defined in it. You have to print the class hierarchy in the given desired format.
For example, classes in php source file are A, B extending A, C extending B, D extending A, E.
The output should look like:

A
B
C
D
E

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters fo

Find the length of the longest no-repeated substring e.g. string without repeating characters. For example, the longest substring without repeating letters

ExampleString s="abcabcbbba" Answer will be "abc" of length 3

Algorithm:

Assuming string has small letter only temp array is of length 26.

Take an temp boolean array to set/reset character is present or not

while iterating through whole string using temp array If character value is already set or true then reset values from current index to previous starting index.and update max-length of non-repeated sub-string.e.g.When you have found a repeated character (let’s say at index j), it means that the current sub-string (excluding the repeated character of course) is a potential maximum, so update the maximum if necessary. It also means that the repeated character must have appeared before at an index i, where i  is less than j.

Since you know that all sub-strings that start before or at index i would be less than your current maximum, you can safely start to look for the next sub-string with head which starts exactly at index i+1.

As we are using two indexes which iterates through string two times e.g. O(2m) where m is length of string  and overall time complexity O(m) .

Lets have a look at Code

int lengthOfLongestSubstring(string s) 
{

  int m= s.length();

  int i = 0, j = 0;

  int maxLen = 0;

 boolean temp[]=new boolean[256];

  while (j < m) {

    if (temp[s[j]]) {

      maxLen = max(maxLen, j-i);

      while (s[i] != s[j])
      {

        temp[s[i]] = false;

        i++;

      }

      i++;

      j++;

    } else  
    {

      temp[s[j]] = true;

      j++;

    }

  }

  maxLen = max(maxLen, m-i);

  return maxLen;

}

Time Complexity O(M)  M is Length of String

Design an algorithm and write code to serialize and deserialize a binary tree.

Writing the tree to a file is called ‘serialization’ and reading back from the file to reconstruct the exact same binary tree is ‘de-serialization’.

First, we are able to save the binary tree to a file and restore it at a later time. We are also able to transmit the binary tree representation via network and load it into another computer. Without doubt, serialization/deserialization of a binary tree is important and an algorithm to represent a binary tree in a compact way is very desirable.

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be “resurrected” later in the same or another computer environment.

The pre-order traversal code below does all the job to serialize a binary tree, believe it or not!
Source :http://www.brilliantsheep.com/serializing-and-deserializing-a-binary-tree-in-java Time Complexity O(N)
Space Complexity O(N) to Store BST in File

Describe an algorithm to save a Binary Search Tree (BST) to a file in terms of run-time and disk space complexity. You must be able to restore to the exact original BST using the saved format.

Question need to be understand clearly .We Have to Transfer the Whole BST/BT across the network this is where he asked to implement the serialization on Tree & the transfer to another host on recipient side we use deserialization . to implement serialization on tree we need to save it in file & restoring the exact tree on receiving side .important question arises that which traversal we have to use here pre,in or post ?? only one is best are u able to think of it ???

let me explain lets we have tree is
_30_
/ \
20 40
/ / \
10 35 50

In-order traversal
If we do an in-order traversal, we will output 10 20 30 35 40 50. There is no way of telling how the original BST structure looks like, as the following unbalanced BST is one of the possible BST sets from the output 10 20 30 35 40 50.

_50
/
40
/
35
/
30
/
20
/
10

Post-order traversal:
If we do a post-order traversal, we will output the leaf nodes before its parent node. Specifically, we will output 10 20 35 50 40 30 using post-order traversal. Imagine we’re reading the nodes to construct the tree back. See the problem that we are reading the leaf nodes before its parent? There’s too much trouble to create the child nodes before its parent. Remember that the BST insertion algorithm works by traversing the tree from the root to the correct leaf to insert.

Pre-order traversal:
Pre-order traversal is the perfect algorithm for making a copy of a BST. The output of a pre-order traversal of the BST above is 30 20 10 40 35 50. Please note the following important observation:
A node’s parent is always output before itself.

Therefore, when we read the BST back from the file, we are always able to create the parent node before creating its child nodes. The code for writing a BST to a file is exactly the same as pre-order traversal.

Ps: we can solve this problem with any traversal if we need to given an array to store in array instead of file isn't it think ?? why

on receiving side Reading a BST from a file:
The question now is, how would you reconstruct a BST back from the file? Assume that we have the following pre-order traversal output of the BST earlier: 30 20 10 40 35 50.
so answer is
When we encounter a new node to insert, we should always place it into the first empty space which it will fit using a pre-order traversal. How do we determine the first empty space which a node will fit in? We can use the ordinary BST insertion algorithm, but the run-time complexity will be O(n lg n), since inserting a node takes O(lg n) time. Not efficient enough! so we need some more efficient algorithm
yes we can do it using what we used to solve "Determine if a Binary Tree is a Binary Search Tree (BST)?"

so what will be the efficent algo then here it is
We use the same idea here. We pass the valid range of the values from the parent node to its child nodes. When we are about to insert a node, we will check if the insert value is in the valid range. If it is, this is the right space to insert. If it is not, we will try the next empty space. Reconstructing the whole BST from a file will take only O(n) time.

void readBSTHelper(int min, int max, int &insertVal,
BinaryTree *&p, ifstream &fin) {
if (insertVal > min && insertVal < max) { int val = insertVal; p = new BinaryTree(val); if (fin >> insertVal) {
readBSTHelper(min, val, insertVal, p->left, fin);
readBSTHelper(val, max, insertVal, p->right, fin);
}
}
}

void readBST(BinaryTree *&root, ifstream &fin) {
int val;
fin >> val;
readBSTHelper(INT_MIN, INT_MAX, val, root, fin);
}

Time Complexity O(N)
Space Complexity O(1)

Given two sorted positive integer rrays A(n) and B(n). We define a set S = {(a,b) such that a in A and b in B}. Obviously there are n^2 elements in S. The value of such a pair is defined as Val(a,b) = a + b. Now we want to get the n pairs from S with largest values. The tricky part is that we need an O(n) algorithm.

Write a program that converts a given tree to its Double tree. To create Double tree of the given tree, create a new duplicate for each node, and insert the duplicate as the left child of the original node.

e.g below tree

1
/ \
2 3
/ \
4 5
is changed to

1
/ \
1 3
/ /
2 3
/ \
2 5
/ /
4 5
/
4

Algorithm:
Recursively convert the tree to double tree in postorder fashion. For each node, first convert the left subtree of the node, then right subtree, finally create a duplicate node of the node and fix the left child of the node and left child of left child.

#include
#include

/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};

/* function to create a new node of tree and returns pointer */
struct node* newNode(int data);

/* Function to convert a tree to double tree */
void doubleTree(struct node* node)
{
struct node* oldLeft;

if (node==NULL) return;

/* do the subtrees */
doubleTree(node->left);
doubleTree(node->right);

/* duplicate this node to its left */
oldLeft = node->left;
node->left = newNode(node->data);
node->left->left = oldLeft;
}

/* UTILITY FUNCTIONS TO TEST doubleTree() FUNCTION */
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}

/* Given a binary tree, print its nodes in inorder*/
void printInorder(struct node* node)
{
if (node == NULL)
return;
printInorder(node->left);
printf("%d ", node->data);
printInorder(node->right);
}

/* Driver program to test above functions*/
int main()
{

/* Constructed binary tree is
1
/ \
2 3
/ \
4 5
*/
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);

printf("Inorder traversal of the original tree is \n");
printInorder(root);

doubleTree(root);

printf("\n Inorder traversal of the double tree is \n");
printInorder(root);

getchar();
return 0;
}
Time Complexity: O(n) where n is the number of nodes in the tree.

An array of size n+1 has integers only from 1 to n. The integers 1 to n can be present 0 or more times in the array. Find the first repeating element in the array. Restrictions: O(n) algo required. Cannot use extra space(not even O(1)) but how you will do if we have to find the all repeating number in given constraints?

Question Seems to bit easy in 1st look but 1st typical Google interview question from their predefined set .in 1st try you won't be able to solve it , i am sure no one can cover the all the test cases in 1st attempt but after trying different test cases we can solve it easily :)

Data Structure Used: Array

Algorithm:(Simple & Straight Forward )

traverse the list for i= 0 to n-1 elements
{
check for sign of A[abs(A[i])] ;
if positive then
make it negative by A[abs(A[i])]=-A[abs(A[i])];
else // i.e., A[abs(A[i])] is negative
this element (ith element of list) is a repetition
}

Working Code

#include
#include

void printRepeating(int arr[], int size)
{
int i;
printf("The repeating elements are: \n");
for(i = 0; i < size; i++) { if(arr[abs(arr[i])] >= 0)
arr[abs(arr[i])] = -arr[abs(arr[i])];
else
printf(" %d ", abs(arr[i]));
}
}

int main()
{
int arr[] = {1, 2, 3, 1, 3, 0, 6};
int arr_size = sizeof(arr)/sizeof(arr[0]);
printRepeating(arr, arr_size);
getchar();
return 0;
}


Its Not Perfect we Need to care of when 0 or any other element occurs more then 2 ?? what happens when it comes multiple times ?? What Happens when array may contains -ive elements ??

suppose you have this array 1 0 2 0 3 0 1 6 4 3 then above algo fail so we need to cover all these case as well isn't it ?? check test case here http://ideone.com/wdxRJ for negative number i will check in last!!!!!!!!

Modified Algorithm(Optimized As Well)
1.While Looping Down from Array Calculate the index of each array element ist clear as all elements will in range of 1 to n so no over flow or underflow conditions.? so index=a[i]%size;
2. then check if value at this index is zero or not if its zero then set its as INT_MIN or -size as you wants. a[index]=-size
3.if above condition fails then check if value at given index is in given range or
not if its in range then multiply the value at given index with -1.
4. if number is less then zero this means its already occurs so print it , multiply with -1 to reset & set value to this index to a[index]=value+size due to time complexity constraints & problem statement i used this when if a number occur say k times algorithm wont fail.
5.

#include
#include
void printRepeating(int arr[], int size)
{
int i,index=0;
printf("The repeating elements are: \n");
for(i = 0; i < size; i++) { index=abs(arr[i])%size; if(arr[index] == 0) arr[index]=-size; else if(arr[index]>0 && arr[index] arr[index] = -arr[index];
else if(arr[index]<0)
{
printf(" %d ", abs(arr[i]));
arr[index]=-arr[index];
arr[index]+=size;// try to dry run for each number you will get it !!! :)
}
}
//restore previous array
for(i=0;i arr[i]=abs(arr[i])%size;
}

int main()
{
int arr[] = {2,2,1,1,1,2,2,3,0,0,0,1,1,2,0,7,5};
int arr_size = sizeof(arr)/sizeof(arr[0]);
printRepeating(arr, arr_size);
getchar();
return 0;
}

Time Complexity O(N)
Space Complexity O(1)
Run Here http://ideone.com/i7n7V

further Thoughts: How we will solve if number is between -n to n e.g. total 2n+1 time in unsorted array .Yes As I have already explained the algorithm above will also work here , above we range from 0 to n & here we have -n to n but logic will remain the same why ?? because range is known to us ..i Will suggest to my read to to try out this & do notify it it will fail

Feel Free to Comment :)

Double Square Problem

A double-square number is an integer X which can be expressed as the sum of two perfect squares. For example, 10 is a double-square because 10 = 32 + 12. Your task in this problem is, given X, determine the number of ways in which it can be written as the sum of two squares. For example, 10 can only be written as 32 + 12 (we don’t count 12 + 32 as being different). On the other hand, 25 can be written as 52 + 02 or as 42 + 32.

Input
You should first read an integer N, the number of test cases. The next N lines will contain N values of X.

Constraints
0 ≤ X ≤ 2147483647
1 ≤ N ≤ 100

Output
For each value of X, you should output the number of ways to write X as the sum of two squares.