CareerCup

You have k lists of sorted integers. Find the smallest range that includes at least one number from each of the k lists.

For example,
List 1: [4, 10, 15, 24, 26]
List 2: [0, 9, 12, 20]
List 3: [5, 18, 22, 30]

The smallest range here would be [20, 24] as it contains 24 from list 1, 20 from list 2, and 22 from list 3.

Pots of gold game: Two players A & B. There are pots of gold arranged in a line, each containing some gold coins (the players can see how many coins are there in each gold pot - perfect information). They get alternating turns in which the player can pick a pot from one of the ends of the line. The winner is the player which has a higher number of coins at the end. The objective is to "maximize" the number of coins collected by A, assuming B also plays optimally. A starts the game.

The idea is to find an optimal strategy that makes A win knowing that B is playing optimally as well. How would you do that?

At the end I was asked to code this strategy!

Given an array of integers. Find two disjoint contiguous sub-arrays such that the absolute difference between the sum of two sub-array is maximum.
* The sub-arrays should not overlap.

eg- [2 -1 -2 1 -4 2 8] ans - (-1 -2 1 -4) (2 8), diff = 16

I gave him o(n^2) algorithm but he was not satisfied.

A k-palindrome is a string which transforms into a palindrome on removing at most k characters.

Given a string S, and an interger K, print "YES" if S is a k-palindrome; otherwise print "NO".
Constraints:
S has at most 20,000 characters.
0<=k<=30

Sample Test Case#1:
Input - abxa 1
Output - YES
Sample Test Case#2:
Input - abdxa 1
Output - No

Given string say ABCGRETCABCG and substring length let us take length as 3, find the count of possible substrings, for example in above string ABC => 2 and BCG => 2 , where CGR and other 3 word length substrings has a count of 1.

You are given a binary tree with the following node structure:

struct Node
{
	int data; // some data
	struct Node *left, *right; // References to left and right children
	struct Node *previous, *next; // References to previous and next nodes
};

The tree is initialized with previous = next = NULL for all the nodes.
Using the previous and next pointers construct a doubly linked list such that each node's next is the node to its right at the same level and the last node's next is the first node at the next level.(similarly previous). The algorithm should have space complexity O(1). i.e., should be done without using extra data structures.You are given a binary tree with the following node structure

Write a program to check if the given string is repeated substring or not.
ex 1: abcabcabc - yes - abc is repeated.
2: abcdabababababab - no.

There is an island which is represented by square matrix NxN.
A person on the island is standing at any given co-ordinates (x,y). He can move in any direction one step right, left, up, down on the island. If he steps outside the island, he dies.

Let island is represented as (0,0) to (N-1,N-1) (i.e NxN matrix) & person is standing at given co-ordinates (x,y). He is allowed to move n steps on the island (along the matrix). What is the probability that he is alive after he walks n steps on the island?

Write a psuedocode & then full code for function
" float probabilityofalive(int x,int y, int n) ".

You have a complete graph with N vertices. You know that all edges have a cost of A and you are given a set of K edges whose cost is B. Find the shortest (cheapest) path from node 0 to node N - 1.

0 < N, K < 500k
1 < A, B < 500k

Give you an array which has n integers,it has both positive and negative integers.Now you need sort this array in a special way.After that,the negative integers should in the front,and the positive integers should in the back.Also the relative position should not be changed.
eg. -1 1 3 -2 2 ans: -1 -2 1 3 2.
o(n)time complexity and o(1) space complexity is perfect.

Given a undirected graph with corresponding edges. Find the number of possible triangles?
Example:
0 1
2 1
0 2
4 1

Answer:
1

Implement binary addition of two strings.
For example "101101" and "111101" equal "1101010"
You cannot use any type conversion, operate only with strings.

You are given two array, first array contain integer which represent heights of persons and second array contain how many persons in front of him are standing who are greater than him in term of height and forming a queue. Ex
A: 3 2 1
B: 0 1 1
It means in front of person of height 3 there is no person standing, person of height 2 there is one person in front of him who has greater height then he, similar to person of height 1. Your task to arrange them
Ouput should be.
3 1 2
Here - 3 is at front, 1 has 3 in front ,2 has 1 and 3 in front.

Given a BST and a value x. Find two nodes in the tree whose sum is equal x. Additional space: O(height of the tree). It is not allowed to modify the tree

If a=1, b=2, c=3,....z=26. Given a string, find all possible codes that string can generate. Give a count as well as print the strings.

For example:
Input: "1123". You need to general all valid alphabet codes from this string.

Output List
aabc //a = 1, a = 1, b = 2, c = 3
kbc // since k is 11, b = 2, c= 3
alc // a = 1, l = 12, c = 3
aaw // a= 1, a =1, w= 23
kw // k = 11, w = 23

How do you parse a phone number from a huge database of a 'n' billion webpages in 30 minutes ?

Given two object arrays of "id,weight" (sorted by weight), merge them together and create a one single array. If the "id"s are same values should be merged. Final resulting array should be sorted by weight. Result should be O(nlogn) in time complexity.

There is a graph which has 1 source and 1 sink(destination node)

In between those 2 nodes there are n levels of nodes. At each level there are exactly m nodes.
Every node of level i is connected to every node of level i+1 (All edges go in forward direction)

Find total no. of paths between source and sink.


This was basic question. Then he tweaked it by adding few more edges.
Now there were some additional edges. Now sdges can go from any lower level to any higher level. That is not just from i to i+1..

can be from i to i+2 or i +3 so on...
(such bouncing edges were added only in the n levels not from or to (to src or sink)
Now find number of paths?

Find the intersection of two linked list given their head pointer.
Constraint: You can only traverse a linked list only once.

Given a set of 2D points, some integer k, find the k points closest to the origin, (0,0).

Write a program to check whether it is a valid binary tree or not. Check all test cases (e.g. No left Node case).

we will name a number "aggregated number" if this number has the following attribute:
just like the Fibonacci numbers
1,1,2,3,5,8,13.....

the digits in the number can divided into several parts, and the later part is the sum of the former parts.

like 112358, because 1+1=2, 1+2=3, 2+3=5, 3+5=8
122436, because 12+24=36
1299111210, because 12+99=111, 99+111=210
112112224, because 112+112=224
so can you provide a function to check whether this number is aggregated number or not?

You are given a directed cyclic graph represented by an adjacency matrix. The graph has at least one terminal node (i.e. the node with no outgoing edges).

Each edge of the graph is assigned a positive integer representing a probability of taking this edge. E.g. if you have 3 outgoing edges with numbers 3, 2, and 4, this means that the prob. of taking these edges are: 3/9, 2/9 and 4/9, respectively.

You need to find the probability of reaching each terminal node from the starting node 0.

Example:
adjacency matrix 5x5:

m = {{0 1 0 0 1},
        {0 0 3 2 0},
        {4 0 0 1 0},
        {0 0 0 0 0},
        {0 0 0 0 0}}

so we have two terminal nodes here: 3 and 4
we can take the following paths:
0 -> 1 -> 3 = probability: 1/2*2/5 = 1/5
0 -> 1 -> 2 -> 3 = probability: 1/2*3/5*1/5 = 3/50
0 -> 1 -> 2 -> 0 -> 1 -> 3 ... and so on

or to the node 4:
0 -> 4: probability: 1/2
0 -> 1 -> 2 -> 0 -> 4: probability 1/2*3/5*4/5*1/2 = 3/25

and so on, summing up probabilities of all possible paths we get:
total probability to reach node 3: 13/38
total probability to reach node 4: 25/38

Given s string, Find max size of a sub-string, in which no duplicate chars present.

Given a string which only contains lowercase. You need delete the repeated letters only leave one, and try to make the lexicographical order of new string is smallest.
i.e:
bcabc
You need delete 1 'b' and 1 'c', so you delete the first 'b' and first 'c', the new string will be abc which is smallest.

ps: If you try to use greedy algorithm to solve this problem, you must sure that you could pass this case:
cbacdcbc. answer is acdb not adcb

I can't solve this problem well and the interviewer said that you can scan the string twice. First scan is do some preprocess, and the second is to get the answer, but I really can't come up this idea.

There are at most eight servers in a data center. Each server has got a capacity/memory limit. There can be at most 8 tasks that need to be scheduled on those servers. Each task requires certain capacity/memory to run, and each server can handle multiple tasks as long as the capacity limit is not hit. Write a program to see if all of the given tasks can be scheduled or not on the servers?

Ex:
Servers capacity limits: 8, 16, 8, 32
Tasks capacity needs: 18, 4, 8, 4, 6, 6, 8, 8
For this example, the program should say 'true'.

Ex2:
Server capacity limits: 1, 3
Task capacity needs: 4
For this example, program should return false.

Got some idea that this needs to be solved using dynamic programming concept, but could not figure out exact solution.

Given an int array which might contain duplicates, find the largest subset of it which form a sequence.
Eg. {1,6,10,4,7,9,5}
then ans is 4,5,6,7

Sorting is an obvious solution. Can this be done in O(n) time

Given an equation in the form 2^i * 3^j * 5^k * 7^l where i,j,k,l >=0 are integers.write a program to generate numbers from that equation in sorted order efficiently.

for example numbers from that equation will be in the order 2,3,5,6,7,8,9.....and so on..

Given a max-heap represented as an array, return the kth largest element without modifying the heap. I was asked to do it in linear time, but was told it can be done in log time.