CareerCup

Two Sum. Then follow up three sum

How is design review done?

Given a BST of memory sizes. Find best fit for a memory block of size M.

Given an infinitely large array and every element has tags associated with them, and there are about 10,000 tags (say) then sort the given array to get all tag-0’s first, tag-1’s next and so on in O(n).

For Amazon SDE-1 On Campus Interview, what are the topics I should study in Database Management ?
Just don't name the topics. Please elaborate too.

For Amazon SDE-1 On Campus Interview, what are the topics I should study in Computer Networking ?
Just don't name the topics. Please elaborate too.

Given a random MxN matrix and a positive integer, recursively Your program should then find a continuous path thought the matrix starting at position 0,0 that will sum to n. Your program shouldomly move left (col -1), right(col +1), up (row -1) and down (row+1)and can only use a position once in the sum. if there is a such path in the matrix, create the path in a separate matrix with the same size, and replacing the indices used with 1 and the rest 0.

Design a music streaming service like Pandora.

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.

Design a class for converting integer to Roman numerals.

Given k, and a binary string, determine if this contains all permutations of length k.
For example, 11001 contains all possible binary sequences with k=2 (00,01,10,11)

Design the Goodreads recommendation model.

Goodreads is a "social networking book" website that allows individuals to freely search its database of books.

- Any given user has a List of friends.
- User can add books to his/her shelve
- When a user logs in, we need to show the top 10 books owned by his friends

Example:
User1 has u2, u3, u4, u5 as friends

u2 owns b1, b2, …b10
u3 own b1, b2, b11…b20
u4 owns b1, b2, b11…b20
u5 owns b1, b33, b35, etc

topmost book is b1, second topmost book is b2 and so on.

If you maintain a cache of top 10 books in the user object for each of the users. How often will you update the cache ?

You have been given a generator string ab from which any number of strings can be generated recursively by inserting ‘ab’ at any location. You have been given an input string to check if that given string is valid or not.(i.e. generated by given with given string.)

eg.
Input: aabbab
Output: valid
Input: abbaab
Output: Invalid

I could not come up with a algorithm less than O(N*N)

Given a multiple tree, and multiple nodes that need to be deleted,
It is required to return a list of nodes so that the children of these nodes can be found after the nodes have been deleted.

Gives you an int m, and a set of char (0,1,2,3,4,5,6,7,8,9)
Lets you implement a function that generates a id based on the characters in the set. Each time you return a string, it must be unique. satisfying the same character can not appear consecutively more than m times, such as m = 3, "1000" is valid,
"0000" is not valid.
The smaller the string, the better.

Let’s say you have two input arrays with sorted elements. Find the union.

a[] = {2, 10, 14, 19, 51, 71}
b[] = {2, 9, 19, 40, 51}

Union = {2, 9, 10, 14, 19, 40, 51}

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.

To push dominoes, find out how many dominoes are standing in the end

For example, the input is ".R...RL..R..L..", which means pushing the 2nd, 6th, and 12th dominoes to the right and pushing the 8th and 15th dominoes to the left. This example returns 4th. 1,7,16,17 blocks are standing

The question is that there are a lot of vm, what is the total vm consumption max. For example, (2,4,8), (3,5,3) this input,
This means that 2 to 4 seconds have a memory usage of 8 and 3 to 5 seconds of 3, so the answer is 11 at 3 seconds.
Return 11 to it. Note that (1,2,3) and (2,3,4) such that the middle 3+4=7 is good.
Follow up is usage is not constant, such as (1,2,1,2) the first second usage is 1,
The second second is 2, the linear increase, the highest is how much.

Given an alphabet where we do not know the order of the letters also do not know the number of letters.

We are give an input list of tuples where each entry in the list gives an ordering between the 2 letters

Determine the alphabet order.

Ex-
<A, B>
<C, D>
<C, E>
<D, E>
<A, C>
<B, C>
Order is A, B, C, D, E

AWS phone interview
Find the left view of binary tree
1
/ \
2 3
/\ \
4 5 6
/ /
7 8
/
9
return [1, 2, 4, 7, 9]

Given as list of movies in a csv file, extract the movie name and genre and be able to return a query based on the years and the genre.

Basically, Parsing a CSV input file and build an indexed data storage to allow search the data in time manner.

Given a list of tasks each with memory requirements and time, only one machine has K memory.
Do not consider the context switch, page swap, virtual memory, (for example, the machine has only 20mb memory, a task that requires 25MB of the task can only wait until there is enough memory to run it.) The running task cannot be suspended.
Ask how long it takes to complete all these tasks. . .

1) You sell roses. Each rose cost 30 cents to buy and you can sell them for $10 a dozen.
a) How many you need to sale to break even if you bought 600 roses?
b) Tomorrow is holiday - there's 20% likelihood you will sale 600 roses, 50% likelihood of selling 900 roses and 30% likelihood of selling 1200 roses. How many would you buy to maximize profit?

Write a method that can take in an unordered list of airport pairs visited during a trip, and return the list in order:

Unordered: ("ITO", "KOA"), ("ANC", "SEA"), ("LGA", "CDG"), ("KOA", "LGA"), ("PDX", "ITO"), ("SEA", "PDX")
Ordered: ("ANC", "SEA"), ("SEA", "PDX"), ("PDX", "ITO"), ("ITO", "KOA"), ("KOA", "LGA"), ("LGA", "CDG")

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/

Find the largest duplicate subtree in a binary tree


For example,

        1
       / \
      2   3
     /   / \
    4   2   4
       /
      4
The following are two duplicate subtrees:

      2
     /
    4
and

    4

but the former is the largest, thus return the root of the first subtree

Given a target string, an input request replaces the word after the given index a->b such as:
Target string: "Hello world!"
Input:{s:0, a:Hello b: Goodbye}
Output:"Goodbye world!".
The requirement is that input be given to several words that need to be changed at one time: {{s:0,a:Hello,b:Goodbye},{s:11,a:!,b:?},{s:6 a: World,b:friend}}
And each modified index is based on the original unmodified target string so the end result is
"Goodbye friend?"

given a n-ary tree, find the total distance from this node to any other nodes

class TreeNode {
int val;
List<TreeNode> children;
TreeNode(int val) {
this.val = val;
children = new ArrayList<>();
}
}


public int findDistance(TreeNode root, TreeNode node) {

}

How many squares are inside a m*n rectangle where some grids in the rectangle were grey and the gray grid could not appear in the small squares.

Given an int array, check if all the numbers can be divided into 5 consecutive numbers.
Eg: [1,2,2,3,3,4,4,5,5,6] Yes: (1,2,3,4,5) (2,3,4,5,6)
Followup: ask if you know that all the numbers are between 1 and 13,
what's a good optimization.