CareerCup

Write a new data structure, "Dictionary with Last"

Methods:
set(key, value) - adds an element to the dictionary
get(key) - returns the element
delete(key) - removes the element
last() - returns the last key that was added or read.

In case a key was removed, last will return the previous key in order.

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;
        }
    }

Given a string s contains lowercase alphabet, find the length of the Longest common Prefix of all substrings in O(n)

For example

s = 'ababac'

Then substrings are as follow:

1: s(1, 6) = ababac
2: s(2, 6) = babac
3: s(3, 6) = abac
4: s(4, 6) = bac
5: s(5, 6) = ac
6: s(6, 6) = c

Now, The lengths of LCP of all substrings are as follow

1: len(LCP(s(1, 6), s)) = 6
2: len(LCP(s(2, 6), s)) = 0
3: len(LCP(s(3, 6), s)) = 3
4: len(LCP(s(4, 6), s)) = 0
5: len(LCP(s(5, 6), s)) = 1
6: len(LCP(s(6, 6), s)) = 0

String contains only lowercase alphabates.

Implement phone book <unique name, number>
1.Sorted phone book
2.searching based on name
3Searching based on number. What are the data strutures required

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

If you had n racers and m checkpoints, how would you list out the racers in the order in which they are in the race given that each checkpoint gets a notification when a specific racer crosses it?

Your code should run in O(1).

Note: Players cannot cheat, i.e. they cannot miss a checkpoint

Example:

Assume 5 checkpoints(C1, C2, C3, C4, C5) and 10 racers(P1, P2,...P10).

Now once the race begins, lets say P2 first crosses C1. So the current race order is P2.

Now P1, P3, P4 cross C1; so the race order is P2, P1, P3, P4.

Now P1, crosses C2; so the race order becomes P1, P2, P3, P4

Now P3, crosses C2; so the race order becomes P1, P3, P2, P4

Now P5, crosses C1; so the race order becomes P1, P3, P2, P4, P5

Now P1 crosses C3; so the race order remains P1, P3, P2, P4, P5

and so on.

Assume that you get notified of players crossing a checkpoint by a function update(player name, checkpoint). Your task is to show the players in order in O(1) i.e return a vector of players in-order in O(1)

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

print hockey stick number in pascal triangle where row of triangle can be upto 30000 and length of stick can be upto 100.

Question : Given a set of N numbers [1,N], partition them into 2 disjoint subsets based on a set of K queries.
Each query is of the type (n1, n2) where n1 and n2 are distinct numbers from the set and n1 and n2
belong to opposite subsets.

Example:

Input:

Input:
N = 4
K = [(1, 2), (1, 3), (2, 4)]

Output:
Set 1 : (1,4)
Set 2 : (2,3)

word look up

You have been given a map which holds book name and book author. One author might have several different books. But books are unique. Now, write a function which will return you a Map which will have the author name as unique and all the books he has written as values.

Book Map=["Java"-->"John", "C#"-->"Rob", "Ruby"-->"John", "Rails"-->"Rob"]

This should return a Map which has the following:

["John"-->{"Java","Ruby"}
"Rob"--{"C#","Rails"}]

https://codejamanalysis.wordpress.com/2017/03/18/crossover-problem-super-stack/

Any Optimized Solution to avoid TLE for 4 test cases. I have tried by implementing Stack using Doubly Linked List.
Still not able to pass test cases!!!

Given a BST of memory sizes. Find best fit for a memory block of size M.

Given a wall, which is made up of two types of bricks (Porus / opaque ). Porus bricks allow water pass through them. Opaque won't. Find whether water reaches to ground, if there is any rainfall.
Water can flow from top to bottom, diagonally, horizontally as well. Only flowing from bottom to top is not possible.

Given a 2-d integer array, find the size of the largest connected area (number of elements connected), where two elements are connected if they are side-adjacent in matrix(up,down,left,right operations). Also there can be maximum of two different integers present in this set.

Given two sets of intervals such as {[1, 2], [4, 8]} and {[2, 5]}. Find their union {[1, 8]} for the two intervals.

Design a dictionary which words are grouped by the same characters. For example, dog and god are in the same group. And how to make it scalable to handle a huge number of words?

We have an array if 0's and 1's like

00010000010001001

Assume that all 1's are a person and if a new person comes and if we want to add to the array in such a way that the gap between individuals are maximum as possible.

if we add a new person, then the new array should be

000100100010001001

Given a string as input, return the list of all the patterns possible:

'1' : ['A', 'B', 'C'], 
'2' : ['D', 'E'],
'12' : ['X']
'3' : ['P', 'Q']

Example if input is '123', then output should be [ADP, ADQ, AEP, AEQ, BDP, BDQ, BEP, BEQ, CDP, CDQ, CEP, CEQ, XP, XQ]

/*Coding question: The customers for a particular business, required to use a webpage to select a Browse Node.
A Browse Node, is an element in the classification structure used to classify products in the Amazon webpage.
The products are classified in 8 categories. Each category has its own sub-classification that looks like a tree with many
children per node and many levels. The UI developer has a tool to paint such tree. He requires from you (You are the backend developer)
to implement 2 interfaces for him:

Node getRoot();
List<Node> getChildren(Node node);
The data is available for you in a text file with this format:
//nodeid, parent_node_id, nodename

Example:
//nodeid, parent_node_id, nodename
10, 1, Comedy Books
20, 2, Tablets
1, -1, Books
11, 1, Novels
12, 11, Terror novels
2, -1, Electronics
-1, 0, GlobalRoot
*/

Given n line segments, find if any two segments intersect
http://www.geeksforgeeks.org/given-a-set-of-line-segments-find-if-any-two-segments-intersect/

N different couple go to cinema with 2N different seats. They take their place randomly. You could make swap operations. Write a code for given input what is the minimum number of swap operations for sitting all couples with their partners? Additionally, be sure that no one swaps more than 2 times.

Given an array of sorted integers and find the closest value to the given number. Array may contain duplicate values and negative numbers.

Example : Array : 2,5,6,7,8,8,9
Target number : 5
Output : 5

Target number : 11
Output : 9

Target Number : 4
Output : 5

Write a merger and separator for Linked List.
eg: 1->2->3->4->5
separator()
1->3->5 and 2->4
merger()
1->2->3->4->5

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

You are given a stream of numbers which represent the stock prices of a company with timestamp. You need to perform some set of operations on the stream of data efficiently as below: 1. findStockPriceAtGivenTimeStamp(Timestamp) 2. deleteAndGetMinimumStockPriceForToday() Timstamp: 1 2 3 . 4 . 5 Prices: 12 34 4 . 1 . 18

Explain the Data Structure which is well suited to implement UNIX commands like PWD, LS, MKDIR, CD in an imaginary OS. No code required.

Design a text based rpg.
- Player can enter room.
- Room has 4 walls and items
- a wall can have door
- user can enter a different room if they chose a wall which has door.
- There is also a Enemy, which walks around different rooms. If present in the same room, takes away all your items
- A player has an inventory which has list of items
- a item can be food or weapon


User should be able to start a game and be given set options(in text) of what command to execute, like pick up item in current room, walk north, east, south, or west, or undo action to return to previous state.

You are given a set of N horizontal lines which are connected by equal number of vertical lines to form squares of size 1x1. Now some segments are removed. You need to count the number of squares of all sizes (1x1, 2x2, ..., NxN) with all sides present.

Image : https://he-s3.s3.amazonaws.com/media/uploads/1ce3516.png

In the above example you see four horizontal and vertical lines and few missing segments. Now you need to count the number of squares of all sizes with all sides.


Input :

First line is a positive integer N, number of horizontal and vertical lines.

Second line is positive integer M, number of segments removed.

Then there are m lines, each containing V,i,j or H,i,j where i and j are positive integers. H,i,j indicates a horizontal missing segment in the ith horizontal line between the jth and (j+1)th point on the line. V,i,j represents a gap in ith vertical line between the jth and (j+1)th point on the line.


Output :

Is the total number of squares in the figure with all sides along the remaining lines in the figure.


Sample Input :
4
4
H,2,1
H,3,1
V,2,2
V,2,3

Output :
5


Explanation : Here in this figure we have 4 squares of size 1x1 and 1 square of size 3x3, hence total is 5.

// 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], ... }