CareerCup

Given the following input:

Array: array of integer coordinates(x,y) of length N

return a integer M that represents the maximum number of points that falls within the same line.

Example:

Array: [ [0,0], [1,1], [3, 12] ]
Output: 2# [0,0] and [1,1] falls in the same line. [3,12] falls on a different line. Thus the maximum number of points that falls on the same line is 2

Given the following inputs:

Array: Array of positive non repetitive integers of length N.
K: Integers in range of [2,N)
Target: A Target integer

return any subset of Array with K elements that sums up to target.

Example:

Array: [1,2,3,4,5]
K: 2
T: 6
Output: [1,5]

Array: [1,2,3,4,5]
K: 3
T: 6
Output: [1,2,3]

Array: [1,2,3,4,5]
K: 4,
T: 11
Output: [1,2,3,5]

Implement multithreaded rm -r <folder>, i.e recursively delete files/folder under <folder> by walking through it and assume there can be billions of files under folder and you can only delete folder if all contents in it are first deleted

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)

Design a space shooter program .
Note: The game includes spaceship , bullets and asteroids. Spaceship rotates in 180 degree generating bullets. The position of the bullets gets updated after certain time period every time . No Need to write the code for collision detection
Basic code in expected . Not the entire working code.

Given a matrix. Convert it into a linked list matrix such that each node is connected to its next right and down node.

Ex:
1 2 3
4 5 6
7 8 9

Output:
1->2->3->NULL
| | |
v v v
4->5->6->NULL
| | |
v v v
7->8->9->NULL
| | |
v v v
--NULL-

This is my code.

class Ideone
{
	public static void main(String args[]) throws Exception {
		int arr[][] = { { 1, 2, 3 }, 
				        { 4, 5, 6 } };
		LList op = convert2DArrintoList(arr, 0, 0);
		System.out.println(op);
	}
 
	public static LList convert2DArrintoList(int arr[][], int col, int row) {
		if (col >= arr[0].length || row >= arr.length)
			return null;
		return new LList(arr[row][col], convert2DArrintoList(arr, col, row + 1), convert2DArrintoList(arr, col + 1, row));
	}
 
	static class LList {
		LList(int data) {
			this.data = data;
		}
 
		LList(int data, LList down, LList next) {
			this.data = data;
			this.down = down;
			this.next = next;
		}
 
		LList() {
			this.data = Integer.MAX_VALUE;
		}
 
		@Override
		public String toString() {
			return " " + this.data + " ";
		}
 
		int data;
		LList next;
		LList prev;
		LList rand;
		LList down;
	}
}

Are there better ways of doing it?

Given a binary tree, write a recursive method boolean method(int x, int y) which will return true
1. if node y (meaning a node with a value of int y) is a node that is contained in one of the two possible subtrees of x,
2. true if x==y, and a node with a value x==y exists, otherwise
3. return false,
basicallly whether x contains y? I had a question like this on my exam, I solved this problem using four arguments in my function. I wonder whether it is even possible to solve it with only 2 int arguments and recursively.

Generate all possible matched parenthesis, given n left parenthesis and right parenthesis needs to be matched.

Create a data structure that stores integers, let then add, delete. It also should be be able to return the minimum diff value of the current integers.
That is,
min_diff = minimum ( | x_i - x_j | )
Example:

-1,3,4,10,11,11
min_diff = 0

-1,3,4,10,11,14
min_diff = 1

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.

write a program to find the nearest smaller number array for the given array.nearest smaller number is the number which is smaller than the given number and nearest to the given numbers position .if no such number is found print -1

// Create a numeric binary tree structure/classes that have left and right children and an integer numeric value.
// Write a function 'isBalanced' for a node that returns true if the sum of all the children on the left is equal
// to the sum of all the children on the right.

//Example:
// [12] [12].isBalanced() -> True. [3, 3]
// / \
// [3] [1] [1].isBalanced() -> True. [2, 2]
// / \
// [2] [0]
// / \
// [2] [0]
// - Part I: setup and isBalanced() function
// - Part II: implement “allBalancedNodes()” <— given a node, finds all balanced children
// allBalancedNodes(12) -> returns a list of balanced nodes: { [1], ... }

Given a fully connected graph with n nodes and corresponding values. One node can interact with other node at a time, to replace/ignore/add its value to other node’s value. Assuming this operation takes 1 unit of time, how much time would it take for all the nodes to have value equal to sum of all the nodes.

Examples : Given a graph with values {1,2,3,4}, find total time it takes, such that all nodes have value as 10.

I am assuming it can be done in O(N).It will take basically two traversals, one for calculating the sum of values of nodes(first traversal), other for replacing the value of the nodes(second traversal).

It will take 2*(no of nodes) time.

Are there any better ways possible ?

Solve the 24 Game

Given a list/array of "Assign" trees with integers, operators and variables, return the result of the requested "Result" tree expression.

Example:

"Assign"
  /  \
"x"  "+"
    /   \ 
   2     3

"Assign"
  /  \
"y"  "-"
    /   \ 
  5000  30

"Assign"
  /  \
"z"  "*"
    /   \ 
  50     x

"Return"
  \
  "-"
  /  \    
 z   "*"
     / \
    1   y

You are given logs that contain user and page visits for a given day.
u1 -> p4
u3 -> p2
u7 -> p9
...
comeup with efficient data structure that answers these queries

Which page was visited by exactly 100 users in day?
Which page was visited by only one user exactly 15 times in a day?
Which page was visited by u3 more than 20 times in a day?

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。。。

Implement a function that returns whether a string made of different bracket characters is well formed or not.

For example,
"{({})[]}" is a well formed bracket string
"{[](}" is not a well formed bracket string

Needless to say any single brackets are automatically counted as not well formed

Design and implement a multi-threaded application that finds the occurrence(s) of a string in a text file of 100GB. It should return the line-number(s) in which the match(es) is/are found.

Need not worry about the system constraints in spawning and running threads. There is a 32 core CPU with immense power. Huge amount of RAM.

The result should be returned in few sec.

You are in charge of a classroom which has n seats in a single row, numbered 0 through n-1.
During the day students enter and leave the classroom for the exam.
In order to minimize the cheating, your task is to efficiently seat all incoming students.

You're given 2 types of queries: add_student(student_id) -> seat index, and remove_student(student_id) -> void.

The rules for seating the student is the following:
1) The seat must be unoccupied
2) The closest student must be as far away as possible
3) Ties can be resolved by choosing the lowest-numbered seat.

Your organization is opening a new warehouse and your manager has tasked you with figuring out how to quickly get some of the inventory in the original warehouse to the new warehouse. You are given a list of the locations of all N packing crates in the facility, any of which is a candidate to be moved to the new facility. All crates are the same size, and the truck has capacity to move exactly M of them. The delivery driver needs to leave promptly, so it is your job to find the crates that are closest to the truck. Crates are heavy, so you can only carry one at a time.

Given an array of the locations of N packing crates, implement an algorithm to find the locations of the M crates closest to the truck.

Input
The input to the function/method consists of three arguments:
totalCrates, an integer representing the total number of packing crates in the facility (N)allLocations, a list where each element consists of a pair of integers representing the x and y coordinates of the packing crates;
truckCapacity, an integer representing the number of packing crates that will be moved to the new facility (M).
Output
Return a list of integers where each element of the list represents the x and y coordinates of the packing crates that will be moved to the new facility.
Constraints
truckCapacity
totalCrates
Note You begin at the truck’s location [0, 0].The distance of the truck from a warehouse location (x, y) is the square root of x^2 + y^2.If there are ties then return any of the locations as long as you satisfy returning M points.
Example Input:totalCrates = 3allLocations = [[1, 2], [3, 4], [1, -1]]
truckCapacity= 2 Output:[[1, -1], [1, 2]]
Explanation:The distance of the truck from point [1, 2] is square root(5) = 2.236 The distance of the truck from point [3, 4] is square root(25) = 5 The distance of the truck from point [1, -1] is square root(2) = 1.414 num is 2, hence the output is [1, -1] and [1, 2].

Design amazon's frequently viewed product page.

Design a ESPN like system. Ensure scaling and availability. Also one should get all details like score of a player, no. of mtches etc.

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

You and your friend go to a game arcade where you choose to play the lucky pick game. In the game,
there is a square grid and on each block some money is placed on it. When a player chooses a block, the
machine randomly chooses a block from the available neighboring and the chosen block (consider 8
neighborhood). The player is awarded the money that is placed on the block that the machine selects.
Your friend needs help choosing the block.
Your job is to return the block position(s) that will maximize the minimum amount your friend will win
for sure. If there are more than one such block positions, then output must return all these positions.
Input Format
You will be given a single input representing the Grid Description (in the form of string array)
(N rows each containing N numbers separated by '#', each number representing the amount of money
put on that block)
Output Format
You need to return the array of string containing the position(s) of a block choosing which will give the
maximum amount of money which your friend will definitely win.
Sample Test Case 1
Sample Input
3 12#45#33 94#54#23 98#59#27
Sample Output
3#1
Explanation: In the above example, if he selects the block (3,1), then under the best case, he could win is
98 and under the worst case the maximum he could win is 54. In such scenario, the worst case of block
(3,1) gives your friend more money than the worst case of other blocks.
Sample Test Case 2
Sample Input 4
12#45#33#27
94#54#23#53
98#59#27#62
11#51#67#13
Sample Output
1#3
1#4
2#3
2#4
Explanation
Note: If the output array contains multiple strings(block's positions), all the positions must be in the
row-wise traversal order. In Example 2, the output is {1 #3,1#4,2#3,2#4}. If your function is returning an
array that has same elements (block's position) but in the different order, then the output array will be
incorrect.
Function to implement:
public static String[] amount_value(String[] input1){
//implement your logic
}