Design a data structure that can be used instead of an array and avoids the "high-cost" (i.e. O(n)) of initializing the array. the data structure ought to holds n items and supports the following operations in O(1) time: * Init – Initializes the data structure to empty. * Set(i, x) – Sets item x at index i in the data structure. * Get(i) – Gets the item stored in index i (or 'empty' if nothing is there). Remark: the data structure should use O(n) space.

Design a data structure that can be used instead of an array and avoids the "high-cost" (i.e. O(n)) of initializing the array. the data structure ought to holds n items and supports the following operations in O(1) time: * Init – Initializes the data structure to empty. * Set(i, x) – Sets item x at index i in the data structure. * Get(i) – Gets the item stored in index i (or 'empty' if nothing is there). Remark: the data structure should use O(n) space.

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.