CareerCup

You are given a 1D array of integers, such as:
int[] array = [3,4,7,2,2,6,0,9];
Suppose you need to treat this array as a 2D table with a given number of rows.
You want to sum the columns of the table.
One value of numRows is 4..in that case the resultant array would look like
what if numRows==4?
3 4
7 2
2 6
0 9
—-
12 21

We have a text file with 13 Million entries, all numbers in the range from 1.000.000 to 100.000.000. Each line has only one number. The file is unordered and we have about 1% duplicate entries. Remove the duplicates.

Given an array A of N integers we draw N discs in a 2D plane, such that i-th disc has center in (0,i) and a radius A[i]. We say that k-th disc and j-th disc intersect, if $k\not =j$ and k-th and j-th discs have at least one common point.

Write a function

class Solution { public int number_of_disc_intersections(int[] A); }

which given an array A describing N discs as explained above, returns the number of pairs of intersecting discs. For example, given N=6 and


\begin{displaymath}A[0]=1 A[1]=5 A[2]=2 A[3]=1 A[4]=4 A[5]=0\end{displaymath}

there are 11 pairs of intersecting discs:

0th and 1st
0th and 2nd
0th and 4th
1st and 2nd
1st and 3rd
1st and 4th
1st and 5th
2nd and 3rd
2nd and 4th
3rd and 4th
4th and 5th

so the function should return 11.

The function should return -1 if the number of intersecting pairs exceeds 10,000,000. The function may assume that N does not exceed 10,000,000.

Given a binary tree, print each level on a single line.

you are given following:
1. An empty tank
2. Unlimited source of water.
3. Some container of certain measurments and a container of 1 litre is always given.

Your job is to fill the tank from source of water using the containers in minimum number of steps.
You cant fill the container with a small amount of water than its size (filling partially is not allowed).
Find the number of steps and print the solution.

e.g.
Tank Size: 80 litre
Containers: 1,3,5,6,25 litre
Solution:
4
5,25,25,25

Tank Size: 71 litre
Containers: 1,3,5,6,25 litre
Solution:
6
3,6,6,6,25,25

Write a function that, given a string, returns number of characters, words and lines in that string.

Given a KxK array, rotate the array 90 degrees counter-clockwise in place.

add 2 link lists widout recursion in O(n) n constant space

Given a binary tree, find 2 leaf nodes say X and Y such that F(X,Y) is maximum where F(X,Y) = sum of nodes in the path from root to X + sum of nodes in the path from root to Y - sum of nodes in the common path from root to first common ancestor of the Nodes X and Y

Is there any algorithm to find distance between each pair of point among n points whose time complexity is better than O(n^2) i.e. C(n,2).

You have a digital clock having 24 hr format of HH:MM:SS. You have to find following probabilities:
1- Occurence of a particular value(let say 05) in SS
2- As 1st point we have to find probabilities for particular value in hour and minute fields.
3- probalities for other combinations(particular HH:SS or MM:SS values)
You have to answer the probability in terms of digits occurence...for example in the second's field.. at unit place 10 digits(0-9) are possible, and in the tens place 6 digits are possible (0-5)

It is not a very straight forward problem. Many different scenarios are possible(value in the seconds field will change in every 1 min, on the other hand, the value in the hour field will remain same till 60 min)
Please don't answer ur probabilty in terms of time(as 1/60, 1/24*60) rather in terms of digits only as described above.

Given a binary matrix of N X N of integers , you need to return only unique rows of binary arrays
eg:
0 1 0 0 1
1 0 1 1 0
0 1 0 0 1
1 1 1 0 0
ans:
0 1 0 0 1
1 0 1 1 0
1 1 1 0 0

Check Whether Point Lie Inside, on or outside the triangle efficiently what will be time complexity & which data structure algorithm
as you can see google asked they wants quality code & efficient algorithm

An easier way than what Richie mentioned is to the following:

if a point P is inside triangle ABC, then

Area PAB+Area PBC +Area PAC=Area ABC

notice that if P is on the edge of AB, BC, or CA, the above hold. But effectively, one of the area PAB, PBC, PAC is 0 (so just make sure you check that).

if P is outside, the above equality does NOT hold..

But how you will approach for if point lie outside the triangle

A rooted binary tree with keys in its nodes has the binary search tree
property (BST property) if, for every node, the keys in its left
subtree are smaller than its own key, and the keys in its right
subtree are larger than its own key. It has the heap property if, for
every node, the keys of its children are all smaller than its own key.
You are given a set of n binary tree nodes that each contain an
integer i and an integer j. No two i values are equal and no two j
values are equal. We must assemble the nodes into a single binary tree
where the i values obey the BST property and the j values obey the
heap property. If you pay attention only to the second key in each
node, the tree looks like a heap, and if you pay attention only to the
first key in each node, it looks like a binary search tree.Describe a
recursive algorithm for assembling such a tree

Suggest a DS for web server to store history of visited pages. The server must maintain data for last n days. It must show the most visited pages of the current day first and then the most visited pages of next day and so on.

Write a function which takes as parameters one regular expression(only ? and * are the special characters) and a string and returns whether the string matched the regular expression.

Given an integer 'k' and an sorted array A (can consist of both +ve/-ve nos), output 2 integers from A such that a-b=k.
PS:
nlogn solution would be to check for the occurence of k-a[i] (using binary search) when you encounter a[i]. methods like hash consume space.

Is an O(n) solution with O(1) extraspace possible?

5- Fibonacci function implement it .
then I did Iterative way to get better performance , then he asked about Fibonacci recursive and what is the complexity of it ? it is O(n2) because of the tree calls and repeated calls.

4-given an array of int and given a number , find the 2 elements in array that add up to the given number.

3- Different ways to communicate between Processes in OS.

2- Virtual function table in C++ , and how they work and how the compiler generate them and how the object know it is overridden and is it shared or each object have it's own table.

1- Difference between Array and linked list.

Write a data structure to count number of connections on web server in last 1 minute.

Given two unsorted int arrays, find the kth element in the merged, sorted array.
example:
int[] a= [3 1 7]
int[] b = [4 9]
k: 3
return 4.

Given a two balanced binary search trees.Merge both the trees so that it will form again a balanced binary search tree.

(NOTE: Request for correction: should the input bst s have same number of nodes? if the input bst s have unequal nodes, we cant necessarily build a balanced bst for the result )

Suppose there are 2 persons A and B on FB . A should be able to view the pictures of B only if either A is friend of B or A and B have at least one common friend . The interviewer discussed it for nearly 30 minutes . The discussion mainly included following points -
1. How are you going to store the list of friends for a given user ?
2. File system vs DB
3. Given list of friends of 2 users , how are you going to find common friends ?
4. If you are going to store the friends in DB then how will the table look like ?
5. How many servers do you need ?
6. How are you going to allocate work to servers ?
7. How many copies of data will you need ?
8. What problems will you face if you are maintaining multiple copies of data.

Given a credit card number with a certain number of fixed digits and a certain number of digit placeholders, find the number of solutions such that the entire number yields a remainder of 3 when divided by 13. Use properties of modulus

Given that you now have 2 geographically separated datacenters and a request comes in for a url that's not present in your current datacentre, how will you handle it?

Design a site similar to tinyurl.com

Given 3 input strings S1, S2, S3 for example take s1 = "hard" s2 = "work", s3 = "success"
assign numeric values (0-9) to each of the characters in these strings such that equation s1 + s2 = s3 holds true. Constraints are that all occurrence of a letter should be assigned the same digit. Return -1 if not possible. I told the algo using backtracking but he required in polynomial time for which I had no idea.