CareerCup

Design a Fresh Grocery System. Means Daily usable Items, you cannot store them in inventory like bread, milk etc.
HLD+ DB Schema + Concurrency issues + Scalable architecture. How will you scale to multiple countries

How to develop a web based multiplayer chess game. There will be 2 player in each session. There will be multiple sessions.

My answer(I was not selected)
Each player will have a database with columns
user id(primary key), passwd,no of games played, won,drawn,last active time,sq1,sq2,...sq64,move made flag,pawn num, sqstart,sqend
where sq1-denotes square 1 and its value represents the pawn num in sq1
question- what all fields in database will be encrypted
answer-passwd
question- why not others
answer-may be system admin needs to access them
question – how will u start a session between players?
Answer-When a player logs in, his last active time is updated. Each player is shown a list of last active players to chose from.Or system can arbitrarily select one.When a player is selected, he gets a request. Each player receives a list of requests from other players. He choses from one. That player gets an acknowledgement others get negative acknowledgement. If acknowledgement does not come in time then that player is dropped and another player is selected.
Question- http connection, can not send request from server. How the 2 players will send request to each other and how session will be initiated?
Question-how the game will be stored?
The 64 squares sq1,sq2,..sq64 will each store the pawn number in them. From random number calculatio, it will be decided which one is white and which one is black 1st time. When a player makes move,has made move flag will be true. The last move is stored as sqstart,sqend,pawn number. Each time a move is made check for valid move.The other player continuously polls for has made move flag to know if it is his turn
remarks- ur design is not scalable.

You are given a Log that contains UserId, ProcessId, Start Time, End Time and Resource Consumption during that time, you need to find out the user who has utilized the most resources.

Example:

UID    PID    StartTime    EndTime     Consumption

1        1        200       300             100

2        2        230       340             80

1        3        245       315             50

1        4        305       330             20

Time 200 signifies: 02:00.


Output: UID# 1
UserID 1 because he has consumed the most number of resources between 200 to 315 (Resource Consumption: 150).

Design an order tracking system using the below constraints.

Once an order is received, it will be assigned to a delivery boy and sends notification at every stage of the order such as order received with expected time of delivery, delivery boy assigned, order picked up, order delivered.

State how your design will help scale and what will be the performance SLAs that will you will set for your design. The system should be able to horizontally scalable from hundreds of orders to million orders and should perform at almost the same level irrespective of the number of orders received.

Add a digit to a number that is represented by a linked list, where each node is a digit of the number. The linked list couldn’t be modified, except the digits to be modified in answer and the number could be infinitely long. Need to do it in O(1) space.

Find the Minimum length Unsorted Subarray, sorting which makes the complete array sorted

Maximum difference between node and its ancestor in Binary Tree in O(n) time.

Given MxN binary matrix, find the largest sub-square matrix with all 1’s.

Design a geographically partitioned multi-player card game, that supports multiple players, multiple games at a time.
Each game will have one contractor like ones we have in a bar, He can play a game or just watch it. Integrate payment systems.
First HLD was required, use cases, flow diagram. then a low level design was required all necessary classes where will you use polymorphism, where inheritance, multithreading, synchronised approach if needed, socket connections

Design a Netflix type system. Start from HLD to LLD.
Consider requirements like search, video serving, authentication, security, serving multi quality video.

Given an array of integers. We need to answer two types of queries point update and range sum in minimum time.

Put the given random pointers in linkedlist to point to next greater node such that if you transverse the list using random pointers, list become sorted. duplicates are allowed.

Find third highest value in a binary tree

You are given a set of N horizontal lines which are connected by equal number of vertical lines to form squares of size 1x1. Now some segments are removed. You need to count the number of squares of all sizes (1x1, 2x2, ..., NxN) with all sides present.

Image : https://he-s3.s3.amazonaws.com/media/uploads/1ce3516.png

In the above example you see four horizontal and vertical lines and few missing segments. Now you need to count the number of squares of all sizes with all sides.


Input :

First line is a positive integer N, number of horizontal and vertical lines.

Second line is positive integer M, number of segments removed.

Then there are m lines, each containing V,i,j or H,i,j where i and j are positive integers. H,i,j indicates a horizontal missing segment in the ith horizontal line between the jth and (j+1)th point on the line. V,i,j represents a gap in ith vertical line between the jth and (j+1)th point on the line.


Output :

Is the total number of squares in the figure with all sides along the remaining lines in the figure.


Sample Input :
4
4
H,2,1
H,3,1
V,2,2
V,2,3

Output :
5


Explanation : Here in this figure we have 4 squares of size 1x1 and 1 square of size 3x3, hence total is 5.

Given data of millions of people, (name, age, M/F etc.) Develop an API that will have age range as input and yield the count of people under this range as output.

A T20 match is going on. You’re in Team B. First innings is over, they have scored “teamARuns” runs. Your team has scored “teamBRuns” runs at the end of “balls” balls. A ball can have multiple possibilities like [0, 1, 2, 3, 4, 5, 6, Wicket, No ball, Wide ball]. What is the probability that your team (Team B) will win?

Given a dictionary of words and a string pattern. Output the count of words that match the string pattern in the dictionary.
Eg. Dictionary: [cat, rat, mat, apple, boy, bat]
String pattern: ?at
Output: 4 (because cat, rat, mat, bat matches the string pattern)

Given any two nodes in a binary tree, find the path from 1st node to another, and tell if the path is a straight line, or there are turns on the line, find number of turns.

Find the maximum difference between any combination of child and parent node in a given binary tree. Here child node can be any level below parent node, but should be in the same sub tree starting from parent node.

Design Truecaller. Both HLD and LLD.

Given a chessboard, find minimum number of moves for a knight to reach from source to destination.

Given a fully connected graph with n nodes and corresponding values. One node can interact with other node at a time, to replace/ignore/add its value to other node’s value. Assuming this operation takes 1 unit of time, how much time would it take for all the nodes to have value equal to sum of all the nodes.
Examples : Given a graph with values {1,2,3,4}, find total time it takes, such that all nodes have value as 10.

Given a Singly Linked list, Update the second half of the list such that n-th element becomes sum(1st + nth) element, (n-1)st element becomes sum(2nd + n-1st) element and so on. Eg: 2->3->4->5->6 => 2->3->(4+4)->(5+3)->(6+2)

Given an Infinite stream of strings as AAAAABBBCCDDDEEE… How will you arrange characters so that string become unique without duplicates .

Return true if it is possible to arrange else return -1.

Ex . AAABBCCDEF – O/p ABABCDCEF : Possible . AAAAAAAAAAAAAAAAAAAAAAB : Not possible

Given an array of integers, replace every number with the next higher number to its right. If a number can’t be replaced, we leave it as-it is.
For example, the list: 5, 2, 1, 4, 6, 7 needs to be changed to 6, 4, 4, 6, 7, 7.

Given two unsorted arrays A, B. They can contain duplicates. For each element in A count elements less than or equal to it in array B

Examples:

Input : A = [1, 2, 3, 4, 7, 9]
B = [0, 1, 2, 1, 1, 4]
Output : [4, 5, 5, 6, 6, 6]

Write a logic to print the elements of 2D matrix in a spiral way?

for eg if int[][] matrix = {{1,2,3,4}{5.6,7,8}{9, 10, 11,12}};
The output should be 1 2 3 4 8 12 11 10 9 5 6 7
The interviewer asked me to implement a recursive algorithm.

Given a continuous stream of numbers, write a logic to find k maximum numbers at any given point of time where k is fixed?

Given some set of points in each quadrant of a 2D graph and two edges at a fixed angle, find the minimum angle at which the edges would cover maximum points between them?

I was confused on how to start and interviewer hinted me to consider each point at some angle from base (say 0) and continue finding all points which lies within the fixed angle.

Given a binary tree, how do you serialize and deserialize. Remember it is not BST it is a general binary tree which can also have duplicate elements.