CareerCup

pair programming example question with code for thoughworks interview

Find out the output. Or Correct it if something is wrong.

#include <iostream>
#include<typeinfo>
using namespace std;

class base{
public:
	int a;
	base():a(0)
	{}
	int getA(){return a;}
};
class der:public base
{
public:
	int b;
	der():b(1)
	{}
	int getB(){return b;}
};
void display(base *obj, int ele)
{
	for(int i = 0; i < ele; i++)
	{
        cout << (obj+i)->getA() <<endl;
	}
}

int main()
{

    int i = 3;
    base arrb[i];
    display(arrb, 3);
    der arrd[i];
    display(arrd, 3);
    return 0;
}

The output is looking like

0 0 0 0 1 0

To me the output should be

0,0,0,0,0,0 //6 0's

But, how come

1

is coming in?

Our merchants receive "weekly" invoices, following these rules:

- Each Saturday (00:00 UTC) marks the beginning of a new billing period
- Each 1st of a month (00:00 UTC) marks the beginning of a new billing
period
- Within a year, billing periods are numbered consecutively, starting
with billing period number 1 on Jan 1

Billing periods can therefore be identified by a year and a period
number.

Task:
-----
Write the following functions:

*) For a given date, return the id of the latest period that ends
before this date, e.g.

auto getLatestBillingPeriodId(Date date) -> PeriodId;

*) For a given period id, return the begin and the end date of the
billing period, e.g.

auto getDateRange(PeriodId periodId) -> std::pair<Date, Date>;

Stanford has to select a team of dodgeball players from its class of 2013. There are n students in the class and each student is identified by his/her student ID, which is between 1 and n. The coach has to select K players out of these n students for his team. But there is a twist, if among the K dodgeball players, a player's ID number evenly divides another player's ID number, then there is a high chance of them getting into a fight. The coach will do his best to select the K players so that no pair of players among them will want to fight one another. But if the game turns out to be very popular, this becomes impossible. Complete the function dodgeBall to return the minimum size of K at which it becomes impossible to choose a dodgeball team that has no fighting?

Input Format:
One line of text, containing the size of the class of 2013, n

Constraints:
1 <= n <= 5,000,000,000
n is guaranteed to be an even number

Output Format:
The minimum size of K that guarantees the existence of 2 players who fight with each other in any K-sized subset of the class.

Sample Input:
4

Sample Output:
3

Explanation:
If the team = {1,2,3}: 1&2 or 1&3 can fight with each other
If the team = {1,3,4}: 1&3 or 1&4 can fight with each other
If the team = {2,3,4}: 2&4 can fight with each other
If K=2, then the teams {3,4} or {2,3} will have no fights. So 3 is the smallest value of K for which any K-sized team, must include a fighting pair.

Sample Input:
2

Sample Output:
2

Explanation:
The team = {1,2}: 1&2 can fight with each other

A flipping rule is given as a follows: Consider a series of positive integer. Take three numbers in the series next to each other. On applying the flipping rule to these numbers, the right most number will go to the left most number position and the other two numbers will move one position to the right at the same time. The rule can be applied to any three numbers present next to each in the series and can be applied as many times as needed.
Given n as the number of element in the original series, elements of the original series and a target series of a numbers, figures out if the target series can be created by flipping numbers of the original number and output the word “POSSIBLE” followed by the number of times the flipping rule has to be applied. In case, the target series cannot be formed, output the word “IMPOSSIBLE”.
Example :
For a series with 4 elements in it, 1 3 4 2 a new series = 4 3 2 1 can be formed by applying flipping rule as follows, From the table below we can say the output is POSSIBLE 3.
Steps
Series
The three Numbers Flipped
Resultant Series
1
1 3 4 2
1 3 4
4 1 3 2
2
4 1 3 2
1 3 2
4 2 1 3
3
4 2 1 3
2 1 3
4 3 2 1


Example input
Example OutPut
4 1 3 4 2 4 3 2 1
POSSIBLE 3
6 1 2 3 4 5 6 6 5 4 3 2 1
IMPOSSIBLE

Description:

A company, create classes for each type of employee and calculate working hours and wages/salaries that will be received.

Example General Manager, IT Manager, Accounting, Marketing, Finance, Procurement Managers

Manager and Higher level employees wont have overtime wage. Overtime wage is 1.5 times higher than the usual wage. Working hours are limited as 8 hours. More than this limit will be considered as overtime.

Inputs:

Employee Name, Surname

Title/Role

Salary

Daily Working hour

Outputs:

Date

Employee Name, Surname

Daily Wage.

Assume that const_cast is not in place for C++, can you please write the code to do such casting?

How would you implement an LRU cache using just a *single* container ? i.e., map or unordered_map ?

The cache must support operations:
1. value_t find(key_t) - find a certain value in cache
2. insert(key_t, value_t) - insert a new value to the cache (with optionally deleting an LRU entry)

There is a garden of strawberry plants represented by a 2D, square array.Each plant represents an element in the matrix ie it has a number of strawberries. If a plant doesnt have strawberries it is denoted by 0. If 0 is encountered you cannot travel through that path.



You can start from any cell along the left border of this ground (i.e the matrix) and travel until it finally stops at one cell in the right border, and you can only move to up/down/right. You can only visit each cell once. Calculate the maximum number of berries is obtained.

Backtracking using Dynamic programming is one of the methods i have thought of.

Also there some special conditions:

a.Even in the left border and right border, we can go up and down.

b. When we are at the top cell of one column, we can still go up, which demands us to

pay all current strawberries , then we will be teleported to the bottom cell of this column and vice

versa.

Input: user enters dimensions of ground ie size of matrix and the matrix itself

Output: is the maximum number of strawberries collected without encountering 0; in case we do we display 0.

Till now i have managed to find the largest value in the first column of the matrix but i am facing difficulty in testing the neighbours of that cell.

Also i am not able to store the position of the cell which i started from or even mark it.

Input

4 4

-1 4 5 1

2 -1 2 4

3 3 -1 3

4 2 1 2

output

23




Input

4 4

-1 4 5 1

2 -1 2 4

3 3 -1 -1

4 2 1 2

output

22

Consider the problem of building a wall out of 21 and 31 bricks (horizontalvertical dimensions) such that, for extra strength, the gaps between horizontally-adjacent bricks never line up in consecutive layers, i.e. never form a "running crack".

There are eight ways of forming a crack-free 93 wall, written W(9,3) = 8.
Calculate W(32,10).

I need solution for this in C / C++ asap
.
Thanks much in advance for your help.

Vivek.

Post order traversal for an N-ary tree iterative way.
Given,
struct Node {
int val;
vector<Node*> children;
};

Without modifying original structure.

Post order traversal for an N-ary tree iterative way.
Given,
struct Node {
int val;
vector<Node*> children;
};

To simplify you can modify the structure.

Implement a method for the following signature:

void * alignedAllocate(size_t sizeInBytes, size_t alignment) {
}

The method should allocate memory for the given size and the pointer should be aligned.
For example if

p = alignedAllocate(1000,64);

p%8 should be 0.

Implement a second method that deleted the pointer give p.

Extend the delete method to handle multiple p's.

// Given the root node of a tree in which each node can contain ANY number of chidren (i.e. NOT binary, unbalanced), find the level in the tree with the most nodes

/*

A Level 0
/ \
B C Level 1
/|\ ||
abc ef
Answer: Level 1

Given a BST write a function that looks for a value.

Sort a matrix such that rows in ascending order and columns should be in descending order.

Skynet
Skynet has grown to become the dominant force on earth and has almost completely wiped out the
human race. Skynet has been
building robots ever since it's inception and has been updating it's models every year while making
them better. Skynet wants to annihilate humanity completely. It plans to remove one last band of
humans lead by John Connor. Skynet thinks it can destroy these humans using only two of it's robots.
But Skynet doesn't want to send two robots with the same model number lest John Connor finds out a
weakness in that model and easily destroy both of them.
Skynet has at its disposal N robots and to save space Skynet has stored information about pairs of
robots belonging to the same model. If it doesn't have any info stored for a particular robot then it is
implied that the robot is the only one in that model.
Given these constraints, in how many ways can Skynet pick two robots to destroy John Connor and
his rag tag group of humans.
Inputs
N Total
number of robots. Each robot is assigned a number from 0 to N1
(2 <= N <= 100000)
P Number
of pairs for which Skynet has information (2 <= P <= 100000)
This is followed by P pairs. Each pair has two numbers P and P each where 0<=P <=N1
and
0<=P <=N1
and P != P
Output
Number of ways in which Skynet can select 2 robots such that both the robots are different models.
Example Input:
4 2
0 1
2 3
Example Output:
4
Explanation:
Here robots 0 and 1 are of one model, say model A. And 2 and 3 are of another model, say B.
Therefore the total number of
possibilities of picking 2 robots such that no two robots are of the same model are (
0, 2), (0, 3), (1, 2)
and (1, 4) = 4

What is sister delegation and how is it implemented ?

What design pattern you will use in this scenario :
One class will print odd numbers and other class will print even numbers.

How to register new classes in factory pattern ?

Given an array of integers and a number. WAP to find the pairs which sum of upto given number.

I solved it. Then he asked about writing test cases for this function.

I wrote below test cases

1.) All the elements should be number.
2.) Length of array should not be 0.
3.) Array itself should not be null.
4.) Given number, arrayLength can be represented by 32bits or 64 bits.
5.) number should not be negative.
6.) Input does not has pair, It should return false
7.) Input has pair, It should return true
8.) Input has all negative values and pair exists, then function should return true
9.) Input has all negative values and pair does not exists, function should return false

He told that he is looking for more test cases. Can you guys think of some more complex test cases.

Insert a value into a sorted linked list.

Using C/C++ write a small function (around 5 lines in the body) to insert a value in a sorted linked list. Take into consideration that the list might be empty at first, and the function should cover the cases of insertion at the head and tail...

PS what the interviewer is looking for is the ability to write a small C/C++ code that solves the question and not the algorithm per se which is trivial

GLaDOS is feeling bored, so she decided to come up with a board game. The game is as follows. There is
board of dimension n x n (2 <= n <= 10). Each position in this board is either a 0 or a power of 2, between 2
and 2048. Once the board is set up, there are only two moves allowed - move all left or move all right.
The way move all left works is as follows:
For every row on the board, starting from the rightmost position each element is moved to its left. An
element with a zero value does not move. An element with non-zero value can move to its left if the value of
the element to its left is a 0 or has the same value as the current element.
In case, the element to the left is 0 then the element and 0 swap positions i.e., 4 0 0 4 would become 4 0 4 0
In case, the element to the left has the same value as the current element then the left element combines
with its right element and creates an element with double the value in place of the right element and leaves
a 0 in its current place. For e.g., 2 2 would become 4 0 or 2 2 2 2 would become 4 0 4 0.
The combining operation can cause a cascading operation i.e., if the new element created has the same
value as the element to its left, it can combine again.
For e.g., if a row had 8 4 2 2, move left would combine 2 and 2 to form 4 leading to 8 4 4 0. Now, it is
possible to combine further as the element to the left of 4 has the same value, thus after the second
combine, the row would be 8 8 0 0. And again 8 and 8 would form a 16. Thus the final values in the row
would be 16 0 0 0.
But if the row was 8 4 2 0 2, then moving left would result in 8 4 2 2 0. The cascading operation is allowed
only after a combination operation, There would no cascading operation if the element is swapped with 0.
Similar rules apply for move all right, wherein for every row elements starting from the leftmost position
move to their right.
You can either choose move all left or move all right operation but not both. Now given a state of the board,
you have determine what will be the maximum value on the board after either move all left or move all right.
Example
3
2 2 0
2 2 4
2 0 2
Move all left would result in:
4 0 0
4 0 4
2 2 0
The maximum value on the board after this move is 4.
Move all right would result in:
0 4 0
0 0 8
0 2 2
In the first row, 2 and 2 combines to form 4. In the second row, left most 2 combines with 2 to form 4. As the
element to its right has a value 4, combination operation cascades to form 8.
The maximum value on the board after this move is 8.
Now of the two operations, the higher of the two maximum values is 8. Thus the expected output is 8.
Input
3
2 2 0
2 2 4
2 0 2
Output
8
Input
3
0 0 4
0 2 2
0 4 8
Output
8
Time limit per test case:
1 second(s)

tower Of Hanoi using priority queue

I was given 90 minutes to complete this test.
I didn't understand how the sample test cases arrived at their return output. Can anyone explain?
================
Approximate Matching (Coding)

You are given 3 strings: text, pre_text and post_text. Let L be a substring of text.
For each substring L of text, we define pattern_score as follows:
* pre_text_pattern_score = highest n, such that first n characters of L are equal to the last n characters of pre_text and occur in the same exact order.
* post_text_pattern_score = highest n such that last n characters of L are equal to the first n characters of post_text and occur in the same exact order.
* pattern_score = pre_text_pattern_score + post_text_pattern_score
For example, if L = "nothing", pre_text = "bruno", and post_text = "ingenious", then
* pre_text_pattern_score of L is 2 because the substring "no" is matched, and
* post_text_pattern_score is 3 because the substring "ing" is matched.
* pattern_score is 5 = 2 + 3
Your program should find a non-empty substring of text that maximizes pattern_score.
* If there is a tie, return the substring with the maximal pre_text_pattern_score.
* If multiple answers still have a tied score, return the answer that comes first lexicographically.
Complete the definition of function string calculateScore(string text, string prefix,string suffix)
Constraints:
* text, pre_text, and post_text contain only lowercase letters ('a' - 'z')
* 1 <= |text| <= 50
* 1 <= |pre-text| <= 50
* 1 <= |post-text| <= 50
(where |S| denotes the number of characters in string S)
* It is guaranteed that an answer will always exist; i.e. there will always be a substring in text that matches either at least one character at the end of pre-text or at least one character at the beginning of post-text.

Sample case #1
text: "nothing"
prefix: "bruno"
suffix: "ingenious"
Returns: "nothing"

Sample case #2
text: "ab"
prefix: "b"
suffix: "a"
Returns: "b"

Point errors (if any) in the following pointer code and explain what it does...

char* cp(char *a)
{
char *f;
f=(char*)malloc(strlen(a)*sizeof(char));
while(*a != 0)
{
*f=*a;
f++;
a++;
}
cout<< f;
return f;

}

Print the following pattern using C/C++

(For n=4)

1
2*3
4*5*6
7*8*9*10
7*8*9*10
4*5*6
2*3
1

PS: Printing above triangle is easy and I easily did it, but couldn't print the lower triangle.

In C++, what's the difference between public and private? what's the purpose of this and please illustrate a design example with this.

The SHIELD is a secretive organization entrusted with the task of guarding the world against any disaster. Their arch nemesis is the organization called HYDRA. Unfortunately some members from HYDRA had infiltrated into the SHIELD camp. SHIELD needed to find out all these infiltrators to ensure that it was not compromised.

Nick Fury, the executive director and the prime SHIELD member figured out that every one in SHIELD could send a SOS signal to every other SHIELD member he knew well. The HYDRA members could send bogus SOS messages to others to confuse others, but they could never receive a SOS message from a SHIELD member. Every SHIELD member would receive a SOS message ateast one other SHIELD member, who in turn would have received from another SHIELD member and so on till NickFury. SHIELD had a sophisticated mechanism to capture who sent a SOS signal to whom. Given this information, Nick needed someone to write a program that could look into this data and figure out all HYDRA members.

Sample Input
Nick Fury : Tony Stark, Maria Hill, Norman Osborn
Hulk : Tony Stark, HawkEye, Rogers
Rogers : Thor,
Tony Stark: Pepper Potts, Nick Fury
Agent 13 : Agent-X, Nick Fury, Hitler
Thor: HawkEye, BlackWidow
BlackWidow:Hawkeye
Maria Hill : Hulk, Rogers, Nick Fury
Agent-X : Agent 13, Rogers
Norman Osborn: Tony Stark, Thor

Sample Output
Agent 13, Agent-X, Hitler


You can code in any language of your choice. Input and Output must be in the same format as above

Reverse left node of BT.
1 (ROOT)
/ \
2 3
/ \
4 5
/ \
6 7

to

1
/
2 - 3
/
4 - 5
/
6 - 7
(6 is root)