CareerCup

Find max size of contiguous shape below, where X represents a shape and . is empty:

.XXXXXX....
...X..XX..X
...XXXX....
..X.....X..
..XXX..XX..
.....XX....
/*method stub*/
public int GetMaxShape(char[][] array) {
}

i was able to come up with a recursive solution but i'd love tips on a dp solution

There are billions and billions of stars in the universe. Which data structure would you use to answer the query
"Give me the k stars nearest to Earth".

Expectation is to come up with the list of parameters/fields in the data structure as well.

How would you design the "call logs" for a mobile phone ? Be as efficient as possible.

Given a 2D matrix A of size m x n, m > 0, n > 0 such that A[i][j] <= A[i][j + 1] and A[i][j] <= A[i + 1][j].

Write a C/C++/Java function to get the k-th smallest element from this matrix.

Inserting dashes between two odd numbers and star between two even numbers

Print Common Suffix In Strings

Ex: cornfiled , Exfiled --- field

Given an unsorted array. for example [2, 3, 1, 4, 5].
Sort the array, we have new array [1, 2, 3, 4, 5],
if we draw the line between the 2 arrays for the same number, for example:

[3, 2, 1,4,5]
\ | /
\|/
/|\
[1, 2, 3,4,5]
then we have 3 line-cross:

line (1 to 1) cross line (2 to 2)
line (1 to 1) cross line (3 to 3)
line (2 to 2) cross line (3 to 3)
Note: the line between two 4s and the line between two 5s don't cross any other lines;

Implement the algorithm to calculate the how many line crosses for an unsorted array.

You are given an alphanumeric string. Complete the function sortSegments that will segment the string into substrings of consecutive letters or numbers and then sort the substrings.

For example, the string "AZQF013452BAB" will result in "AFQZ012345ABB". The input letters will be uppercase and numbers will be between 0 and 9 inclusive.

You are given an integer array n. Complete the function sortIntegers which takes as an argument, an integer array n of up to 1 million integers such that 1 <= n_i <= 10.
for every element n_i in the array, and returns the sorted array. The sort does not need to occur in-place.
Please do not call a standard sorting function like quicksort, you can do better. A sample input is {3, 1, 4, 1, 5, 9, 2, 6, 5} and the corresponding output is {1, 1, 2, 3, 4, 5, 5, 6, 9}. Constraints: i <= 10^9; 1 <= n_i <= 10

This was a 3 hours coding round in which we had to code 1 problem having 50 test cases. Only those students were selected for the next round who passed all the test cases. Here is the question:
You’ll be given a grid as below:

0 1 0 2 0
0 2 2 2 1
0 2 1 1 1
1 0 1 0 0
0 0 1 2 2
1 1 0 0 1
x x S x x
In the grid above,
1: This cell has a coin.
2: This cell has an enemy.
0: It contains nothing.
The highlighted(yellow) zone is the control zone. S is a spaceship that we need to control so that we can get maximum coins.
Now, S’s initial position will be at the center and we can only move it right or left by one cell or do not move.
At each time, the non-highlighted part of the grid will move down by one unit.
We can also use a bomb but only once. If we use that, all the enemies in the 5×5 region above the control zone will be killed.
If we use a bomb at the very beginning, the grid will look like this:

0 1 0 2 0
0 0 0 0 1
0 0 1 1 1
1 0 1 0 0
0 0 1 0 0
1 1 0 0 1
x x S x x
As soon as, the spaceship encounters an enemy or the entire grid has come down, the game ends.
For example,
At the very first instance, if we want to collect a coin we should move left( coins=1). This is because when the grid comes down by 1 unit we have a coin on the second position and by moving left we can collect that coin. Next, we should move right to collect another coin( coins=2).
After this, remain at the same position( coins=4).
This is the current situation after collecting 4 coins.

0 1 0 2 0 0 1 0 0 0
0 2 2 2 1 -->after using 0 0 0 0 1
x x S x x -->bomb x x S x x
Now, we can use the bomb to get out of this situation. After this, we can collect at most 1 coin. So maximum coins=5.

Tweet Recommendation
Twitter Interview Online Test
On Twitter, millions of tweets are posted on a daily basis. Help Twitter write a simple ranking algorithm to find the best of all tweets. It works as follows: A good tweet receives many “likes” from people on Twitter, either from people you follow, or people you do now follow. A tweet is more relevant to you if people you follow also liked the tweet. If enough people you follow have liked that tweet, we recommend that tweet to you.

Your task is to complete the function
getRecommendedTweets(followGraph_edges, likeGraph_edges, targetUser, minLikeThreshold), which returns a list of tweet IDs in sorted order that should be recommended for a certain user. It takes 4 parameters:

followGroup_edges stores follow relationships as an array of tuple of integers.
For example, followGraph_edges = Array{(A, B), (A, C), (B, C)} represents 3 follow relationships:
A follows B
A follows C
B follows C
likeGraph_edges stores like relationships, also in an array of tuple of integers.
For example, likeGraph_edges = Array{(A, T1), (B, T2), (A, T2)} means:
A liked tweet T1
B liked tweet T2
A liked tweet T2
targetUser is the user ID for which we generate recommended tweets
minLikeThreshold is the minimum number of likes a tweet mush receive from people you follow to be recommended
For example, if minLikeThreshold = 4, only tweets that received at least 4 likes from people you follow should be recommended
Note: If you cannot find a single tweet that meets our requirement, simply return an empty list. You may also use any functions provided by the standard library.

Employees Per Department
Twitter Interview Online Test SQL

A company uses 2 data tables, Employee and Department, to store data about its employees and departments.

Table Name: Employee
Attributes:
ID Integer,
NAME String,
SALARY Integer,
DEPT_ID Integer

Table Name: Department
Attributes:
DEPT_ID Integer,
Name String,
LOCATION String

View sample tables:
https://s3-us-west-2.amazonaws.com/aonecode/techblog/50cfcdd1d61f1bd6002cf4d3b4a61deb-min.jpeg

Write a query to print the respective Department Name and number of employees for all departments in the Department table (even unstaffed ones).

Sort your result in descending order of employees per department; if two or more departments have the same number of employees, then sort those departments alphabetically by Department Name.

The numbers on a telephone keypad are arranged thus:

1 2 3
4 5 6
7 8 9
  0

Starting from any digit, and choosing successive digits as a knight moves in chess, determine how many different paths can be formed of length n. There is no need to make a list of the paths, only to count them.

A knight moves two steps either horizontally or vertically followed by one step in the perpendicular direction; thus, from the digit 1 on the keypad a knight can move to digits 6 or 8, and from the digit 4 on the keypad a knight can move to digits 3, 9 or 0. A path may visit the same digit more than once.

Your task is to write a function that determines the number of paths of length n that a knight can trace on a keyboard starting from any digit .
public int findNumberOfPaths(int digit, int step){

Hacking Time
Twitter Interview Online Test

Alice and Bob are avid Twitter users and tweet to each other every day. One day, Alice decides to send Bob a secret message by encrypting it and tweeting it publicly to Bob. They had anticipated a scenario like this, and exchanged a shared secret key some time in the past. Unfortunately, Alice isn’t very familiar with encryption algorithms, so she decides to make her own. Her encryption algorithm works as follows:
1. Choose a key entirely composed of digits 0 - 9, for example: 12345.
2. Iterate each letter of the plaintext message and rotate the letter forward a number of times equal to the corresponding digit in the key. If the rotation of the letter passes Z, start back at A.
3. If the message is longer than the key, loop back to the first digit of the key again, as many times as needed.
4. If a non-alphabetical character is encountered, leave it as it is and don’t move to the next digit in the key.
5. Characters should maintain their upper or lowercase orientation after rotation.

Here is an example message and its encrypted output using Alice’s algorithm:
Original message: Hi, this is an example
Example Key: 4071321
Encrypted message: Li, ailu jw facntll

Where H was rotated forward 4 letters to L, i rotated 0 to i, t rotated forward 7 letters to a, etc.

Satisfied with the security of her algorithm, Alice tweets the following ciphertext to Bob:
Otjfvknou kskgnl, K mbxg iurtsvcnb ksgq hoz atv. Vje xcxtyqrl vt ujg smewfv vrmcxvtg rwqr ju vhm ytsf elwepuqyez. -Atvt hrqgse, Cnikg

Uh oh! Unfortunately for Alice and Bob, you are “Eve”, the world’s greatest hacker. You’ve been intercepting Alice’s messages for some time now, and know she always ends her messages with the signature “-Your friend, Alice”. You job is now as follows:

Determine the key Alice is using.
Using this key, write a function to decrypt any future communications from Alice. This method should take the encrypted string as an input and return the original unencrypted string.

## This is the text editor interface.
## Anything you type or change here will be seen by the other person in real time.
# Implement the function that takes a board string
# and decodes it into the representative 2D array.
#
# |_|_|_|_|_|_|_|
# |_|_|r|_|_|_|_|
# |b|r|b|r|b|r|_|
# |b|b|b|r|r|b|_|
# |b|r|r|b|b|r|_|
# |r|b|b|r|r|r|b|
# CFN: 9_r4_brbrbr_3b2rb_b2r2br_r2b3rb
#
# This function should return a list of lists of strings.
# (i.e. a string[6][7]). The strings should be one of:
# * 'r' to indicate a red piece
# * 'b' to indicate a black piece
# * '_' to indicate an empty space
#
# The input string is not necessarily a valid
# CFN board string. It is guaranteed not-empty.

III. Square root of a number?

IV. Expression operators? Add signs (+, -, *, /) to a string to form target

V. Top trending posts in last 5m, 1H, 1Day?

I. Closest K nodes to a target in BST? (Do it in O(n)?)

II. Nested List sum?

Generate a random binary tree, with equal probability.

Median of Stream of Running Integers
Note: The integers are in particular range from 1..n
The time complexity of the code should be o(n)

If you are given 2 infinitely large integers in the form of strings, given the length of the string, find the product of the two integers.

How will you multiply two infinitely large integers.

Solve the 24 Game

Problem:
Given 100 stones, two players alternate to take stones out. One can take any number from 1 to 15; however, one cannot take any number that was already taken. If in the end of the game, there is k stones left, but 1 - k have all been previously taken, one can take k stones. The one who takes the last stone wins. How can the first player always win?

My Idea
Use recursion (or dynamic programming). Base case 1, where player 1 has a winning strategy.
Reducing: for n stones left, if palyer 1 takes m1 stones, he has to ensure that for all options player 2 has (m2), he has a winning strategy. Thus the problem is reduced to (n - m1 - m2).

Follow Up Question:
If one uses DP, the potential number of tables to be filled is large (2^15), since the available options left depend on the history, which has 2^15 possibilities.
How can you optimize?

I don't have a great answer to the follow up question。。。

Round4
Starting from num = 0, add 2^i (where i can be any non-negative integer) to num until num == N. Print all paths of how num turns from 0 to N.
For example if N = 4,
Paths printed are [0,1,2,3,4], [0,1,2,4], [0,1,3,4], [0,2,4], [0,2,3,4], [0,4].
[0,2,4] is made from 0 + 2^1 + 2^1. [0,1,3,4] from 0 + 2^0 + 2^1 + 2^0

Round3
For N light bulbs, implement two methods
I. isOn(int i) - find if the ith bulb is on or off.
II. toggle(int start, int end)

Round1
Find if two people in a family tree are blood-related.

Round2
Given some nodes in a singly linked list, how many groups of consecutively connected nodes there is.
For linked list
0->1->2->3->4->5->6,
given nodes 1, 3, 5, 6
there are 3 groups [1], [3], and [5, 6].

Explain the linear piecewise function.

Explain event driven programming in C with example

Given a sorted array A, find how many subsets of A satisfies MIN(subset) + MAX(subset) < K.

We have N gas stations, and we are given all the distances between each pair of station. So we have nC2 distances provided to us. For example if I have 3 stations namely A, B, C the distances provided will be AB, AC, BC. We have to find the exact position of each gas station provided with these nC2 distances.

eg. we have 5 stations so 5C2 distances are given in random order - 10, 20, 70, 80, 30, 20, 100, 70, 50, 90

Output the exact positions of gas stations A, B, C, D, E
i.e
A - 0
B - 10
C - 30
D - 80
E - 100

refer this image for more clarity

https://drive.google.com/open?id=0BxPkptdH01OBZzEwX29iRGI4cEU