tag:blogger.com,1999:blog-71731347788313756742024-02-20T23:43:20.766+05:30Tech WorldCodes, I metArvind Mohanhttp://www.blogger.com/profile/09421036756092622107noreply@blogger.comBlogger94125tag:blogger.com,1999:blog-7173134778831375674.post-69955363652926165092012-10-13T17:22:00.002+05:302012-10-13T17:24:04.214+05:30Blog # 95 : Microsoft Interview Questions 2013 Batch<div dir="ltr" style="text-align: left;" trbidi="on">
<br />
<br />
<div class="MsoNormal">
<b><span style="font-family: Trebuchet MS, sans-serif;">Name of Company:
Microsoft<o:p></o:p></span></b></div>
<div class="MsoNormal">
<b><span style="font-family: Trebuchet MS, sans-serif;">Year: 2012<o:p></o:p></span></b></div>
<div class="MsoNormal">
<b><span style="font-family: Trebuchet MS, sans-serif;">Profile: Software<o:p></o:p></span></b></div>
<div class="MsoNormal">
<b><span style="font-family: Trebuchet MS, sans-serif;">Website link of
company: http://www.microsoft.com/<o:p></o:p></span></b></div>
<div class="MsoNormal">
<b><span style="font-family: Trebuchet MS, sans-serif;">Venue: On Campus<o:p></o:p></span></b></div>
<div class="MsoNormal">
<b><span style="font-family: Trebuchet MS, sans-serif;">CTC: 15-16.5 LPA<o:p></o:p></span></b></div>
<div class="MsoNormal">
<b><span style="font-family: Trebuchet MS, sans-serif;">Total number of
students appeared for written: 200+<o:p></o:p></span></b></div>
<div class="MsoNormal">
<b><span style="font-family: Trebuchet MS, sans-serif;">Number of students
shortlisted for interview: 30<o:p></o:p></span></b></div>
<div class="MsoNormal">
<b><span style="font-family: Trebuchet MS, sans-serif;">Number of offers: 7<o:p></o:p></span></b></div>
<div class="MsoNormal">
<b><span style="font-family: Trebuchet MS, sans-serif;">Written:<o:p></o:p></span></b></div>
<div class="MsoNormal">
<b><span style="font-family: Trebuchet MS, sans-serif;">Round 1: 50 questions
in 60 minutes<o:p></o:p></span></b></div>
<div class="MsoNormal" style="text-indent: 36.0pt;">
<span style="font-family: Trebuchet MS, sans-serif;">Section 1: Quantitative and
aptitude questions (Level: easy 30
questions)<o:p></o:p></span></div>
<div class="MsoNormal" style="text-indent: 36.0pt;">
<span style="font-family: Trebuchet MS, sans-serif;">Section 2: C/C++ basic coding
questions (Level: Easy 20 questions)<o:p></o:p></span></div>
<div class="MsoNormal">
<b><span style="font-family: Trebuchet MS, sans-serif;">Round 2: 3 Coding
question in 60 minutes {No compiler, On a notepad}<o:p></o:p></span></b></div>
<div class="MsoNormal">
<span style="font-family: Trebuchet MS, sans-serif;"> Q1: Write
a program to swap odd and even bits in an integer with as few instructions as
possible (e.g., bit 0 and bit 1 are swapped, bit 2 and bit 3 are swapped, etc).<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Trebuchet MS, sans-serif;"> Q2: Write a program to convert binary search tree
to double linked list<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Trebuchet MS, sans-serif;"> Q3:
Write a program to sort a linked list consisting of only 3 distinct elements.<o:p></o:p></span></div>
<div class="MsoNormal">
<b><span style="font-family: Trebuchet MS, sans-serif;">Interview Question
(All the design questions except first: Program manager post)<o:p></o:p></span></b></div>
<div class="MsoNormal">
<b><span style="font-family: Trebuchet MS, sans-serif;">Round 1:<o:p></o:p></span></b></div>
<div class="MsoNormal">
<span style="font-family: Trebuchet MS, sans-serif;">Q1: How to sort a array consisting of only 3 distinct
elements efficiently? (Don’t use counting method)<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Trebuchet MS, sans-serif;">Q2: You are given a sheet of paper of dimensions w*h. You
have to fit photographs (Dimensions: m*n) in that sheet such that each
photograph is separated from other photograph or boundary of paper by “d”
distance from all the sides. You have to output the maximum number of
photograph you can fit in the sheet. The arrangement should be symmetrical from
centre.<o:p></o:p></span></div>
<div class="MsoNormal">
<b><span style="font-family: Trebuchet MS, sans-serif;">Round 2:<o:p></o:p></span></b></div>
<div class="MsoNormal">
<span style="font-family: Trebuchet MS, sans-serif;">Q1: Tell something about yourself<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Trebuchet MS, sans-serif;">Q2: How you will design alarm clock for a blind person?<o:p></o:p></span></div>
<div class="MsoNormal">
<b><span style="font-family: Trebuchet MS, sans-serif;">Round 3:<o:p></o:p></span></b></div>
<div class="MsoNormal">
<span style="font-family: Trebuchet MS, sans-serif;">Q1: Description of various projects<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Trebuchet MS, sans-serif;">Q2: You have to stream songs of radio station of a
particular area through your applications so that you can hear it anywhere:
Design and implementation details.
Questions like:<o:p></o:p></span></div>
<div class="MsoListParagraphCxSpFirst" style="margin-left: 54.0pt; mso-add-space: auto;">
<span style="font-family: Trebuchet MS, sans-serif;">- How will user fast-forward the song?(He can’t because it is radio ;))<o:p></o:p></span></div>
<div class="MsoListParagraphCxSpMiddle" style="margin-left: 54.0pt; mso-add-space: auto;">
<span style="font-family: Trebuchet MS, sans-serif;">- How you will provide music storage service to user? What will happen
when he will click fast-forward and reverse button?<o:p></o:p></span></div>
<div class="MsoListParagraphCxSpLast" style="margin-left: 54.0pt; mso-add-space: auto;">
<span style="font-family: Trebuchet MS, sans-serif;">-
How to make sure that speed is maintained?<o:p></o:p></span></div>
<div class="MsoNormal">
<b><span style="font-family: Trebuchet MS, sans-serif;">Round 4:<o:p></o:p></span></b></div>
<div class="MsoNormal" style="margin-left: 36.0pt;">
<span style="font-family: Trebuchet MS, sans-serif;">Q1: Design a banking application
for SBI which users (especially students) can use in their smart-phones for
daily transactions, take the history of transactions, pay their fees etc.<o:p></o:p></span></div>
<div class="MsoListParagraphCxSpFirst" style="margin-left: 108.0pt; mso-add-space: auto; mso-list: l1 level1 lfo1; text-indent: -18.0pt;">
<!--[if !supportLists]--><span style="font-family: Trebuchet MS, sans-serif;">-
<!--[endif]-->What main features must be included in the app?<o:p></o:p></span></div>
<div class="MsoListParagraphCxSpMiddle" style="margin-left: 108.0pt; mso-add-space: auto; mso-list: l1 level1 lfo1; text-indent: -18.0pt;">
<!--[if !supportLists]--><span style="font-family: Trebuchet MS, sans-serif;">-
<!--[endif]-->How will user interface look like?<o:p></o:p></span></div>
<div class="MsoListParagraphCxSpLast" style="margin-left: 108.0pt; mso-add-space: auto; mso-list: l1 level1 lfo1; text-indent: -18.0pt;">
<!--[if !supportLists]--><span style="font-family: Trebuchet MS, sans-serif;">-
<!--[endif]-->How will transactions take place?<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Trebuchet MS, sans-serif;">TIPS:<o:p></o:p></span></div>
<div class="MsoListParagraphCxSpFirst" style="mso-list: l0 level1 lfo2; text-indent: -18.0pt;">
<!--[if !supportLists]--><span style="font-family: Trebuchet MS, sans-serif;">1)
<!--[endif]-->For Round 1 of written all that matter is speed
and accuracy.<o:p></o:p></span></div>
<div class="MsoListParagraphCxSpMiddle" style="mso-list: l0 level1 lfo2; text-indent: -18.0pt;">
<!--[if !supportLists]--><span style="font-family: Trebuchet MS, sans-serif;">2)
<!--[endif]-->For Round 2 of written: Coding Questions are
pretty easy just try practicing your coding skills on paper/ notepad instead of
using a compiler. You will be surprised as you will find it is more difficult
than expected.<o:p></o:p></span></div>
<div class="MsoListParagraphCxSpMiddle" style="mso-list: l0 level1 lfo2; text-indent: -18.0pt;">
<!--[if !supportLists]--><span style="font-family: Trebuchet MS, sans-serif;">3)
<!--[endif]-->When interviewer asks you a question you already
know, Take your time and make sure you solve the question all over again. Start
with the basic algorithm and then keep improving till the interviewer is
satisfied.<o:p></o:p></span></div>
<div class="MsoListParagraphCxSpMiddle" style="mso-list: l0 level1 lfo2; text-indent: -18.0pt;">
<!--[if !supportLists]--><span style="font-family: Trebuchet MS, sans-serif;">4)
<!--[endif]-->In Microsoft recruitment there is no separate
round as HR. You can be asked any HR question in any of the interview round.
When you are asked to describe about yourself, Make sure you don’t hurry. While
telling about yourself, try to sense the interest of interviewer. If
interviewer looks interested in a particular project of yours and you are confident
about it, make sure you elaborate the topic giving him chance to ask questions.<o:p></o:p></span></div>
<div class="MsoListParagraphCxSpMiddle" style="mso-list: l0 level1 lfo2; text-indent: -18.0pt;">
<!--[if !supportLists]--><span style="font-family: Trebuchet MS, sans-serif;">5)
<!--[endif]-->There are no books which can help you master the
design questions. All you need is innovation and confidence. Take care of
following points :<o:p></o:p></span></div>
<div class="MsoListParagraphCxSpMiddle" style="margin-left: 108.0pt; mso-add-space: auto; mso-list: l1 level1 lfo1; text-indent: -18.0pt;">
<!--[if !supportLists]--><span style="font-family: Trebuchet MS, sans-serif;">-
<!--[endif]-->When asked to design something, Take paper and
write down all that comes in your mind so that you don’t miss any point. Take
your time and don’t panic at this point.<o:p></o:p></span></div>
<div class="MsoListParagraphCxSpMiddle" style="margin-left: 108.0pt; mso-add-space: auto; mso-list: l1 level1 lfo1; text-indent: -18.0pt;">
<!--[if !supportLists]--><span style="font-family: Trebuchet MS, sans-serif;">-
<!--[endif]-->Read your thoughts aloud to the interviewer. In
design questions nothing is wrong or right so make sure you say everything in
your mind to the interviewer, you never know which point may impress him.<o:p></o:p></span></div>
<div class="MsoListParagraphCxSpMiddle" style="margin-left: 108.0pt; mso-add-space: auto; mso-list: l1 level1 lfo1; text-indent: -18.0pt;">
<!--[if !supportLists]--><span style="font-family: Trebuchet MS, sans-serif;">-
<!--[endif]-->Try to sense the interest of interviewer. In my
interview round I was asked to design alarm clock, I put out all the technical
details but he asked me how I know it is the right thing to do. I understood he
wants me to talk about customer involvement.<o:p></o:p></span></div>
<div class="MsoListParagraphCxSpMiddle" style="mso-list: l0 level1 lfo2; text-indent: -18.0pt;">
<!--[if !supportLists]--><span style="font-family: Trebuchet MS, sans-serif;">6)
<!--[endif]-->At end of each interview round, Interviewer asks
you if you have any questions. Make sure after you ask interviewer about 2
things :<o:p></o:p></span></div>
<div class="MsoListParagraphCxSpMiddle" style="margin-left: 108.0pt; mso-add-space: auto; mso-list: l1 level1 lfo1; text-indent: -18.0pt;">
<!--[if !supportLists]--><span style="font-family: Trebuchet MS, sans-serif;">-
<!--[endif]--><b>Something
about their company.</b> While asking the question try to reflect that you feel
you will be selected. When you ask
question make sure you listen what he reply. Depending on interviewer you can
also ask him his experience in that company.
While asking questions don’t show that you are asking because you have a
doubt if you will join the company or not instead show you will be selected so
you are eager to know more about company.<o:p></o:p></span></div>
<div class="MsoListParagraphCxSpLast" style="margin-left: 108.0pt; mso-add-space: auto; mso-list: l1 level1 lfo1; text-indent: -18.0pt;">
<!--[if !supportLists]--><span style="font-family: Trebuchet MS, sans-serif;">-
<!--[endif]--><b>Feedback
about yourself.</b> This will enable you to know about your weaknesses and
improve it further because each interview is preparation for the next. It also
shows the interviewer that you ready to take feedback and improve. It will push
your chances to get selected.<o:p></o:p></span></div>
<div class="MsoNormal" style="margin-left: 36.0pt;">
<br /></div>
<div class="MsoNormal">
<span style="font-family: Trebuchet MS, sans-serif;"> </span><o:p></o:p></div>
</div>
Arvind Mohanhttp://www.blogger.com/profile/09421036756092622107noreply@blogger.com0tag:blogger.com,1999:blog-7173134778831375674.post-62581857037242652822012-09-01T11:07:00.000+05:302012-10-13T17:21:48.644+05:30Blog # 94 : Amazon Interview Questions 2013 Batch (2)<div dir="ltr" style="text-align: left;" trbidi="on">
<u style="background-color: white; color: #333333; font-family: 'trebuchet ms', sans-serif; font-size: 13px;">Round 1</u><br />
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">1. BST to DLL conversion.</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">2. Given a linked list you have to delete all nodes for which there is a node with higher value on right side.</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">for eg. 41 1 6 4 8 34 3 5 9</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">output 41 34 9</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">n^2 solution is obvious. Do this in O(n)</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;"><br />
</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;"><u>Round 2</u></span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">I forgot questions from this round. 1 question I remember is</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">1. You are given with an iPod. There is a sequence of n songs and a function rand(int i) which upon calling returns an integer from 0 to n-1 (or 1 to n, depends on you). You have to write a function so that it will play random songs every time. After finishing one song you have to play another song randomly. The constraint is you cant repeat a song until every song has been played.</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;"><br />
</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;"><u>Round 3</u></span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">1. Normal HR questions</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">2. There are 2 persons jumping from the parachute on a infinite 1 dimensional plane. Upon landing they go to a random direction. We have to write a code using a given API which will run on different system, independent to each other so that they cant communication by any mean. The given API contains</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">moveLeft - moves the person 1 unit left/1 unit time</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">moveRight - moves the person 1 unit right/1 unit time</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">noOpt - moves the person 0 unit/1 unit time</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">isOnTop - returns true if the person is on top of any parachute. False otherwise.</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">didWeMeet - returns true if they meet. False otherwise.</span></span></div>
</div>
Arvind Mohanhttp://www.blogger.com/profile/09421036756092622107noreply@blogger.com0tag:blogger.com,1999:blog-7173134778831375674.post-45917779517760254882012-08-31T15:08:00.000+05:302012-10-13T17:21:31.647+05:30Blog # 93 : Amazon Interview Questions 2013 Batch (1)<div dir="ltr" style="text-align: left;" trbidi="on">
<br />
<pre style="white-space: pre-wrap; word-wrap: break-word;"><span style="font-family: Helvetica Neue, Arial, Helvetica, sans-serif;">
</span><pre style="white-space: pre-wrap; word-wrap: break-word;"><span style="font-family: Helvetica Neue, Arial, Helvetica, sans-serif;">Written Round (1 hour 30 minutes):
20 MCQs (mostly from latest GATE paper)
2 Programming questions:
1) An operation "swap" means removing an element from the array and appending it at the back of the same array. Find the minimum number of "swaps" needed to sort that array.
Eg 3124
output: 2 (3124->1243->1234)
2) find if there exists a path from root to leaf in binary tree with sum K.
Interview:
Round 1 (1 hour 15 minutes):
write programs on paper keeping in mind all the boundary cases and complexity of the code. Following were the programs:
1) Find if the given linked list is a palindrome or not (including inplace reversal of linked list)
2) We have a right rotated sorted array.Eg
4 5 1 2 3
You need to find where this rotation had occured.
3) There exists a linked list such that each node has two pointers next and random. Random pointers points to any other node in the same linked list or to
itself or NULL. Clone this linked list.
Round 2 (1 hour 15 minutes):
First part was mainly concerned with questions related to OOPs, second part included OS and lastly algorithms and miscellaneous.
OOPs
1) interviewer turned the laptop towards me and then asked me to write an "interface" for this laptop. Then he asked me to implement this interface.
2) Event handler. Asked how will you tell whether a key on the laptop has been pressed or not. Write a function (whose signature I had written in interface).
3) Difference between interface, abstract class, instance.
OS
He asked me back to back questions which covered topics:
1) Processes and threads (Asked example, desing a software which will be having three components-file copy, data transfer, user input efficiently)
2) Multi-threading
3) Scheduling Algorithms (both Process and thread)
4) Synchronization (many questions from mutex and semaphore)
5) Deadlock (deadlock prevention, avoidance, etc)
6) context switching
Algo and misc
1) Scenario: In gmail if somebody wants to sort mails according to name, date, size, etc which sorting algorithm is most accurate one for this puropse.
2) quicksort and heapsort.
3) what are shared library.
4) Other type of libraries.
Round 3 (1 hour):
Write the programs for following:
1) COunt the total number of parenthesis pattern for a given number n.
Eg
n=1
()
count=1
n=2
()() (())
count=2
n=3
()()() ()(()) (())() ((())) (()())
count=3
2) If the given graph is bipartite or not.
3) (not code only ds) Scenario: There is a huge database of telephone numbers. Each telephone number is unique and information (name, address, etc) of the user is attached to this telephone number. Design a data structure to store this.
Round 4 (1 hour):
HR plus techincal
1) Tell me about yourself.
2) What is your educational background.
3) Why Amazon
tech:
1) delete nth element from the end in a linked list.
2) find the maximum sum subarray in an array A of size n which may also contain negative numbers.
Selected!</span></pre>
</pre>
</div>
Arvind Mohanhttp://www.blogger.com/profile/09421036756092622107noreply@blogger.com0tag:blogger.com,1999:blog-7173134778831375674.post-79297761648646756962012-08-31T13:33:00.000+05:302012-10-13T17:21:16.353+05:30Blog # 92 : Pritam Das : Microsoft<div dir="ltr" style="text-align: left;" trbidi="on">
<br />
<div class="MsoNormal" style="line-height: 18px; margin: 0cm 6.6pt 0cm 5pt;">
<span style="font-family: Trebuchet MS, sans-serif;">Whe<span style="letter-spacing: -0.05pt;">n</span><span style="letter-spacing: -0.1pt;">e</span><span style="letter-spacing: 0.05pt;">v</span>er<span style="letter-spacing: 0.05pt;"> </span>u<span style="letter-spacing: -0.15pt;"> </span>wri<span style="letter-spacing: -0.1pt;">t</span>e<span style="letter-spacing: 0.05pt;"> </span>a p<span style="letter-spacing: -0.15pt;">r</span><span style="letter-spacing: 0.05pt;">o</span><span style="letter-spacing: -0.05pt;">g</span>ram<span style="letter-spacing: -0.05pt;"> </span>be<span style="letter-spacing: 0.05pt;"> </span>su<span style="letter-spacing: -0.15pt;">r</span>e<span style="letter-spacing: 0.15pt;"> </span><span style="letter-spacing: -0.1pt;">t</span>o<span style="letter-spacing: 0.1pt;"> </span><span style="letter-spacing: -0.1pt;">c</span><span style="letter-spacing: -0.05pt;">o</span><span style="letter-spacing: 0.05pt;">v</span>er<span style="letter-spacing: 0.05pt;"> </span>all<span style="letter-spacing: -0.15pt;"> </span><span style="letter-spacing: -0.1pt;">t</span><span style="letter-spacing: -0.05pt;">h</span>e<span style="letter-spacing: 0.05pt;"> </span>c<span style="letter-spacing: 0.05pt;">o</span>r<span style="letter-spacing: -0.15pt;">n</span>er<span style="letter-spacing: 0.05pt;"> </span>ca<span style="letter-spacing: -0.1pt;">s</span>es<span style="letter-spacing: 0.1pt;"> </span>a<span style="letter-spacing: -0.05pt;">n</span>d<span style="letter-spacing: -0.15pt;"> </span>write<span style="letter-spacing: -0.05pt;"> </span><span style="letter-spacing: -0.1pt;">i</span>t<span style="letter-spacing: 0.05pt;"> </span>in a p<span style="letter-spacing: -0.15pt;">r</span><span style="letter-spacing: 0.05pt;">o</span><span style="letter-spacing: -0.05pt;">p</span>er i<span style="letter-spacing: -0.05pt;">nd</span>ented <span style="letter-spacing: 0.05pt;">w</span><span style="letter-spacing: -0.15pt;">a</span><span style="letter-spacing: 0.05pt;">y</span>. As<span style="letter-spacing: 0.05pt;"> </span>i<span style="letter-spacing: -0.05pt;">n</span><span style="letter-spacing: -0.1pt;">t</span>er<span style="letter-spacing: 0.05pt;">v</span><span style="letter-spacing: -0.15pt;">i</span>e<span style="letter-spacing: -0.05pt;">w</span>ers<span style="letter-spacing: 0.05pt;"> </span>ask<span style="letter-spacing: -0.1pt;"> t</span>o<span style="letter-spacing: 0.05pt;"> w</span>r<span style="letter-spacing: -0.15pt;">i</span>te<span style="letter-spacing: -0.05pt;"> </span>t<span style="letter-spacing: 0.05pt;">e</span>stcases<span style="letter-spacing: -0.1pt;"> f</span><span style="letter-spacing: 0.05pt;">o</span>r t<span style="letter-spacing: -0.05pt;">h</span>e<span style="letter-spacing: -0.1pt;"> </span>pro<span style="letter-spacing: -0.05pt;">g</span>r<span style="letter-spacing: -0.15pt;">a</span>m<span style="letter-spacing: 0.05pt;"> </span>u h<span style="letter-spacing: -0.15pt;">a</span><span style="letter-spacing: 0.05pt;">v</span>e<span style="letter-spacing: -0.1pt;"> </span><span style="letter-spacing: 0.05pt;">w</span>ri<span style="letter-spacing: -0.1pt;">t</span>t<span style="letter-spacing: 0.05pt;">e</span>n<span style="letter-spacing: -0.05pt;"> </span>and<span style="letter-spacing: -0.05pt;"> </span><span style="letter-spacing: 0.05pt;">t</span><span style="letter-spacing: -0.05pt;">h</span>en<span style="letter-spacing: -0.1pt;"> </span>check if <span style="letter-spacing: -0.05pt;">u</span>r p<span style="letter-spacing: -0.05pt;">r</span><span style="letter-spacing: 0.05pt;">o</span><span style="letter-spacing: -0.05pt;">g</span>r<span style="letter-spacing: -0.15pt;">a</span>m<span style="letter-spacing: 0.05pt;"> </span><span style="letter-spacing: -0.1pt;">c</span><span style="letter-spacing: 0.05pt;">o</span><span style="letter-spacing: -0.05pt;">v</span>ers<span style="letter-spacing: 0.05pt;"> </span>all<span style="letter-spacing: -0.15pt;"> </span><span style="letter-spacing: 0.05pt;">t</span><span style="letter-spacing: -0.05pt;">h</span>e<span style="letter-spacing: -0.1pt;"> </span><span style="letter-spacing: 0.05pt;">t</span>est<span style="letter-spacing: -0.05pt;"> </span>ca<span style="letter-spacing: -0.1pt;">s</span>es.<o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 10pt; margin: 0.3pt 0cm 0cm;">
<br /></div>
<div class="MsoNormal" style="margin: 0cm -1pt 0.0001pt 5pt;">
<b><span style="font-family: Trebuchet MS, sans-serif;">A<span style="letter-spacing: 0.05pt;">l</span>l<span style="letter-spacing: -0.05pt;"> </span><span style="letter-spacing: 0.05pt;">t</span><span style="letter-spacing: -0.05pt;">h</span>e<span style="letter-spacing: -0.05pt;"> </span>b<span style="letter-spacing: -0.05pt;">e</span>st<span style="letter-spacing: 0.05pt;"> </span>f<span style="letter-spacing: -0.15pt;">e</span><span style="letter-spacing: 0.05pt;">ll</span><span style="letter-spacing: -0.05pt;">a</span>s<span style="letter-spacing: -0.1pt;"> </span>!!!</span></b></div>
</div>
Arvind Mohanhttp://www.blogger.com/profile/09421036756092622107noreply@blogger.com0tag:blogger.com,1999:blog-7173134778831375674.post-7643525319287572602012-08-31T13:31:00.000+05:302012-10-13T17:20:58.568+05:30Blog # 91 : Microsoft Interview Qusetions 2013 Batch<div dir="ltr" style="text-align: left;" trbidi="on">
<div class="WordSection1">
<div class="MsoNormal" style="line-height: 17.05pt; margin-bottom: .0001pt; margin-bottom: 0cm; margin-left: 5.0pt; margin-right: -1.0pt; margin-top: 0cm; mso-line-height-rule: exactly;">
<b style="font-family: 'Trebuchet MS', sans-serif;">W</b><b style="font-family: 'Trebuchet MS', sans-serif;">ri</b><b style="font-family: 'Trebuchet MS', sans-serif;">tten<span style="letter-spacing: -.15pt;"> </span>R<span style="letter-spacing: -.05pt;">oun</span>d<span style="letter-spacing: -.05pt;"> </span>1<span style="letter-spacing: .1pt;"> </span></b><span style="font-family: 'Trebuchet MS', sans-serif;">: </span><span style="font-family: 'Trebuchet MS', sans-serif; letter-spacing: 2.4pt;"> </span><span style="font-family: 'Trebuchet MS', sans-serif; letter-spacing: 0.05pt;">5</span><span style="font-family: 'Trebuchet MS', sans-serif;">0 </span><span style="font-family: 'Trebuchet MS', sans-serif; letter-spacing: 0.05pt;">m</span><span style="font-family: 'Trebuchet MS', sans-serif; letter-spacing: -0.05pt;">u</span><span style="font-family: 'Trebuchet MS', sans-serif; letter-spacing: -0.15pt;">l</span><span style="font-family: 'Trebuchet MS', sans-serif;">ti</span><span style="font-family: 'Trebuchet MS', sans-serif; letter-spacing: -0.05pt;">p</span><span style="font-family: 'Trebuchet MS', sans-serif;">le c</span><span style="font-family: 'Trebuchet MS', sans-serif; letter-spacing: -0.05pt;">h</span><span style="font-family: 'Trebuchet MS', sans-serif; letter-spacing: 0.05pt;">o</span><span style="font-family: 'Trebuchet MS', sans-serif; letter-spacing: -0.15pt;">i</span><span style="font-family: 'Trebuchet MS', sans-serif;">ce</span><span style="font-family: 'Trebuchet MS', sans-serif; letter-spacing: 0.15pt;"> </span><span style="font-family: 'Trebuchet MS', sans-serif; letter-spacing: -0.05pt;">qu</span><span style="font-family: 'Trebuchet MS', sans-serif; letter-spacing: -0.1pt;">e</span><span style="font-family: 'Trebuchet MS', sans-serif;">sti</span><span style="font-family: 'Trebuchet MS', sans-serif; letter-spacing: 0.05pt;">o</span><span style="font-family: 'Trebuchet MS', sans-serif; letter-spacing: -0.05pt;">n</span><span style="font-family: 'Trebuchet MS', sans-serif;">s</span><span style="font-family: 'Trebuchet MS', sans-serif; letter-spacing: -0.1pt;"> </span><span style="font-family: 'Trebuchet MS', sans-serif;">in </span><span style="font-family: 'Trebuchet MS', sans-serif; letter-spacing: -0.1pt;">6</span><span style="font-family: 'Trebuchet MS', sans-serif;">0</span><span style="font-family: 'Trebuchet MS', sans-serif; letter-spacing: -0.05pt;"> </span><span style="font-family: 'Trebuchet MS', sans-serif; letter-spacing: 0.1pt;">m</span><span style="font-family: 'Trebuchet MS', sans-serif;">i</span><span style="font-family: 'Trebuchet MS', sans-serif; letter-spacing: -0.05pt;">n</span><span style="font-family: 'Trebuchet MS', sans-serif;">s</span><span style="font-family: 'Trebuchet MS', sans-serif; letter-spacing: -0.1pt;"> </span><span style="font-family: 'Trebuchet MS', sans-serif;">ti</span><span style="font-family: 'Trebuchet MS', sans-serif; letter-spacing: -0.05pt;">m</span><span style="font-family: 'Trebuchet MS', sans-serif;">e.</span><span style="font-family: 'Trebuchet MS', sans-serif; letter-spacing: 0.05pt;"> </span><span style="font-family: 'Trebuchet MS', sans-serif; letter-spacing: -0.05pt;">H</span><span style="font-family: 'Trebuchet MS', sans-serif;">ad</span><span style="font-family: 'Trebuchet MS', sans-serif; letter-spacing: -0.05pt;"> </span><span style="font-family: 'Trebuchet MS', sans-serif;">2</span><span style="font-family: 'Trebuchet MS', sans-serif; letter-spacing: -0.05pt;"> </span><span style="font-family: 'Trebuchet MS', sans-serif;">s</span><span style="font-family: 'Trebuchet MS', sans-serif; letter-spacing: 0.05pt;">e</span><span style="font-family: 'Trebuchet MS', sans-serif; letter-spacing: -0.1pt;">c</span><span style="font-family: 'Trebuchet MS', sans-serif;">ti</span><span style="font-family: 'Trebuchet MS', sans-serif; letter-spacing: 0.05pt;">o</span><span style="font-family: 'Trebuchet MS', sans-serif; letter-spacing: -0.05pt;">n</span><span style="font-family: 'Trebuchet MS', sans-serif;">s</span><span style="font-family: 'Trebuchet MS', sans-serif; letter-spacing: -0.2pt;"> </span><span style="font-family: 'Trebuchet MS', sans-serif;">–</span><span style="font-family: 'Trebuchet MS', sans-serif; letter-spacing: 0.05pt;"> </span><span style="font-family: 'Trebuchet MS', sans-serif;">A</span><span style="font-family: 'Trebuchet MS', sans-serif; letter-spacing: -0.05pt;">p</span><span style="font-family: 'Trebuchet MS', sans-serif;">titu</span><span style="font-family: 'Trebuchet MS', sans-serif; letter-spacing: -0.05pt;">d</span><span style="font-family: 'Trebuchet MS', sans-serif;">e</span><span style="font-family: 'Trebuchet MS', sans-serif; letter-spacing: 0.1pt;"> </span><span style="font-family: 'Trebuchet MS', sans-serif;">a</span><span style="font-family: 'Trebuchet MS', sans-serif; letter-spacing: -0.05pt;">n</span><span style="font-family: 'Trebuchet MS', sans-serif;">d</span></div>
<div class="MsoNormal" style="margin: 2.15pt -1pt 0.0001pt 5pt;">
<span style="font-family: Trebuchet MS, sans-serif;"><span style="letter-spacing: .05pt; mso-ascii-font-family: Calibri; mso-bidi-font-family: Calibri; mso-fareast-font-family: Calibri; mso-hansi-font-family: Calibri;">P</span>r<span style="letter-spacing: .05pt;">o</span><span style="letter-spacing: -.05pt;">g</span>r<span style="letter-spacing: -.15pt;">a</span><span style="letter-spacing: -.05pt;">m</span><span style="letter-spacing: .05pt;">m</span>i<span style="letter-spacing: -.05pt;">n</span>g<span style="letter-spacing: -.05pt;"> </span><span style="letter-spacing: .05pt;">A</span><span style="letter-spacing: -.05pt;">b</span>ilit<span style="letter-spacing: .05pt;">y</span>.<o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 12.0pt; margin-bottom: .0001pt; margin-bottom: 0cm; mso-line-height-rule: exactly;">
<br /></div>
<div class="MsoNormal" style="margin: 0cm -1pt 0.0001pt 5pt;">
<span style="font-family: Trebuchet MS, sans-serif;"><b>W</b><b>ri</b><b>tten<span style="letter-spacing: -.15pt;"> </span>R<span style="letter-spacing: -.05pt;">oun</span>d<span style="letter-spacing: -.05pt;"> </span>2<span style="letter-spacing: .1pt;"> </span></b>:<span style="letter-spacing: -.05pt;"> </span>3<span style="letter-spacing: -.05pt;"> </span>c<span style="letter-spacing: .05pt;">o</span><span style="letter-spacing: -.05pt;">d</span>i<span style="letter-spacing: -.05pt;">n</span>g<span style="letter-spacing: -.15pt;"> </span>q<span style="letter-spacing: -.05pt;">u</span>es<span style="letter-spacing: .05pt;">t</span>i<span style="letter-spacing: .05pt;">o</span><span style="letter-spacing: -.05pt;">n</span>s<span style="letter-spacing: -.1pt;"> </span>in 1<span style="letter-spacing: -.05pt;"> </span>h<span style="letter-spacing: .05pt;">o</span><span style="letter-spacing: -.05pt;">u</span>r.<o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 11.0pt; margin-bottom: .0001pt; margin-bottom: 0cm; margin-left: 0cm; margin-right: 0cm; margin-top: .9pt; mso-line-height-rule: exactly;">
<br /></div>
<div class="MsoNormal" style="margin: 0cm -1pt 0.0001pt 23pt;">
<span style="font-family: Trebuchet MS, sans-serif;"><span style="letter-spacing: .05pt; mso-ascii-font-family: Calibri; mso-bidi-font-family: Calibri; mso-fareast-font-family: Calibri; mso-hansi-font-family: Calibri;">1</span>. <span style="letter-spacing: 2.1pt;"> </span>Swap<span style="letter-spacing: -.05pt;"> e</span><span style="letter-spacing: .05pt;">v</span>ery <span style="letter-spacing: -.1pt;">c</span><span style="letter-spacing: .05pt;">o</span><span style="letter-spacing: -.05pt;">n</span>se<span style="letter-spacing: .05pt;">c</span><span style="letter-spacing: -.05pt;">u</span>t<span style="letter-spacing: -.1pt;">i</span><span style="letter-spacing: .05pt;">v</span>e <span style="letter-spacing: .05pt;">o</span><span style="letter-spacing: -.15pt;">d</span>d<span style="letter-spacing: -.05pt;"> </span>and<span style="letter-spacing: -.05pt;"> </span><span style="letter-spacing: .05pt;">e</span><span style="letter-spacing: -.05pt;">v</span>en pos<span style="letter-spacing: -.15pt;">i</span>ti<span style="letter-spacing: .05pt;">o</span><span style="letter-spacing: -.05pt;">n</span>ed<span style="letter-spacing: .05pt;"> </span><span style="letter-spacing: -.05pt;">b</span><span style="letter-spacing: -.15pt;">i</span>t<span style="letter-spacing: .1pt;"> </span><span style="letter-spacing: -.15pt;">i</span>n<span style="letter-spacing: -.05pt;"> </span>a<span style="letter-spacing: .05pt;"> </span><span style="letter-spacing: -.05pt;">nu</span><span style="letter-spacing: .05pt;">m</span>ber.<o:p></o:p></span></div>
<div class="MsoNormal" style="margin: 1.9pt -1pt 0.0001pt 41pt;">
<span style="font-family: Trebuchet MS, sans-serif;">Ex<span style="letter-spacing: .05pt;">:</span>-<span style="letter-spacing: -.1pt;"> </span><span style="letter-spacing: .05pt;">1</span><span style="letter-spacing: -.1pt;">0</span><span style="letter-spacing: .05pt;">1</span><span style="letter-spacing: -.1pt;">0</span><span style="letter-spacing: .05pt;">1</span><span style="letter-spacing: -.1pt;">01</span><span style="letter-spacing: .05pt;">1</span><span style="letter-spacing: -.1pt;">0</span><span style="letter-spacing: .05pt;">1</span><span style="letter-spacing: -.1pt;">0</span><span style="letter-spacing: .05pt;">1</span><span style="letter-spacing: -.05pt;">0</span>1<span style="letter-spacing: 2.5pt;"> </span>= <span style="letter-spacing: 2.5pt;"> </span><span style="letter-spacing: -.1pt;">0</span><span style="letter-spacing: .05pt;">1</span><span style="letter-spacing: -.1pt;">0</span><span style="letter-spacing: .05pt;">1</span><span style="letter-spacing: -.1pt;">0</span><span style="letter-spacing: .05pt;">1</span><span style="letter-spacing: -.1pt;">1</span><span style="letter-spacing: .05pt;">1</span><span style="letter-spacing: -.1pt;">1</span><span style="letter-spacing: .05pt;">0</span><span style="letter-spacing: -.1pt;">1</span><span style="letter-spacing: .1pt;">0</span><span style="letter-spacing: -.1pt;">10</span><o:p></o:p></span></div>
<div class="MsoNormal" style="margin-bottom: .0001pt; margin-bottom: 0cm; margin-left: 41.0pt; margin-right: 2.8pt; margin-top: 2.05pt; text-indent: -18.0pt;">
<span style="font-family: Trebuchet MS, sans-serif;"><span style="letter-spacing: .05pt; mso-ascii-font-family: Calibri; mso-bidi-font-family: Calibri; mso-fareast-font-family: Calibri; mso-hansi-font-family: Calibri;">2</span>. <span style="letter-spacing: 2.1pt;"> </span>Giv<span style="letter-spacing: .05pt;">e</span>n<span style="letter-spacing: -.05pt;"> </span>a<span style="letter-spacing: -.1pt;"> </span>bi<span style="letter-spacing: -.05pt;">n</span>ary<span style="letter-spacing: .05pt;"> </span><span style="letter-spacing: -.1pt;">s</span>earch t<span style="letter-spacing: -.1pt;">r</span>ee<span style="letter-spacing: -.05pt;"> </span>.<span style="letter-spacing: .1pt;"> </span>C<span style="letter-spacing: .05pt;">o</span><span style="letter-spacing: -.05pt;">nv</span>ert<span style="letter-spacing: .1pt;"> </span><span style="letter-spacing: -.15pt;">i</span>t<span style="letter-spacing: .05pt;"> </span>i<span style="letter-spacing: -.05pt;">n</span><span style="letter-spacing: -.1pt;">t</span>o<span style="letter-spacing: .05pt;"> </span>a<span style="letter-spacing: .05pt;"> </span><span style="letter-spacing: -.15pt;">d</span><span style="letter-spacing: .05pt;">o</span><span style="letter-spacing: -.05pt;">ub</span>ly<span style="letter-spacing: .05pt;"> </span>li<span style="letter-spacing: -.15pt;">n</span>k<span style="letter-spacing: .05pt;">e</span>d<span style="letter-spacing: -.05pt;"> </span>list<span style="letter-spacing: .05pt;"> </span>in<span style="letter-spacing: -.15pt;"> </span>pl<span style="letter-spacing: -.05pt;">a</span>ce<span style="letter-spacing: -.05pt;"> </span><span style="letter-spacing: .1pt;">(</span><span style="letter-spacing: -.05pt;">n</span>o<span style="letter-spacing: -.05pt;"> </span>e<span style="letter-spacing: .05pt;">x</span>tra<span style="letter-spacing: -.1pt;"> s</span><span style="letter-spacing: -.05pt;">p</span>ac<span style="letter-spacing: .05pt;">e</span>)<span style="letter-spacing: .05pt;"> </span>such that<span style="letter-spacing: .05pt;"> </span><b><span style="letter-spacing: -.05pt;">p</span><span style="letter-spacing: .05pt;">r</span><span style="letter-spacing: -.05pt;">e</span>v<span style="letter-spacing: -.05pt;"> </span></b><span style="letter-spacing: -.05pt;">p</span><span style="letter-spacing: .05pt;">o</span>i<span style="letter-spacing: -.05pt;">n</span>ts<span style="letter-spacing: -.1pt;"> t</span>o<span style="letter-spacing: .05pt;"> </span>le<span style="letter-spacing: -.1pt;">f</span>t<span style="letter-spacing: .05pt;"> </span>ch<span style="letter-spacing: -.05pt;">i</span><span style="letter-spacing: -.15pt;">l</span>d<span style="letter-spacing: -.05pt;"> </span>and<span style="letter-spacing: .05pt;"> </span><b><span style="letter-spacing: -.05pt;">ne</span>xt </b><span style="letter-spacing: -.05pt;">p</span><span style="letter-spacing: .05pt;">o</span>i<span style="letter-spacing: -.05pt;">n</span>ts<span style="letter-spacing: .05pt;"> </span><span style="letter-spacing: -.1pt;">t</span>o<span style="letter-spacing: .05pt;"> </span>ri<span style="letter-spacing: -.05pt;">gh</span>t<span style="letter-spacing: -.1pt;"> c</span><span style="letter-spacing: -.05pt;">h</span>il<span style="letter-spacing: -.05pt;">d</span>.<o:p></o:p></span></div>
<div class="MsoNormal" style="margin: 0.25pt -1pt 0.0001pt 23pt;">
<span style="font-family: Trebuchet MS, sans-serif;"><span style="letter-spacing: .05pt; mso-ascii-font-family: Calibri; mso-bidi-font-family: Calibri; mso-fareast-font-family: Calibri; mso-hansi-font-family: Calibri;">3</span>. <span style="letter-spacing: 2.1pt;"> </span>Giv<span style="letter-spacing: .05pt;">e</span>n<span style="letter-spacing: -.05pt;"> </span>a<span style="letter-spacing: -.1pt;"> </span>li<span style="letter-spacing: -.05pt;">n</span>k<span style="letter-spacing: .05pt;">e</span>d<span style="letter-spacing: -.05pt;"> </span>li<span style="letter-spacing: -.15pt;">s</span>t<span style="letter-spacing: .05pt;"> </span>that<span style="letter-spacing: -.1pt;"> </span>c<span style="letter-spacing: .05pt;">o</span><span style="letter-spacing: -.15pt;">n</span><span style="letter-spacing: -.1pt;">t</span>ai<span style="letter-spacing: -.05pt;">n</span>s <span style="letter-spacing: .15pt;">0</span><span style="letter-spacing: -.1pt;">,</span>1<span style="letter-spacing: .05pt;"> </span>and 2<span style="letter-spacing: -.05pt;"> </span>. So<span style="letter-spacing: -.15pt;">r</span>t<span style="letter-spacing: .05pt;"> </span>th<span style="letter-spacing: -.05pt;">i</span>s li<span style="letter-spacing: -.15pt;">n</span>k<span style="letter-spacing: .05pt;">e</span>d<span style="letter-spacing: -.05pt;"> </span>such<span style="letter-spacing: -.05pt;"> </span><span style="letter-spacing: .05pt;">t</span><span style="letter-spacing: -.05pt;">h</span><span style="letter-spacing: -.15pt;">a</span>t<span style="letter-spacing: .05pt;"> </span>it<span style="letter-spacing: -.05pt;"> </span>c<span style="letter-spacing: .05pt;">o</span><span style="letter-spacing: -.05pt;">n</span><span style="letter-spacing: -.1pt;">t</span>ai<span style="letter-spacing: -.05pt;">n</span>s <span style="letter-spacing: .05pt;">0</span>s<span style="letter-spacing: -.1pt;"> </span>first,then<o:p></o:p></span></div>
<div class="MsoNormal" style="margin: 2.05pt -1pt 0.0001pt 41pt;">
<span style="font-family: Trebuchet MS, sans-serif;"><span style="letter-spacing: .05pt; mso-ascii-font-family: Calibri; mso-bidi-font-family: Calibri; mso-fareast-font-family: Calibri; mso-hansi-font-family: Calibri;">1</span>s and<span style="letter-spacing: -.05pt;"> </span><span style="letter-spacing: .05pt;">t</span><span style="letter-spacing: -.15pt;">h</span>en <span style="letter-spacing: .05pt;">2</span>s<span style="letter-spacing: -.1pt;"> </span>in O<span style="letter-spacing: .05pt;">(</span>n)<span style="letter-spacing: -.05pt;"> </span>ti<span style="letter-spacing: -.05pt;">m</span><span style="letter-spacing: -.1pt;">e</span>.<o:p></o:p></span></div>
<div class="MsoNormal" style="margin: 2.15pt -1pt 0.0001pt 41pt;">
<span style="font-family: Trebuchet MS, sans-serif;">Ex<span style="letter-spacing: .05pt;">:</span>-<span style="letter-spacing: -.1pt;"> </span><span style="letter-spacing: .05pt;">2</span>-<span style="letter-spacing: -.1pt;">></span><span style="letter-spacing: .05pt;">2</span>-><span style="letter-spacing: .05pt;">1</span><span style="letter-spacing: -.15pt;">-</span>><span style="letter-spacing: .05pt;">0</span>-<span style="letter-spacing: -.1pt;">></span><span style="letter-spacing: .05pt;">0</span>-<span style="letter-spacing: -.1pt;">></span><span style="letter-spacing: .05pt;">2</span>-<span style="letter-spacing: -.1pt;">></span><span style="letter-spacing: .05pt;">1</span>-<span style="letter-spacing: -.1pt;">></span><span style="letter-spacing: .05pt;">1</span>->0<span style="letter-spacing: 2.5pt;"> </span>=<span style="letter-spacing: -.1pt;"> </span><span style="letter-spacing: .05pt;">0</span>-<span style="letter-spacing: -.1pt;">></span><span style="letter-spacing: .05pt;">0</span>-<span style="letter-spacing: -.1pt;">></span><span style="letter-spacing: .05pt;">0</span>-><span style="letter-spacing: .05pt;">1</span><span style="letter-spacing: -.15pt;">-</span>><span style="letter-spacing: .05pt;">1</span><span style="letter-spacing: -.15pt;">-</span>><span style="letter-spacing: .05pt;">1</span><span style="letter-spacing: -.15pt;">-</span><span style="letter-spacing: -.1pt;">2</span>-><span style="letter-spacing: .05pt;">2</span>-<span style="letter-spacing: -.1pt;">>2</span><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 12.0pt; margin-bottom: .0001pt; margin-bottom: 0cm; mso-line-height-rule: exactly;">
<br /></div>
<div class="MsoNormal" style="margin: 0cm -1pt 0.0001pt 5pt;">
<span style="font-family: Trebuchet MS, sans-serif;"><b>PI<span style="letter-spacing: .05pt;"> r</span><span style="letter-spacing: -.05pt;">oun</span>d<span style="letter-spacing: -.05pt;"> </span>1<span style="letter-spacing: -.05pt;"> (</span><span style="letter-spacing: .05pt;">T</span><span style="letter-spacing: -.05pt;">e</span><span style="letter-spacing: .05pt;">c</span><span style="letter-spacing: -.05pt;">hni</span><span style="letter-spacing: .05pt;">c</span><span style="letter-spacing: -.05pt;">al</span><span style="letter-spacing: .05pt;">):</span></b><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 11.0pt; margin-bottom: .0001pt; margin-bottom: 0cm; margin-left: 0cm; margin-right: 0cm; margin-top: .9pt; mso-line-height-rule: exactly;">
<br /></div>
<div class="MsoNormal" style="margin: 0cm -1pt 0.0001pt 23pt;">
<span style="font-family: Trebuchet MS, sans-serif;"><b>1</b><b>. <span style="letter-spacing: 1.95pt;"> </span></b><span style="letter-spacing: -.05pt; mso-ascii-font-family: Calibri; mso-bidi-font-family: Calibri; mso-fareast-font-family: Calibri; mso-hansi-font-family: Calibri;">Ab</span><span style="letter-spacing: .05pt; mso-ascii-font-family: Calibri; mso-bidi-font-family: Calibri; mso-fareast-font-family: Calibri; mso-hansi-font-family: Calibri;">o</span><span style="letter-spacing: -.05pt; mso-ascii-font-family: Calibri; mso-bidi-font-family: Calibri; mso-fareast-font-family: Calibri; mso-hansi-font-family: Calibri;">u</span>t<span style="letter-spacing: .05pt;"> </span><span style="letter-spacing: -.05pt;">u</span>rself,<span style="letter-spacing: -.1pt;"> </span><span style="letter-spacing: -.05pt;">m</span><span style="letter-spacing: .05pt;">o</span><span style="letter-spacing: -.1pt;">s</span>t<span style="letter-spacing: .05pt;"> </span>ch<span style="letter-spacing: -.05pt;">a</span>llen<span style="letter-spacing: -.15pt;">g</span>i<span style="letter-spacing: -.05pt;">n</span>g<span style="letter-spacing: -.05pt;"> </span>pr<span style="letter-spacing: .1pt;">o</span>je<span style="letter-spacing: .05pt;">c</span>t<span style="letter-spacing: -.1pt;"> </span><span style="letter-spacing: .05pt;">o</span>f<span style="letter-spacing: -.15pt;"> </span>all <span style="letter-spacing: -.05pt;">y</span><span style="letter-spacing: .05pt;">o</span>u<span style="letter-spacing: -.05pt;"> </span>h<span style="letter-spacing: -.15pt;">a</span><span style="letter-spacing: .05pt;">v</span>e<span style="letter-spacing: -.05pt;"> d</span><span style="letter-spacing: .05pt;">o</span><span style="letter-spacing: -.05pt;">n</span>e<span style="letter-spacing: .05pt;"> </span>a<span style="letter-spacing: -.05pt;">n</span>d<span style="letter-spacing: -.05pt;"> </span>a<span style="letter-spacing: -.15pt;">b</span><span style="letter-spacing: .05pt;">o</span><span style="letter-spacing: -.05pt;">u</span>t<span style="letter-spacing: .05pt;"> </span><span style="letter-spacing: -.05pt;">u</span>r i<span style="letter-spacing: -.05pt;">n</span><span style="letter-spacing: -.1pt;">t</span>erns<span style="letter-spacing: -.05pt;">h</span>i<span style="letter-spacing: -.05pt;">p</span>.<o:p></o:p></span></div>
<div class="MsoNormal" style="margin: 2.05pt -1pt 0.0001pt 23pt;">
<span style="font-family: Trebuchet MS, sans-serif;"><b>2</b><b>. <span style="letter-spacing: 1.95pt;"> </span></b>Re<span style="letter-spacing: -.05pt;">mo</span><span style="letter-spacing: .05pt;">v</span>e<span style="letter-spacing: .05pt;"> </span>f<span style="letter-spacing: -.15pt;">r</span><span style="letter-spacing: -.05pt;">o</span>m<span style="letter-spacing: .05pt;"> </span>s<span style="letter-spacing: -.05pt;">t</span>ri<span style="letter-spacing: -.05pt;">n</span>g<span style="letter-spacing: -.05pt;"> </span>s<span style="letter-spacing: .05pt;">1</span>,<span style="letter-spacing: -.1pt;"> </span>all <span style="letter-spacing: -.1pt;">t</span><span style="letter-spacing: -.05pt;">h</span>e<span style="letter-spacing: .05pt;"> </span>ch<span style="letter-spacing: -.05pt;">a</span>ra<span style="letter-spacing: .1pt;">c</span><span style="letter-spacing: -.1pt;">t</span>ers<span style="letter-spacing: .05pt;"> </span>th<span style="letter-spacing: -.15pt;">a</span>t<span style="letter-spacing: .05pt;"> </span>are<span style="letter-spacing: -.1pt;"> </span>pre<span style="letter-spacing: -.1pt;">s</span>ent in stri<span style="letter-spacing: -.05pt;">n</span>g<span style="letter-spacing: .05pt;"> </span><span style="letter-spacing: -.1pt;">s</span><span style="letter-spacing: .05pt;">2</span>.<o:p></o:p></span></div>
<div class="MsoNormal" style="margin: 1.9pt -1pt 0.0001pt 41pt;">
<span style="font-family: Trebuchet MS, sans-serif;"><span style="letter-spacing: -.05pt; mso-ascii-font-family: Calibri; mso-bidi-font-family: Calibri; mso-fareast-font-family: Calibri; mso-hansi-font-family: Calibri;">S</span><span style="letter-spacing: .05pt; mso-ascii-font-family: Calibri; mso-bidi-font-family: Calibri; mso-fareast-font-family: Calibri; mso-hansi-font-family: Calibri;">1</span>=<span style="letter-spacing: .05pt;">”</span>a<span style="letter-spacing: -.15pt;">b</span>cde” s<span style="letter-spacing: -.1pt;">2</span>=<span style="letter-spacing: -.05pt;">”</span>x<span style="letter-spacing: .05pt;">y</span>a<span style="letter-spacing: -.05pt;">zbx</span>” <span style="letter-spacing: 2.45pt;"> </span>A<span style="letter-spacing: -.05pt;">n</span>s. <span style="letter-spacing: -.05pt;">S</span><span style="letter-spacing: .05pt;">1</span>=<span style="letter-spacing: -.05pt;"> </span><span style="letter-spacing: .05pt;">”</span>cd<span style="letter-spacing: -.1pt;">e</span>”<o:p></o:p></span></div>
<div class="MsoNormal" style="margin: 2.05pt -1pt 0.0001pt 23pt;">
<span style="font-family: Trebuchet MS, sans-serif;"><b>3</b><b>. <span style="letter-spacing: 1.95pt;"> </span></b>Re<span style="letter-spacing: -.05pt;">v</span>erse<span style="letter-spacing: -.05pt;"> </span>altern<span style="letter-spacing: -.05pt;">a</span><span style="letter-spacing: -.1pt;">t</span>e<span style="letter-spacing: .05pt;"> </span>k<span style="letter-spacing: -.1pt;"> </span>n<span style="letter-spacing: .05pt;">o</span><span style="letter-spacing: -.05pt;">d</span><span style="letter-spacing: -.1pt;">e</span>s <span style="letter-spacing: -.1pt;">i</span>n<span style="letter-spacing: -.05pt;"> </span>an <span style="letter-spacing: .05pt;">l</span>i<span style="letter-spacing: -.05pt;">n</span>k<span style="letter-spacing: .05pt;">e</span>d<span style="letter-spacing: -.05pt;"> </span>list.<o:p></o:p></span></div>
<div class="MsoNormal" style="margin: 2.05pt -1pt 0.0001pt 41pt;">
<span style="font-family: Trebuchet MS, sans-serif;">Ex<span style="letter-spacing: .05pt;">:</span>-<span style="letter-spacing: -.1pt;"> </span><span style="letter-spacing: .05pt;">1</span>-<span style="letter-spacing: -.1pt;">></span><span style="letter-spacing: .05pt;">2</span>-><span style="letter-spacing: .05pt;">3</span><span style="letter-spacing: -.15pt;">-</span>><span style="letter-spacing: .05pt;">4</span>-<span style="letter-spacing: -.1pt;">></span><span style="letter-spacing: .05pt;">5</span>-<span style="letter-spacing: -.1pt;">></span><span style="letter-spacing: .05pt;">6</span>-<span style="letter-spacing: -.1pt;">></span><span style="letter-spacing: .05pt;">7</span>-<span style="letter-spacing: -.1pt;">></span>8 <span style="letter-spacing: .1pt;"> </span>if<span style="letter-spacing: -.1pt;"> </span>k<span style="letter-spacing: -.05pt;">=</span><span style="letter-spacing: .05pt;">2</span>;<span style="letter-spacing: -.05pt;"> </span><span style="letter-spacing: .05pt;">t</span><span style="letter-spacing: -.05pt;">h</span>en r<span style="letter-spacing: -.1pt;">e</span>turn<span style="letter-spacing: -.05pt;"> </span><span style="letter-spacing: .05pt;">2</span>-<span style="letter-spacing: -.1pt;">></span><span style="letter-spacing: .05pt;">1</span><span style="letter-spacing: -.15pt;">-</span>><span style="letter-spacing: .05pt;">3</span>-<span style="letter-spacing: -.1pt;">></span><span style="letter-spacing: .05pt;">4</span>-<span style="letter-spacing: -.1pt;">></span><span style="letter-spacing: .05pt;">6</span>-><span style="letter-spacing: .05pt;">5</span><span style="letter-spacing: -.15pt;">-</span>><span style="letter-spacing: .05pt;">7</span>-<span style="letter-spacing: -.1pt;">></span>8<o:p></o:p></span></div>
<div class="MsoNormal" style="margin: 1.9pt -1pt 0.0001pt 23pt;">
<span style="font-family: Trebuchet MS, sans-serif;"><b>4</b><b>. <span style="letter-spacing: 1.95pt;"> </span></b>A<span style="letter-spacing: -.05pt;">l</span>wa<span style="letter-spacing: .05pt;">y</span>s <span style="letter-spacing: -.1pt;">a</span>sk<span style="letter-spacing: .05pt;"> </span><span style="letter-spacing: -.1pt;">s</span><span style="letter-spacing: -.05pt;">o</span><span style="letter-spacing: .05pt;">m</span>e<span style="letter-spacing: .05pt;"> </span><span style="letter-spacing: -.05pt;">q</span><span style="letter-spacing: -.15pt;">u</span>es<span style="letter-spacing: .05pt;">t</span><span style="letter-spacing: -.15pt;">i</span><span style="letter-spacing: .05pt;">o</span><span style="letter-spacing: -.05pt;">n</span>s<span style="letter-spacing: -.1pt;"> </span><span style="letter-spacing: .05pt;">t</span>o<span style="letter-spacing: -.05pt;"> </span>the<span style="letter-spacing: .2pt;"> </span>i<span style="letter-spacing: -.05pt;">n</span><span style="letter-spacing: -.1pt;">t</span>er<span style="letter-spacing: .05pt;">v</span><span style="letter-spacing: -.15pt;">i</span>e<span style="letter-spacing: -.05pt;">w</span>er<span style="letter-spacing: .05pt;"> </span>at<span style="letter-spacing: -.05pt;"> </span>the<span style="letter-spacing: -.05pt;"> </span><span style="letter-spacing: -.1pt;">e</span><span style="letter-spacing: -.05pt;">nd</span>. That’s<span style="letter-spacing: .05pt;"> </span>a <span style="letter-spacing: -.15pt;">g</span><span style="letter-spacing: .05pt;">oo</span>d<span style="letter-spacing: -.15pt;"> </span>gesture.<o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 115%; margin-bottom: .0001pt; margin-bottom: 0cm; margin-left: 41.0pt; margin-right: 14.3pt; margin-top: 2.05pt; text-indent: -18.0pt;">
<span style="font-family: Trebuchet MS, sans-serif;"><b>5</b><b>. <span style="letter-spacing: 1.95pt;"> </span></b>Write<span style="letter-spacing: -.05pt;"> </span>t<span style="letter-spacing: .05pt;">e</span><span style="letter-spacing: -.1pt;">s</span>t<span style="letter-spacing: .05pt;"> </span>ca<span style="letter-spacing: -.1pt;">s</span>es<span style="letter-spacing: .05pt;"> </span><span style="letter-spacing: -.15pt;">f</span><span style="letter-spacing: .05pt;">o</span>r t<span style="letter-spacing: -.15pt;">h</span>e<span style="letter-spacing: .05pt;"> </span><span style="letter-spacing: -.05pt;">p</span>r<span style="letter-spacing: -.05pt;">og</span>ra<span style="letter-spacing: .05pt;">m</span>s a<span style="letter-spacing: -.15pt;">b</span><span style="letter-spacing: .05pt;">o</span><span style="letter-spacing: -.05pt;">v</span>e<span style="letter-spacing: .15pt;"> </span>a<span style="letter-spacing: -.05pt;">n</span>d<span style="letter-spacing: -.05pt;"> </span><span style="letter-spacing: -.1pt;">s</span>ee<span style="letter-spacing: .05pt;"> </span>if ur<span style="letter-spacing: -.25pt;"> </span><span style="letter-spacing: -.05pt;">p</span>r<span style="letter-spacing: .05pt;">o</span><span style="letter-spacing: -.05pt;">g</span>ram<span style="letter-spacing: -.05pt;"> </span>c<span style="letter-spacing: -.05pt;">o</span><span style="letter-spacing: .05pt;">v</span>e<span style="letter-spacing: -.1pt;">r</span>s all t<span style="letter-spacing: -.15pt;">h</span>e<span style="letter-spacing: .05pt;"> </span><span style="letter-spacing: -.1pt;">t</span>est<span style="letter-spacing: -.05pt;"> </span>cases<span style="letter-spacing: -.05pt;"> </span><span style="letter-spacing: .05pt;">o</span>r <span style="letter-spacing: -.05pt;">n</span><span style="letter-spacing: .05pt;">o</span>t.<o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 10.0pt; margin-bottom: .0001pt; margin-bottom: 0cm; margin-left: 0cm; margin-right: 0cm; margin-top: .25pt; mso-line-height-rule: exactly;">
<br /></div>
<div class="MsoNormal" style="margin: 0cm -1pt 0.0001pt 5pt;">
<span style="font-family: Trebuchet MS, sans-serif;"><b>PI<span style="letter-spacing: .05pt;"> r</span><span style="letter-spacing: -.05pt;">oun</span>d<span style="letter-spacing: -.05pt;"> </span>2<span style="letter-spacing: -.05pt;"> </span><span style="letter-spacing: .05pt;">(</span><span style="letter-spacing: -.1pt;">P</span><span style="letter-spacing: .05pt;">r</span><span style="letter-spacing: -.05pt;">o</span><span style="letter-spacing: .05pt;">gr</span><span style="letter-spacing: -.15pt;">a</span>m<span style="letter-spacing: .05pt;"> </span>ma<span style="letter-spacing: -.05pt;">n</span><span style="letter-spacing: -.15pt;">a</span><span style="letter-spacing: .05pt;">g</span><span style="letter-spacing: -.05pt;">e</span><span style="letter-spacing: .1pt;">r</span>)</b><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 11.0pt; margin-bottom: .0001pt; margin-bottom: 0cm; margin-left: 0cm; margin-right: 0cm; margin-top: .9pt; mso-line-height-rule: exactly;">
<br /></div>
<div class="MsoNormal" style="margin: 0cm -1pt 0.0001pt 23pt;">
<span style="font-family: Trebuchet MS, sans-serif;"><span style="letter-spacing: .05pt; mso-ascii-font-family: Calibri; mso-bidi-font-family: Calibri; mso-fareast-font-family: Calibri; mso-hansi-font-family: Calibri;">1</span>. <span style="letter-spacing: 2.1pt;"> </span><span style="letter-spacing: .05pt;">D</span>esign<span style="letter-spacing: -.05pt;"> </span>a<span style="letter-spacing: -.05pt;"> </span>tic-ta<span style="letter-spacing: .05pt;">c</span><span style="letter-spacing: -.15pt;">-</span>t<span style="letter-spacing: -.05pt;">o</span>e<span style="letter-spacing: .05pt;"> </span><span style="letter-spacing: -.05pt;">g</span><span style="letter-spacing: -.15pt;">a</span><span style="letter-spacing: .05pt;">m</span>e<span style="letter-spacing: .05pt;"> </span><span style="letter-spacing: -.15pt;">f</span><span style="letter-spacing: .05pt;">o</span>r<span style="letter-spacing: -.1pt;"> </span><span style="letter-spacing: .05pt;">m</span><span style="letter-spacing: -.05pt;">u</span>lti<span style="letter-spacing: -.05pt;">p</span>la<span style="letter-spacing: -.1pt;">y</span>er<span style="letter-spacing: -.05pt;"> </span><span style="letter-spacing: .05pt;">o</span>n<span style="letter-spacing: -.05pt;"> </span>a<span style="letter-spacing: .05pt;"> </span><span style="letter-spacing: -.1pt;">s</span><span style="letter-spacing: .05pt;">m</span>art<span style="letter-spacing: -.15pt;">p</span><span style="letter-spacing: -.05pt;">h</span><span style="letter-spacing: .05pt;">o</span><span style="letter-spacing: -.05pt;">n</span>e.<o:p></o:p></span></div>
<div class="MsoNormal" style="margin: 2.05pt -1pt 0.0001pt 23pt;">
<span style="font-family: Trebuchet MS, sans-serif;"><span style="letter-spacing: .05pt; mso-ascii-font-family: Calibri; mso-bidi-font-family: Calibri; mso-fareast-font-family: Calibri; mso-hansi-font-family: Calibri;">2</span>. <span style="letter-spacing: 2.1pt;"> </span><span style="letter-spacing: .05pt;">D</span>esign<span style="letter-spacing: -.05pt;"> </span>a<span style="letter-spacing: -.05pt;"> </span><span style="letter-spacing: .05pt;">v</span>en<span style="letter-spacing: -.05pt;">d</span>i<span style="letter-spacing: -.05pt;">n</span>g<span style="letter-spacing: -.15pt;"> </span><span style="letter-spacing: .05pt;">m</span>ac<span style="letter-spacing: -.05pt;">h</span>i<span style="letter-spacing: -.05pt;">n</span>e<span style="letter-spacing: .05pt;"> </span><span style="letter-spacing: -.15pt;">f</span><span style="letter-spacing: .05pt;">o</span>r b<span style="letter-spacing: -.05pt;">l</span>i<span style="letter-spacing: -.05pt;">n</span>d<span style="letter-spacing: -.05pt;"> </span>and<span style="letter-spacing: -.05pt;"> </span>deaf.<o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 12.0pt; margin-bottom: .0001pt; margin-bottom: 0cm; mso-line-height-rule: exactly;">
<br /></div>
<div class="MsoNormal" style="margin: 0cm -1pt 0.0001pt 5pt;">
<span style="font-family: Trebuchet MS, sans-serif;"><b>PI<span style="letter-spacing: .05pt;"> r</span><span style="letter-spacing: -.05pt;">oun</span>d<span style="letter-spacing: -.05pt;"> </span>3<span style="letter-spacing: -.05pt;"> (</span><span style="letter-spacing: .05pt;">T</span><span style="letter-spacing: -.05pt;">e</span><span style="letter-spacing: .05pt;">c</span><span style="letter-spacing: -.05pt;">hni</span><span style="letter-spacing: .05pt;">c</span><span style="letter-spacing: -.05pt;">al</span>)</b><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 10.0pt; margin-bottom: .0001pt; margin-bottom: 0cm; margin-left: 0cm; margin-right: 0cm; margin-top: .8pt; mso-line-height-rule: exactly;">
<br /></div>
<div class="MsoNormal" style="margin: 0cm -1pt 0.0001pt 23pt;">
<span style="font-family: Trebuchet MS, sans-serif;"><span style="letter-spacing: .05pt; mso-ascii-font-family: Calibri; mso-bidi-font-family: Calibri; mso-fareast-font-family: Calibri; mso-hansi-font-family: Calibri;">1</span>. <span style="letter-spacing: 2.1pt;"> </span>A<span style="letter-spacing: -.05pt;">d</span>d<span style="letter-spacing: -.05pt;"> </span>n<span style="letter-spacing: -.05pt;">u</span><span style="letter-spacing: .05pt;">m</span><span style="letter-spacing: -.05pt;">b</span>ers<span style="letter-spacing: .05pt;"> </span>f<span style="letter-spacing: -.15pt;">r</span><span style="letter-spacing: -.05pt;">o</span>m<span style="letter-spacing: .05pt;"> </span>1<span style="letter-spacing: -.05pt;"> </span><span style="letter-spacing: -.1pt;">t</span>o<span style="letter-spacing: .15pt;"> </span><span style="letter-spacing: -.05pt;">n</span><span style="font-size: 12.0pt; mso-ascii-font-family: Calibri; mso-bidi-font-family: Calibri; mso-fareast-font-family: Calibri; mso-hansi-font-family: Calibri; mso-text-raise: 5.0pt; position: relative; top: -5.0pt;">2 <span style="letter-spacing: .85pt;"> </span></span>i<span style="letter-spacing: -.05pt;">n</span>to<span style="letter-spacing: .1pt;"> </span>a<span style="letter-spacing: .05pt;"> </span>n<span style="letter-spacing: -.15pt;"> </span>X<span style="letter-spacing: .05pt;"> </span>n<span style="letter-spacing: -.15pt;"> </span><span style="letter-spacing: .05pt;">m</span>atr<span style="letter-spacing: -.15pt;">i</span>x<span style="letter-spacing: .05pt;"> </span>sp<span style="letter-spacing: -.05pt;">i</span>ra<span style="letter-spacing: -.05pt;">l</span><span style="letter-spacing: -.15pt;">l</span><span style="letter-spacing: .05pt;">y</span>.<o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 2.0pt; margin-bottom: .0001pt; margin-bottom: 0cm; margin-left: 0cm; margin-right: 0cm; margin-top: .35pt; mso-line-height-rule: exactly;">
<br /></div>
<table border="0" cellpadding="0" cellspacing="0" class="MsoNormalTable" style="border-collapse: collapse; margin-left: 35.05pt; mso-padding-alt: 0cm 0cm 0cm 0cm; mso-table-layout-alt: fixed; mso-yfti-tbllook: 480;"><tbody>
<tr style="height: 14.15pt; mso-height-rule: exactly; mso-yfti-firstrow: yes; mso-yfti-irow: 0;"> <td style="border: solid black 1.0pt; height: 14.15pt; mso-border-alt: solid black .5pt; mso-height-rule: exactly; padding: 0cm 0cm 0cm 0cm; width: 34.1pt;" valign="top" width="45"><div class="MsoNormal" style="line-height: 13.0pt; margin-bottom: .0001pt; margin-bottom: 0cm; margin-left: 5.1pt; margin-right: -1.0pt; margin-top: 0cm; mso-line-height-rule: exactly;">
<span style="font-family: Trebuchet MS, sans-serif;">1<o:p></o:p></span></div>
</td> <td style="border-left: none; border: solid black 1.0pt; height: 14.15pt; mso-border-alt: solid black .5pt; mso-border-left-alt: solid black .5pt; mso-height-rule: exactly; padding: 0cm 0cm 0cm 0cm; width: 34.1pt;" valign="top" width="45"><div class="MsoNormal" style="line-height: 13.0pt; margin-bottom: .0001pt; margin-bottom: 0cm; margin-left: 5.1pt; margin-right: -1.0pt; margin-top: 0cm; mso-line-height-rule: exactly;">
<span style="font-family: Trebuchet MS, sans-serif;">2<o:p></o:p></span></div>
</td> <td style="border-left: none; border: solid black 1.0pt; height: 14.15pt; mso-border-alt: solid black .5pt; mso-border-left-alt: solid black .5pt; mso-height-rule: exactly; padding: 0cm 0cm 0cm 0cm; width: 34.25pt;" valign="top" width="46"><div class="MsoNormal" style="line-height: 13.0pt; margin-bottom: .0001pt; margin-bottom: 0cm; margin-left: 5.1pt; margin-right: -1.0pt; margin-top: 0cm; mso-line-height-rule: exactly;">
<span style="font-family: Trebuchet MS, sans-serif;">3<o:p></o:p></span></div>
</td> <td style="border-left: none; border: solid black 1.0pt; height: 14.15pt; mso-border-alt: solid black .5pt; mso-border-left-alt: solid black .5pt; mso-height-rule: exactly; padding: 0cm 0cm 0cm 0cm; width: 34.1pt;" valign="top" width="45"><div class="MsoNormal" style="line-height: 13.0pt; margin-bottom: .0001pt; margin-bottom: 0cm; margin-left: 5.0pt; margin-right: -1.0pt; margin-top: 0cm; mso-line-height-rule: exactly;">
<span style="font-family: Trebuchet MS, sans-serif;">4<o:p></o:p></span></div>
</td> <td style="border-left: none; border: solid black 1.0pt; height: 14.15pt; mso-border-alt: solid black .5pt; mso-border-left-alt: solid black .5pt; mso-height-rule: exactly; padding: 0cm 0cm 0cm 0cm; width: 34.2pt;" valign="top" width="46"><div class="MsoNormal" style="line-height: 13.0pt; margin-bottom: .0001pt; margin-bottom: 0cm; margin-left: 5.1pt; margin-right: -1.0pt; margin-top: 0cm; mso-line-height-rule: exactly;">
<span style="font-family: Trebuchet MS, sans-serif;">5<o:p></o:p></span></div>
</td> </tr>
<tr style="height: 13.9pt; mso-height-rule: exactly; mso-yfti-irow: 1;"> <td style="border-top: none; border: solid black 1.0pt; height: 13.9pt; mso-border-alt: solid black .5pt; mso-border-top-alt: solid black .5pt; mso-height-rule: exactly; padding: 0cm 0cm 0cm 0cm; width: 34.1pt;" valign="top" width="45"><div class="MsoNormal" style="line-height: 13.0pt; margin-bottom: .0001pt; margin-bottom: 0cm; margin-left: 5.1pt; margin-right: -1.0pt; margin-top: 0cm; mso-line-height-rule: exactly;">
<span style="font-family: Trebuchet MS, sans-serif;"><span style="letter-spacing: .05pt; mso-ascii-font-family: Calibri; mso-bidi-font-family: Calibri; mso-fareast-font-family: Calibri; mso-hansi-font-family: Calibri;">16</span><o:p></o:p></span></div>
</td> <td style="border-bottom: solid black 1.0pt; border-left: none; border-right: solid black 1.0pt; border-top: none; height: 13.9pt; mso-border-alt: solid black .5pt; mso-border-left-alt: solid black .5pt; mso-border-top-alt: solid black .5pt; mso-height-rule: exactly; padding: 0cm 0cm 0cm 0cm; width: 34.1pt;" valign="top" width="45"><div class="MsoNormal" style="line-height: 13.0pt; margin-bottom: .0001pt; margin-bottom: 0cm; margin-left: 5.1pt; margin-right: -1.0pt; margin-top: 0cm; mso-line-height-rule: exactly;">
<span style="font-family: Trebuchet MS, sans-serif;"><span style="letter-spacing: .05pt; mso-ascii-font-family: Calibri; mso-bidi-font-family: Calibri; mso-fareast-font-family: Calibri; mso-hansi-font-family: Calibri;">17</span><o:p></o:p></span></div>
</td> <td style="border-bottom: solid black 1.0pt; border-left: none; border-right: solid black 1.0pt; border-top: none; height: 13.9pt; mso-border-alt: solid black .5pt; mso-border-left-alt: solid black .5pt; mso-border-top-alt: solid black .5pt; mso-height-rule: exactly; padding: 0cm 0cm 0cm 0cm; width: 34.25pt;" valign="top" width="46"><div class="MsoNormal" style="line-height: 13.0pt; margin-bottom: .0001pt; margin-bottom: 0cm; margin-left: 5.1pt; margin-right: -1.0pt; margin-top: 0cm; mso-line-height-rule: exactly;">
<span style="font-family: Trebuchet MS, sans-serif;"><span style="letter-spacing: .05pt; mso-ascii-font-family: Calibri; mso-bidi-font-family: Calibri; mso-fareast-font-family: Calibri; mso-hansi-font-family: Calibri;">18</span><o:p></o:p></span></div>
</td> <td style="border-bottom: solid black 1.0pt; border-left: none; border-right: solid black 1.0pt; border-top: none; height: 13.9pt; mso-border-alt: solid black .5pt; mso-border-left-alt: solid black .5pt; mso-border-top-alt: solid black .5pt; mso-height-rule: exactly; padding: 0cm 0cm 0cm 0cm; width: 34.1pt;" valign="top" width="45"><div class="MsoNormal" style="line-height: 13.0pt; margin-bottom: .0001pt; margin-bottom: 0cm; margin-left: 5.0pt; margin-right: -1.0pt; margin-top: 0cm; mso-line-height-rule: exactly;">
<span style="font-family: Trebuchet MS, sans-serif;"><span style="letter-spacing: .05pt; mso-ascii-font-family: Calibri; mso-bidi-font-family: Calibri; mso-fareast-font-family: Calibri; mso-hansi-font-family: Calibri;">19</span><o:p></o:p></span></div>
</td> <td style="border-bottom: solid black 1.0pt; border-left: none; border-right: solid black 1.0pt; border-top: none; height: 13.9pt; mso-border-alt: solid black .5pt; mso-border-left-alt: solid black .5pt; mso-border-top-alt: solid black .5pt; mso-height-rule: exactly; padding: 0cm 0cm 0cm 0cm; width: 34.2pt;" valign="top" width="46"><div class="MsoNormal" style="line-height: 13.0pt; margin-bottom: .0001pt; margin-bottom: 0cm; margin-left: 5.1pt; margin-right: -1.0pt; margin-top: 0cm; mso-line-height-rule: exactly;">
<span style="font-family: Trebuchet MS, sans-serif;">6<o:p></o:p></span></div>
</td> </tr>
<tr style="height: 14.15pt; mso-height-rule: exactly; mso-yfti-irow: 2;"> <td style="border-top: none; border: solid black 1.0pt; height: 14.15pt; mso-border-alt: solid black .5pt; mso-border-top-alt: solid black .5pt; mso-height-rule: exactly; padding: 0cm 0cm 0cm 0cm; width: 34.1pt;" valign="top" width="45"><div class="MsoNormal" style="line-height: 13.0pt; margin-bottom: .0001pt; margin-bottom: 0cm; margin-left: 5.1pt; margin-right: -1.0pt; margin-top: 0cm; mso-line-height-rule: exactly;">
<span style="font-family: Trebuchet MS, sans-serif;"><span style="letter-spacing: .05pt; mso-ascii-font-family: Calibri; mso-bidi-font-family: Calibri; mso-fareast-font-family: Calibri; mso-hansi-font-family: Calibri;">15</span><o:p></o:p></span></div>
</td> <td style="border-bottom: solid black 1.0pt; border-left: none; border-right: solid black 1.0pt; border-top: none; height: 14.15pt; mso-border-alt: solid black .5pt; mso-border-left-alt: solid black .5pt; mso-border-top-alt: solid black .5pt; mso-height-rule: exactly; padding: 0cm 0cm 0cm 0cm; width: 34.1pt;" valign="top" width="45"><div class="MsoNormal" style="line-height: 13.0pt; margin-bottom: .0001pt; margin-bottom: 0cm; margin-left: 5.1pt; margin-right: -1.0pt; margin-top: 0cm; mso-line-height-rule: exactly;">
<span style="font-family: Trebuchet MS, sans-serif;"><span style="letter-spacing: .05pt; mso-ascii-font-family: Calibri; mso-bidi-font-family: Calibri; mso-fareast-font-family: Calibri; mso-hansi-font-family: Calibri;">24</span><o:p></o:p></span></div>
</td> <td style="border-bottom: solid black 1.0pt; border-left: none; border-right: solid black 1.0pt; border-top: none; height: 14.15pt; mso-border-alt: solid black .5pt; mso-border-left-alt: solid black .5pt; mso-border-top-alt: solid black .5pt; mso-height-rule: exactly; padding: 0cm 0cm 0cm 0cm; width: 34.25pt;" valign="top" width="46"><div class="MsoNormal" style="line-height: 13.0pt; margin-bottom: .0001pt; margin-bottom: 0cm; margin-left: 5.1pt; margin-right: -1.0pt; margin-top: 0cm; mso-line-height-rule: exactly;">
<span style="font-family: Trebuchet MS, sans-serif;"><span style="letter-spacing: .05pt; mso-ascii-font-family: Calibri; mso-bidi-font-family: Calibri; mso-fareast-font-family: Calibri; mso-hansi-font-family: Calibri;">25</span><o:p></o:p></span></div>
</td> <td style="border-bottom: solid black 1.0pt; border-left: none; border-right: solid black 1.0pt; border-top: none; height: 14.15pt; mso-border-alt: solid black .5pt; mso-border-left-alt: solid black .5pt; mso-border-top-alt: solid black .5pt; mso-height-rule: exactly; padding: 0cm 0cm 0cm 0cm; width: 34.1pt;" valign="top" width="45"><div class="MsoNormal" style="line-height: 13.0pt; margin-bottom: .0001pt; margin-bottom: 0cm; margin-left: 5.0pt; margin-right: -1.0pt; margin-top: 0cm; mso-line-height-rule: exactly;">
<span style="font-family: Trebuchet MS, sans-serif;"><span style="letter-spacing: .05pt; mso-ascii-font-family: Calibri; mso-bidi-font-family: Calibri; mso-fareast-font-family: Calibri; mso-hansi-font-family: Calibri;">20</span><o:p></o:p></span></div>
</td> <td style="border-bottom: solid black 1.0pt; border-left: none; border-right: solid black 1.0pt; border-top: none; height: 14.15pt; mso-border-alt: solid black .5pt; mso-border-left-alt: solid black .5pt; mso-border-top-alt: solid black .5pt; mso-height-rule: exactly; padding: 0cm 0cm 0cm 0cm; width: 34.2pt;" valign="top" width="46"><div class="MsoNormal" style="line-height: 13.0pt; margin-bottom: .0001pt; margin-bottom: 0cm; margin-left: 5.1pt; margin-right: -1.0pt; margin-top: 0cm; mso-line-height-rule: exactly;">
<span style="font-family: Trebuchet MS, sans-serif;">7<o:p></o:p></span></div>
</td> </tr>
<tr style="height: 13.9pt; mso-height-rule: exactly; mso-yfti-irow: 3;"> <td style="border-top: none; border: solid black 1.0pt; height: 13.9pt; mso-border-alt: solid black .5pt; mso-border-top-alt: solid black .5pt; mso-height-rule: exactly; padding: 0cm 0cm 0cm 0cm; width: 34.1pt;" valign="top" width="45"><div class="MsoNormal" style="line-height: 13.0pt; margin-bottom: .0001pt; margin-bottom: 0cm; margin-left: 5.1pt; margin-right: -1.0pt; margin-top: 0cm; mso-line-height-rule: exactly;">
<span style="font-family: Trebuchet MS, sans-serif;"><span style="letter-spacing: .05pt; mso-ascii-font-family: Calibri; mso-bidi-font-family: Calibri; mso-fareast-font-family: Calibri; mso-hansi-font-family: Calibri;">14</span><o:p></o:p></span></div>
</td> <td style="border-bottom: solid black 1.0pt; border-left: none; border-right: solid black 1.0pt; border-top: none; height: 13.9pt; mso-border-alt: solid black .5pt; mso-border-left-alt: solid black .5pt; mso-border-top-alt: solid black .5pt; mso-height-rule: exactly; padding: 0cm 0cm 0cm 0cm; width: 34.1pt;" valign="top" width="45"><div class="MsoNormal" style="line-height: 13.0pt; margin-bottom: .0001pt; margin-bottom: 0cm; margin-left: 5.1pt; margin-right: -1.0pt; margin-top: 0cm; mso-line-height-rule: exactly;">
<span style="font-family: Trebuchet MS, sans-serif;"><span style="letter-spacing: .05pt; mso-ascii-font-family: Calibri; mso-bidi-font-family: Calibri; mso-fareast-font-family: Calibri; mso-hansi-font-family: Calibri;">23</span><o:p></o:p></span></div>
</td> <td style="border-bottom: solid black 1.0pt; border-left: none; border-right: solid black 1.0pt; border-top: none; height: 13.9pt; mso-border-alt: solid black .5pt; mso-border-left-alt: solid black .5pt; mso-border-top-alt: solid black .5pt; mso-height-rule: exactly; padding: 0cm 0cm 0cm 0cm; width: 34.25pt;" valign="top" width="46"><div class="MsoNormal" style="line-height: 13.0pt; margin-bottom: .0001pt; margin-bottom: 0cm; margin-left: 5.1pt; margin-right: -1.0pt; margin-top: 0cm; mso-line-height-rule: exactly;">
<span style="font-family: Trebuchet MS, sans-serif;"><span style="letter-spacing: .05pt; mso-ascii-font-family: Calibri; mso-bidi-font-family: Calibri; mso-fareast-font-family: Calibri; mso-hansi-font-family: Calibri;">22</span><o:p></o:p></span></div>
</td> <td style="border-bottom: solid black 1.0pt; border-left: none; border-right: solid black 1.0pt; border-top: none; height: 13.9pt; mso-border-alt: solid black .5pt; mso-border-left-alt: solid black .5pt; mso-border-top-alt: solid black .5pt; mso-height-rule: exactly; padding: 0cm 0cm 0cm 0cm; width: 34.1pt;" valign="top" width="45"><div class="MsoNormal" style="line-height: 13.0pt; margin-bottom: .0001pt; margin-bottom: 0cm; margin-left: 5.0pt; margin-right: -1.0pt; margin-top: 0cm; mso-line-height-rule: exactly;">
<span style="font-family: Trebuchet MS, sans-serif;"><span style="letter-spacing: .05pt; mso-ascii-font-family: Calibri; mso-bidi-font-family: Calibri; mso-fareast-font-family: Calibri; mso-hansi-font-family: Calibri;">21</span><o:p></o:p></span></div>
</td> <td style="border-bottom: solid black 1.0pt; border-left: none; border-right: solid black 1.0pt; border-top: none; height: 13.9pt; mso-border-alt: solid black .5pt; mso-border-left-alt: solid black .5pt; mso-border-top-alt: solid black .5pt; mso-height-rule: exactly; padding: 0cm 0cm 0cm 0cm; width: 34.2pt;" valign="top" width="46"><div class="MsoNormal" style="line-height: 13.0pt; margin-bottom: .0001pt; margin-bottom: 0cm; margin-left: 5.1pt; margin-right: -1.0pt; margin-top: 0cm; mso-line-height-rule: exactly;">
<span style="font-family: Trebuchet MS, sans-serif;">8<o:p></o:p></span></div>
</td> </tr>
<tr style="height: 14.9pt; mso-height-rule: exactly; mso-yfti-irow: 4; mso-yfti-lastrow: yes;"> <td style="border-top: none; border: solid black 1.0pt; height: 14.9pt; mso-border-alt: solid black .5pt; mso-border-top-alt: solid black .5pt; mso-height-rule: exactly; padding: 0cm 0cm 0cm 0cm; width: 34.1pt;" valign="top" width="45"><div class="MsoNormal" style="line-height: 13.0pt; margin-bottom: .0001pt; margin-bottom: 0cm; margin-left: 5.1pt; margin-right: -1.0pt; margin-top: 0cm; mso-line-height-rule: exactly;">
<span style="font-family: Trebuchet MS, sans-serif;"><span style="letter-spacing: .05pt; mso-ascii-font-family: Calibri; mso-bidi-font-family: Calibri; mso-fareast-font-family: Calibri; mso-hansi-font-family: Calibri;">13</span><o:p></o:p></span></div>
</td> <td style="border-bottom: solid black 1.0pt; border-left: none; border-right: solid black 1.0pt; border-top: none; height: 14.9pt; mso-border-alt: solid black .5pt; mso-border-left-alt: solid black .5pt; mso-border-top-alt: solid black .5pt; mso-height-rule: exactly; padding: 0cm 0cm 0cm 0cm; width: 34.1pt;" valign="top" width="45"><div class="MsoNormal" style="line-height: 13.0pt; margin-bottom: .0001pt; margin-bottom: 0cm; margin-left: 5.1pt; margin-right: -1.0pt; margin-top: 0cm; mso-line-height-rule: exactly;">
<span style="font-family: Trebuchet MS, sans-serif;"><span style="letter-spacing: .05pt; mso-ascii-font-family: Calibri; mso-bidi-font-family: Calibri; mso-fareast-font-family: Calibri; mso-hansi-font-family: Calibri;">12</span><o:p></o:p></span></div>
</td> <td style="border-bottom: solid black 1.0pt; border-left: none; border-right: solid black 1.0pt; border-top: none; height: 14.9pt; mso-border-alt: solid black .5pt; mso-border-left-alt: solid black .5pt; mso-border-top-alt: solid black .5pt; mso-height-rule: exactly; padding: 0cm 0cm 0cm 0cm; width: 34.25pt;" valign="top" width="46"><div class="MsoNormal" style="line-height: 13.0pt; margin-bottom: .0001pt; margin-bottom: 0cm; margin-left: 5.1pt; margin-right: -1.0pt; margin-top: 0cm; mso-line-height-rule: exactly;">
<span style="font-family: Trebuchet MS, sans-serif;"><span style="letter-spacing: .05pt; mso-ascii-font-family: Calibri; mso-bidi-font-family: Calibri; mso-fareast-font-family: Calibri; mso-hansi-font-family: Calibri;">11</span><o:p></o:p></span></div>
</td> <td style="border-bottom: solid black 1.0pt; border-left: none; border-right: solid black 1.0pt; border-top: none; height: 14.9pt; mso-border-alt: solid black .5pt; mso-border-left-alt: solid black .5pt; mso-border-top-alt: solid black .5pt; mso-height-rule: exactly; padding: 0cm 0cm 0cm 0cm; width: 34.1pt;" valign="top" width="45"><div class="MsoNormal" style="line-height: 13.0pt; margin-bottom: .0001pt; margin-bottom: 0cm; margin-left: 5.0pt; margin-right: -1.0pt; margin-top: 0cm; mso-line-height-rule: exactly;">
<span style="font-family: Trebuchet MS, sans-serif;"><span style="letter-spacing: .05pt; mso-ascii-font-family: Calibri; mso-bidi-font-family: Calibri; mso-fareast-font-family: Calibri; mso-hansi-font-family: Calibri;">1</span>0<o:p></o:p></span></div>
</td> <td style="border-bottom: solid black 1.0pt; border-left: none; border-right: solid black 1.0pt; border-top: none; height: 14.9pt; mso-border-alt: solid black .5pt; mso-border-left-alt: solid black .5pt; mso-border-top-alt: solid black .5pt; mso-height-rule: exactly; padding: 0cm 0cm 0cm 0cm; width: 34.2pt;" valign="top" width="46"><div class="MsoNormal" style="line-height: 13.0pt; margin-bottom: .0001pt; margin-bottom: 0cm; margin-left: 5.1pt; margin-right: -1.0pt; margin-top: 0cm; mso-line-height-rule: exactly;">
<span style="font-family: Trebuchet MS, sans-serif;">9<o:p></o:p></span></div>
</td> </tr>
</tbody></table>
<div class="MsoNormal" style="line-height: 14.0pt; margin-bottom: .0001pt; margin-bottom: 0cm; margin-left: 0cm; margin-right: 0cm; margin-top: .5pt; mso-line-height-rule: exactly;">
<br /></div>
<div class="MsoNormal" style="margin: 0.6pt -1pt 0.0001pt 23pt;">
<span style="font-family: Trebuchet MS, sans-serif;"><span style="letter-spacing: .05pt; mso-ascii-font-family: Calibri; mso-bidi-font-family: Calibri; mso-fareast-font-family: Calibri; mso-hansi-font-family: Calibri;">2</span>. <span style="letter-spacing: 2.1pt;"> </span>Re<span style="letter-spacing: -.05pt;">mo</span><span style="letter-spacing: .05pt;">v</span>e<span style="letter-spacing: .05pt;"> </span><span style="letter-spacing: -.05pt;">dup</span>lica<span style="letter-spacing: -.1pt;">t</span>es<span style="letter-spacing: .05pt;"> </span>f<span style="letter-spacing: -.15pt;">r</span><span style="letter-spacing: -.05pt;">o</span>m<span style="letter-spacing: .05pt;"> </span>a<span style="letter-spacing: -.05pt;"> </span>string<span style="letter-spacing: -.05pt;"> </span>in <span style="letter-spacing: -.05pt;">p</span>lace.<o:p></o:p></span></div>
<div class="MsoNormal" style="margin: 2.05pt -1pt 0.0001pt 41pt;">
<span style="font-family: Trebuchet MS, sans-serif;">Ex-<span style="letter-spacing: .05pt;">m</span>ic<span style="letter-spacing: -.15pt;">r</span><span style="letter-spacing: .05pt;">o</span><span style="letter-spacing: -.1pt;">s</span><span style="letter-spacing: .05pt;">o</span>ft<span style="letter-spacing: -.05pt;"> </span>-><span style="letter-spacing: -.05pt;"> </span><span style="letter-spacing: .05pt;">m</span>ic<span style="letter-spacing: -.15pt;">r</span><span style="letter-spacing: .05pt;">o</span>sft<o:p></o:p></span></div>
<div class="MsoNormal" style="margin: 2.05pt -1pt 0.0001pt 23pt;">
<span style="font-family: Trebuchet MS, sans-serif;"><span style="letter-spacing: .05pt; mso-ascii-font-family: Calibri; mso-bidi-font-family: Calibri; mso-fareast-font-family: Calibri; mso-hansi-font-family: Calibri;">3</span>. <span style="letter-spacing: 2.1pt;"> </span>So<span style="letter-spacing: -.05pt;">m</span>e<span style="letter-spacing: .05pt;"> </span><span style="letter-spacing: -.05pt;">qu</span>es<span style="letter-spacing: .05pt;">t</span><span style="letter-spacing: -.15pt;">i</span><span style="letter-spacing: .05pt;">o</span>n<span style="letter-spacing: -.15pt;"> </span><span style="letter-spacing: .05pt;">o</span>n<span style="letter-spacing: -.05pt;"> </span>r<span style="letter-spacing: -.1pt;">e</span>cu<span style="letter-spacing: -.05pt;">r</span>si<span style="letter-spacing: -.1pt;">v</span>e<span style="letter-spacing: .05pt;"> </span>f<span style="letter-spacing: -.05pt;">un</span>ct<span style="letter-spacing: -.1pt;">i</span><span style="letter-spacing: .05pt;">o</span><span style="letter-spacing: -.05pt;">n</span>s usi<span style="letter-spacing: -.05pt;">n</span>g<span style="letter-spacing: .1pt;"> </span><span style="letter-spacing: -.05pt;">m</span><span style="letter-spacing: -.1pt;">e</span><span style="letter-spacing: .05pt;">mo</span>ri<span style="letter-spacing: -.2pt;">z</span>ati<span style="letter-spacing: .05pt;">o</span>n<span style="letter-spacing: .05pt;"> </span><span style="letter-spacing: -.1pt;">t</span>ech<span style="letter-spacing: -.05pt;">n</span>i<span style="letter-spacing: -.05pt;">qu</span>e<span style="letter-spacing: .05pt;"> </span><span style="letter-spacing: -.15pt;">f</span><span style="letter-spacing: .05pt;">o</span>r<span style="letter-spacing: -.1pt;"> </span><span style="letter-spacing: .05pt;">o</span><span style="letter-spacing: -.05pt;">p</span>ti<span style="letter-spacing: .05pt;">m</span>i<span style="letter-spacing: -.15pt;">z</span>ati<span style="letter-spacing: .05pt;">o</span><span style="letter-spacing: -.05pt;">n</span>.<o:p></o:p></span></div>
</div>
<span style="font-family: Trebuchet MS, sans-serif;"><span style="font-size: 15pt; line-height: 115%;"><br clear="all" style="mso-break-type: section-break; page-break-before: always;" /> </span> </span><br />
<div class="MsoNormal" style="margin: 2.85pt -1pt 0.0001pt 5pt;">
<span style="font-family: Trebuchet MS, sans-serif;"><b>PI<span style="letter-spacing: .05pt;"> r</span><span style="letter-spacing: -.05pt;">oun</span>d<span style="letter-spacing: -.05pt;"> </span>4<span style="letter-spacing: -.05pt;"> (</span><span style="letter-spacing: .05pt;">T</span><span style="letter-spacing: -.05pt;">e</span>s<span style="letter-spacing: -.1pt;">t</span><span style="letter-spacing: .05pt;">i</span><span style="letter-spacing: -.05pt;">n</span><span style="letter-spacing: .1pt;">g</span>)</b><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 11.0pt; margin-bottom: .0001pt; margin-bottom: 0cm; margin-left: 0cm; margin-right: 0cm; margin-top: .9pt; mso-line-height-rule: exactly;">
<br /></div>
<div class="MsoNormal" style="margin: 0cm -1pt 0.0001pt 23pt;">
<span style="font-family: Trebuchet MS, sans-serif;"><b>1</b><b>. <span style="letter-spacing: 1.95pt;"> </span></b>Giv<span style="letter-spacing: .05pt;">e</span>n<span style="letter-spacing: -.05pt;"> </span>a<span style="letter-spacing: -.1pt;"> </span>fu<span style="letter-spacing: -.05pt;">n</span>c<span style="letter-spacing: .05pt;"> </span><span style="letter-spacing: -.05pt;">:</span>: i<span style="letter-spacing: -.05pt;">n</span>t<span style="letter-spacing: -.05pt;"> </span><span style="letter-spacing: .05pt;">*</span>str<span style="letter-spacing: -.1pt;">c</span><span style="letter-spacing: -.05pt;">mp</span>(ch<span style="letter-spacing: -.05pt;">a</span>r *<span style="letter-spacing: -.1pt;">s</span><span style="letter-spacing: .05pt;">1</span>,ch<span style="letter-spacing: -.05pt;">a</span>r <span style="letter-spacing: -.1pt;">*</span>s<span style="letter-spacing: .05pt;">2</span><span style="letter-spacing: -.1pt;">)</span>;<o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 114%; margin-bottom: .0001pt; margin-bottom: 0cm; margin-left: 41.0pt; margin-right: 50.05pt; margin-top: 2.05pt;">
<span style="font-family: Trebuchet MS, sans-serif;">Write<span style="letter-spacing: -.05pt;"> </span>t<span style="letter-spacing: .05pt;">e</span><span style="letter-spacing: -.1pt;">s</span>t<span style="letter-spacing: .05pt;"> </span>ca<span style="letter-spacing: -.1pt;">s</span>es<span style="letter-spacing: .05pt;"> </span><span style="letter-spacing: -.1pt;">t</span>o<span style="letter-spacing: -.05pt;"> </span>check <b><span style="letter-spacing: -.15pt;">f</span><span style="letter-spacing: -.05pt;">un</span><span style="letter-spacing: .05pt;">c</span>t<span style="letter-spacing: .05pt;">i</span><span style="letter-spacing: -.05pt;">ona</span><span style="letter-spacing: .05pt;">li</span><span style="letter-spacing: -.1pt;">t</span>y<span style="letter-spacing: .1pt;"> </span></b>a<span style="letter-spacing: -.05pt;">n</span>d<span style="letter-spacing: -.15pt;"> </span><b>s<span style="letter-spacing: -.05pt;">e</span><span style="letter-spacing: .05pt;">c</span><span style="letter-spacing: -.05pt;">u</span><span style="letter-spacing: -.1pt;">r</span><span style="letter-spacing: .05pt;">i</span><span style="letter-spacing: -.1pt;">t</span>y<span style="letter-spacing: .15pt;"> </span></b>i<span style="letter-spacing: -.15pt;">s</span>sues and<span style="letter-spacing: -.05pt;"> e</span><span style="letter-spacing: .05pt;">v</span>en a<span style="letter-spacing: -.15pt;">u</span>t<span style="letter-spacing: -.05pt;">o</span><span style="letter-spacing: .05pt;">m</span>a<span style="letter-spacing: -.1pt;">t</span>e<span style="letter-spacing: .05pt;"> </span>t<span style="letter-spacing: -.15pt;">h</span>e <span style="letter-spacing: -.05pt;">g</span>enerati<span style="letter-spacing: .05pt;">o</span>n<span style="letter-spacing: -.15pt;"> </span><span style="letter-spacing: .05pt;">o</span>f<span style="letter-spacing: -.15pt;"> </span><span style="letter-spacing: .05pt;">t</span>e<span style="letter-spacing: -.1pt;">s</span>t<span style="letter-spacing: .05pt;"> </span>ca<span style="letter-spacing: -.1pt;">s</span>es.<o:p></o:p></span></div>
<div class="MsoNormal" style="margin-bottom: .0001pt; margin-bottom: 0cm; margin-left: 41.0pt; margin-right: 2.95pt; margin-top: .45pt; tab-stops: 114.0pt; text-indent: -18.0pt;">
<span style="font-family: Trebuchet MS, sans-serif;"><b>2</b><b>. <span style="letter-spacing: 1.95pt;"> </span></b>Giv<span style="letter-spacing: .05pt;">e</span>n<span style="letter-spacing: -.05pt;"> </span>a<span style="letter-spacing: -.1pt;"> </span>fu<span style="letter-spacing: -.05pt;">n</span>c<span style="letter-spacing: .05pt;"> </span><span style="letter-spacing: -.05pt;">:</span>: i<span style="letter-spacing: -.05pt;">n</span>t<span style="letter-spacing: .05pt;"> </span><span style="letter-spacing: -.1pt;">t</span><span style="letter-spacing: .05pt;">y</span><span style="letter-spacing: -.05pt;">p</span><span style="letter-spacing: -.1pt;">e</span>O<span style="letter-spacing: -.1pt;">f</span>Tria<span style="letter-spacing: -.05pt;">ng</span>l<span style="letter-spacing: .05pt;">e</span>(i<span style="letter-spacing: -.05pt;">n</span>t<span style="letter-spacing: .05pt;"> </span>si<span style="letter-spacing: -.05pt;">d</span><span style="letter-spacing: -.1pt;">e</span><span style="letter-spacing: .05pt;">1</span>,i<span style="letter-spacing: -.05pt;">n</span>t<span style="letter-spacing: -.05pt;"> </span>si<span style="letter-spacing: -.05pt;">d</span>e<span style="letter-spacing: .05pt;">2</span><span style="letter-spacing: -.1pt;">,</span>i<span style="letter-spacing: -.05pt;">n</span>t<span style="letter-spacing: .05pt;"> </span>si<span style="letter-spacing: -.05pt;">d</span>e<span style="letter-spacing: .15pt;">3</span><span style="letter-spacing: -.1pt;">)</span>;<span style="letter-spacing: .1pt;"> </span>(f<span style="letter-spacing: -.05pt;">un</span>c<span style="letter-spacing: -.1pt;"> </span>gi<span style="letter-spacing: .05pt;">v</span><span style="letter-spacing: -.1pt;">e</span>s<span style="letter-spacing: .05pt;"> </span>a n<span style="letter-spacing: -.2pt;">u</span><span style="letter-spacing: .05pt;">m</span><span style="letter-spacing: -.05pt;">b</span>er<span style="letter-spacing: .05pt;"> </span><span style="letter-spacing: -.15pt;">f</span><span style="letter-spacing: .05pt;">o</span>r<span style="letter-spacing: -.05pt;"> </span>the t<span style="letter-spacing: .05pt;">y</span><span style="letter-spacing: -.05pt;">p</span>e<span style="letter-spacing: -.05pt;"> </span><span style="letter-spacing: .05pt;">o</span>f<span style="letter-spacing: -.1pt;"> </span>tria<span style="letter-spacing: -.05pt;">ng</span>l<span style="letter-spacing: .05pt;">e</span>)<o:p></o:p></span></div>
<div class="MsoNormal" style="margin-bottom: .0001pt; margin-bottom: 0cm; margin-left: 41.0pt; margin-right: 50.05pt; margin-top: .25pt;">
<span style="font-family: Trebuchet MS, sans-serif;">Write<span style="letter-spacing: -.05pt;"> </span>t<span style="letter-spacing: .05pt;">e</span><span style="letter-spacing: -.1pt;">s</span>t<span style="letter-spacing: .05pt;"> </span>ca<span style="letter-spacing: -.1pt;">s</span>es<span style="letter-spacing: .05pt;"> </span><span style="letter-spacing: -.1pt;">t</span>o<span style="letter-spacing: -.05pt;"> </span>check <b><span style="letter-spacing: -.15pt;">f</span><span style="letter-spacing: -.05pt;">un</span><span style="letter-spacing: .05pt;">c</span>t<span style="letter-spacing: .05pt;">i</span><span style="letter-spacing: -.05pt;">ona</span><span style="letter-spacing: .05pt;">li</span><span style="letter-spacing: -.1pt;">t</span>y<span style="letter-spacing: .1pt;"> </span></b>a<span style="letter-spacing: -.05pt;">n</span>d<span style="letter-spacing: -.15pt;"> </span><b>s<span style="letter-spacing: -.05pt;">e</span><span style="letter-spacing: .05pt;">c</span><span style="letter-spacing: -.05pt;">u</span><span style="letter-spacing: -.1pt;">r</span><span style="letter-spacing: .05pt;">i</span><span style="letter-spacing: -.1pt;">t</span>y<span style="letter-spacing: .15pt;"> </span></b>i<span style="letter-spacing: -.15pt;">s</span>sues and<span style="letter-spacing: -.05pt;"> e</span><span style="letter-spacing: .05pt;">v</span>en a<span style="letter-spacing: -.15pt;">u</span>t<span style="letter-spacing: -.05pt;">o</span><span style="letter-spacing: .05pt;">m</span>a<span style="letter-spacing: -.1pt;">t</span>e<span style="letter-spacing: .05pt;"> </span>t<span style="letter-spacing: -.15pt;">h</span>e <span style="letter-spacing: -.05pt;">g</span>enerati<span style="letter-spacing: .05pt;">o</span>n<span style="letter-spacing: -.15pt;"> </span><span style="letter-spacing: .05pt;">o</span>f<span style="letter-spacing: -.15pt;"> </span><span style="letter-spacing: .05pt;">t</span>e<span style="letter-spacing: -.1pt;">s</span>t<span style="letter-spacing: .05pt;"> </span>ca<span style="letter-spacing: -.1pt;">s</span>es.<o:p></o:p></span></div>
<div class="MsoNormal" style="margin: 0.35pt -1pt 0.0001pt 23pt;">
<span style="font-family: Trebuchet MS, sans-serif;"><b>3</b><b>. <span style="letter-spacing: 1.95pt;"> </span></b>WAP<span style="letter-spacing: -.05pt;"> </span>to<span style="letter-spacing: -.05pt;"> </span>r<span style="letter-spacing: -.1pt;">e</span><span style="letter-spacing: .05pt;">v</span>er<span style="letter-spacing: -.1pt;">s</span>e<span style="letter-spacing: 2.5pt;"> </span>w<span style="letter-spacing: .1pt;">o</span>r<span style="letter-spacing: -.05pt;">d</span>s in<span style="letter-spacing: -.15pt;"> </span>a<span style="letter-spacing: -.1pt;"> </span>s<span style="letter-spacing: .05pt;">e</span><span style="letter-spacing: -.05pt;">n</span>t<span style="letter-spacing: .05pt;">e</span><span style="letter-spacing: -.05pt;">n</span><span style="letter-spacing: -.1pt;">c</span>e.<o:p></o:p></span></div>
<div class="MsoNormal" style="margin: 1.9pt -1pt 0.0001pt 41pt;">
<span style="font-family: Trebuchet MS, sans-serif;">I am<span style="letter-spacing: .05pt;"> </span>a<span style="letter-spacing: -.05pt;"> go</span><span style="letter-spacing: .05pt;">o</span>d <span style="letter-spacing: -.05pt;">bo</span>y<span style="letter-spacing: .05pt;"> </span>-><span style="letter-spacing: -.05pt;"> bo</span>y<span style="letter-spacing: .05pt;"> </span><span style="letter-spacing: -.15pt;">g</span><span style="letter-spacing: .05pt;">o</span><span style="letter-spacing: -.05pt;">o</span>d<span style="letter-spacing: -.05pt;"> </span>a<span style="letter-spacing: .05pt;"> </span>am<span style="letter-spacing: -.05pt;"> </span>i<o:p></o:p></span></div>
<div class="MsoNormal" style="margin: 2.05pt -1pt 0.0001pt 23pt;">
<span style="font-family: Trebuchet MS, sans-serif;"><b>4</b><b>. <span style="letter-spacing: 1.95pt;"> </span></b>WAP<span style="letter-spacing: -.05pt;"> </span>to<span style="letter-spacing: -.05pt;"> </span>get<span style="letter-spacing: -.05pt;"> </span>the n<span style="letter-spacing: -.1pt;">e</span>xt<span style="letter-spacing: .05pt;"> </span>hi<span style="letter-spacing: -.05pt;">gh</span>er<span style="letter-spacing: -.1pt;"> </span>pa<span style="letter-spacing: -.05pt;">l</span>i<span style="letter-spacing: -.05pt;">nd</span>r<span style="letter-spacing: .05pt;">o</span><span style="letter-spacing: -.05pt;">m</span>e<span style="letter-spacing: -.05pt;"> </span><span style="letter-spacing: .05pt;">o</span>f a<span style="letter-spacing: .05pt;"> </span><span style="letter-spacing: -.05pt;">g</span><span style="letter-spacing: -.15pt;">i</span><span style="letter-spacing: .05pt;">v</span>en n<span style="letter-spacing: -.2pt;">u</span><span style="letter-spacing: -.05pt;">mb</span>er.<o:p></o:p></span></div>
<div class="MsoNormal" style="margin: 2.05pt -1pt 0.0001pt 41pt;">
<span style="font-family: Trebuchet MS, sans-serif;"><span style="letter-spacing: .05pt; mso-ascii-font-family: Calibri; mso-bidi-font-family: Calibri; mso-fareast-font-family: Calibri; mso-hansi-font-family: Calibri;">1</span><span style="letter-spacing: -.1pt; mso-ascii-font-family: Calibri; mso-bidi-font-family: Calibri; mso-fareast-font-family: Calibri; mso-hansi-font-family: Calibri;">2</span>3<span style="letter-spacing: .1pt;"> </span>-><span style="letter-spacing: -.05pt;"> </span><span style="letter-spacing: -.1pt;">1</span><span style="letter-spacing: .05pt;">3</span>1 <span style="letter-spacing: -.1pt;">12</span><span style="letter-spacing: .05pt;">3</span>2<span style="letter-spacing: .15pt;"> </span><span style="letter-spacing: -.15pt;">-</span>><span style="letter-spacing: -.05pt;"> </span><span style="letter-spacing: .05pt;">1</span><span style="letter-spacing: -.1pt;">3</span><span style="letter-spacing: .05pt;">3</span>1<o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 7.0pt; margin-bottom: .0001pt; margin-bottom: 0cm; margin-left: 0cm; margin-right: 0cm; margin-top: .45pt; mso-line-height-rule: exactly;">
<br /></div>
<div class="MsoNormal" style="line-height: 10.0pt; margin-bottom: .0001pt; margin-bottom: 0cm; mso-line-height-rule: exactly;">
<br /></div>
<div class="MsoNormal" style="line-height: 115%; margin-bottom: .0001pt; margin-bottom: 0cm; margin-left: 41.0pt; margin-right: 2.45pt; margin-top: 0cm;">
<span style="font-family: Trebuchet MS, sans-serif;"><span style="letter-spacing: .05pt; mso-ascii-font-family: Calibri; mso-bidi-font-family: Calibri; mso-fareast-font-family: Calibri; mso-hansi-font-family: Calibri;">P</span>S - <span style="letter-spacing: .05pt;"> </span>F<span style="letter-spacing: -.1pt;">u</span><span style="letter-spacing: -.05pt;">n</span>ct<span style="letter-spacing: -.1pt;">i</span><span style="letter-spacing: .05pt;">o</span><span style="letter-spacing: -.05pt;">n</span>al iss<span style="letter-spacing: -.15pt;">u</span><span style="letter-spacing: .05pt;">e</span>s<span style="letter-spacing: .05pt;"> </span>a<span style="letter-spacing: -.15pt;">r</span>e<span style="letter-spacing: .05pt;"> </span><span style="letter-spacing: -.1pt;">t</span>est<span style="letter-spacing: .05pt;"> </span>c<span style="letter-spacing: -.15pt;">a</span>ses<span style="letter-spacing: -.05pt;"> </span>that c<span style="letter-spacing: -.15pt;">h</span>eck<span style="letter-spacing: -.05pt;"> </span>the f<span style="letter-spacing: -.15pt;">u</span><span style="letter-spacing: -.05pt;">n</span>cti<span style="letter-spacing: .05pt;">o</span><span style="letter-spacing: -.05pt;">n</span>al<span style="letter-spacing: -.05pt;">i</span><span style="letter-spacing: -.1pt;">t</span>y<span style="letter-spacing: -.05pt;"> </span><span style="letter-spacing: .05pt;">o</span>f <span style="letter-spacing: .05pt;">t</span><span style="letter-spacing: -.05pt;">h</span>e<span style="letter-spacing: -.1pt;"> </span>pro<span style="letter-spacing: -.05pt;">g</span>r<span style="letter-spacing: -.15pt;">a</span>m<span style="letter-spacing: -.05pt;"> </span>a<span style="letter-spacing: -.05pt;">n</span>d<span style="letter-spacing: -.05pt;"> </span>Secur<span style="letter-spacing: -.05pt;">i</span>ty iss<span style="letter-spacing: -.05pt;">u</span>es<span style="letter-spacing: .05pt;"> </span>are<span style="letter-spacing: -.1pt;"> </span><span style="letter-spacing: .05pt;">t</span><span style="letter-spacing: -.05pt;">h</span>e<span style="letter-spacing: -.05pt;"> </span><span style="letter-spacing: .05pt;">o</span><span style="letter-spacing: -.05pt;">n</span>es<span style="letter-spacing: -.1pt;"> </span><span style="letter-spacing: .05pt;">w</span><span style="letter-spacing: -.05pt;">h</span><span style="letter-spacing: -.1pt;">e</span>re<span style="letter-spacing: .1pt;"> </span><span style="letter-spacing: -.1pt;">t</span><span style="letter-spacing: -.05pt;">h</span>e<span style="letter-spacing: .05pt;"> </span><span style="letter-spacing: -.05pt;">p</span>r<span style="letter-spacing: .05pt;">o</span><span style="letter-spacing: -.05pt;">g</span>r<span style="letter-spacing: -.15pt;">a</span>m<span style="letter-spacing: -.05pt;"> </span><span style="letter-spacing: .05pt;">m</span>ay<span style="letter-spacing: -.1pt;"> </span>cras<span style="letter-spacing: -.05pt;">h</span>.<o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 10.0pt; margin-bottom: .0001pt; margin-bottom: 0cm; margin-left: 0cm; margin-right: 0cm; margin-top: .25pt; mso-line-height-rule: exactly;">
<br /></div>
<div class="MsoNormal" style="margin: 0cm -1pt 0.0001pt 5pt;">
<span style="font-family: Trebuchet MS, sans-serif;"><b>PI<span style="letter-spacing: .05pt;"> r</span><span style="letter-spacing: -.05pt;">oun</span>d 5<span style="letter-spacing: -.05pt;"> </span><span style="letter-spacing: -.1pt;">(</span><span style="letter-spacing: .05pt;">T</span><span style="letter-spacing: -.05pt;">e</span><span style="letter-spacing: .05pt;">c</span><span style="letter-spacing: -.05pt;">hni</span><span style="letter-spacing: .05pt;">c</span><span style="letter-spacing: -.05pt;">al</span>)</b><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 11.0pt; margin-bottom: .0001pt; margin-bottom: 0cm; margin-left: 0cm; margin-right: 0cm; margin-top: .9pt; mso-line-height-rule: exactly;">
<br /></div>
<div class="MsoNormal" style="margin: 0cm -1pt 0.0001pt 23pt;">
<span style="font-family: Trebuchet MS, sans-serif;"><span style="letter-spacing: .05pt; mso-ascii-font-family: Calibri; mso-bidi-font-family: Calibri; mso-fareast-font-family: Calibri; mso-hansi-font-family: Calibri;">1</span>. <span style="letter-spacing: 2.1pt;"> </span>WAP<span style="letter-spacing: -.05pt;"> </span>to<span style="letter-spacing: -.05pt;"> </span>c<span style="letter-spacing: -.05pt;">h</span>e<span style="letter-spacing: -.1pt;">c</span>k<span style="letter-spacing: .05pt;"> </span>if a b<span style="letter-spacing: -.05pt;">in</span>a<span style="letter-spacing: -.15pt;">r</span>y<span style="letter-spacing: .05pt;"> t</span><span style="letter-spacing: -.15pt;">r</span>ee<span style="letter-spacing: .05pt;"> </span>is<span style="letter-spacing: -.1pt;"> </span>a BST<span style="letter-spacing: -.1pt;"> </span><span style="letter-spacing: .05pt;">o</span>r <span style="letter-spacing: -.15pt;">n</span><span style="letter-spacing: .05pt;">o</span>t.<o:p></o:p></span></div>
<div class="MsoNormal" style="margin: 2.05pt -1pt 0.0001pt 23pt;">
<span style="font-family: Trebuchet MS, sans-serif;"><span style="letter-spacing: .05pt; mso-ascii-font-family: Calibri; mso-bidi-font-family: Calibri; mso-fareast-font-family: Calibri; mso-hansi-font-family: Calibri;">2</span>. <span style="letter-spacing: 2.1pt;"> </span>WAP<span style="letter-spacing: -.05pt;"> </span>to<span style="letter-spacing: -.05pt;"> </span>fi<span style="letter-spacing: -.05pt;">n</span>d<span style="letter-spacing: -.05pt;"> </span><span style="letter-spacing: .05pt;">L</span>e<span style="letter-spacing: -.1pt;">a</span>st<span style="letter-spacing: .05pt;"> </span><span style="letter-spacing: -.1pt;">C</span><span style="letter-spacing: -.05pt;">o</span><span style="letter-spacing: .05pt;">m</span><span style="letter-spacing: -.05pt;">mo</span>n<span style="letter-spacing: .05pt;"> </span>A<span style="letter-spacing: -.05pt;">n</span>ce<span style="letter-spacing: .05pt;">s</span><span style="letter-spacing: -.1pt;">t</span><span style="letter-spacing: .05pt;">o</span>r<span style="letter-spacing: -.1pt;"> </span><span style="letter-spacing: .05pt;">o</span>f <span style="letter-spacing: -.1pt;">t</span>wo <span style="letter-spacing: -.05pt;">n</span><span style="letter-spacing: .05pt;">o</span><span style="letter-spacing: -.05pt;">d</span>es<span style="letter-spacing: -.1pt;"> </span>in<span style="letter-spacing: -.1pt;"> </span>a BST.<o:p></o:p></span></div>
<div class="MsoNormal" style="margin: 2.05pt -1pt 0.0001pt 23pt;">
<span style="font-family: Trebuchet MS, sans-serif;"><span style="letter-spacing: .05pt; mso-ascii-font-family: Calibri; mso-bidi-font-family: Calibri; mso-fareast-font-family: Calibri; mso-hansi-font-family: Calibri;">3</span>. <span style="letter-spacing: 2.1pt;"> </span>Re<span style="letter-spacing: -.05pt;">v</span>erse<span style="letter-spacing: -.05pt;"> </span>e<span style="letter-spacing: -.05pt;">v</span>ery<span style="letter-spacing: -.05pt;"> </span><span style="letter-spacing: .05pt;">t</span><span style="letter-spacing: -.1pt;">w</span>o<span style="letter-spacing: .05pt;"> </span><span style="letter-spacing: -.15pt;">n</span><span style="letter-spacing: .05pt;">o</span><span style="letter-spacing: -.05pt;">d</span>es<span style="letter-spacing: .05pt;"> </span><span style="letter-spacing: -.15pt;">i</span>n<span style="letter-spacing: -.05pt;"> </span>a<span style="letter-spacing: .05pt;"> </span>li<span style="letter-spacing: -.05pt;">n</span>k<span style="letter-spacing: .05pt;">e</span>d<span style="letter-spacing: -.05pt;"> </span>i<span style="letter-spacing: -.1pt;">t</span>erat<span style="letter-spacing: -.1pt;">i</span><span style="letter-spacing: .05pt;">v</span>e<span style="letter-spacing: -.1pt;">l</span>y<span style="letter-spacing: .05pt;"> </span>and<span style="letter-spacing: -.05pt;"> </span>r<span style="letter-spacing: -.1pt;">e</span>cu<span style="letter-spacing: -.05pt;">r</span>si<span style="letter-spacing: .05pt;">v</span>e<span style="letter-spacing: -.1pt;">l</span><span style="letter-spacing: .05pt;">y</span>.</span></div>
</div>
Arvind Mohanhttp://www.blogger.com/profile/09421036756092622107noreply@blogger.com0tag:blogger.com,1999:blog-7173134778831375674.post-8408186069164887592012-08-31T12:59:00.001+05:302012-10-13T17:20:45.128+05:30Blog # 90 : Flipkart Interview Questions 2013 Batch<div dir="ltr" style="text-align: left;" trbidi="on">
<u style="background-color: white; color: #333333; font-family: 'trebuchet ms', sans-serif; font-size: 13px;">Round 1</u><br />
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">Write a code to check if a tree is BST or not.</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">Modify this code to find the maximum subtree in tree which is a BST. Maximum subtree means subtree goes upto its leaves from any node.</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">Modify the code again to find the maximum tree which is a BST. BST can lie anywhere and it may or may not go upto its leaves.</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;"><br />
</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;"><u>Round 2</u></span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">1. There is code like</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">var i;</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">{</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;"> ..</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;"> var j;</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;"> ..</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">}</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">var k;</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">..</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">var a;</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">{</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;"> ..</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;"> var c;</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;"> {</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;"> var i;</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;"> }</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;"> ..</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;"> var d;</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;"> ..</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">}</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">For simplicity you may assume that there is only one variable declaration on 1 line. Now given a line number, you have to tell what all variables are valid on that line. Propose an algorithm for this.</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;"><br />
</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">2. Implement LRU cache. Write a code for this. LRU cache supports 3 operations,</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">put(key, value)</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">get(key)</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">remove(key)</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">P.S. This is very important and actually good question. Even if you know the answer, dont rush with it. Take your time to frame the algorithm. Always speak your thoughts. Interviewers like to know the way you are thinking in.</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;"><br />
</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;"><u>Round 3</u></span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">1. Implement next_permutation function (similar to what is in algorithm.h).</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">2. Given n sequences, and starting and stopping point of every sequence with its score. For eg.</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">no of sequences = 5</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">start stop score</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">0 4 4</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">3 10 11</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">6 8 8</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">7 15 10</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">11 15 4</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">All scores are positive. You have to find the maximum subset of non overlapping sequences having maximum total sum of scores. I proposed a n^2 approach first and then modified it to nlgn.</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">3. Normal discussion on work culture, teams etc.</span></span></div>
</div>
Arvind Mohanhttp://www.blogger.com/profile/09421036756092622107noreply@blogger.com1tag:blogger.com,1999:blog-7173134778831375674.post-1918498388756557092012-08-31T12:30:00.000+05:302012-10-13T17:20:33.854+05:30Blog # 89 : Anshu Kumar : Amazon, Flipkart, Adobe<div dir="ltr" style="text-align: left;" trbidi="on">
<br />
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">I am not an interview expert, but from my experience I found that it is really very helpful to speak up your thoughts. This shows interviewer the direction of your approach. Even if you reject your thought, the interviewer will know that. Speak everything. Also at the end of every round, they will ask if you have any question to ask. Never let this opportunity going waste. Prepare you with some questions like "What are the various teams in the company?" "How are they related?" or questions about working environment etc.. These type of question give you chance to communicate with the interviewer and he will get an impression that this guy wants to know about the company and work. Prepare general questions which can work for all companies.</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;"><br />
</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">All the best for your placements. :)</span></span></div>
</div>
Arvind Mohanhttp://www.blogger.com/profile/09421036756092622107noreply@blogger.com0tag:blogger.com,1999:blog-7173134778831375674.post-53625697450436846422012-08-31T11:59:00.001+05:302012-10-13T17:20:21.596+05:30Blog # 88 : Adobe Interview Questions 2013 Batch<div dir="ltr" style="text-align: left;" trbidi="on">
<u style="background-color: white; color: #333333; font-family: 'trebuchet ms', sans-serif; font-size: 13px;">Round 1</u><br />
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">1. How will you implement a stack using a priority queue. Push and pop should be in O(1).</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">2. 3 mislabeled jars problem.</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;"><br />
</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;"><u>Round 2</u></span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">1. How does stack look in function calls? Given a recursive function call, how will the stack look like?</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">2. When does stack(process stack) overflow? What are the remedies?</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">3. What are balanced BST's. Then he randomly gave me various numbers and asked me to create a BST. And the balance it.</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">4. Advantages of linked list over arrays. And arrays over linked list.</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">5. How are vectors implemented internally in the library. This question revolved around dynamic implementation of arrays. Then discussed the amortized time of the operations using dynamic implementation of arrays.</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;"><br />
</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;"><u>Round 3</u></span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">1. There was a question in written round that there is a global static variable 'lock' initially set to 0 and there was a code segment given.</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;"><br />
</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">while(lock);</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">lock = 1;</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">//Critical section</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">lock = 0;</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;"><br />
</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">Does this solve critical section problem. I answered that it will solve in uni processor system but not in multiprocessor system. Then he asked me to explain my answer. After a long discussion we came to a conclusion that this wont even solve in uni processor system. </span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">Then he asked me the solution to solve this. I did that using testandset instruction. </span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;"><br />
</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">2. When a function is called in thread, what variables can be accessed from it. There was a long discussion on this too. I went in the wrong direction but corrected myself later. Stack variables are copied but heap variables are same.</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;"><br />
</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;"><u>Round 4</u></span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">1. What data structures will you use to implement a text editor. Size of editor can be changed and you also need to save the styling information for all the text like italic, bold etc.</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;"><br />
</span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;"><u>Round 5</u></span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;"><u>HR Round</u></span></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="color: #333333;"><span style="font-family: trebuchet ms,sans-serif;">Normal HR questions</span></span></div>
</div>
Arvind Mohanhttp://www.blogger.com/profile/09421036756092622107noreply@blogger.com0tag:blogger.com,1999:blog-7173134778831375674.post-35973964163674160232012-08-25T10:07:00.000+05:302012-08-25T10:07:00.538+05:30Blog # 87 : Amazon Interview Questions 2013<div dir="ltr" style="text-align: left;" trbidi="on"><br />
<div class="MsoNormal" style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13.333333969116211px;"><b>Written Test (Time): 90 Minutes</b></div><div class="MsoNormal" style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13.333333969116211px;">20 Objective Questions: Aptitude and basic C objective problems.</div><div class="MsoNormal" style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13.333333969116211px;">2 Subjective Questions:</div><div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13.333333969116211px; margin-left: 54pt;">I.<span style="font-family: 'Times New Roman'; font-size: 7pt;"> </span>To find if there is any root to leaf path with specified sum in a binary tree.</div><div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13.333333969116211px; margin-left: 54pt;">II.<span style="font-family: 'Times New Roman'; font-size: 7pt;"> </span>Some question based on sorting.</div><div class="MsoNormal" style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13.333333969116211px;"><br />
</div><div class="MsoNormal" style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13.333333969116211px;"><b>Interview Round 1(60-70 Minutes):</b></div><div class="MsoNormal" style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13.333333969116211px;">Technical Interview</div><div class="MsoNormal" style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13.333333969116211px;"><b>Question 1:</b> Check if a character link list is palindrome or not.</div><div class="MsoNormal" style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13.333333969116211px;"><b>Question 2:</b> A sorted array has been rotated r times to the left. Find r in least possible time.</div><div class="MsoNormal" style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13.333333969116211px;"><b>Question 3:</b> Clone a singly link list whose nodes contain, apart from next pointers, an extra pointer to any random node. The random pointer of a node N could be after N, before N or the node N itself.</div><div class="MsoNormal" style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13.333333969116211px;"><br />
</div><div class="MsoNormal" style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13.333333969116211px;"><b>Interview Round 2(50-60 Minutes):</b></div><div class="MsoNormal" style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13.333333969116211px;">Technical Interview</div><div class="MsoNormal" style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13.333333969116211px;"><b>Question 1:</b> There is a big file of words which is dynamically changing. We are continuously adding some words into it. How would you keep track of top 10 trending words at each moment?</div><div class="MsoNormal" style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13.333333969116211px;"><b>Question 2:</b> Write code for minHeapify() operation.</div><div class="MsoNormal" style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13.333333969116211px;"><b>Question 3:</b> Design a data structure for the following operations:</div><div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13.333333969116211px; margin-left: 54pt;">I.<span style="font-family: 'Times New Roman'; font-size: 7pt;"> </span>Enqueue</div><div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13.333333969116211px; margin-left: 54pt;">II.<span style="font-family: 'Times New Roman'; font-size: 7pt;"> </span>Dequeue</div><div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13.333333969116211px; margin-left: 54pt;">III.<span style="font-family: 'Times New Roman'; font-size: 7pt;"> </span>Delete a given number(if it is present in the queue, else do nothing)</div><div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13.333333969116211px; margin-left: 54pt;">IV.<span style="font-family: 'Times New Roman'; font-size: 7pt;"> </span>isNumberPresent</div><div class="MsoNormal" style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13.333333969116211px;">All these operations should take O(1) time.</div><div class="MsoNormal" style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13.333333969116211px;"><b>Question 4:</b> Write a function that returns the length of the longest leaf-to-leaf path in a binary tree.</div><div class="MsoNormal" style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13.333333969116211px;"><br />
</div><div class="MsoNormal" style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13.333333969116211px;"><b>Interview Round 3(60-70 Minutes):</b></div><div class="MsoNormal" style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13.333333969116211px;">Technical Interview</div><div class="MsoNormal" style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13.333333969116211px;"><b>Question 1:</b> There is a binary tree of size N. All nodes are numbered between 1-N(inclusive). There is a N*N integer matrix Arr[N][N], all elements are initialized to zero. So for all the nodes A and B, put Arr[A][B] = 1 if A is an ancestor of B (<b>NOT</b> just the immediate ancestor).</div><div class="MsoNormal" style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13.333333969116211px;"><b>Question 2:</b> Find an element in a sorted rotated integer array.</div><div class="MsoNormal" style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13.333333969116211px;"><b>Question 3:</b> There is a N*N integer matrix Arr[N][N]. From the row r and column c, we can go to any of the following three indices:</div><div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13.333333969116211px; margin-left: 54pt;">I.<span style="font-family: 'Times New Roman'; font-size: 7pt;"> </span>Arr[r+1][c-1] (valid only if c-1>=0)</div><div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13.333333969116211px; margin-left: 54pt;">II.<span style="font-family: 'Times New Roman'; font-size: 7pt;"> </span>Arr[r+1][c]</div><div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13.333333969116211px; margin-left: 54pt;">III.<span style="font-family: 'Times New Roman'; font-size: 7pt;"> </span>Arr[r+1][c+1] (valid only if c+1<=N-1)</div><div class="MsoNormal" style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13.333333969116211px;">So if we start at any column index on row 0, what is the largest sum of any of the paths till row N-1.</div><div class="MsoNormal" style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13.333333969116211px;"><br />
</div><div class="MsoNormal" style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13.333333969116211px;"><b>Interview Round 4(40-50 Minutes):</b></div><div class="MsoNormal" style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13.333333969116211px;">Bar Raiser Round</div><div class="MsoNormal" style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13.333333969116211px;">Interviewer asked HR Questions Initially, then a sort of puzzle.</div><div class="MsoNormal" style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13.333333969116211px;">Two robots land with their parachutes on an infinite one-dimensional number line. They both release their parachutes as soon as they land and start moving. They are allowed only to make use of the following functions.</div><div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13.333333969116211px; margin-left: 54pt;">I.<span style="font-family: 'Times New Roman'; font-size: 7pt;"> </span>moveLeft() // robot moves to left by 1 unit in 1 unit time</div><div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13.333333969116211px; margin-left: 54pt;">II.<span style="font-family: 'Times New Roman'; font-size: 7pt;"> </span>moveRight() // robot moves to right by 1 unit in 1 unit time</div><div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13.333333969116211px; margin-left: 54pt;">III.<span style="font-family: 'Times New Roman'; font-size: 7pt;"> </span>noOperation() // robot does not move and takes 1 unit time</div><div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13.333333969116211px; margin-left: 54pt;">IV.<span style="font-family: 'Times New Roman'; font-size: 7pt;"> </span>onTopOfParachute() // returns true if the robot is standing on top of either of the parachute, else false</div><div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13.333333969116211px; margin-left: 54pt;">V.<span style="font-family: 'Times New Roman'; font-size: 7pt;"> </span>didWeMeet() // returns true if the robot meets to the other robot, else false</div><div class="MsoNormal" style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13.333333969116211px;">Write a function in order to make the robots meet each other. Robots will be executing the same copy of this function.</div><div class="MsoNormal" style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13.333333969116211px;"><br />
</div><div class="MsoNormal" style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13.333333969116211px;"><b>Tips / Advice:</b></div><div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13.333333969116211px; margin-left: 54pt;">I.<span style="font-family: 'Times New Roman'; font-size: 7pt;"> </span>Each time you write a code, check for the edge cases.</div><div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13.333333969116211px; margin-left: 54pt; text-align: left;">II.<span style="font-family: 'Times New Roman'; font-size: 7pt;"> </span>Do not assume anything. Keep asking questions if there are any doubts.</div><br />
<span style="font-family: Trebuchet MS, sans-serif;">Courtesy: A selected sincere candidate</span></div>Arvind Mohanhttp://www.blogger.com/profile/09421036756092622107noreply@blogger.com1tag:blogger.com,1999:blog-7173134778831375674.post-17811274988486357962012-07-27T12:03:00.000+05:302012-07-27T12:03:00.555+05:30Blog # 86 : How to find Avg. Salary? Help them!<div dir="ltr" style="text-align: left;" trbidi="on"><br />
<div dir="ltr" style="text-align: left;" trbidi="on"><script language="javascript">
function show(targetID) {
target = document.getElementById(targetID);
if (target.style.display == "none")
{ target.style.display = ""; }
}
function hide(targetID) {
target = document.getElementById(targetID);
target.style.display = "none";
}
function toggle(targetID) {
remark = document.getElementById(targetID + '_remark');
hint = document.getElementById(targetID + '_hint');
solution = document.getElementById(targetID + '_solution');
if (remark.style.display == "none" ) {
remark.style.display = "";
}
else if (hint.style.display == "none" ) {
hint.style.display = ""; return;
}
else if (solution.style.display == "none" ) {
solution.style.display = ""; return;
}
else {
remark.style.display = "none";
hint.style.display = "none";
solution.style.display = "none";
}
}
</script><br />
<div dir="ltr" style="text-align: left;" trbidi="on"><div style="font-family: "Trebuchet MS",sans-serif;"><table cellpadding="8" cellspacing="0" style="font-family: "Trebuchet MS",sans-serif;"><tbody>
<tr> <td valign="top"><div align="justify"><span style="font-size: small;">Five coworkers want to know what the average of all their salaries is, but refuse to reveal ANY information about their own salaries to their coworkers. How can they calculate the average ?</span><br />
<span style="font-size: small;"><br />
</span><br />
<span style="font-size: small;">courtesy: Vibhaj </span></div><div align="justify"><br />
<span style="font-size: small;">Click <a href="javascript:%20toggle('86');"><b>here</b></a> to see the solution.<br />
p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice.</span></div><br />
<div class="remark" id="86_remark" style="display: none;"><br />
<br />
<br />
<br />
<br />
<center><br />
<table><tbody>
<tr><td><table bgcolor="white" border="0" cellpadding="5" cellspacing="0" class="bodyline"><tbody>
<tr><td><div align="justify"><b><span style="font-size: small;">Remarks:</span></b> </div><span style="font-size: small;">What you'd do if such thing happens in your life? Hit again for hints.</span></td></tr>
</tbody></table><table border="0" cellpadding="0" cellspacing="0" class="tbl"><tbody>
<tr> </tr>
</tbody></table></td></tr>
</tbody></table></center></div><div class="hint" id="86_hint" style="display: none;"><br />
<br />
<br />
<br />
<br />
<br />
<br />
<center><br />
<table><tbody>
<tr><td><table bgcolor="white" border="0" cellpadding="5" cellspacing="0" class="bodyline"><tbody>
<tr><td><div align="justify"><b><span style="font-size: small;"> Hints:</span></b></div><span style="font-size: small;">No Hints. Hit again for solution.</span></td></tr>
</tbody></table><table border="0" cellpadding="0" cellspacing="0" class="tbl"><tbody>
<tr> </tr>
</tbody></table></td></tr>
</tbody></table></center></div><div class="solution" id="86_solution" style="display: none;"><br />
<br />
<br />
<br />
<br />
<br />
<center><br />
<table><tbody>
<tr><td><table bgcolor="white" border="0" cellpadding="5" cellspacing="0" class="bodyline"><tbody>
<tr><td><div align="justify"><b><span style="font-size: small;">Solution:</span></b></div><span style="font-size: small;"><br />
One of them may choose any random number (not to be known any other) and add his salary to it and tell the sum to the second person, then he will add his salary to the sum and tell the result to the third person and so on. The fifth person after adding his salary to the sum will tell it to the first person. He will subtract the random number he choose from the final sum giving them the sum of their salaries and the average.</span></td></tr>
</tbody></table></td></tr>
</tbody></table></center></div></td> </tr>
</tbody></table></div></div></div></div>Arvind Mohanhttp://www.blogger.com/profile/09421036756092622107noreply@blogger.com0tag:blogger.com,1999:blog-7173134778831375674.post-30978705207419541402012-07-27T08:53:00.000+05:302012-07-27T08:53:00.531+05:30Blog # 85 : Largest 100 from files<div dir="ltr" style="text-align: left;" trbidi="on"><script language="javascript">
function show(targetID) {
target = document.getElementById(targetID);
if (target.style.display == "none")
{ target.style.display = ""; }
}
function hide(targetID) {
target = document.getElementById(targetID);
target.style.display = "none";
}
function toggle(targetID) {
remark = document.getElementById(targetID + '_remark');
hint = document.getElementById(targetID + '_hint');
solution = document.getElementById(targetID + '_solution');
if (remark.style.display == "none" ) {
remark.style.display = "";
}
else if (hint.style.display == "none" ) {
hint.style.display = ""; return;
}
else if (solution.style.display == "none" ) {
solution.style.display = ""; return;
}
else {
remark.style.display = "none";
hint.style.display = "none";
solution.style.display = "none";
}
}
</script><br />
<div dir="ltr" style="text-align: left;" trbidi="on"><div style="font-family: "Trebuchet MS",sans-serif;"><table cellpadding="8" cellspacing="0" style="font-family: "Trebuchet MS",sans-serif;"><tbody>
<tr> <td valign="top"><div align="justify"><span style="font-size: small;">There is a big file containing 10^8 integers, one per line. Devise an algorithm to find the largest 100 integers among them. Remember you cannot read all of them into memory at once.</span><br />
<span style="font-size: small;"><br />
</span><br />
<span style="font-size: small;">courtesy: Vibhaj </span></div><div align="justify"><br />
<span style="font-size: small;">Click <a href="javascript:%20toggle('85');"><b>here</b></a> to see the solution.<br />
p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice.</span></div><br />
<div class="remark" id="85_remark" style="display: none;"><br />
<br />
<br />
<br />
<center><br />
<table><tbody>
<tr><td><table bgcolor="white" border="0" cellpadding="5" cellspacing="0" class="bodyline"><tbody>
<tr><td><div align="justify"><b><span style="font-size: small;">Remarks:</span></b> </div><span style="font-size: small;">No remarks. Hit again for hints.</span></td></tr>
</tbody></table><table border="0" cellpadding="0" cellspacing="0" class="tbl"><tbody>
<tr> </tr>
</tbody></table></td></tr>
</tbody></table></center></div><div class="hint" id="85_hint" style="display: none;"><br />
<br />
<br />
<br />
<center><br />
<table><tbody>
<tr><td><table bgcolor="white" border="0" cellpadding="5" cellspacing="0" class="bodyline"><tbody>
<tr><td><div align="justify"><b><span style="font-size: small;"> Hints:</span></b></div><span style="font-size: small;">Value stored in any element of the Array reaches a maxima at certain index.</span></td></tr>
</tbody></table><table border="0" cellpadding="0" cellspacing="0" class="tbl"><tbody>
<tr> </tr>
</tbody></table></td></tr>
</tbody></table></center></div><div class="solution" id="85_solution" style="display: none;"><br />
<br />
<br />
<br />
<br />
<center><br />
<table><tbody>
<tr><td><table bgcolor="white" border="0" cellpadding="5" cellspacing="0" class="bodyline"><tbody>
<tr><td><div align="justify"><b><span style="font-size: small;">Solution:</span></b></div><span style="font-size: small;"><br />
We simply use Min-Heap data structure to keep list of top 100 numbers replacing next with lowest if greater.<br />
<b>Complexity:</b><br />
1. Time: O(N*logN)<br />
2. Space: O(1)<br />
</span><br />
<br />
<pre class="cpp" name="code">/**
* Assume standard heap ADT operations : heap_min(), heap_remove() and heap_insert()
**/
void top_100(FILE *fp, int output[]){
int num, count=0;
while(fscanf(fp, "%d\n", &num)){
if(++count > 100 && num > heap_min(output)){
heap_remove(output);
}
heap_insert(output, num);
}
}
</pre></td></tr>
</tbody></table></td></tr>
</tbody></table></center></div></td> </tr>
</tbody></table></div></div></div>Arvind Mohanhttp://www.blogger.com/profile/09421036756092622107noreply@blogger.com0tag:blogger.com,1999:blog-7173134778831375674.post-65738490655373433482012-07-26T20:49:00.000+05:302012-07-26T20:49:00.095+05:30Blog # 84 : Risky Bridge<div dir="ltr" style="text-align: left;" trbidi="on"><script language="javascript">
function show(targetID) {
target = document.getElementById(targetID);
if (target.style.display == "none")
{ target.style.display = ""; }
}
function hide(targetID) {
target = document.getElementById(targetID);
target.style.display = "none";
}
function toggle(targetID) {
remark = document.getElementById(targetID + '_remark');
hint = document.getElementById(targetID + '_hint');
solution = document.getElementById(targetID + '_solution');
if (remark.style.display == "none" ) {
remark.style.display = "";
}
else if (hint.style.display == "none" ) {
hint.style.display = ""; return;
}
else if (solution.style.display == "none" ) {
solution.style.display = ""; return;
}
else {
remark.style.display = "none";
hint.style.display = "none";
solution.style.display = "none";
}
}
</script><br />
<div dir="ltr" style="text-align: left;" trbidi="on"><div style="font-family: "Trebuchet MS",sans-serif;"><table cellpadding="8" cellspacing="0" style="font-family: "Trebuchet MS",sans-serif;"><tbody>
<tr> <td valign="top"><div align="justify"><span style="font-size: small;">A truck stops at a weigh station at the entrance to a bridge and is shown to weigh exactly 2000 lbs. The operator of the weigh station notes that the bridge can hold exactly 2000 lbs, but would crumble if it were subjected to even a fraction of an ounce more. But he says that no other vehicles ever cross over the bridge and so it's fine if the truck crosses. The truck continues on.<br />
Once the truck is halfway across the 10-mile long bridge, a sparrow flies over to the truck and lands on the hood. The truck driver sees the bird lands and his heart drops as he realizes the bridge is about to collapse, but even after the bird lands, the bridge doesn't crumble.<br />
How was the bridge able to hold up despite the extra weight from the bird ?<br />
<br />
</span><br />
<span style="font-size: small;"><br />
</span><br />
<span style="font-size: small;">courtesy: Vibhaj </span></div><div align="justify"><br />
<span style="font-size: small;">Click <a href="javascript:%20toggle('84');"><b>here</b></a> to see the solution.<br />
p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice.</span></div><br />
<div class="remark" id="84_remark" style="display: none;"><br />
<br />
<br />
<br />
<br />
<center><br />
<table><tbody>
<tr><td><table bgcolor="white" border="0" cellpadding="5" cellspacing="0" class="bodyline"><tbody>
<tr><td><div align="justify"><b><span style="font-size: small;">Remarks:</span></b> </div><span style="font-size: small;">Observe. Hit again for hints.</span></td></tr>
</tbody></table><table border="0" cellpadding="0" cellspacing="0" class="tbl"><tbody>
<tr> </tr>
</tbody></table></td></tr>
</tbody></table></center></div><div class="hint" id="84_hint" style="display: none;"><br />
<br />
<br />
<br />
<center><br />
<table><tbody>
<tr><td><table bgcolor="white" border="0" cellpadding="5" cellspacing="0" class="bodyline"><tbody>
<tr><td><div align="justify"><b><span style="font-size: small;"> Hints:</span></b></div><span style="font-size: small;">An intelligent question. Just compare the states of the truck.</span></td></tr>
</tbody></table><table border="0" cellpadding="0" cellspacing="0" class="tbl"><tbody>
<tr> </tr>
</tbody></table></td></tr>
</tbody></table></center></div><div class="solution" id="84_solution" style="display: none;"><br />
<br />
<br />
<br />
<br />
<center><br />
<table><tbody>
<tr><td><table bgcolor="white" border="0" cellpadding="5" cellspacing="0" class="bodyline"><tbody>
<tr><td><div align="justify"><b><span style="font-size: small;">Solution:</span></b></div><span style="font-size: small;"><br />
The weight of bird was compensated by the fuel burnt during 5 mile drive.</span></td></tr>
</tbody></table></td></tr>
</tbody></table></center></div></td> </tr>
</tbody></table></div></div></div>Arvind Mohanhttp://www.blogger.com/profile/09421036756092622107noreply@blogger.com0tag:blogger.com,1999:blog-7173134778831375674.post-43807530353282212872012-07-26T16:43:00.002+05:302012-07-26T16:44:35.250+05:30Blog # 83 : Bitonic Array<div dir="ltr" style="text-align: left;" trbidi="on"><script language="javascript">
function show(targetID) {
target = document.getElementById(targetID);
if (target.style.display == "none")
{ target.style.display = ""; }
}
function hide(targetID) {
target = document.getElementById(targetID);
target.style.display = "none";
}
function toggle(targetID) {
remark = document.getElementById(targetID + '_remark');
hint = document.getElementById(targetID + '_hint');
solution = document.getElementById(targetID + '_solution');
if (remark.style.display == "none" ) {
remark.style.display = "";
}
else if (hint.style.display == "none" ) {
hint.style.display = ""; return;
}
else if (solution.style.display == "none" ) {
solution.style.display = ""; return;
}
else {
remark.style.display = "none";
hint.style.display = "none";
solution.style.display = "none";
}
}
</script><br />
<div dir="ltr" style="text-align: left;" trbidi="on"><div style="font-family: "Trebuchet MS",sans-serif;"><table cellpadding="8" cellspacing="0" style="font-family: "Trebuchet MS",sans-serif;"><tbody>
<tr> <td valign="top"><div align="justify"><span style="font-size: small;">Given an array of N distinct integers with the property that there exists an index K (0 <= K <= N-1) such that input[0], ..., input[K] is and increasing sequence and input[K], ..., input[N-1] is a decreasing sequence. Devise and algorithm to find K. Ex [1 2 4 7 10 15 13 11 5 0 -5] Answer: K=5 (input[K]=15) </span><br />
<span style="font-size: small;"><br />
</span><br />
<span style="font-size: small;">courtesy: Vibhaj </span></div><div align="justify"><br />
<span style="font-size: small;">Click <a href="javascript:%20toggle('83');"><b>here</b></a> to see the solution.<br />
p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice.</span></div><br />
<div class="remark" id="83_remark" style="display: none;"><br />
<br />
<br />
<center><br />
<table><tbody>
<tr><td><table bgcolor="white" border="0" cellpadding="5" cellspacing="0" class="bodyline"><tbody>
<tr><td><div align="justify"><b><span style="font-size: small;">Remarks:</span></b> </div><span style="font-size: small;">No remarks. Hit again for hints.</span></td></tr>
</tbody></table><table border="0" cellpadding="0" cellspacing="0" class="tbl"><tbody>
<tr> </tr>
</tbody></table></td></tr>
</tbody></table></center></div><div class="hint" id="83_hint" style="display: none;"><br />
<br />
<br />
<br />
<br />
<center><br />
<table><tbody>
<tr><td><table bgcolor="white" border="0" cellpadding="5" cellspacing="0" class="bodyline"><tbody>
<tr><td><div align="justify"><b><span style="font-size: small;"> Hints:</span></b></div><span style="font-size: small;">Value stored in any element of the Array reaches a maxima at certain index.</span></td></tr>
</tbody></table><table border="0" cellpadding="0" cellspacing="0" class="tbl"><tbody>
<tr> </tr>
</tbody></table></td></tr>
</tbody></table></center></div><div class="solution" id="83_solution" style="display: none;"><br />
<br />
<br />
<br />
<center><br />
<table><tbody>
<tr><td><table bgcolor="white" border="0" cellpadding="5" cellspacing="0" class="bodyline"><tbody>
<tr><td><div align="justify"><b><span style="font-size: small;">Solution:</span></b></div><span style="font-size: small;"><br />
Use binary search with the following conditions :<br />
<br />
input[mid-1] < input[mid] > input[mid+1] for mid != 0 and mid != N-1<br />
input[mid] > input[mid+1] for mid == 0<br />
input[mid-1] < input[mid] for mid == N-1 with initial low = 0, high = N-1, mid = (high + low)/2 </span><br />
<pre class="cpp" name="code">int bitonic_pivot(int input[], int N)
{
int low=0, high=N-1, mid;
while(low < high)
{
mid=(low+high)/2;
if((!mid || (input[mid-1] < input[mid])) && (mid != N-1 || (input[mid] > input[mid+1])))
return mid;
else if((!mid || (input[mid-1] < input[mid])) && (mid != N-1 || (input[mid] < input[mid+1])))
low=mid+1;
else if((!mid || (input[mid-1] > input[mid])) && (mid != N-1 || (input[mid] > input[mid+1])))
high=mid;
}
return -1;
}
</pre></td></tr>
</tbody></table></td></tr>
</tbody></table></center></div></td> </tr>
</tbody></table></div></div></div>Arvind Mohanhttp://www.blogger.com/profile/09421036756092622107noreply@blogger.com0tag:blogger.com,1999:blog-7173134778831375674.post-49373987883009272492012-07-13T22:46:00.001+05:302012-07-13T22:46:00.195+05:30Blog # 82 : Birthday Problem<div dir="ltr" style="text-align: left;" trbidi="on"><script language="javascript">
function show(targetID) {
target = document.getElementById(targetID);
if (target.style.display == "none")
{ target.style.display = ""; }
}
function hide(targetID) {
target = document.getElementById(targetID);
target.style.display = "none";
}
function toggle(targetID) {
remark = document.getElementById(targetID + '_remark');
hint = document.getElementById(targetID + '_hint');
solution = document.getElementById(targetID + '_solution');
if (remark.style.display == "none" ) {
remark.style.display = "";
}
else if (hint.style.display == "none" ) {
hint.style.display = ""; return;
}
else if (solution.style.display == "none" ) {
solution.style.display = ""; return;
}
else {
remark.style.display = "none";
hint.style.display = "none";
solution.style.display = "none";
}
}
</script><br />
<div dir="ltr" style="text-align: left;" trbidi="on"><div style="font-family: "Trebuchet MS",sans-serif;"><table cellpadding="8" cellspacing="0" style="font-family: "Trebuchet MS",sans-serif;"><tbody>
<tr> <td valign="top"><div align="justify"><span style="font-size: small;">What is the least number of people that need to be in a room such that there is greater than a 50 % chance that at least two of the people have the same birthday ?</span><br />
<span style="font-size: small;"><br />
</span><br />
<span style="font-size: small;"><br />
</span></div><div align="justify"><span style="font-size: small;">Click <a href="javascript:%20toggle('82');"><b>here</b></a> to see the solution.</span><br />
<span style="font-size: small;"><br />
Courtesy: Vibhaj Rajan<br />
p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice.</span></div><br />
<div class="remark" id="82_remark" style="display: none;"><br />
<br />
<br />
<br />
<center><br />
<table><tbody>
<tr><td><table bgcolor="white" border="0" cellpadding="5" cellspacing="0" class="bodyline"><tbody>
<tr><td><div align="justify"><b><span style="font-size: small;">Remarks:</span></b> </div><span style="font-size: small;">No remarks. Hit again for hints.</span></td></tr>
</tbody></table><table border="0" cellpadding="0" cellspacing="0" class="tbl"><tbody>
<tr> </tr>
</tbody></table></td></tr>
</tbody></table></center></div><div class="hint" id="82_hint" style="display: none;"><br />
<br />
<br />
<center><br />
<table><tbody>
<tr><td><table bgcolor="white" border="0" cellpadding="5" cellspacing="0" class="bodyline"><tbody>
<tr><td><div align="justify"><b><span style="font-size: small;"> Hints:</span></b></div><span style="font-size: small;">Probability, think how will it be not possible? Hit again for solution.</span></td></tr>
</tbody></table><table border="0" cellpadding="0" cellspacing="0" class="tbl"><tbody>
<tr> </tr>
</tbody></table></td></tr>
</tbody></table></center></div><div class="solution" id="82_solution" style="display: none;"><br />
<br />
<br />
<br />
<center><br />
<table><tbody>
<tr><td><table bgcolor="white" border="0" cellpadding="5" cellspacing="0" class="bodyline"><tbody>
<tr><td><div align="justify"><b><span style="font-size: small;">Solution:</span></b></div><span style="font-size: small;"><br />
At least 23 people should be there. <br />
<br />
To find N such that probability of two people sharing the same birthday be more than 50%, we find N such that probability of no two people sharing same birthday be less than 50%.<br />
<br />
Thus probability would be 364/365 * 363/365 * 362/365.... (N-1 terms)... (365 - (N-1) )/365 < 0.5
So, N = 23
For more information : <a href="http://en.wikipedia.org/wiki/Birthday_problem">http://en.wikipedia.org/wiki/Birthday_problem</a><br />
</span></td></tr>
</tbody></table></td></tr>
</tbody></table></center></div></td> </tr>
</tbody></table></div></div></div>Arvind Mohanhttp://www.blogger.com/profile/09421036756092622107noreply@blogger.com0tag:blogger.com,1999:blog-7173134778831375674.post-12681561888072545002012-07-13T16:55:00.001+05:302012-07-13T16:45:52.194+05:30Blog # 81 : Adobe Interview Questions 2012 Batch<div dir="ltr" style="text-align: left;" trbidi="on"><div style="font-family: "Trebuchet MS",sans-serif;"><div dir="ltr" style="text-align: left;" trbidi="on"><span style="font-size: small;"><br />
</span><br />
<div style="text-align: -webkit-auto;"><span style="font-size: small;"><span style="color: #333333; font-family: 'Lucida Grande', 'Trebuchet MS', Verdana, Helvetica, Arial, sans-serif;"><span style="line-height: 18px;"><b>Written Round:</b></span></span></span></div><div style="text-align: -webkit-auto;"><span style="font-size: small;"><span style="color: #333333; font-family: 'Lucida Grande', 'Trebuchet MS', Verdana, Helvetica, Arial, sans-serif;"><span style="line-height: 18px;">1st Paper was completely a speed test.</span></span></span></div><div style="text-align: -webkit-auto;"><span style="font-size: small;"><span style="color: #333333; font-family: 'Lucida Grande', 'Trebuchet MS', Verdana, Helvetica, Arial, sans-serif;"><span style="line-height: 18px;">2nd Paper had 20 question, 10 from general computer science and 10 from algorithm and data structure, few from paper 2 are below:</span></span></span></div><div style="text-align: -webkit-auto;"><span style="font-size: small;"><span style="color: #333333; font-family: 'Lucida Grande', 'Trebuchet MS', Verdana, Helvetica, Arial, sans-serif;"><span style="line-height: 18px;"><br />
</span></span></span></div><div style="text-align: -webkit-auto;"><span style="font-size: small;"><span style="color: #333333; font-family: 'Lucida Grande', 'Trebuchet MS', Verdana, Helvetica, Arial, sans-serif;"><span style="line-height: 18px;">1. For every number that has 3 in its units place has one number which has all one's i.e. 111 that can be divided by it completely and 13 has a multiple 111111. Write a program to find such multiple for any number that has 3 at its units place.</span></span></span></div><div style="text-align: -webkit-auto;"><span style="font-size: small;"><span style="color: #333333; font-family: 'Lucida Grande', 'Trebuchet MS', Verdana, Helvetica, Arial, sans-serif;"><span style="line-height: 18px;">2. write a program for checking the given number is a palindrome.</span></span></span></div><div style="text-align: -webkit-auto;"><span style="font-size: small;"><span style="color: #333333; font-family: 'Lucida Grande', 'Trebuchet MS', Verdana, Helvetica, Arial, sans-serif;"><span style="line-height: 18px;">3. write a recursive program for reversing the linked list.</span></span></span></div><div style="text-align: -webkit-auto;"><span style="font-size: small;"><span style="color: #333333; font-family: 'Lucida Grande', 'Trebuchet MS', Verdana, Helvetica, Arial, sans-serif;"><span style="line-height: 18px;">4. what are the maximum no of edges that can be connected in a graph of n vertices and 0 edges such that after adding edges given graph is still disconnected.</span></span></span></div><div style="text-align: -webkit-auto;"><span style="font-size: small;"><span style="color: #333333; font-family: 'Lucida Grande', 'Trebuchet MS', Verdana, Helvetica, Arial, sans-serif;"><span style="line-height: 18px;">5. A question of OS on critical section.</span></span></span></div><div style="text-align: -webkit-auto;"><span style="font-size: small;"><span style="color: #333333; font-family: 'Lucida Grande', 'Trebuchet MS', Verdana, Helvetica, Arial, sans-serif;"><span style="line-height: 18px;">6. write a program to return the row number which has max no of one's in an array of NxN matrix where all 1's occur before any 0's starts.</span></span></span></div><div style="text-align: -webkit-auto;"><span style="font-size: small;"><span style="color: #333333; font-family: 'Lucida Grande', 'Trebuchet MS', Verdana, Helvetica, Arial, sans-serif;"><span style="line-height: 18px;">for example:</span></span></span></div><div style="text-align: -webkit-auto;"><span style="font-size: small;"><span style="color: #333333; font-family: 'Lucida Grande', 'Trebuchet MS', Verdana, Helvetica, Arial, sans-serif;"><span style="line-height: 18px;">1110</span></span></span></div><div style="text-align: -webkit-auto;"><span style="font-size: small;"><span style="color: #333333; font-family: 'Lucida Grande', 'Trebuchet MS', Verdana, Helvetica, Arial, sans-serif;"><span style="line-height: 18px;">1111</span></span></span></div><div style="text-align: -webkit-auto;"><span style="font-size: small;"><span style="color: #333333; font-family: 'Lucida Grande', 'Trebuchet MS', Verdana, Helvetica, Arial, sans-serif;"><span style="line-height: 18px;">1000</span></span></span></div><div style="text-align: -webkit-auto;"><span style="font-size: small;"><span style="color: #333333; font-family: 'Lucida Grande', 'Trebuchet MS', Verdana, Helvetica, Arial, sans-serif;"><span style="line-height: 18px;">1100</span></span></span></div><div style="text-align: -webkit-auto;"><span style="font-size: small;"><span style="color: #333333; font-family: 'Lucida Grande', 'Trebuchet MS', Verdana, Helvetica, Arial, sans-serif;"><span style="line-height: 18px;">7. 1 question on deadlock and starvation</span></span></span></div><div style="text-align: -webkit-auto;"><span style="font-size: small;"><span style="color: #333333; font-family: 'Lucida Grande', 'Trebuchet MS', Verdana, Helvetica, Arial, sans-serif;"><span style="line-height: 18px;">8. Given two arrays A[], B[]. Given a no. 'sum'. Find a and b such that a+b=sum ['a' from A and 'b' from B]</span></span></span></div><div style="text-align: -webkit-auto;"><span style="font-size: small;"><span style="color: #333333; font-family: 'Lucida Grande', 'Trebuchet MS', Verdana, Helvetica, Arial, sans-serif;"><span style="line-height: 18px;"><br />
</span></span></span></div><div style="text-align: -webkit-auto;"><span style="font-size: small;"><span style="color: #333333; font-family: 'Lucida Grande', 'Trebuchet MS', Verdana, Helvetica, Arial, sans-serif;"><span style="line-height: 18px;"><b>Technical Round 1:</b></span></span></span></div><div style="text-align: -webkit-auto;"><span style="font-size: small;"><span style="color: #333333; font-family: 'Lucida Grande', 'Trebuchet MS', Verdana, Helvetica, Arial, sans-serif;"><span style="line-height: 18px;">1. For every number that has 3 in its units place has one number which has all one's i.e. 111 that can be divided by it completely and 13 has a multiple 111111. Write a program to find such multiple for any number that has 3 at its units place. [As I could not solve it in written round]. </span></span></span></div><div style="text-align: -webkit-auto;"><span style="font-size: small;"><span style="color: #333333; font-family: 'Lucida Grande', 'Trebuchet MS', Verdana, Helvetica, Arial, sans-serif;"><span style="line-height: 18px;">[proposed 3 different methods and their complexity]</span></span></span></div><div style="text-align: -webkit-auto;"><span style="font-size: small;"><span style="color: #333333; font-family: 'Lucida Grande', 'Trebuchet MS', Verdana, Helvetica, Arial, sans-serif;"><span style="line-height: 18px;"><br />
</span></span></span></div><div style="text-align: -webkit-auto;"><span style="font-size: small;"><span style="color: #333333; font-family: 'Lucida Grande', 'Trebuchet MS', Verdana, Helvetica, Arial, sans-serif;"><span style="line-height: 18px;"><b>Technical Round 2:</b></span></span></span></div><div style="text-align: -webkit-auto;"><span style="font-size: small;"><span style="color: #333333; font-family: 'Lucida Grande', 'Trebuchet MS', Verdana, Helvetica, Arial, sans-serif;"><span style="line-height: 18px;">1. Virtual Function</span></span></span></div><div style="text-align: -webkit-auto;"><span style="font-size: small;"><span style="color: #333333; font-family: 'Lucida Grande', 'Trebuchet MS', Verdana, Helvetica, Arial, sans-serif;"><span style="line-height: 18px;">2. Copy Constructor</span></span></span></div><div style="text-align: -webkit-auto;"><span style="font-size: small;"><span style="color: #333333; font-family: 'Lucida Grande', 'Trebuchet MS', Verdana, Helvetica, Arial, sans-serif;"><span style="line-height: 18px;">3. Inheritance</span></span></span></div><div style="text-align: -webkit-auto;"><span style="font-size: small;"><span style="color: #333333; font-family: 'Lucida Grande', 'Trebuchet MS', Verdana, Helvetica, Arial, sans-serif;"><span style="line-height: 18px;">4. Virtual Destructor</span></span></span></div><div style="text-align: -webkit-auto;"><span style="font-size: small;"><span style="color: #333333; font-family: 'Lucida Grande', 'Trebuchet MS', Verdana, Helvetica, Arial, sans-serif;"><span style="line-height: 18px;">5. Suppose a Date in the format DD/MM/YYYY is palindrome, find the next palindrome date.</span></span></span></div><div style="text-align: -webkit-auto;"><span style="font-size: small;"><span style="color: #333333; font-family: 'Lucida Grande', 'Trebuchet MS', Verdana, Helvetica, Arial, sans-serif;"><span style="line-height: 18px;">6. "He is a good boy" -> "boy good a is He" [He kept on adding constraints.]</span></span></span></div><div style="text-align: -webkit-auto;"><span style="font-size: small;"><span style="color: #333333; font-family: 'Lucida Grande', 'Trebuchet MS', Verdana, Helvetica, Arial, sans-serif;"><span style="line-height: 18px;">7. 10 Red and 10 Blue balls are given. You have 2 jars, now a person will be picking 1 ball out of any of them. How will you maximize probability of picking Red Ball.</span></span></span></div><div style="text-align: -webkit-auto;"><span style="font-size: small;"><span style="color: #333333; font-family: 'Lucida Grande', 'Trebuchet MS', Verdana, Helvetica, Arial, sans-serif;"><span style="line-height: 18px;"><br />
</span></span></span></div><div style="text-align: -webkit-auto;"><span style="font-size: small;"><span style="color: #333333; font-family: 'Lucida Grande', 'Trebuchet MS', Verdana, Helvetica, Arial, sans-serif;"><span style="line-height: 18px;"><b>Technical Round 3:</b></span></span></span></div><div style="text-align: -webkit-auto;"><span style="font-size: small;"><span style="color: #333333; font-family: 'Lucida Grande', 'Trebuchet MS', Verdana, Helvetica, Arial, sans-serif;"><span style="line-height: 18px;">1. How T9 dictionary is implemented?</span></span></span></div><div style="text-align: -webkit-auto;"><span style="font-size: small;"><span style="color: #333333; font-family: 'Lucida Grande', 'Trebuchet MS', Verdana, Helvetica, Arial, sans-serif;"><span style="line-height: 18px;">2. How do Touch Phones know in which area they are touched?</span></span></span></div><div style="text-align: -webkit-auto;"><span style="font-size: small;"><span style="color: #333333; font-family: 'Lucida Grande', 'Trebuchet MS', Verdana, Helvetica, Arial, sans-serif;"><span style="line-height: 18px;">3. Project info.</span></span></span></div><div style="text-align: -webkit-auto;"><span style="font-size: small;"><span style="color: #333333; font-family: 'Lucida Grande', 'Trebuchet MS', Verdana, Helvetica, Arial, sans-serif;"><span style="line-height: 18px;"><br />
</span></span></span></div><div style="text-align: -webkit-auto;"><span style="font-size: small;"><span style="color: #333333; font-family: 'Lucida Grande', 'Trebuchet MS', Verdana, Helvetica, Arial, sans-serif;"><span style="line-height: 18px;"><b>Technical Round 4:</b></span></span></span></div><div style="text-align: -webkit-auto;"><span style="font-size: small;"><span style="color: #333333; font-family: 'Lucida Grande', 'Trebuchet MS', Verdana, Helvetica, Arial, sans-serif;"><span style="line-height: 18px;">1. 2 arrays A & B of numbers are given. Find combination such that a+b=c+d. [a,b from A and c,d from B] [Kept on adding constraint to minimize time and space complexity]</span></span></span></div><div style="text-align: -webkit-auto;"><span style="font-size: small;"><span style="color: #333333; font-family: 'Lucida Grande', 'Trebuchet MS', Verdana, Helvetica, Arial, sans-serif;"><span style="line-height: 18px;">2. How to design a stack using 2 queues.</span></span></span></div><div style="text-align: -webkit-auto;"><span style="font-size: small;"><span style="color: #333333; font-family: 'Lucida Grande', 'Trebuchet MS', Verdana, Helvetica, Arial, sans-serif;"><span style="line-height: 18px;"><br />
</span></span></span></div><div style="text-align: -webkit-auto;"><span style="font-size: small;"><span style="color: #333333; font-family: 'Lucida Grande', 'Trebuchet MS', Verdana, Helvetica, Arial, sans-serif;"><span style="line-height: 18px;"><b>HR Round:</b></span></span></span></div><div style="text-align: -webkit-auto;"><span style="font-size: small;"><span style="color: #333333; font-family: 'Lucida Grande', 'Trebuchet MS', Verdana, Helvetica, Arial, sans-serif;"><span style="line-height: 18px;">1. Tell me about yourself.</span></span></span></div><div style="text-align: -webkit-auto;"><span style="font-size: small;"><span style="color: #333333; font-family: 'Lucida Grande', 'Trebuchet MS', Verdana, Helvetica, Arial, sans-serif;"><span style="line-height: 18px;">2. Why do you want to join Adobe?</span></span></span></div><div style="text-align: -webkit-auto;"><span style="font-size: small;"><span style="color: #333333; font-family: 'Lucida Grande', 'Trebuchet MS', Verdana, Helvetica, Arial, sans-serif;"><span style="line-height: 18px;"><br />
</span></span></span><br />
<span style="font-size: small;"><span style="color: #333333; font-family: 'Lucida Grande', 'Trebuchet MS', Verdana, Helvetica, Arial, sans-serif;"><span style="line-height: 18px;">Placed!</span></span></span><br />
<span style="font-size: small;"><span style="color: #333333; font-family: 'Lucida Grande', 'Trebuchet MS', Verdana, Helvetica, Arial, sans-serif;"><span style="line-height: 18px;"><br />
</span></span></span></div><div style="text-align: -webkit-auto;"><span style="font-size: small;"><span style="color: #333333; font-family: 'Lucida Grande', 'Trebuchet MS', Verdana, Helvetica, Arial, sans-serif;"><span style="line-height: 18px;">-All the very best!</span></span></span></div><div style="text-align: -webkit-auto;"><span style="font-size: small;"><span style="color: #333333; font-family: 'Lucida Grande', 'Trebuchet MS', Verdana, Helvetica, Arial, sans-serif;"><span style="line-height: 18px;">Will post more as I recall them. :)</span></span></span></div></div></div></div>Arvind Mohanhttp://www.blogger.com/profile/09421036756092622107noreply@blogger.com0tag:blogger.com,1999:blog-7173134778831375674.post-9879199736207472232012-07-13T16:15:00.002+05:302012-07-13T16:20:30.874+05:30Blog # 80 : Simple but Tricky Sum<div dir="ltr" style="text-align: left;" trbidi="on"><script language="javascript">
function show(targetID) {
target = document.getElementById(targetID);
if (target.style.display == "none")
{ target.style.display = ""; }
}
function hide(targetID) {
target = document.getElementById(targetID);
target.style.display = "none";
}
function toggle(targetID) {
remark = document.getElementById(targetID + '_remark');
hint = document.getElementById(targetID + '_hint');
solution = document.getElementById(targetID + '_solution');
if (remark.style.display == "none" ) {
remark.style.display = "";
}
else if (hint.style.display == "none" ) {
hint.style.display = ""; return;
}
else if (solution.style.display == "none" ) {
solution.style.display = ""; return;
}
else {
remark.style.display = "none";
hint.style.display = "none";
solution.style.display = "none";
}
}
</script><br />
<div dir="ltr" style="text-align: left;" trbidi="on"><div style="font-family: "Trebuchet MS",sans-serif;"><table cellpadding="8" cellspacing="0" style="font-family: "Trebuchet MS",sans-serif;"><tbody>
<tr> <td valign="top"><div align="justify"><span style="font-size: small;">What would be the output of the following code ?<br />
<pre class="cpp" name="code">int main(int argc, char **argv){
printf("%d", 012345 + 123450);
return 0;
}
</pre>courtesy: Mahesh Gondi<br />
</span><br />
<span style="font-size: small;"><br />
</span></div><div align="justify"><span style="font-size: small;">Click <a href="javascript:%20toggle('80');"><b>here</b></a> to see the solution.</span><br />
<span style="font-size: small;"><br />
p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice.</span></div><br />
<div class="remark" id="80_remark" style="display: none;"><br />
<br />
<br />
<br />
<br />
<center><br />
<table><tbody>
<tr><td><table bgcolor="white" border="0" cellpadding="5" cellspacing="0" class="bodyline"><tbody>
<tr><td><div align="justify"><b><span style="font-size: small;">Remarks:</span></b> </div><span style="font-size: small;">No remarks. Hit again for hints.</span></td></tr>
</tbody></table><table border="0" cellpadding="0" cellspacing="0" class="tbl"><tbody>
<tr> </tr>
</tbody></table></td></tr>
</tbody></table></center></div><div class="hint" id="80_hint" style="display: none;"><br />
<br />
<br />
<br />
<br />
<center><br />
<table><tbody>
<tr><td><table bgcolor="white" border="0" cellpadding="5" cellspacing="0" class="bodyline"><tbody>
<tr><td><div align="justify"><b><span style="font-size: small;"> Hints:</span></b></div><span style="font-size: small;">Think of different number system representations. Hit again for solution.</span></td></tr>
</tbody></table><table border="0" cellpadding="0" cellspacing="0" class="tbl"><tbody>
<tr> </tr>
</tbody></table></td></tr>
</tbody></table></center></div><div class="solution" id="80_solution" style="display: none;"><br />
<br />
<br />
<br />
<br />
<center><br />
<table><tbody>
<tr><td><table bgcolor="white" border="0" cellpadding="5" cellspacing="0" class="bodyline"><tbody>
<tr><td><div align="justify"><b><span style="font-size: small;">Solution:</span></b></div><span style="font-size: small;"><br />
The number 012345 shall be considered an octal literal and thus its value will be 5349 and addition with 123450 shall result in 128799.<br />
</span></td></tr>
</tbody></table></td></tr>
</tbody></table></center></div></td> </tr>
</tbody></table></div></div></div>Arvind Mohanhttp://www.blogger.com/profile/09421036756092622107noreply@blogger.com0tag:blogger.com,1999:blog-7173134778831375674.post-24654831819246045182012-07-13T15:46:00.003+05:302012-07-13T16:17:29.392+05:30Blog # 79 : Strange Indian Coins<div dir="ltr" style="text-align: left;" trbidi="on"><script language="javascript">
function show(targetID) {
target = document.getElementById(targetID);
if (target.style.display == "none")
{ target.style.display = ""; }
}
function hide(targetID) {
target = document.getElementById(targetID);
target.style.display = "none";
}
function toggle(targetID) {
remark = document.getElementById(targetID + '_remark');
hint = document.getElementById(targetID + '_hint');
solution = document.getElementById(targetID + '_solution');
if (remark.style.display == "none" ) {
remark.style.display = "";
}
else if (hint.style.display == "none" ) {
hint.style.display = ""; return;
}
else if (solution.style.display == "none" ) {
solution.style.display = ""; return;
}
else {
remark.style.display = "none";
hint.style.display = "none";
solution.style.display = "none";
}
}
</script><br />
<div dir="ltr" style="text-align: left;" trbidi="on"><div style="font-family: "Trebuchet MS",sans-serif;"><table cellpadding="8" cellspacing="0" style="font-family: "Trebuchet MS",sans-serif;"><tbody>
<tr> <td valign="top"><div align="justify"><span style="font-size: small;">You have two Indian coins that add up to 6 rupees. However, one of them is not a 5 rupee coin. <br />
What are the two coins ?<br />
<br />
<br />
courtesy: Vibhaj Rajan<br />
</span><br />
<span style="font-size: small;"><br />
</span></div><div align="justify"><span style="font-size: small;">Click <a href="javascript:%20toggle('79');"><b>here</b></a> to see the solution.<br />
p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice.</span></div><br />
<div class="remark" id="79_remark" style="display: none;"><br />
<br />
<br />
<br />
<center><br />
<table><tbody>
<tr><td><table bgcolor="white" border="0" cellpadding="5" cellspacing="0" class="bodyline"><tbody>
<tr><td><div align="justify"><b><span style="font-size: small;">Remarks:</span></b> </div><span style="font-size: small;">No remarks. Hit again for hints.</span></td></tr>
</tbody></table><table border="0" cellpadding="0" cellspacing="0" class="tbl"><tbody>
<tr> </tr>
</tbody></table></td></tr>
</tbody></table></center></div><div class="hint" id="79_hint" style="display: none;"><br />
<br />
<br />
<br />
<center><br />
<table><tbody>
<tr><td><table bgcolor="white" border="0" cellpadding="5" cellspacing="0" class="bodyline"><tbody>
<tr><td><div align="justify"><b><span style="font-size: small;"> Hints:</span></b></div><span style="font-size: small;">Read the question loud. Hit again for solution.</span></td></tr>
</tbody></table><table border="0" cellpadding="0" cellspacing="0" class="tbl"><tbody>
<tr> </tr>
</tbody></table></td></tr>
</tbody></table></center></div><div class="solution" id="79_solution" style="display: none;"><br />
<br />
<br />
<center><br />
<table><tbody>
<tr><td><table bgcolor="white" border="0" cellpadding="5" cellspacing="0" class="bodyline"><tbody>
<tr><td><div align="justify"><b><span style="font-size: small;">Solution:</span></b></div><span style="font-size: small;"><br />
There are 2 coins. If one of them is not 5, the other one will be. LOL<br />
</span></td></tr>
</tbody></table></td></tr>
</tbody></table></center></div></td> </tr>
</tbody></table></div></div></div>Arvind Mohanhttp://www.blogger.com/profile/09421036756092622107noreply@blogger.com0tag:blogger.com,1999:blog-7173134778831375674.post-53243819771902867922012-05-26T22:30:00.004+05:302012-05-26T22:42:18.655+05:30Blog # 78 : Google Interview Question 2012<div dir="ltr" style="text-align: left;" trbidi="on"><div style="font-size: 16;"><div dir="ltr" style="text-align: left;" trbidi="on"><span style="font-family: 'Trebuchet MS', sans-serif;"><span class="GingerNoCheckStart"></span>Interview questions asked by Google Recruitment team after qualifying the first on-campus round comprising a written exam:</span><br />
<span style="font-family: 'Trebuchet MS', sans-serif;"><br />
</span><br />
<span style="font-family: 'Trebuchet MS', sans-serif;">Round 1:</span><br />
<span style="font-family: 'Trebuchet MS', sans-serif;">1) Given a database, a query returns correct output 99% of the time, however 1% of the time, it returns <span class="GRcorrect" grphrase="c58534eb789459affab5bd5d02b18d4b9bfe5411" grtype="null" id="GRmark_c58534eb789459affab5bd5d02b18d4b9bfe5411_wrong output:0">wrong output</span>. What could be the possible reasons?</span><br />
<span style="font-family: 'Trebuchet MS', sans-serif;">2) On a 2-D grid, the positions (x<span class="GRcorrect" grphrase="2ef0dedb64265af89c0096979ec0408db48c2da6" grtype="null" id="GRmark_2ef0dedb64265af89c0096979ec0408db48c2da6_,:0">,</span>y) of 3 persons are given. Find the meeting point such that <span class="GRcorrect" grphrase="24469f4263622c9f3e412aa46900a0d3d18f5924" grtype="null" id="GRmark_24469f4263622c9f3e412aa46900a0d3d18f5924_sum:0">sum</span> of <span class="GRcorrect" grphrase="24469f4263622c9f3e412aa46900a0d3d18f5924" grtype="null" id="GRmark_24469f4263622c9f3e412aa46900a0d3d18f5924_distances:1">distances</span> of each person from meeting point is minimized.</span><br />
<span style="font-family: 'Trebuchet MS', sans-serif;">Now generalize this to N persons and solve.</span><br />
<span style="font-family: 'Trebuchet MS', sans-serif;">3) A very long question related to hashing. I don't remember it.</span><br />
<span style="font-family: 'Trebuchet MS', sans-serif;"><br />
</span><br />
<span style="font-family: 'Trebuchet MS', sans-serif;">Round 2:</span><br />
<span style="font-family: 'Trebuchet MS', sans-serif;">1) Given a string of <span class="GRcorrect" grphrase="be8711b0f65962615e8d438eb81ca2356257ef54" grtype="null" id="GRmark_be8711b0f65962615e8d438eb81ca2356257ef54_parantheses:0">parantheses</span>, check if the string is valid. <span class="GRcorrect" grphrase="b06181aa281cd77c8635208334c3d8baaf2c72b0" grtype="null" id="GRmark_b06181aa281cd77c8635208334c3d8baaf2c72b0_ex:0">ex</span>: [[]] is valid, <span class="GRcorrect" grphrase="b06181aa281cd77c8635208334c3d8baaf2c72b0" grtype="null" id="GRmark_b06181aa281cd77c8635208334c3d8baaf2c72b0_]:1">]</span>[<span class="GRcorrect" grphrase="b06181aa281cd77c8635208334c3d8baaf2c72b0" grtype="null" id="GRmark_b06181aa281cd77c8635208334c3d8baaf2c72b0_]:2">]</span>[ is not valid. How would you <span class="GRcorrect" grphrase="8f57d2800e007f3f93578e622dc6b2e767d04b71" grtype="null" id="GRmark_8f57d2800e007f3f93578e622dc6b2e767d04b71_solve:0">solve</span> if the <span class="GRspelling" grtype="null">parantheses</span> could be <span class="GRcorrect" grphrase="8f57d2800e007f3f93578e622dc6b2e767d04b71" grtype="null" id="GRmark_8f57d2800e007f3f93578e622dc6b2e767d04b71_of:2">of </span></span><span class="GRcorrect" grphrase="feb37970e2875fd230f5400019c53cdb83323ddc" grtype="null" id="GRmark_feb37970e2875fd230f5400019c53cdb83323ddc_different:0" style="background-color: transparent; font-family: 'Trebuchet MS', sans-serif;">different</span><span style="font-family: 'Trebuchet MS', sans-serif;"> types like {</span><span class="GRcorrect" grphrase="feb37970e2875fd230f5400019c53cdb83323ddc" grtype="null" id="GRmark_feb37970e2875fd230f5400019c53cdb83323ddc_,:1" style="background-color: transparent; font-family: 'Trebuchet MS', sans-serif;">,</span><span style="font-family: 'Trebuchet MS', sans-serif;">[</span><span class="GRcorrect" grphrase="feb37970e2875fd230f5400019c53cdb83323ddc" grtype="null" id="GRmark_feb37970e2875fd230f5400019c53cdb83323ddc_,:2" style="background-color: transparent; font-family: 'Trebuchet MS', sans-serif;">,</span><span style="font-family: 'Trebuchet MS', sans-serif;">(</span><br />
<span style="font-family: 'Trebuchet MS', sans-serif;">2) Given a layout like </span><br />
<span style="font-family: 'Trebuchet MS', sans-serif;"><span class="GRcorrect" grphrase="8795a3b65131dc1070d0f4b79f4d26c9a669409e" grtype="null" id="GRmark_8795a3b65131dc1070d0f4b79f4d26c9a669409e_a:0">a</span> b c d e</span><br />
<span style="font-family: 'Trebuchet MS', sans-serif;"><span class="GRcorrect" grphrase="8bfa191cff78fbf4787bd44ebd530b197071e886" grtype="null" id="GRmark_8bfa191cff78fbf4787bd44ebd530b197071e886_f:0">f</span> g h <span class="GRcorrect" grphrase="8bfa191cff78fbf4787bd44ebd530b197071e886" grtype="null" id="GRmark_8bfa191cff78fbf4787bd44ebd530b197071e886_i:1">i</span> j</span><br />
<span style="font-family: 'Trebuchet MS', sans-serif;">k l m n o</span><br />
<span style="font-family: 'Trebuchet MS', sans-serif;"><span class="GRcorrect" grphrase="2521d8af01a28ef6ca15f810a28f0efdef0beaa6" grtype="null" id="GRmark_2521d8af01a28ef6ca15f810a28f0efdef0beaa6_p:0">p</span> q r s t</span><br />
<span style="font-family: 'Trebuchet MS', sans-serif;"><span class="GRcorrect" grphrase="68411ec7815d3beac926add5df15f3aa30d4dc6c" grtype="null" id="GRmark_68411ec7815d3beac926add5df15f3aa30d4dc6c_u:0">u</span> v w x y</span><br />
<span style="font-family: 'Trebuchet MS', sans-serif;">z</span><br />
<span style="font-family: 'Trebuchet MS', sans-serif;">Your initial point is a. You want to form a string like "movie". WAP to find the sequence of moves consisting of letters 'U','D','L','R' </span><br />
<span style="font-family: 'Trebuchet MS', sans-serif;">( <span class="GRcorrect" grphrase="6b1ef1cde88dcdf4eaefa86d8c5d6a0db7bdf73e" grtype="null" id="GRmark_6b1ef1cde88dcdf4eaefa86d8c5d6a0db7bdf73e_normal:0">normal</span> conventions) that would form the movie. <span class="GRcorrect" grphrase="8d9dd90d7081c54ba2b85ed66c6aa793a0e6442d" grtype="null" id="GRmark_8d9dd90d7081c54ba2b85ed66c6aa793a0e6442d_for:0">for</span> example: for string "<span class="GRcorrect" grphrase="8d9dd90d7081c54ba2b85ed66c6aa793a0e6442d" grtype="null" id="GRmark_8d9dd90d7081c54ba2b85ed66c6aa793a0e6442d_afg:1">afg</span>" sequence would be DR.</span><br />
<span style="font-family: 'Trebuchet MS', sans-serif;"><br />
</span><br />
<span style="font-family: 'Trebuchet MS', sans-serif;">Round 3:</span><br />
<span style="font-family: 'Trebuchet MS', sans-serif;">1) Given a number N, <span class="GRcorrect" grphrase="cabe7199caf240678ecd909a6b1c84bfc2434e2b" grtype="null" id="GRmark_cabe7199caf240678ecd909a6b1c84bfc2434e2b_form:0">form</span> all possible <span class="GRcorrect" grphrase="cabe7199caf240678ecd909a6b1c84bfc2434e2b" grtype="null" id="GRmark_cabe7199caf240678ecd909a6b1c84bfc2434e2b_paranthesizations:1">paranthesizations</span>. <span class="GRcorrect" grphrase="39b233695d0d3f80d77f1593d4d0fdd4420a7d2c" grtype="null" id="GRmark_39b233695d0d3f80d77f1593d4d0fdd4420a7d2c_like:0">like</span> for N=3, there would be 5 possible <span class="GRcorrect" grphrase="39b233695d0d3f80d77f1593d4d0fdd4420a7d2c" grtype="null" id="GRmark_39b233695d0d3f80d77f1593d4d0fdd4420a7d2c_parathesizations:1">parathesizations</span> ( <span class="GRcorrect" grphrase="39b233695d0d3f80d77f1593d4d0fdd4420a7d2c" grtype="null" id="GRmark_39b233695d0d3f80d77f1593d4d0fdd4420a7d2c_catalan:2">catalan</span> numbers ). </span><br />
<span style="font-family: 'Trebuchet MS', sans-serif;">Kept on asking to optimize time and space.</span><br />
<span style="font-family: 'Trebuchet MS', sans-serif;">2) Given <span class="GRcorrect" grphrase="d3442d70f33f82ecfa8c0eab3c914e4a091a9bfc" grtype="null" id="GRmark_d3442d70f33f82ecfa8c0eab3c914e4a091a9bfc_a:0">a</span> 8X8 chess-board, there is a bishop placed on a square (<span class="GRcorrect" grphrase="d3442d70f33f82ecfa8c0eab3c914e4a091a9bfc" grtype="null" id="GRmark_d3442d70f33f82ecfa8c0eab3c914e4a091a9bfc_i:1">i</span><span class="GRcorrect" grphrase="d3442d70f33f82ecfa8c0eab3c914e4a091a9bfc" grtype="null" id="GRmark_d3442d70f33f82ecfa8c0eab3c914e4a091a9bfc_,:2">,</span>j). You have to move to any square (x<span class="GRcorrect" grphrase="674ea6926729abee18840371de674670059cb683" grtype="null" id="GRmark_674ea6926729abee18840371de674670059cb683_,:0">,</span>y). In how many moves you could do it ?</span><br />
<span style="font-family: 'Trebuchet MS', sans-serif;">Find the <span class="GRcorrect" grphrase="82ee016926db776dc69b9cf566eb47259d75f74f" grtype="null" id="GRmark_82ee016926db776dc69b9cf566eb47259d75f74f_intemediate:0">intemediate</span> point.</span><br />
<span style="font-family: 'Trebuchet MS', sans-serif;">3) Given an array of integers, where each element of <span class="GRcorrect" grphrase="45bf7b225f5828e1d8f3f8ceb3a3adddbbc2bd25" grtype="null" id="GRmark_45bf7b225f5828e1d8f3f8ceb3a3adddbbc2bd25_array:0">array</span> represents <span class="GRcorrect" grphrase="45bf7b225f5828e1d8f3f8ceb3a3adddbbc2bd25" grtype="null" id="GRmark_45bf7b225f5828e1d8f3f8ceb3a3adddbbc2bd25_height:1">height</span> of a building. <span class="GRcorrect" grphrase="355def11a82f7e52dba3a4f6c0c9d80d8c54801f" grtype="null" id="GRmark_355def11a82f7e52dba3a4f6c0c9d80d8c54801f_Width:0">Width</span> of each building is 1. [ Think of it as histogram].</span><br />
<span style="font-family: 'Trebuchet MS', sans-serif;">It starts raining, so <span class="GRcorrect" grphrase="2752d74499259089ff957545ea657cc0c1b65142" grtype="null" id="GRmark_2752d74499259089ff957545ea657cc0c1b65142_water:0">water</span> will get accumulated between some buildings. Find the amount of water that will be accumulated.</span><br />
<span style="font-family: 'Trebuchet MS', sans-serif;"><br />
</span><br />
<span style="font-family: 'Trebuchet MS', sans-serif;">Round 4:</span><br />
<span style="font-family: 'Trebuchet MS', sans-serif;">1) Given a rod of length L, there are some positions marked on <span class="GRcorrect" grphrase="df114ed7e40d40a506299edc5dcf9e8cfbb4987c" grtype="null" id="GRmark_df114ed7e40d40a506299edc5dcf9e8cfbb4987c_rod:0">rod</span> at which the rod can be cut. The cost of cutting at any position is the current </span><span class="GRcorrect" grphrase="2036289d5b4569563ac77a5d04fce7d96b244daa" grtype="null" id="GRmark_2036289d5b4569563ac77a5d04fce7d96b244daa_length:0" style="background-color: transparent; font-family: 'Trebuchet MS', sans-serif;">length</span><span style="font-family: 'Trebuchet MS', sans-serif;"> of rod you are cutting. Like if the rod length is 10 and you can cut it at 4,9, cost of cutting at any position would be 10.</span><br />
<span style="font-family: 'Trebuchet MS', sans-serif;">Find the minimum cost of cutting the rod.</span><br />
<span style="font-family: 'Trebuchet MS', sans-serif;"><br />
</span><br />
<span style="font-family: 'Trebuchet MS', sans-serif;">2) What features would you suggest that should be added in Google+ to attract more users.</span><br />
<span style="font-family: 'Trebuchet MS', sans-serif;">What signals would you use to determine any particular interest of a user.</span><br />
<span style="font-family: 'Trebuchet MS', sans-serif;">More on similar topics, like suppose you have to design a page where top 100 posts by random users on Google+. What signals would you use to </span><span class="GRcorrect" grphrase="11872c36870d9e7fadeb08a77c637cf8be355c11" grtype="null" id="GRmark_11872c36870d9e7fadeb08a77c637cf8be355c11_determine:0" style="background-color: transparent; font-family: 'Trebuchet MS', sans-serif;">determine</span><span style="font-family: 'Trebuchet MS', sans-serif;"> that. How would you rank the posts on that page.</span><br />
<span style="font-family: 'Trebuchet MS', sans-serif;"><br />
</span><br />
<span style="font-family: 'Trebuchet MS', sans-serif;">Round 5:</span><br />
<span style="font-family: 'Trebuchet MS', sans-serif;">1) Questions on final year project.</span><br />
<span style="font-family: 'Trebuchet MS', sans-serif;">2) Design an interface on <span class="GRcorrect" grphrase="5db15052cd6e0e03235bc3dfff3bacfc2f81e8ce" grtype="null" id="GRmark_5db15052cd6e0e03235bc3dfff3bacfc2f81e8ce_cache:0">cache</span>. Then I was asked incremental questions <span class="GRcorrect" grphrase="ad98c7b240319eb42bb29d9fdbf9fafe86eb4ccf" grtype="null" id="GRmark_ad98c7b240319eb42bb29d9fdbf9fafe86eb4ccf_of:0">of</span> the code that I have written. Pointed some issues and I was </span><span class="GRcorrect" grphrase="9acf5de11a1995368f0f2b6e37ed909c61f1a8e6" grtype="null" id="GRmark_9acf5de11a1995368f0f2b6e37ed909c61f1a8e6_asked:0" style="background-color: transparent; font-family: 'Trebuchet MS', sans-serif;">asked</span><span style="font-family: 'Trebuchet MS', sans-serif;"> to correct them.</span><br />
<span class="GingerNoCheckEnd"></span></div></div></div>Arvind Mohanhttp://www.blogger.com/profile/09421036756092622107noreply@blogger.com0tag:blogger.com,1999:blog-7173134778831375674.post-58676219738297088742012-02-12T12:07:00.000+05:302012-02-12T12:07:00.081+05:30Blog # 77 : The Lonely Element<div dir="ltr" style="text-align: left;" trbidi="on"><script language="javascript">
function show(targetID) {
target = document.getElementById(targetID);
if (target.style.display == "none")
{ target.style.display = ""; }
}
function hide(targetID) {
target = document.getElementById(targetID);
target.style.display = "none";
}
function toggle(targetID) {
remark = document.getElementById(targetID + '_remark');
hint = document.getElementById(targetID + '_hint');
solution = document.getElementById(targetID + '_solution');
if (remark.style.display == "none" ) {
remark.style.display = "";
}
else if (hint.style.display == "none" ) {
hint.style.display = ""; return;
}
else if (solution.style.display == "none" ) {
solution.style.display = ""; return;
}
else {
remark.style.display = "none";
hint.style.display = "none";
solution.style.display = "none";
}
}
</script><br />
<div dir="ltr" style="text-align: left;" trbidi="on"><div style="font-family: "Trebuchet MS",sans-serif;"><table cellpadding="8" cellspacing="0" style="font-family: "Trebuchet MS",sans-serif;"><tbody>
<tr> <td valign="top"><div align="justify"><span style="font-size: small;">Given an array of integers with size 2N+1 such that N elements appear twice in arbitrary positions and 1 element appears only once.<br />
Devise an algorithm to find the lonely element.<br />
<br />
Ex : {1 2 4 5 1 4 2}<br />
Answer : 5<br />
<br />
<br />
courtesy: Syed Wali Hamza<br />
</span></div><div align="justify"><span style="font-size: small;">Click <a href="javascript:%20toggle('77');"><b>here</b></a> to see the solution.<br />
p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice.</span></div><br />
<div class="remark" id="77_remark" style="display: none;"><br />
<br />
<br />
<br />
<br />
<center><br />
<table><tbody>
<tr><td><table bgcolor="white" border="0" cellpadding="5" cellspacing="0" class="bodyline"><tbody>
<tr><td><div align="justify"><b><span style="font-size: small;">Remarks:</span></b> </div><span style="font-size: small;">No remarks. Hit again for hints.</span></td></tr>
</tbody></table><table border="0" cellpadding="0" cellspacing="0" class="tbl"><tbody>
<tr> </tr>
</tbody></table></td></tr>
</tbody></table></center></div><div class="hint" id="77_hint" style="display: none;"><br />
<br />
<br />
<br />
<br />
<br />
<center><br />
<table><tbody>
<tr><td><table bgcolor="white" border="0" cellpadding="5" cellspacing="0" class="bodyline"><tbody>
<tr><td><div align="justify"><b><span style="font-size: small;"> Hints:</span></b></div><span style="font-size: small;">Think of some bit manipulation techniques. Hit again for solution.</span></td></tr>
</tbody></table><table border="0" cellpadding="0" cellspacing="0" class="tbl"><tbody>
<tr> </tr>
</tbody></table></td></tr>
</tbody></table></center></div><div class="solution" id="77_solution" style="display: none;"><br />
<br />
<br />
<br />
<br />
<center><br />
<table><tbody>
<tr><td><table bgcolor="white" border="0" cellpadding="5" cellspacing="0" class="bodyline"><tbody>
<tr><td><div align="justify"><b><span style="font-size: small;">Solution:</span></b></div><span style="font-size: small;"><br />
Note the properties of XOR :<br />
1. A ^ A = 0<br />
2. 0 ^ A = A<br />
3. A ^ (B ^ C) = (A ^ B) ^ C<br />
Thus we just XOR all integers to finally get the lonely element since all others will be made 0 for repeating twice.<br />
<b>Complexity:</b><br />
1. Space: O(1)<br />
2. Time: O(N)<br />
</span><br />
<pre class="cpp" name="code">int lonely_element(int input[], int N){
int result=0, i=0;
for(i=0; i<N; i++)
result ^= input[i];
return result;
}
</pre></td></tr>
</tbody></table></td></tr>
</tbody></table></center></div></td> </tr>
</tbody></table></div></div></div>Arvind Mohanhttp://www.blogger.com/profile/09421036756092622107noreply@blogger.com0tag:blogger.com,1999:blog-7173134778831375674.post-33394738991318924922012-02-11T11:52:00.002+05:302012-02-11T11:52:00.268+05:30Blog # 76 : Checking the range of an array<div dir="ltr" style="text-align: left;" trbidi="on"><script language="javascript">
function show(targetID) {
target = document.getElementById(targetID);
if (target.style.display == "none")
{ target.style.display = ""; }
}
function hide(targetID) {
target = document.getElementById(targetID);
target.style.display = "none";
}
function toggle(targetID) {
remark = document.getElementById(targetID + '_remark');
hint = document.getElementById(targetID + '_hint');
solution = document.getElementById(targetID + '_solution');
if (remark.style.display == "none" ) {
remark.style.display = "";
}
else if (hint.style.display == "none" ) {
hint.style.display = ""; return;
}
else if (solution.style.display == "none" ) {
solution.style.display = ""; return;
}
else {
remark.style.display = "none";
hint.style.display = "none";
solution.style.display = "none";
}
}
</script><br />
<div dir="ltr" style="text-align: left;" trbidi="on"><div style="font-family: "Trebuchet MS",sans-serif;"><table cellpadding="8" cellspacing="0" style="font-family: "Trebuchet MS",sans-serif;"><tbody>
<tr> <td valign="top"><div align="justify"><span style="font-size: small;">Write a function that takes an int array of size M, and returns (true/false) if the array consists of the numbers only within the range [N, N+M-1]. The array is not guaranteed to be sorted. <br />
For instance, {2,3,4} would return true. {1,3,1} would return true, {1,2,4} would return false.<br />
<br />
<br />
courtesy: Vibhaj<br />
</span></div><div align="justify"><span style="font-size: small;">Click <a href="javascript:%20toggle('76');"><b>here</b></a> to see the solution.<br />
p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice.</span></div><br />
<div class="remark" id="76_remark" style="display: none;"><br />
<br />
<br />
<br />
<br />
<center><br />
<table><tbody>
<tr><td><table bgcolor="white" border="0" cellpadding="5" cellspacing="0" class="bodyline"><tbody>
<tr><td><div align="justify"><b><span style="font-size: small;">Remarks:</span></b> </div><span style="font-size: small;">No remarks. Hit again for hints.</span></td></tr>
</tbody></table><table border="0" cellpadding="0" cellspacing="0" class="tbl"><tbody>
<tr> </tr>
</tbody></table></td></tr>
</tbody></table></center></div><div class="hint" id="76_hint" style="display: none;"><br />
<br />
<br />
<br />
<br />
<br />
<center><br />
<table><tbody>
<tr><td><table bgcolor="white" border="0" cellpadding="5" cellspacing="0" class="bodyline"><tbody>
<tr><td><div align="justify"><b><span style="font-size: small;"> Hints:</span></b></div><span style="font-size: small;">No hint this time. Hit again for solution.</span></td></tr>
</tbody></table><table border="0" cellpadding="0" cellspacing="0" class="tbl"><tbody>
<tr> </tr>
</tbody></table></td></tr>
</tbody></table></center></div><div class="solution" id="76_solution" style="display: none;"><br />
<br />
<br />
<br />
<br />
<center><br />
<table><tbody>
<tr><td><table bgcolor="white" border="0" cellpadding="5" cellspacing="0" class="bodyline"><tbody>
<tr><td><div align="justify"><b><span style="font-size: small;">Solution:</span></b></div><span style="font-size: small;"><br />
Simply find out the maximum and minimum in one pass and check if N == (max - min + 1)<br />
<b>Complexity:</b><br />
1. Space: O(1)<br />
2. Time: O(N)<br />
</span><br />
<pre class="cpp" name="code">int check_range(int input[], int N){
int max = input[0], min = input[0], i;
for(i=1; i<N; i++){
if(input[i] < min) min=input[i];
if(input[i] > max) max=input[i];
}
return (max - min + 1) == N;
}
</pre></td></tr>
</tbody></table></td></tr>
</tbody></table></center></div></td> </tr>
</tbody></table></div></div></div>Arvind Mohanhttp://www.blogger.com/profile/09421036756092622107noreply@blogger.com2tag:blogger.com,1999:blog-7173134778831375674.post-38444871118988762372012-02-10T11:43:00.001+05:302012-02-10T11:43:00.204+05:30Blog # 75 : Catch the repetition<div dir="ltr" style="text-align: left;" trbidi="on"><br />
<script language="javascript">
gfunction show(targetID) {
target = document.getElementById(targetID);
if (target.style.display == "none")
{ target.style.display = ""; }
}
function hide(targetID) {
target = document.getElementById(targetID);
target.style.display = "none";
}
function toggle(targetID) {
remark = document.getElementById(targetID + '_remark');
hint = document.getElementById(targetID + '_hint');
solution = document.getElementById(targetID + '_solution');
if (remark.style.display == "none" ) {
remark.style.display = "";
}
else if (hint.style.display == "none" ) {
hint.style.display = ""; return;
}
else if (solution.style.display == "none" ) {
solution.style.display = ""; return;
}
else {
remark.style.display = "none";
hint.style.display = "none";
solution.style.display = "none";
}
}
</script><br />
<div dir="ltr" style="text-align: left;" trbidi="on"><div style="font-family: "Trebuchet MS",sans-serif;"><table cellpadding="8" cellspacing="0" style="font-family: "Trebuchet MS",sans-serif;"><tbody>
<tr> <td valign="top"><div align="justify"><span style="font-size: small;">Given an array of size N which contains all the numbers from 1 to N-1. Find the number which is repeated in O(N) time.<br />
How do you proceed with the same with floating numbers from 0 to 1 instead of 1 to N-1 ?<br />
<br />
<br />
courtesy: Vibhaj<br />
</span></div><div align="justify"><span style="font-size: small;">Click <a href="javascript:%20toggle('75');"><b>here</b></a> to see the solution.<br />
p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice.</span></div><br />
<div class="remark" id="75_remark" style="display: none;"><br />
<br />
<br />
<br />
<br />
<br />
<br />
<center><br />
<table><tbody>
<tr><td><table bgcolor="white" border="0" cellpadding="5" cellspacing="0" class="bodyline"><tbody>
<tr><td><div align="justify"><b><span style="font-size: small;">Remarks:</span></b> </div><span style="font-size: small;">No remarks. Hit again for hints.</span></td></tr>
</tbody></table><table border="0" cellpadding="0" cellspacing="0" class="tbl"><tbody>
<tr> </tr>
</tbody></table></td></tr>
</tbody></table></center></div><div class="hint" id="75_hint" style="display: none;"><br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<center><br />
<table><tbody>
<tr><td><table bgcolor="white" border="0" cellpadding="5" cellspacing="0" class="bodyline"><tbody>
<tr><td><div align="justify"><b><span style="font-size: small;"> Hints:</span></b></div><span style="font-size: small;">No hint this time. Hit again for solution.</span></td></tr>
</tbody></table><table border="0" cellpadding="0" cellspacing="0" class="tbl"><tbody>
<tr> </tr>
</tbody></table></td></tr>
</tbody></table></center></div><div class="solution" id="75_solution" style="display: none;"><br />
<br />
<br />
<br />
<br />
<br />
<br />
<center><br />
<table><tbody>
<tr><td><table bgcolor="white" border="0" cellpadding="5" cellspacing="0" class="bodyline"><tbody>
<tr><td><div align="justify"><b><span style="font-size: small;">Solution:</span></b></div><span style="font-size: small;"><br />
For integers use sum to find the repeated number.<br />
For floating numbers, use Hash tables.<br />
<b>Complexity:</b><br />
1. Space: O(1) [O(K), K >> N for hash table]<br />
2. Time: O(N)<br />
</span><br />
<pre class="cpp" name="code">int repetition_int(int input[], int N){
int i=0, sum=0;
for(i=0; i<N; i++)
sum += input[i];
return sum - (N*(N-1)/2);
}
float repetition_float(float input[], int N){
int i;
for(i=0; i<N; i++){
if(hash_table_exists(input[i]))
return input[i];
hash_table_insert(input[i]);
}
return -1.0;
}
</pre></td></tr>
</tbody></table></td></tr>
</tbody></table></center></div></td> </tr>
</tbody></table></div></div></div>Arvind Mohanhttp://www.blogger.com/profile/09421036756092622107noreply@blogger.com0tag:blogger.com,1999:blog-7173134778831375674.post-52843876938613520262012-02-09T12:01:00.000+05:302012-02-09T12:01:00.338+05:30Blog # 74 : Truth is all about the question you ask!<div dir="ltr" style="text-align: left;" trbidi="on"><script language="javascript">
function show(targetID) {
target = document.getElementById(targetID);
if (target.style.display == "none")
{ target.style.display = ""; }
}
function hide(targetID) {
target = document.getElementById(targetID);
target.style.display = "none";
}
function toggle(targetID) {
remark = document.getElementById(targetID + '_remark');
hint = document.getElementById(targetID + '_hint');
solution = document.getElementById(targetID + '_solution');
if (remark.style.display == "none" ) {
remark.style.display = "";
}
else if (hint.style.display == "none" ) {
hint.style.display = ""; return;
}
else if (solution.style.display == "none" ) {
solution.style.display = ""; return;
}
else {
remark.style.display = "none";
hint.style.display = "none";
solution.style.display = "none";
}
}
</script><br />
<div dir="ltr" style="text-align: left;" trbidi="on"><div style="font-family: "Trebuchet MS",sans-serif;"><table cellpadding="8" cellspacing="0" style="font-family: "Trebuchet MS",sans-serif;"><tbody>
<tr> <td valign="top"><div align="justify"><span style="font-size: small;">You are walking down a path when you come to two doors. Opening one of the doors will lead you to a life of prosperity and happiness, while opening the other door will lead to a life of misery and sorrow. You don't know which door leads to which life. In front of the doors are two twin brothers who know which door leads where. One of the brothers always lies, and the other always tells the truth. You don't know which brother is the liar and which is the truth-teller. You are allowed to ask one single question to one of the brothers (not both) to figure out which door to open.<br />
What question should you ask?<br />
<br />
</span></div><div align="justify"><span style="font-size: small;">Click <a href="javascript:%20toggle('74');"><b>here</b></a> to see the solution.<br />
p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice.</span></div><br />
<div class="remark" id="74_remark" style="display: none;"><br />
<br />
<br />
<br />
<br />
<br />
<center><br />
<table><tbody>
<tr><td><table bgcolor="white" border="0" cellpadding="5" cellspacing="0" class="bodyline"><tbody>
<tr><td><div align="justify"><b><span style="font-size: small;">Remarks:</span></b> </div><span style="font-size: small;">No remarks. Hit again for hints.</span></td></tr>
</tbody></table><table border="0" cellpadding="0" cellspacing="0" class="tbl"><tbody>
<tr> </tr>
</tbody></table></td></tr>
</tbody></table></center></div><div class="hint" id="74_hint" style="display: none;"><br />
<br />
<br />
<br />
<br />
<br />
<br />
<center><br />
<table><tbody>
<tr><td><table bgcolor="white" border="0" cellpadding="5" cellspacing="0" class="bodyline"><tbody>
<tr><td><div align="justify"><b><span style="font-size: small;"> Hints:</span></b></div><span style="font-size: small;">Doesn't the question name ring a bell itself. Hit again for solution.</span></td></tr>
</tbody></table><table border="0" cellpadding="0" cellspacing="0" class="tbl"><tbody>
<tr> </tr>
</tbody></table></td></tr>
</tbody></table></center></div><div class="solution" id="74_solution" style="display: none;"><br />
<br />
<br />
<br />
<br />
<br />
<center><br />
<table><tbody>
<tr><td><table bgcolor="white" border="0" cellpadding="5" cellspacing="0" class="bodyline"><tbody>
<tr><td><div align="justify"><b><span style="font-size: small;">Solution:</span></b></div><span style="font-size: small;"><br />
<br />
Ask "If I asked your brother what the good door is, what would he say ?". Both would point to wrong door.<br />
</span><br />
<br />
</td></tr>
</tbody></table></td></tr>
</tbody></table></center></div></td> </tr>
</tbody></table></div></div></div>Arvind Mohanhttp://www.blogger.com/profile/09421036756092622107noreply@blogger.com0tag:blogger.com,1999:blog-7173134778831375674.post-47079631003698852122012-02-08T12:05:00.000+05:302012-02-08T12:05:00.538+05:30Blog # 73 : The hourglass<div dir="ltr" style="text-align: left;" trbidi="on"><script language="javascript">
function show(targetID) {
target = document.getElementById(targetID);
if (target.style.display == "none")
{ target.style.display = ""; }
}
function hide(targetID) {
target = document.getElementById(targetID);
target.style.display = "none";
}
function toggle(targetID) {
remark = document.getElementById(targetID + '_remark');
hint = document.getElementById(targetID + '_hint');
solution = document.getElementById(targetID + '_solution');
if (remark.style.display == "none" ) {
remark.style.display = "";
}
else if (hint.style.display == "none" ) {
hint.style.display = ""; return;
}
else if (solution.style.display == "none" ) {
solution.style.display = ""; return;
}
else {
remark.style.display = "none";
hint.style.display = "none";
solution.style.display = "none";
}
}
</script><br />
<div dir="ltr" style="text-align: left;" trbidi="on"><div style="font-family: "Trebuchet MS",sans-serif;"><table cellpadding="8" cellspacing="0" style="font-family: "Trebuchet MS",sans-serif;"><tbody>
<tr> <td valign="top"><div align="justify"><span style="font-size: small;">You have two sand hourglasses, one that measures exactly 4 minutes and one that measures exactly 7 minutes. You need to measure out exactly 2 minutes. <br />
Using only these two hourglasses, how can you measure out exactly 2 minutes ?<br />
<br />
</span></div><div align="justify"><span style="font-size: small;">Click <a href="javascript:%20toggle('73');"><b>here</b></a> to see the solution.<br />
p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice.</span></div><br />
<div class="remark" id="73_remark" style="display: none;"><br />
<br />
<br />
<center><br />
<table><tbody>
<tr><td><table bgcolor="white" border="0" cellpadding="5" cellspacing="0" class="bodyline"><tbody>
<tr><td><div align="justify"><b><span style="font-size: small;">Remarks:</span></b> </div><span style="font-size: small;">No remarks. Hit again for hints.</span></td></tr>
</tbody></table><table border="0" cellpadding="0" cellspacing="0" class="tbl"><tbody>
<tr> </tr>
</tbody></table></td></tr>
</tbody></table></center></div><div class="hint" id="73_hint" style="display: none;"><br />
<br />
<br />
<br />
<br />
<br />
<center><br />
<table><tbody>
<tr><td><table bgcolor="white" border="0" cellpadding="5" cellspacing="0" class="bodyline"><tbody>
<tr><td><div align="justify"><b><span style="font-size: small;"> Hints:</span></b></div><span style="font-size: small;">Just think what type of actions can be responsbile for such result? Hit again for solution.</span></td></tr>
</tbody></table><table border="0" cellpadding="0" cellspacing="0" class="tbl"><tbody>
<tr> </tr>
</tbody></table></td></tr>
</tbody></table></center></div><div class="solution" id="73_solution" style="display: none;"><br />
<br />
<br />
<br />
<br />
<center><br />
<table><tbody>
<tr><td><table bgcolor="white" border="0" cellpadding="5" cellspacing="0" class="bodyline"><tbody>
<tr><td><div align="justify"><b><span style="font-size: small;">Solution:</span></b></div><span style="font-size: small;"><br />
<br />
7x - 4y = 2<br />
we have a simple soultion, x=2 and y=3<br />
We have 7*2 - 4*3 = 2<br />
So we start both simultaneously.<br />
When 4 completes invert it, next invert 7 when done, next invert 4 when done again twice. Time remaining for 7 to finish is 2 minutes now.<br />
</span><br />
<br />
</td></tr>
</tbody></table></td></tr>
</tbody></table></center></div></td> </tr>
</tbody></table></div></div></div>Arvind Mohanhttp://www.blogger.com/profile/09421036756092622107noreply@blogger.com0tag:blogger.com,1999:blog-7173134778831375674.post-73945390137985038042012-01-29T11:45:00.001+05:302012-01-29T11:45:00.273+05:30Blog # 72 : No mathematical operator<div dir="ltr" style="text-align: left;" trbidi="on"><script language="javascript">
function show(targetID) {
target = document.getElementById(targetID);
if (target.style.display == "none")
{ target.style.display = ""; }
}
function hide(targetID) {
target = document.getElementById(targetID);
target.style.display = "none";
}
function toggle(targetID) {
remark = document.getElementById(targetID + '_remark');
hint = document.getElementById(targetID + '_hint');
solution = document.getElementById(targetID + '_solution');
if (remark.style.display == "none" ) {
remark.style.display = "";
}
else if (hint.style.display == "none" ) {
hint.style.display = ""; return;
}
else if (solution.style.display == "none" ) {
solution.style.display = ""; return;
}
else {
remark.style.display = "none";
hint.style.display = "none";
solution.style.display = "none";
}
}
</script><br />
<div dir="ltr" style="text-align: left;" trbidi="on"><div style="font-family: "Trebuchet MS",sans-serif;"><table cellpadding="8" cellspacing="0" style="font-family: "Trebuchet MS",sans-serif;"><tbody>
<tr> <td valign="top"><div align="justify"><span style="font-size: small;">Write a function to add two integers without using mathematical operators (+, -, *, /).<br />
<br />
</span></div><div align="justify"><span style="font-size: small;">Click <a href="javascript:%20toggle('72');"><b>here</b></a> to see the solution.<br />
p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice.</span></div><div align="justify"><br />
<span style="font-size: small;">Courtesy: Vibhaj</span></div><div class="remark" id="72_remark" style="display: none;"><br />
<br />
<br />
<br />
<center><br />
<table><tbody>
<tr><td><table bgcolor="white" border="0" cellpadding="5" cellspacing="0" class="bodyline"><tbody>
<tr><td><div align="justify"><b><span style="font-size: small;">Remarks:</span></b> </div><span style="font-size: small;">No remarks. Hit again for hints.</span></td></tr>
</tbody></table><table border="0" cellpadding="0" cellspacing="0" class="tbl"><tbody>
<tr> </tr>
</tbody></table></td></tr>
</tbody></table></center></div><div class="hint" id="72_hint" style="display: none;"><br />
<br />
<br />
<br />
<br />
<center><br />
<table><tbody>
<tr><td><table bgcolor="white" border="0" cellpadding="5" cellspacing="0" class="bodyline"><tbody>
<tr><td><div align="justify"><b><span style="font-size: small;"> Hints:</span></b></div><span style="font-size: small;">No hint, think properly. One thing for sure you'll have to use some operators that are not mathematical. Hit again for solution.</span></td></tr>
</tbody></table><table border="0" cellpadding="0" cellspacing="0" class="tbl"><tbody>
<tr> </tr>
</tbody></table></td></tr>
</tbody></table></center></div><div class="solution" id="72_solution" style="display: none;"><br />
<br />
<br />
<br />
<center><br />
<table><tbody>
<tr><td><table bgcolor="white" border="0" cellpadding="5" cellspacing="0" class="bodyline"><tbody>
<tr><td><div align="justify"><b><span style="font-size: small;">Solution:</span></b></div><span style="font-size: small;"><br />
<br />
We use the logic used in digital circuits where sum = A XOR B and carry = A AND B. We simply add the carry again after shifting it 1 left till it become zero.<br />
<br />
<b>Complexity:</b><br />
1. Time: O(1)<br />
2. Space: O(1)<br />
<br />
<b>Code:</b><br />
</span><br />
<pre class="cpp" name="code">int add(int a, int b){
int carry = 0;
while(b){
carry = a & b;
a = a ^ b;
b = carry << 1;
}
return a;
}
</pre><br />
</td></tr>
</tbody></table></td></tr>
</tbody></table></center></div></td> </tr>
</tbody></table></div></div></div>Arvind Mohanhttp://www.blogger.com/profile/09421036756092622107noreply@blogger.com0tag:blogger.com,1999:blog-7173134778831375674.post-45375453370000096652012-01-28T11:00:00.001+05:302012-01-28T11:00:01.804+05:30Blog # 71 : Largest "absolute" sum<div dir="ltr" style="text-align: left;" trbidi="on"><script language="javascript">
function show(targetID) {
target = document.getElementById(targetID);
if (target.style.display == "none")
{ target.style.display = ""; }
}
function hide(targetID) {
target = document.getElementById(targetID);
target.style.display = "none";
}
function toggle(targetID) {
remark = document.getElementById(targetID + '_remark');
hint = document.getElementById(targetID + '_hint');
solution = document.getElementById(targetID + '_solution');
if (remark.style.display == "none" ) {
remark.style.display = "";
}
else if (hint.style.display == "none" ) {
hint.style.display = ""; return;
}
else if (solution.style.display == "none" ) {
solution.style.display = ""; return;
}
else {
remark.style.display = "none";
hint.style.display = "none";
solution.style.display = "none";
}
}
</script><br />
<div dir="ltr" style="text-align: left;" trbidi="on"><div style="font-family: "Trebuchet MS",sans-serif;"><table cellpadding="8" cellspacing="0" style="font-family: "Trebuchet MS",sans-serif;"><tbody>
<tr> <td valign="top"><div align="justify"><span style="font-size: small;">Given an array of N integers (both positive and negative), find the sub-sequence with largest absolute sum.<br />
For ex: Let A = {1 2 -5 4 5 -1 2 -11} then largest absolute sum is 11 with sub-sequence {-11}.<br />
<br />
</span></div><div align="justify"><span style="font-size: small;"><br />
</span></div><div align="justify"><span style="font-size: small;">Click <a href="javascript:%20toggle('71');"><b>here</b></a> to see the solution.<br />
p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice.</span></div><div align="justify"><br />
<span style="font-size: small;"><br />
</span><br />
<span style="font-size: small;">Courtesy: Vibhaj</span></div><div class="remark" id="71_remark" style="display: none;"><br />
<br />
<center><br />
<table><tbody>
<tr><td><table bgcolor="white" border="0" cellpadding="5" cellspacing="0" class="bodyline"><tbody>
<tr><td><div align="justify"><b><span style="font-size: small;">Remarks:</span></b> </div><span style="font-size: small;">A simpler variant was previously discussed [Largest consecutive sum]. Hit again for hints.</span></td></tr>
</tbody></table><table border="0" cellpadding="0" cellspacing="0" class="tbl"><tbody>
<tr> </tr>
</tbody></table></td></tr>
</tbody></table></center></div><div class="hint" id="71_hint" style="display: none;"><br />
<br />
<br />
<center><br />
<table><tbody>
<tr><td><table bgcolor="white" border="0" cellpadding="5" cellspacing="0" class="bodyline"><tbody>
<tr><td><div align="justify"><b><span style="font-size: small;"> Hints:</span></b></div><span style="font-size: small;">Compare the maximum positive and negative sum. Hit again for solution.</span></td></tr>
</tbody></table><table border="0" cellpadding="0" cellspacing="0" class="tbl"><tbody>
<tr> </tr>
</tbody></table></td></tr>
</tbody></table></center></div><div class="solution" id="71_solution" style="display: none;"><br />
<br />
<center><br />
<table><tbody>
<tr><td><table bgcolor="white" border="0" cellpadding="5" cellspacing="0" class="bodyline"><tbody>
<tr><td><div align="justify"><b><span style="font-size: small;">Solution:</span></b></div><span style="font-size: small;"><br />
<br />
We use the same algorithm of O(N) here too first to get highest positive sum and then highest negative sum and find the one with higher absolute value as the answer.<br />
<br />
<b>Complexity:</b><br />
1. Time: O(N)<br />
2. Space: O(1)<br />
<br />
<b>Code:</b><br />
</span><br />
<pre class="cpp" name="code">void largest_consecutive_sum(int input[], int N, int *start, int *end, int *max){
*start = *end = *max = -1;
int current = -1;
int sum = 0;
for(int i=0; i<N; i++){
sum += input[i];
if(sum < 0){
sum = 0;
current = i+1;
}
if(sum > *max){
*max = sum;
*start = current;
*end = i;
}
}
}
void largest_consecutive_absolute_sum(int input[], int N, int *start, int *end, int *max){
int pos_start, pos_end, pos_max, neg_start, neg_end, neg_max;
int i;
largest_consecutive_sum(input, N, &pos_start, &pos_end, &pos_max);
for(i=0; i<N; i++){
input[i] = -1*input[i];
}
largest_consecutive_sum(input, N, &neg_start, &neg_end, &neg_max);
if(pos_max > neg_max){
*start = pos_start;
*end = pos_end;
*max = pos_max;
}
else {
*start = neg_start;
*end = neg_end;
*max = neg_max;
}
}
</pre><br />
</td></tr>
</tbody></table></td></tr>
</tbody></table></center></div></td> </tr>
</tbody></table></div></div></div>Arvind Mohanhttp://www.blogger.com/profile/09421036756092622107noreply@blogger.com0