CareerCup

Given an input of the calendar objects of 10,000 employees, input is a time interval T and an employee[] array, find the first interval where all the employees in the employee[] array are free for a minimum time interval T (i.e schedule the meeting)

Given a binary tree, connect all node in the same level in toggle manner.

Toggle the linking every K level. For first K level, you should link to next right node. Next K you should link to next left and so on.

Node structure is :

struct node
{
int data;
struct node *left, *right, *next;
};

Each level next should point to the next right or left node in the level. For last node in each level, next should be NULL

For ex - if K=2 then for first 2 level of tree connect next pointer from left to right and for next 2 levels connect next pointer from right to left and so on.

This question is windows based subsystem design to test the design skills. We are working in a complex system which involves multiple process, DLLs, windows services which will be gets installed on our system with the project. We have to design a logger system for this project where in all the multiple subsystem can use this logger system for their logging activities .
Design pattern used
Statically linked or Dynamically linked?
How the logger functions are designed (sample signatures)
How we can improve performance while logging (Think of ETL tracing)

Sort a set of ip address given either in ascending or descending order

char** SortIPAsc(char** pIPAddress);
char** SortIPDesc(char** pIPAddress);

for given array

s[] = {5,1,0,4,2,3}

1) length of array is not given.
2) If length of array is 5 content is guaranteed to be between 0 to 5. There is no repetition of numbers. Sample example for length(s, 3)
- a[3] = 4 , a[4] = 2, a[2] = 0, a[0] = 5, a[5] =3
returns length of 4 .

For given condition write subroutine
int length (s, 3)
- to find the number of steps it takes to find given value - It's a function api - that I was asked to write with the conditions - I cannot change parameters of the function - I have to make sure return value is correct

Additional Condition:

You cannot use any loop statements like for, while and so on -
You cannot use any global or static variables.
You cannot call other routines inside this routine
You cannot modify given function parameters - it stays length (s, n) only
You cannot change original array too

Given three arrays(arr1, arr2, arr3) each containing distinct positive numbers find three numbers a,b,c each from arr1, arr2, arr3 respectively such that (abs(a-b) + abs(b-c) + abs(c-a)) is minimum.

design question:
I will request you to first read only upto Solution-2 only and try to think about your solution and then read other lines. If we read whole post(without thinking about your solution) then your brain will get polluted with my idea and you may not be able to think naturally.

----------------------------------------------------------------------------
One machine daily taking backup of its datatstore on some server machine, MINIMIZE network data transferred.

Solution -1 : Compress storage and then send over network

Solution - 2 : Take diff and send only diff(and not whole data daily)

Interviewer asked for better ideas as above two are well known ideas but I was stuck.

---------------------------------------------------------------------------------

So he gave me hint(no 1) and depending upon hint I devise following solution

Solution - 3: Divide storage into sequence of 1K bits so total number of possible patters are 2^1000. Now Using hashTable just store existing 1000bits-length pattern and all their sequence numbers. And, then transfer this hashTable to server. So for example datastore consists of "file1, file2, file3=file1+file2" then we can reduce network data by 50%

So interviewer asked why 1000bits and why not 100bits or 10000bits. Also, as we increase length of bit-pattern, probability of getting duplicate patterns reduces and if we decrease length of pattern we may not be able to effectively reduce network data transferred

Solution-4: Don't divided storage bits into equal length pattern but in variable length pattern so client tells server "Pattern-X(bit string) of length L exists at offsets 5, 10003, 363738, 42311, 43433.

Interviewer said how can check for variable length patterns on client machine as this will be computaionally inefficient. I suggested Trie, Huffman coding, file-by-file comparison but he straightway discarded those ideas :)

He gave final important hint that
somehow client should give indication to server that next bytes are going to be like this without tranferring those bytes and
then server should tell client that "OK don't send next 1000bits as I already have them from previously send/stored data at different section(like different file) in storage"
and asked me how to do it and how will be the handshake/protocol between server-client

Since, throughout interview I was stuck to my hashTable solution and not able to think beyond hashTable, as per HR I got negative feedback in this interview :(

Overall interviewer was helping lot and was really helpful. He gave lot of hints and time(never said "Ok thats enough let us move on"...Finally I myself gave up :) )

Given the two objects below, implement the methods defined in the Phonebook class. This is a simulated phonebook. You should expect LookupByName and LookupByPhoneNumber to be called much more often than AddPerson. Also, this is a multi-threaded simulation so your implementations of the functions other than the constructor should be threadsafe. Feel free to rewrite this in any language of your
choice.

public struct Person 
{
	string name; 
	string phoneNumber; 
}
public class Phonebook 
{
	public Phonebook (List<Person> people) 
	{
	}

	public Person LookupByName(string name) 
	{
	}

	public person LookupByphoneNumber(string phoneNumber) 
	{
	}

	public void Addperson(person person) 
	{
	}
}

Check given Number is same after 180 degree rotation?

i/p: 69
o/p: True

i/p: 916
o/p: True

i/p: 123
o/p: False

Write a function to detect the number of cycles in a directed graph. The graph is passed as an adjacency matrix.

Given a sentence in a form of a string, reverse the words in the string and return a string. Handle a case where there might be period at the end of the sentence. If there is a period, the period has to come to the end of the reversed sentence. Discuss the time complexity of your algorithm.

INPUT: "This is a sentence"
OUTPUT: "sentence a is This"

INPUT2: "This one has period."
OUTPUT2: "period has one This."

Sort an array of 0s, 1s and 2s
Given an array A[] consisting 0s, 1s and 2s, write a function that sorts A[]. The functions should put all 0s first, then all 1s and all 2s in last.

Example
Input = {0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1};
Output = {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2}

The problem is similar to http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/

But they have added 1 trick into the question, You cannot use high = n;

It means don't calculate the length of array.

Can anyone help me in writing the code for this problem ?

there are N cities (numbered from 1 to N) in the game and connect them by N-1 highways. It is guaranteed that each pair of cities are connected by the highways directly or indirectly.The game has a very important value called Total Highway Distance (THD) which is the total distances of all pairs of cities. Suppose there are 3 cities and 2 highways. The highway between City 1 and City 2 is 200 miles and the highway between City 2 and City 3 is 300 miles. So the THD is 1000(200 + 500 + 300) miles because the distances between City 1 and City 2, City 1 and City 3, City 2 and City 3 are 200 miles, 500 miles and 300 miles respectively.

During the game the length of some highways may change. you want to know the latest THD.

sample input
3 5
1 2 2
2 3 3
QUERY
EDIT 1 2 4
QUERY
EDIT 2 3 2
QUERY

sample output
10
14
12

Given two arrays were digits of one array represent a number,maxmise the number by replacing it with elements of second array.
eg:
arr={3,1,4,5,6}
rep={1,9,5,2,3}

after replacement
arr={9,5,4,5,6}
one digit of rep can be used to replace only once.

Write a program to process the matrix. If an element is 0 at ith row and jth column, then make the whole ith row and jth column to 0.

Constraints:
Space complexity should be O(1)
Time complexity - Only single pass is allowed. Note that single pass is not O(n). This is single pass : An element will read and written only ones.

Edit:

Recursion is not allowed since it is O(n) space on stack

Given N tasks, find the maximal points that can be achieved by finishing them

Problem Constraints

There are T minutes for completing N tasks

Solutions can be submitted at any time, including exactly T minutes after the start

i-th task submitted t minutes after the start, will get maxPoints[i] - t * pointsPerMinute[i] points

i-th task takes requiredTime[i] minutes to solve

Input Format

Line 1: T, total minutes available to finish

Line 2: Comma separated list of maxPoints

Line 3: Comma separated list of pointsPerMinute

Line 4: Comma separated list of requiredTime

Sample Input

75

250,500,1000

2,4,8

25,25,25

Sample Output

1200

Explanation

First, solve the third task 25 minutes after the start of the contest. Get 1000 - 8 * 25 = 800 points

Second, solve the second task 50 minutes after the start of the contest. Get 500 - 4 * 50 = 300 points

Third, solve the first task 75 minutes after the start of the contest. Get 250 - 2 * 75 = 100 points

In total, get 800 + 300 + 100 = 1200 points


Any optimized solution for this ?

Give four points, determine is it is a square, rectangle or none of the above.

Given list of nodes of a tree, find the root of the tree. Nodes in the list are not in any particular order.
If all nodes in the tree are not given, return null



A
B C
D E F



F E A << input
A << output

John observers the following while driving to work.

•   4 were driving a red car. 
•   3 were driving a blue car.
•   3 were driving a black car.
He also notices that

•   3 of them were listining to Hip Hop
•   4 of them were listining to pop music.
•   3 of them were listining to Rock.
Additionally he notices that,

•   3 of them reached office before time on Friday.
•   3 of them reached office before time on Tuesday.
•   2 of them reached office before time on Wednesday.
•   2 of them reached office before time on Thursday.
Which of the following practice maximises his chance of getting to office before time.

a) He should drive a red car to work listining to pop music on a friday? 
b) He should drive a blue car to work listining to rock music on a Tuesday.
State how did you calculate the probabiltiy for both in your answer.

Minimum number of jumps required to climb stairs

Its basically like, you have 2 parallel staircases and both the staircases have n steps. You start from the bottom and you may move upwards on either of the staircases. Each step on the staircase has a penalty attached to it. You can also move across both the staircases with some other penalty.

I had to find the minimum penalty that will be imposed for reaching the top.

I tried writing a recurrence relation but I couldn't write anything because of so many variables.

I recently read about dynamic programming and I think this question is related to that.

With some googling, I found that this question is the same as

https://www.hackerrank.com/contests/frost-byte-final/challenges/stairway

Can you please give a solution or an approach for this problem ?

Input: two linked lists that have some duplicate nodes
the list node contains a student's info: name, telephone, address. duplication exist if the same name and phone number appears in two different lists or repeat more than ones in the same list.
Output: one lists that contains unique elements, duplications should be removed.

Input: two strings, one is short then the other
Output: indices of where a permutation of the short string start at the long string.

Generate all possible sorted arrays from alternate elements of two given sorted arrays.

Given two sorted arrays A and B, generate all possible arrays such that once first element is taken from A then from B then from A and so on in increasing order till the arrays exhausted. Then first element is taken from B then From A, and do same as above.

Design a game like angry birds

Check if the given cordinates on a map correspond to the correct address (where address or cordinates are provided in a tab separated file)

Reverse string except spaces. A string has mix of alphabets and spaces. Your task is to reverse the string, but preserve the positions of spaces. For example, reverse of " a if" is " f ia".

Write a function which takes a BST and then "flattens" it (converts in-place into new BST), so all the nodes have only right child and no left.
Example:

10
   /   \
  5   15

Output:

5
  \
  10
    \
    15

Round 6
Question 3 : You are given a word document, you have to print the words with frequencies. Now print the kth rank word in terms of frequency. Print top k words as well by frequencies

Round 6
Question 2 : VRBO(Vacation Rentals by Owner), is a portal for real state where owners can rent their properties, renters can occupy them for sort duration by giving rent to the owner via VRBO. Lets start by thinking how you can design such system. ?, What are the complexities you have address here ?, both business and technical ?, what will be your main focus ?, tell me about the architecture of the system ?
Note that he wasn't concern about finer implementation details, but looking for broader things and thoughts.

Round 6 (taken by PRINCIPAL SOFTWARE ENGINEER)
Question 1 : Since when you started searching for a new job ?, any project you are proud of ?, If you are given the same project now, how differently you will do now ?, why do you think whatever you have applied at that time was optimal ?.