CareerCup

How to divide a circular array into k group of contiguous element such that difference between maximum sum and minimum sum is minimum. Each group have contiguous element of array. For e.g If the array is as follow. [6 13 10 2] and k=2 then o/p should be 18(6+10+2)-13=5. As array is circular 6,10,2 are contiguous element of array.

For e.g If the array is as follow. [6 13 2 10] and k=2 then o/p should be 16(6+10)-15(13+2)=1. As array is circular 6,10 are contiguous element of array.

For e.g If the array is as follow. [100 92 133 201 34 34 34 94 108] and k=4 then group as follow 208(108,100), 225(92,133), (201), 196(34,34,34,94) so 225-196=29

l1=[1,2,3,4]
l2=[1,3,6,7,null,null,null,null]
output: l2=[1,1,2,3,3,4,6,7]

k=2, l=[1,2,3,4,5,6]
output: l=[5,6,1,2,3,4]
In place O(1) space complexity

You have two sorted arrays, where each element is an interval. Now, merge the two array, overlapping intervals can be merged as a single one.

I/P :
List 1 [1,2] , [3,9]
List 2 [4,5], [8, 10], [11,12]

O/P [1,2], [3,10], [11,12]

I/P [8, 3, 2, [5, 6, [9]], 6]

O/P 8+3+2+2*(5+6+3*(9))+6 => 95

You are given an array A of size N and Q queries. For each query, you are given two indices of the array L and R. The subarray generated from L to R is reversed. Your task is to determine the maximum sum of the subarrays.

Note: After each query is solved, the array comes to its initial states.

Input format

First line: Two space-separated integers N and Q
Next line: N space-separated integers denoting the array elements.
Next
Q lines: Two space-separated integers in every line denoting the values of Li and Ri
Output format

For each query, print the required answer in a new line.



5 2
3 -1 4 2 -1
3 4
1 2

//output
8
9

Given the root of a binary tree, print the nodes column wise and row wise.

..............6
............/....\
...........9......4
........../..\......\
.........5....1.....3
..........\........./
...........0.......7

The answer would be 5 9 0 6 1 4 7 3.

Explain the difference between ORM and JDBC.
Provide some examples and when to use one over the other.

given two strings s1 and s2 we have to convert s1 into palindrome such that s1 contain s2 as a substring. in a minimum number of operation. wherein a single operation we can replace any word of s1 with any character.
constraint : |s1| <= 1000
|s2| <= |s1|
ex: s1 = "abaa" , s2 = "bb"
output : 1

Given an array which represents columns, find the position of two columns which when removed will trap the maximum amount of water. This is related to trapping raining water problem.

Given an unsorted array find the maximum distance between two elements satisfying the condition A[i] < A[j] where i < j. There will always be a solution.

For eg. 6, 9, 3, 2, 10, 2, 3

Database query response times have increased. An API which is dependent on this database will see - *

This is a multi-select answer.

Increase in the latencies.
Increase in RAM utilisation on the API servers
Increase in CPU utilisation on the API servers
Increase in 200 response codes
Increase in 5xx responses

If a sorted array is rotated by k positions, what is the time complexity to find the starting point of the original array?
1 point
O(logn)
O(1)
O(n)
O(nlogn)

Setting a value in cache is failing. What are the acceptable production practices? *

1. Raise an exception immediately
2. Retry in equal intervals of time until the set call succeeds
3. Retry with exponential back off until the set call succeeds
4. Retry 2 or 3 times with exponential back off.
5. Retry 2 or 3 times with equal intervals of time.

This is a multi-select question.

We have a database that allows 2 concurrent writes and 3 concurrent reads. Each read/write operation takes 10ms to complete. What is the time taken to process all the requests in the orders mentioned (all requests can be assumed to be coming in at the same instant of time and are operating on a single row in a table) - 1. write, write, read, write, read, read, write, read 2. read, write, read, write, read: *


1. 30 ms 2. 10ms
1. 60 ms 2. 10ms
1. 10 ms 2. 10ms
1. 20 ms 2. 10ms
1. 10ms 2. 20ms
1. 60ms 2. 30ms

Given an array, coin of size n, coin[i] denotes the no. of coins on the position i. Can move any number of coins from the position i to (i+1) or (i-1). What is the minimum no. of moves required to redistribute the coins, so that each position i has at least 1 coin ?
Note: Summation of total coins on the array is exactly n.

Morse code is a method of transmitting text information as series of long and short sounds or visual signals. Pauses are used during transmission to group letters and words. The common convention for writing morse code is to use dots (.) and dashes (-) for the short and long signals however without including pauses (e.g. as spaces) morse code quickly becomes ambiguous. For example the code -....--.... has 13 valid translations (bans, bates, bath, begs, digs, etc)
Write a function getAllEnglishTranslations which takes a morse code without any pauses and returns all valid translations.
std::vector<std::string> getAllEnglishTranslations(std::string morseCode)

Output must be sorted in ascending alphabetical order.
Assume there are only 7 alphabets and below are their mappings
M = dash-dash (--)
C = dash-dot-dash-dot (-.-.)
O = dash-dash-dash (---)
D = dash-dot-dot (-..)
I = dot-dot (..)
N = dash-dot (-.)
G = dash-dash-dot (--.)
Assume input code is a valid morse code

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?

Lets there are n stores.

A customer order x items. All the stores might not have all the items from the order list. So find the store/combination of stores that can serve the order request such that the set that contain least number of stores is selected so that there are lesser number of shipments.

print hockey stick number in pascal triangle where row of triangle can be upto 30000 and length of stick can be upto 100.

For a given amount of currency, find the minimum set of bills. The currency set is the following: 0.01, 0.05, 0.1, 0.25, 1, 5, 10, 20, 50, and 100. For example, for 21.28, 1 20 bill, and 1 1 bill, and 1 0.25 bill and 3 0.01 bills.

Find top 10 most frequent words in the past hour, day and month from twitter service. Given a streaming data such as tweets from twitter service, the objective is to find the top 10 frequent words in the past hour, day and past month at any instant of time.

Write a function that takes a magic number and a list of numbers. It returns true if it can insert add or subtract operations in the list of numbers to get the magic number. Otherwise, it returns false.

For example:

f(10, [1,2]) = false. There's no way to add or subtract 1 and 2 to get 10.
f(2, [1,2,3,4]) = true. 1 + 2 + 3 - 4 = 2.
f(0, []) = true
f(1, []) = false
f(1, [1]) = true
f(0, [1]) = false

I don't remember perfectly the question, but it was like this


Given a list of 100 songs on your cell phone, find a way for each user to hear the songs without repeating songs, you need to use an algorithm that uses shuffle for songs.

Implement a rate-limiter-like iterator and how to improve the space complexity

Given a <Word, TimeStamp> pair data type iterator as input. Implement an iterator based on it which can ignore the item if the same word has occurred in the past 10 seconds.

My implementation is to use a HashMap to memorize the word and its latest timestamp + 10s. For each new item, it will be checked against the HashMap to see if it has duplicated word occurred in the past 10s.

The interviewer asked me how to improve the space complexity if the string value varieties are infinite. He mentioned some boundary stuff.

Could anyone share some thoughts?

I was asked to design a system on a whiteboard which simulate a executor.
This system has a method that is being triggered every second. I need to add logic to the method (i.e. run jobs).
There is also a method called job_arrived() that is called when a new job arrives.. I need to implement it as well.
I needed to implement a system which tries to run each job right when it is arrived (it has a return value that gets a success status from a black box service). if the job ran successfully that's the end of it..
if not I need to re-run it after 2 seconds (and if that fails as well - there will be no re-runs).
of course - more than one job can be accepted each second.
I was asked to describes the system (describe the classes and method) and consider the system to be large scale one (meaning.. threading is in order here..).
The answer I gave was apparently not multi threaded enough..
any idea to what I should have done?
Thanks guys

Give m balls and n bins. Find out how many ways to assign balls to bins. Notice the buckets has no order. Like (1,2,3) and (3,2,1) are considered the same.
eg, m = 3, n = 2, return 2. (1, 2) and (3, 0)

Two Sum. Then follow up three sum

Consider a game similar to tennis. The game can be palyed by 'N' number of players. The player has to win atleast 'M' games to win a set.
Print all the possible combination of winning set for all the payers.
Where
2 <= N
1 <= M

For Example if [A, B] are the players and

if M = 2 The player has to win atleast '2' games to win a set.

The output will be

A A
A B A
B A A
B B
B A B
A B B

if M = 3 The player has to win atleast '3' games to win a set.

The output will be

A A A
A B A A
A A B A
B A A A
B B B
B A B B
B B A B
A B B B

Write an algorithm to print all the possible combination of winning set for all the payers

Find Duplicate number from a huge amount of data which cannot fit in the memory.