CareerCup

Now we have one server, one database, what if response time is slow?
How to optimize?

Given an integer n, count the total number of digit 3 appearing in all non-negative integers less than or equal to n.
(E.x: given 30, return 4 {3,13, 23, 30})

prime factors. given a number return the prime factor multiplication.
eg. 90 = 2 * 3 * 3 * 5.

Remove any number containing 9 like 9, 19, 29, ... 91, 92, ... 99, 109...
Write a function that returns the nth number. E.g. newNumber(1) = 1
newNumber(8) = 8, newNumber(9) = 10

Given a n*m size 2D array with integers from 1 to n*m - 1 in it.
Integers are not sorted. The last position of the matrix stays a movable block.
For each time, you can swap the movable block with any adjacent number.
And eventually you will have the integers sorted and the movable block returned
to its starting position. Think about an approach to print the path.
(You can assume it always have at least a solution)

How to get the repeating decimal pattern of a division? (e.g 1/3, 1/6)

Given a preorder traversal of a BST, print out the inorder transversal of the BST
public void printInorder(int[] nums){}

Implement circular buffer with read & write functions

Coding III
Implement int divide(int a, int b) without division or mod operation.



## Round IV
Behavioral Questions + Project Walk Through + Coding (Validate BST)

## System Design V
Design memcache to enable read, write and delete (single server, non-distributed infrastructure).
Which data structure to go with?
Eviction rules?
How to minimize segmentation?
How to handle concurrency?

## Extra
After two weeks they called me to an extra round of system design.
How to store social graphs?
How to handle concurrent read/write requests(read heavy) on one server.

Find Famous person in the list of persons.

A person is a famous person if he doesn't know anyone in the list and everyone else in the list should know this person.

The function isKnow(i,j) => true/ false is given to us. No need to worry about it.

Goal is to find the famous person in O(n) complexity.

/* Find all subsets of size k in an array that sum up to target
the array may contains negative number */
class Solution {

public List<List<Integer>> combinationSum(int[] nums, int target, int k) {

}

A bot is an id that visit the site m times in the last n seconds,
given a list of logs with id and time sorted by time, return all the bots's id

class Log{
	String id;
	int time;
}
public HashSet<String> getBots(Log[] logs, int m, int n){
	
}

download all urls from 1000 hosts. Imagine all the urls are graph.
Requirement: Each host has bad internet connection among each other, Has to download url exacly once.

Give you a robot and a room where you do not know where the robot is in the room and you do not know the size of the room, you have a remote control that allows the robot to walk around four directions. Here you give a move method: boolean move (int direction), direction: 0,1,2,3 that four directions. If it can move in that direction, return true, and if it cannot move in that direction, return false. Ask you determine how big this room is. the shape of the room can be any shape, so you cannot assume it is rectangle or square.

Given a 2D character array of size NxN. Find if there is a path from the cell 'R' to the cell 'T'. You can go left, right, up, down from a cell and you cannot pass through any cell marked with 'X'.

Example input:
X__R_X
X_XXX_
______
_XX_XX
XT__X_

Output: true

Print all permutations of a given string.

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].
You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You can begin the journey with an empty tank at one of the gas stations.
Return ALL the starting gas station's index where you can travel around the circuit once
public List<Integer> canCompleteCircuit(int[] gas, int[] cost) {
}

You have a array with integers:

[ 1, -2, 0, 6, 2, -4, 6, 6 ]

You need to write a function which will evenly return indexes of a max value in the array.
In the example below max value is 6, and its positions are 3, 6 and 7. So each run function should return random index from the set.

Try to implement with O(n) for computation and memory.
Try to reduce memory complexity to O(1).

You have a binary tree which consists of 0 or 1 in the way, that each node value is a LOGICAL AND between its children:

0
   /   \
  0     1
 / \   / \
0   1  1  1

You need to write a code, which will invert given LEAF and put tree in a correct state.

Given n1, n2 is the number after removing one digit from n1. Example, n1 = 123, then n2 can be 12, 13 or 23.

If we know the sum of n1 + n2, and find the possible values of n1 and n2.

public List<List<Integer>> getNumber(int sum){
}

Design copy-on-write string class
e.g. stringclass s("abc");
stringclass s1 = s; // no copy
s = "bcd"; // copy

Design and implement an algorithm to assign an unlimited M number of messages evenly among N number of servers (N will not change).
Input to the algorithm
A message contains a message identifier and a text string. The algorithm will be fed one message at a time.
There are N numbers of servers (N will not change), each can be identified by a unique id.
Output of the algorithm
When the algorithm is called to process a message, it should output the id of the server that the message is assigned to.

Given an ODD number, print diamond pattern of stars recursively.

n = 5, Diamond shape is as follows:
  *
 ***
*****
 ***
  *

void print(int n){
}

/From the input array, output a subset array with numbers part of a Fibonacci series.
// input: [4,2,8,5,20,1,40,13,23]
// output: [2,5,1,8,13]
public static List<Integer> getFibNumbers(int[] nums){}

The number of valid combinations of a strings for given input array a[], where a=>1, z => 26, and 0 <= a[i] <= 9

{1,1,1} => {aaa, ak, ka} => 3
{1,1,0} => {aj} => 1

Can multiple threads improve the time complexity to merge k sorted arrays? If so, how?

Gives an array of unsorted int (may have negative number),
rearrange the array such that the
num at the odd index is greater than the num at the even index.
example
giving 5, 2, 3, 4, 1, one of the expected result is 1,4,2,5,3,
please solve it in o(n) time, where n is the length of the array
public void rearrange(int[] nums){

}

Given a string, find all possible combinations of the upper 
and lower case of each Alphabet char, keep the none Alphabet char as it is.
example1 s = "ab", return: "Ab", "ab", "aB", "AB"
example2 s = "a1b", return: "A1b", "a1b", "a1B", "A1B"
public List<String> getPermutation(String s){
	
}

Given a binary tree of integers, write code to store the tree into a list of integers and recreate the original tree from a list of integers.

Here's what your method signatures should look like (in Java):

List<Integer> store(Node root)
Node restore(List<Integer> list)

Example Tree:

5
/ \
3 2
/ / \
1 6 1

For a given array, find the subarray (containing at least k number) which has the largest sum.
Example:
// [-4, -2, 1, -3], k = 2, return -1, and the subarray is [-2, 1]
// [1, 1, 1, 1, 1, 1], k = 3, return 6, and the subarray is [1, 1, 1, 1, 1, 1]
try to do it in O(n) time
Followup, if input is stream, how to solve it
public int maxSubArray(int[] nums, int k) {}