CareerCup

Given an array of sets find the one that does not belong:
example: [[a,b,c,d], [a,b,f,g], [a,b,h,i], [j,k,l,m]]
output: [j,k,l,m]

We can see above that the first three sets have a subset [a,b,c] and the last one does not. Note: There may be a case where the outlier set does have elements contained in the input group. In this case we have the find the set that has the least in common with the other sets.

Q. find the number of ways a string can be formed from a matrix of characters.
It can start forming a word from any position in mat[i][j] and can go in any unvisited direction from the 8 directions available across every cell [i][j].

sample case :

input:

N = 3 (length of string)
string = fit

matrix :
fitptoke
orliguek
ifefunef
tforitis

output: 5

explanation:
num of ways to make 'fit' from matrix chars are 5 as given below sequence:
(0,0) (0,1)(0,2)
(2,1) (2,0)(3,0)
(2,3) (1,3)(0,4)
(3,1) (2,0)(3,0)
(2,3) (3,4)(3,5)


How can we solve it efficiently without doing DFS across every position [i][j], which makes time complexity exponential?
Is there a better way possible in terms of time complexity? Maybe caching of values or something!

What to do when we are poor on coding

Class A has two data members which are instances of class B and class C. Class B needs an instance of class C to be created. We have to create an instance of object A on stack like 'A objA' in main function. 'new' operator should not be used anywhere.no objects on the heap

Given a list of 2d points, if any two points have distance(straight line) <= k , group them together. For example. [P1,P2,P3], P1 to P2 <=k, P2 to p3<=k, p1 to p3>k. they are still in the same group. (distance relationship is chainable ) ask how many groups can you find ? I can think of N^2 time complexity with union and find. but how to do better than that? maybe NlogN or O(N)?

reverse an array for k distance.
[2,3,1,5,4] and k =3
output : [2,3,1,5,4]
method
void reverse(int[] arr, k)

this method will only reverse the array

write another method which will sort the array by incorporating reverse method inside sort.

You must have to call reverse(arr,k) method to sort the array. You are not allowed to modify the reverse method

Giving a the following:

A list of a store items T={t_1, t_2,...,t_n}.

A list of prices of each item P={p_1, p_2,...,p_n}.

A list of quantities of each item Q={q_1, q_2,...,q_n}, respectively.

And total bill M.

Our goal is to find any possible list of items that its total value is equal to M using dynamic problem.

Write down a recursive solution.

Given a set of horizontal and vertical line segments, find the number of squares formed by them?

Design a voting system. 100M users will be logging in within a window of 24h (not necessarily uniformly). Every user will be able to choose from a fixed list of options. If the user has already voted the system should not let them to vote a second time. Additional constraint: only the first 100K votes are accepted. If the quota is exceeded any attempt to vote should be rejected.

A mobile phone company wants to deploy network of cell towers to provide good signal coverage for its customers. But it doesn't want to have too many towers because they can interfere with one another. All towers are laid out over a 2-dimensional surface and that towers have same sized circular signal zone. You can determine whether their signal zones will overlap in 0 1) time. Give a parallel algorithm for choosing maximal subset of towers that cover non-overlapping areas.

I was not sure if this can be solved using DP?

How can you read last 10 lines of a big file and a follow up question was how would you extend this process optimally to read last 10 lines of 1000s of files?

Implement a comparator class that is capable of sorting by multiple key/order pairs, each pair being a tiebreaker for the previous.

You're running a pool of servers where the servers are
numbered sequentially starting from 1. Over time, any
given server might explode, in which case its server
number is made available for reuse. When a new
server is launched, it should be given the lowest available number.

Write a function which, given the list of currently
allocated server numbers, returns the number of the next server to allocate.

For example, your function should behave something like the following:

>> next_server_number([5, 3, 1])
2
>> next_server_number([5, 4, 1, 2])
3
>> next_server_number([3, 2, 1])
4
>> next_server_number([2, 3])
1
>> next_server_number([])
1

Server names consist of an alphabetic host type (e.g. "apibox") concatenated with the server number,
with server numbers allocated as before (so "apibox1",
"apibox2", etc. are valid hostnames).

Write a name tracking class with two operations,
allocate(host_type) and deallocate(hostname).
The former should reserve and return the next
available hostname, while the latter should release
that hostname back into the pool.

# For example:
#
# >> tracker = Tracker.new()
# >> tracker.allocate("apibox")
# "apibox1"
# >> tracker.allocate("apibox")
# "apibox2"
# >> tracker.deallocate("apibox1")
# nil
# >> tracker.allocate("apibox")
# "apibox1"
# >> tracker.allocate("sitebox")
# "sitebox1"

Write a map implementation with a get function that lets you retrieve the value of a key at a particular time.
t:0 A =1
t:2 A = 2
get(A, t:1) -> 1
get(A, t:3) -> 2

Card Game

Card game rule: the hand is drawn from a pack of cards (no jokers).
Play cards ONLY when they are
1. 3 of a kind ('AAA' ) or 4 of a kind('AAAA’).
2. a straight flush of 3 or more cards('JQK' or 'A23456...' in the same suit).
Find out whether the player is able to play the whole hand given.
e.g. [Spade A, Spade K, Spade Q, Diamond Q, Heart Q] return false.
[Spade A, Spade K, Spade Q, Diamond Q, Heart Q, Club Q] return true.

Implement a function which accepts a number and returns top 10 big numbers the function is called with so far;

If we call the function with 1.. to 100 , for the call function(100) the function will return 91 to 100 in reverse order since they are top 10 biggest number so far

Given a list L of video names and their watch rates, write a function that will return the videos with the top 10 watch rates. Video names may appear more than once.

Example:

L = [(‘abc’, 10), (‘def’, 15), (‘ghi’, 10), (‘abc’, 12), …, (‘xyz’, 100)]

The function should return [‘xyz’, ‘abc’, …, ‘def’, ‘ghi’]

Write a function that takes a list L and returns a random sublist of size N of that list. Assume that the indexes must be in increasing order. That is, you cannot go backwards.

Example:

L = [1, 2, 3, 4, 5]
N = 3

The function should return one of these lists:

[1, 2, 3]
[1, 2, 4]
[1, 2, 5]
[1, 3, 4]
[1, 3, 5]
[1, 4, 5]
[2, 3, 4]
[2, 3, 5]
[2, 4, 5]
[3, 4, 5]

Consider an undirected tree with N nodes, numbered from 1 to N. Each node has a label associated with it, which is an integer value. Different nodes can have the same label. Write a function that, given a zero indexed array A of length N, where A[j] is the label value of the (j + 1)-th node in the tree and a zero-indexed array E of length K = (N – 1) * 2 in which the edges of the tree are described, returns the length of the longest path such that all the nodes on that path have the same label. The length is the number of edges in that path.

Example:

A = [1, 1, 1, 2, 2]
E = [1, 2, 1, 3, 2, 4, 2, 5]

This tree is shown below. A node follows the form label, value.

----------1, 1

-----1, 2 1, 3

2, 4 2, 5
The function should return 2, because the longest path is 2->1->3, and there are 2 edges in this path.

Assume that 1 <= N <= 1000 and each element of the array A is an integer in the range [1, 1000000000].

Given a string A consisting of n characters and a string B consisting of m characters, write a function that will return the number of times A must be stated such that B is a substring of the repeated A. If B can never be a substring, return -1.

Example:
A = ‘abcd’
B = ‘cdabcdab’
The function should return 3 because after stating A 3 times, getting ‘abcdabcdabcd’, B is now a substring of A.

You can assume that n and m are integers in the range [1, 1000].

Given 1-D list of co-ordinates determine if interval (a,b) is covered

Ex - [(2,5), (5,7),(1,4)] and interval = (1,6)
return true
Explanation - Points 1 to 6 lies in list of interval given 1 to 4. 2 to 5 and 5 to 7.

[(1,4),(6,7),(2,5)] and interval - (1,6)
return false
Explanation - Distance between 5 to 6 is not covered in the list given so return false

Compare two documents(string array) based on n grams.
e.g doc1 – Today is Sunday.
doc2 – Today is Saturday
if n = 2 then number of duplicates is 1 (Today is)
if n = 1 then number of duplicates is (Today, is)
if n = 3 duplicates is 0

Given a bench with n seats and few people sitting, tell the seat number each time when a new person goes to sit on the bench such that his distance from others is maximum

Given a room with thief on left side of the room with finite number of sensors. He has to reach on right side missing the sensors. Each sensor is placed at any random point in the room and has its coverage in the radius r. Find out if the thief can reach to the right side without touching the range of any sensor.

Given an infinite chessboard, find minimum no. of steps for a knight to reach from the origin to (x, y).
Extension A list of forbidden coordinates are introduced where knight can’t reach. Handle this in your code. Make sure the infinite loop is handled since the board is infinite.

Given a matrix of people(denoted by small alphabets) and bikes(denoted by capital alphabets), find the nearest bike for a given person.
How will you change your solution if you have to find bikes for a set of people? (assuming multiple bikes can be at the same distance from 1 person)

Given an array of n integers, find the lexicographically smallest subsequence of length k.

Given a list of player names and their scores – {Carl, 70; Alex, 55; Isla, 40}, design a data structure that can support following modules in optimal time-
i) updateEntry(string name)
ii) getEntryFromRank(int rank)

Given an input stream of boolean values, design a data structure that can support following modules in optimal time-
i) setTrue(index)
ii) setFalse(index)
iii) setAllTrue()
iv) setAllFalse()
v) getIndex(index)

Given two strings, A and B, of equal length, find whether it is possible to cut both strings at a common point such that the first part of A and the second part of B form a palindrome.

Extension1. How would you change your solution if the strings could be cut at any point (not just a common point)?
Extension2. Multiple cuts in the strings (substrings to form a palindrome)? Form a palindrome using a substring from both strings. What is its time complexity?