CareerCup

There are n number of stones. Each stone has a weight associated with it. 1st stone’s weight is 1, 2nd stone’s weight is 2.. and so on. You are given an integer x. You need to pick the maximum number of stones such that the total weight of stones picked is less than x.
You’re also given an array of stones which you can not pick.?

You are given a set of functions:

int open_port();
opens a serial port and returns 0 if everything ok (or -1 if error)

int read_port(char *buf, int buf_size)
which reads data from a serial port and stores it to 'buf' of size 'buf_size' or blocks until the data is available and returns the number of bytes read (or -1 if error occurred)

void close_port();
closes a serial port connection

Design a class:

class SerialConnection {
public:
     using ByteHook = std::function<void(char)>;

     SerialConnection(ByteHook callback);
....    
};

which should read data from the serial port asynchronously and send it to the callback function ByteHook byte by byte (e.g., for decoding).

Note that if you don't call 'read_port' often enough, the underlying system buffer might get full and some bytes will get lost..

Which data structures / sync primitives you are going to use ?

Question : Given a set of N numbers [1,N], partition them into 2 disjoint subsets based on a set of K queries.
Each query is of the type (n1, n2) where n1 and n2 are distinct numbers from the set and n1 and n2
belong to opposite subsets.

Example:

Input:

Input:
N = 4
K = [(1, 2), (1, 3), (2, 4)]

Output:
Set 1 : (1,4)
Set 2 : (2,3)

I don't remember perfectly the question, but it was like this


Given a list of 100 songs on your cell phone, find a way for each user to hear the songs without repeating songs, you need to use an algorithm that uses shuffle for songs.

Did any one took Microsoft Online Technical Screen ?? What questions I can expect in this test ??

Given a wall, which is made up of two types of bricks (Porus / opaque ). Porus bricks allow water pass through them. Opaque won't. Find whether water reaches to ground, if there is any rainfall.
Water can flow from top to bottom, diagonally, horizontally as well. Only flowing from bottom to top is not possible.

Give an positive integer n, find out the smallest integer m, such that all digits in m multiply equals to n. For example, n = 36, return 49. n = 72, return 89. You can assume there is no overflow.

Find Duplicate number from a huge amount of data which cannot fit in the memory.

Find kth-largest number from a huge amount of data which cannot fit in the memory.

We have an array if 0's and 1's like

00010000010001001

Assume that all 1's are a person and if a new person comes and if we want to add to the array in such a way that the gap between individuals are maximum as possible.

if we add a new person, then the new array should be

000100100010001001

Evaluate infix expression: 2 + 3 * 5

Interleave two singly linked lists into one.

LL1: 1 -> 2 -> 3 -> 4
LL2: 10 -> 20 -> 30 -> 40 ->50

Output LL1: 1-> 10 -> 2 -> 20 -> 3 -> 30 -> 4.
Note: Stop when we hit null for LL1.

You need to design a new YouTube feature where userA is uploading a video and userB (friend of userA) gets notified for the video and wants to watch the same video in real time (i.e. even the video is not completely uploaded but we want to enable the other user to watch it).
How would you tackle the situation when userB wants to view the content starting from a position which is not yet uploaded.

Draw block diagram for this problem identifying the different components.

Design calculator and related class, which returns result of the given expression, e.g if input is (3* 3) + 2 it returns 11.

Identify different OOPS classes and how would you call them.

A bus has to travel from A to B and the distance is d miles. There are many gas stations between A and B.
The bus has initially g gallon of gas in tank. 1 gallon of gas travels 1 mile.
Gas stations have inforamtion of remaining distance from station to destination b and max gas that can be filled from the station.
Find the minimum number of stops for bus without running out of gas ever.

eg: gas = 10 , distance = 20
gasStation[] = {{16,3}, {10, 7}, {14, 11},{11, 5}, {7, 6}}

o/p = 1
If bus stops at the stop{14,11} that is 14 miles away from destination and fills 11 gallon then it can reach destination with 1 gallon spare.
It can also stop as {16,3} and {10,7} but its 2 stops and at destination it runs out of gas.
Similarly {11, 5}, {7, 6} has 2 stops but has 1 gallon spare at destination.

Write a word processor that can do left and right justification for a sample input of string type.

Here is an example:
This is a sample.This is a sample.This is a sample.
This is a sample.This is a sample.This is a sample.This is a sample.

Additional details:
* The left margin is 5 units.
* The right margin is 75 units.
* The input string is a single-spaced collection of words and punctuation.
* If the length of the word exceeds the right margin, then we must not break the word. Instead, we must print it on the next line and justify the existing line by adding more spaces to the middle of the line.

Given a 3x3 tic-tac-toe board with players 1 and 2. Find all the possible ways player 1 can lose given a particular configuration of the board.

For example (0 denotes empty spot):
input:
0, 1, 0
2, 2, 1
1, 1, 2

Output: 1 (because the only move for player 2 to win would be to play board[0,0])

The input board can have any configuration (player 1 and 2 can be in all possible spots with any number).

Design a data structure which reads below block of text

*Status update1
**Joe is working on a bug
**Alice is on vacation
*StatusUpdate2
**Alex finished task1

and returns me an Object such that I can navigate the this nested text easily like this:

obj.children[0] - > returns "StatusUpdate"
obj.children[0].children[1] -> "Alice is on vacation"

Given a Tree where each node contains an attribute say color(R,G,B... etc). find subtree with maximum number of attributes.
Input:
G
/ \
B R
/ \ / \
B B R R
/ \ / \
B R R R

Output:

Input:
R
/ \
R R
\ / \
R R R

The best project you have worked till now.

Convert an Integer to a String.
eg 10--->"10",
2.5--->"2.5"
+10--->"+10"
-10----->"-10"
1.25e-7--->0.000000125

Given n line segments, find if any two segments intersect
http://www.geeksforgeeks.org/given-a-set-of-line-segments-find-if-any-two-segments-intersect/

Congrats on aonecode.com member V.S. on the offer from Microsoft and thanks for sharing with us the experience.

Coding Question 1 - Find all the paths between two nodes

Coding question 2 : Max sum in adjacent sub array

Design Question - Design a ticketing System

Design Question 2 - Design a system which allows multiple agents to read different data from same tables. Latency should be low. Algorithm should rank agents through some logic and assigned work according to that so that each agents are reading different set of rows from same table. Scale it for 20 million active agents .

Follow up - If Data Sharding is allowed, what will be the Shard Id and how the partition will look like? How your system will respond if there are agents which are also writing at same time. Consistency should be given high preference over availability.

Looking for coaching on interview prep?
Visit AONECODE.COM for ONE-TO-ONE private lessons by FB, Google and Uber engineers!

Customized course covers
System Design (for candidates of FB, LinkedIn, AMZ, Google & Uber etc)
Algorithms (DP, Greedy, Graph etc. every aspect you need in a coding interview & Clean Coding)
Interview questions sorted by companies
Mock Interviews

Our members got into G, U, FB, Amazon, LinkedIn, MS and other top-tier companies after weeks of training.

Feel free to email us aonecoding@gmail.com with any questions. Thanks!

3. Complete the following function-

Node * alternateReverse( Node* head1, Node*head2){
// code goes here
}
Where ‘Node’ is the structure of a linked list node defined as:

struct Node{
int data;
struct Node *next;
};
alternateReverse() must remove the even number nodes from the linked list and append them to the end in reverse order. No extra space was allowed. It was for 5 marks.
Example:

Input-1->2->3->4->5->6
Output-1->3->5->6->4->2

Input-1->2->3->4->5->6->7->8->9
Output-1->3->5->7->9->8->6->4->2

What is the Big O of that algorithm? What happens at runtime?

What's the algorithm to transform the sentence "the brown fox ran fast" in "eht nworb xof nar tsaf" (reverse any word)

Write a program to shuffle a deck of card?

Suppose you have a stock broker events that send events whenever there is an event occurs, like buy, sell etc.
There are apps that needs gets these data from the events application, not all application needs all the functions.
There is broker interface that is a link between the apps and the stock application. How will you design the classes, methods etc.

Supposed you have a sorted array, that was rotated like [2 4 6 7 8] => [7 8 2 4 6]. How will find an element in the array.

Consider a social networking site, where in each user has a number of contacts, how will you find the shortest path between 2 users who are not connected.