CareerCup

Given a list of sentences and a list of phrases. The task is to find which sentence(s) contain all the words in a phrase and for every phrase print the sentences number that contains the given phrase.
Constraint: A word cannot be a part of more than 10 sentences.
Examples:

Input:
Sentences:
1. Strings are an array of characters.
2. Sentences are an array of words.
Phrases:
1. an array of
2. sentences are strings
Output:
Phrase1 is present in sentences: 1,2
Phrase2 is present in sentences: None
Since each word in phrase 1 exists in both the sentences,
but all the words in second phrase do not exist in either.

given array and max element in array. Find no. of elements present between a given range in O(1). You can do one time processing of array.

LCA of directed graph.

Design Movie Review system using OOP concepts. Code should pass all test cases.

Given movement of Robot -
G-GO one unit
L-Turn left
R-Turn right

Given an input of string have to find whether there exists a circle which the robot would traverse. Input of string is the set of G,L,R have to return yes or no.

Given a list of strings. Check whether any two strings, if concatenated will form palindrome or not.

There is a hierarchical structure in an organization. A party is to be organized. No two immediate subordinates can come to the party. A profit is associated with every person. You have to maximize the total profit of all the persons who come to the party.

Given a number line from -infinity to +infinity. You start at 0 and can go either to the left or to the right. The condition is that in i’th move, you take i steps.

How to Design an Meeting scheduler

Implement a Message Broker, with Publisher and Subscriber. There can be multiple Topic or Subject in Message Broker.

Given login/logout time of all users for a particular website in below form.
userId, login time, logout time.

Now store this data in some data structure, so that we can efficiently query total number of users who logedin and logedout in given time range.

Write a program to check if a chess move is valid. The api should be extendible to cover cases like castling and pawn promotion.

Implement a finite state machine.
– The machine should have one start state and can have multiple end states
– It should be extensible (I should be able to add any number of states or transitions at any time)
– I should be able to set notifications on or off for any state or for the whole state machine

You are given some equations which may contain > or = on different-different operand. For example there are valid input and invalid (a=5, b<a=50)

String e1 = "a>b=1";
String e2 = "a>b=2";
String e3 = "a>c>e=3";
String e4 = "a>c>f=4";
String e5 = "b>a=5";
String e6 = "a>b>c=5";
String e7 = "b=7";
String e8 = "a>b>c>d=99";
String e9 = "a>b=99";

You need to create JSON string from it.
{
‘a’: {
‘b’: [1,2,99],
‘c’: {
‘e’:3,
‘f’:4
}
},

‘b’: {
‘a’ : 5

}
}

Input: You are given those string in string array
Output:

Construct JSON
Print it

There is down-turn in the ship-building industry. Ace Shipping Corp (ASC) wants to be prepared by having a system that will help evaluate the total cost saving they will achieve if they were to ‘let go’ some employees.

Following are the rules for drawing up this Firing List:

Each manager at every level in the organization will have to contribute ‘heads’ from his team to the firing list

The input to the system would be a small integer k (=1,2, etc) which would be the number of employees chosen per manager. The output would be the total cost saved for this k. Different values of k would give an idea of the total cost saving achieved.

The primary selection criteria is Performance Rating. k employees with the minimum rating under a given manager are to be selected.

If two employees have the same rating, the one with the higher salary gets selected (to maximize cost saved)

The activity might be requested for the sub-org under any manager. The default is to consider the entire org.

Although total number of reportees for a manager is usually of the order of 10, it could possibly be a much larger number in some org too. An optimal way of choosing the k reportees would be preferred.

The following information needs to get stored per Employee:

Employee ID (unique)

Name

Performance Rating (1-5, 1 is lowest, 5 is highest)

Salary (Rs)

There is a car company and customers ask the car company for 'n' cars for start - end time intervals.

A company can get multiples request for the cars, find the minimum numbers of cars that the car company should have, to satisfy all the requirement for the given list of time intervals:

Eg :

for interval 1-3 cars needed are 2
for interval 2 -3 cars needed are 3
for intervals 3-4 cars needed are 4
for intervals 5-6 cars needed are 2

Answer is 5 for above, as we there is overlap between interval 1-3 & 2-3

Given a string regex and another string pat find whether the pattern is acceptable against given regex string.
Regex string contains following characters and special characters:
1. Normal alphabets – a to z and A to Z
2. ‘$’ – all string should end with all characters preceding $
Example:
Regex :abc$ ,
Pattern: abcd(Not acceptable) , abc(acceptable), ab(Not acceptable), dhfusdhabc(acceptable) etc..
3. ‘^’ – all string should start with all characters exceeding ^
Example: Regex : ^abc
Pattern: abcd(acceptable) , abc(acceptable), ab(Not acceptable), dhfusdhabc(NOT acceptable) etc..
Regex: ^ then only pattern acceptable is null.
4. ‘.’ – any character can be mapped to dot except null
Example 1: Regex : .abc
Pattern: Zabc(acceptable) , abc(NOT acceptable), ab(Not acceptable), habc(acceptable) etc..
Example 2: Regex :a.bc
Pattern: abc(NOT acceptable) , aXbc(acceptable), ab(Not acceptable), habc(NOT acceptable) etc..
5. ‘*’-the character just preceding * can be repeated n time where (n>=0)
Example 1: Regex :abc*de
Pattern: abccccccccccde (acceptable), abcde(acceptable), abcccd(not acceptable)

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

Design and implement a scalable multi-player N*N TicTacToe game.

Billions of 2 digit number is coming from stream and you have a variable avg. which store only 2 digit number that means you cant store 2 number in any temp variable also.calculate avg on incoming stream

Design a data structure in which we can do all CRUD operations in O(1) ?

CRUD- Create, Retrieve, Update, Delete

2. There is a maze of size n*n. Tom is sitting at (0,0). Jerry is sitting in another cell (the position of Jerry is input). Then there are k pieces of cheese placed in k different cells (k <= 10). Some cells are blocked while some are not. Tom can move to 4 cells at any point of time (left, right, up, down one position). Tom has to collect all the pieces of cheese and then reach to Jerry’s cell. You need to print the minimum no. of steps required to do so.


I know it is possible throgh dp but please provide me solution with approoch i am unable to solve it please

Given huge database of songs design search data structure and algorithm to search all songs with words starting with the letters entered and words matching the sequence of words entered.
Suppose the songs are:
1. Every night in my dreams
2. Listen to my heart
3. Show me the meaning
4. Night in London
5. Night changes

Entering "m" should list 1,2 and 3. "my" should list 1 and 2. "Night" should list 1,4 and 5. "Night in" should list 1 and 4.

Given access to live stream of purchases, design the algorithm to list the top 100 products in past X minutes/hours/days.

Implement a meeting organizer

Given a pond where all the stones are lined at a distance of one unit (C in each row and there are R such rows).

Each stone has a special value which denotes the length of the jump the frog can make i.e if frog is on stone (x,y) and value is k then frog can jump to (x+dx,y+dy) where dx+dy=k and frog doesn’t leave the bounds.

Find the min number of jumps to reach the stone at (R,C). Also print the path taken by frog to reach the stone.

Given 1000 elephant ,none of whom exact heights are known, there are statements given which will be of two forms

i- E_i is taller than E_j
OR
ii- E_i is smaller than E_j

Calculate the ascending order of the elephants(in terms of height).

For ex-
1) E1 is taller than E3
2) E3 is smaller than E2
3) E2 is taller than E1

Then order would be E3, E1, E2

Given a mxn grid, each of it’s element be either ‘.’, ‘R’, ‘G’ or ‘B’,
where ‘.’ -> empty, ‘R’ -> Red, ‘G’ -> Green, ‘B’ -> Blue
A Blue strip has width 1 and length greater or equal to one.
A Red strip has length 1 and width greater or equal to one.
If a Red strip and a Blue strip overlaps, the overlapped portion will become ‘G’.
Find the minimum number of strips required to cover the whole grid.

1<= m,n <=100

Input
5 5
..B..
..GRR
..B..
R....
R....
Output
4

You are given a String S that consists of characters '0' and '1' only.Return the smallest positive integer K such that it is possible to cut S into K pieces, each of them being a power of 5. If there is no such K, return -1 instead.
Examples
0)

"101101101"
Returns: 3
We can split the given string into three "101"s.

Note that "101" is 5 in binary.

1)

"1111101"
Returns: 1
"1111101" is 5^3.

2)

"110011011"
Returns: 3
Split it into "11001", "101" and "1".

3)

"1000101011"
Returns: -1

4)

"111011100110101100101110111"
Returns: 5

Design and code the sudoku solver.