CareerCup

Given a array of integers there is one that is repeated several time. How would you compute the length of the sequence of repeated elements.
Assuming the initial array is sorted can you do better than O(n) both for spatial and temporal cost?

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.

FB on-site two weeks ago last round of coding . (This problem is also in the internal question bank of G.)

There is a robot in a room. The initial location of the robot is unknown. The shape or area of the room is unknown.
You have a remote that could walk the robot into any of the four directions - up, left, down or right.
Here is the move method: boolean move(int direction), direction: 0, 1, 2, 3. If the robot hits the wall, the method returns false.
Otherwise returns true and the robot moves on to the direction given.
Find out the area of the room.


e.g.
X
XXX X
XXXXX 'X' marks the floor plan of the room.

A room like such has an area of 10.

Last Monday phone interview of G.

Given a vector/list of doubly linked list pointers (a pointer is the directed linkage of two nodes), count how many independent blocks of linked lists there are for the pointers given.

Edward is organizing a meeting and has to order lunch for everyone in the team. To make his task simpler he has prepared two lists. The first list has pairs of team members and their preferred cuisine types. Each team member either has a preference for a particular cuisine or does not have any particular preference and likes all cuisines. The second one contains a list of lunch options along with the cuisine type to which it belongs. Each lunch option belongs to only one cuisine type.

Write an algorithm that outputs a list of all possible pairs of team members along with lunch option they would enjoy. There can be no, one or more entries for a team member in the output list depending on how many lunch options satisfy their choice of cuisine(s).

Input
The input to the function/method consists of four arguments – lunchMenuPairs, representing a list containing pairs of lunch option and its associated cuisine type; teamCuisinePreference, representing a list containing pairs of team members and their cuisine preferences.

Output
Return a list representing all possible pairs of team members and lunch options they would enjoy.

Note
If a team member does not have a particular preference and likes all cuisines, then the preference is specified as a "*" in the teamCuisinePreference list.
Order of rows in the returned list does not matter.

Example
Input:
lunchMenuPairs:
[[Pizza, Italian],
[Curry, Indian],
[Masala, Indian]]

teamCuisinePreference:
[[Jose, Italian],
[John, Indian],
[Sarah, Thai],
[Mary, *]]

Output:
[[John, Curry],
[John,Masala],
[Jose, Pizza],
[Mary, Curry],
[Mary, Masala],
[Mary, Pizza]]

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.

If you find your web-services are slow, So where you start debugging and what could be the reasons for performance slow down.

Find the first non repeating character in a string. For example if the input string "abcdeabc", non repeating character is "e"

Find if a mathematical string is balanced in terms of parenthesis. For example "(1+2)" is balanced and "(1+2" is not balanced.

hi, anyone please help in deleting my post.?
By mistakenly i added the post. I want to delete that. I am not seeing any option to delete.

With times stored in the format "HH:MM:SS", find the number of "interesting" times that can be displayed between two given times S and T (inclusive).

An "interesting" time is one that can be displayed with at most 2 characters.

For example S "15:15:00" and T "15:15:12" would return the count of 1 as the only "interesting" time between S and T (inclusive) is "15:15:11".

Another example, S "22:22:21" and T "22:22:23" would return the count of 3 because of the following times: "22:22:21", "22:22:22", "22:22:23"

Constraints:

S <= T
00 <= HH <= 23
00 <= MM <= 59
00 <= SS <= 59

/* The objective of this exercise is to build a road network connecting every pair of cities.
Each city should be connected to each other city once.
*/
public class Program
{
/* Your function RoadBuilder should return a list of new roads required to be built,
if the existing roads are given by builtRoads and the total number of
cities is nCities. Roads should not connect cities to themselves.
*/
public static int[][] RoadBuilder(int nCities, int[, ] builtRoads)
{
//implement the function here
return new int[0][];
}

public static void Main()
{
int[, ] test1 = new int[3, 2]{{0, 1}, {1, 2}, {3, 2}};
Console.WriteLine(RoadBuilder(4, test1)); // expected result should be {{0,2}, {0, 3}, {1, 3}}
}
}

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) {
}

Implement power function. The function should take two numbers as input (e.g. 2,3) and return 8 as output

See link below for hints and answer https://baquerrizvinotes.blogspot.in/2017/05/how-to-crack-amazoncom-technical.html

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

/* The objective of this exercise is to build a road network connecting every pair of cities.
Each city should be connected to each other city once.
*/
public class Program
{
/* Your function RoadBuilder should return a list of new roads required to be built,
if the existing roads are given by builtRoads and the total number of
cities is nCities. Roads should not connect cities to themselves.
*/
public static int[][] RoadBuilder(int nCities, int[, ] builtRoads)
{
//implement the function here
return new int[0][];
}

public static void Main()
{
int[, ] test1 = new int[3, 2]{{0, 1}, {1, 2}, {3, 2}};
Console.WriteLine(RoadBuilder(4, test1)); // expected result should be {{0,2}, {0, 3}, {1, 3}}
}
}

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

There is 3D space, limited with a cube, with edge=2000.

The center of coordinate system is point (0; 0; 0), so the maximum/minimal coordinate value is 1000/-1000.

There are 10000 points generated with discrete uniform distribution inside of K spheres, located in the cube.

Radius (R) of each sphere is 250.

Centers of spheres are located at the distance of not less than 2*R.

It is required to determine which point related to which sphere.

Input: array of 10000 structures, like:

struct Point {

int number;
int x;
int y;
int z;

}
where number is unique id of the point, x,y,z - it's coordinates.

Output:

array of 10000 structures, like:

struct Point {

int number;
int cluster_id;

}
where cluster_id is unique cluster id of a sphere that point belongs to.

Initially I considered a following solution:

1) Find Euclidian distance for each point from center of coordinates (0;0;0) to point's coordinates.

2) Sort this array of distances in descending order.

3) Get the point from the sorted array of distances and put in a new Set of Cluster Maximals.

4) Compare following point from the array to each value from the Set of Cluster Maximals (initially 1 value).

If it's Euclidian distance less than or equal to 2*R, then

mark this point as belonging to Kth cluster (range=1..N), otherwise add the point to the Set of Cluster Maximals.

5) Repeat step 4.

Two concerns I have:

1) There is an issue that my algorithm would work only in case if Claster Maximals are located on the surface of the spheres.

2) Plus, according to the task requirements, there could be the case when 2 spheres can have 1 and only common point.

I think in case if point belongs to 2 spheres, it is ok to mark it with cluster_id of any of these 2 shperes.

Could you please provide a proper solution to the task?

Products are identified by alphanumeric codes. Each code is stored as a string. We have three types of products:high priority, medium priority, and low priority. Given an array of product codes, sort the array so that the highest priority products come at the beginning of the array, the medium priority products come in the middle, and the low priority customers come at the end. Within a priority group, order does not matter. You are given a priority function which, given a product code, returns 1 for high, 2 for medium and 3 for low. This array may contain a large number of product codes, so do your best to minimize additional storage.

Products are identified by alphanumeric codes. Each code is stored as a string. We have three types of products:high priority, medium priority, and low priority. Given an array of product codes, sort the array so that the highest priority products come at the beginning of the array, the medium priority products come in the middle, and the low priority customers come at the end. Within a priority group, order does not matter. You are given a priority function which, given a product code, returns 1 for high, 2 for medium and 3 for low. This array may contain a large number of product codes, so do your best to minimize additional storage.

You get a password and a mapping for each character of the password. Print out all the possible mutations for the password.

E.g. password: "pass"
mapping:
p-> $
p-> P
a-> A
s-> /
s-> S
s-> &

Possible mutations would be for example "PASS" or "$A&S"