SDE2 Interview Questions
 0of 0 votes
Given a list a1,a2,a3….an. Comparison between elements is given like a1>a2, a3>a5, a4>a2…..etc. Find whether there are any situations that we can sort the list in to the ascending order on the basis of comparison. Yes or No , explain the conditions
 0of 0 votes
Given 2D Array of only 0s and 1s, Find the row which gives max decimal value.
Input: int array[3][3] = {{0,1,0,}{1,1,0},{1,0,1}};
Output : 2(second row)...decimal value is 6
 0of 0 votes
Find the largest substring in s1, such that all characters in the substring are present somewhere in s2
 1of 1 vote
Design and implement a scalable multiplayer N*N TicTacToe game.
 3of 3 votes
I had two interviews with Google
first) one with US person...he asked decent question with lot of hints...experience : positive
and
then second) interview with person from India...I prepared for one month but he asked me very tough one graph/tree question...never gave single hint and based on that one question he judged my seven years of experience in Software Development (I never experienced what they say...Google looks for approach and not final answer)
Q.1 : Arrange array in wave form A1 > a2 < a3 > a4 ...
O(n.logn) (Note: its not A1 >= A2)
Q.2 : Given Graph with Tree characteristics, find one node as root so that height of tree will be minimum
 3of 3 votes
Imagine a man reading a book.
He can perform only 2 possible actions of reading:
1) read a page in a minute (careful reading),
2) read two pages in a minute (look through).
Nothing else is permitted.
Calculate the number of all possible combinations of book reading ways with given number of pages.
Example: given 3 pages.
Answer is 3 combinations, as follows:
1st: Careful reading (1)  careful reading (1)  careful reading (1),
2nd: Careful reading (1)  look through (2),
3rd: Look through (2)  careful reading (1).
 2of 2 votes
How do we achieve (google news) personalization.
 2of 2 votes
Cadbury bar size of 5*3 can be distributed to 4 children.
5*4 can be distributed to 5 children.
6*3 can be distributed to 2 children.
6*4 can be distributed to 3 children. so the whole carton can be distributed among 14 children
Program output shall be 14.
Input/Output Specification: M,N,P,Q are the integer type (M,N values are the ranges for the length of cadburybar P,Q values are the ranges for breadth of Cadbury bar)
Output: Number of children who will receive cadbury bar from the carton.
 0of 0 votes
2. VeryLongInt
Design a class which can add and subtract integers up to 1000 digits. You can make the following assumptions
No need to handle overflow or underflow (extra credit if you do)
Copy constructor is available
“+” and “” are binary operators
 2of 2 votes
1. Balanced Parentheses
Given a string s of parentheses (ex: “(()”), return the minimum number of parentheses that need to be inserted to make it into a well formed string
A well formed (balanced) string of parentheses is defined by the following rules: ● The empty string is well formed. ● If s is a well formed string, (s) is a well formed string. ● If s1 and s2 are well formed strings, their concatenation s1s2 is a well formed string.
Implement
int MinNumInsersertionsForBalancing(const string& s)
 1of 1 vote
Sort an array of 0s, 1s and 2s
Given an array A[] consisting 0s, 1s and 2s, write a function that sorts A[]. The functions should put all 0s first, then all 1s and all 2s in last.
Example
Input = {0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1};
Output = {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2}
The problem is similar to http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/
But they have added 1 trick into the question, You cannot use high = n;
It means don't calculate the length of array.
Can anyone help me in writing the code for this problem ?
 0of 0 votes
Given a list of sorted arrays, like List<int[]>. Prepare and return a single sorted list.
 0of 0 votes
Given two Binary Trees (not BST). Each node of both trees has an integer value. Validate whether both trees have the same integers, there could be repetitive integers.
ex
Tree1:
5
1 6
5 4 3 6
Tree2:
1
3 4
6 5
have identical integers.
 1of 1 vote
Given a string which may contain parenthesis. We must verify the validity of the string.
ex
1) "<ad675+fkmfd>" is a valid string
2) "<[((kskfhdbh7)" is invalid
3) "[<<((shfs8))>>]" is valid
Extension to the question 
Suppose you had a hash table that told you how a parenthesis starts and how it ends as a key value pair, how would you then validate the string.
ex  <key,value> = < '(' , ')' > indicates '(' is a start parenthesis and ')' should be the end of that paranthesis.
<'A','&'> indicates that 'A' is a start parenthesis and '&' is the end parenthesis.
Note: Validity means a parenthesis that starts, must end.
 0of 0 votes
Given a grid of m*n size. Each block in grid has some amount of gold.
We start from first column of the grid(any row) and we can move in 3 direction  right, rightup and rightdown.
What is the maximum amount of gold we can collect from the grid.
 1of 1 vote
Print first and last node of all the levels of a tree.
Ex if tree is 
root>data = 1
root>left>data = 2
root>right>data = 3
root>left>right>data = 4
root>right>right>data = 6
root>right>left>data = 5
root>right>left>left>data = 7
root>right>left>left>right>data = 8
Output  1 2 3 4 6 7 8
 0of 0 votes
Given a 2D matrix which contains 0’s and 1’s. Given two points of matrix whose value is 1. Find the path(with only 1’s) between the given points
 1of 1 vote
Connect nodes at same level of a binary tree recursively using O(1) space (we can ignore stack space used for recursion)
Tree node is like following.struct node { int data; struct node* left; struct node* right; struct node* nextRight; }
Initially, all the nextRight pointers point to garbage values. Your function should set these pointers to point next right for each node. You can use only constant extra space.
 2of 2 votes
In a string detect the smallest window length with highest number of distinct characters. For eg.
A = “aabcbcdbca”, then ans would be 4 as of “dbca”
 1of 1 vote
WAP to get following.
input : {2, 4, 3, 5, 6}
output: {360, 180, 240, 144, 120 }
Hint: {4*3*5*6, 2*3*5*6, 2*4*5*6, 2*4*3*5}
Please note, division is not allowed and time complexity should be O(N).
 8of 10 votes
/**
You have list,which contains a DS(Data Structure) which have a list and a value (basically a list of list).
You need to write an iterator such that it will iterate over the numbers/integers whenever a .next() is called
1>2>3>4

6>7>10
 
8>9 11>12
Output
1 .next() > 1
2..next() > 6
3..next() >7
4..next() >8
5..next() >9
6..next() >10
7..next() >11
8..next() >12
9..next() >2
10..next() >3
11..next() >4
12..next() > throws Exception
**/
 1of 1 vote
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
int main(void) {
int i =0;
while(1)
{
i++;
printf("\n %d ", i);
pid_t pid;
pid = fork();
if(pid < 0)
{
wait(3600);
}
else if(!pid)
{
sleep(1);
exit(0);
}
else
{
sleep(10);
}
}
// your code goes here
return 0;
}
Is there any problem with this code ?. I ran this code, and saw same i value printing, but do not understand why it is printing twice
 0of 0 votes
class A {
public:
void virtual fun1() { cout << " A::fun1" << endl; }
void virtual fun2() { cout << "A::fun2" << endl; }
};
class B : public A {
public:
void fun1() { cout << " B::fun1" << endl; } // fun1 > B
};
class C {
public:
int z;
virtual void fun3() { cout << "C::fun3" << endl; }
};
class D: public B, public C {
public:
void fun4() { cout << "D::fun4" << endl; }
};
void other(void* obj) {
C *c = (C*)obj;
c>fun3();
}
int main() {
D* d = new D();
other(d);
return 0;
}
what prints c>fun3 in other() function ?, reason behind it ?.
It is printing B::fun1. I do not know reason , can some one explain it
 0of 0 votes
public class Node
{
public Node[] Children;
public Node Right;
}
Each node represents an element of a tree and specifies a list of immediate children.
The 'Children' property lists all children (in order) but the 'Right' property is set to null.
Suppose you are given the root of a fully populated tree (i.e. a Node called RootNode). Write code to set the 'Right' property so that each node is linked to its right sibling.
 1of 1 vote
How would you design a price tracking website like camelcamelcamel.com?
For example, we might want the following behavior. Input: Item URL and target price. Result: if the item goes below the target price, then users tracking the item will get an email alert.
Consider the following topics in the answer: database design (SQL or NoSQL), automated price checking mechanism, price scraping or price API, caching data.
 0of 0 votes
How do you decide whether we should use Java or C++ for a particular project . what are pros and cons
 0of 0 votes
How does garbage collector work ? In mark and sweep , how does gc know which objects it needs to mark , how are references stored for objects for gc to understand that its reference is null or it is no more referenced anywhere j
 0of 0 votes
You are given a library of n words. You have to select any one word and remove a character from it such that it becomes one of the words remaining in the inventory. What is the length of the longest possible chain of these removed steps?
The selected word is discarded and not added to the library.
 0of 0 votes
This interview was held 3 years back. adding this question for others reference.
Design a picasa.i.e. A photo album application where user can store his pictures and share among the others using their email ids.
You need provide high level design for server and client.
I explained about
 storage on RDBMS database ( Interviewer was expecting some datwarehousing or NOSql over here but I could not explain as was not aware of it till that time)
 Different sizes of photo storage.
 Cache for recently accessed photos
 Cache for most accessed photos
 Regional servers
 Disaster management, clustering, HA
 0of 0 votes
Given a linked list of strings find the sequence where last character should be equal to first character. Here the head string should always be the same. All the solutions possible should be printed Ex given following Here > is> ew> long > shut > error > roll Output should be 1. [Here, ew] 2. [Here, error, roll, long] All the possibilites should be printed.