Big Data Analytics:Deep Findings

Question
You are given a tree with N nodes. Each node is given an integer value from 0 to N­1 . Tree given as an input will be an array of parent nodes.
You need to find following (all mandatory):
1 . The depth of the tree (Aim for O(N))
2. Maximum number of children for any node in whole tree (Aim for O(N))
3. Nearest Common Ancestor for two given nodes (Aim for O(log(N)))
INPUT FORMAT
First line has the value of N
Second line has list of N values where the number at index ‘i’ is the parent of node ‘i’. The parent of root is
­1 . ( The index has the range [0,N­1 ] )
Third line contains two integers within the range of [0,N­1 ] whose common ancestor you have to find.
OUTPUT FORMAT
First line has the depth of the tree. Second line has the max children.
Third has the nearest common ancestor to two
given nodes n1 and n2.

Sorting Tutorial

What is Sorting ? Why Sorting?

Sotring is an algorithms  that arranges the elements of a list in certain order.it can be in ascending , descending or any other fashion.sometimes sorting reduces the problem complexity.we can reduce the search complexity.

Classification  categories of sorting ?

1.Number of Comparision 

2.Number of Swap

3.Memory Usages

4.By Recursion

5.Adaptability

Other ways are :

1.INTERNAL(uses main memory only) 

2.EXTERNAL SORT(uses external memory ).

1. Bubble Sort

2. Insertion Sort

3. others

Bubble Sort

Bubble Sort is the simplest sorting algorithm. It works by iterating the input from the first to last.Comparing each pair and swapping them if needed. Bubble sort continues until no swapping needed.it got its name  from the way smaller elements "bubble"  to the top of the list.

Google code jam :Standing Ovation

Problem

It's opening night at the opera, and your friend is the prima donna (the lead female singer). You will not be in the audience, but you want to make sure she receives a standing ovation -- with every audience member standing up and clapping their hands for her.

Sorting : Tournament sort algorithm

Question:Given a team of N players. How many minimum games are required to  find kth best player in O(n+klog(n)) ?

JOSH :Diameter of a Binary Tree

Question: WAP that find out longest Diameter of Tree. The diameter of a tree (sometimes called the width) is the number of nodes on the longest path between two leaves in the tree.

Vinsol : Defected Meter

Question :A Defected meter is given with missing number 4 from it's rim.WAP that convert the wrong  reading into right one.

Example:

input 100

output 81

Google code jam :Alien Language

Question:

After years of study, scientists at Google Labs have discovered an alien language transmitted from a faraway planet. The alien language is very unique in that every word consists of exactly L lowercase letters. Also, there are exactly D words in this language.

Google code jam :Minimum Scalar Product

Problem

You are given two vectors v1=(x1,x2,...,xn) and v2=(y1,y2,...,yn). The scalar product of these vectors is a single number, calculated as x1y1+x2y2+...+xnyn.

Suppose you are allowed to permute the coordinates of each vector as you wish. Choose two permutations such that the scalar product of your two new vectors is the smallest possible, and output that minimum scalar product.

Google Code jam:Reverse Words in O(nm)

Problem

Given a list of space separated words, reverse the order of the words. Each line of text contains L letters and W words. A line will only consist of letters and space characters. There will be exactly one space character between each pair of consecutive words.

Nagarro:GenerateNextDate

Question: Write a function char[] GenerateNextDate(char[]) such that if a date of the format "23Jan201 2" is input, the next date should be produced.

Eg: Input ­ "12-Dec-1987"
Output ­ "13-Dec-1987"
Please remember the input and output are both strings.

Compro: Shifting arrays k positions without using additional memory

Key idea :Swapping based

Google Code jam:StoreCredit

Problem

You receive a credit C at a local store and would like to buy two items. You first walk through the store and create a list L of all available items. From this list you would like to buy two items that add up to the entire value of the credit. The solution you provide will consist of the two integers indicating the positions of the items in your list (smaller number first).

JOSH:Question: WAP that sum up all one child parent nodes without globle variable

//Question: WAP that sum up all one child parent nodes without globle variable
//             3
//            / \
//          4    5
//         / \   \
//        6   8    9
//            /
//           7
//output 8+5=13

Algorithms:Round Robin scheduling Algorithm

Concept:Round-robin (RR) is one of the algorithms employed by process and network schedulers in computing.As the term is generally used, time slices are assigned to each process in equal portions and in circular order, handling all processes without priority (also known as cyclic executive). Round-robin scheduling is simple, easy to implement, and starvation-free. Round-robin scheduling can also be applied to other scheduling problems, such as data packet scheduling in computer networks. It is an Operating System concept.

Pseudo Code : 
* CPU scheduler picks the process from the circular/ready queue , set a timer to interrupt it after 1 time slice    / quantum  and dispatches it .
*  If  process has burst time less than 1 time slice/quantum             
             >  Process will leave the CPU after the completion
             >  CPU will proceed with the next process in the ready queue / circular queue .
    else If process has burst time longer than 1 time slice/quantum
             >  Timer will be stopped . It cause interruption to the OS .
             >   Executed process is then placed at the tail of the circular / ready  querue by applying  the context                   switch
             >  CPU scheduler then proceeds by selecting the next process in the ready queue .        
Here , User can calculate the average turnaround time and average waiting time along with the starting and finishing time of each process

Turnaround time   :   Its the total time taken by the process between starting and the completion.(Completion Time-Arrival Time).

Waiting time         :   Its the time for which process is ready to run but not executed by CPU scheduler(Turnaround time-Burst time )
for example ,
we have three processes arrives at  0 ms.
     
                          Burst time             Waiting time         Turnaround time


P1                          20                          7                          (27-0)27

P2                          3                             4                            7

P3                          4                              7                           11

So here we can see the turnaround time for the process 1 is 30 while 7 and 10 for 2nd and 3rd process

 A Gantt chart is a chart which shows the start and finish times of  all the processes .use time Quantum 4ms.
  Gantt chart for the round robin algorithm with  is

  |--------|-------|-----|------|------|------|-----|
  |   P1    |    P2  | P3  |  P1  | P1  |  P1  | P1  |
  |--------|-------|-----|------|------|------|-----|
 0         4        7     11    15     19     23    27
The major features of the Round Robin algorithm is that

* Throughput is low as the large process is holding up the Central processing unit for execution .

* The main advantage of Round robin is to remove starvation  . As long as all processes completes the execution then we  dont have any trouble, But the problem starts when any of the process fails to complete . The incomplete   execution of any process leads to starvation .

* Queuing is done without using any prioritization of the processes.

AMCAT: INACTIVE AND ACTIVE Puzzle solution in C

Question :There are 8 peoples which are standing in a row. They can have two states on a  respective day: Inactive(0) or Active(1). We were given an array of 8 elements which shows the states of these people today and we have to calculate the state of these people after the given no. of days.

Assumption 1: State of person will be Inactive on the next day if both the adjacent persons are having the Active state or Inactive state today.

Assumption 2: State of person will be Active on the next day if one adjacent person is having Active state and other adjacent person is having Inactive state or vice versa.

Assumption 3: Person on the extreme left and extreme right have only one adjacent person, so we can imagine, the other adjacent person is Inactive.

Ex- 1

Input 1: [0,1,1,0,0,1,0,1], 1

Output 1: [1,1,1,1,1,0,0,0]

Ex-2

Input 2: [0,1,0,1,1,0,1,1], 2

Output 2: [0,1,1,1,1,0,1,1]

 /* After day 1, states will be like this [1,0,0,1,1,0,1,1] 

Optimus information :The Illusionist

Question:Voldemort has now cast a new kind of spell named 'Illusio'. This spell creates the illusion that he is at multiple locations at the same time. Since Harry does not know the location of the real Voldemort, he must destroy all his illusions in order to win.

Assume there is a 2-dimensional square grid with illusions spread across it. Outside the grid, on the boundary, stands Harry Potter. Harry can quickly reach the exterior of any row or column and cast a spell which will destroy all the illusions in that row or column. Realizing that he has very little strength left, he must cast as few spells as possible and destroy all the illusions. Your job is to help him determine the minimum number of spells he will need to destroy all the illusions in the grid and win the duel.

Input

The first line of the input contains an integer N denoting the length of the square grid.

The second line contains an integer T denoting the total number of illusions in the grid.

Then follow T lines, the ith of which contains 2 space-separated integers R[i] and C[i] denoting the (1-based) row and column coordinates of the ith illusion.

Output

A single integer denoting the minimum number of spells needed to destroy all of Voldemort's illusions as per the problem statement.

Constraints

1 <= N <= 100

1 <= T <= N*N

1 <= R[i], C[i] <= N

For all 1 <= i < j <= T, either R[i]!=R[j] or C[i]!=C[j], that is to say that the locations of all the T illusions are distinct

Example

Input:

4

3

1 3

2 1

4 3

Output:

2

Explanation

Since the illusions at (1,3) and (4,3) are both located in column 3, they can be destroyed with a single spell if Harry casts it on column 3. The illusion at (2,1) can be destroyed with another spell either by casting it on row 2 or column 1. This makes a total of 2 spells. It is easy to see that 2 is the least possible number.

Nagarro : Theatre Seat Planing

Question :Write a function for seat allocate and seat reserved.Seat allocate array and seat reserver array.Seat allocate array is of 10*20 and each row and column represent A1 ,A2....;B1 ,B2.....;........J1 ,J2... and so on i.e row are A to J whereas col starts from 0 to 1 9.Each cell in the table represent either 0 or 1 . 0 rep seat available , 1 rep  seat reserved. Seat allocation starts from highest to lowest.And row j is highest, i is second highest and so on.Max 20 seats can be booked at a time. 

if seat is available print the seat no like "B2" i.e (2 row, 3 col)and seat is booked." otherwise Print "Seat is not available."

Nagarro :Resort the array taking absolute value of negative numbers

Question: You are given a sorted array containing both negative and positive values. Resort the array taking absolute value of negative numbers. Your complexity should be O(n)
 Ex. A = {-8,-5,-3,-1,3,6,9} Expected Output: {-1,-3,3,-5,6,-8,9}

JOSH: WAP that sum up all leaf nodes without globle variable

Question: 

WAP that sum up all leaf nodes without globle
input tree  3
           / \
         4    5
        / \    \
       6   8    9
          /
         7
Output 6+7+9=22

AMCAT:Pattern Based Question2

Pattern  for n=6
11111112
32222222
33333334
54444444
55555556
76666666

AMCAT:Pattern Based Question1

Question:For input N print 2N  no. of lines same as following  pattern
Assume input is 4 assume start number is 4
4
55
666
7777
7777
666
55
4 
 Note: i got only idea of Question, not  the extact Question so modify According to your need.

Thoughtworks :StairProblem

This is Screening interview Question asked in Thoughtworks.


Question: Print spiral stair case pattern.

Input: Y is the number of stairs available, X  is the length spiral visible stairs.
Output: Pattern in spiral form.

Stair Problem ...Enter X,Y(Y is number of stair and Y length of stair)
15 4
1
_2
__3
___4
__5
_6
7
8
_9
__10
___11
__12
_13
14
15

Nagarro:Minimum no of counts from the knight to reach the king?

Question. A chessboard was given to us. Where in there was a Knight and King was placed on certain positions. Our aim is to reach the king from the knight in minimum no of counts.As we know, knight can either move 2 steps vertical/horizontal and 1 step horizontal/vertical. same goes here as well. Proper image of the chess board was given in the question paper, and all the positions(max 8) were given that knight can take in the first step.

Nagarro: check whether combination of paranthis is valid or not?

JOSH:Merge two sorted array(first in asc,second dec) into array in ascending order

Solution:
 Merge two sorted array into new sorrted array
input A 1,2,3,4,5(asc)
input B 10,9,8,7,6(dec)
output 1,2,3,4,5,6,7,8,9,10(asc)

Building a Stack with a getMax() function

Building a Stack with a getMax() function
Question:Suppose you had a Stack class. Write a new class MaxStack which, in addition to push() and pop(), has a method getMax() which returns the largest item in the stack. Use your existing Stack class to store the stack’s contents.

About this blog page

This blog is a collection of programming problems which are useful for Programming Interviews as well as Competitive programming. I try to cover my Interview experience with the help of this blog . I think ,this blog will be  gateway to crack the coding interview. I try to solve one problem daily so that my blog  gets the latest feeds . This blog might going to have some typographical errors but  with your feedback and with  time. I try to improve it.
I try to cover some usually asked coding Question and I try to give  my perceptive solution to the problem.I prefer java Language  and later I try to solve some google code jam Questions.
Competitive programming is way to enhance your programming skills. Below are the list of sites in which you can register yourself and try to solve the problems on your own.

1. Hackerrank
2. Code chef
3. Hackerearth
4. SPOJ
5. Codeforces
6. UVa online judge
7. Top coder