//Question: WAP that sum up all one child parent nodes without globle variable // 3 // / \ // 4 5 // / \ \ // 6 8 9 // / // 7 //output 8+5=13
"Success = (DSA + System Design) × Consistency × Problem-Solving + Mindfulness" 💡💻🚀
March 21, 2015
JOSH:Question: WAP that sum up all one child parent nodes without globle variable
March 20, 2015
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
* 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 .
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]
March 19, 2015
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."
March 18, 2015
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}
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
March 17, 2015
AMCAT:Pattern Based Question2
Pattern for n=6
11111112
32222222
33333334
54444444
55555556
76666666
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.
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.
March 15, 2015
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.
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.
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)
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)
Subscribe to:
Posts (Atom)