CareerCup

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.log-n) (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

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).

How do we achieve (google news) personalization.

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.

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

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)

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 ?

Given a list of sorted arrays, like List<int[]>. Prepare and return a single sorted list.

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.

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.

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, right-up and right-down.

What is the maximum amount of gold we can collect from the grid.

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

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

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.

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”

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).

/**
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
**/

#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

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

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.

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.

How do you decide whether we should use Java or C++ for a particular project . what are pros and cons

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

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.

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

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.

You are given a large array of 10,000,000 bits. Each bit is initially 0. You perform several operations of the type "Flip all the bits between start_index and end_index, inclusive". Given a sequence of several such operations, perform all the operations on the array. Finally, split the array into sets of 4 bits - first four, next four, then next four and so on. Each set can represent a hexadecimal integer. There will be exactly 2,500,000 hexadecimal integers. Calculate the frequency of each of the hexadecimal integers from '0' to 'f' among the 2,500,000 integers, and print it. See Input / Output and explanation of Sample Input / Output for clarity.
Input

The first line of input contains an integer T (1 ≤ T ≤ 10), the number of test cases. Then follows the description of T test cases. You should assume that the array has exactly 10,000,000 bits and that the bits are all unset at the start of each test case. The first line of each test case contains an integer N (1 ≤ N ≤ 10,000), the number of operations performed. The next N lines contain two integers separated by a space, the start_index and end_index for the respective operation. Note that the flip operation is performed from start_index to end_index, inclusive. Also, the array is 1-indexed - meaning, the smallest index is 1 and the largest index is 10,000,000.
Output

For each test case, output 16 integers on a single line, separated by single space characters. The first integer should represent the number of times 0 occurs among the 2,500,000 hexadecimal integers created according to the problem statement. The second integer should represent the number of times 1 occurs among the 2,500,000 hexadecimal integers created according to the problem statement, and so on.
Constraints

1 ≤ start_index ≤ end_index
start_index ≤ end_index ≤ 10,000,000
Sample Input

2
2
1 4
9999997 10000000
2
3 6
5 8

Sample Output

2499998 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2
2499998 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0

Explanation

In the first test case, after we perform the two operations and split the array into 2,500,000 groups of 4 bits, the first and the last group will have all 4 bits set - representing 'f' hexadecimal digit. All the other groups will have all 4 bits unset - representing '0' hexadecimal digit.
In the second test case, after we perform the two operations and split the array into 2,500,000 groups of 4 bits, the first two groups will have the state 0011. This represents the hexadecimal digit '3'. All the other groups will have all the 4 bits unset - representing '0' hexadecimal digit.

Dave's Father wants to make chocolates for his birthday. The volume of every chocolate will be 2 cm3. Every chocolate will be cuboid in shape. He has a box of a*b*c dimensions (again a cuboid). Given an input a,b,c write a function to find out if x number of chocolates of 2cm3 volume can fill the box completely. If so, find the number of chocolates too (x).

You are planning a big programming conference and have received many proposals which have passed the initial screen process but you're having trouble fitting them into the time constraints of the day -- there are so many possibilities! So you write a program to do it for you.

The conference has multiple tracks each of which has a morning and afternoon session.
Each session contains multiple talks.
Morning sessions begin at 9am and must finish by 12 noon, for lunch.
Afternoon sessions begin at 1pm and must finish in time for the networking event.
The networking event can start no earlier than 4:00 and no later than 5:00.
No talk title has numbers in it.
All talk lengths are either in minutes (not hours) or lightning (5 minutes).
Presenters will be very punctual; there needs to be no gap between sessions.


Note that depending on how you choose to complete this problem, your solution may give a different ordering or combination of talks into tracks. This is acceptable; you don’t need to exactly duplicate the sample output given here.

Test input:
Writing Fast Tests Against Enterprise Rails 60min
Overdoing it in Python 45min
Lua for the Masses 30min
Ruby Errors from Mismatched Gem Versions 45min
Common Ruby Errors 45min
Rails for Python Developers lightning
Communicating Over Distance 60min
Accounting-Driven Development 45min
Woah 30min
Sit Down and Write 30min
Pair Programming vs Noise 45min
Rails Magic 60min
Ruby on Rails: Why We Should Move On 60min
Clojure Ate Scala (on my project) 45min
Programming in the Boondocks of Seattle 30min
Ruby vs. Clojure for Back-End Development 30min
Ruby on Rails Legacy App Maintenance 60min
A World Without HackerNews 30min
User Interface CSS in Rails Apps 30min

Test output:
Track 1:
09:00AM Writing Fast Tests Against Enterprise Rails 60min
10:00AM Overdoing it in Python 45min
10:45AM Lua for the Masses 30min
11:15AM Ruby Errors from Mismatched Gem Versions 45min
12:00PM Lunch
01:00PM Ruby on Rails: Why We Should Move On 60min
02:00PM Common Ruby Errors 45min
02:45PM Pair Programming vs Noise 45min
03:30PM Programming in the Boondocks of Seattle 30min
04:00PM Ruby vs. Clojure for Back-End Development 30min
04:30PM User Interface CSS in Rails Apps 30min
05:00PM Networking Event

Track 2:
09:00AM Communicating Over Distance 60min
10:00AM Rails Magic 60min
11:00AM Woah 30min
11:30AM Sit Down and Write 30min
12:00PM Lunch
01:00PM Accounting-Driven Development 45min
01:45PM Clojure Ate Scala (on my project) 45min
02:30PM A World Without HackerNews 30min
03:00PM Ruby on Rails Legacy App Maintenance 60min
04:00PM Rails for Python Developers lightning
05:00PM Networking Event

Given a binary tree (not search tree), find the path which adds up to given sum.