Testing Zone Recommended Books Important CS Topics at a Glance Common programming interview questions Puzzle Type Problems Hints, code and solutions to selected questions Testing Zone For ProgrammersTry out our online MultipleChoiceQuestion tests in Programming and Computer Science!Important Topics at a GlanceBefore getting to the questions and answers, here are some of the essential data structures and algorithms, which you need to know thoroughly:

Tree Data Structures 

Binary Search Trees  Heaps  Height Balanced Trees  
Graphs and Graph Algorithms  
Depth First Search 
Breadth First Search  Minimum Spanning Trees: Kruskal Algorithm 
Minumum Spanning Trees: Prim's Algorithm 
Dijkstra Algorithm for Shortest Paths 
Floyd Warshall Algorithm for Shortest Paths 
Bellman Ford Algorithm 

Popular Algorithms in Dynamic Programming  
Dynamic Programming 
Integer Knapsack problem  Matrix Chain Multiplication  Longest Common Subsequence 
Greedy Algorithms 

Elementary cases : Fractional Knapsack Problem, Task Scheduling 
Data Compression using Huffman Trees 
A Collection of commonly asked programming interview questions  from Google,Amazon,Facebook,Microsoft interviews and placement tests(Answers/Hints at the end of the page)
Questions
Q1.Write a code in C to reverse a LinkedList?[Google Interview Question]
Q2. Given an array of Integers (Both +ve and ve numbers), in random order, Then find the subarray with the largest sum.[Google Interview Question]
Q3.A man pushed his car to a hotel and lost his fortune. What happened?[Google Interview Question]
Q4.What is the difference between a mutex and a semaphore?What one of them would you like to use to protect to an increment operation?[Google Interview Question]
Q5.Describe the Algorithm for DepthFirst graph Traversal.[Google Interview Question]
Q6.What is the space complexity of a Quicksort Algorithm and how do you find it?[Google Interview Question]
Q7.How are cookies passed in the HTTP protocol?[Google Interview Question]
A7.The Server sends a SetCookie: name=value to the client, in response to the header to set the field. If there is a cookie then the client sends a Cookie: name = value in its request header.
Q8.Design a SQL database tables for a car rental.[Google Interview Question]
Q9.How will you search for a word in a very large database?[Google Interview Question]
Q10.You are given three strings A,B,C. Now you have to check whether the 3rd string is interleaved from string A and B.[Google Interview Question]
Q11.There are two arrays A and B.Now Answer the following:
a)Find the intersection of A and B.
b)If array A is small and array B id too large then who will you proceed or change the procedure used previously to find the intersection.[Google Interview Question]
Q12.What is TCP,UDP?What is reliability,unreliability and also give examples respectively.[Google Interview Question]
Q13.Explain a database in three sentences to your eightyearold nephew.[Google Interview Question]
Q14.Explain the functioning/working of Google search engine.[Google Interview Question]
Q15.Give a C Code which can measure the speed of a context switch on a LINUX/UNIX system.[Google Interview Question]
Q16.Design a class library for writing card games.[Google Interview Question]
Q17.You are given a function that generates a random number from 1 to 6. Now write a code that generates a number from 1 to 7, using that given function.[Google Interview Question]
Q18.In java differentiate between final,finally,finalize.[Google Interview Question]
Q19.Given two linked list, how will you find the intersection of the two lists.i.e. return the list containing the elements common in both.[Google Interview Question]
Q20.Explain the working of congestion control in the TCP protocol.[Google Interview Question]
Q21.Give is the size of the C structure below on a 32bit system and on a 64bit.[Google Interview Question]
struct foo
{
char a;
char* b;
};Q22.Write a function f(a,b) that takes two strings and returns a string containing only the characters found in both the strings in the order of a.Give the solution in O(N^2) and O(N).[Google Interview Question]
Q23.Explain the terms Multithreading programming and Deadlocks.[Google Interview Question]
Q24.You are given a circularly sorted integers, then tell how will you find a given integer?[Google Interview Question]
Q25.What the difference between hashtable and hashmap?[Google Interview Question]
Q26.What is the significance of the term “dead beef“?[Google Interview Question]
Q27.What are dangling pointer?[Google Interview Question]
Q28.In an array, how will you find the minimun and maximum in less number of comparisions?[Google Interview Question]
Q29.What sorting algorithm would you use for a very large data set on the disk but less space in memory?[Google Interview Question]
Q30.You are given a string of length N and M small strings each of length L.How will you find that each of the M strings occurred in the larger string?[Google Interview Question]
Q31.Write the elements of a binary search tree while traversing it using the BFS algorithm. Construct a tree with atleast 4 levels and traverse over it.[Microsoft Interview Question]
Q32.Write a function to combine two 2 sorted linked list, and get the new list in sorted form, without using any temporary Node.[Microsoft Interview Question]
Q33.Given a set of coins {50,25,10,5,1} inside a box. Now write a program than can create a 1 Rs by grouping of these coins.[Microsoft Interview Question]
Q34. Write a code that will remove the duplicates from a sorted array.[Microsoft Interview Question]
Q35.Given an array of characters. Then reverse the order of the words in that array.[Microsoft Interview Question]
Q36.What does the ERROR_PROCEDURE() function return?The name of the stored procedure that caused an error.[Microsoft Interview Question]
Q37. How do you use RSA for both authentication and secrecy?[Microsoft Interview Question]
Q38.Write a code in C that can print “hello world” without using any semicolon in the code.
Q39.Write a code that can find the sum of values in the leftsubtree nodes after entering the root node of the tree.[Microsoft Interview Question]
Q40.Give the algorithm from a preorder traversal of a binary tree represented in a 2D array.[Microsoft Interview Question]
Q41.What are the various problems faced by using distributed database Systems?[Microsoft Interview Question]
Q42.What is the difference between asp and asp.net?[Microsoft Interview Question]
Q43.Write a function to check if the two rectangles overlap or not. The structure is as follows:
struct rect{
int top, bot, left, right;
} r1, r2;
[Microsoft Interview Question]
Q44.How is garbage collected in java?[Microsoft Interview Question]
Q45.Write the “ping” method in java.[Microsoft Interview Question]
Q46.How will you find the size of a java object.[Microsoft Interview Question]
Q47.Give reasons for not providing multiple inheritance in java.[Microsoft Interview Question]
Q48.What is DMA?[Microsoft Interview Question]
Q49.Write a program that can generate the nth fibonacci number.[Microsoft Interview Question]
Q50.Design a class library to writing game cards.[Microsoft Interview Question]
Q51.You are given a set of pointers pointing to very large strings. Find the pointer to the lexicographically smallest and largest strings.[Microsoft Interview Question]
Q52.In UNIX, how are the file blocks stored in the disk.Is is continuous?[Microsoft Interview Question]
Q53.What is disk interleaving and why is it adopted?[Microsoft Interview Question]
Q54.Write a C code for 'tr' program. 'tr' has two command line arguments. They both are strings of same length. tr reads an input file, replaces each character in the first string with the corresponding character in the second string. eg. 'tr abc xyz' replaces all 'a's by 'x's, 'b's by 'y's and so on. ANS.
a) have an array of length 26.
b)put 'x' in array element corr to 'a'
put 'y' in array element corr to 'b'
put 'z' in array element corr to 'c'
put 'd' in array element corr to 'd'
put 'e' in array element corr to 'e'
and so on.[Microsoft Interview Question]
Q55.Assume that deadlocks can occur only due to locks.Now give a method that can avoid deadlocks in a system.[Microsoft Interview Question]
Q56.Give the names of some routing protocols.[Microsoft Interview Question]
Q57.What are digital signatures and smart cards?[Microsoft Interview Question]
Q58.Write a function that can print out a 2D array in a spiral way.[Microsoft Interview Question]
Q59.You are given a sorted linked list.How will you insert an element in the list so that the sorted order retains?[Microsoft Interview Question]
Q60.Give the difference between a latch and a flipflop.[Microsoft Interview Question]
Q61.Given two numbers m,n. Now write a function that returns the first integer r that is divisible by both m and n.[Amazon Interview Question]
Q62.Write a C program that can copy a linked list.[Amazon Interview Question]
Q63.Give the four basics of Object Oriented Programming.[Amazon Interview Question]
Q64.What is Data Abstract and what is its importance.[Amazon Interview Question]
Q65.How will you compare two linked list.Write a code.[Amazon Interview Question]
Q66.Write a C code that can find the depth of a tree.[Amazon Interview Question]
Q67.What does the “top” command in linux do?[Amazon Interview Question]
Q68.Father's age is three years more than three times the son's age.After three years, father's age will be ten years more than twice the son's age. What is the father's present age?[Amazon Interview Question]
Q69.Write a function that takes two parameters, one a regular expression and the other a string and returns whether the string matches the regular expression or not.[Amazon Interview Question]
Q70.You are given an array of size n+1 which contains all the numbers from 1 to n. Now you have to find the number which is repeated in O(n) time. Also tell how do you proceed with the same with floating numbers from 0 to 1 instead of 1 to n?[Amazon Interview Question]
Q71.Give the output of the following program.[Amazon Interview Question]
main()
{
int a[8][10],c=0,i,j;
for(i=0;i<10;i++)
for(j=0;j<8;j++)
a[j][i]=c++;
printf("%d",a[3][6]);
}Q72.Give the time and space complexity of merge sort.[Amazon Interview Question]
Q73.What is a C array and how it is different from a list?[Amazon Interview Question]
Q74.Give the postfix and prefix notation of the following:
(a+b)*c(d+e)^(fg).[Amazon Interview Question]
Q75.What is the difference between sleep() and wait() in java.[Amazon Interview Question]
Q76.What happens if the parent process of a child exits before the child?[Amazon Interview Question]
Q77.Write a shell command to find all the files that end with java in the nested directories.[Amazon Interview Question]
Q78.Which of the following are valid in c++:
char *cp; or const char *cpp[Amazon Interview Question]
Q79.Given two linked list and they meet at a point.Write a code to find how will you find that point.[Amazon Interview Question]
Q80.There is a very large array, in which all the numbers are repeated once except one number. Tell how will you find that number.[Amazon Interview Question]
Q81.Write a code to find the number of elements in a tree.[Amazon Interview Question]
Q82.What are heterogeneous linked list and what kind of pointers will you use to implement it?[Amazon Interview Question]
Q83.Write a code to delete a tree in C.[Amazon Interview Question]
Q84.Explain polymorphism with an Example.[Amazon Interview Question]
Q85. Write a code that can swap two variables without using an extra memory.[Amazon Interview Question]
Q86.Differentiate between deep copy and shallow copy.[Amazon Interview Question]
Q87.Given a binary tree, you have to find the kth smallest element without using any static or global variables. You also can’t pass k to any other function.[Amazon Interview Question]
Q88.Write a code to convert a decimal number to a hexadecimal equivalent.[Amazon Interview Question]
Q89.Given an employee table with attributes name and salary, now find the name of the employee with the second highest salary.[Amazon Interview Question]
Q90.Find all the tennis playing pairs from a given table of players with S.no and player name.[Amazon Interview Question]
Q91.What is the major difference between C and C++?[Amazon Interview Question]
Q92.What is wrong in the following statement?
std::auto_ptr ptr(new char[10]); [Amazon Interview Question]
Q93.Is it possible to build a C++ compliers on top of a C complier?How will you do the same if possible?[Amazon Interview Question]
Q94.What is the output of the following program? [Amazon Interview Question]
void main()
{
int c=5;
printf("%d\n%d\n%d",c,c<<2,c>> 2);
}Q95.Figure out the error in the following program:[Amazon Interview Question]
int main()
{
char *p,*q;
p=(char *)malloc(25);
q=(char*) malloc(25);
strcpy(p,"amazon" );
strcpy(q,"hyd");
strcat(p,q);
printf("%s",p);
}Q96.When will the following function always return true:[Amazon Interview Question]
fun (node *p)
{
return ((p==null)(p>next==null) (p>info<=p>next>info)&&( fun(p>next)));
}Q97.Write a command to kill a process.[Amazon Interview Question]
Q98.Write a code for level order traversal of a tree.[Amazon Interview Question]
Q99.You are given the following:
a)3 type of vehicle:Motorbike, Car, and a car for the handicapped.
b)3 type of parking:Motorbike parking, Car parking and handicapped car parking.
c)Motorbike and Cars can park only at the designated parking, but the handicapped can park either on their own parking or the regular car parking.
Explain how will you model your class and your methods.[Amazon Interview Question]
Q100.Write a linux command that can find all the files in a directory that contains an IP address.[Amazon Interview Question]
Q101.Implement a read/write lock using the mutex that has lock() and trylock() as its interface.[Facebook Interview Question]
Q102.Give a data Structure that can support the two operations: insert() and get_median().[Facebook Interview Question]
Q103.Write a code to update a black and white coin game.[Facebook Interview Question]
Q104.Write a code to implement a dir*.[Facebook Interview Question]
Q105.Given the root of a binary search tree along with a node inside it, find the successor node for the given node.[Facebook Interview Question]
Q106.Say u use a SVN for source control and have several revisions of a file say r1,r2,r3 and so on. And someone checked in a bug and the revision became bad. Now to find the bad revision write a function findBadRevision(int goodRevision, int BadRevision). Say for example the revisions are GGBB, so the functions will take 0,4 and returns 2 as after two revisions a bad revision came up. There is also a function hasBug(int revision) which tells if that revision has a bug or not.[Facebook Interview Question]
Q107.Write a function that can tell that a polygon is simple or not based on the the set of points of the polygon.[Facebook Interview Question]
Q108.You are given an array of integers, now write a code to check if there exists three integers that add up to zero.[Facebook Interview Question]
Q109.Write a code to reverse a linked list.[Facebook Interview Question]
Q110.You are given a m*n grid, starting at (1,1). At any point (x,y) you can chose one of the following:
a)Go to (x+y,x);
b)go to (x,y+x);
Now how can u move to (m,n) with minimum number of moves, if possible.[Facebook Interview Question]
Q111.Given a set of login and logout pairs of users, write a function that can show the number of users online at any given point of time.[Facebook Interview Question]
Q112.Implement the "see and tell" algorithm with a given seed number x and a number of iterations y. You have to output the result on iterations y.[Facebook Interview Question]
Q113.Given a lot of intervals [ai,bi], you have to find a point with the intersection of most number of intervals.[Facebook Interview Question]
Q114.How to find the intersection of n sets without using hash tables.[Facebook Interview Question]
Q115.Write a code to compute the cubic root of a number.What is its complexity.[Facebook Interview Question]
Q116.Write a program to implement a LRU(Least Recently used) cache.[Facebook Interview Question]
Q117.Given a matrix with only binary numbers. Write a code that can find the groups of 1’s. A group is defined by horizontal or vertical adjacent 1’s.[Facebook Interview Question]
Q118.You are given a set of numbers and an integer k. Now you have to find all the possible subset of the set with size k.Write the time complexity for your algorithm.[Facebook Interview Question]
Q119.Write a function to multiply two big integers that can’t be stored in a buildin integer type. How will you represent big integers as data structures.[Facebook Interview Question]
Q120. Write a code to implement atof() of C.[Facebook Interview Question]
Q121.Write a code to implement Sqrt(double k) efficiently.[Facebook Interview Question]
Q122.How to implement multiple Inheritance in Java?[Facebook Interview Question]
Q123.You are given a double[] probs array that stores the probability of various coins of showing up heads.(Each coins has a unique probability of showing up heads).Output all the different cases along with their probabilities.[Facebook Interview Question]
Q124.Write a program that takes a tree and prints out elements of each level at the same line.For eample Let A be root and B and C be its children, Then output:[Facebook Interview Question]
A
B C
Q125.Write a function sqrt(number,precision), it take a number and precision and returns a number in between the numbers squareroot(number)precision and squareroot(number) + precision.[Facebook Interview Question]
Q126.Find the max sum of a subsequence from an array of positive integers where no two number in the subsequence are adjacent to each other in the array.[Facebook Interview Question]
Q127.You are given an array, now you want to erase all the zeros from the array and want the resultant array to have no empty cells.[Facebook Interview Question]
Q128.Write a code that can print out all the prime numbers in a given string.eg:abc2134kd31 > 2, 13, 3, 3[Facebook Interview Question]
Q129.How will you design a tinyURL?[Facebook Interview Question]
Q130.You are given a BST and you have to iterate over it without using recursion.[Facebook Interview Question]
Q131.Implement the queue data structure using the stack data structure. Give the time complexity of enqueue and dequeue operations of the implemented data structure.[Facebook Interview Question]
Q132.Given a set of nonoverlapping integer range and an input integer, now design a data structure to store them and have operations of insert,delete and search on that element.[Facebook Interview Question]
Q133.Find all the permutations of a telephone number given that 1=abc , 2=def , 3=ghi and so on.[Facebook Interview Question]
Q134.Write a code to remove all the duplicate characters from a string.The characters need not be consecutive in the string.[Facebook Interview Question]
Q135.Write a program that can print a singlylinked list backwards, in constant space and linear time.[Facebook Interview Question]
Q136.Write a program to tell whether two lines intersect or not.[Facebook Interview Question]
Q137.Write an algorithm to find the largest sub array with maximum sum of an array of integers.[Facebook Interview Question]
Q138.Write a function to implement log2() using sqrt() function.[Facebook Interview Question]
Q139.Write a code to convert an ASCII representation of a positive integer to its numeric value.[Facebook Interview Question]
Q140.Write a function to find the longest path in a binary tree.[Facebook Interview Question]
Q141.How will you find the min depth of a BST.[Facebook Interview Question]
Q142.Implement the divide operator without using / or % operator.[Facebook Interview Question]
Q143.Write a code for binary search.[Facebook Interview Question]
Q144.There are N systems available and you have to find duplicate strings from a file that contains 10 billion Strings.[Facebook Interview Question]
Q145.Write a program to merge two sorted arrays.[Facebook Interview Question]
Q146.Write a code to check if a graph is bipartite or not.[Facebook Interview Question]
Q147.Write a function to check if two binary trees have the same elements.[Facebook Interview Question]
Q148.You are given two events that have a start time and an end time, not write a function to check if they overlapped or not.[Facebook Interview Question]
Q149.How will you implement a stack using queue.[Facebook Interview Question]
Q150.Given a number from 1 to 1000, what is the minimum number of guesses needed to find a number if given a hint that the chosen number is higher or lower than the actual number.[Facebook Interview Question]
Q151.Write a code for BFS of a tree.[Accenture]
Q152.Can you have two JVM’s running on a single machine?If yes, can we run them at the same time?[Accenture]
Q153.You have to choose from three doors, in which one has a prize. And if u select door A, and the host tells you that there is no prize in door B, then will you change your decision to door C or will retain your decision?[Accenture]
Q154.Write a code to draw a triangle in C/C++.[Accenture]
Q155.Write a program to print square of order n where n > 3 and is an odd number.[Accenture]
Q156.How will you create a ftp user on a linux system?[Accenture]
Q157.What is the maximum length of a table name,database name and field name in mysql?[Accenture]
Q158.Write a program to store the result of the procedure PROC_RESET_MAIL on database “USER_NOTIFY”.[Accenture]
Q159.Can we define constructors in servlet?[Accenture]
Q160.How will u encode the URL value in php?[Accenture]
Q161.What is the time complexity of the following program?[Synopsis]
fun(n)
{
if(n<=2)
return (1);
else
return ((fun(n1)*fun(n2));
}Q162.In a binary search tree what is the heighest and lowest number of levels for N Node?[Synopsis]
Q163.How can you find nodes with the same data in a linked list?[Synopsis]
Q164.Write a code to reverse a very long string without using the builtin functions.[Goldman Sachs]
Q165.Design an employee class with the following properties:ID, FName, LName and the following functions: tracking down an employee’s manager and subordinates. And a method of all the subordinates of the employee.[Goldman Sachs]
Q166.Count the number of higher bits(1) in an integer and also determine its time complexity.[Goldman Sachs]
Q167.
static synchronized method 1()
{
counter++;
}synchronized method 2()
{
counter++;
}Use only one counter variable to count the number of method calls from both the above functions.[Goldman Sachs]
Q168.Write a program to check that whether two given arrays having same number of elements are equally.You are not allowed to use hash tables or sorting.[Goldman Sachs]
Q169.Write a code to print the distance of a node from the root.Print error if node doesn’t exists.[Goldman Sachs]
Q170.Write a code that can display a number in a sevensegment display format.[Goldman Sachs]
Q171.Given an array of binary number.You have to write a code so that you have all the 1’s at the start of the array and all the 0’s at the end of the array.[Goldman Sachs]
Q172.You are given a word processor type program. There are 2^16 fonts in it. And it takes linear time to search for a font. How will you optimise this search time for a font?[Goldman Sachs]
Q173.What is the output of the following code:[Goldman Sachs]
void fun(int *p)
{
int v = 0;
p=&v;
v++;
}int main()
{
int* p;
fun(p);
}Q174.Write a command to sort a file in linux operating system.[Goldman Sachs]
Q175.Design an ATM machine.[Goldman Sachs]
Q176.What is the problem with the following code, if any:
class Foo
{
int a;
public :
virtual void Fun1() {};
};Class X
{
Foo f;
public:
X(){
memset(&f,0x0,sizeof(f);
}
int main(){X x;}
}[Goldman Sachs]
Q177.Give the internal structure of STL’s set and map and why are they so efficient?[Goldman Sachs]
Q178.Write a function that takes 3 arguments and returns a string telling that either it is scalene, isosceles,equilateral or error.Also give the test cases for the same if someone else wrote the code.[Goldman Sachs]
Q179.Give a unix script to find a specific string in a file.[Goldman Sachs]
Q180.Write a program that returns distinct numbers from a list of numbers.[Goldman Sachs]
Q181.Write a code to check whether a string is a palindrome or not.[Goldman Sachs]
Q182.Given an IP address, you have to check whether that IP is valid or not.How will you go about it?[Goldman Sachs]
Q183.A point in 3D is defined by (x,y,z).And distance between any two points is d and can be calculated as d= sqrt((Xx)^2 + (Yy)^2 + (Zz)^2). Now there are millions entries in a file each corresponding to a point in 3D space. You have to find 10 closest points to a given point (a,b,c).[Goldman Sachs]
Q184.Given a list of denominations and have an unlimited supply of coins, find the max sum S in min number of of coins.[Adobe]
Q185.A set of integers in N files, each having a set of integers. Now write a code to tell if sum of all these integers is divisible by 8 or not.[Adobe]
Q186.Write a code to check is memory allocated to a program and memory returned by a program is the same or not.[Adobe]
Q187.Write a code to split a circular linked list in equal number of nodes.[Adobe]
Q188.You have to find a point from N points such that the distance from the rest of the N1 points is minimum.[Adobe]
Q189.Give an algorithm to find all the pairs in an unsorted integers which have a difference of g(given).[Adobe]
Q190.There are two process p1,p2 doing the following:
p1:reading a file.
p2:modifying a file.
How will you synchronize in such a manner that modifies happens only after reading is done.[Adobe]
Q191.Write a code to determine if the given string is of the form aZb. Where a is the reverse string of b.[Adobe]
Q192.Give the complexity of the following code:
int j;
for(int k=1;k<n;k++)
{
j=k;
while(j>0)
{
j=j/2;
}
}Q193.Write a program to check if a given sum exists on a following path of a binary search tree.[Adobe]
Q194.You are given two classes for dog and animal, where dog class inherits animal class.Write a function that will return a deep clone instance.[Adobe]
Q195.Write a program that can reverse a doublylinked list.[Adobe]
Q196.How will you achieve the operation AB by only using the loop(count) and increment(count) functions. You can’t use any other operator.[Adobe]
Q197.Write a code to merge two binary trees. Also give the complexity for the same if they contain m,n nodes.[Adobe]
Q198.How will you reverse a stack without using an extra stack.[Adobe]
Q199.Write a java program that connects to mysql server and displays the global time zone.[Adobe]
Q200.Give the output:[Adobe]
#define SQUARE(x) x*x
main()
{
int s;
s = 64/SQUARE(4);
print ("%d", s);
}Q201.Write a code to print the main diagonal elements from bottomleft to topright.[Adobe]
Q202.give the output:
main()
{
int x = 2;
switch(x)
{
case 1.5: print ("One");
case 2.5: print ("Two");
default: print ("Zero");
}
}Q203.How many IP address are available on IPv6.[Adobe]
Q204.Write a program to count the number of leaf nodes in a binary tree.[Adobe]
Q205.Write a parenthesis matching code.[Adobe]
Q206.Design minesweeper game.[Yahoo]
Q207.Give an algorithm to sort an array of integers whose first nsqrt(n) numbers are already sorted.[Yahoo]
Q208.How will you store 10GB file using a 2GB RAM.[Yahoo]
Q209.Given a string, now write a code to print consecutive characters in the same line, otherwise on a separate line.[Yahoo]
Q210.Write a code to find the middle element of a linked list.[Yahoo]
Q211.Given a file, write a function to return the top 5 occuring words.[Yahoo]
Q212.You have to implement a search engine. You have 100 files and u have to return those files and paragraph which contain those words.[Yahoo]
Q213.Write a program to implement twitter's trending topic.Given input is a text file.[Yahoo]
Q214.Write a code to sort a stack. You can only use the following function :Push , Pop, Top, IsEmpty, IsFull.[Yahoo]
Q215.Write a function for the intersection of two arrays.[Yahoo]
Q216.Given a stream of numbers, give a data structure to store that stream along with their number of occurrences.[Yahoo]
Q217.Give an algorithm to find the width of a given binary tree.[Yahoo]
Q218.Write a code to give the next prime number after any given number.[Yahoo]
Q219.You are given an infinite binary stream of characters, now after a point of time you need to print whether the count is divisible by 3 or not.Tell how will you do that.[Yahoo]
Q220.Give an algorithm to cover all the squares on a chessboard by a knight, starting from a particular point.[Yahoo]
Q221.Write all possible test cases to test a DVD player and a smart phone.[Qualcomm]
Q222.Give the best data structure to implement a buffer for a text editor.[Qualcomm]
Q223.Give an algorithm to find the nth node from the end of a linked list in linear time.[Qualcomm]
Q224.How can u find the size of a structure.[Qualcomm]
Q225.What does the following function do:[Qualcomm]
bool foo(int y)
{
int x;
x = y  1;
return ((x & y) == 0)
}
Puzzle Type Problems:
Q226.Given two identical eggs. You are infront of a 100 floor building, you think what is the maximun number of floors from which the egg can be dropped without breaking it and what is the minimum number of tries that you will need to find the solution?[Google Interview Question]
Q227.Here is a conversation between two old friends who meet after a very long time:
Jack: Hey, how are you man?
Bill: Not bad, got married and I have three kids now.
Jack: That’s awesome. How old are they?
Bill: The product of their ages is 72 and the sum of their ages is the same as your birth date.
Jack: Cool… But I still don’t know.
Bill: My eldest kid just started taking piano lessons.
Jack: Oh now I get it.
What is the age of Bill’s kids?[Google Interview Question]
Q228.You are given a rectangular cake, in which there is one rectangular piece being cut out of it. It can be of any shape and orientation.You have to divide the cake in two equal pieces.You are allowed to make only one straight cut.[Google Interview Question]
Q229.The probability of a car passing through an intersection in a 20 mins window is 0.9. What is the probability that a car passes in a window of 5 mins. [Google Interview Question]
Q230.In some country, people continue to have child untill they have a boy.After some time, what is the ratio of boys to girls in the country.Assume that probabilty of having the boy or girl is the same.[Google Interview Question]
Q231.You are a prisoner sentenced to death. The king gives you a chance to win your life by playing a game. The game is as follows:You are given 50 black and 50 white marbles and 3 empty bowls. You have to divide the 100 marbles in the 2 bowls as long as you use all the marbles.Now the king will blindfold you and mix the bowls around. And you will draw a marble. If the drawn marble is white then u live else you die. How will you divide them in such a manner that you have the greatest probability of surviving?[Google Interview Question]
Q232.At a movie theater, the manager announces that the first person that will have the same birthday as someone who already has booked a ticket will get a free ticket. There is a line in which you have to stand to book ticket. Where will you stand so that you have the maximum chance of getting the free ticket?The birthdays are all random and you don’t know anyone’s birthday.[Google Interview Question]
Q233.You are in a game of Russian Roulette with a gun that has three bullets in consecutive chambers. Now the gun is spun at the beginning of the game and is then passed between players until it fires.Would you prefer to go 1st or 2nd?[Microsoft Interview Question]
Q234.500 men are arranged in an array of 10 rows and 50 columns according to their heights.Tallest in each row comes out and the shortest among them is A. After they return to their position the shortest among each column are called to come out and the tallest among them is B.How is taller A or B?[Microsoft Interview Question]
Q235.Three ants are sitting on the three vertices of an equilateral and they start to move in random direction along the edge.What is the probability that the three don’t colloid.[Microsoft Interview Question]
Q236.How many points are there on the earth from where, if you go 1 mile south then 1 mile east and then 1 north, you will return to the starting point?[Microsoft Interview Question]
Q237.There are 10 boxes of balls, each ball weighing 10gm.One of the box among them contains defective balls, each weighing 9gm. You are given a weighing machine that can be used only once. How will you know which one is the bax contains defective balls.[Microsoft Interview Question]
Q238.You have infinite quantity of water and 5 quart and 3 quart of pails, how would you measure 4 quart in min number of steps.[Microsoft Interview Question]
Q239.There are four people who need to cross a bridge. They have only one torch and they can’t cross without one. Only 2 people can cross at a time. Each person takes 1, 2, 7, 10 mins. What is the shortest time needed for all of them to cross the bridge?[Microsoft Interview Question]
Q240.You have hired someone to work for you for seven days and you pay them from a bar of gold. You must pay them everyday.You are allowed to make only two breaks.How will you may them?[Microsoft Interview Question]
Q241.Why are manhole covers round?[Google Interview Question]
Q242.Imagine you are standing in front of a mirror. When you raise your left hand your reflection raises its left hand, when you raise your right hand the reflection raises its left hand. But when you raise your head up your reflection doesn’t go down. Why is that it does for the left/right but not for top/bottom?[Microsoft Interview Question]
Q243.There is a bucket full of jelly beans, which are red, blue, and green in color.Now how many beans do you have to grab to be sure that you have two of each color?[Microsoft Interview Question]
Q244.There are four dogs at the four corner of a square of unit distance.At the same time all of them start moving with unit speed towards the person clockwise direction and always run towards them.How long will it take them to meet and where?[Microsoft Interview Question]
Q245.There are 10 soldiers on one side of a river and they have to cross to the other side. There is no bridge and none can swim. One soldiers spot the spots with two boys in it. And it can hold only one soldier and two boys at a time.Tell how will they cross the river?[Yahoo]
Q246.You have to find the 3 top fastest horse among 25 horses. You can conduct race among at most with 5 to find their relative speeds. And you can’t find the actual speed of any horse.How will you do that?[Yahoo]
Q247.Three people checked into a hotel. The three pay a total of $30 to the manager and go to the room.Later the managers comes to know that room rate is $25 and gives $5 to the bellboy to return. On the way, the bellboy reasons that $5 would be difficult to share among three so he gives $1 to each and pockets $2 for himself. Now each is $10 and gets $1 back, so each and everyone paid $9, totalling $27. The bellboy get $2, totalling $29. Where is the last dollar?[Amazon Interview Question]
Q248.There is a logical progression in the following words:
CODIFY
LAMINA
STOVE
RESET
JOKUL
QUIRES
What is the next word on the series:
REST, GRAIL, STOIC, ORDEAL, ?[LinkedIn]
Q249.A man has a wolf, a goat, a cabbage.He must cross a river with the 2 animals and the cabbage. There is a small boat in which he can take them. The condition is that he can take one thing at a time and he can’t leave wolf with goat and goat with cabbage.How will he do that?[Synopsis]
Q250.There is a bulb hanging in a room. Outside the room there are three switches, among the three only one switch is for the bulb.Initially only all switches are off and the bulb is not lit. You are allowed to go in only once.You can’t see from outside if the bulb is lit or not.How will you tell which switch is for the bub?[HewlettPackard]
Answers, hints and solutions to selected questions (from the set above)
Answers
Node * reverse(Node *ptr)
{
Node *temp; //Temp node
Node *prv = NULL; //Previous pointer
while(ptr !=NULL) //looping through the list and reversing
{
temp = ptr>next;
ptr>next = prv;
prv = ptr;
ptr = temp;
}
return prv;
}//The list is reverse with prv points to the start of the list.
A2.This is solved by Kadane’s algorithm which runs in O(n) time. The code is as follows:
Void maxSumArray(int *arr, int len)
{
int maxSum = 12345554;
int start,end
int sum=0
for(int i=0 ; i < len ; i++)
{
sum = sum + arr[i];
if(sum > maxSum)
{
maxSum = sum;
end= i;
}
if(sum < 0)
{
sum = 0 ;
start = start + 1;
}
}
}
A3.That man was playing monopoly.
A4. Mutexes and semaphores are both used to control access to resources like variables with can be used by various process or threads. But mutex is used when only one thread is allowed to use that resources, but semaphore is used when a set of thread can use that resource. Mutex is a semaphores when that set has only one thread.
A5. DFS is an algorithm that is used to traverse along one edge and is explored without backtracking.
The psedo code is as follows:
function DFS(G,v):
label v as explored
for all edges e in G.incidentEdges(v) do
if edge e is unexplored then
w ← G.opposite(v,e)
if vertex w is unexplored then
label e as a discovery edge
recursively call DFS(G,w)
else
label e as a back edge
A6.The Space complexity is O(logn), It is the same in case of a worst case scenario, but is o(1) in case of the best case scenario.
After the partition minimum elements are sorted with O(logn) space. The other partition is sorted using tailrecursion.The quicksort with inplace partition uses constant space before making recursive calls.It makes O(logn) recursive calls thus needs O(logn) space. The worst case takes O(n) nested calls thus requires O(n) space. Best case makes O(logn) calls thus requires O(logn) space.
In case we are sorting large lists, we have to consider the left and right variables as well, they will no longer occupy constant space. It will take O(logn) bits to index into a list of n items.
A8.The Answer may vary on how you want to plan it, thus is left to the readers.
A9.As the database is very large, it can’t be searched directly in memory. Partial files are created and search is done on these partial files. Here we sort it if not in alphabetical order. Then we use binary search to find the word. It will take O(logn) for each file.
A10.
A11.
a)The intersection can be found procedure by using a variation of the merge function of the merge sort.
b)In this case for each entry in B, we can run binary search on the larger
one to know its presence.
A12.
A13.It is a way of organising of information. It’s like a genie who knows where your every toy is in the room and he will also get you any toy that you wish from your collection of toys. It will search for the toys on the name if its a cartoon toy, or any G.I.Joe action toy, or any car toy.
A14.Google uses automated programs called spiders or crawlers, just like most search engines. Google has a large index of keywords and where those words can be found. What makes google different is how it ranks search results, which in turn determines the order Google displays results on its search engine results page(SERP). It uses pageRank algorithm which assigns relevancy score to each web page. It depends of the following factors:
The frequency and location of keywords within the Web page.
How long the Web page has existed.
The number of other Web pages that link to the page in question.
A15.Function to alter between three states.And to alter counter:
uint32_t counter;
pthread_mutex_t lock;
pthread_mutex_t start;
pthread_cond_t cond;
void * threads (void * unused) {
pthread_mutex_lock(&start);
pthread_mutex_unlock(&start);
pthread_mutex_lock(&lock);
if (counter > 0) {
pthread_cond_signal(&cond);
}
while(1){
counter++;
pthread_cond_wait(&cond, &lock);
pthread_cond_signal(&cond);
}
pthread_mutex_unlock(&lock);
}
Now creating two threads t1,t2 which are unlocked and we roughly sleep one second to let them do the firing:
pthread_mutex_lock(&start);
counter = 0;
pthread_create(&t1, NULL, threads, NULL);
pthread_create(&t2, NULL, threads, NULL);
pthread_detach(t1);
pthread_detach(t2);
myTime = tTimer();
pthread_mutex_unlock(&start);
sleep(1);
// Lock both simultaneous threads
pthread_mutex_lock(&lock);
//Normalize the result in second precision
myTime = tTimer()  myTime / 1000;
A16.Left to the readers.
A17.Code for random number between 1 to 7:
int randomGen()
{
BigInteger bigRandom = GivenFunction() * 100000
+ GivenFunction() * 10000+ GivenFunction() * 1000
+ GivenFunction() * 100
+ GivenFunction() * 10
+ GivenFunction();
return (bigRandom % 7) + 1;
}
A18.
finalconstant declaration.
finallyThe finally block always executes when the try block exits, except System.exit(0) call. This ensures that the finally block is executed even if an unexpected exception occurs.
finalize This method helps in garbage collection. A method that is invoked before an object is discarded by the garbage collector, allowing it to clean up its state.
A19. Traverse the first list and hash them to a hash table.Now take the second list and and while iterating over it check whether it is hashed or not, If not then push it to a new list.
A20.Acknowledgments for data sent, or lack of acknowledgments, are used by senders to infer network conditions between the TCP sender and receiver. Coupled with timers, TCP senders and receivers can alter the behavior of the flow of data. This is more generally referred to as congestion control. In addition, senders employ a retransmission timer that is based on the estimated roundtrip time (or RTT) between the sender and receiver, as well as the variance in this round trip time.
A21.
32 : 5 bytes
64 : 9 bytes
A22.
int* init_vector(const int n, const int d) {
int* a = new int[n];
for (int i = 0; i < n; i++) a[i] = d;
return a;
}
// O(n^2)
char* n2_common(char* a, char* b, char* c) {
int n = strlen(a);
int m = strlen(b);
int* v = init_vector(MAX, 0);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (a[i] == b[j]) v[a[i]] = 1;
}
}
int k = 0;
for (int i = 0; i < n; i++) {
if (v[a[i]] != 0) c[k++] = a[i];
}
c[k] = '\0';
delete[] v;
return c;
}
// O(n)
char* n_common(char* a, char* b, char* c) {
int n = strlen(a);
int n = strlen(a);
int m = strlen(b);
A23.Answer left for the users to do on their own.[Google]
A24.The pseudocode is as follows:
pivot=1;
if arr[1]<=arr[2]<=arr[3]
then
arr_dir=UP
elif arr[1]>=arr[2]>=arr[3]
then
arr_dir=Down;
else
pivot = X; //integer found
for i =0 to N:
if arr[i] == data
return true;
if dir == UP
if arr[i] > data
return false
if arr[i+1]<arr[i]
pivot = i+1
dir = change Direction;
break;
if pivot > 0
then
loop to find data
return false
A25.Difference between hashtable and hashmap:
a)Hashtable is synchronized, whereas HashMap is not.
b)Hashtable does not allow null keys or values. HashMap allows one null key and any number of null values.
c)One of HashMaps subclasses is LinkedHashMap, so in the event that you'd want predictable iteration order (which is insertion order by default), you could easily swap out the HashMap for a LinkedHashMap.
A26.It's a made up expression using only the letters AF, often used when a recognisable hexadecimal number is required. Systems use this to show how much memory has been freed or how much shouldn’t be referred again.It is a sign in debugging showing that you have made an error.
A27.Dangling pointers are pointers that don’t point to a valid object of an appropriate type. They mainly occur when an object is deleted or deallocated, without updating the value of the pointer. So the pointer is still pointing to the deallocated memory.
A28. Maximum and minimum can be found in 1.5n comparisons.Here we maintain the min and max seen so far. We compare in pairs. We compare the pair and compare the smaller one with the min and the larger one with the greater of the two elements. Thus we require a total of three comparisons for two elements. Thus 3n/2 comparisons.
A29.Twoway merge sort should be used, as it divides the large data in blocks and sorts them individually, and merges them to sort the large dataset.
A30.Create a suffix tree of the string of length N, Then for each M strings , do the search in the tree and if the small string gets exhausted while reaching the leaf node then the small string will be present in the larger string.
A31.Left for the users.
A32.This can be done by taking the traversing to the end of one of the list and making the ptr>next = list2. Then sorting the new list obtained.
A33.
A34.Removing duplicates from a sorted array:
void removeDuplicates(int* arr, int size)
{
int temp[size];
int prev=0,flag=0,j=0;
for(int current=1 ; current<size ; current++ , prev++)
{
if(arr[current]==arr[prev])
{
flag=1;
}
else
{
flag=0;
temp[j] = arr[prev];
j++;
}
}
}//temp arr will contain the arr free of duplicates, which can be copied by to the original arr.
A35.Steps to follow:
a)Write a code that could reverse the order of an string.
b)Now break the main arr from its blank space to obtain the words.
c)Call the reverse word function to reverse each word in the string.
d)Concatenate all the reverse string to get the final output.
A36.It returns the name of a procedure that caused the error.And this function is place in the cathch block of a TRY CATCH construct.
A37.For authentication one can encrypt the hash (MD5/SHA) of the data with a private key. This is known as digital signature.And secrecy / confidentiality is achieved by encrypting the data with the public key of the target user.
A38.
void main()
{
if(printf(“hello world”))
}
A39.
A40.preOrder(node * Tree)
{
push(tree);
while(stack is not empty)
{
myNode= pop();
print myNode>info;
push(node>right);
push(node>left);
}
}A41.One of the problem in distributed database system is that the network is very unpredictable i.e. over the network on which the database is distributed.This makes processes such as 3phase commit extremely complicated, and makes complexity grow exponentially with number of nodes and desired robustness of the database.
A42.
ASP:
 ASP has limited oops support and no built in support for xml.
 Error handling system is very poor in ASP.
 ASP is not having inbuilt facility for validation of controls.
ASP.NET
 ASP .NET is fully Object Oriented Programming and full XML support
 Error handling is very good.
 Inbuilt validations controls are provided in ASP.NET. which are easy to implement
A43.Function:
int checkOverlap(struct rec r1, struct rec r2)
{
if(((r1.left > r2.right  r1.right < r2.right)  (r1.top < r2.bottom  r1.bottom>r2.top)))
return 1;
else
return 0;
}A44.Left to the readers.
A45.
void ping()
{
String host = "172.16.0.2" //IP address
int timeOut = 3000; // 3000 milliseconds
boolean status = InetAddress.getByName(host).isReachable(timeOut)
}
A46.To find the size of an object type cast it to the type String. And use the method length() to it to find its size.
((String)Obj).length()
A47.Left to the readers.
A48.Left to the users.
A49.This is the nonrecursive code which has less time complexity:
int Fibonacci(int n)
{
if(n == 0)
return 0;
if(n == 1)
return 1;
int first = 0;
int second = 1;
int ans = 0;
for(int i=0; i < n1; i++)
{
ans = first + second;
first = second;
second = ans;
}
return ans;
A51.Algorithm is as follows:
a)Scan array in pairs and remember the largestsofar and smallestsofar in the arrays.
b)On comparing the larger of the two strings with the largestsofar and update it accordingly.
c)Compare the smaller of the pair with the smallersofar and update accordingly.
d)Done in less than equal to 3n/2 strcmp() calls.
A52.No it is not continuous, It is fragmented.
A53.Disk interleaving is for the purpose of transferring data at a faster rate.It is spreading of data across disks and by treating multiple disks as if they were a single one. The rotation of the interleaved disks may be
synchronized to simplify control and also to optimize performance.
A54.
while (!eof)
{
c = getc();
putc(array[c  'a']);
}A55.The common approach is lock levelling. This strategy factors all locks into numeric levels, permitting components at specific architectural layers in the system to acquire locks only at lower levels.
A56.
a)RIP(Routing INformation Protocol)
b)OSPF(Open Shortest Path First)
c)EIGRP(Enhanced Interior Gateway Routing Protocol)
d)BGP(Border Gateway Protocol)
A57. The information that is encrypted with a private key assures the recipient with authenticity of the message to which the information is appended to. So the digital signature provides that the message was signed by the entity who owns the private key.
Smart cards help business evolve and expand the products and services in the global market.
A58.Printing a 2D array in a spiral manner:
void print()
{
int arr[50][50];
int size = m*n;
int flag=0
for(int i=0 ; i<size ; i++)
{
/* for(int j =0 ; j<50 ; j++)
{
if(i%2==0)
printf(“%d ”,arr[i][j]);
else
printf(“%d ”,arr[j][i]);
}*/
if(i%50==0)
{
flag = 1;
}
if(flag==0)
{
row = coli%50;
printf(“%d ”,arr[row][k]);
}
else
{
col = i%50+1;
printf(“%d ”,arr[k][col])
}
}}
A59.Given a sorted linked list, then we have to insert an element to it, so that the order is retained. We can do this by iterating two pointers, and by checking if the value is between those two pointers. If It is there then then we insert it by prv>next = element and element>next=curr.
A60.Latches are sensitive to the duration of a pulse and transfer data only when switched on. They store the last unit of output.
FlipFlop: they are sensitive to a change in the pulse. So they transfer data only when there is a change, i.e. when the pulse drops or when it rises. And this value is not changed until the next change in pulse.
A61.
For each prime p less than m and n:
find Largest a,b() such that p^a\m and p^b\n
q = q*p^max(a,b)
return q
A62.
Node* copy_linked_list(Node* s)
{
Node node,temp,prv;
node = (Node*)malloc(sizeof(Node));
node>data = s>data;
prv = node;s = s>next;
while(s!=NULL)
{
temp = (Node*)malloc(sizeof(Node));
temp>data = s>data;
prv>next = temp;
prv = temp;
s = s>next;
}
return node;
}
A64.Left to the Readers.
A65.We can compare two linked list by maintaining two pointers *p1, *p2 for the two list and then iterating both of them in the same loop. If anywhere the elements diff then the lists are not same, if till end all the elements are the same then they are the same.
A66.
int tree_height(mynode *p)
{
if(p==NULL)
return(0);
if(p>left)
h1=tree_height(p>left);
if(p=>right)h2=tree_height(p>right);
return(max(h1,h2)+1);}
A67.Top command gives the lists of all the active process running on the system.Along with their details.
A68.33 years.
A69.
boolean testExp(String str, String reglr)
{
return str.matchs(regr);
}A70.The number appearing 2 times is (sum of all the numbers in the array)  (sum of the numbers from 1 to n). For floating numbers multiply it with 100 and proceed.
A71.The series comes out to be 4,12,28,........ So the 7th element of the is 60.
A72.Time complexity is O(nlogn) and space complexity is O(n).
A73.Left to the readers.
A74.
prefix: ^  * +ABC  DE  FG
postfix : AB + C * DE   FG  ^
A75.sleep() method send a thread to a nonrunnable state.The thread keeps the monitors it acquired.i.e if the thread is currently in a synchronized block or method no other thread can enter this block or method.
wait() also sends a thread to nonrunnable state, but wait() is for an object. Not a thread. This object is the lock object.Before lock.wait() is called, the current thread must synchronize on the lock object; wait() then releases this lock, and adds the thread to the "wait list" associated with the lock.
A76.If a parent process exits before a child process, then if the child process is separated from parent process, i.e. it is demonised then nothing happens to the child process, it continues to live. But if the child still has some file shared with the parent, then a the child is signaled and is terminated.
A77.find name *.java
A78.char* cp
A79.
bool pointMeet(struct node* s,struct node* p)
{
int flag=0;
while(s!=NULL && p!=NULL)
{
if(s==p)
{
return true;
}
}
return false;
}A80.There is a very large array in which all the elements has a duplicate, then we can just use the operator (^) i.e. exor all the elements and the element that doesn’t have a duplicate will be left.(see property of exor)
A81.
int tree_size(struct node* node)
{
if (node==NULL)
{
return(0);
}
else
{
return(tree_size(node>left) + tree_size(node>right) + 1);
}}
A82.heterogeneous linked lists are lists which contain different data types as data in their node. We need void pointers to links these nodes. As they can store pointers of any type.
A83.
clear(struct node* p)
{
if (p != NULL)
{
clear(p>left);
clear(p>right);
delete p;
}
}A84.left for the users.
A85.One of the methods is to do the following operations:
a=a*b
b=a/b
a=a/b
A86.Left to the readers.
A87.Without using any static variable or global variable, to find the kth smallest element, one can do a inorder traversal, and store the elements in ascending order and print the kth smallest element.
A88.See how the decimal to hexadecimal is done. Coding it won’t be a difficult task.
A89.
SELECT max(salary)
FROM Employee
WHERE Employee.salary < (SELECT max(salary) FROM Employee)
A90.SELECT Sno , playerName
FROM PLAYER as p1 , PLAYER as p2
WHERE p1.Sno != p2.Sno;
A91.Left to the readers.
A92.auto pointer is used to delete those objects it is pointing to.And this can only be used on objects that are created by unbracketed new. But here array is created using new[] and only delete[] can destroy it. Thus due to mismatch, it causes memory leak.
A93.Left to the readers.(Not a programming question)
A94.
5
20
1
A95.There is nothing wrong with the code.It won’t show any complination or runtime error.
A96.When the list is empty, then it will return true.
A97.to kill a process, we use the “kill” command followed by the process id.See the man page for kill for various other options.
eg:kill process_ID
A98.Level order traversal, left for the readers to do it on their own.
A99.
public interface vehicles{
public boolean park(ParkingSlot slot);
}public class Motorbike implement vehicles{
public boolean park(ParkingSlot slot)
{
if(slot is motobikeslot)
return true;
else
return false;
}
}Similar class is for the Car and function for handicapped class is as follows:
public boolean park(ParkingSlot slot)
{
if(slot is Carslot or handicappedslot)
return true;
else
return false;
}A100.
A101.
A102.Keeping track of the median, using min and max heap.
A103One solution is to use the while loop in 8 possible ways.
A104.
A105.In a binarysearch tree, the successor of a node is the leftmost leaf node of the right child. Writing a function for the leftmost leaf and passing the rightchild will return the successor.
A106.
int findBadRevision(int goodRevision, int badRevision)
{
while (1)
{
int mid = (goodRevision + badRevision) / 2;
if (hasBug(mid)) {
if (mid == 0  !hasBug(mid1)) {
return mid;
}
badRevision = mid;
}
else {
goodRevision = mid;
}
}
A108.
bool find_three(int arr[], int c, int sum)
{
int i, j, e, s, k;
bool ret = false;
//Sorting the input array
std::sort(&arr[0], &arr[c]);
for (int i = 0; i < c; i++)
{
s = sum  arr[i]; // the sum of two elements should be this value
e = c  1;
j = i + 1;
while (j < e)
{
k = arr[j] + arr[e];
if (k == s)
{ // found two elements that sum up to our sought value
printf("SUM: %d ELEMENTS (%d %d %d): %d %d %d\n",sum, i, j, e, arr[i], arr[j], arr[e]);
//return true;
ret = true;
j++;
e;
}
else if (k < s)
j++;
else
e;
}
}
if (false == ret)
{
printf("SUM: %d\n", sum);
}
return ret;
}
A109.To reverse a linked list, maintain two pointers, one present and one previous.And after each iterantion, move both the pointers forward and curr>next = prev.
A110.Any solutions are possible.Like we can use the A* heuristic search to find out the sorted path to (m,n). Or could write the following function for it.:
struct movement
{
int x;
int y;
};
vector<movement> trace;
bool move(int x, int y, int m, int n)
{
movement motion;
bool horizontal = false;
bool vertical = false;
motion.x=x;motion.y=y;
if(x==m && y==n)
{
trace.push_back(motion);
return true;
}
if(x+y<=m && y<=n)
horizontal=move(x+y,y,m,n);
if(x<=m && x+y<=n)
vertical=move(x,x+y,m,n);
if(horizontal  vertical)
{
trace.push_back(motion);
return true;
}
return false;
}
The function just follows the problem statement.
A111.The algorithm for the same is as follows:
1.Sort the set by login order.
2.Search the first element greater than the given time.
3.Discard everything after that, only keep the elements behind it.(including that element)
4.From the set find the logout time more than the given set.
A112.A source to read fom:http://en.wikipedia.org/wiki/Lookandsay_sequence
Here is a code in PHP for the same
<?php
$x = trim(fgets(STDIN));
$y = (int)trim(fgets(STDIN));
while ($y)
{
for ($i = 0, $c = 0, $n = $f = ''; $i < strlen($x); $i++, $c++) {
if ($x[$i] != $f) {
if ($c) $n .= $c . $f;
$f = $x[$i];
$c = 0;
}
}
if ($c) $n .= $c . $f;
$x = $n;
}
echo "$x\n";
A113.
quicksort intervals by ai
for each intervals:
queue.insert (bi)
while( queue_head < ai)
queue.pop()
updatemax(ai, queue.size)
A114.Left to the users.
A115.You can use binary search, or newton's method to find the cube root of a number.
A116.HINT:use splay trees.
A117.Using DFS search and coloring will efficiently divide the set into the desired groups.
A118.
static void main(string[] args)
{
GetNKCombinations(10, 6);
foreach (List<int> s in combinations)
{
System.Console.Write("[");
foreach(int i in s)
System.Console.Write(" "+i);
System.Console.Write(" ]\n");
}
System.Console.ReadLine();
}
static List<List<int>> combinations = new List<List<int>>();
public static void GetNKCombinations(int N, int K)
{
if (N < K)
return;
Combine(N, K, new List<int>(), 0);
}
private static void Combine(int N, int K, List<int> result, int startIndex)
{
if (result.Count == K)
{
List<int> l = new List<int>();
l.AddRange(result);
combinations.Add(l);
return;
}
for (int i = startIndex; i <= N; i++)
{
result.Add(i);
Combine(N, K, result, i + 1);
result.RemoveAt(result.Count  1);
}
}
A119.This can be done as follows: Use two array to store these numbers, and use each digit to multiply by using the basic rules of multiplication, by multiplying digits.
A120.To implement a atof() of C, we can simply find the dot of the string and multiply to the digit to 10 raise to power to (the position of the digit from the dot  1).The raised power will be positive id number id left to the dot, and negitive if right to the dot.
A121.Left to the readers.
A122.
A124.It can be done using a level order traversal.
A125.Python code:
x = 1.0
while (x * x  num).abs > precision
x = (x * x  num) / (2 * x)
end
A126.This can be done using DP. The code follows as:
int max_sum(int arr[], int sz, int index)
{
if(index >= sz)
return 0;
if(dp[index] != 1)return dp[index];
int a = max_sum(arr, sz, index+1);int b = max_sum(arr, sz, index+2);
if(a > (b+arr[index]))
dp[index] = a;
elsedp[index] = b+arr[index];
return dp[index];}
A127.Many data structures can be used which directly have an inbuilt function like erase, in C++ and java.I am showing an example in python:
arr = [1, 2, 4, 0, 5, 0, 1, 0, 0, 1, 7, 0, 8, 0, 2, 4, 5, 1, 2, 8, 0, 5, 6, 8]
for i in xrange(len(arr), 0, 1):
if not arr[k1]:
arr.pop(k1)
A128.
void PrintPrimes(char* text, int len)
{
if (len == 0)
return;
int currentIndex, currentLen;
while (currentIndex < len)
{
char* temp = new char[currentLen+1];
strcpy(temp, text+currentIndex, currentLen);
int num;
if (ConverToNum(temp, currentLen, &num))
{
if (isPrime(num))
{
Console.WriteLine(num);
}
currentLen++;
}
else
{
// couldn't convert to a number therefore we hit a noninteger
currentIndex = currentIndex + currentLen + 1;
currentLen = 0;
}
}
}
The functions: ConerToNum converts strings to number and Isprime checks if it is prime or not.
A129.Left to the readers.
A130.Python code for inorder:
def inorder(node):
stack = []
leftChecked = False
while node != None:
if not leftChecked and node.left != None:
stack.append(node)
node = node.left
else:
print node.data
if node.right != None:
node = node.right
leftChecked = False
elif len(stack)>0:
node = stack.pop()
leftChecked = True
else:
node = None
A131.Python code:
class queue:
in_stack
out_stack
def enqueue(data):
in_stack.push(data)
def dequeue():
if out+stack.size() == 0:
while in+stack.size() > 0:
out_stack.push(in_stack.pop())
return out_stack.pop()
def size():
return in_stack.size()+outstack.size()
If out_stack not empty then:
O(1) for both operations.
else if out_stack empty:
O(n) for both operations.
A132.BST
A133.Find all permutations of XYZ, except for each XYZ, you should include permutations for each X0 to Xn and Y0 to Yn , etc
A134.Left for the readers.
A135.This can be done by reversing the list and printing it in order.
A136.HINT:use the dot product of the two vectors.
A137.Kadane's Algorithm.
A138.
from math import sqrt
def log2(x):
if x <= 2:
return 1
y = sqrt(x)
if (y*y != x):
return log2(x / 2) + 1
else:
return 2*log2(y)
A139.
int main(){
char *s = "88934";
int sum=0;
int i=0;
while(i<strlen(s)){
int value = s[i]'0';
sum = 10*sum+value;
i++;
}
printf("%s %d\n", s, sum);
}
A140.Find the depth of the leftchild and that of the right child and add them up.
A141.Not a good, optimised solution.
int mindepth(node* root)
{
if(root==NULL) return 0;
return 1 + min(mindepth(root>left),mindepth(root>right));
}
A142.
public static int Div(int divisor, int dividend)
{
if (divisor==0)
return 1;
int pDividend = Math.abs(dividend);
int pDivisor = Math.abs(divisor);
int quotient = 0;
while(pDividend>pDivisor)
{
pDividend=pDivisor;
quotient++;
}
quotient = (divisor>0&÷nd<0  divisor<0&÷nd>0)? quotient*1:quotient;
return quotient;
}
A143.Left for the readers.
A144. Hash partition the strings into buckets, let each system distribute the buckets among themselves and find duplicates in each bucket separately.Finding a bucket separately is easy.
A145.Left for the readers.
A146.Left for the readers.
A147. We can use hash table to achieve the pourpose. Traverse one tree and hash all the elements of the form: <element,count>. Now
traverse 2nd tree and for each node:
if data not in hashtable return false;
otherwise, decrease count by 1, remove the key if count is 0
return hashtable.ItemCount == 0;
A148.!(s1>e2  s2 < e1)
A149.We want to have enqueue() over push() and dequeue() over pop(). This can be done by maintaining two stacks A and B.
1.enqueue(): Push the element to stack A.
2.dequeue(): Pop all the elements to stack B and remove the top element of stack B. And then pop all the elements and push then to stack A.
A150.Use binary Search on that range where the number can be found after the result of higher or lower is given on every guess.
A151.Left to the readers.
A152.Yes you can have two JVMs running on a single machine. But you can only run one at a time.
A153.You should change the door. P(A) = ⅓. P(B) + P(C) = ⅔. Then the interview adds information on the set that P(B) =0 . so the P(C) = ⅔. While P(A) still is ⅓. As P(C) > P(A). Then change it to C.
A154.To draw a triangle in C/C++. It is done like this:
glBegin(TRIANGLES);
glVertex3f(x1,y1,z1);
glVertex3f(x2,y2,z2);
glVertex3f(x3,y3,z3);
glEnd();
A155.Left to the readers.
A156.Follow these steps:
1.create a user:
useradd:[username]
passwd:[password]
2.Now add this line to file vsftpd.conf located in the directory /etc/vsftpd :userlist_deny=NO
3.Now add the user to file user_list located in the same directory as mentioned above.
4.then restart the ftp services by : /etc/init.d/vsftpd start.
A157.
tablename=64
databasename=64
fieldname=64
A158.Left
A159.Init() creates and loads the servlet, But if the servlet instance is first created through the constructors which is done by the Servlet container. We can’t write constructors of a servlet class with arguments in servlet as it will throw an exception. To overcome this init() accepts an SevletConfig object as an argument. ServletConfig object supplies a servlet with information about its initialization parameters.
A160.string urlencode (string $str)
A161.O(2^n)
A162.
A163.To find the same data in a linked list, we iterate over a list and hash all the elements of the form <element , count > . Now the elements with count more than one will be a repeat in the list.
A164.To reverse a string without using a builtin function:
1.Maintain two indices, one at the start and one at the end of the char array of the string.
2.Now swap the two characters which are at the two indices pointers and increment the start and decrement the end one after each iteration, till start > end.
A165.This can be done using a tree, having the assumption that each employee can have only one manager.
P:Immediate parent(Immediate manager)
R:Root of the moss.
E:Employee
Functions of the class:
P searchChildElementInTree(R ,E)  gives manager of the employee
R addEmployee(R, P, E)
displayTree(P)  all nodes under P(root) and its children are displayed
A166.To count the number of higher bits in an integer:
1.Convert the integer to binary form as string.
2.Iterate over the string and if ‘1’ occurs increment the count value for the higher bits.
A167. Change the static method to nonstatic or use two variables.
A168.To check if two arrays are equal or not:
1.arr1.len==arr2.len
2.Sum(arr1) == Sum(arr2)
3.Xor of all the elements in both the arrays should be equal to zero.
A169.
int distance(int num,tree *temp,int height)
{
if(temp==NULL)
return 0;
if(temp>val==n)
return height;
else
return (distance(n,temp>left,height+1)  distance(n,temp>right,height+1));
}A170.Left to the users.
A171.
int[] a = {0, 1, 1, 0, 0, 0, 0, 1, 1, 1};
int i = 0;
int j = a.length  1;
int temp = 0;
while(i<j) {
if (a[i] == 0 && a[j] == 1) {
temp = a[i];
a[i] = a[j];
a[j] = temp;
i++;
j;
}
if (a[i] == 1) {
i++;
}
if (a[j] == 0) {
j;
}
}
A172.To have fast access all you need to do is have a hash mapped, access. You can achieve this by hashing, or a map table.
A173.It will give a compilation error.
A174.sort filename.
A175.Left for the readers.
A176.’a’ in Foo function is private, so can’t be set by derived class X.
A177.Using a map makes the operation constant time O(1). It uses red black tree for its implementation that has time complexity of O(logn).
A178.Left to the users.
A179.cat filename  grep string.
A180.To return distinct numbers from a list, we can use a random function.It generates a number between 0 to the max index of the list. And once the number is generated then that number is marked on a hash table, so that if that number comes up again, a different number is selected.
A181.To check weather a string is a palindrome or not, one should reverse the string and check it which the previous string. If they are the same then it’s a palindrome else not.
A182.Function to check for the validity of an IP address:
boolean verifyIpAddress(String ipAdd)
{
String regExp = "[02][05][05]\\.[02][05][05]\\.[02][05][05]\\.[02][05][05]";
return ipAdd.matches(regExp);
}A183.Hint:use a min heap data structure.
A184.A coin change problem, left to the readers.
A185.
int isdiv8(FILE*fp)
{
int total = 0;
while(fscanf(fp, "%d", &num))
{
total = total + num;
}
if (total%8==0)
return 1;
else
return 0;
}A186.In the program it must be cheacked how much memory is allocated using the ‘new’, that creates the object, and when the stack clears that object, after the program ends.
A187.Two divide a circular linked list, do the following:
1.Give a start pointer to any node and let it be the start node.
2.Maintain two pointers, increment one my 1 and the second by two, from this we can know the pointers, that covers all the nodes.
3.Count the number of nodes from start to end.
4.At the half of the list, point it to the start and point the last one to the node at mid.
A188.Select min abs value of x and y, max abs value of x and y. Find the mean of both the x’s and y’s. And the resultant would be the answer.
A189.Steps:
a)Sort the array, using quick sort O(nlogn)
b)For each element in that array find the complement number “element ± d” using binary search.
A190.It can be syncronized using mutex.
P1 :
wait(mutex);
readcount ++;
if(readcount == 1)
wait(wrt);
signal(mutex);CRITICAL SECTION
//perform reading
wait(mutex)
readcount;
if(readcount==0)
signal(wrt);
signal(mutex);
P2:
wait(wrt);
//perform writing
signal(wrt);
A191.This can be done by checking whether the string is a palindrome or not.
A192.O(nlogn)
A193.
public bool SumExistsOverAnyPathInBinTree(Tree t, int sum)
{
if (t == null)
return (sum == 0);
int data = t.Data;
int result = sum  data;
if (result == 0)
return true;
return (SumExistsOverAnyPathInBinTree(t, result) 
SumExistsOverAnyPathInBinTree(t.LeftChild, sum) 
SumExistsOverAnyPathInBinTree(t.RightChild, sum));
}A194.left for the readers.
A195.To reverse a double linked list all be need to do is :
void reverseList(node* ptr)
{
while(ptr!=NULL)
{
temp = ptr>next;
ptr>next = ptr>prev;
ptr>prev = temp;
ptr = temp;
}
}A196.
bool notEqual(int a, int b)
{
int i=0;
loop(a)
increment(1); //increment i
loop(b)
increment(1); //decrease i
if(i)
return true;
else
return false;
}
int result(a,b)
{
diff =0;
while(notEqual(a,b))
{
increment(1) //a++;
diff++;
}
return diff;
}
A197.To merge two binary tree, Iterate over one tree and add thoses elements to the other binary tree.
A198.Hint:Use recursion.
A199.Left to the users.
A200.64.
A201.Left to the readers.
A202.It will show an error because only charachters and integers can be used in switchcase statements.
A203. 256^6
A204.
int CountLeafNode(node* root)
{
if(root==NULL)
return 0;
if(root>left==NULL && root>right==NULL)
return 1;
return CountLeafNode(root>left)+CountLeafNode(root>right);
}A205.Hint:Use stacks
A206.Left to the users.
A207.
a)Sort the rightmost half and merge.
b)Use the insertion sort way.
A208.To store a 10GB file using a 2 GB RAM, use twoway merge sort, that divides the file into small parts that can fit into RAM for sorting. These files are sorted using quicksort and stored back, then all are merged together to have one 10 GB sorted file.
A209.
A210.To find the middle elemement of a linked list, first iterate over the list to count the total number of node in it.Then half the count and iternate to that element.
A211.This can be done by using maps or hash tables of the form <word,count>. The list is then sorted on the basis of maximum count, and the top 5 words are then returned by the function.
A212.A script can be used using the grep command.
A213.Left for the readers.
A214.To sort a stack, we can pop all the elements out to an arry and use the quicksort algorithm to sort out the array, and then the elements are pushed back to the stack. It can be pushed from behind or from the front depending on how we want the stack.
A215.For the intersection of two array, we can use mapping functions. a)We can map all the elements of one array of the form <element,count>.
b)then we iterate over all the elements of the second array, and increment the count if the element is found and if not then left as it is.
c)All the elements in the map that have count greater than one are included in the intersection.
A216.Hash data structure.
A217.
int width (Node n)
{
if (n == null)
return 0;
else
return 1 + (width(n.left) + width(n.right));
}A218.To find any prime number after any given number can be done as follows:
a)we have stored all the prime numbers before that number.
b)We increment the number and check all the numbers till we get a prime number.
c)We check the number whether it’s prime or not from the list of prime numbers by dividing it from that list.And add the new prime number to it.
A219.
a)int sum=0;
b)Add 1 to sum if first bit is set. Add 2 to sum if second bit is set.
c)Now proceed only for the 3rd fit onwards, for every odd bit set add 1 to sum, and even bit subtract 1 from sum.
d)When sum exceeds 3 make it sum%3.
Thus at any point, if sum==0 then its is divisible by 3 else it is not.
A220.
a)Create a graph with 64 vertices.
b)Each vertex will have an adjacency list of all positions where Knight can be placed.for example if the Knight is placed at the center of chessBoard, Knight can move 8 different ways. Adj list will be of 8 vertices.
c)Apply it to the Knight throughout chess Board.
A221.Left to the readers.
A222.Rope is the best data structure that can be used here.
A223.
node* getNthLast(node* head,int n)
{
node *temp1, *temp2;
temp1=temp2=head;
while(tmp2)
{
if(n>0)
{
tmp2=tmp2>next;
n;
}
else
{
temp1 = temp1>next;
temp2 = temp2>next;
}
}
return temp1;
}
A224.Use sizeof()
A225.The functions checks if y is a power of 2.
A226.One solution is that we go to the first floor and drop the egg, if it doesn’t break we go to the next floor.If it breaks we know it is the maximum floor from where the egg doesn’t break. The maximum number of tries is 100 as we can go to 100th floor without breaking it.
A227.their ages are 3,3,8.
A228.Make a cut at an angle such that it passes through the centre of the cake and from the center of the hollow rectangle which has been removed already. The cut must pass through pass through both the rectangles so that the two pieces have equal area.
A229.x:probability that car passes in 5 mins window.
P(Car passing in 20 mins window) = 1  P(Car not passing in 20 mins window)
P(Car passing in 20 mins window) = 1  P(1  P(car passing in a 5 mins window)^4)
==>0.9 = 1  (1x)^4
==>x = 0.4377
A230.Let the number of couples be C. The number of boys will be C.No of girls is calucate as:
==>0*(Probability of 0 girls) + 1*(Probability of 1 girl) + 2*(Probability of 2 girls) + ….........
==>C
thus, the ratio is 1:1
A231.Place one white marble in one bowl and the rest of the marbles in the second bowl.
bowl 1 :1 white marble
bowl 2: 49 white marble , 50 black marble.
Now you have 50/50 chance to survive if any one of the bowl is selected.He will survive if he selects the white marble bowl. And even if he selects the other bowl, he will still have an almost 50/50 chance to survive.
A232.You should be the 20th person in line.
A233.Prefer going 2nd as it has a chance of winning of ⅔.Try all possible cases to find the probability.
A234.No one it taller as both are the same person.
A235.P(No collision) = P(All ants go in a clockwise direction) + P(All ants go in an anticlockwise direction)
=> 0.5 * 0.5 * 0.5 + 0.5 * 0.5 * 0.5 = 0.25
A236.Infinite number of points.
A237.To find out which box contains defective balls, we will name boxes from 1 to 10. Then from first box we take 1 ball, from 2nd we take 2 balls, from 3rd we take 3 balls and so on. So we have a total of 55 balls.Now assuming that all the balls are fine, the total weight will be 550gm.But it would be less due to the defective balls. Now if the difference is one less then it is due to 1 balls, from box one. If 4 less than the total then from 2nd box and so on.
A238.
1.Fill 3 quart pail:: ( 5p:0, 3p: 3)
2.Transfer to 5 quart pail:: (5p: 3, 3p: 0)
3.Fill 3 quart pail:: ( 5p:3, 3p:3)
4.Transfer to 5 quart pail:: (5p: 5, 3p: 1)
5.Empty 5 quart pail:: (5p: 0, 3p:1)
6.Transfer to 5 quart pail:: (5p: 1, 3p: 0)
7.Fill 3 quart pail:: ( 5p: 1, 3p: 3)
8. Transfer to 5 quart pail (5p: 4, 3p: 0)
We have 4 quart of water.
A239.It would take 17 mins in total.
a)1 and 2 crosses.
b)2 returns.
c)7 and 10 crosses.
d)1 returns
e)1 and 2 crosses.
2+2+10+1+2 = 17.
A240.
Day 1:Give Bar 1 (You:2 and 4, Worker: 1)
Day 2:Give Bar 2, Take back Bar 1 (You: 1 and 4, Worker: 2)
Day 3:Give Bar 1 (You: 4, Worker: 1 and 2)
Day 4:Give Bar 4, Take back Bar 1 and Bar 2 (You: 1 and 2, Worker: 4)
Day 5:Give Bar 1 (You: 2, Worker: 1 and 4)
Day 6:Give Bar 2, Take back Bar 1 (You: 1, Worker: 2 and 4)
Day 7:Give Bar 1 (You: Empty, Worker: 1, 2 and 4)
A241.Manholes are round so that they don't fall through the manhole.When the plane ordinarily flush with the plane of the street that is perpendicular to it.
A242.It is because of the lateral inversion property of the mirror. Which can easily be proved.
A243.Four.
A244.They will move in a spiral way and will meet at the center of the square due to symmetry.
A245.The two boys will go to the other side of the river and then one of them will return. Then one soldier will go to the other side of the river and the boy will return. This will keep on repeating until all the soldiers return.
A246.We will conduct 7 races to know the top three fastest horses.
A247.Here is a cheating part, the three give $9 dollar includes the tip to the bellboy.25/3 rent paid by each person and $2/3 to the bellboy. Totalling to $27. Now if we if we add $3 to it, $30 will be the final sum.
A248.REST
A249.He can take the wolf, then the cabbage. Both of them will be safe at the other end. Then he can bring the goat with him, thus all will be safe.
A250.Switch on first and leave it for 2 mins. Then switch on the 2nd and go to the room.Now if it is on, its switch is the 2nd one. If its off and hot then its the first one and is its off and not hot then its the 3rd one.