CareerCup

It was a online coding round on software provided by samsung itself.
Given a graph print either of the set of the vertices that are colored with the same color. And if the graph is not bipartite print “-1”. Test cases also included the cases when a graph is not connected.
Note: No STL or other library functions were allowed

you are given two arrays .You have to print minimum number of swap operation to perform so that the median of two arrays are equal. if not possible then print -1.
link = https://www.hackerearth.com/practice/basic-programming/implementation/basics-of-implementation/practice-problems/algorithm/equal-median-8aba723b/

print hockey stick number in pascal triangle where row of triangle can be upto 30000 and length of stick can be upto 100.

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 ?

A car has to be given on rent. Different people come and ask for it for interval [s,e] and offer some price p. To whom shall the car be given in order to earn maximum.

write a main program to take snapshots of VMs
Input: List of VMs(vmId: String), list of SLAs -> there is one-to-one mapping from VM to SLA

class SLA {
int freq_in_mins;
}

vm1 -> sla1{30 mins}
vm2 -> sla2{60 mins}

Constraints:
1) You can use takeSnapshot(vmId: String) -> Synchronous - I/O
2) If you start a snapshot of VM(with sla1) at time t0 and if it finishes at time t1, then the next snapshot should be scheduled at t1+sla1.freq_in_mins


vm1 at 00:00 and vm2 at 00:00
00:10 and 00:15

vm1 -> 00:10 + 30 = 00:40

write a class that 1) calculates the average of the stream, 2) provides an API read the average.

Handle overflows as the numbers can be very large and not fit into double/long.

Given a string “SELECT c1,… FROM (SELECT c2,… FROM (…) WHERE c2=v2,…) WHERE c1=v1,…”, format to the following by inserting "\n" and "\t":
“SELECT
  c1,…
 FROM
  (
  SELECT
   c2,…
  FROM
   (
     …
   )
  WHERE
   c2=v2,…
  )
 WHERE
  c1=v1,…

Multi -level cache system design with different storage in each level.
Read Operation : – Minimum time to read a particular key from cache system. This should be followed by writing the key in all levels above it. Eg. if “key” is found at level ‘i’, add this key to cache present at 1 to i-1 level.

b. Write Operation: – Any write Operation should write in cache of all levels.

You can choose any algorithm for cache management like LRU, MRU.

Because Ethereum smart contracts are deployed publicly, anyone with the right tooling can read their contents.
Furthermore, people can access any state the contract specifies. Knowing that people have access to your
validation code, how do you write the contract so that somebody *must solve the problem. (*it should be near
impossible or significantly computationally expensive to derive the answer from your contract code)

Ethereum is a blockchain that can run arbitrary programs. Write an ethereum program (i.e. contract) that will send 0.1 ETH (a bounty) to the first person who gets the correct answer to the above "100-digit"
question.

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.

Given a string as input, return the list of all the patterns possible:

'1' : ['A', 'B', 'C'], 
'2' : ['D', 'E'],
'12' : ['X']
'3' : ['P', 'Q']

Example if input is '123', then output should be [ADP, ADQ, AEP, AEQ, BDP, BDQ, BEP, BEQ, CDP, CDQ, CEP, CEQ, XP, XQ]

Given a singly linked list, Your task is to remove every Kth node. The task is to complete a method deleteK that takes two argument, head of linked list and an integer k.The method returns the head of the new linked list. There are multiple test cases. For each test case, this method will be called individually.

I am surprised by this GS question.I thought this is one of the classic number theory partition problem which is so hard that the best algorithm is approximation one.

Given value, find all possible combination of ways which equals to that sum.

Google Fucked up question.

Given a random list of appointments (Start Date , End Date). Find all the appointments that are colliding.

This pretty easy looking question screwed me up today.There are tons of edge cases, I couldn't complete em all and 45 minutes pass like 15 minutes while explaining and coding same time.

Imagine a computer where you have no "/" (divide) operation. All other operations are implemented including addition, multiplication, binary shift etc. Implement function div(int a, int b) using available operators only.

I was given this question recently in an interview.. There are three threads and a counter that will increase from 1 to 100. Catch is that thread 1 increments counter from 1 to 20. Thread 2 increments from 21 to 80. Thread 3 increments from 81 to 100.

N different couple go to cinema with 2N different seats. They take their place randomly. You could make swap operations. Write a code for given input what is the minimum number of swap operations for sitting all couples with their partners? Additionally, be sure that no one swaps more than 2 times.

Given an array of sorted integers and find the closest value to the given number. Array may contain duplicate values and negative numbers.

Example : Array : 2,5,6,7,8,8,9
Target number : 5
Output : 5

Target number : 11
Output : 9

Target Number : 4
Output : 5

Write a function to convert a String of ip address to hex
eg: ip is 197.27.11.11 = 0xC51BBB. The conversion to hex has to be done without pre-existing library function. like String.format() etc.

An web service maintains logs (suppose there are multiple log files per day) of all ip address which has requested service. If there is a DOS attack on the server find all ip addresses that has sent more number of requests and block them. Can this be done without writing any function in higher programming language?

What would the function look like if written in some language like C, Java etc?

Can this be done in Time optimized and space optimized manner?

You are provided with 2D char array. You have to provide the 2D char array as response which contains the multiplication od the input array. For eg: input=> {{a,b},{c,d}}, output => {{a,c},{a,d},{b,c},{b,d}}

aa

A company's organizational structure is represented as
1: 2, 3, 4
In the above employees with id 2, 3 and 4 report to 1
Assume the following hierarchy.
1: 2, 3, 4
3: 5, 6, 7
5: 8, 9, 10
Given an employee Id, return all the employees reporting to him directly or indirectly

Given a array of integers there is one that is repeated several time. How would you compute the length of the sequence of repeated elements.
Assuming the initial array is sorted can you do better than O(n) both for spatial and temporal cost?

Implement power function. The function should take two numbers as input (e.g. 2,3) and return 8 as output

See link below for hints and answer https://baquerrizvinotes.blogspot.in/2017/05/how-to-crack-amazoncom-technical.html

You are given an array of nodes where each node consists of node name, isValid flag, and parent Node index. so, this array actually represents a tree(forest). where root node has -1 as its index for the parent node. rest all node have their parent's index value.

You will be given this array and an index. You have to cut down the subtree from the index. Cutting down a tree means, making all the nodes of that subtree false(Isvalid flag).
He was expecting O(N) solution.

You are given an array of values, (not necessary integers or positives) and a value. You have to print all the pairs whose sum is given value. Write a general method which can accept integers, float, doubles, long, or any other thing where this make sense.

A college student's record contains the following:

1. Name
2. Age
3. Subject(s)
4. Marks
5. ID

The student can choose from English, Mathematics and History as subjects. A student can choose one, two or all of the subjects.

The requirement is to search for students who have scored marks more than X in a certain subject. Which Data Structure would you use and how would you solve this problem in an optimal manner?