Fastest Super Computer is From Japan Till Today :) ,its K Computer

 Japanese supercomputer becomes world’s fastest and first to clear 10 petaflops

The fastest got faster, as the K Computer topped its own record on the twice-yearly supercomputer speed test by scoring 10.51 quadrillion calculations per second

 

The performance of the fastest machine on the Top500 supercomputer list hasn't stopped surging since the list began in 1993. Here, it's measured with a linear scale.

(Credit: chart by Stephen Shankland; data from Top500.org)

The rankings of the 10 fastest machines didn't change at all on today's new version of the Top500 supercomputer list, but the top dog cleared the notable performance hurdle of 10 petaflops.

"Flops" stands for floating-point operations per second and is a measure of how fast a supercomputer can perform mathematical calculations using the Linpack benchmark. The K Computer, at the Riken Advanced Institute for Computational Science in Japan, moved up from 8.16 petaflops, the score it used to reach the top of the twice-yearly supercomputer ranking last June, to 10.51 petaflops.

It reached the new top speed through being fully assembled, with all 705,024 of its Fujitsu Sparc64 processor cores running.

The Tianhe-1A in China, a former No. 1 machine at 2.57 petaflops, remains No. 2. It uses a combination of Intel central processing units and Nvidia graphical processing units. The United States is the top market for supercomputers on the list, but China is in second place, list organizers said.

Intel remains king of the heap when it comes to processor designs, supplying chips for 384 of the systems.

Among other aspects of the November 2011 list:

• Even though the top 10 machines remained the same--a first since the Top500 list began in 1993--there was still plenty of flux elsewhere on the list. The bottom of the barrel for the November list ranked No. 305 in June, and the total performance of all 500 machines rose from 58.7 petaflops to 74.2 petaflops.

• It's now required 50.9 teraflops to get on the list at all. That score beats the top system from 2004. The scores, though somewhat simplify the broad range of computing work that researchers strive to accomplish on these massive systems.

• A total of 39 systems now us graphics chips as accelerators for some computing tasks. That's the approach employed by a forthcoming Cray-built system with AMD 16-core processors and Nvidia Tesla chips slated for shipment to the National Center for Supercomputing Applications.

• IBM supplied 223 of the 500 systems and Hewlett-Packard supplied 146.

• At least 29 of the systems gulp down more than 1 megawatt of power--enough to power 10,000 100-watt light bulbs. The K Computer consumes 12.66 megawatts, but it's "one of the most efficient systems on the list," with a performance of 830 megaflops per watt, the list organizers said.

The Top500 supercomputer list shows plenty of changes over the 
years, but one constant is surging performance. This chart at the 
top shows performance in calculations per second, with a logarithmic 
scale that makes the rate of change look steady--for example by 
making the jump from 1 teraflops to 10 teraflops look as significant 
as the jump from 10 teraflops to 100 teraflops.

(Credit: Top500.org)

Read more: http://news.cnet.com

Complete the function getFirstLetterWord,

Complete the function getFirstLetterWord, which takes in a string text,consisting of only lowercase letters and spaces. A word is a maximal sequence of consecutive letters. There may be multiple spaces between words. Also, text may contain only spaces.
The function getFirstLetterWord is expected to return the word which is formed by concatenating the first letter from each word in text, in the order they appear.Return an empty string is no word is possible

Sample Test Cases:

Input #00:
the quick brown fox jumped over the lazy dog

Output #00:
tqbfjotld

Explanation:
Picking up the 1st character from each of the words in the sentence, we get, tqbfjotld


Input #01:
dice     gambling     las vegas

Output #01:
dglv

Explanation:
Ignore multiple spaces, picking the 1st character from dice, gambling, las and vegas results in dglv

import java.io.FileReader;
 
class WordCount 
{
 
public static void main(String args[]) throws Exception 
{
 
String text="dice       gambling       las    vegas";//"the quick brown fox jumped over the lazy dog";
 
char ch[]=new char[text.length()];
char c;
boolean lastWhite = true;
String whiteSpace = " \t";
int i=0;
 
   for(i=0;i<text.length();i++)
   {
        c=text.charAt(i);
 
        int index = whiteSpace.indexOf(c);
        if (index == -1)
        {
                  if (lastWhite == true)
                  {
                      ch[i]=c;
                  }
        
          lastWhite = false;
 
        }
 
        else
 
        {
 
                lastWhite = true;
 
        }
 
  }
 
    String ss = new String(ch);
    System.out.println(ss);
 
 }
 
}

Run Here http://ideone.com/zVquq 

WAP to Count Tottal number of Characters, Words and Lines in File Efficiently

Guys Think its Funny & Can be solved Easily..but when interviewer ask how u counts no of words when u have more then 1 spaces or tabs,line feeds or new lines , i mean white spaces ?? Its Asked Recently from one of the my friend in Amazon & Adobe Both

here is the solution i have taken car of such Scenario

import java.io.FileReader;

class WordCount {
public static void main(String args[]) throws Exception {
int words = 0;
int lines = 0;
int chars = 0;

FileReader fr = new FileReader("E:/ubuntu/tests.txt");
int c = 0;
boolean lastWhite = true;
String whiteSpace = " \t\n\r";
char sp=' ';
char tab=' ';
char lin='\n';
char ret='\r';

System.out.println(" " +(int)sp + " " + (int)tab + " " + (int)lin + " " + (int)ret);

while ((c = fr.read()) != -1)
{
chars++;

System.out.println(c);

if (c == '\n')
{
lines++;
}

int index = whiteSpace.indexOf(c);
//icrement word count when 1st time index of any spaces occurs -1 so set next
//using boolena value lastwhite time it to false

if (index == -1)
{
if (lastWhite == true)
{
++words;
}
lastWhite = false;
}
else
{
lastWhite = true;
}

System.out.println("chars" + chars + " words" + words + " lines " + lines);
}

/*if (chars != 0)
{
++lines;
}*/


}
}

WAP to Print a Binary tree in level order with a new line after every level.

Data Structure Used Queue

Algorithm Shown Below

printLevelorder(tree)
Initialize the global variable size=0
1) Create an empty queue q
2) temp_node = root /*start from root*/ & initialize the local variable cur_size=0
3) Loop while temp_node is not NULL
A) print temp_node->data.
B) Enqueue temp_node’s children (first left then right children) to q
C) After this check cur_size is equals to zero or not
if(cur_size==0)set cur_size=size of queue(no of elements at that time in queue
D) Dequeue a node from q and assign it’s value to temp_node
E) Decrement the cur_size until it become zero so that we can re-initialize it
again with new size of queue.


#include
#include
#define MAX_Q_SIZE 100

/* 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;
};

/* frunction prototypes */
struct node** createQueue(int *, int *);
void enQueue(struct node **, int *, struct node *);
struct node *deQueue(struct node **, int *);

int size=0;

/* Given a binary tree, print its nodes in level order
using array for implementing queue */
void printLevelOrder(struct node* root)
{
int rear, front;
struct node **queue = createQueue(&front, &rear);
struct node *temp_node = root;
int nsize=0;

while(temp_node)
{
printf("%d ", temp_node->data);

/*Enqueue left child */
if(temp_node->left)
enQueue(queue, &rear, temp_node->left);

/*Enqueue right child */
if(temp_node->right)
enQueue(queue, &rear, temp_node->right);
if(nsize==0)
{
nsize=size;
printf( " \n ");
}

/*Dequeue node and make it temp_node*/
temp_node = deQueue(queue, &front);
nsize--;
}
}

/*UTILITY FUNCTIONS*/
struct node** createQueue(int *front, int *rear)
{
struct node **queue =
(struct node **)malloc(sizeof(struct node*)*MAX_Q_SIZE);

*front = *rear = 0;
return queue;
}

void enQueue(struct node **queue, int *rear, struct node *new_node)
{
queue[*rear] = new_node;
(*rear)++;
size++;
}

struct node *deQueue(struct node **queue, int *front)
{
(*front)++;
size--;
return queue[*front - 1];
}

/* 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);
}

/* Driver program to test above functions*/
int main()
{
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->left->left = newNode(41);
root->left->right = newNode(5);
root->right->left = newNode(6);
root->right->right = newNode(7);
root->right->right->right = newNode(71);


printf("Level Order traversal of binary tree is \n");
printLevelOrder(root);

getchar();
return 0;
}

Time Complexity O(n)
Space Complexity O(1)
Run Here https://ideone.com/FLgSI

Write a method to shuffle a deck of cards. It must be a perfect shuffle - in other words, each 52! permutations of the deck has to be equally likely. Assume that you are given a random number generator which is perfect.

Design The Algorithm for AutoComplete Feature of Google

Autocomplete is a program function that enables inputting the text (in editors, command line shells, browsers etc.) completing the text by its inputted part. Vasya is busy working on a new browser called 'BERowser'. He happens to be working on the autocomplete function in the address line at this very moment. A list consisting of n last visited by the user pages and the inputted part s are known. Your task is to complete s to make it an address of one of the pages from the list. You have to find the lexicographically smallest address having a prefix s. 

Input text- 

next

select output from 

nextelement       ---- Answer

nextpermutation

Device An Algorithm to Find minimal number of moves the to pegs to transform from the initial to final configuration. .

There are K pegs. Each peg can hold discs in decreasing order of radius when looked from bottom to top of the peg. There are N discs which have radius 1 to N; Given the initial configuration of the pegs and the final configuration of the pegs, output the moves required to transform from the initial to final configuration. You are required to do the transformations in minimal number of moves.

• A move consists of picking the topmost disc of any one of the pegs and placing it on top of anyother peg.
• At anypoint of time, the decreasing radius property of all the pegs must be maintained.

Convert Given Message Sequence in to Corrsponding Digits

The Latin alphabet contains 26 characters and telephones only have ten digits on the keypad. We would like to make it easier to write a message to your friend using a sequence of keypresses to indicate the desired characters. The letters are mapped onto the digits as shown below. To insert the character B for instance, the program would press 22. In order to insert two characters in sequence from the same key, the user must pause before pressing the key a second time. The space character ' ' should be printed to indicate a pause. For example, 2 2 indicates AA whereas 22 indicates B.

Example

hi      Case #1: 44 444 yes     Case #2: 999337777 foo bar Case #3: 333666 6660 022 2777 hello world   Case #4: 4433555 555666 Follow Up-Now Think if Question asked reverse e.g. Given a telephone number print or produce all the possible telephone words or combinations of letters that can represent the given telephone number, then can you device an algorothm that will solve this problem efficiently. This is More Simple Then Previous One.

How fast can robots can complete the given sequence

Blue and Orange are friendly robots. An evil computer mastermind has locked them up in separate hallways to test them, and then possibly give them cake.
Each hallway contains 100 buttons labeled with the positive integers {1, 2, ..., 100}. Button k is always k meters from the start of the hallway, and the robots both begin at button 1. Over the period of one second, a robot can walk one meter in either direction, or it can press the button at its position once, or it can stay at its position and not press the button. To complete the test, the robots need to push a certain sequence of buttons in a certain order. Both robots know the full sequence in advance. How fast can they complete it?
For example, let's consider the following button sequence:
   O 2, B 1, B 2, O 4
Here, O 2 means button 2 in Orange's hallway, B 1 means button 1 in Blue's hallway, and so on. The robots can push this sequence of buttons in 6 seconds using the strategy shown below:

Time | Orange           | Blue
-----+------------------+-----------------
  1  | Move to button 2 | Stay at button 1
  2  | Push button 2    | Stay at button 1
  3  | Move to button 3 | Push button 1
  4  | Move to button 4 | Move to button 2
  5  | Stay at button 4 | Push button 2
  6  | Push button 4    | Stay at button 2

Note that Blue has to wait until Orange has completely finished pushing O 2 before it can start pushing B 1.

catalan number pdfs

http://mathcircle.berkeley.edu/BMC6/pdf0607/catalan.pdf
http://www-math.mit.edu/~rstan/ec/catadd.pdf

How many paths from one corner to the diagonally opposite corner in an n x n matrix do not cross the diagonal?

A sequence of n numbers, 1 thru n, is processed as follows: we either drop the next number into a stack, or we pop the topmost number of the stack. In 2n operations, all numbers would have been processed and the stack would also be empty. The output is the sequence of elements that were popped. How many output sequences are possible?

In how many ways may we pick a subset from 1, 2, 3, 4, … n so that no two successive numbers are picked?

The Britney Spears Problem ,Tracking who's HOT and who's not , presents an algorithmic challenge ?

 By Brian Hayes

• Back in 1999, the operators of the Lycos Internet portal began publishing a weekly list of the 50 most popular queries submitted to their Web search engine. Britney Spears—initially tagged a "teen songstress," later a "pop tart"—was No. 2 on that first weekly tabulation. She has never fallen off the list since then—440 consecutive appearances when I last checked. Other perennials include ­Pamela Anderson and Paris Hilton. What explains the enduring popularity of these celebrities, so famous for being famous? That's a fascinating question, and the answer would doubtless tell us something deep about modern culture. But it's not the question I'm going to take up here. What I'm trying to understand is how we can know Britney's ranking from week to week. How are all those queries counted and categorized? What algorithm tallies them up to see which terms are the most frequent?

                                  

• One challenging aspect of this task is simply coping with the volume of data. Lycos reports processing 12 million queries a day, and other search engines, such as Google, handle orders of magnitude more. But that's only part of the problem. After all, if you have the computational infrastructure to answer all those questions about Britney and Pamela and Paris, then it doesn't seem like much of an added burden to update a counter each time some fan submits a request. What makes the counting difficult is that you can't just pay attention to a few popular subjects, because you can't know in advance which ones are going to rank near the top. To be certain of catching every new trend as it unfolds, you have to monitor all the incoming queries—and their variety is unbounded.
• In the past few years the tracking of hot topics has itself become a hot topic in computer science. Algorithms for such tasks have a distinctive feature: They operate on a continuous and unending stream of data, rather than waiting for a complete batch of information to be assembled. Like a worker tending a conveyor belt, the algorithm has to process each element of the stream in sequence, as soon as it arrives. Ideally, all computations on one element are finished before the next item comes along.
• Much of the new interest in stream algorithms is inspired by the Internet, where streams of many kinds flow copiously. It's not just a matter of search-engine popularity contests. A similar algorithm can help a network manager monitor traffic patterns, revealing which sites are generating most of the volume. The routers and switches that actually direct the traffic also rely on stream algorithms, passing along each packet of data before turning to the next. A little farther afield, services that filter spam from e-mail can use stream algorithms to detect messages sent in thousands or millions of identical copies.
• Apart from the Internet, stream algorithms are also being applied to flows of financial data, such as stock-market transactions and credit-card purchases. If some government agency wanted to monitor large numbers of telephone calls, they too might have an interest in stream algorithms. Finally, the designers of software for some large-scale scientific experiments adopt a stream-oriented style of data processing. Detectors at particle-physics laboratories produce so much data that no machine can store it all, even temporarily, and so preliminary filtering is done by programs that analyze signals on the fly....................................................to be contd. :)

Interested People Can Read Full Article Here
http://amsciadmin.eresources.com/libraries/documents/2008631225466814-2008-07Hayes.pdf

Identify the ‘Bottleneck Spanning Tree’ of an undirected graph

Given an undirected graph, identify the ‘Bottleneck Spanning Tree’ of an undirected graph, which is defined to be any spanning tree that minimizes the weight of the heaviest edge used in the tree. In the usual ‘Minimum Spanning Tree’ problem, the sum of weights is minimized.

Identify if a given graph is a scorpion or not.

A scorpion is an undirected graph with 3 special vertices: the sting, the tail, and the body. The sting has degree one and is connected to the tail. The tail has degree two and is connected to the sting and the body. The body has degree n – 2 and is connected to all vertices except the sting. The other vertices may be arbitrarily connected with each other. Identify if a given graph is a scorpion or not.

Gray Code for Fibonacci Sequences: identify the starting string and then enumerate these positions in time proportional to the number of strings.

The number of binary strings of length k such that two 1′s are never adjacent in any string equals the k-th Fibonacci number. Further, these strings can be ordered to form a Gray code, which means that successive strings differ in only one position. For example, a Gray code for 3-bit strings is 100 101 001 000 010. The goal is to identify the starting string and then enumerate these positions in time proportional to the number of strings.

Working Computer Problem :discover an undamaged computer in as few queries as possible.

A room has n computers, less than half of which are damaged. It is possible to query a computer about the status of any computer. A damaged computer could give wrong answers. The goal is to discover an undamaged computer in as few queries as possible.

implement procedure find(N,X) that returns 1 if there exists a sensor at height X and returns 0 otherwise.

Animal behavior researchers would like to get information on animal movements in a valley. They have placed N motion sensors along a straight line crossing the valley at various heights. For 0 <= i <= N-1, the i-th sensor's height is h_i (0 <= h_i <= 1 000 000 000). No two sensors are on the same height.
Since the line is on a valley, the heights of sensors satisfy these constraints:

• there is an integer k (0 <= k <= N-1), such that the k-th sensor has the minimum height,
• for all 0 <= i < k, h_i > h_i+1, and
• for all k <= i < N-1, h_i < h_i+1.

However, because the sensor installation team forgot to measure the sensors' heights, the value of k, and all the heights h_i's are not known.
You would like to find if there is a sensor at height X. This seems to be hopelessly impossible, but you recall that each sensor has a height meter and can report its height. To minimize the power usage, you would like to make only a small number of height queries.

Implement

You have to implement procedure find(N,X) that returns 1 if there exists a sensor at height X and returns 0 otherwise. Your procedure can call a procedure query(i) to get h_i. However, you can make at most 50 calls, for each run of procedure find.
Note: In a single run, the sample grader, provided with the prototype, may perform many calls to find in one run. While the sample grader uses the same heights for all calls, the real grader may use different heights between each call to procedure find. Therefore, you should not assume that two different calls to procedure find share the same height information.

Example

Suppose that N=4 and the height of each sensor is:

sensor	height
0	10
1	7
2	9
3	15

Note that in this case, k=1. The following are the return values from procedure query:

calls	returns
query(0)	10
query(1)	7
query(2)	9
query(3)	15

The correct implementation of procedure find, when called by the grader, should return as in the following table.

calls	returns
find(4,10)	1
find(4,2)	0
find(4,9)	1
find(4,15)	1
find(4,100)	0

find the maximum sum of temperatures of K consecutive days

Thailand is a tropical country. Thai people usually say that Thailand has 3 seasons: Hot Summer, Hotter Summer, and Hottest Summer. It especially feels very hot when you have many consecutive days with high temperatures.
You are planning a K-day trip to Thailand. Since you would like to experience the real Thai Summer, you want your stay to be as hot as possible.
You are given a list of forecasted temperatures of N consecutive days. You would like to find the maximum sum of temperatures of K consecutive days. It is guaranteed that 1 <= K <= N.

Implement 

You are to implement procedure maxk(N,T,K) that returns the maximum sum of temperatures of any K consecutive days, where N is the number of days and T is an array of positive integers where T[i], for 0 <= i < N, is the temperature of day i.

Example

Suppose that N=6, K=3 and T = 10 50 30 20 5 1.

There are 4 possible 3-day trips, starting from day 0, day 1, day 2, and day 3; and their sum of temperatures are 90, 100, 55, and 26. Therefore, procedure maxk should return 100.

Subtasks

Subtask 1

• N <= 1 000, 0 < T[i] <= 1 000

Subtask 2

• N <= 1 000 000, 0 < T[i] <= 1 000

you have to encode the data into a sequence of alphabets, transmit the encoded data, and decode it to obtain the original integer data.

You would like to transmit integer data through a special channel, i.e., this channel only supports transmission of alphabets a - z. In order to do so, you have to encode the data into a sequence of alphabets, transmit the encoded data, and decode it to obtain the original integer data.
The overall process is shown in the following figure.

       You have to implement:

• Procedure encode(N,D) that encodes the data, where N denotes the length of data and D is an array of integers representing the data, where D[i] is the i-th integer in the data. (0 <= D[i] <= 255.) This procedure must call procedure send_data(c) for each character c in the sequence to transmit the encoded data. Each encoded character c must be lowercase English alphabets, i.e., alphabets a - z.
  
  Procedure decode(M) that decodes the data, where M denotes the length of the encoded data. To read the encoded data as a sequence of characters, this procedure must call procedure read_data() for each character in the sequence. It may call read_data for at most M times. To output the decoded data, it must call procedure output_data(y) for each integer y in the decoded data.
  
   Follow Up
  

  Subtask 1

• N <= 100 and 0 <= D[i] <= 25.
• The encoded data should not contain more than 100N characters, i.e., encode may not call send_data more than 100N times.

        Subtask 2

• N <= 100.
• The encoded data should not contain more than 100N characters, i.e., encode may not call send_data more than 100N times.

        Subtask 3 (40 points)

• N <= 100.
• The encoded message should not contain more than 2N characters, i.e., encode may not call send_data more than 2N times.

You need to write a program that calculates the advanced edit distance of two given words.

The edit distance of two strings S and T is the minimum number of edit operations that need to be done to transform S into T . The valid edit operations are:
• Insert a single character at any position.
• Modify an existing character.
• Remove an existing character.
For example, the edit distance of “pantera” and “aorta” is 5, because the following chain of
edits is valid (and there is no shorter chain):
“pantera” >>> “antera” >>> “aotera” >>> “aoera” >>> “aora” >>> “aorta”.
We define the advanced edit distance in a similar way, but adding the swap of two adjacent characters as an extra valid operation. With this setting, the advanced edit distance of “pantera” and “aorta” is 4:
“pantera” >>> “antera” >>> “antra” >>> “aotra” >>> “aorta”.

You need to write a program that calculates the advanced edit distance of two given words.

In given array of elements like [a1,a2,a3,..an,b1,b2,b3,..bn,c1,c2,c3,...cn] Write a program to merge them like [a1,b1,c1,a2,b2,c2,...an,bn,cn]. We have to do it in O(1) extra space.

Transpose Algorithm 

Basically, we are converting rows into columns. E.g. a1 a2 a3 a4 b1 b2 b3 b4 c1 c2 c3 c4 should be changed to a1 b1 c1 a2 b2 c2 a3 b3 c3 a4 b4 c4.

a1 b1 c1 (i=1)

a2 b2 c2 (i=2)

a3 b3 c3 (i=3)

a4 b4 c4 (i= 4)

So we should write the array as a1 a2 a3 a4 b1 b2 b3 b4........, only this time, we are writiing column wise.

The program is recursive. The variable i is the number of groups

#include

#define SIZE 12 //multiple of 3

void arrange(int arr[], int n, int i)

{

if(i == 1)

{

arr[1] = arr[n];

arr[2] = arr[n <<1]

return;

}

int a = arr[i - 1];

int b = arr[n + i - 1];

int c = arr[2*n + i - 1];

arrange(arr, n, i - 1);

int x = 3 * (i - 1);

arr[x] = a;

arr[x + 1] = b;

arr[x + 2] = c;

}

int main()

{

int n = SIZE;

int a[SIZE], i;

printf("\nEnter %d numbers", SIZE);

for(i = 0; i <>

scanf("%d", a + i);

if(n != 0 && n % 3 == 0)arrange(a, n/3, n/3);

for(i = 0; i <n;i++)
printf(a[i]);

printf("\n");

}

Given a root and a node of a BST tree, write a function which print all the nodes which are a 'k' distance from the given nodes in sorted order. (distance can be upwards and downwards)

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.

Beaded Necklace-Find a sequence of such operations with minimum total cost for a given initial distribution of beads.

You are given a circular necklace containing n beads. Each bead maybe black or white. You have to rearrange the beads so that beads of the same color occur consecutively.

The only operation allowed is to cut the necklace at any point, remove some number of beads from both ends and put them back in any order, and join the cut ends. The cost of this operation is the number of beads removed. Any number of such operations can be used. You have to find a sequence of such operations with minimum total cost for a given initial distribution of beads.

For example, if the initial string is wbwbwb, this can be done by a single operation of cost 4, or two operations of cost 2 as shown.

Describe a polynomial-time algorithm for this problem; with short proof of correctness. You get points only if you match (or better) the judge solution's time complexity.

Save Me Please, Doctor!

Mr. Bean drinks from a water bottle that he carried for a long time without re lling, and
the stale water has resulted in him su ering from mild dysentery. He goes to a nearby nursing
home and gets diagnosed with Amoebiasis. The doctor identi es the pathogen to be a partic-ular kind of amoeba that has two variants, namely Asperdabrum (a) and Bostonostrum (b).
Each amoeba reproduces every hour by splitting into two, a !ab, and b !ba, and they stick
together in a chain in that particular sequence. At every step of reproduction, all the present
amoeba undergo binary ssion. For e.g. starting with type a, after 1st step the chain is ab,
after 2nd step the chain is abba, after the 3rd step the chain is abbabaab and so on. Mr.Bean
was infected n hours ago by a single amoeba and the doctor needs to know the type of the kth amoeba in the chain present now to be able zo nd a cure. Help the doctor cure him.

Input Format:
First line contains the number of test cases T. For each test case, there will be a single line of
input that starts with a character denoting the type of amoeba, , that infected him initially (a
or b) followed by two integers, n - the number of hours that have passed since he was infected,
and k - the position at which the doctor needs to know the type of amoeba.
Limits: 1<= T<=1000000, 1<= N<=4100, 1<=K<=2^N
.
Moreover, for the rst test le you can assume N, K lie within integer range (32 bits).

Output Format:
For each test case, output on a separate line the type of the kth amoeba in the current chain.

Sample Input:
2
a 3 3
b 4 6
Sample Output:
b
b

Source BITWise IITKGP,

Place N number from 1 to N, in 2N positions in such a way so that there are Exactly “n” number of cells between two placed locations of number “n”

Write a program to display numbers placed in this way.

Example:-

(1) One of the possible placement for 7 numbers in 14 positions is :

5 7 2 3 6 2 5 3 4 7 1 6 1 4

write an algorithm that outputs each point along with the three other points that are closest to it.

You are given a list of points in the plane, write a program that
outputs each point along with the three other points that are closest
to it. These three points ordered by distance.
The order is less then O(n^2) .

For example, given a set of points where each line is of the form: ID
x-coordinate y-coordinate


1  0.0      0.0
2  10.1     -10.1
3  -12.2    12.2
4  38.3     38.3
5  79.99    179.99



Your program should output:


1 2,3,4
2 1,3,4
3 1,2,4
4 1,2,3
5 4,3,1

Determine whether a number is colorful or not. 263 is a colorful number because (2,6,3,2x6,6x3,2x3x6) are all different whereas 236 is not because (2,3,6,2x3,3x6,2x3x6) have 6 twice. So take all consecutive subsets of digits, take their product and ensure all the products are different

first point from where a truck will be able to complete the circle.

Given a circle. You have five points on that circle. Each
point corresponds to a petrol pump. You are given two sets of data.

1. The amount of petrol that petrol pump will give.
2. Distance from that petrol pump tp the next petrol pump.

(Assume for 1 lit Petrol the truck will go 1 km)

Now calculate the first point from where a truck will be able to
complete the circle.
(The truck will stop at each petrol pump and it has infinite
capacity).
Give o(n) solution. You may use o(n) extra space.

The Social Network (2010) - FaceMash Algorithm

I saw Social Network 2-3 times in 1 week. Not for entertainment. Not because I had nothing better to do. But because I wanted to understand the math and computer science fundae used in the movie. I would like to discuss one particularly interesting scene from the movie.

You may remember Mark inviting his friend Eduardo to give him his chess algorithm at the beginning of the movie (Mark was drinking, blogging and hacking simultaneously and creating Facemash.com). You may also remember the scribbles on the window:

and

What is this? This is actually the math behind Elo Rating System. Elo rating system is a method for calculating the relative skill levels of players in two-player games such as chess. It is named after its creator Arpad Elo, a Hungarian-born American physics professor.

As explained in the movie, Facemash was quite simple. Not unlike hotornot.com, students went to a page and 2 random images of girls were picked and presented to them. The students then had to click on the hottest girl presented to them and then another set of two girls would be presented asking the students to repeat the same actions they had done. The difference with hotornot was that the girls presented were all Harvard students. In other words, the students were rating girls of Harvard based on their looks (You can imagine why Mark got into trouble).

The algorithm used - The Elo Rating system - insured a fair rating and ranking of the girls. A hot girl A winning over hot girl B girl would gain more points than winning (or being picked) against ugly girl C. Same goes for the following: ugly girl C wins over ugly girl D. ugly girl C gains some points in her general ranking. If ugly girl C wins over hot girl A then ugly girl C gains more points because the ranking of hot girl A is much higher than ugly girl D. The previous scenario is roughly what the algorithm implemented by Mark was doing. It was somewhat insuring a level of fairness despite the misogynistic nature of the product.

In today’s society, the Elo Rating system is used by many rating and ranking system to predict the outcome of matches but also insure a level of fairness between teams of different levels playing against each others. FIFA uses it to rank football teams.

You can read more about the system on wikipedia page(http://en.wikipedia.org/wiki/Elo_rating_system).

Why Programmer Works @ Night ..A Programmer Must Read :)

I found this quite Interesting, so posting this article, have a good read and happy coding.

A popular saying goes that Programmers are machines that turn caffeine into code.

And sure enough, ask a random programmer when they do their best work and there’s a high chance they will admit to a lot of late nights. Some earlier, some later. A popular trend is to get up at 4am and get some work done before the day’s craziness begins. Others like going to bed at 4am.

At the gist of all this is avoiding distractions. But you could just lock the door, what’s so special about the night?

I think it boils down to three things: the maker’s schedule, the sleepy brain and bright computer screens.

The maker’s schedule

Paul Graham wrote about the maker’s schedule in 2009 – basically that there are two types of schedules in this world (primarily?). The traditional manager’s schedule where your day is cut up into hours and a ten minute distraction costs you, at most, an hour’s worth of time.

Image via Wikipedia

On the other hand you have something PG calls the maker’s schedule – a schedule for those of us who produce stuff. Working on large abstract systems involves fitting the whole thing into your mind – somebody once likened this to constructing a house out of expensive crystal glassand as soon as someone distracts you, it all comes barreling down and shatters into a thousand pieces.

This is why programmers are so annoyed when you distract them.

Because of this huge mental investment, we simply can’t start working until we can expect a couple of hours without being distracted. It’s just not worth constructing the whole model in your head and then having it torn down half an hour later.

In fact, talking to a lot of founders you’ll find out they feel like they simply can’t get any work done during the day. The constant barrage of interruptions, important stuff ™ to tend to and emails to answer simply don’t allow it. So they get most of their “work work” done during the night when everyone else is sleeping.

The sleepy brain

But even programmers should be sleeping at night. We are not some race of super humans. Even programmers feel more alert during the day.

Ballmer's peak

Why then do we perform our most mentally complex work work when the brain wants to sleep and we do simpler tasks when our brain is at its sharpest and brightest?

Because being tired makes us better coders.

Similar to the ballmer peak, being tired can make us focus better simply because when your brain is tired it has to focus! There isn’t enough left-over brainpower to afford losing concentration.

I seem to get the least work done right after drinking too much tea or having a poorly timed energy drink. Makes me hyperactive and one second I’m checking twitter, the next I’m looking at hacker news and I just seem to be buzzing all over the place..

You’d think I’d work better – so much energy, so much infinite overclocked brainpower. But instead I keep tripping over myself because I can’t focus for more than two seconds at a time.

Conversely, when I’m slightly tired, I just plomp my arse down and code. With a slightly tired brain I can code for hours and hours without even thinking about checking twitter or facebook. It’s like the internet stops existing.

I feel like this holds true for most programmers out there. We have too much brainpower for ~80% of the tasks we work on – face it, writing that one juicy algorithm, requires ten times as much code to produce an environment in which it can run. Even if you’re doing the most advanced machine learning (or something) imaginable, a lot of the work is simply cleaning up the data and presenting results in a lovely manner.

And when your brain isn’t working at full capacity it looks for something to do. Being tired makes you dumb enough that the task at hand is enough.

Bright computer screens

This one is pretty simple. Keep staring at a bright source of light in the evening and your sleep cyclegets delayed. You forget to be tired until 3am. Then you wake up at 11am and when the evening rolls around you simply aren’t tired because hey, you’ve only been up since 11am!

Image via Wikipedia

Given enough iterations this can essentially drag you into a different timezone. What’s more interesting is that it doesn’t seem to keep rolling, once you get into that equilibrium of going to bed between 3am and 4am you tend to stay there.

Or maybe that’s just the alarm clocks doing their thing because society tells us we’re dirty dirty slobs if we have breakfast at 2pm.

Fin

To conclude, programmers work at night because it doesn’t impose a time limit on when you have to stop working, which gives you a more relaxed approach, your brain doesn’t keep looking for distractions and a bright screen keeps you awake.

Source : http://swizec.com/blog/why-programmers-work-at-night/swizec/3198

Problem: You are given a two dimensional bit array(elements are 0 or 1). Find number of islands in this array. One island is defined as all elemnts which are 1, including neighbours(with or without diagonals). Or Array Islands problem.

Happy New Year to All :) have a Gr8 & Safe New Year Ahead :) May God Fulfill all of Your Dreams :) Promise to Show More Code Hacks in this year :)