CareerCup

Given a graph in which there is an edge between (u,v) if gcd(u,v)>g . Given queries of u,v find if a path from u,v exists

Given an integer S, you have to count the total number of integral solutions of the equation a+b^2+c^3+d^4<=S, such that 0<=a,b,c,d<=10000 and 0<S<10^15

Edit: Here value can be less than or equal to S, so if input S= 2 ,then output=12
i.e we can consider 0,0,0,1 and 0,0,0,0 etc also as sum will be less than S(i.e 2)

Given two strings Y and Z , return True if y beats z or z beats y .
Beating Criteria : for i in [1,N] y[i]>=z[i] , if this condition is true for any of permutations of y for any of the permutations of z .

How to divide a circular array into k group of contiguous element such that difference between maximum sum and minimum sum is minimum. Each group have contiguous element of array. For e.g If the array is as follow. [6 13 10 2] and k=2 then o/p should be 18(6+10+2)-13=5. As array is circular 6,10,2 are contiguous element of array.

For e.g If the array is as follow. [6 13 2 10] and k=2 then o/p should be 16(6+10)-15(13+2)=1. As array is circular 6,10 are contiguous element of array.

For e.g If the array is as follow. [100 92 133 201 34 34 34 94 108] and k=4 then group as follow 208(108,100), 225(92,133), (201), 196(34,34,34,94) so 225-196=29

Given a target number and a single number, write a program to find the shortest path to calculate the target number by applying "+-*/" operations to the single number. No parentheses. For example, if we have target number=26 and single number=3 return 3 * 3 * 3 - 3 / 3.

Given a Start Node and an End Node in a graph report if they are “necessarily connected”. This means that all paths from the start node lead to the end node. Report true all paths from start node lead to end node and false if at least one path does not lead to the end node. This is a directed graph which can have cycles


Does anyone know how to solve this? I had it in my interview at Google in CA and I still cant solve it

code Bubble sort, and modify it to return if the array is already sorted.
2.If single swap is needed perform and break without going through o(n2) looping

In a hashtable you can only ask for the most recent value for a key. We are going to build a hashtable where you can ask for a key at any time in the past.

API is:

get(k, t) // get the value for k at time t
put(k, v) // insert k, v at time()

time is given as a monotonically increasing version of unix system time.

Given a string S of length N. Now, you need to cut the string S into K+1 non-empty substrings by performing K cuts.
There are lots of ways of performing the cuts in the string S. For every way of performing the cuts, you need to count how many substrings will be a palindrome in that way of cut. You need to sum this count over all possible ways of cutting the string S.

Input Format
The first line contains two integers N and K as input.
The second line contains the string S as input.

Output Format
In the output, you need to print the sum modulo 
10^9+7.

Constraints
2≤N≤5000

1≤K≤N−1

String S contains only lowercase english alphabets


Sample Input

5 2
aabbc
Sample Output

12


Explanation
In the given test case there are 
6 ways to perform the cuts. All the ways are described below.

a | a | bbc = 2 substrings are palindrome
a | ab | bc = 1 substring is palindrome
a | abb | c = 2 substrings are palindrome
aa | b | bc = 2 substrings are palindrome
aa | bb | c = 3 substrings are palindrome
aab | b | c = 2 substrings are palindrome
So, the output is 
2+1+2+2+3+2=12

Int minSemsToFinishAllCourses(Map<string, list<string>)

Given a map containing courses and the list of prerequisites for that course in no particular order, determine the least number of semesters to finish all the courses.
You have to take all prerequisites before you take a given course.

Eg.
Calculus : English, math2
Math2: math 1, Arabic, english
Math1: english
English: <>
Arabic:<>

Give an algorithm for the above and code using java

Roulette -Gamblers Fallacy. start with $50, bet opposite color every time same color 4 in a row. loop 100 time or until $0. Suggest create roulette wheel object with history, a gambler object with maybe gamblingplan object. (you can find more detailed suggestions elsewhere)

Add two numbers represented as LinkedList (not LeetCode 445 which uses ListNode)
e.g
inputs: '5'->'6'->'3'
'8'->'4'->'2'
output: '1'->'4'->'0'->'5'
method signature:
LinkedList<Integer> sumList(LinkedList<Integer> l1, LinkedList<Integer> l2)

Program to find the rank student

1. Input string s. Check if string s is a valid string with valid brackets
For example:
(({{}})) is a valid s
{[]} is a valid s
[{[}]] is not valid

2. What kind of tests would you conduct to your program to minimize bugs in your program.

3. On the previous example there is only "()", "{}", and "[]" combination of brackets. If other developers want to add a new kind of brackets such as "<>". What kind of changes would change in your previous program.

Given a matrix of 0's and 1's find the smallest number of groups made of 1's, where one group can cover up to two 1's at the same time vertically or horizontally.

01111
11011
00100

The matrix above has 5 of such groups. I've seen similar questions but there the question was about groups of adjacent 1's. Here the groups are limited.
Another question how it would change, if the group wasn't limited to two but to given k - number of 1's vertically or horizontally. The time complexity should be the most efficient.
My idea here i to iterate through rows and when we find a 1, check it's bottom and right neighbour. If it has a right but no bottom, a group is made and we skip the right neighbour as it is already in a group. When the checked 1 has a bottom but no right, we make a group of them and we can skip checking the right as well i think.

Given the root of a binary tree, print the nodes column wise and row wise.

..............6
............/....\
...........9......4
........../..\......\
.........5....1.....3
..........\........./
...........0.......7

The answer would be 5 9 0 6 1 4 7 3.

Given multiple tuples in the form of (A,B) where A is the parent and B is the child in a binary tree, find if the input is valid or not. 4 error conditions were provided:
1. If a parent has more than 2 children,
2. If duplicate tuples entered,
3. If the tree has a cycle,
4. If more than one root possible.

For violation of multiple validity conditions, print the condition coming first in the above order.
If the input is valid, print the tree in a serial representation. For eg: If input is (A,B), (B,C), (A,D), (C,E) , output: (A(B(C(E)))(D))

Suppose If you are hacker, you have to push data to server and find how much data server can accept using minimal number of times. We don't the size of how much server will accept.

If a sorted array is rotated by k positions, what is the time complexity to find the starting point of the original array?
1 point
O(logn)
O(1)
O(n)
O(nlogn)

Given an array and threshold value. The threshold represents the maximum length of subarrays that may be created. Each subarray created has a cost equal to the maximum integer within the subarray. Partition the entire array into subarrays no longer than the threshold and do it at minimum cost. The subarrays are to be chosen from contiguous elements and the given array must remain in its original order. Write a function to return an integer that denotes the minimum cost to partition the array.

For more clarification, here are the test cases.
1. Array: [1,2], threshold: 1.
we divide the array to {(1),(2)} Total cost is 1+2 = 3
2. Array: [1,5,2], threshold: 2.
we divide the array to {(1),(5),(2)} with total cost 1+5+2 = 8. OR
we divide to {(1,5),(2)} with total cost 5+2 = 7 OR
we divide to {(1),(5,2)} with total cost 1+5 = 6.
Of these minimum total cost is 6. So the ans is 6 with subarrays as {(1),(5,2)}

A company wants to fly in a total of 100 candidates for the interview. The company has two office location, one in NY and other in SF and max capacity at each location is 50 candidates. You are given the cost it incurs to fly in each candidate to NY and SF.

[500, 300],[540, 600],[550, 600],[300, 50]..so on

Write an algorithm for the minimum total cost?

Given 3 unsorted arrays A, B and C you need to find all possible combinations such that A[i] + B[j] = B[k] + C[l].

Lets there are n stores.

A customer order x items. All the stores might not have all the items from the order list. So find the store/combination of stores that can serve the order request such that the set that contain least number of stores is selected so that there are lesser number of shipments.

Pascal Triangle Hockey Stick Identity?

Given an array of negative and positive integers, find the biggest sum of a sub-array.

Given an array of integers and a target. Find the two array elements if they are summed up, will result in the target.

Find 2nd duplicate in an array

Given 2 sets of words. Find the words in 2nd set that begin with any word in the 1st set.

Largest Sum Contiguous Subarray

Given integer m and n where n is odd, for all mxn matrixes that consist of 0 and 1, find the one that has max count of 1s and meets following conditions:
1. All 0s are connected;
2. All 1s are adjacent to at least one 0 (Adjacent includes diagonal line adjacent, 8 directions);
3. maxtrix[m-1][n/2] = 0.

Example :

Input: m=2, n=3
Output: [[1,1,1],[1,0,1]]

Follow up:
Given another list of 'blocked' points. Matrix will set those points to -1 and you cannot change that. Solve the problem again.