CareerCup

Round 2:(1.h 15min)
===================
Q1. Given a sorted array having duplicate elements,how would you find first index of a given element in O(nlogn).
Write code for it. Change the condition to find out last index of that elements.
[ Hint Binary search]

R1 | Q2. Find an element in a sorted rotated array in O(nlogn ) complexity.

Round 1: (1 h)
==============
Q1. Design a Garbage collector like java. How would you detect depended reference loop ?
Hist : Class design, Cycle detection algorithms for disjoint graph( List of connected graph)

There is a byte array which contains the character of one byte and two bytes. One byte character has range 0 to 127 and first character of 2 byte character is 128 to 255 and second byte character has range 0 to 255. Now, two pointers are given, one points to the start of the and another points to somewhere else.
Tell which character 2nd pointers points to?

Given a set of 21 tasks = {A, B,....Z} except I, O, U, X and Q. Each task requires 4 hours of processing. Except for tasks E, Y, P, R, W that require 8 hours of processing.

You have 3 machines to process these tasks = T1, T2, T3. T1 and T2 are available everyday for 8 hours. T3 is available only on Mon, Wed and Fri for 8 hours.

You are given 3 lists that indicate the dependency list among the tasks.
L1 = A->R->K->M (eg A can be completed if R is completed, R can be completed only if K is completed etc.)
L2 = N->G->V->E->Z->H
L3 = C->F->Y->D->J->P->T->S->W->B->C (cycle)

Each task needs one machine for its duration to complete.
Tasks cannot be resumed. Which means the 8 hour tasks cannot be executed over 2 days.
Each machine can process only one task at any time.
T1, T2 and T3 can process different tasks in parallel.
You are starting your schedule on a Wednesday.
Machines can be scheduled only during weekdays.
The first Monday in your schedule is a downtime for all the machines.

Given these constraints, write a program that generates a schedule between the tasks and machines such that all the tasks are completed at the
earliest.

Given a linked list with next and high pointers, populate high pointers to the next higher node, inplace and O(n).

Given a table of the form:

1 A,B,C,A,B
2 A,B,A,A,A
3 C,D,C

Give the number of duplicate characters, eg: for 1 there are 2 A's and 2 B's, so the result is 2

For 2 A is repeated 4 times so the result is 3

For 3, C is repeated twice so the result is 1

My suggestion was to use a CLRSQL function to calculate it

Write a function to return a path from a given node of a Binary tree to the node on its right.

Each node contains a left pointer, a right pointer and a parent pointer

The root node is not provided, the tree is not balanced, the tree is not a Binary search tree

Finding the root node and running BFS from there is not an acceptable solution. You have 30 minutes to give syntactically correct code

I was unable to complete this question and was rejected without further interviews. Perhaps I did something to offend the interviewer, this was for an entry level SDE position

You have a set of pairs of characters that gives a partial ordering between the characters. Each pair (a, b) means that a should be before b. Write a program that displays a sequence of characters that keeps the partial ordering (topological sorting).

Given pattern P (say aba) search for the pattern if the input is a stream of characters.

1. You cant store the stream of chars. not even till Length(P)
2. You have access to only one char of stream at a time.

I gave KMP algo which was okay for him, but he mentioned you could have used some better DS..

I am wondering which DS can be used to store pattern..
Trie ???

You need to consider cases for stream like aababa
there are 2 occurences

given a string determine which character appears the most and the number of times that character appeared.

As you are on Seattle, tell me how many rain drops pour on earth every year

We have a bag containing numbers 1, 2, 3, …, 100. Each number appears exactly once, so there are 100 numbers. Now one number is randomly picked out of the bag. Find the missing number.

What do you think is the next big thing in technology? For example, search engine is Google, social media is Facebook, etc. etc...

"How would you find the number of gas stations in the United States?"

*You cannot look up any concrete information (like the average number of gas stations per state), but you need to yield an accurate answer.

Implement a class that does string manipulation by overloading the following operators: <<, >>, = and ==. For example consider the following code:
StrShift example;
example = “Microsoft”;
printf(“\”example << 2\” results in %s\n“, example << 2);
In the above code the output would be “ftMicroso” which shows the last two characters of the string “Microsoft” rotated to the left of the string. Please note that state is maintained so two calls of example << 1 would give the same end result as calling example << 2 once.

3. Write a class that represents a minimal heap. The heap class should at a minimum support the following methods:
- AllocTinyHeap() which should initialize the heap with a given amount of bytes
- DeleteTinyHeap() which frees all memory associated with the heap
- TinyAlloc() which allocates a given number of bytes on the heap if there is room
- TinyFree() which frees a specific location on the heap
You may define whatever parameters are necessary for the above methods as well as write any additional methods. Overall consideration will be given to correctness, design, code readability as well as any unit testing done. As part of a final solution please submit test cases you used to verify correctness in addition to any unit tests done.

Move the first n numbers in a 10 element array to the end.

I think the way to do it was to reverse the array and then reverse the first 10-n and then the last n.

One of the questions in one of the interviews -

Given a stack S and another empty stack T and a variable v, write a function that returns S but with its elements reversed.

Suppose you have a collection of collection
Eg : CEO-> Vps-> GMs ->..
CEO will contain collection of VP's, VP's will have collection of GM's and so on.
Suppose you need to find a particular GM is the alias is given. Write a linq query to get the employee details if the employee alias is given.
Hint : Use Recursion + Linq

Given an array of integers and a length L, find a sub-array of length L such that the products of all integers are the biggest.
Example:
Input: {4, 1, -7, -8, 9}, 3
Output: {-7,-8,9}

Design a download manager. The download manager would be shipped with a browser. Detailed design of components and interaction between them.

Follow up question - What features would you add to the download manager so that it is more marketable than others.

Suppose you get number of unique users every second from bing
For eg, 2,4,5,1,2,etc
You need to write a web service method , such that it takes the input n, which return lowest n unique number from the list of unique numbers. For eg, if n is 3 then you need to return 2,1,2

A draw method is given, write a function to draw a chess board. The Draw method, draws a square and has parameters row position, column position and color.

Forgot to add this question along with my previous...
This is a brain teaser type question...

S E N D
+
M O R E
--------------
M O N E Y
--------------

Each of the above characters hold a specific value which is unique (meaning no two characters have same value). Now the question is, to uncover what value each character stands for...

(Hint - 'M' has to be 1 because it's the carry in the result (M O N E Y). Now similarly back track the rest of the characters)
Note: this hint is given by me, for the sake of understanding the question for interested folks, it was not given to me in the interview).

Imagine we have a large string like this "ABCBAHELLOHOWRACECARAREYOUIAMAIDOINGGOOD" which contains multiple palindromes within it, like ABCBA, RACECAR, ARA, IAMAI etc... Now write a method which will accept this large string and return the largest palindrome from this string. If there are two palindromes which are of same size, it would be sufficient to just return any one of them.

Test cases for int rand() which returns a random number between 0 - 999

Given a number give its english form
1-> One
999 -> Nine hundred and ninety nine

Max number is: 999, 999, 999

Design a webservice which would take a word, and return all anagrams

Given a graph that where A->B indicates that node A should be processed before processing B. Design an parallel algorithm to process all the nodes