CareerCup

Given the changes to SAP stock price over a period of time as an array of distinct integers, count the number of spikes in the stock price which are counted as k-Spikes.

A k-Spike is an element that satisfies both the following conditions:

There are at least k elements from indices (0, -1) that are less than prices[i].

• There are at least k elements from indices (i+1, n-1) that are less than prices[i].

Count the number of k-Spikes in the given array.

Example

prices = [1, 2, 8, 5, 3, 4] k = 2

There are 2 k-Spikes:

• 8 at index 2 has (1, 2) to the left and (5, 3, 4) to the right that are less than 8.

• 5 at index 3 has (1, 2) to the left and (3, 4) to the right that are less than 5.

Output is : 2

Create a stack for bools. it will have these functions
void push(bool input)
bool pop() // no one will ever try to pop if it is empty
bool empty() const // returns true if the stack is empty
void clear() // cleans out the data and recovers the memory
This stack should not be limited in size but grow as needed.
hard part
save space, it is ok if it is slow from time to time but should generally be fast
98% of the time we will push false and 2% of the time we will push true
edge conditions
the first push may be true or false
there may be long runs of just pushing true or long runs of just pushing true
second part
how would you change it to if it was 80 / 20 and there were long runs of an average length of 15 trues in a row?
third part
How would you change it if there were different ratios and different average length runs.

Write code to return true if a cycle exist in a graph.

Input to function is a 2D array where every array was of size 2 and contained connecting vertices.

Print the most near missing integer in the unsorted value.

public static void main(String args[]) {

        System.out.println(solution(new int[]{-4,-2}));
    }

    private static int solution(int[] ints) {
        //1,2,3,4
        //2,3,4 = 1
        //-2,-1,2,3,4 = 0,0,2,3,4 = 1
        //-4,-3,-2 = 1
        //-4,-2 = 1
        //-3,-2,-1 , 1 = 2

        Arrays.sort(ints); //O(log*n)
        for (int i = 0; i < ints.length; i++) {
            if (ints[i] > 0) {
                if (ints[i + 1] - ints[i] > 1) {
                    return 1;
                }
                break;
            }
            ints[i] = 0;
        }
        //O(n-m) n- lenght array , m - negative interger
        //1,2,3,5,7,8,9,10
        for (int i = 0; i < ints.length - 1; i++) {
            if (ints[i + 1] - ints[i] > 1) {
                return ints[i] + 1;
            }
        }
        //O(n-k)
        return ints[ints.length - 1] + 1;
        //O(log n * n2)
    }

When a person who knows it meets any other person, they immediately share the story with them.
Initially, only person 1 knows the story. Given a list of meetings between people in a form of
(person_1_id, person_2_id, timestamp) construct a list of the persons who will know the story
at the very end.

Example: [(1, 2, 100), (3,4, 200), (1,3, 300), (2,5, 400)], 1 // The events could be out of order.
Person 2 will learn the story at the moment 100, person 3 — at the moment 300,
person 5 — in the moment 400. Person 4 will never learn the story. So the answer is [1, 2, 3, 5].

Eg2: [(1, 2, 100), (2, 3, 100), (4, 5, 100)], 2
where the first parameter is array of the Persons meet at particular timestamp, second parameter is the PersonId who knows the story first.
Output: [1, 2, 3]

Given a string s consisting of items as "*" and closed compartments as an open and close "|", an array of starting indices startIndices, and an array of ending indices endIndices, determine the number of items in closed compartments within the substring between the two indices, inclusive.

An item is represented as an asterisk ('*' = ascii decimal 42)
A compartment is represented as a pair of pipes that may or may not have items between them ('|' = ascii decimal 124).
Example

s = '|**|*|*'

startIndices = [1, 1]

endIndices = [5, 6]

The string has a total of 2 closed compartments, one with 2 items and one with 1 item. For the first pair of indices, (1, 5), the substring is '|**|*'. There are 2 items in a compartment.

For the second pair of indices, (1, 6), the substring is '|**|*|' and there are 2 + 1 = 3 items in compartments.

Both of the answers are returned in an array, [2, 3].

Function Description .

Complete the numberOfItems function in the editor below. The function must return an integer array that contains the results for each of the startIndices[i] and endIndices[i] pairs.

numberOfItems has three parameters:

- s: A string to evaluate

- startIndices: An integer array, the starting indices.

- endIndices: An integer array, the ending indices.

Constraints

1 ≤ m, n ≤ 105
1 ≤ startIndices[i] ≤ endIndices[i] ≤ n
Each character of s is either '*' or '|'
Input Format For Custom Testing

The first line contains a string, s.

The next line contains an integer, n, the number of elements in startIndices.

Each line i of the n subsequent lines (where 1 ≤ i ≤ n) contains an integer, startIndices[i].

The next line repeats the integer, n, the number of elements in endIndices.

Each line i of the n subsequent lines (where 1 ≤ i ≤ n) contains an integer, endIndices[i].

Sample Case 0

Sample Input For Custom Testing

STDIN Function
----- --------
*|*| → s = "*|*|"
1 → startIndices[] size n = 1
1 → startIndices = 1
1 → endIndices[] size n = 1
3 → endIndices = 3
Sample Output

0
Explanation

s = *|*|

n = 1

startIndices = [1]

n = 1

startIndices = [3]

The substring from index = 1 to index = 3 is '*|*'. There is no compartments in this string.

Sample Case 1

Sample Input For Custom Testing

STDIN Function
----- --------
*|*|*| → s = "*|*|*|"
1 → startIndices[] size n = 1
1 → startIndices = 1
1 → endIndices[] size n = 1
6 → endIndices = 6
Sample Output

2
Explanation

s = '*|*|*|'

n = 1

startIndices = [1]

n = 1

endIndices = [6]

The string from index = 1 to index = 6 is '*|*|*|'. There are two compartments in this string at (index = 2, index = 4) and (index = 4, index = 6). There are 2 items between these compartments.

Q.1 Rather than separate T[1…m] into two half size arrays for the purpose of merge sorting, we
might choose to separate it into three arrays of size x%3, (x+1)%3, and (x+2)%3, to sort each of
these recursively, and them to merge the three sorted arrays. Give a more formal description of
this algorithm and analyze its execution time. Justify your answer with example.

rain strikes and the roads are flooded .Mr x has to get home from work.your task is to make sure he returns home in the shortest time .consider the roads as a graph with crossing as nodes and the path between two nodes as an edge. SAssume the graph is unidirected and the numbers are numbered .1 to v(v<=50)

Given a square (n x n) matrix which only contains 0 and
1. Find the minimum cost to reach from left most column to rightmost column.
Constraints/rules:
a. Starting point: You can start from any cell in the left most column i.e. (i, 0) where i can be between 0 and n( number of rows/ columns)
b. Destination: You can reach any cell in the rightmost column i. e ( k, n) where k can be anything between 0 and n.
c. You cannot visit a cell marked with 0.
d. Cost is defined as the sum of cells visited in path.
e. You can move up, down, left and right but not diagonally.

For example,
take 2x2 matrix
1 | 0
1 | 1

One possible path is 00 -- 10 -- 11 with cost 3
Other one is 10 -- 11 with cost 2
so minimum cost on this case is 2.

A dictionary is combination of characters from a-z. let's say a=1,b=2.. and so on z=26. you are given n and k. you have to find sum of length k from given combination.
for example n=51 and k=3 then your answer should be =axz
as there can be many combination for given sum so it is suggested to print those string which comes first in dictonary

beautiful numbers are those numbers which contains digit only 4 and 5 also they are palindrome.length of number can't be odd. for example
44,55,4554 are beautiful numbers where as 38, 444 are not.
your task is to find nth number in this series. let's say if n=4 then output should be 4554. for n=1 output will be 44 always.

How can you read last 10 lines of a big file and a follow up question was how would you extend this process optimally to read last 10 lines of 1000s of files?

You are required to collect N numbers from a bag. Initially, the bag is empty. Whenever you put a number X in the bag, then the owner of the bag asks the question.

The questions are as follows:

. What is the greatest integer that is smaller than X and present inside the bag?

. What is the smallest number that is greater than X and present inside the bag?

If you answer both the questions correctly, then you can put X inside the bag. Your task is to answers the questions that are asked by the owner of the bag. If no such numbers exist in the bag print -1.



Example:
5 (Number of elements in the bag)
1
4
2
3
7


output:
-1 -1
1 -1
1 4
2 4
4 -1

given array and max element in array. Find no. of elements present between a given range in O(1). You can do one time processing of array.

Given an integer 'n', create an array such that each value is repeated twice. For example

n = 3 --> [1,1,2,2,3,3]
n = 4 --> [1,1,2,2,3,3,4,4]

After creating it, find a permutation such that each number is spaced in such a way, they are at a "their value" distance from the second occurrence of the same number.

For example: n = 3 --> This is the array - [1,1,2,2,3,3]

Your output should be [3,1,2,1,3,2]

The second 3 is 3 digits away from the first 3.
The second 2 is 2 digits away from the first 2.
The second 1 is 1 digit away from the first 1.

Return any 1 permutation if it exists. Empty array if no permutation exists.

Follow up: Return all possible permutations.

Write a program to find the given new program can be scheduled or not?
Already scheduled Programs: P1(10,5), P2(25,15)
New Programs: P3(18,7), P4(12, 10).
In P1(10, 5), where 10 is the starting time, 5 is the execution time.
As The P3(18, 7) starts at time 18 and executes for 7 mins i.e., the end time is 18+7 = 25. So this time slot is free and there is no overlap with already scheduled programs. Hence P3 can be scheduled.

As the P4 overlaps with P1, So P4 cannot be scheduled.

Given two strings, A and B, of equal length, find whether it is possible to cut both strings at a common point such that the first part of A and the second part of B form a palindrome.

Extension1. How would you change your solution if the strings could be cut at any point (not just a common point)?

Extension2. Multiple cuts in the strings (substrings to form a palindrome)? Form a palindrome using a substring from both strings. What is its time complexity?

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.