neer.1304
BAN USER
- 1of 1 vote
AnswersGiven a array of integers find the index which partitions the array to two with high numbers and low numbers. For example [5, -1, 3, 8,6] the index 3 will partition the array to [5,-1,3] and [8,6] all the numbers in the second partition are greater than first. The solution has to work in O(n).
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Microsoft Algorithm - 4of 4 votes
AnswersYou have an array of numbers. You have to give the range in which each number is the maximum element. For Example, If array is 1, 5, 4, 3, 6 The output would be
- neer.1304 in United States
1 [1, 1]
5 [1, 4]
4 [3, 4]
3 [4, 4]
6 [1, 5]| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswerGiven an array of billion of numbers. Billions of queries are generated with parameters as starting and an ending index. Both these indices lie within that array. Find the maximum number between these two indices in less than O(N)
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersMultiply two numbers without using * and only be using bitwise operations
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersDisplay nodes of a tree in level order using DFS
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersImplement a deque using stacks
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersGiven the entire dictionary of English words, what data structure will you use to efficiently store and match the custom regex string like "D*sk", where * represents any single alphabet, and return the list of matched words?
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswerGiven a skewed tree, an insect is sitting at the root of the tree at t = 0min, every minute insect steps down in the tree, find the probability of the insect being at any node at t = infinity. Once I came up with a solution various other complexities has been added to the problem such as: What if the tree is binary tree (written code for this) What if three is n-ary What if it is now a directed acyclic graph Handle cases that there can be more than one entry point There can be more that one way to reach a node
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersGiven a binary tree of numbers and a search number has given, find out first occurence of that number and smallest distance from root node. if you have given k search numbers find their occurence and nearest from root node in a single walk.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersGiven an array of 0s and 1s. find maximum no of consecutive 1s. If you have given chance to flip a bit to 1 such that it maximises the consecutive 1s. find out that flipped bit and after flipping that bit maximum no of consecutive 1s. Above question but you have options to flip k bits.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersDesign a system which will keep track of product and its inventory count. The service will expose two api incrCnt(int prodId, int cnt) and decrCnt(int prodId, int cnt). Which db would you use ? How will you handle hot products ?
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 Software Design - 0of 0 votes
AnswerDesign a system in which read a file which has data and operation to be performed give a line by line. Ex a=5, next line b= 10, next line a*b. This design extended to support float, doubles, boolean, vector and complex numbers. Like if the file has a=5+i8, then how you handle such scenarios. How you will store and process data.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 Software Design - 0of 0 votes
AnswersDesign database schema with entity and relations to store the family tree of a person.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Microsoft Senior Software Development Engineer Database - -4of 4 votes
AnswersGiven an integer array and an integer K, find the number of sub arrays in which all elements are less than K.
- neer.1304 in United States
Follow up -
Given an integer array and an integer K, find the number of non overlapping unordered pairs of sub arrays in which all elements are less than K.| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 0of 0 votes
AnswersDesign a low level design and db schema for railway reservation system for supporting following 2 features -
- neer.1304 in United States
1) User would give source city, destination city and date as input and would get the list of trains matching the criteria.
2) On selection of a train from the list user should be able to see the schedule of the train including the arrival time, departure time and station name.| Report Duplicate | Flag | PURGE
Microsoft Senior Software Development Engineer design - 0of 0 votes
AnswersDesign a distributed key-value store that can perform the following
- neer.1304 in United States
Store a set of attributes (value) against a particular key (k)
Fetch the value stored against a particular key (k)
Delete a key (k)
- Perform a secondary index scan to fetch all key along with their attributes where one of the attribute values is v.
Key can have a value consisting of multiple attributes.
Each attribute will have name, type associated (primitive types - boolean, double, integer, string) & type has to be identified at run time.
Ex -
1) Key = delhi has 2 attributes ( pollution_level & population)
2) Key = jakarta has 3 attributes (latitude, longitude, pollution_level)
3) Key = bangalore has 4 attributes (extra - free_food)
4) Key = india has 2 attributes (capital & population)
5) Key = crocin has 2 attributes (category & manufacturer)
Example of Secondary index:
Get all keys (cities) where pollution_level is high. Get all medicines by manufacturer (GSK)
So, in a nutshell, value must be strongly typed when defined.
Attribute
1. Attribute is uniquely identified by its name (latitude, longitude etc.
2. Data type of the attribute is defined at the first insert. (i.e. data type of pollution_level is set when key = delhi is inserted)
3. Once data type is associated with a particular attribute, it cannot be changed.
(i.e. free_food when defined takes type = boolean, hence, any key when using the attribute - free_food must allow only boolean values on subsequent inserts/updates)
Non-functional requirements
Highly scalable - Support for high throughput with very low latency
Highly available
Shared nothing architecture i.e. Support for Multiple nodes and each node is independent & self-sufficient.
Stretch - Smart client i.e. clients being aware of available servers & makes smart routing based on that available information.| Report Duplicate | Flag | PURGE
Amazon Principal Software Engineer Computer Architecture & Low Level - 0of 0 votes
AnswersDesign twitter trending topics feature to show trending topics in past 24 hours.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-3 Computer Architecture & Low Level - 0of 0 votes
AnswersGiven two very large files – first contains Id and name, another one contains Id and address – you need to create 3rd file which will contain id, name, and address. -First, ask the clarifying questions and then tell the approach.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Microsoft Senior Software Development Engineer Algorithm - 0of 0 votes
AnswersTwo tables employee (contains name and Id) and employee details having work experience history (contains Id, fromYear, toYear) – find out all the employees who worked w/o career break.
- neer.1304 in United States
Java implementation for the same.
From the same table list the name, fromYear, toYear for all employee.
Dependency Injection.
Design patterns which can be used.| Report Duplicate | Flag | PURGE
Microsoft Senior Software Development Engineer Algorithm - 0of 0 votes
AnswersGiven a binary matrix of size M * N. You are given H and V where H denotes the number of horizontal cuts and V represents number of vertical cuts. You need to find whether you can make H and V amount of cuts such that each submatrix formed after the cuts will have equal number of 1. E.g.
- neer.1304 in United States
4 5
1 1 1 1 1
0 0 1 1 1
0 1 1 1 1
1 0 1 1 1
Given H=1 and V=3, we can make 1st horizontal cut after 2nd row and 3 vertical cuts after 2nd, 3rd and 4th column such that each of the sub matrix will have equal number of 1s.
| ----------------|
| 1 1 | 1 | 1 | 1 |
| 0 0 | 1 | 1 | 1 |
| ----------------|
| 0 1 | 1 | 1 | 1 |
| 1 0 | 1 | 1 | 1 |
| ----------------|| Report Duplicate | Flag | PURGE
Amazon SDE-3 Algorithm - 0of 0 votes
AnswersGiven a remote having 0-9 digits, plus button (to increase channel), minus (to decrease) and previous channel button (to go to previous channel). We were given 2 numbers stating start and end channel number and an array having various channel numbers. The task is to go to all channel numbers given in array with minimum number of clicks.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-3 Algorithm - 0of 0 votes
AnswersYou are given 2 arrays: one representing the time people arrive at a door and other representing the direction they want to go(in or out) You have to find at what time each person will use the door provided no 2 people can use the door at the same time. Constraints: the door starts with ‘in’ position, in case of a conflict(2 or more people trying to use the door at the same time), the direction previously used holds precedence. If there is no conflict whoever comes first uses the door. Also if no one uses the door, it reverts back to the starting ‘in’ position. Should be linear time complexity.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersImplement auto complete for IDE, you will be given strings of classes and input, input can be like MVC, MoClick, MouseClickHand
- neer.1304 in United States
For MouseClickH => MouseClickHandler
MVC => can match to any classes where first word starts from M then V then C| Report Duplicate | Flag | PURGE
Pinterest Software Engineer / Developer Algorithm - 0of 0 votes
AnswerMake a system that returns the average number of hits on the site per minute from the past 5 minutes
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Indeed SDE-2 Software Design - 0of 0 votes
AnswersDesign distributed crawling system which would be feeded a source url.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-3 Distributed Computing - 1of 1 vote
AnswersGiven a binary matrix of 0 and 1 where we can move in 4 directions left, right, top, down and we can only pass through 1's. Find the shortest path from given source coordinate (a,b) to destination (m,n) given we can flip any one of the zero to one.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-3 Algorithm - 0of 0 votes
AnswersYou're running a pool of servers where the servers are
- neer.1304 in United States
numbered sequentially starting from 1. Over time, any
given server might explode, in which case its server
number is made available for reuse. When a new
server is launched, it should be given the lowest available number.
Write a function which, given the list of currently
allocated server numbers, returns the number of the next server to allocate.
For example, your function should behave something like the following:
>> next_server_number([5, 3, 1])
2
>> next_server_number([5, 4, 1, 2])
3
>> next_server_number([3, 2, 1])
4
>> next_server_number([2, 3])
1
>> next_server_number([])
1
Server names consist of an alphabetic host type (e.g. "apibox") concatenated with the server number,
with server numbers allocated as before (so "apibox1",
"apibox2", etc. are valid hostnames).
Write a name tracking class with two operations,
allocate(host_type) and deallocate(hostname).
The former should reserve and return the next
available hostname, while the latter should release
that hostname back into the pool.
# For example:
#
# >> tracker = Tracker.new()
# >> tracker.allocate("apibox")
# "apibox1"
# >> tracker.allocate("apibox")
# "apibox2"
# >> tracker.deallocate("apibox1")
# nil
# >> tracker.allocate("apibox")
# "apibox1"
# >> tracker.allocate("sitebox")
# "sitebox1"| Report Duplicate | Flag | PURGE
Stripe Software Engineer Algorithm - 1of 1 vote
AnswersUse synchronized, wait() and notify() to write a program such that below mentioned conditions are fulfilled while reading and writing data to a shared resource.
- neer.1304 in United States
When a write is happening, no read or other write should be allowed(read and write threads should wait)
When a read is happening, no write should be allowed (write threads should wait) but. other read threads should be able to read.
Donot use any API classes e.g. ReadWriteLock, AtomicInteger etc..| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Java - 0of 0 votes
AnswersDesign election voting system. Election would be country wide. System should be scalable, available and consistent.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 Software Design - 0of 0 votes
AnswersImplement following method of ScheduledExecutorService interface in Java
- neer.1304 in United States
schedule(Runnable command, long delay, TimeUnit unit)
Creates and executes a one-shot action that becomes enabled after the given delay.
scheduleAtFixedRate(Runnable command, long initialDelay, long period, TimeUnit unit)
Creates and executes a periodic action that becomes enabled first after the given initial delay, and subsequently with the given period; that is executions will commence after initialDelay then initialDelay+period, then initialDelay + 2 * period, and so on.
scheduleWithFixedDelay(Runnable command, long initialDelay, long delay, TimeUnit unit)
Creates and executes a periodic action that becomes enabled first after the given initial delay, and subsequently with the given delay between the termination of one execution and the commencement of the next.| Report Duplicate | Flag | PURGE
Uber SDE-2 Algorithm - 0of 0 votes
AnswersImplement BST Iterator and use them in 2 sum and 3 sums problem on a BST
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Rubrik - 0of 0 votes
AnswersImplement a rate limiter that multiple threads can use, while the global rate is limited to a value
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Rubrik Coding - 0of 0 votes
AnswersImplement a thread-safe data structure which can keep track of number of incoming
- neer.1304 in United States
requests grouped by IP Address over a time window. Add support for grouping by other
attributes such as BrowserAgent.| Report Duplicate | Flag | PURGE
Rubrik Algorithm - 0of 0 votes
AnswersGiven a string select two non-overlapping strings that are same and remove them. Perform this operation recursively till there are no desired strings.
- neer.1304 in United States
Print the number of possible substring after completing above operation.
Ex - abcc
Duplicate non-overlapping substring - abc
After removing abc from we are left with 1 substring abc.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersIn a 2-D matrix of m*n select m-1 elements from each row such that that the resulting sum is minimum and each column is selected atleast once.
- neer.1304 in United States
Ex -
2 3 5
3 2 5
4 4 7
Selecting (2,3) from 1st row, (2,5) from 2nd row and (4,4) from 3rd row would result in minimum sum of 20| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersFind LCA for list of nodes of a tree
- neer.1304 in United States
Function defined as below -
TreeNode findLCA(TreeNode root, List<TreeNode> nodes)| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswerDesign DB schema for maintaining e-commerce various category ,sub category ,sub-sub category and so on.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Boomerang Commerce Database - 0of 0 votes
AnswersWrite a program to find number of words in a file not using any standard tokenizing API's.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Boomerang Commerce Algorithm - 0of 0 votes
AnswersGiven n, you will be getting stream of sets each set may contain like (1,3,4,5) which signifies that 1,3,4,5 are related. Similarly you may get like (6,7) , (1,8).
- neer.1304 in United States
And you will be asked to find whether 1 & 4 are related => Yes (as they are from same set).
3 & 8 are related => yes as 8 & 3 are related through 1.
5 & 7 are related =>No| Report Duplicate | Flag | PURGE
Boomerang Commerce Algorithm - 0of 0 votes
AnswersImplement a fair mutex
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Nutanix MTS System Design - 0of 0 votes
AnswersAn array is called a Good Array if the elements continually increasing or continually decreasing or continually decrease and then increase.
- neer.1304 in United States
Question 1: He asked how will you tell whether a given array is a good array or not.
Question 2: Given an array, you are allowed to add any number of values to each of the element. Find the minimum sum of elements that can make the array a good array.| Report Duplicate | Flag | PURGE
Nutanix Algorithm - 0of 0 votes
AnswersA software-based LRU Cache replacement algorithm has to be implemented for a Single Touch/Multi-Touch Cache. Single Touch can occupy at least 30% of the total cache space. A key accessed for the first time will appear in the Single Touch cache. When accessed multiple times, this will be part of the multi-touch cache. Also, multiple threads will access the cache. Following are the functions allowed for cache access.
- neer.1304 in United States
1. get(key): returns the value against the key if present else return NULL
2. set(key, value): set the value against the key| Report Duplicate | Flag | PURGE
Nutanix Algorithm - 0of 0 votes
AnswersGiven a tree, and there will be treasure in one of the nodes. We can query any node, it will return the node itself if it contains the treasure or it returns the branch which leads to the treasure. we need to find out the treasure in minimum number of queries.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Nutanix Algorithm - 0of 0 votes
AnswersDesign a jenkins kind of system
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Nutanix Software Design - 0of 0 votes
AnswerImagine someone maliciously duplicated every file on your computer, and completely randomized their names and locations on your hard drive. Discuss an efficient way to clean up your drive of all these duplicates.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Nutanix Algorithm - 1of 1 vote
AnswersDesign real time tail log search
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Rubrik MTS Distributed Computing - 1of 1 vote
AnswersBuild a key-value data structure that allows the user to take a snapshot of the data. The user can read the key-value store from any snapshot.
- neer.1304 in United States
Structure has the normal key/value like methods plus something like
snapshot = dataStructure.takeSnapshot()
value = dataStructure.get(key, snapshot)
void dataStructure.deleteSnapshot()| Report Duplicate | Flag | PURGE
Rubrik MTS Algorithm - 0of 0 votes
AnswersA table has some number of balls at various positions on a line segment. All are moving with same speed in one or the other direction. Wherever a collision occurs they change direction. A ball falls from the edges of the table. Find the time when all balls fall of the table given initial position of each ball and speeds
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Rubrik MTS Algorithm - 1of 1 vote
AnswersGiven a list L of video names and their watch rates, write a function that will return the videos with the top 10 watch rates. Video names may appear more than once.
- neer.1304 in United States
Example:
L = [(‘abc’, 10), (‘def’, 15), (‘ghi’, 10), (‘abc’, 12), …, (‘xyz’, 100)]
The function should return [‘xyz’, ‘abc’, …, ‘def’, ‘ghi’]| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 3of 3 votes
AnswersWrite a function that takes a list L and returns a random sublist of size N of that list. Assume that the indexes must be in increasing order. That is, you cannot go backwards.
- neer.1304 in United States
Example:
L = [1, 2, 3, 4, 5]
N = 3
The function should return one of these lists:
[1, 2, 3]
[1, 2, 4]
[1, 2, 5]
[1, 3, 4]
[1, 3, 5]
[1, 4, 5]
[2, 3, 4]
[2, 3, 5]
[2, 4, 5]
[3, 4, 5]| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersConsider an undirected tree with N nodes, numbered from 1 to N. Each node has a label associated with it, which is an integer value. Different nodes can have the same label. Write a function that, given a zero indexed array A of length N, where A[j] is the label value of the (j + 1)-th node in the tree and a zero-indexed array E of length K = (N – 1) * 2 in which the edges of the tree are described, returns the length of the longest path such that all the nodes on that path have the same label. The length is the number of edges in that path.
- neer.1304 in United States
Example:
A = [1, 1, 1, 2, 2]
E = [1, 2, 1, 3, 2, 4, 2, 5]
This tree is shown below. A node follows the form label, value.
----------1, 1
-----1, 2 1, 3
2, 4 2, 5
The function should return 2, because the longest path is 2->1->3, and there are 2 edges in this path.
Assume that 1 <= N <= 1000 and each element of the array A is an integer in the range [1, 1000000000].| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswersGiven a string A consisting of n characters and a string B consisting of m characters, write a function that will return the number of times A must be stated such that B is a substring of the repeated A. If B can never be a substring, return -1.
- neer.1304 in United States
Example:
A = ‘abcd’
B = ‘cdabcdab’
The function should return 3 because after stating A 3 times, getting ‘abcdabcdabcd’, B is now a substring of A.
You can assume that n and m are integers in the range [1, 1000].| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersGiven 1-D list of co-ordinates determine if interval (a,b) is covered
- neer.1304 in United States
Ex - [(2,5), (5,7),(1,4)] and interval = (1,6)
return true
Explanation - Points 1 to 6 lies in list of interval given 1 to 4. 2 to 5 and 5 to 7.
[(1,4),(6,7),(2,5)] and interval - (1,6)
return false
Explanation - Distance between 5 to 6 is not covered in the list given so return false| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswerCompare two documents(string array) based on n grams.
- neer.1304 in United States
e.g doc1 – Today is Sunday.
doc2 – Today is Saturday
if n = 2 then number of duplicates is 1 (Today is)
if n = 1 then number of duplicates is (Today, is)
if n = 3 duplicates is 0| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersGiven a room with thief on left side of the room with finite number of sensors. He has to reach on right side missing the sensors. Each sensor is placed at any random point in the room and has its coverage in the radius r. Find out if the thief can reach to the right side without touching the range of any sensor.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswersGiven an infinite chessboard, find minimum no. of steps for a knight to reach from the origin to (x, y).
- neer.1304 in United States
Extension A list of forbidden coordinates are introduced where knight can’t reach. Handle this in your code. Make sure the infinite loop is handled since the board is infinite.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersGiven a matrix of people(denoted by small alphabets) and bikes(denoted by capital alphabets), find the nearest bike for a given person.
- neer.1304 in United States
How will you change your solution if you have to find bikes for a set of people? (assuming multiple bikes can be at the same distance from 1 person)| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersGiven an array of n integers, find the lexicographically smallest subsequence of length k.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersGiven a list of player names and their scores – {Carl, 70; Alex, 55; Isla, 40}, design a data structure that can support following modules in optimal time-
- neer.1304 in United States
i) updateEntry(string name)
ii) getEntryFromRank(int rank)| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersGiven an input stream of boolean values, design a data structure that can support following modules in optimal time-
- neer.1304 in United States
i) setTrue(index)
ii) setFalse(index)
iii) setAllTrue()
iv) setAllFalse()
v) getIndex(index)| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswerGiven two strings, A and B, of equal length, find whether it is possible to cut both strings at a common point such that the first part of A and the second part of B form a palindrome.
- neer.1304 in United States
Extension1. How would you change your solution if the strings could be cut at any point (not just a common point)?
Extension2. Multiple cuts in the strings (substrings to form a palindrome)? Form a palindrome using a substring from both strings. What is its time complexity?| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswerGiven a stream of integers, a value k and a value w, consider the integers in the window w and chop off greater k and smaller k elements from the window w. From the remaining elements, compute the average.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersImplement the version control map system which takes the snapshot of the versions of data. Implement the following functions:
- neer.1304 in United States
put(key, value) -> puts the value again the key in the latest version of the map
get(key) -> get the value of the key for the latest version of the data
snapshot() -> take a snapshot and increment the version
getValVersion(version id, key) -> return value of the key of the particular version| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersA graph has N vertices numbered from 1 to N. We have two lists. One list M consisted of edges between vertices. The other list K consists of restricted paths. We have to add edges one by one from M and check whether the addition of the particular edge leads to a path between the restricted edges given in K. If it creates a path, we have to discard the edge.
- neer.1304 in United States
Example: N = 4; K = {(1, 4)}; M = {(1, 2), (2, 3), (3, 4)}. Here, addition of edge (3, 4) will create a path between 1 and 4. Hence we discard edge (3, 4)| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - -1of 1 vote
AnswersYou are given 2 strings which are exactly same but 1 string has an extra character. Find that character.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswerYou are given an array of million numbers and provided a range of index (say left, right). For multiple queries, each with input left and right indexes, output the maximum in that range.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersGiven (x, y) coordinates, create a function such that each coordinate is uniquely mapped to an integer. Also make sure that given an integer, you should be able to find (x, y) coordinates. So F(x, y) = z and also that inverse F(z) = (x, y).
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswersWe have to paint n boards of length {A1, A2…An}. There are k painters available and each takes 1 unit time to paint 1 unit of board. The problem is to find the minimum time to get
- neer.1304 in United States
this job done under the constraints that any painter will only paint continuous sections of boards, say board {2, 3, 4} or only board {1} or nothing but not board {2, 4, 5}.
Input : k = 2, A = {10, 10, 10, 10}
Output : 20.
Here we can divide the boards into 2
equal sized partitions, so each painter
gets 20 units of board and the total
time taken is 20.
Input : k = 2, A = {10, 20, 30, 40}
Output : 60.
Here we can divide first 3 boards for
one painter and the last board for
second painter.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersP0, P1, ...., Pn players in tournament. In first level, P0 plays with P1, P2 plays with P3 and so on. In level 2, Winner of P0,P1 plays with winner of P2,P3. For i,j output level in which they will face each other assuming they win all games.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Curefit SDE-2 Algorithm - 0of 0 votes
AnswersGiven multiple tuples in the form of (A,B) where A is the parent and B is the child in a binary tree, find if the input is valid or not. 4 error conditions were provided:
- neer.1304 in United States
1. If a parent has more than 2 children,
2. If duplicate tuples entered,
3. If the tree has a cycle,
4. If more than one root possible.
For violation of multiple validity conditions, print the condition coming first in the above order.
If the input is valid, print the tree in a serial representation. For eg: If input is (A,B), (B,C), (A,D), (C,E) , output: (A(B(C(E)))(D))| Report Duplicate | Flag | PURGE
Swiggy SDE-3 Algorithm - 0of 0 votes
AnswersDesign a catalog system – Restaurants, Items, Categories, VariantGroups like Size, Variants like (S,M,L), AddOnGroups like Extra cheese, AddOns like White Cheese, Yellow Cheese. Price of item will vary on variant selected and even addon price will vary on variant selected.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Swiggy SDE-3 Software Design - 1of 1 vote
AnswersDesign Flipkart Flash sale architecture. 2 million hits and 20k orders in 2 sec.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Swiggy SDE-3 Software Design - 0of 0 votes
AnswersGiven character a-z find out nth permutation. Where all permutation are only ascending. For e.g
- neer.1304 in United States
Given characters a,b,c. valid permutations are : a,b,c,aa,ab,ac,bb,bc,cc,aaa,aab,aac,abb,acc,baa,bab,bac,bbb,bbc,bcc,caa,cab,cac,cbb,cbc,ccc
Ex- 4th permutation is : aa| Report Duplicate | Flag | PURGE
Swiggy SDE-3 Algorithm - 0of 0 votes
AnswersGiven customer Geo Location(Lat-Long) and List of Restaurants. Each restaurant consist of :
- neer.1304 in United States
- Lat long of restaurant
- Name
- List of Items, where each item has
- Item Name
- Prep Time
- Sensitivity ( Low, Medium, High). Lower sensitive items like Icecream cannot be delivered more than 2 KM.
- Find out List of Restaurant Given Customer and Cart is Empty
- Find out SLA(Time to deliver) given cart, restaurant and Cutomer
- Parameters should be Configurable like Sensitivity, Max prep time etc| Report Duplicate | Flag | PURGE
Swiggy SDE-3 design - 0of 0 votes
AnswersUse the location data getting generated from multiple delivery boys moving on the ground to estimate time which a delivery boy will take to move from point A to point B in an area. Additionally, try to do this in real time so that it can be used in assigning delivery boys and minimising delivery time in real time.
- neer.1304 in India| Report Duplicate | Flag | PURGE
Swiggy SDE-2 design - 0of 0 votes
AnswerYou are given an N-Dimensional list with 2 methods:
- neer.1304 in United States
i) getDim -> returns the dimensions .e.g [5,4,3].
ii) getElement([i,j,k]) -> return list[i][j][k] . You have to implement a method to sum all elements in the list.| Report Duplicate | Flag | PURGE
Linkedin Senior Software Development Engineer Algorithm - 0of 0 votes
AnswersGiven a list of files. Return all the unique lines from all files.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswerGiven a set of points, find the smallest rectangle by area.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersGiven N shop coordinates on a 2-d plane, Find the nearest shop from a man whose coordinates are given.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersGive you a text file, remove duplicated lines.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersGiven movement of Robot -
- neer.1304 in United States
G-GO one unit
L-Turn left
R-Turn right
Given an input of string have to find whether there exists a circle which the robot would traverse. Input of string is the set of G,L,R have to return yes or no.| Report Duplicate | Flag | PURGE
Flipkart SDE-2 Algorithm - 1of 1 vote
AnswersGiven a list of strings. Check whether any two strings, if concatenated will form palindrome or not.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Flipkart SDE-2 Algorithm - 0of 0 votes
AnswerThere is a hierarchical structure in an organization. A party is to be organized. No two immediate subordinates can come to the party. A profit is associated with every person. You have to maximize the total profit of all the persons who come to the party.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Flipkart SDE-2 Algorithm - 0of 0 votes
AnswersDesign a vending machine with following functionalities
- neer.1304 in United States
Three types of Users : User, Operator, Admin
User can select and buy multiple items at a time. Money can be inputted multiple times (you will get the item if there is a time gap > 30 secs). He can also do window shopping (see only the prices of items and buy nothing)
Operator can load the items and mark the items as expired if needed, gets notified if a product goes out of stock.
Admin can own multiple vending machines, he should have a analytics report of the items purchased in a month. He can also change the prices directly and it should reflect in all the vending machines which he owns.
Exception handling in all the edge cases
Both HLD and LLD were expected.| Report Duplicate | Flag | PURGE
Amazon SDE-2 System Design - 0of 0 votes
AnswerYou have been given a set of inter-dependent tasks along with the time taken to execute them. We have more number of parallel processors available than the number of tasks given. There could be multiple starting tasks. There could also be cyclic dependencies. Calculate the minimum time required to complete all the task.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersImplement an api that let's users create multiple timers. You can only use one system timer in your implementation though. For example a user can write:
- neer.1304 in United States
timer.startTimer(3, callback)
timer.startTimer(7, callback)
timer.startTimer(1, callback)
and the user will get three callbacks 1, 3, and 7 seconds later. In startTimer you only have one timer that you call like this:
System.startTimer(seconds, callback)
but it can only be called once it has finished with the previous timer.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersGiven a rectangle with width 'W' and height 'H', you have to fit a string 'S' in it with maximum possible font size
- neer.1304 in United States
The font size ranges from 1 to 30
You are given two APIs getCharacterWidth(char c , int font_size) and getCharacterHeight(int font_size)
getCharacterWidth(char c , int font_size): returns the width of a character for a particular font size
getCharacterHeight(int font_size): returns the height of characters for a particular font size| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 0of 0 votes
AnswerHow will you implement organizational chart? Implement two methods - isPeer - Should return true if two employees have same managers. isManager - should return true if manager is management chain of given employee.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Google SDE-2 Algorithm - 0of 0 votes
AnswersRelation between 2 animals is given. A is child of B C is child of B A is child of D
- neer.1304 in United States
An animal can be child of 0 to 2 parents. With this given data, find out if two animals are related to each other. Follow up question was - Maternal side animals, should not be related to patrernal side family.| Report Duplicate | Flag | PURGE
Google SDE-2 Algorithm - 2of 2 votes
AnswersYou have a 3x3 grid. In each cell you can have two colors, white or black. At the beginning, the matrix has some cells painted white and others black.
- neer.1304 in United States
If you change a color cell, that is, grid [i] [j] the cells grid [i-1] [j], grid [i + 1] [j], grid [i] [j-1] and grid [ i] [j + 1] also change (if these positions do not leave the 3x3 grid), that is, if they were white, they change to black.
Return, the minimum number of cells you have to flip for the 3x3 grid to be totally white. If you cannot do this, return -1!
Sample input/output - ibb.co/3Y0WVNR| Report Duplicate | Flag | PURGE
Google SDE-2 Algorithm - 0of 0 votes
AnswersYou have a database table that stores information about the price change of various product with time. It's append only table. Whenever the price of the product p1 is changed to c1 at time t1, a new row will be appended.
- neer.1304 in United States
product_id price time
p1 10 4
p2 40 4
p1 20 5
p1 25 6
p2 55 7
...
Write an SQL query that will give the price of every product at time t1.
e.g. at time 6
product_id price
p1 25
p2 40
Note: Consider the case where two updates are made at the same time. Don't assume that the table is sorted by time.| Report Duplicate | Flag | PURGE
Walmart Labs SDE-3 SQL - 0of 0 votes
AnswersDesign payments system like Google Pay or Paytm.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Uber SDE-3 System Design - 0of 0 votes
AnswersDesign QR code system for a grocery shop.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Uber SDE-3 System Design - 0of 0 votes
AnswerDesign a Notification Service. Notification can be sent to multiple devices.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Uber SDE-3 System Design - 0of 0 votes
AnswersDesign a job workflow system wherein a job is defined as sequence of steps. This system will take jobs and execute as per the steps in job. The steps can be conditional(if this then do this else do that). This system should be able to handle multiple jobs, should be fault tolerant etc
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Uber SDE-3 System Design - 0of 0 votes
AnswersDesign and implement a Message broker which can handle high throughput and is fault tolerant.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Uber SDE-3 System Design - 0of 0 votes
AnswersDesign a workflow system. You need to implement pause/continue operations of the workflow using your database. Essentially, the interviewer was looking completely manage workflow system using database.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Uber SDE-3 System Design - 0of 0 votes
AnswersDesign a finite state machine
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Uber SDE-3 System Design - 0of 0 votes
AnswerDesign slack like collaboration tool
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Uber SDE-3 System Design - 1of 1 vote
AnswersThere is a notepad which accepts only four operations:
- neer.1304 in United States
1. Character X
2. select all
3. copy
4. paste
Given n number of operations, provide the sequence of choices that gives maximum characters in the notepad.| Report Duplicate | Flag | PURGE
Uber SDE-3 Algorithm - 0of 0 votes
AnswersGiven two async streams -
- neer.1304 in United States
Trip : {tripId, date, city}
Bill: {billId, tripId, date, amount}
Design a system to get real time aggregated view of following nature
City, TripCount, TotalAmount
Events in both streams can be out of sync or duplicate. But result needs to be accurate and realtime.| Report Duplicate | Flag | PURGE
Uber SDE-3 System Design - 0of 0 votes
AnswersDesign a log4j style logging library for a high throughput multi threaded application.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Uber SDE-3 System Design - 1of 1 vote
AnswersParking lot problem: Given 3-dimensional parking lot, lets say, length width and floor. Implement following two methods: void unpark(int i, int j, int k); where i, j, k are the parking coordinates. void park(); The car should be parked in empty cell with lowest floor and between length and breadth prefer minimum length.Example, (3, 4, 2) is preferred over (1, 1, 3) as floor is 2 in first case. (1, 2, 3) is preferred over (2, 1, 3). (2, 3, 3) is preferred over (2, 4, 3).
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-3 System Design - -1of 1 vote
AnswersLLD for third party delivery vendor for registration and notification system.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-3 System Design - 0of 0 votes
AnswersYou are given many files of 6 GB, each having stream of integers. You have space of 4 GB left in your main memory (mainly to swap out, swap in). You have to store sorted sequence of integers in all file in a other output file. How will you do that?
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-3 System Design - 0of 0 votes
AnswersDesign an authentication using AWS services like Api gateway and lambda.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-3 System Design - 0of 0 votes
AnswersDesign an online chess game.
- neer.1304 in United States
It supports 3 mode:
Player vs. AI
Player vs. player (Offline)
Player vs, player (Online)
The questions asked were how will you assign a player to another player who wants to play. You need to think about how to divide your players into multiple groups of ratings, so that a newbie is not playing a grand master, rather with someone who is of his level only. Then the question was how will you design your system when a player comes in and say I want to play, and the max wait time is 1 min, you need to find a player suitable for his level| Report Duplicate | Flag | PURGE
Amazon SDE-3 System Design - 0of 0 votes
AnswersDesign subscription based sports website which can display scores, game status, history for any games hld and lld
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-3 design - 0of 0 votes
AnswersConsider an infinite stream of numbers. At any point print smallest k elements.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-3 Algorithm - 0of 0 votes
AnswersThere is a huge road. Given are the following
- neer.1304 in United States
- Array D that stores the distance from a starting point where billboard can be installed.
- Array C that stores the profit. C[i] -> profit if the billboard is installed at distance D[i].
- dist -> minimum distance to maintain between the billboards.
Assume you can install any number of billboards while maintaining a given minimum distance 'dist' between each of them. Find the maximum profit you can achieve.| Report Duplicate | Flag | PURGE
Amazon SDE-3 Algorithm - 0of 0 votes
AnswersDesign an airport service that will be used to allocate a free runway when the plane is about to land. Data structure for the same. What if the runway is not available? Message passing between control centre and the plane. Focus on low-level design and code. Can the same runway be alloted to two different planes (locking)? Database storage needed?
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-3 design - 0of 0 votes
AnswerA thief trying to escape from a jail has to cross ‘N’ walls each with varying heights. He climbs ‘X’ feet every time. But, due to the slippery nature of those walls, every times he slips back by ‘Y’ feet. Now the input is given as (N, {H1, H2, H3,….Hn}, X, Y}. Calculate the total number of jumps required to cross all walls and escape from the jail.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Cisco Systems Software Developer Algorithm - 2of 2 votes
AnswersSingleton Design pattern. How you make it double ton(in even call of getInstance() first object should be return and odd call of getInstance() second instance should be return). Make it triple ton.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Goldman Sachs SDE-2 Software Design - 0of 0 votes
AnswersAdd 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.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 1of 1 vote
AnswersFind the Minimum length Unsorted Subarray, sorting which makes the complete array sorted
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersMaximum difference between node and its ancestor in Binary Tree in O(n) time.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersGiven a very large binary number which cannot be stored in a variable, determine the remainder of the decimal equivalent of the binary number when divided by 3. Then generalize to remainder of any number 'k'
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Algorithm - 2of 2 votes
AnswersGiven a pre-order traversal, construct a binary search tree in O(n) time.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Algorithm - 0of 0 votes
Answershere are tuples given for each users of a website (Si,Ei) where Si denotes the when the user entered the website and Ei denotes when the user exits the website .Find the maximum number of users active of website at any time duration.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Adobe MTS Algorithm - 1of 1 vote
AnswersYou are given a text file. You have to return the list of starting index of the given word in text file. Design an efficient DS for that.
- neer.1304 in United States
Example :-
Text file content : “geeks for geeks”
word : “geeks”
List : {0,10}| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Algorithm - 0of 0 votes
AnswersIn a file, there are two columns, first column has some word (String) and 2nd column has some value (Double).
- neer.1304 in United States
Example :-
ABC 23.4
ERF 34.89
WERT 122.9
Now user wants some arithmetic operations like
1) ABC + ERF = 23.4 + 34.89 = 58.29
2) ABC – WERT = 23.4 – 122.9 = -99.5
Design an efficient DS for these kind of operations.| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Algorithm - 0of 0 votes
AnswersGiven a remote having 0-9 digits, plus button (to increase channel), minus (to decrease) and previous channel button (to go to previous channel). We were given 2 numbers stating start and end channel number and an array having various channel numbers. The task was to go to all channel numbers given in array with minimum number of clicks.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Goldman Sachs Backend Developer Algorithm - 0of 0 votes
AnswersGiven MxN binary matrix, find the largest sub-square matrix with all 1’s.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-3 Algorithm - 0of 0 votes
AnswersDesign a geographically partitioned multi-player card game, that supports multiple players, multiple games at a time.
- neer.1304 in United States
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| Report Duplicate | Flag | PURGE
Amazon SDE-3 design - 0of 0 votes
AnswersGiven an array of integers. We need to answer two types of queries point update and range sum in minimum time.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-3 Algorithm - 1of 1 vote
AnswersFind third highest value in a binary tree
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-3 Algorithm - 0of 0 votes
AnswersThere are n Thread , n/2 thread are producer and n/2 are consumer, number produced by producer-1 thread must be consumed by consumer-1 thread. Thread must also run in order, producer 1, then consumer 1, again producer 2 and then consumer 2…so on…..
- neer.1304 in India| Report Duplicate | Flag | PURGE
One97 SDE-2 Algorithm - 0of 0 votes
AnswerImplement function which add n days to given date without using inbuilt library.
- neer.1304 in India| Report Duplicate | Flag | PURGE
One97 SDE-2 Algorithm - 1of 1 vote
AnswerA 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?
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersGiven a dictionary of words and a string pattern. Output the count of words that match the string pattern in the dictionary.
- neer.1304 in United States
Eg. Dictionary: [cat, rat, mat, apple, boy, bat]
String pattern: ?at
Output: 4 (because cat, rat, mat, bat matches the string pattern)| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersFind 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.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 1of 1 vote
AnswersDesign Truecaller. Both HLD and LLD.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 design - 0of 0 votes
AnswersGiven a chessboard, find minimum number of moves for a knight to reach from source to destination.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswerGiven 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.
- neer.1304 in United States
Examples : Given a graph with values {1,2,3,4}, find total time it takes, such that all nodes have value as 10.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 1of 1 vote
AnswersGiven 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)
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersThere are some professors, some courses, and some students.
- neer.1304 in United States
Each professor can teach only a single course.
Each course has a fixed duration(Eg. 10 weeks).
For each professor, you are given time availability schedule(assume week wise).
Each student has a list of courses he wants to learn.
There can be only 1:1 classes, i.e., 1 professor can teach only a single student.
A student can attend only one course at a time.
A professor has to finish teaching a course in a one go.
Your aim is to prepare a schedule so that all courses are taught in the least time.| Report Duplicate | Flag | PURGE
Adobe Computer Scientist Algorithm - 1of 1 vote
AnswersImplement a queue using only one stack.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Algorithm - 0of 0 votes
AnswersIt’s a two player game. Both the players are equally intelligent to win the game. Give n no. of stones. A player can choose either 1 stone or k stones or l stone (1<k<l). Suppose player 'A' starts game then challenge was to identify the player who will win the game. Player who picks the last 1 stone or last k stone or last l stones win the game.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Algorithm - 0of 0 votes
AnswersThere is a bridge and N no. people takes (a1,a2,—an) time to cross it and there are K torch and at any time x no of people can pass the bridge and it takes maximum of x people time to cross it. Minimum time required for N persons to cross the bridge.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Algorithm - 0of 0 votes
AnswerThere is a graph where each node represents a city and it contains specific no. of people. A tournament is going on and each match is playing in one city. All city’s people gather to watch match. Traffic department wants to manage how many people travel through city x if match is playing in city y for each x. City x and y can be any city.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Algorithm - 0of 0 votes
AnswersGiven an Infinite stream of strings as AAAAABBBCCDDDEEE… How will you arrange characters so that string become unique without duplicates .
- neer.1304 in United States
Return true if it is possible to arrange else return -1.
Ex . AAABBCCDEF – O/p ABABCDCEF : Possible . AAAAAAAAAAAAAAAAAAAAAAB : Not possible| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersGiven 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.
- neer.1304 in United States
For example, the list: 5, 2, 1, 4, 6, 7 needs to be changed to 6, 4, 4, 6, 7, 7.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersGiven 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
- neer.1304 in United States
Examples:
Input : A = [1, 2, 3, 4, 7, 9]
B = [0, 1, 2, 1, 1, 4]
Output : [4, 5, 5, 6, 6, 6]| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 2of 2 votes
AnswerDesign a movie ticket booking system like bookmyshow.com
- neer.1304 in United States
Follow-up question -
1) How do you handle issues like scalability, concurrency, fault-tolerance etc.
2) Show movie theaters near to user where movie is playing and seats are available
3) Design database. What kind of DB would you use SQL or No-SQL
4) In real time how would you show which seats are booked which are free
5) If theaters do not have any api for fetching information then what can we do about it.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Software Design - 1of 1 vote
AnswersDesign Uber. Low level Design needed (OOPS based - classes, relations, message flow etc.)
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 Software Design - 0of 0 votes
AnswerDesign Cricinfo website
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 Software Design - 0of 0 votes
AnswersDesign snake n ladder game to be played online
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 Software Design - 0of 0 votes
AnswersDesign a system having multiple jobs, interacting with each other such that :
- neer.1304 in United States
1) A job can run for very long periods (1-2 days)
2) A node can fail/crash on which certain job is running
system should be scalable
3) Amount of data getting transferred is huge
4) Data in the system is very sensitive and needs security
job/s can fail| Report Duplicate | Flag | PURGE
Amazon SDE-3 Software Design - 0of 0 votes
AnswersTop View of a Binary Tree in constant space
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-3 Algorithm - 0of 0 votes
AnswersGiven a pattern containing only Is and Ds. I for increasing and D for decreasing. Devise an algorithm to print the MINIMUM number following that pattern. Digits from 1-9 and digits can’t repeat.
- neer.1304 in United States
Example:
1. Input: D Output: 21
2. Input: I Output: 12
3. Input: DD Output: 321
4. Input: II Output: 123
5. Input: DIDI Output: 21435
6. Input: IIDDD Output: 126543
7. Input: DDIDDIID Output: 321654798| Report Duplicate | Flag | PURGE
Amazon SDE-3 Algorithm - 0of 0 votes
AnswersImplement ConcurrentHashMap class in Java
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-3 Algorithm - 0of 0 votes
AnswersImplement LinkedHashMap class in Java
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-3 Algorithm - 0of 0 votes
AnswersYou have been given a grid with some doors, walls and some empty spaces.
- neer.1304 in United States
1st part : You have to tell the least no of moves to go from random position in the grid to the nearest door. You can move in four directions only, i.e, left, right, above, below.
2nd part : Least distance of every empty cell to the nearest door. Lots of discussion was done on both the parts of the problem.| Report Duplicate | Flag | PURGE
Amazon SDE-3 Algorithm - 0of 0 votes
AnswersDesign garbage collector in Java
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-3 Software Design - 0of 0 votes
AnswersMaximum triangle path Sum : Starting from the top of a pyramid of numbers like below, you can walk down going one step on the right or on the left, until you reach the bottom row:
- neer.1304 in United States
55
94 48
95 30 96
77 71 26 67
One of such walks is 55 -> 94 >- 30 -> 26. You can compute the total of the numbers you have seen in such walk, in this case it’s 205.
Your problem is to find the maximum total among all possible paths from the top to the bottom row of the triangle. In the little example above it’s 321.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersDesign a online shipment tracking system.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 Software Design - -1of 1 vote
AnswersDesign a system to upload images and tag them. Ability to search images with single and multiple tags.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-3 Algorithm - 1of 1 vote
AnswersGiven a very large binary number which cannot be stored in a variable, determine the remainder of the decimal equivalent of the binary number when divided by 3. Generalize to find the remainder for any number k.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-3 Algorithm - 0of 0 votes
AnswersGiven a file having many lines of text(words) and given a dictionary having an API function boolean isValid(String word), which will return true is a word passed to this function is valid word in dic.,and will return false if given passed argument is not a valid word in dic.
- neer.1304 in United States
Now read the file and check if each word as well as all possible words from its L to R and R to L combinations, are valid words in dic. or not.| Report Duplicate | Flag | PURGE
Amazon SDE-3 Algorithm - 1of 1 vote
AnswersGiven sequentially placed boxes, each representing a number( which may be positive or negative), we need to select the numbers in order to have the maximum sum, having the constraint that if we select a given box, we cannot select adjacent box to it, but can select any other.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-3 Algorithm - 0of 0 votes
AnswersGiven 2 integers, add them without using any arithmetic operator
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-3 Algorithm - 0of 0 votes
AnswersImplement a LRU cache with ttl at each block
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-3 Algorithm - 0of 0 votes
AnswersFind all anagrams of a given string in a file of size 1TB.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-3 Algorithm - 1of 1 vote
AnswersGiven two strings print all possible permutations of two strings such that the order of characters are maintained.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-3 Algorithm - 0of 0 votes
AnswersGiven an array,generate all valid ip address from the array.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-3 Algorithm - 0of 0 votes
AnswersFind Longest Repeated Substring in the given string.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-3 Algorithm - 0of 0 votes
AnswersGiven a equi-weighted uni directed graph and need to find the max distance possible from a given node.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-3 Algorithm - 0of 0 votes
AnswerWrite a program to check whether it is a valid binary tree or not.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersMultiply two numbers represented as a linked list.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersGiven a sorted array which has been rotated n number of times. Find the value of n.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersClone the binary tree.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersIn a binary tree return the maximum "turns" in tree. A "turn" is defined as LRL or RLR traversal.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-3 Algorithm - 0of 0 votes
AnswersReturn the maximum length sequence containing consecutive numbers from a binary tree.
- neer.1304 in United States
90
/ \
1 66
/ \
2 67
/ \ /
5 4 68
/ \
99 100
Consecutive sequence of maximum length: [66, 67, 68] of length 3.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersImplement Tower of Hanoi without using recursion.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersA stepping number is defined as a number in which the absolute difference between the consecutive digits is not greater than 1, A stepping number cannot be a single digit number. You have to find the number of stepping numbers between n1 and n2 where n2 > n1 and n2, n1 > 0.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersGiven a stack of integers of size n, you have to sort it using only push and pop operations in O(1) space.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersGiven a tree return the number of elements for the level with the maximum elements.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersImplement multiple stacks using a single contiguous block of memory
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Ola Cabs SDE-3 Algorithm - 0of 0 votes
AnswersWrite a program to implement event bus
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Ola Cabs SDE-3 Algorithm - 0of 0 votes
AnswerDesign and implement a sender and receiver system where there can be multiple senders and receivers subscribed to Topics. Each event generated at sender should be received by all receivers subscribed to that topic. Bonus if you can implement group mechanism at receiver side where event is received by one of the receiver in group and received by all groups subscribed to that Topic.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Ola Cabs SDE-3 Algorithm - 0of 0 votes
AnswerImplement in-memory file system
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Ola Cabs SDE-3 Algorithm - 0of 0 votes
AnswersIn memory cache implementation which supports concurrent operations for PUT, GET and DELETE
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Ola Cabs SDE-3 Algorithm - 0of 0 votes
AnswersImplement thread safe generic typed hashmap.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Ola Cabs SDE-3 Algorithm - 0of 0 votes
AnswerDetermine if a point is inside a 2D convex polygon
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Ola Cabs SDE-3 Algorithm - 0of 0 votes
AnswerDesign and write algo for a bowling game wherein multiple games could be played in parallel and the scores to be shown for each game.
- neer.1304 in United States
Detailed question
Design the entire bowling alley system. One bowling game will be played by multiple players on a single lane.
During the game,players and their scores will be maintained and shown by the system and winner will be declared at the end of the game.
Likewise multiple games can be played in parallel on multiple free lanes.
Some rules about bowling:
A game consists of ten sets
In each set,the player has two opportunities to knock down ten pins.
The score for a set is the total number of pins knocked down,plus bonuses for strikes and spares.
A spare is when the player knocks down all ten pins in two tries.If there is spare the player gets 5 bonus points.
A strike is when the player knocks down all ten pins on his/her first try.If there is a strike the player gets 10 bonus points.
In the final set a player who rolls a spare or a strike is allowed to roll the extra balls to complete the set.However only a maximum of three balls can be rolled in the final set.| Report Duplicate | Flag | PURGE
Ola Cabs SDE-3 design - 0of 0 votes
AnswersDesign rubik’s cube and its operation (all rotations and checking final state)
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Ola Cabs SDE-3 Algorithm - 2of 2 votes
AnswersDesign OO food delivery app catering to use cases -
- neer.1304 in United States
1) User can search different restaurant
2) User can select a restaurant
3) User sees a menu
4) Restaurant can change the menu any time
5) User adds an item from menu
6) User orders the food
7) User can track the order in real time
8) User can cancel the order
9) User pays for the order| Report Duplicate | Flag | PURGE
Amazon SDE-2 Object Oriented Design - 0of 0 votes
AnswersDesign food delivery app (OO design). Cater to use cases like search for different restaurants, selecting a restaurant, select an item from menu, menu can be updated in real time by restaurant, order the food, customer keeps track of the order in real time, payment for the order, cancel the order etc.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 Object Oriented Design - 1of 1 vote
AnswersGiven a dictionary and an char array print all the valid words that are possible using char from the array.
- neer.1304 in United States
Ex- char[] arr = {'e','o','b', 'a','m','g', 'l'}
Dict - {"go","bat","me","eat","goal", "boy", "run"}
Print - go, me, goal.
We can pre-compute as much we want but the query time must be optimal.| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Algorithm - -2of 2 votes
AnswersGiven a matrix which is spirally sorted. Remove an element and insert another element maintaining the sorted order.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Algorithm - 0of 0 votes
AnswerGiven a few points in first quadrant – (x1,y1) …..(xn,yn) and given another set of points (a1,b1…..an,bn), determine whether all the points (a1,b1…an,bn) have already occured in (x1,y1)…..xn,yn)
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Algorithm - 0of 0 votes
AnswersGiven a graph where every two nodes are either friends or enemies with each other. Find a way to go from one node to the other.
- neer.1304 in United States
Restrictions:
1) You can also travel from one node to next if they are friends with each other
2) You have some “magic potions”. You can convert an enemy path to a friend path with a magic potion.
Find the path with min number of magic potions required.| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Algorithm - 0of 0 votes
AnswersYou are given a structure msg
- neer.1304 in United States
struct msg
{
long timestamp;
double price;
string label;
};
The msg represents price of a stock on a given timestamp.
Create a class with two functions -
addStockPrice(msg m) -> Used to add Stock Price in Data structure
getAvgPriceForAStockLast10Minutes(String stockName) -> Get average price of a stock for last 10 minutes.
The program should be time and space optimized.| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Algorithm - 0of 0 votes
AnswersDesign and Implement: Producers and Consumer Problem. Producers produce different kind of messages and Consumers register themselves for different kind of messages. Need to design and implement Producer, Consumer and a Delegator which is responsible for storing and delivering the messages to appropriate listeners.
- neer.1304 in United States
Changed the question to handle millions of messages.
Changed the question to handle different priority messages.
Threading model for Producer, Listener and Delegator.
In the end he asked me to code 2 methods of Delegator.
1: which adds the message from Producer to its internal queue.
2: Delegate, which delivers the message to appropriate listener.| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Software Design - 0of 0 votes
AnswersGiven a series of number form a binary tree find the minimum weight binary tree. The weight of the node is depth * value of the element + weight of the left tree + weight of the right tree.
- neer.1304 in United States
Weight of the root node is the weight of the tree . Find the minimum weight binary tree out of all possible binary trees that are possible.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswerGiven start time and end time of parking (below is the table of price rule). Come up with data structure you can store these price rules
- neer.1304 in United States
Price Rules:
On Weekday On Weekend
Hours Price Hours Price
0 – 2 $5 0 – 2 $8
2 – 6 $10 2 – 6 $13
6 – 12 $15 6 – 12 $18
12 – 24 $20 12 – 24 $25
Design an architecture for the system which shows parking spaces available near customer's location in a mobile app.| Report Duplicate | Flag | PURGE
Amazon SDE-3 Software Design - 1of 1 vote
AnswersGiven an array of 0s and 1s, and k, Find the longest continuous streak of 1s after flipping k 0s to 1s.
- neer.1304 in United States
E.x array is {1,1,0,0,1,1,1,0,1,1}
k = 1 (which means we can flip ‘k’ one 0 to 1)
Answer: 6 (if we flip 0 at index 7, we get the longest continuous streak of 1s having length 6)| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersImplement a finite state machine.
- neer.1304 in United States
– The machine should have one start state and can have multiple end states
– It should be extensible (I should be able to add any number of states or transitions at any time)
– I should be able to set notifications on or off for any state or for the whole state machine| Report Duplicate | Flag | PURGE
Flipkart SDE-2 Algorithm - 0of 0 votes
AnswersYou are given some equations which may contain > or = on different-different operand. For example there are valid input and invalid (a=5, b<a=50)
- neer.1304 in United States
String e1 = "a>b=1";
String e2 = "a>b=2";
String e3 = "a>c>e=3";
String e4 = "a>c>f=4";
String e5 = "b>a=5";
String e6 = "a>b>c=5";
String e7 = "b=7";
String e8 = "a>b>c>d=99";
String e9 = "a>b=99";
You need to create JSON string from it.
{
‘a’: {
‘b’: [1,2,99],
‘c’: {
‘e’:3,
‘f’:4
}
},
‘b’: {
‘a’ : 5
}
}
Input: You are given those string in string array
Output:
Construct JSON
Print it| Report Duplicate | Flag | PURGE
Flipkart SDE-2 Algorithm - 0of 0 votes
AnswersThere is down-turn in the ship-building industry. Ace Shipping Corp (ASC) wants to be prepared by having a system that will help evaluate the total cost saving they will achieve if they were to ‘let go’ some employees.
- neer.1304 in United States
Following are the rules for drawing up this Firing List:
Each manager at every level in the organization will have to contribute ‘heads’ from his team to the firing list
The input to the system would be a small integer k (=1,2, etc) which would be the number of employees chosen per manager. The output would be the total cost saved for this k. Different values of k would give an idea of the total cost saving achieved.
The primary selection criteria is Performance Rating. k employees with the minimum rating under a given manager are to be selected.
If two employees have the same rating, the one with the higher salary gets selected (to maximize cost saved)
The activity might be requested for the sub-org under any manager. The default is to consider the entire org.
Although total number of reportees for a manager is usually of the order of 10, it could possibly be a much larger number in some org too. An optimal way of choosing the k reportees would be preferred.
The following information needs to get stored per Employee:
Employee ID (unique)
Name
Performance Rating (1-5, 1 is lowest, 5 is highest)
Salary (Rs)| Report Duplicate | Flag | PURGE
Flipkart SDE-2 Algorithm - 2of 2 votes
AnswersGiven a binary tree print it in inward spiral order i.e first print level 1, then level n, then level 2, then n-1 and so on.
- neer.1304 in United States
For Ex -
1
2 3
4 5 6 7
8 9 10 11 12 13 14 15
Print- 1 15 14 13 12 11 10 9 8 2 3 7 6 5 4
Follow up question - Extend the algorithm to n-ary tree.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 3of 3 votes
AnswersGiven a singly connected linked list, find the largest palindrome in the list in O(1) space.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Algorithm - 3of 3 votes
AnswersGiven a linked list consisting of String in each Node . Given just a pointer to the head Node find whether the resultant String formed by combining all the Nodes of the linked list is a palindrome or not in O(1) space and O(n) time.
- neer.1304 in United States
eg – Consider this linked List structure
“aba” -> “cd” -> “efe” -> “d” -> “caba”
Hence this structure is palindrome .| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Algorithm - -1of 1 vote
AnswerGiven an N-ary tree with thousands of nodes in it. Pair (Join) the Leaf nodes which do NOT SHARE the common path. i.e. Two Leaves can be Paired only if they do NOT have Intersecting path.
- neer.1304 in United States
For example,
A
/ | \
B C D
/ / | \
E F G H
Leaf nodes: E, F, G, H & D
Possible Pairs in O/Ps:
a) (E-F), (G-H) or
b) (E-G), (F-H) or
c) (E-H), (F-G) or
d) (E-D), (F-G) or
e) (E-D), (G-H) or
f) (E-D), (F-H) or
g) (D-H), (F-G) or
h) (D-G), (F-H) or
i) (D-F), (G-H)
Note: If we pair(join) say, (E-F) then we can NOT pair any of the (D-G) or (D-H) as they SHARE the COMMON path from A to C.
i.e. E-B-A-C-F —> (E-F) pair
D-A-C-G —> (D-G) pair
D-A-C-H —> (D-H) pair| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Algorithm - 0of 0 votes
AnswersGiven a tree, and a pointer to some node in the tree, print the left most element in the same level as that node
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Algorithm - 0of 0 votes
AnswersGiven 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)
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Algorithm - 0of 2 votes
AnswersGiven a binary tree, connect all node in the same level in toggle manner.
- neer.1304 in United States
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.| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Algorithm - 0of 0 votes
AnswersGiven a string regex and another string pat find whether the pattern is acceptable against given regex string.
- neer.1304 in United States
Regex string contains following characters and special characters:
1. Normal alphabets – a to z and A to Z
2. ‘$’ – all string should end with all characters preceding $
Example:
Regex :abc$ ,
Pattern: abcd(Not acceptable) , abc(acceptable), ab(Not acceptable), dhfusdhabc(acceptable) etc..
3. ‘^’ – all string should start with all characters exceeding ^
Example: Regex : ^abc
Pattern: abcd(acceptable) , abc(acceptable), ab(Not acceptable), dhfusdhabc(NOT acceptable) etc..
Regex: ^ then only pattern acceptable is null.
4. ‘.’ – any character can be mapped to dot except null
Example 1: Regex : .abc
Pattern: Zabc(acceptable) , abc(NOT acceptable), ab(Not acceptable), habc(acceptable) etc..
Example 2: Regex :a.bc
Pattern: abc(NOT acceptable) , aXbc(acceptable), ab(Not acceptable), habc(NOT acceptable) etc..
5. ‘*’-the character just preceding * can be repeated n time where (n>=0)
Example 1: Regex :abc*de
Pattern: abccccccccccde (acceptable), abcde(acceptable), abcccd(not acceptable)| Report Duplicate | Flag | PURGE
Flipkart SDE-2 Algorithm - 0of 0 votes
AnswerGiven a list a1,a2,a3….an. Comparison between elements is given like a1>a2, a3>a5, a4>a2…..etc. Find whether there are any situations that we can sort the list in to the ascending order on the basis of comparison. Yes or No , explain the conditions
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Flipkart SDE-2 Algorithm - -1of 1 vote
AnswersDesign and implement a scalable multi-player N*N TicTacToe game.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Flipkart SDE-2 Algorithm - 0of 0 votes
AnswersGiven a grid of m*n size. Each block in grid has some amount of gold.
- neer.1304 in United States
We start from first column of the grid(any row) and we can move in 3 direction - right, right-up and right-down.
What is the maximum amount of gold we can collect from the grid.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 1of 1 vote
AnswersPrint first and last node of all the levels of a tree.
- neer.1304 in United States
Ex if tree is -
root->data = 1
root->left->data = 2
root->right->data = 3
root->left->right->data = 4
root->right->right->data = 6
root->right->left->data = 5
root->right->left->left->data = 7
root->right->left->left->right->data = 8
Output - 1 2 3 4 6 7 8| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - -1of 1 vote
AnswersConnect nodes at same level of a binary tree recursively using O(1) space (we can ignore stack space used for recursion)
Tree node is like following.struct node { int data; struct node* left; struct node* right; struct node* nextRight; }
Initially, all the nextRight pointers point to garbage values. Your function should set these pointers to point next right for each node. You can use only constant extra space.
- neer.1304 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 - 0of 0 votes
AnswersGiven a pond where all the stones are lined at a distance of one unit (C in each row and there are R such rows).
- neer.1304 in United States
Each stone has a special value which denotes the length of the jump the frog can make i.e if frog is on stone (x,y) and value is k then frog can jump to (x+dx,y+dy) where dx+dy=k and frog doesn’t leave the bounds.
Find the min number of jumps to reach the stone at (R,C). Also print the path taken by frog to reach the stone.| Report Duplicate | Flag | PURGE
Flipkart SDE-2 - 0of 0 votes
AnswersGiven 1000 elephant ,none of whom exact heights are known, there are statements given which will be of two forms
- neer.1304 in United States
i- E_i is taller than E_j
OR
ii- E_i is smaller than E_j
Calculate the ascending order of the elephants(in terms of height).
For ex-
1) E1 is taller than E3
2) E3 is smaller than E2
3) E2 is taller than E1
Then order would be E3, E1, E2| Report Duplicate | Flag | PURGE
Flipkart SDE-2 - 0of 0 votes
AnswersYou are given a String S that consists of characters '0' and '1' only.Return the smallest positive integer K such that it is possible to cut S into K pieces, each of them being a power of 5. If there is no such K, return -1 instead.
- neer.1304 in India
Examples
0)
"101101101"
Returns: 3
We can split the given string into three "101"s.
Note that "101" is 5 in binary.
1)
"1111101"
Returns: 1
"1111101" is 5^3.
2)
"110011011"
Returns: 3
Split it into "11001", "101" and "1".
3)
"1000101011"
Returns: -1
4)
"111011100110101100101110111"
Returns: 5| Report Duplicate | Flag | PURGE
Flipkart SDE-2 Algorithm - 1of 1 vote
AnswersYou are given a catalog of books, which have following attributes :-
- neer.1304 in United States
Name, Author, Publisher, Publish year, Category, Price, Count (sold)
Implement following APIs on top of this catalog -
1) addBookToCatalog(Book)
2) searchBook(by partial book name/author)
3) getMostSoldBooks(by author name/category, limit)
Expectations:
Maintain DB on memory
Code should be readable. Design, handle naming convention,handle exceptions & should be running| Report Duplicate | Flag | PURGE
Flipkart SDE-2 Algorithm - 0of 0 votes
AnswersYou have an organizational structure, which shows hierarchy of the organization. This hierarchy contains employees E or managers M who has some Employees or Managers reporting to M. Employee has ( id, name, JobDesc, salary etc). Design the data structure you would be using to store this hierarchy
- neer.1304 in United States
1: Given an ID of an employee , print all the employee ID's who are directly reporting or indirectly reporting to the manager.
2. Given a bonus and performance rating of each employee divide it to the lowest level employees(in the hierarchy ) in the ratio of their rating. i.e 100 divided among 2:3 is 40 and 60. and print the bonus of each
3. Top 10 employees with ratio of bonus:salary
Note :-
1) Employee can have only 1 mgr, and a mgr has 1+ employees.
2) Input can be in any order for ex- employees might be input before his manager.| Report Duplicate | Flag | PURGE
Flipkart SDE-2 Algorithm
Tried few test cases but got wrong answer for them
1. String input = "aasasatb"; O/p - 2asas1a1t1b Exp O/p - 2a2sa1t1b
2. String input = "aaaaabaaaaabaaaaabaaaaab" 5ab5ab5ab5ab Exp O/p- 4aaaaab
3. String input = "aaaaabaaaaabaaaaabZaaaaab" 5ab5ab5ab1Z5a1b Exp O/p - 3aaaaab1Z4a1b
RepRutviOrtiz, Android Engineer at AMD
I am experienced in teaching other translators through one-on-one mentoring and professional development courses. I am passionate about Unbinding spell ...
Repmariacbrister, Graphics Programmer at Graphic Systems
Hey, I am Maria and I am from Bluefield. Currently, I work as a freelancer graphic artist. From an early ...
Reptanyamayst, Android Engineer at ABC TECH SUPPORT
I am an experienced project support officer seeking a team focused on excellence and accelerated performance in a BMO company ...
Reprosejgarciaa, abc at ADP
I am SheliaWMoore and working in Red news from many years.Manage latest current affairs and print articles in newspaper ...
Repjuanktait, Blockchain Developer at ADP
I am Juan from Seattle, WA. I am working as a LAN administrator. I love music, reading historical books, and ...
Repomarcdei, Android Engineer at Abs india pvt. ltd.
I'm Omar. I am working as a Mail carrier in Manning's Cafeterias company. I love to learn and ...
Repbrakpeter2, AT&T Customer service email at Absolute Softech Ltd
My Profession Is photography for a number of years.My Friends were interested in photography, so I was always exposed ...
Rephim4211, Applications Developer at Accenture
RepGenesisCruz, Integration Software Engineer at NetApp
I am a highly professional and experienced board director with many years of experience leading non-profit as well as for-profit ...
yes it means to set all values in stream to be true
- neer.1304 July 20, 2019