Given a function getInorderSuccessor which takes a BST (Binary Search Tree) as it's parameter. Every node has an extra pointer "next" , which is intialized to null, fill next with node pointers which represent Inorder Successor.

Design a Architecture of Online Movie Booking System . Find the possible issues and Idea to Resolve them. How do you optimize the Performance against all these issues.

We are interested to find out the number of Distinct customer visited at-least p distinct pages within exactly T days.

Suppose, Amazon have a Logging system Like This:
They Track all logs daily basis, stored in separate log file.Log contains a collection of tuples of Customer ID and Page ID. The length of Customer ID and Page ID is L1 and L2. Suppose We have a log of D-days , and size of each log fine can be Order of n , where n be the number of customer.
In a most generalized situation, you can assume that a customer can visit the same page multiple times in a day or any number of days.
We are interested to find out the number of Distinct customer visited at-least p distinct pages within exactly T days.
Propose a Data Structure to be use to solve this problem efficiently . Design an Algorithm to solve this problem and Find out the complexity of the algorithm.

how many heaps can be created with complete binary tree of n nodes

Alex is curious about data structures. He is working on binary trees recently and particularly interested in complete binary trees.
A complete binary tree satisfies that all levels of the tree, except possibly the last one (deepest) are fully filled, and, if the last level of the tree is not complete, the nodes of that level are filled from left to right.

Alex defines his own complete binary tree: each node has a weight, while father's is always less than or equal to its sons'. He names this complete binary tree as minimum heap.

Now he wants to know: With N nodes weighted from 1 to N (each appears once), how many heaps can be created. The answer (represented by Q) may be very large, so please output a number P while P = Q mod M.

Followed Up:
Consider a complete binary tree of height n, where each edge is a one Ohm resistor. Suppose all the
leaves of the tree are tied together. Approximately how much is the effective resistance from the root to thisbunch of leaves for very large n?

(a) Exponential in n
(b) Cubic in n
(c) Linear in n
(d) Logarithmic in n
(e) Of the order square root of n

Google Wants Us to Find an Element thats greater then A, in Unsorted Element....Do You Think its Possible or Just They Wants to Test if Possible or Not

First greater number in an array. Given a large array of positive
integers, for an arbitrary integer A, we want to know the first integer in
the array which is greater than or equal A . O(logn) solution required
ex [2, 10,5,6,80]

input : 6 output : 10
input :20 output : 80

Convert integers to roman numbers

Question: write an algorithm to convert an integer into roman number. For example, 1 -> I, 2 -> II, or 4 -> IV.

Solution: in order to solve this problem, we must know the rules of writing roman numerals. For example, I is 1 and V is 5 but IV is not 6 but 4 (5 -1). Moreover, there is no 0 number in roman numeral system. Here is the link to an articleabout roman numerals if you are unfamiliar with the system.

As you may notice, the roman numeral system consists of several fundamental and unique numbers. They are used in conjunction with rules to create other numbers. Therefore, we just have to cache the unique numbers and apply the rules in order to generate any roman number we want. Let's take a look at the implementation below in C++

#include<iostream>
#include<map>
#include<string>
using namespace std;

string int2RomanNum(int intVal)
{
   if (intVal <= 0)
   {
      cout << "Roman numbers don't support 0 or negative! Return NULL" << endl;
      return ""; 
   }

   //build hash table of unique values 
   map valueMap;

   valueMap[1] = "I";
   valueMap[4] = "IV";
   valueMap[5] = "V";
   valueMap[9] = "IX";
   valueMap[10] = "X";
   valueMap[40] = "XL";
   valueMap[50] = "L";
   valueMap[90] = "XC";
   valueMap[100] = "C";
   valueMap[400] = "CD";
   valueMap[500] = "D";
   valueMap[900] = "CM";
   valueMap[1000] = "M";

   //the roman value
   string romanResult = "";

   //traverse the list in reverse order 
   map::reverse_iterator it;
   
   for (it = valueMap.rbegin(); it != valueMap.rend(); it++)
   {
      //if current number is greater than current key in list
      //add the value corresponded with key to result
      //then subtract the equivalent int value from current number
      while (intVal >= it->first)
      {
         romanResult = romanResult + it->second;
         intVal = intVal - it->first;
      }
   }

   return romanResult;
}

 

Explanation: our method accepts an integer as parameter and return a string that contains the roman number equivalent to that integer.

1. First we check the parameter to see if it is equal or less than 0. Because there is no 0 or negative roman numbers, we return an empty string after printing out the warning.
2. Next, we build a hash table of unique roman numbers which are then combined to create other numbers.
3. The heart of this method consists of two loops. The "for" loop runs through the hash table from bottom to top (largest number to smallest number). At each number in the hash table, we run the "while" loop to construct the roman number. This while loop will run until the integer is less than the current number in the hash table. And for every iteration in the while loop we add the current roman number to the returned string. For example, if our integer is 35, at the 10 or X position in the hash table, the while loop will kick in and add XXX into our string. And then the for loop continues at the 5 or V position, letting the while loop add V into our string.

Example: let's say we want to convert the integer 430 into its equivalent roman number. Here is how the method runs:

1. First "for" loop's iteration, intVal = 430 and it->first = 1000. No while loop because intVal is less than it->first.
2. Second iteration, intVal = 430 and it->first = 900. No while loop.
3. Third iteration, intVal = 430 and it->first = 500. No while loop.
4. Fourth iteration, intVal = 430 and it->first = 400. Enter while loop:romanResult = CD and intVal = 30. Because intVal is less than it->first after the first "while" iteration, the while loop exits.
5. Fifth iteration, intVal = 30 and it->first = 100. No while loop.
6. Sixth iteration, intVal = 30 and it->first = 90. No while loop.
7. Seventh iteration, intVal = 30 and it->first = 50. No while loop.
8. Ninth iteration, intVal = 30 and it->first = 40. No while loop.
9. Tenth iteration, intVal = 30 and it->first = 10. Enter while loop: 1) intVal = 20 and romanResult = CDX, 2) intVal = 10 and romanResult = CDXX, and 3) intVal = 0 and romanResult = CDXXX. The while loop exits after that because intVal is less than it->first.
10. Nothing happens in the last four iterations because intVal is 0. Thus, the final result is romanResult = CDXXX

Thank you for reading and until next time :)

Resilient Binary Search-search an element in O(log n) time in the perturbed array?

You are about to search for an element in a sorted array A[1..n] using binary search when the array suddenly gets perturbed. By perturbed, we mean a number in ith position in the array can now be either in i, i-1 or i+1th position; but all the numbers are still in A[1..n]. Can you still search an element in O(log n) time in the perturbed array?

Valid Strings-erase the smallest possible number of characters such that the remaining string after the erasures is valid

A string over the characters (, [, ] and ) is said to be valid if one can reduce the string to the null string by repeatedly erasing two consecutive characters of the form () or []. For example, the string [([])[]] is valid but neither ([)] nor ([ is valid.
Give a polynomial time algorithm to solve the following problem: Given a string, erase the smallest possible number of characters such that the remaining string after the erasures is valid. For example, given the string [(], we can erase ( to get [].

Nab the thief-prove that Alice can win in at most 3n moves.

Alice and Bob play the following game: Two cops(c) and a thief(t) are positioned at some vertices of an nxn grid. Alice controls the two cops and Bob controls the thief. The players take turns to play, starting with Alice. In one turn, Alice can move each cop to a neighboring vertex, i.e. left, right, up or down or keep the cop in the same place. In his turn, Bob can move the thief similarly.
If the thief and a cop end up in the same vertex, Alice wins.
For any arbitrary positioning of the two cops and the thief, prove that Alice can win in at most 3n moves.

Estimating Distance-Find maximum distance between any pair of points in a plane

A set of n points are on a plane. Let d denote the maximum distance between any pair of points. Design a linear time algorithm to guess the value of d. Your guess is good if it lies between 0.7d and d. also proove correctness of algorithm.