CareerCup

Given an array of edges between any two points in 2 dimensional space. A single edge is represented by the co-ordinates of two points it is connecting for example (2,3),(4,5) represents and edge connecting points (2,3) and (4,5).Find out the total number of squares possible if all edges are parallel to X or Y axis.
NOTE : Include overlapping squares, squares having one side in common and squares contained within another square. Co-ordinates can have float values.

Example below -
I have considered a very simple input and output combination to keep it short.
Input
{
(0,0),(0,3)
(0,0),(3,0)
(0,3),(3,3)
(3,0),(3,3)
}
Output : 1

Possible Approach : Create a map as below -

Key(Slope of Edge in Degrees) - Value(Array of Edges)
0 - {(0,0),(3,0)},{(0,3),(3,3)}
90 - {(0,0),(0,3)},{(3,0),(3,3)}

While inserting edges in the map, make sure the edges are sorted by max(x1,x2) first and then max(y1,y2).
Pick 2 edges from one slope let's say slope 0, then pick 2 edges from slope 90 and see if square is formed or not. If square not formed, then look at next 2 edges of slope 90 and so on.
Sorting here is an expensive operation.

Please share any better solutions.

Given a grid M x N cells having weight in each cell(any integer),
For every path from TOP-LEFT to BOTTOM-RIGHT, find the minimum weight you come across.(Minimum per path.)
Now from all those minimum weights, find the Maximum.
You can move in all 9 directions.

Is this a trick question?

Get the sum of all prime numbers up to N. primeSum(N).
Follow-up: If primeSum(N) is frequently called, how to optimize it.

Find a pair that equals to the given target from the list of given two lists.
example:
input:
target = 7
list1= [[1,2],[2,4[,[3,6]]
list2 = [[1,2]]

Output:[[2,1]]

Explanation: There are only three combinations [1,1],[2,1] and [3,1], which use a total of 4,6, 8 respectively. Since 6 is the largest use that does not exceed 7, [2,1] is the only optimal pair.

Example 2:
Input :
target = 10
list1 = [[1,3],[2,5],[3,7],[4,10]]
list2 = [[1,2],[2,3],[3,4],[4,5]]

Output;
[[2,4],[3,2]]

Prroblem: write an algorithm to calculate the minimum cost to add new roads between the cities such that all the cities are accessible from each other

int numTotalAvailableCities = 6;
int numTotalAvailableRoads = 3;
int[,] roadsAvailable = { { 1, 4 }, { 4, 5 }, { 2, 3 } };
int[,] costNewRoadsToConstruct = { { 1, 2,5 }, { 1,3,10 }, {1,6,2} ,{ 5, 6, 5 } };
int numNewRoadsConstruct = 4;

public class MinimumCostToConstructNewRoad
    {
        public static int getMinimumCostToConstruct(int numTotalAvailableCities,
            int numTotalAvailableRoads,
            int[,] roadsAvailable,
            int numNewRoadsConstruct,
            int[,] costNewRoadsConstruct)

        {
            int totalCost = 0;
            bool[] Visited = new bool[numTotalAvailableCities];
            int[] Keys = new int[numTotalAvailableCities];
            int[] Parent = new int[numTotalAvailableCities];

            int[,] AdjMatrix = GetAdjecencyMatrix(roadsAvailable, costNewRoadsConstruct, numTotalAvailableCities);


            for (int i=0;i< numTotalAvailableCities;i++)
            {
                Keys[i] = Int32.MaxValue;
            }

            Keys[0] = 0;
            Parent[0] = -1;

            for(int i=0;i< numTotalAvailableCities-1;i++)
            {
                var u = FindMin(Visited, Keys);

                Visited[u] = true;
                for(int v=0;v< numTotalAvailableCities;v++)
                {
                    if(Visited[v]==false && AdjMatrix[u, v]!=Int32.MaxValue && AdjMatrix[u,v]<Keys[v])
                    {
                        Parent[v] = u;
                        Keys[v] = AdjMatrix[u, v];
                    }
                }

            }

           for(int i=1;i< numTotalAvailableCities;i++)
            {
                totalCost = totalCost + AdjMatrix[Parent[i], i];
            }
            return totalCost;
        }


        private static int FindMin(bool[] Visited, int[] Keys)
        {
            int min = Int32.MaxValue; int index = -1;
            for (int i = 0; i < Keys.Length; i++)
            {
                if (Visited[i] == false && Keys[i] < min)
                {
                    min = Keys[i];
                    index = i;
                }
            }
            return index;
        }


        private static int[,]  GetAdjecencyMatrix(int[,] roadsAvailable, int[,] costNewRoadsConstruct,int numTotalAvailableCities)
        {
            int[,] AdjMatrix = new int[numTotalAvailableCities, numTotalAvailableCities];

            for (int i = 0; i < numTotalAvailableCities; i++)
            {
                for (int j = 0; j < numTotalAvailableCities; j++)
                {
                    AdjMatrix[i, j] = Int32.MaxValue;
                }
            }


            int count = 0;
            for (int i = 0; i < roadsAvailable.GetLength(0); i++)
            {
                int start = roadsAvailable[i, count]-1;
                int end = roadsAvailable[i,count+1]-1;
                AdjMatrix[start, end] = 0;
            }

            for (int i = 0; i < costNewRoadsConstruct.GetLength(0); i++)
            {
                int start = costNewRoadsConstruct[i, count]-1;
                int end = costNewRoadsConstruct[i, count+1]-1;
                int cost= costNewRoadsConstruct[i, count + 2];

                AdjMatrix[start, end] = cost;
            }

            return AdjMatrix;
        }
    }

how would you debug a tablet with a part of its touch screen is broken.

Given a series of equations e.g. [A = B, B = D, C = D, F = G, E = H, H = C]
and then another series [A != C, D != H, ..., F != A ]

Check whether the equations combined is valid.

For the example given, your program should return 'invalid', because the first series implies that A = C, which contradicts the statement A != C in the second series.

Imagine you have a computer keyboard that has all the letters mismatched

example:
typing q gives you a
typing w gives you b

all 26 letters in the alphabet are there, but typing one letter will give you another one

you are asked to write an algorithm to find whatever word you tried to type and count how many cycles you did to find the word

a restriction was set you need to type the whole word every time, not go character by character

note: a graph was suggested to represent the letter mappings

How to find out distinct ngrams from a email_alias.
For instance xyz@gmail.com here the email_alias is xyz.for xyz if we want to find bigram then function should have input the email_id,and the number of grams lets say 2.
Than it has to return the distinct count of ngrams present in the email_alias.

You have two files in hdfs one having date range with two columns start date and end date and another having two column with date and visitors field. You have to write a spark code which gives date range having maximum no. of visitors using that two files.

Given an array which represents columns, find the position of two columns which when removed will trap the maximum amount of water. This is related to trapping raining water problem.

Given an unsorted array find the maximum distance between two elements satisfying the condition A[i] < A[j] where i < j. There will always be a solution.

For eg. 6, 9, 3, 2, 10, 2, 3

How should I prepare for the interview with Alexa team at Amazon?

Given max. travel distance and forward and backward route list, return pair of ids of forward and backward routes that optimally utilized the max travel distance.:

eg: max travel distance is : 11000
forward route list : [1,3000],[2,5000],[3,4000],[4,10000]
backward route list : [1,2000],[2,3000],[3,4000]

Result : [2,3] ...2 is from forward and 3 is from backward...total distance is 9000...no other combination is there which is >9000 and <=11,000.......0(n^2) solution is straight forward, thinking that sorting both might help.

Given an array, coin of size n, coin[i] denotes the no. of coins on the position i. Can move any number of coins from the position i to (i+1) or (i-1). What is the minimum no. of moves required to redistribute the coins, so that each position i has at least 1 coin ?
Note: Summation of total coins on the array is exactly n.

Given multiple input streams of sorted numbers of infinite size, produce a single sorted output stream.

(The size of all the input streams are unknown)

For eg.

Input Stream 1: 2,4,5,6,7,8...........
Input Stream 2: 1,3,9,12..............
Input Stream 3: 10,11,13,14........

Output Stream:
1,2,3,4,5,6,7,8,9,10,11,12,13...............

Group orders by items present in the orders.

Class Order{
String orderId;
List<String> items;
}

Given Order id and items:

O1: [A, B]
O2: [B, C]
O3: [D, E]

Output: [[O1, O2], [O3]]

Note: There can be more that 2 items in an order.

List<List<String>> implementhis(List<Order> orders){
}

Design an email client where you can only send emails to people who are present in your contact list. Build for only the following functionaliy
1) Send/Receive Emails
2) Add/Remove Contacts
3) See Inbox
4) See Sent Mail

Design a distributed LRU Cache.

Given a binary tree, find the closest LEAF node to the target.

What would be the sample class design of notification system?

What would be the sample class design of tic tac toe game?

What would be the sample class design of Outlook like meeting scheduler?

Given two arrays. One is for tasks (Processes) and each element depicts the amount of cores required to run the task. 2nd array is an array of CPU where each element depicts the no of cores in it.We have to tell how many maximum number of tasks can be allocated. Example: Task: [3, 5, 7], Cores: [1, 3, 5] . Here only task 0 and 1 can be allocated to CPU 1 and 2 . So, answer=2.

What is the best way to generate first N primes? (not primes up to N but first N primes)

How do find out the top trendings products on a last hour/day/monthly basis?

Given that we have access to a real-time stream of sold product ids.

Design Amazon prime video

How would you design a system where you have 1000 records in database and on UI you are showing them, a user can select single or bulk record which can be in any order and drag drop to reorder the sequence of the record. Example :
I have below records
1
2
3
4
5
a user selects 1 and dragdrops it on 5th position, so the new order becomes 2,3,4,5,1. This has to be done at the database layer and in efficient way. How to maintain continuous reordering sequence of records?

Give m balls and n bins. Find out how many ways to assign balls to bins. Notice the buckets has no order. Like (1,2,3) and (3,2,1) are considered the same.
eg, m = 3, n = 2, return 2. (1, 2) and (3, 0)

Two Sum. Then follow up three sum