CareerCup

Bubble Sort best is O(n^2) and not O(n)

Method 1:
lowermost layer = n*n
uppermost layer = n*n
in between = (n-2)*(4*(n-1)) = (n-2)*(4n-4)=4*n*n -12n +8

Total = 6*n*n -12n +8

Method 2:
Total exposed cube surfaces on one flat surface = n*n
Total exposed cubes surfaces on 6 flat surfaces = 6*n*n ---(1)
No. of surfaces having another exposed surface in its cube twice or more times = No. of edges * cubes/edge = 12 * n ---(2)
No. of surfaces having 3 exposed surfaces in it's cube = No. of cornwes =8 ---(3)



Total no. of exposed cubes = (1) - (2) + (3)
= 6*n*n -12n +8

import java.io.*;
import java.util.*;


class rf{
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		String str = sc.nextLine();

		//Solution 1.
		int l=str.length();
		String reverse="";
		for(int i=l-1;i>=0;i--)
			reverse= reverse + str.charAt(i);
		System.out.println(reverse);

		//Soultion 2.
/*
		StringBuilder sb= new StringBuilder(str);
		reverse = sb.reverse().toString();
		System.out.println(reverse);
*/

}

}

Ok. That is one way, but do you know any offline ways? I mean like in C we use printf() but don't have the code for it. How does it work?

interfaces don't contain implementations. So how am i sharing the implementation details? I mean something like dll file perhaps? I don't know much about it though.
I mean to ask in what particular format should I share the implementation details

In C and C++ yes, it is allowed.
In java you will get 'ArrayIndexOutOfBoundsException'.
You can easily mess around with addresses in C. That is both the beauty and the drawback of using C language.

Now try predicting the output of this question:

#include<stdio.h>
int main()
{
	int a[3],i;
	for(i=-1;i<3;i++)
	{
//		printf("i is %d\n",i);
		a[i]=-2;
//		printf("i is %d\n",i);
	}
}

This gives you an infinite loop because a[-1] points to i
a[i]=-2 means i=-2.
Then i++ changes i to -1
and it gets stuck in an infinite loop!

Due to these security issues is C, there came the arrival of a new programming language- Java, which is nothing but modified C++ to remove security vulnerabilities and have better checks for overflows,etc.

DFS comes to our rescue.
if you observe a little you can find out that there is a nice pattern
Start with a char 1-9 in that order (9 iterations).
Add a 0-9 to right of string one at a time and recursively do dfs.
if value<=n print it.
recursively keep on adding char to the right.
when value>n. return from dfs call.

Here is the fully working code in C++

#include<stdio.h>
#include<stdlib.h>
using namespace std;
char s[8]="";
int n;
void dfs(int i)//i is the position of null character. initially null is at 0
{
	s[i+1]='\0';
	for(int j=48;j<=57;j++)//ascii 48 to 57 is '0' to '9'
	{
		s[i]=j;
		if(atoi(s)<=n)
		{
			printf("%s ",s);
			dfs(i+1);//add characters to the right
		}
		else
			break;
	}
	s[i]='\0';
}
int main()
{
	scanf("%d",&n);
	s[1]='\0';
	for(int j=49;j<=57;j++)//ascii for char '1' to '9'
	{
		s[0]=j;
		if(atoi(s)<=n)
		{
			printf("%s ",s);
			dfs(1);			
		}
		else
			break;
	}
	return 0;
}

In concurrent programming, a critical section is a piece of code that accesses a shared resource (data structure or device) that must not be concurrently accessed by more than one thread of execution. A critical section will usually terminate in fixed time, and a thread, task, or process will have to wait for a fixed time to enter it (aka bounded waiting). Some synchronization mechanism is required at the entry and exit of the critical section to ensure exclusive use, for example a semaphore.

mutex is short for mutual exclusion object. In computer programming, a mutex is a program object that allows multiple program threads to share the same resource, such as file access, but not simultaneously. When a program is started, a mutex is created with a unique name. After this stage, any thread that needs the resource must lock the mutex from other threads while it is using the resource. The mutex is set to unlock when the data is no longer needed or the routine is finished.

Yes, threads within the same process or within other processes can share mutexes.

time O(n^2) space O(n^2) solution.
we will need a 2D array visited[n][n] and two global vars->start and max=0.
Now we will traverse the matrix row by row.
for each 'not visited' element k start a recursive dfs such that next element is k+1.
Mark all traversed elements as visited so that you do not start a traversal from them again
the dfs() will return you the depth value till which it could go.
e.g. for 6 it will return 4 (6-7-8-9). for 7 it will return 3 (7-8-9).
if this value is greater than max, then update max and start value.

At last print max no. of consecutive characters from start value.

Saurabh, you were almost there.
You just ended your binary search prematurely.
we have the sorted array={1,2,3,4,900,901,902,903,1000}
after 2nd iteration we have min=1(index of 2) max=3

3rd iteration:
pivot value=3
no of elements on right side of 3>3
so we move right

4th iteration:
min=2 max=3
pivot=4 (since we already know 3 satisfies the property)
now for 4 we have >=4 values which are>4

now min=max=3
This is our final answer -> 4

Here is the fully working Java code for 1 player vs computer Tic Tac Toe game.
Compile it. Run it!

import java.util.Random;
import java.util.Scanner;
import java.io.*;
class Player
{
	private int score;
	private String name;
	Player()
	{
		name="Unknown";
		score=0;
	}
	Player(String name)
	{
		this.name=name;
		score=0;
	}
	public void addScore(int add)
	{
		score+=add;
	}
	public int getScore()
	{
		return score;
	}
	public String getName()
	{
		return name;
	}
}
class Board
{
	private final int size=3;
	private boolean gameOver;
	private boolean win;
	private int noOfMoves;
	private char[][] matrix=new char[size][size];
	Board()
	{
		int i,j;
		for(i=0;i<size;i++)
			for(j=0;j<size;j++)
				matrix[i][j]='.';
		gameOver=false;
		win=false;
		noOfMoves=0;
	}
	public void show()
	{
		int i,j;
		for(i=0;i<size;i++)
		{
			for(j=0;j<size;j++)
				System.out.print(" "+matrix[i][j]);			
			System.out.println();
		}
		System.out.println();
	}
	public boolean isGameOver()
	{
		return gameOver;
	}
	public boolean won()
	{
		return win;
	}
	public int playerMove(int x,int y)//1 player game against Computer
	{
		if(x<0 || y<0 ||x>=size || y>=size)
			return -1;//invalid move;
		if(matrix[x][y]=='O' || matrix[x][y]=='X')
			return -1;//invalid move
		matrix[x][y]='X';
		noOfMoves++;
		return 0;
	}
	public void computerMove()//1 player game against Computer
	{	//random move
		Random rand=new Random();
		int x,y;
		x=rand.nextInt(size);
		y=rand.nextInt(size);
		while(matrix[x][y]=='X' || matrix[x][y]=='O')
		{
			x=rand.nextInt(size);
			y=rand.nextInt(size);
		}
		matrix[x][y]='O';
		noOfMoves++;
	}
	public void setWon(char c)
	{
		if(c=='.')
			return;
		if(c=='X')
			win=true;
		else
			win=false;
		gameOver=true;
	}
	public void check()
	{
		int i,j;
		boolean f;
		for(i=0;i<size;i++)
		{
			j=1;
			if(matrix[i][0]!='.')
				for(;j<size;j++)//ith row check
					if(matrix[i][j]!=matrix[i][j-1])
						break;
			if(j==size)
			{
				System.out.println("row "+i+" crossed");
				setWon(matrix[i][0]);
				return;
			}
			j=1;
			if(matrix[0][i]!='.')
				for(;j<size;j++)//ith column check
					if(matrix[j][i]!=matrix[j-1][i])
						break;
			if(j==size)
			{
				System.out.println("col "+i+" crossed");
				setWon(matrix[0][i]);
				return;
			}
		}
		//diagonals
		i=1;
		if(matrix[0][0]!='.')
		for(;i<size;i++)
			if(matrix[i][i]!=matrix[i-1][i-1])
				break;
		if(i==size)
		{
			System.out.println("first diagonal "+i+" crossed");
			setWon(matrix[0][0]);
			return;
		}
		i=1;
		if(matrix[0][size-1]!='.')
		for(;i<size;i++)
			if(matrix[i][size-1-i]!=matrix[i-1][size-i])
				break;
		if(i==size)
		{
			System.out.println("second diagonal "+i+" crossed");
			setWon(matrix[0][size-1]);
			return;
		}
		if(noOfMoves>=size*size)
		{
			gameOver=true;
			win=false;
		}
		return;
	}
}
class TTT
{
	public static void main(String args[])
	{
		Scanner sc=new Scanner(System.in);
		Board board=new Board();
		Player player=new Player();
		int x,y;
		while(!board.isGameOver())
		{
			board.show();
			x=sc.nextInt();
			y=sc.nextInt();
			while(board.playerMove(x,y)==-1)
			{
				System.out.println("Invalid input. Enter again!");
				x=sc.nextInt();
				y=sc.nextInt();		
			}
			board.check();
			if(!board.isGameOver())
			{
				board.computerMove();
				board.check();
			}
		}
		board.show();
		if(board.won())
			System.out.println("Congrats! You won!!!!");
		else
			System.out.println("You lose! Go practice some more.");
	}
}

1. first name<3 characters
2. password<8 characters
3. password does not contain any integer
4. password does not contain any special character like _ ; '.:& @$%+
5. invalid email id format
6. email id already taken
7. email id starts with a ' ' space
8. password starts with a space
9. password>40 characters
10. email id>40 characters
11. age<18
12. D.O.B. not entered
13. password mismatch
14. country not entered
14. mobile no. not entered
15. mobile no. invalid
16. captcha does not match with input value
17. terms and conditions not accepted
18. last name not entered
19. submit after 10 minutes of requesting reg. form
20. email id is only 1 charactere long (before @)

1.private variables.
2.public get and set methods
3.multiple constructor-without args,with 1,2,3,... args,copy constructor
4.do i need to overload operators? +,-,=. eg.in matrix class overloading + will simplify usage
5.destructor. free memory if you allocated any
6.Do I need virtual functions or an abstract class or just a simple class?

sort in mlog(m)
then binary search log(m)

C++ code

{
struct node{
	struct node *left,*right;
	int lcount,rcount;
	int data;
}*root;
const int INFINITY=1000000000;
int low,high;
int main()
{
	int low,high;
	//build tree and input low and high...
	int res=findcount(root,-INFINITY,INFINITY);
	printf("result: %d\n",res);
	return 0;
}
int findcount(struct node * root,int lbound,int rbound)
{
	if(root==NULL)
		return 0;
	if(root->data > high)
	{
		//search left side only
		return findcount(root->left,lbound,root->data);
	}
	else if(root->data < low)
	{
		//search left side only
		return findcount(root->right,root->data,rbound);
	}
	else
	{
		//search both side
		if(lbound>=low && rbound<=right)//if all further children are within low & high, no need to iterate further 
			return 1 + root.lcount + root.rcount;
		else
			return 1 + findcount(root->left,lbound,root->data) + findcount(root->right,root->data,rbound);
	}
}

}

3306
you can run command 'nmap localhost' on your linux machine to verify it if you have sql installed

3306
you can run command 'nmap localhost' on your linux machine to verify it if you have sql installed

ip address corresponding to a domain name
e.g. google 74.125.68.113

Multicast- Send message to group of devices, not necessarily every device on your network
Broadcast- Send message to every device on your network

Hubs can only broadcast messages as they work at physical level of OSI model and thus does not understand MAC(Media Access Control) addresses.
Switch, however is also capable of multicasting as it works on the data link layer and can distinguish devices by their MAC addresses

n=4 books ->order will not be taken
n=5 ->order taken. No discount
n=100 -> order taken. No discount
n=101 ->order taken. 20% discount

hey the question does not permit you to output just the last 10 digits.
It should make use of 2 arrays to hold 2 big no.s and add 2nd to 1st.

There are two types of threads-
1.user level threads ULT
they run in user mode

2.kernel level thread KLT
they run in kernel mode

Now if a ULT executes a blocking system call,all the threads of process are blocked.
However there is a technique 'jacketing' that can be used to convert a blocking system call to a non blocking system call.

In a KLT , blocking a thread does not block the whole process.

firefox -> new tab is a thread
chrome-> process . actually you have a separate task manager for chrome. just press shift+Esc

A process can contain multiple threads.
That is to say that a thread is the smallest unit of execution of a process.
A process can basically be divided to have two units-

1.Resource ownership
resources like virtual address space , main memory , I/O devices and files are owned by the process

2.execution unit->this is the one that is generally often called thread
this unit is totally independent from the resource ownership unit.

threads have their shared address space and individual private address space.
They are a means to divide a process into various modules that can execute independently.

simply speed of access of various memory devices are in the order
register > cache > RAM > hard-drive
Now, when you are running multiple processes on the system process switching keeps on happening.
When a new process is scheduled for execution and there is not enough memory in RAM to keep the previous one ,the process is swapped out to disk which is a slower memory than RAM.This swapping out is a wastage of time.
Later when the old process is rescheduled to execute, it again needs to be swapped in from the slower hard-drive. This is a wastage of time. While the process is being swapped in or out the processor remains idle. Hence, it is not desirable and we prefer to have larger RAM sizes to avoid keeping the processor idle.

tree
AVL tree
graph
trie
heap
stack
queue
union set
hash table

Java code //not fully implemented. it is already 100 lines!!

interface data{
	//cell types;
	enum cellType={EMPTY=0,MINE=1,LIFE=2,MONEY=3,CLICKED=4};
	const int SIZE=8;

} 
class Board implements data
{
	int[][] board;
	int noOfMines;
	int size;
	Board()
	{
		board=new int[size][zise];
		size=SIZE;
		initCells();
	}
	Board(int n)
	{
		size=n;
		board=new int[size][zise];
		initCells();
	}
	void initCells()
	{
		Random rand=new Random();
		noOfMines=7+rand.nextInt(7);//7 to 13 mines per game
		plantMines();//not implemented.just use a random fn to get i and j and put board[i][j]=MINE
	}
	int move(int x)//returns score added
	{
		int i=x/8,j=x%8;//get cell location x= i*8 + j
		int val=board[i][j];
		if(val==CLICKED)
			return 0;//already clicked . do nothing
		if(val==EMPTY)
		{
			int scoreToAdd=openUpCellsRecursively();
			return scoreToAdd;
		}
		else if(val==MINE)
		{
			alive=false;
			openSingleCell(x);
			return -1;//-1=dead
		}
		else if(val==MONEY)
		{
			return 100;//100 score bonus on clicking a MONEY cell 
		}
	}
}
class Player{
	String name;
	int noOflives;
	boolean alive,won;
	void init()
	{
		alive=true;
		won=false;
		noOflives=1;
	}
	Player()
	{
		init();
		name="player";
	}
	Player(String pname)
	{
		init();
		name=pname;
	}	
	int getinput()
	{
		Scanner sc=new Scanner(System.in);
		int x=sc.nextInt();//input cell no, assuming cells are numbered 1 to 64 row-wise for size=8
		return x;
	}
}
class Game
{
	Player player;
	Board board;
	boolean alive;
	public static void main()
	{
		player=new Player("John");
		board=new Board();
		while(player.alive && !player.won)
		{
			int input=player.getinput();
			int val=board.move(input);
			if(val==-1)
				player.alive=false;
			else
				if(val>0)
					player.score+=val;
		}
	}
}

simple BFS will do,though you will have to store currently traversed path node by node in the stack

int rand7()
{
	int x,y,z,n=0;
	while((x=rand5())==2);
	x/=2;
	while((y=rand5())==2);
	y/=2;
	while((z=rand5())==2);
	z/=2;
	n=4*x+2*y+1*z;
	return n;
}

precompute till 10^6 using D.P.
Then use recursion that stops if n<=1000000

This combination of precomputation + recursion should get it done within the time limit

c++ solution

#include<bits/stdc++.h>
using namespace std;
int main()
{	int i,j,l,hash[10];
	char s[1000001],max;//using string to store number.. no precision issues atleast for a 1000000 digits!!!
	scanf("%s",s);
	for(i=0;i<10;i++)
		hash[i]=0;//initially count of 0..9 digits is 0 in the number
	l=strlen(s);
	i=l-1;
	max='0';
	while(i>=0)//from right to left until we find a smaller digit than present max digit found.
	{
		hash[s[i]-48]++;//add digit to hash
		if(s[i]>max)//update max if greater digit found
			max=s[i];
		else if(s[i]<max)//end loop if smaller digit found
			break;
		i--;
	}
	if(i<0)//if number has digits in non increasing order from left to right i.e.no greater no. possible
	{
		puts(s);
		return 0;
	}
	//i currently holds the position of leftmost digit to be changed
	j=s[i]-48+1;
	while(hash[j]==0)
		j++;
	s[i]=48+j;//use digit which is just greater than digit at ith position
	hash[j]--;	
	i++;
	j=0;
	for(;i<l;i++)//update all digits to the right of the previous digit
	{
		while(hash[j]==0)
			j++;
		s[i]=48+j;
		hash[j]--;
	}
	puts(s);
	return 0;
}

1. squares in NxN grid

1X1	 ->  (N)^2
2X2	 ->  (N-1)^2
3X3  ->  (N-2)^2
...
NxN  ->  (1)^2
So, total no. of squares=sigma(N^2) over N
					=(N)*(N+1)*(2*N+1)/6

2.squares in MxN grid

let M>N //swap if M<N
let k=M-N
1x1  ->  (N+k)x(N)
2x2  ->  (N-1+k)x(N-1)
3X3  -> (N-2+k)x(N-2) 
...
NxN  ->(1+k)x(1)
So, total no. of squares=sigma((N+k)*(N)) over N
					=sigma(N^2 + k*N)
					=sigma(N^2) +k*sigma(N)
					=(N)(N+1)(2*N+1)/6 + k*N*(N+1)/2

3.rectangles in MxN grid

In an MxN grid you have M+1 horizontal lines
and N+1 vertical lines to enclose a rectangle.
If we choose 2 out of M+1 lines and 2 out of N+1 lines then the intersection of these 4 lines makes a rectangle.

so,answer is 	  (N+1)C(2) * ((M+1)C(2))   		//nCr
			=(N*(N+1)/(2)) * (M*(M+1)/2)