CareerCup

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?

Given a stream of integers, a value k and a value w, consider the integers in the window w and chop off greater k and smaller k elements from the window w. From the remaining elements, compute the average.

Implement the version control map system which takes the snapshot of the versions of data. Implement the following functions:

put(key, value) -> puts the value again the key in the latest version of the map

get(key) -> get the value of the key for the latest version of the data

snapshot() -> take a snapshot and increment the version

getValVersion(version id, key) -> return value of the key of the particular version

Given various subsequences of an array, print the overall array:

Example: [1, 3, 5], [1, 3, 9], [9, 5]

Array : [1, 3, 9, 5]

A graph has N vertices numbered from 1 to N. We have two lists. One list M consisted of edges between vertices. The other list K consists of restricted paths. We have to add edges one by one from M and check whether the addition of the particular edge leads to a path between the restricted edges given in K. If it creates a path, we have to discard the edge.

Example: N = 4; K = {(1, 4)}; M = {(1, 2), (2, 3), (3, 4)}. Here, addition of edge (3, 4) will create a path between 1 and 4. Hence we discard edge (3, 4)

You are given 2 strings which are exactly same but 1 string has an extra character. Find that character.

You are given an array of million numbers and provided a range of index (say left, right). For multiple queries, each with input left and right indexes, output the maximum in that range.

Given (x, y) coordinates, create a function such that each coordinate is uniquely mapped to an integer. Also make sure that given an integer, you should be able to find (x, y) coordinates. So F(x, y) = z and also that inverse F(z) = (x, y).

We have to paint n boards of length {A1, A2…An}. There are k painters available and each takes 1 unit time to paint 1 unit of board. The problem is to find the minimum time to get
this job done under the constraints that any painter will only paint continuous sections of boards, say board {2, 3, 4} or only board {1} or nothing but not board {2, 4, 5}.

Input : k = 2, A = {10, 10, 10, 10}
Output : 20.
Here we can divide the boards into 2
equal sized partitions, so each painter
gets 20 units of board and the total
time taken is 20.

Input : k = 2, A = {10, 20, 30, 40}
Output : 60.
Here we can divide first 3 boards for
one painter and the last board for
second painter.

Given two numbers m and n. Find all numbers between these two numbers such that difference between adjacent digit is 1
For ex m =0 n =22
O/p - 0,1,2,3,4,5,6,7,8,9,10,12,21

N number of balloons are kept at different heights. You are asked to find out number of arrows to burst them. When an arrow hits the balloon it goes one level down.
Assume that the balloons are having same size.

for example given the balloons heights as array(Array will be given in decreasing order of size) :
5 4 3 3 2 2 1 1 1
minimum number of arrows to shoot them is: 3

explanation:
using first arrow shoot: 5 4 3 2 1
using second arrow shoot: 3 2 1
using third arrow shoot: 1

Example 2:
5 4 2 1

minimum number of arrows to shoot them is: 2
using first arrow shoot: 5 4
using second arrow shoot: 2 1

Expecting the solution to be in O(1) space complexity.

In a garden, there are several apples trees planted in a grid format. Each point (i,j) in the grid has |i| + |j| apples.

Allie can buy a square plot centred at (0,0). Find the minimum perimeter of the plot (1 unit having length = 1) such that she can collect at
least X apples. All plants on the perimeter of the plot are also included.

Sample:

Input = 1 Output = 8
input = 11 Output = 8
Input = 13 Output = 16

Given an array of integers A. calculate the sum of A[i] %A[j] for all possible i,j pair. return sum%(10^9+7) as an output solve this problem on o(n).

input :-
A=[1,2,3]
Output:-
5
Explanation:-
(1%1)+(1%2)+(1%3)+(2%1)+(2%2)+(2%3)+(3%1)+(3%2)+(3%3)

Print an unbalanced binary tree in level order with new lines after each level.

Say you have two large files (100 TB each) and only 1 MB of RAM. What's an efficient algorithm that will print the missing lines (diff)? The files don't necessarily contain duplicates.

The two files are not sorted and could have different ordering in both files.

e.g.:

File1 File2
A B
B A
C C
D E
F D
F

Output:
File 2: E
The input are two large files (containing strings).

The output is a list of strings telling you the presence of a line in File X and not in File Y.

P0, P1, ...., Pn players in tournament. In first level, P0 plays with P1, P2 plays with P3 and so on. In level 2, Winner of P0,P1 plays with winner of P2,P3. For i,j output level in which they will face each other assuming they win all games.

Given directory change command -

cd a/b/../c/d/e/../../

Output the visit count for each directory such as -
Root - 1
a - 2
b - 1
c - 2
d - 2
e - 1

Given a nested list of integers, return the sum of all integers in the list weighted by their depth.

Each element is either an integer, or a list -- whose elements may also be integers or other lists.

Different from the question where weight is increasing from root to leaf, now the weight is defined from bottom up. i.e., the leaf level integers have weight 1, and the root level integers have the largest weight.

Example 1:

Input: [[1,1],2,[1,1]]
Output: 8
Explanation: Four 1's at depth 1, one 2 at depth 2.
Example 2:

Input: [1,[4,[6]]]
Output: 17
Explanation: One 1 at depth 3, one 4 at depth 2, and one 6 at depth 1; 13 + 42 + 6*1 = 17.