CareerCup

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.

Find kth-largest number from a huge amount of data which cannot fit in the memory.

How you will design and make a website like Hackerrank? How you will measure and limit the running time and memory usage of the program.

Write a function that receives string with decimal number (i.e. all characters are decimal digits) and prints the sum of all possible substring-numbers, example:
sum(“123”) = 123 + 12 + 23 + 1 + 2 + 3 = 167

Given N number of Strings, generate all combination of these String's characters, these Strings must be N long, and must contain only one number of char from each string.

example: "abc", "def", "ghi" --> adg, adh, adi, aeg ... cfg

You are given the length and time of occurrence of packet and Queues which process packets. Total processing time for a packet is equal to the length of packet plus the waiting time in queue. For eg lets say we have only one queue for now, and A packet of length 5 comes at t = 1, and another packet of length 4 comes at t = 3. Total processing time for first packet is 5( no waiting time as queue is empty at t = 1) and at t = 3, 2 units of first packet is processed and 3 units remaining so, for second packet 3 units will be waiting time in queue plus 4 units for its length. Total processing time for 2nd packet is 7 units. If there are multiple queues you can add new packet in any of the other queues. Given the time and length of all incoming packets, we need to find the minimum no. of queues required such that total processing time of each packet is less than 10 units. Maximum possible no. of queues are 5. If you require more than 5 queues print -1.


Test Cases Format: First Line contains the number N, the total no. of packets and N following line contains two numbers ti, li where li is length of packet coming at time = ti units.

Test case1:
2
2 7
5 8

Test Case 2:
3
1 3
2 3
3 5

Test Case 3:
3
1 5
2 4
3 8

Output:

Case1: 2
Case2: 1
Case3: 2

Consider the following time table of incoming packets:

time	packets-length
1	    8
2	    5
3	    2
4	    6

If you put the packet in queue with minimum time then this will lead to 3 queues:

t = 1:
q1: 8

t = 2:
q1: 7
q2: 5

t = 3:
q1: 6
q2: 4, 2

t = 4:
q1: 5
q2: 3, 2
q3: 6

But its output should be 2 queues:
1) 8 in queue 1
2) 5 in queue 2
3) 2 in queue 1
4) 6 in queue 2

You are given an array of strings. For example, ["AB", "BC", "FOO", "ZA", "BAZ"]
- Output strings where you can get from one to the other using any ROT transformation.

ROT_1(AB) = BC
ROT_1(BC) = CD
ROT_25(AB) = ZA
AB,BC you can go from one to the other using ROT_1
Input: list of strings
Output: strings where you can get from one to the other using any ROT transformation.
Example:
Input : ["AB", "BC", "FOO", "ZA", "BAZ"]
Output: [ [ab, bc] , [ab, za] ]
AB,BC because you can go from one to the other using ROT_1
AB,ZA because you can go from one to the other using ROT_25
Do not return FOO, BAZ you can’t get from one to the other.

Given an array of elements print even and odd numbers out of it using 2 threads . even_thread and odd_thread.
int arr[] = {3,1 ,2, 5, 6, 7, 8, 10, 9};

Interleave list of lists in Java
Example:
input = [[1,2,3], [9, 0], [5], [-4,-5,-2,-3,-1]];
output = [1,9,5,-4,2,0,-5,3,-2,-3,-1]

given period and threshold, Assume there is a endless streaming events, each event occurs at timestamp "x". The question want you to write an API that return true if number of the events are over the threshold within the period around timestamp "x"


Ex:
period = 3, threshold =2
getEvent(10) -> false
getEvent(12) -> false
getEvent(13) -> true [10,12,13]
getEvent(20) -> false


part one: event come in order
part two: event come without order

Given vector<int> nums, and pair<int, int> range. Find out how many continuous subsequences within this vector sum up the number within the range.

Input: [1, 2, 3], [3,6]
Output: (4)

because [1,2,3], [1,2], [2,3], [3]

Each have a (x,y) coordinate.
Write an API that group three Googler together for lunch if they are close enough. Otherwise, throw them in un-schedule pool.

Distance formula = sqrt((x1-x2) ^2 + (y1-y2) ^2)
Given an int range;

Range: 2
Input | Output of API Un-schedule pool
0,0 -> [] [[0,0]]
1,0 -> [] [[0,0], [1,0]]
3,0 -> [] [[0,0], [1,0], [3,0]]
1,1-> [[0,0], [1,0], [1,1]] [[3,0]]

Given an vector<int> nums and an int target, you can change any element of the vector to positive or negative. How many uniquely different vector sum up to target?
Input: [1,1,1], target = 2
[-1,1,1]
[1,-1,1]
[1,1,-1]

return (3)

Given a string with alpha-numeric characters and parentheses, return a string with balanced parentheses by removing the fewest characters possible. You cannot add anything to the string.

Given a collection of two dimensional points and a number k, return the k closest points to (0,0) by Euclidean distance.

A group of friends are tracking the miles per gallon for each of their cars. Each time one of them fills up their gas tank, they record the following in a file:
His or her name
The type of car they drove
How many miles driven since they last filled up
How many gallons purchased at this fill up
Date of the fill
Their data is formatted as a comma separate value (csv) file with the following format for each row:(#person,carName,milesDriven,gallonsFilled,fillupDate)
Miles are recorded as floating-point numbers and gallons as integers.
Please create a program that allows members of this group to determine the miles per gallon (MPG) of each of their cars during a specific time range. Note: person may have more than one so a time range query might need to output data for one or more cars. A skeleton class will be provided; your job will be to complete the program.
The principal function for querying MPG is of the form (the exact name, data types, etc., can be learned by inspecting the "solution" class in the skeleton code):
GetRangeMPG(PersonName, StartDate, EndDate)
Returns list of objects containing (CarName, MPG)
MPG is calculated as (total miles traveled during time period)/ (total gallons filled during time period.
The dates you receive in the query should be treated inclusively.

Design a data structure which reads below block of text

*Status update1
**Joe is working on a bug
**Alice is on vacation
*StatusUpdate2
**Alex finished task1

and returns me an Object such that I can navigate the this nested text easily like this:

obj.children[0] - > returns "StatusUpdate"
obj.children[0].children[1] -> "Alice is on vacation"

Given a Tree where each node contains an attribute say color(R,G,B... etc). find subtree with maximum number of attributes.
Input:
G
/ \
B R
/ \ / \
B B R R
/ \ / \
B R R R

Output:

Input:
R
/ \
R R
\ / \
R R R

Partition given string in such manner that i'th substring is sum of (i-1)'th and (i-2)'nd substring. If such partition not possible then return empty arrayList.
eg.
1) given "1111223" then return ["1", "11", "12", "23"]
2) given "1111213" then return ["11", "1", "12", "13"]
3) given "11121114" then return []

Modify the following code:

def GenerateGraph(data):
    d = {}
    g = Graph()
    for word in data:
        for i in range(len(word)):
            bucket = word[:i] + '_' + word[i+1:]
            if bucket in d:
                d[bucket].append(word)
            else:
                d[bucket] = [word]

    for v in d.keys():
        for word1 in d[v]:
            for word2 in d[v]:
                if word1 != word2:
                     g.addEdge(word1,word2)
    return g

The objective is to find all combination of words by changing one letter at a time and adding to the graph if word exists in the dictionary.

We need to rewrite a different logic for the above code.

Given a list of characters, write a function to output a list of length of minimum non overlapping subsequences that can partition the input list.

For example:
Input : [a,b,c]
Output: [1,1,1]
Explanation: There are no repeated characters.

Input : [a,b,c,a]
Output: [4]
Explanation: The 'a' is repeated so one subsequence is between a to last a.


Input : [a,b,c,b,a,e,b,a,d,f,g,d,f,i,f,k,l,m,n,m,l]
Output: [8,7,6]
Explanation: max length from 1st 'a' to last 'a' is 8.
1st 'f' to last is 6 adding d to it = 7
so on

from robot movement tell final position of robot...

testcases:
"ULDLLUDL"
"UP 2xDOWN LEFT 4xRIGHT"