sonesh
BAN USER 0of 0 votes
AnswersYou have to desing a system for a shop kepper to keep his/her inventory managed. He/she have furniture at the begining, but he may add more items to it. His/her furnitures are wood char, wood table, steel chair, etc.
 sonesh in United States
Each furniture have one property, a boolean one, called isChildSafe.
Later, he said, what if the shopkeeper wants to add new type of items, such as phone or may be something else, and he/she might also wants to add two new properties, such as isFireSafe, isWaterSafe etc.
How would you design extend to these types. Report Duplicate  Flag  PURGE
Amazon SDE2 design  0of 0 votes
AnswersYou have to design a job scheduler. The job schedular should be able to accept all kind of jobs, small or long running. Multiple systems might be adding jobs to it and multiple systems should be able to execute jobs simultaneously.
 sonesh in United States
Please list down the components and data flows between them, what kind of interfaces you will be having, what kind of retry logic you will be providing, storage and middle tier design was also asked. Report Duplicate  Flag  PURGE
Amazon SDE2 design  3of 3 votes
AnswersYou are given set of strings, You have return anagrams subsets from it. An anagram set is that one where every string is an anagram of another string. If the subset contains only one string, don't include that in the result.
 sonesh in United States Report Duplicate  Flag  PURGE
Amazon SDE2 Algorithm String Manipulation  0of 0 votes
AnswerDesign/Implement an LRU cache so that Read/Write/Find operation only takes constant time.
 sonesh in United States
Now, Let's say, we will be considering the frequency as well. It means to keep the most used processes and in a case of the tie, use lease recently used to remove an element.
Now, as this new algorithm can cause many hits, or no new process will come to the cache if the last process of the cache has two hits., What can you do to prevent this, and how would you implement that. Report Duplicate  Flag  PURGE
Amazon SDE2 Algorithm design  0of 0 votes
AnswersRegex matching algorithms
 sonesh in United States
You will be given a string and a pattern string consisting of only '*','?', and small letters. You have to return tree or false based upon the comparisons.
? repersent one char.
* means zero or n number of char for any positive n.
Example
abc, a?c : true
abc, a*?c : true
abc, * : true
abc, ?c : false Report Duplicate  Flag  PURGE
Two Sigma Software Engineer / Developer String Manipulation  0of 0 votes
AnswersYou are given following design architecture.
[DB] <==> [Server]
Now let's say user are complaining about our server being slow, how would you figure out where is the problem?
 sonesh in United States
2) now let's say the problem is in server, where do you think the problem is in server?
3) What if you found our server is fast, how about now?
4) you have also found that the network call from server to DB is also fast, how about now?
5) Lets say, our server is also setting near the complaining user, how about now? Report Duplicate  Flag  PURGE
Two Sigma Software Engineer / Developer design  0of 0 votes
AnswersYou are given two Queues where each queue contains timestamp price pair. You have to print <price1 price 2> pair for all those timestamps where abs(ts1ts2) <= 1 second where ts1 and price1 are the from the first queue and ts2 and price2 are from the second queue.
 sonesh in United States
Now let's say one queue is slow, what kind of modification you will make? Report Duplicate  Flag  PURGE
Two Sigma Software Engineer / Developer Stacks q  0of 0 votes
AnswersYou are given an array of nodes where each node consists of node name, isValid flag, and parent Node index. so, this array actually represents a tree(forest). where root node has 1 as its index for the parent node. rest all node have their parent's index value.
 sonesh in United States
You will be given this array and an index. You have to cut down the subtree from the index. Cutting down a tree means, making all the nodes of that subtree false(Isvalid flag).
He was expecting O(N) solution. Report Duplicate  Flag  PURGE
Two Sigma Software Engineer / Developer Arrays Coding Trees and Graphs  0of 0 votes
AnswersDefine Reverse Polish notation calculator. Interviewer needed class design for the calculator. Please make sure that adding extra operator tomorrow should not make us change the class or any of its methods.
 sonesh in United States Report Duplicate  Flag  PURGE
Two Sigma Software Engineer / Developer design  0of 0 votes
AnswersYou are given an array of values, (not necessary integers or positives) and a value. You have to print all the pairs whose sum is given value. Write a general method which can accept integers, float, doubles, long, or any other thing where this make sense.
 sonesh in United States Report Duplicate  Flag  PURGE
Bloomberg LP Senior Software Development Engineer Algorithm Coding  0of 0 votes
Answers1) write a concurrent singleton class.
 sonesh in United States
2) Write a factory method class, and how it is used
3) Define a sealed class.
4) What if we want to replace sealed class with another class and use this new class where ever we have used our sealed class, how do you do that.
5) What would you look in a code review?
6) Do you know about adapters, bridges design pattern
7) Define async await method, how do we read data in task library
8) What are the other methods of making your call multithreaded
9) Do you know Linq queries
10) How to make defer/no defer execution in Linq Queries.
11) Where do you use singleton class, give at least three examples
12) When we use singleton class and when static, both have the single instance. Report Duplicate  Flag  PURGE
Bloomberg LP Senior Software Development Engineer design  0of 0 votes
AnswersYou are given set of strings, you have to print out the could of each distinct patterns. Please consider anagrams as same pattern and even the char count does not matter.
 sonesh in United States
Ex:
abbba
ab
ba
abcd
abdc
adbc
aabddc
output:
ab: 3
abcd: 4 Report Duplicate  Flag  PURGE
Bloomberg LP Software Engineer / Developer Algorithm  0of 0 votes
AnswersYou are given three type of data sets.
 sonesh in United States
Type 1
Data size: 4 billion
Distinct Data: 1000
Type 2
Data Size: 4 billion
Distinct Data: 2 billion
Type 3
Data Size: 1000
Each Data is of length 100 million byte
What kind of data structure would you use to answer search/insert/remove queries for each data types? Report Duplicate  Flag  PURGE
Bloomberg LP Software Engineer / Developer Data Structures  0of 0 votes
AnswersQ 4. You are given a binary tree, and you have to return list of lists of node. where same level nodes should be in the same list, nodes are in opositive order in next list from the previous list
Ex:4 / \ 3 5 / \ \ 1 10 4
Output would be
 sonesh in United States
[[4], [5, 3], [1, 10, 4]]
Desigred Complexity : O(N) + O(N). Report Duplicate  Flag  PURGE
Hitachi Data Systems Software Engineer / Developer Linked Lists Stacks Trees and Graphs  0of 0 votes
AnswersQ 3. You are given a LinkedList and a number K. You have to reverse it in the groups of K
 sonesh in United States
Ex :
[1] > [2] > [3] > [4] > [5] > null, K = 3
output: [3] > [2] > [1] > [5] > [4] > null
Desired Complexity: O(n) + O(1) Report Duplicate  Flag  PURGE
Hitachi Data Systems Software Engineer / Developer Linked Lists  0of 0 votes
AnswersQ 2. You are given a chess game board of size NxN. You have find out positions(i,j), where you can place N queens so that, none of the queens can kill each other without making their first move.
 sonesh in United States Report Duplicate  Flag  PURGE
Hitachi Data Systems Software Engineer / Developer Algorithm Coding Dynamic Programming Matrix  1of 1 vote
AnswersQ 1. You are given an array of integers, contains positive, negative and zeros. You have to written subarray whose sum is maximum in this array.
 sonesh in United States
Desired Complexity is O(N) + O(1) Report Duplicate  Flag  PURGE
Hitachi Data Systems Software Engineer / Developer Algorithm Arrays  0of 0 votes
AnswersYou have given a tree, where each node can have multiple children. You have to find if the tree has a cycle or not.
ExA / \ / \ B C /  \  \ D E F E H  B
This tree has a cycle from B > E > B.
 sonesh in United States
Please note that you only know the nodes that you have traveled in the tree, so at the beginning, you will only know that there is a root node and nothing else about any other node.
The followup question was to print the cycle in the tree if found. Report Duplicate  Flag  PURGE
Electronic Arts SDE3 Algorithm  0of 0 votes
AnswersTheoretical Questions
 sonesh in United States
Q 1. Any design patterns you have used, please explain in details
Q 2. Difference between a process and a thread
Q 3. How threads/processes can communicate with each other.
Q 4. What is latency and throughput, what is there the difference?
Q 5. When to use merge sort over quick sort and viceversa.
Q 6. What is hashmap, how would to implement one. Report Duplicate  Flag  PURGE
Two Sigma Software Engineer / Developer Brain Storming technical  1of 1 vote
AnswersYou are given an array of integers and a number K. You have to find the any continue subarray whose elements sum is K. Please note that, the array may have positive, negative, and zeros as its element.
 sonesh in United States
The desired complexity is O(N).
Example:
Input: [7 0 9 10 0 789], K = 0
Output: Array from index 1 to Index 1.
Input: [1 2 3 5 10] K = 0
Output: Array from Index 1 to Index 4.
If K = 2, Output would have been SubArray from Index 2 to Index 4. Report Duplicate  Flag  PURGE
Snap Inc Software Engineer / Developer Arrays  0of 0 votes
AnswersYou are given a positive integer number and you have to return the greatest smaller tidy number of this input number. If the input number itself is tidy, then, it become the answer
 sonesh in India
Example
Input: 1234
output: 1234
input: 100
output: 99
input 143456
output: 139999.
PS.A tidy number is a number whose digits are in nondecreasing order. Report Duplicate  Flag  PURGE
FreshoKartz Software Engineer Intern Bit Manipulation  0of 0 votes
AnswersYou are given a positive integer number and you have to return a boolean telling whether the input number is a tidy number or not. A tidy number is a number whose digits are in nondecreasing order. For example, 1234 is a tidy number, 122334 is also a tidy number but 143567 is not a tidy number.
 sonesh in India Report Duplicate  Flag  PURGE
FreshoKartz Software Engineer Intern Bit Manipulation  0of 0 votes
AnswersYou are given an integer array. You have to return/print an array where kth element of this array is the multiplications of all the elements from 0 to k1 and from k+1 to n1.
 sonesh in United States
Example
input: [1 2 5 6]
output: [60 30 12 10] Report Duplicate  Flag  PURGE
Coupang Software Engineer / Developer Arrays  0of 0 votes
AnswersYou are given a BST of integers and an integer K. You have to find the smallest greater integer then K in the BST.
Ex
 sonesh in United States40  50  80    45 20  30   10 K = 35 Output: 40
 Report Duplicate  Flag  PURGE
Hitachi Data Systems Software Engineer / Developer Trees and Graphs  1of 1 vote
AnswersWe define a ksubsequence of an array as follows
 sonesh in United States
1) it is a subsequence of consecutive elements in the array
2) the sum of the subsequence's elements s, is evenly devisible by k(i.e. s % k == 0)
Given an integer and input array, find out the number of ksubsequences.
Example: k=3 and array be [1 2 3 4 1]
Output: 4 ({1 2},{1,2,3},{2,3,4},{3}) Report Duplicate  Flag  PURGE
Expedia Software Engineer / Developer Algorithm  0of 0 votes
AnswersYou are given an array with duplicates. You have to sort the array with decreasing frequency of elements. If two elements have the same frequency, sort them by their actual value in increasing order.
 sonesh in United States
Ex: [2 3 5 3 7 9 5 3 7]
Output: [3 3 3 5 5 7 7 2 9] Report Duplicate  Flag  PURGE
Expedia Software Engineer / Developer Sorting  0of 0 votes
AnswersYou are given two string (like two statements). You have to remove all the words of second string from first string and print the remaining first string. Please maintain the order of the remaining words from the first string. You will be only removing the first word, not all occurrence of a word.
 sonesh in United States
Example: Str1 = "A Statement is a Statement", Str2 = "Statement a"
Output: "A is Statement" Report Duplicate  Flag  PURGE
Expedia Software Engineer / Developer String Manipulation  0of 0 votes
AnswersYou are given an integer, print its 4th least significant bit
 sonesh in United States Report Duplicate  Flag  PURGE
Expedia Software Engineer / Developer Bit Manipulation  0of 0 votes
AnswersYou are given an array of words. from each word, you make a chain, in that, you remove one char at a time and you remove that char only when the remaining word is present in the input array.
 sonesh in United States
For Example, if the input is {a, b, ab, ac, aba}
then the possible chains are
from 'a', there is no chain, the chain it 'a' itself (of length 1)
similarly, from 'b', the chain length is 1 one (length is defined by the number of words in the chain)
now from 'ab', there are two possibilities which are ({ab > b when you remove a},{ab > a when you remove b}). So the max length is 2 here
now from 'ac', we only have one possibility which is ({ac > a when we remove c}), because, when we remove 'a', we left with 'c' which is not present in the input.
Now, you have to find the length of the biggest such chain.
Input: array of words
Output: length of the biggest such chain. Report Duplicate  Flag  PURGE
Two Sigma Software Engineer / Developer Algorithm String Manipulation  0of 0 votes
AnswersFriends have transitive property where if A is the friend of B, and B is the friend of C then A is also the friend to C. Like that we make friend circle.
 sonesh in United States
You have to find the number of such circles in a given list of friends
You are given a NxN matrix, where columns of each row will have either 'N' or 'Y', where 'N' represents not a friend and 'Y' represents Yes, they are friends.
Example :
YNY
NYN
YNY
The output is 2({0,2},{1}), as the 0 and 2 are friends of each other and 1 is another friend who is neither friend with 0 nor with 2. Report Duplicate  Flag  PURGE
Two Sigma Software Engineer / Developer Graphics  0of 0 votes
AnswersQ1. You are given a binary search tree (with unique values) and two values. You need to find their lowest common ancestor. (Expected Complexity O(log(n)) + O(1))
 sonesh in United States
Q2. Now let's assume the tree has duplicates, and when a duplicate number come, the insertion logic chooses left node. (Expected Complexity O(log(n)) + O(1))
Q3.Now let's assume the input tree is a binary tree instead of the binary search tree.(Expected Complexity O(n) + O(1)) Report Duplicate  Flag  PURGE
Bloomberg LP Software Engineer / Developer Trees and Graphs  0of 0 votes
AnswersYou are given an unsorted binary array.
 sonesh in United States
Ex [0 1 1 0 0 1 0 1 1 1 1 0 0 1 0 0 1]
and a number K, which represents the number of swap operations allowed on this binary array.
you need to find out the maximum length continuous subarray that can be generated using K many swaps.
Ex if K = 3 in above case
[0 1 1 0 0 1 0 1 1 1 1 0 0 1 0 0 1] => [0 1 1 0 0 1 1 1 1 1 1 0 0 0 0 0 1] => [0 1 1 0 1 1 1 1 1 1 1 0 0 0 0 0 0] => [0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0]
so the answer is 9. Report Duplicate  Flag  PURGE
Amazon Software Engineer / Developer Algorithm  1of 1 vote
AnswersYou are given a binary matrix whose each row is sorted. that means each row will have zeros at front and ones at the back. You need to find out the row which contains a maximum number of ones.
Ex :[0 0 0 0 0 0 0 1 1 1 1 1] [0 0 0 0 1 1 1 1 1 1 1 1] [0 0 0 0 0 0 1 1 1 1 1 1] [0 0 0 0 0 0 0 0 0 1 1 1] [0 0 0 0 0 0 0 1 1 1 1 1] [0 0 0 0 1 1 1 1 1 1 1 1]
Ans : second row and sixth with 8 ones. you will print [2,8] and [6,8];
 sonesh in United States
Update : Required complexity O(M+N) + O(1) only. Report Duplicate  Flag  PURGE
Amazon Software Engineer / Developer Algorithm  0of 0 votes
AnswersOne question containing multiple questions
 sonesh in United States
1) Define the structure of a function which takes an array of size n as input and returns True or False.
2) Write a function which takes an array as input and returns a string containing all the elements separated by a comma.
Ex : [0, 45, 9, 10] => "0,45,9,10";
3) Write a function which takes two arrays ass input, and returns minimum common element in them.
Ex : [0, 90, 45, 10, 4], [4, 8, 90, 45] => 4
4) Now let's say, the function takes an array of arrays, and each array is sorted. now, returns their first common element.
Ex : [0, 90, 45, 10, 4], [4, 8, 90, 45], [1, 3, 5, 7, 10, 4], [24, 35, 78, 90, 56, 4] => 4 Report Duplicate  Flag  PURGE
Bloomberg LP Software Engineer / Developer Arrays  1of 1 vote
AnswersYou are given an array of integers both negative and positive.
 sonesh in United States
Print the maximum continuous sum of the array and if all the elements are negative, print the smallest of them.
Ex : [20, 5, 2, 9] :> 2(2)
Ex : [20, 19, 6, 9, 4] :> 20(20)
Ex : [10, 3, 4, 2, 1, 10] > 18 (10, 3, 4, 2, 1, 10)
Thanks velu007 for pointing out the mistake Report Duplicate  Flag  PURGE
Bloomberg LP Software Engineer / Developer Algorithm  1of 1 vote
AnswersDefine a graph using Adjacency list where node and graphs are different entities, for example, Node is a struct/class and graph is set of nodes.
 sonesh in United States
The graph is an acyclic directed graph(may be a forest not necessarily connected).
Write an assignment copy constructor for this graph.
Please note that the copy constructor should create a new copy of the graph, including all its edges and vertices. Interviewer called this deep copy. Report Duplicate  Flag  PURGE
Bloomberg LP Software Engineer / Developer Graphics  2of 2 votes
AnswersRound 6
 sonesh in United States
Question 3 : You are given a word document, you have to print the words with frequencies. Now print the kth rank word in terms of frequency. Print top k words as well by frequencies Report Duplicate  Flag  PURGE
Microsoft Software Engineer / Developer Algorithm Arrays Coding Sorting  0of 0 votes
AnswersRound 6
 sonesh in United States
Question 2 : VRBO(Vacation Rentals by Owner), is a portal for real state where owners can rent their properties, renters can occupy them for sort duration by giving rent to the owner via VRBO. Lets start by thinking how you can design such system. ?, What are the complexities you have address here ?, both business and technical ?, what will be your main focus ?, tell me about the architecture of the system ?
Note that he wasn't concern about finer implementation details, but looking for broader things and thoughts. Report Duplicate  Flag  PURGE
Microsoft Software Engineer / Developer Brain Storming Software Design System Design Terminology & Trivia  1of 1 vote
AnswersRound 6 (taken by PRINCIPAL SOFTWARE ENGINEER)
 sonesh in United States
Question 1 : Since when you started searching for a new job ?, any project you are proud of ?, If you are given the same project now, how differently you will do now ?, why do you think whatever you have applied at that time was optimal ?. Report Duplicate  Flag  PURGE
Microsoft Software Engineer / Developer General Questions and Comments  0of 0 votes
AnswersRound 5
 sonesh in United States
Question 5 : Now lets say you are given k number of input streams, each stream have two method implemented, one is ReadNextNumber() and another is WriteToStream(), lets say each of the streams are sorted. How will you return a single sorted stream which contains all the streams data. Report Duplicate  Flag  PURGE
Microsoft Software Engineer / Developer Algorithm Arrays Sorting  1of 1 vote
AnswersRound 5
 sonesh in United States
Question 4 : Now lets say you have 1 PB(1000 TB) of numbers, what kind of system you would prefer, not that you can't store this data in one box. How will you sort these many numbers, what is the time complexity in seconds ?. does increasing core per machine help here ? Report Duplicate  Flag  PURGE
Microsoft Software Engineer / Developer Algorithm Arrays Data Structures Distributed Computing Sorting  1of 1 vote
AnswerRound 5
 sonesh in United States
Question 3 : Now lets say you have 1 TB(1000 GB) of numbers, how do you sort it, tell me the complexity in seconds ?, any optimization you would like to do here, ?, lets say your machine is having two core, now ? Report Duplicate  Flag  PURGE
Microsoft Software Engineer / Developer Algorithm Sorting  2of 2 votes
AnswersRound 4
 sonesh in United States
Question 5 : Question 5 : Do you know A/B testing ?, when we tell you some result of an experiment, how do you know the results are accurate ?, actually this question was about the statistics, he asked me many questions to check my statistics knowledge ? Report Duplicate  Flag  PURGE
Microsoft Software Engineer / Developer Brain Storming Data Mining Math & Computation Matrix Probability Testing  1of 3 votes
AnswersRound 4
 sonesh in United States
Question 4 : You are given following input
Input{userId, LoginTime}
You have ping output in following way
Output(UserId, LoginTime, SessionId).
Note that the session Id is an integer, and when a user login after 30 minutes of its previous login, you will give him/her next sessonid.
new user, will always get next sessionId.
Example
Input
1 9:00 AM
2 9:10 AM
1 9:25 AM
30 12:34PM
23 3:09 PM
Output
UserId LoginTime SessionId
1 9:00 AM 1
2 9:10 AM 2
1 9:25 AM 1
30 12:34PM 3
23 3:09 PM 4
You have to do it in either SQL/Scope. You also have to minimise the complexity. Report Duplicate  Flag  PURGE
Microsoft Software Engineer / Developer SQL  1of 1 vote
AnswersRound 4
 sonesh in United States
Question 2 : Why are you switching your job ?, why our team ? Report Duplicate  Flag  PURGE
Microsoft Software Engineer / Developer General Questions and Comments  1of 1 vote
AnswersRound 3
 sonesh in United States
Question 2 : You are given a array of integers, array may have duplicates, you have to find out the rank k number, and then print out the k highest numbers ?
Required complexity is O(N) + O(1) space, duplicates may be an issue, on which she wanted me to put more focus. Report Duplicate  Flag  PURGE
Microsoft Software Engineer / Developer Algorithm Arrays Data Structures  1of 1 vote
AnswersRound 3 (taken by SOFTWARE ENGINEER 2)
 sonesh in United States
Question 1 : How are you ?, Tell me about your career achievements, Tell me about one of the project you are proud of ?. Report Duplicate  Flag  PURGE
Microsoft Software Engineer / Developer General Questions and Comments  0of 0 votes
AnswersRound 2
 sonesh in United States
Question 3 : You have to implement an external iterator which iterate the binary tree InOrder. You have to figure out what kind of iterator one should use, and implement each of those function. required complexity is O(N) time + O(log(N)) space Report Duplicate  Flag  PURGE
Microsoft Software Engineer / Developer Coding Data Structures Trees and Graphs  1of 1 vote
AnswersRound 2
 sonesh in United States
Question 3 : You are given following set of tables
Object{obj_id, obj_name,....<Other object related details>}
Attribute{att_id, att_name,....<Other attribute related details>}
ObjectAttributeMapping{objAtt_id, obj_id, att_id, att_value}
You have to provide the output in following format
Output table with column name {obj_id, obj_name, att_name1, att_name2, att_name3,...}
each object should only be represented in one row, and att_name1 column will have att_id1 values, from ObjectAttributeMapping table, similarly att_name2 column will have value of att_id2 from ObjectAttributeMapping etc...
Note that you have to do this in either SQL/Scope.
Example
Object
obj_id obj_name
1 cube
2 square
3 matrix
Attribute
Att_id Att_name
1 color
2 height
3 length
4 width
ObjectAttributeMapping
objAtt_id obj_id att_id att_value
1 1 1 'red'
2 1 2 10
3 1 3 12
4 1 4 5
5 2 1 'green'
6 2 2 6
7 3 3 5
8 3 4 9
Output should be
obj_id obj_name color height length width
1 cube 'red' 10 12 5
2 square 'green' 6 null null
3 matrix null null 5 9 Report Duplicate  Flag  PURGE
Microsoft Software Engineer / Developer SQL  1of 1 vote
AnswersRound 2
 sonesh in United States
Question 2 : You are given following two tables,
Customer{cust_id, cust_name, ...<Other customer related details>}
Order{order_id, order_name, cust_id, ...<Other order related details>}
You have to provide the output in following format.
cust_id, cust_name, [Total amount of orders]
Please note that you have to do this in SQL/Scope, and print only those customer who have at least one order. Report Duplicate  Flag  PURGE
Microsoft Software Engineer / Developer SQL  2of 2 votes
AnswersRound 2(taken by PARTNER SCIENTIST MANAGER)
 sonesh in United States
Question 1 : How are you ?, What is your interest ?, why you want to change your job and move to our team ? Report Duplicate  Flag  PURGE
Microsoft Software Engineer / Developer General Questions and Comments  3of 3 votes
AnswersRound 1(taken by DATA SCIENTIST 2)
 sonesh in United States
Question 1 : You are given a street map of a city, Every day you travel from your home to work. some day you take bus or someday your our car. Bus fare is also not constant, it may change in future, may increase or decrease ?
you have to find shortest path from your home to your work ?.
Note that : you have to expose this as library, so no custom assumptions. need to find out how you incorporate variable bus fare ?, also it is upto the user to choose between bus and his car ?, in case of bus, you have to minimise the total money, and in case of care, you have to minimise the distance. Report Duplicate  Flag  PURGE
Microsoft Software Engineer / Developer Algorithm Data Structures Trees and Graphs  2of 2 votes
AnswersTech Screening
 sonesh in United States
Question 1 : You will be given a stream of integers, and a integer k for window size, you will only receive the streams integers one by one. whenever you receive an integer, you have to return the maximum number among last k integers inclusive of current entry.
Interviewer was expecting O(N) solution for N asks.
Edits: Interviewer was expecting O(N) Time + O(1) avg case space complexity solution for N asks.
and integers are not given in a array, every time only one integer will be passed as input to your method. Report Duplicate  Flag  PURGE
Microsoft Software Engineer / Developer Algorithm Arrays Data Structures  0of 0 votes
AnswersRound 3
Question 1, you are given a puzzle, You can check the image herehttps://drive.google.com/file/d/0B6TjTCKfTqQThBamxPa0NwNGM/view?usp=sharing
You have to write a program to provide a solution for this.
 sonesh in United States Report Duplicate  Flag  PURGE
Microsoft SDE2 Coding Data Structures Puzzle  0of 0 votes
AnswersRound 2
 sonesh in United States
Question 1: Design a traffic signalling system for a city.
1.a : think as you were asked this question in a high level meeting with leadership teams, what would you do at that time ?
1.b : what are the checklist/todo you will do before start of your project.
1.c : how will you go over each and every checklist/todo
1.d : Once you have done all this, what are the design principle you will follow.
1.e : what kind of system you would choose(I gave distributed/centralized)
1.f : Tell me the pros and cons of these type which you have listed
1.g : how do you go over your goal.
1.h : how will you make the cons go away from one system which out changing it to another type(like possible modification).
1.i : How will to achieve your goal which was given to you by LT team.
1.f : Now lets write the code for a road intersection, make it generic enough both in terms of colors, and ordering, so what it can be used anywhere.
Note that : a road intersection may have many traffic lights one for each side of the roads Report Duplicate  Flag  PURGE
Microsoft SDE2 Coding Data Structures Software Design System Design  0of 0 votes
AnswersRound 1
 sonesh in United States
Question 1.a
You are given a stock market feed of a single stock.
It contains the change over the previous value. you have to find out the max gain one can get out of it.
Example : 1, 2, 6, 5, 3 7, 3
Days 0 1 2 3 4 5 6
Answer is buy before day 1 and sell it after day two.
WAP for this.
Question 1.b : How do you make the changes in previous code to return the maximum loss. Please note that the changes should be minimum only.
Question 1.c: Lets undo the Question 1.b's additional changes, and now lets you are given a limit on how many days one can hold the money, lets say "k", which means, the investor will give you the money for k days only. you have to again make the additional change to figure out the optimal start date and end date.
Few Example
input : 1 6 10 2 5 20 5 10 6
days 0 1 2 3 4 5 6 7 8
Max Gain : End of first day to end of 6th day, amount is 32.
Max Loss : End of 6th day to end of 7th day, amount is 10.
if K is 3 then the max gain is 25, which is end of 4th day to end of 6th day.
Edits : Interviewer was expecting O(N) solution here. Report Duplicate  Flag  PURGE
Microsoft SDE2 Algorithm  0of 0 votes
AnswersTech Screening round
 sonesh in United States
Q.1 : a non decreasing sorted array is rotated by some random amount, write a routine to figure out this random amount.you can consider the clockwise rotation.
Write the test cases for it.
Interviewer wanted to see prod ready code. Report Duplicate  Flag  PURGE
Microsoft SDE2 Algorithm Arrays Coding  0of 2 votes
AnswersRound 3 :
 sonesh in India
Q 6 : You are given a ternary tree (a tree with 3 children at max with left, middle, right pointer at each node), create a singly linked list from it without using extra space ? Report Duplicate  Flag  PURGE
Microsoft Software Engineer / Developer Algorithm Data Structures Linked Lists Trees and Graphs  3of 3 votes
AnswersRound 3 :
 sonesh in India
Q 5 : You are given a binary search tree, and a value(data item), you need to tell the left most right cousin in as minimum time and as minimum space ?(need to minimize actual time complexity, he need minimum order of complexity as well as number of node access should be minimum) Report Duplicate  Flag  PURGE
Microsoft Software Engineer / Developer Algorithm Data Structures Trees and Graphs  3of 7 votes
AnswersRound 3 :
 sonesh in India
Q 1 : How are you ?
Q 2 : Do you want to go for MS or PHD ?
Q 3 : What type of branch is yours ?(actually my branch name is mathematics and computing, and after 3 year Microsoft allowed our branch to appear for placement, so they ask this question)
Q 4 : One question is from my project “Garbage cleaner Robot” ? Report Duplicate  Flag  PURGE
Microsoft Software Engineer / Developer General Questions and Comments  1of 1 vote
AnswersRound 2 :
 sonesh in India
Q 3 : you are given some nodes, and for each node a probability is given which will tell its importance, you need to design an efficient data structure such that the expected search time as minimum as possible. (Hint : Use dynamic programming + binary tree). Report Duplicate  Flag  PURGE
Microsoft Software Engineer / Developer Algorithm Dynamic Programming Trees and Graphs  0of 0 votes
AnswersRound 2 :
 sonesh in India
Q 2 : You are given finitely many intervals in 1D, you have to design a data structure an efficient data structure which can answer queries of the form “In how many intervals the point P belong ?”, P is an input point, and all intervals are closed. I answer B tree(think why) which is most efficient. Report Duplicate  Flag  PURGE
Microsoft Software Engineer / Developer Algorithm Data Structures Dynamic Programming Probability Trees and Graphs  1of 1 vote
AnswersRound 2 :
 sonesh in India
Q 1 : You are the supervisor of an airport. What happens is that visitors are not visit your airport, instead they go to another one, which means your airport become unpopular nowadays, Now as a supervisor you need to find out what has happens ?, What went wrong ?,How do you find out ?, What is correct ?, How do you find correct one and at what cost ? Report Duplicate  Flag  PURGE
Microsoft Software Engineer / Developer Algorithm Behavioral Data Mining Data Structures Experience Ideas Probability Application / UI Design  0of 0 votes
AnswersRound 1 :
 sonesh in India
Q 3 : What do you think, how the posts in Facebook are shown, to your page, as there are thousands of posts, likes, videos, images, links etc. shared by your friends, but not all are shown to you ? (Data mining question, have to tell appropriate solution which can work ?) Report Duplicate  Flag  PURGE
Microsoft Software Engineer / Developer Algorithm Data Mining Data Structures  0of 0 votes
AnswersRound 1 :
 sonesh in India
Q 1 : When you visit on your friend’s Facebook profile, there is a mutual friend section where common friends are listed, now let’s assume that your friend do the same thing, he/she visit his/her friend other then you, now the people other than common are connected to you by distance of two. Similarly think you are given two people on Facebook, how do you find this connectivity?. (Please give appropriate solution),
Now let’s think that some important people are given some weight(any), now do the same thing ?
Now calculate the most influential person? (Not an easy question, because of weights) ? Report Duplicate  Flag  PURGE
Microsoft Software Engineer / Developer Algorithm Data Mining Data Structures Trees and Graphs  0of 0 votes
AnswersDesign a data structure for LRU where replacement can take up to O(log n ) time, searching take O(log n) time, inserting will also take only O(log n) time(Big question, I was given some time(around 5 to 10 minute) to think) ?
 sonesh in India for Strategies Group Report Duplicate  Flag  PURGE
Goldman Sachs Software Engineer / Developer Operating System  0of 0 votes
AnswersWhat is virtual memory, how operating system uses it ?
 sonesh in India for Strategies Group Report Duplicate  Flag  PURGE
Goldman Sachs Software Engineer / Developer Operating System  1of 1 vote
AnswersHow can we reduce search time in linked list(reduce time complexity to O(log n), it is not given but I gave my answer with O(log n) complexity) ?
 sonesh in India for Strategies Group Report Duplicate  Flag  PURGE
Goldman Sachs Software Engineer / Developer Algorithm Linked Lists  0of 0 votes
AnswerDraw a simple model of a Program Control Block ?, Now write a simple code and show all the sections in the code (means when this code will run then which section of the code go where in PCB) ?
 sonesh in India for Strategies Group Report Duplicate  Flag  PURGE
Goldman Sachs Software Engineer / Developer Application / UI Design  0of 0 votes
AnswersPrint a binary tree without using recursion(inorder print) ?
 sonesh in India for Strategies Group Report Duplicate  Flag  PURGE
Goldman Sachs Software Engineer / Developer Algorithm  0of 0 votes
Answersgiven an array of positive integers and that you are allowed to change the sign of any of the integers whenever you require.
write a program to calculate the minimum sum of this array.
the sum should be >=0.
for example :Array = {1,2,4,5} then sum = 0 as we change sign of 1 and 5{1,2,4,5
}
Another Example :Array = {1,2,4,5,6,17,20}, sum = 1 with {1,2,4,5,6,17,20
}
 sonesh in United States Report Duplicate  Flag  PURGE
InMobi Software Engineer / Developer Algorithm
The question says that, you are given n nodes, each node have probability associated with it, lets say node *A* have probability *P*, here P is the probability that in one search element A is searched. for example i have 3 element, "a,b,c" with "2/4,1/4,1/4", this means if i do 4 searches then 2 times i will ask for a, one time b and one time c,
Now you need to give me a data structure where expected search time is minimum
@zyfo2 : yes BFS is good for first question only, what about others
@lxduan :
consider the case when you have two people having equal number of edge connectivity, and there total weight sum are equal, does it mean that they are equally influential person, what if one person (out of two) is connected with the persons having more edge connectivity, and another person connected with persons having less edge connectivity,
for example A, B are two person
A connected with A1 and A2
B connected with B1 and B2
weight(A1) + weight(A2) = weight(B1) + weight(B2)
but A1 and A2 are connected with 10, 15 other people, and B1 and B2 are connected with 5 , 6 other people, then according to you both A and B are same influential person but they are not, actually A is more influential person then B, now to tell us your solution ?
Here is my algo :
j,k;
for i from 2:N1
j=0;k=i1;
while(j < k)
if(A[j]*A[j] + A[k]*A[k] < A[i]*A[i])
j++;
else if(A[j]*A[j] + A[k]*A[k] > A[i]*A[i])
k;
else
break;
print i,j,k;
Now as you can see, any Pythagorean triplet the 2nd larger number is much nearer to largest, and smallest number is much smaller to 0, so the loop will run very less, or i can say for const(ya i know in some cases the loop might run for n/3 many cases also). amount of time for any "i", so here i can say , that on an avg. the complexity somewhat less then O(n*n)
 sonesh November 27, 2012then how the complexity comes to be O(n+h) it would be O(n*h), because you gonna calculate frequency of a number and then calculate frequency in another array, if they are equal, then you increment element then again do the same for this element also.
as you said that you are not storing the frequencies(as it is restricted), so your complexity goes to O(n*h) not O(n+h)
@eugene.yarovoi, min heap actually require worst case 2n and average case 1.5n complexity, Heap is min heap, so every time if a element if bigger then this min element then we replace it with new element and rebuild heap, this rebuild require either 1 step or 2 step only. so heap is much better then having a array of 4 element, where worst case complexity can goes to(is more likely also, you can calculate the probability distribution also(like p(i),where p(i) is the probability that next would we placed at ith location.)) 4n.
 sonesh November 25, 2012Yes, we use minheap but if n is much larger (around 1 million )then the heap will be a generalized heap.
Now when we get a new element we insert it a the bottom,(at the end), then we build it again, and we remove the last element. the same procedure follows for all element. Which means for one element costs us O(log(n)) complexity. Now when we extract element from heap, then we only extract the top element, then we replace the last element with it, then rebuild the heap on n1 element, then again top and again the same procedure, So if we extract k data then we need O(k*log(n)) complexity.
Here extract means we remove that element from heap.
Now we only want to view the element then also we can do the same procedure, where the last position will be used to store the topmost entry,(nth entry of array(starts from 1)).
with Dynamic programming I have implemented it in O(n^3) + O(n^2) solution,
the solution is similar to matrix chain multiplication solution, where we calculate M(i,j){minimum possible sum when we consider the subarray starting from "i" and ends with "j"}, But the minimum value computation will be different.
More clarifications : Hash key "Line" means two coordinates of line, Now you have to tell how the hash function actually determine whether the given line is already present or not ?
certainly not by "slope", and obviously not by two coordinates, So How ?
another thing is that in worst case there can be O(n*n) many lines present, similar solution is given by(most trivial one) @USTChucat(complexity : O(n*n*n))
but anyways, good starting..!
We have given MAT[][] as the information of the 10x10 grid, information are like where are snake, or where are ladders, etc.
B is just an abstraction of matrix MAT into an array, where the index conversation is done by B[i] = MAT[j][k], where i = 10*(j1) + k, in simple scene it is just to consider the matrix as an array.
A[i] will give you minimum number of dice rolling require to reach at i(1<=i<=100)
And expectation is in terms of probability, but it is not required here.
Use dynamic programming :
Following is the algorithm :
Let B[100] is the matrix(I am representing the matrix(10*10) as an array(with Mat[j][k] = B[i] where i = 10*(j1) + k))
A[1] = 1;A[2] = 1;A[3] = 1;A[4] = 1;A[5] = 1;A[6] = 1;
for i=7:100
if B[i] != 1 // 1 to represent snake
A[i] = A[i1] + 1;
for j=i2:i7
if A[i] > A[j] + 1
A[i] = A[j] + 1;
else
A[i] = MAX /// this is to ignore the value when we calculate minimum.
return A[100]
Here we don't have to consider expectation, as we only need to tell minimum number of dice rolling,
 sonesh November 22, 2012The problem is very similar to matrix chain multiplication, the only difference is the calculation of new comparison from previous ones.
Now look at it very carefully, it is clear that we need to use DP, and in DP also we need to calculate(remember) a matrix. Now because the not a be placed at any position from i to j (if we are calculating MAT[ i ][ j ]), so the complexity will go to O(N*N*N)
Now Here is the algorithm :
M[i][j] = min(p[k] + M[i][k1] + M[k+1][j] + sum(M[r][r] for r=i:j) for k=i:j), please consider boundary conditions,
we set M[i][i] = p[i], not that firstly we sort the array of number and maintain their corresponding probabilities also(sort can be in any order).
For example like above construct a upper diagonal matrix, here each entry actually store the comparisons only. Now if you want to construct the tree, you need another matrix(B od same size which store node data), which tells who to be chosen as parent node at each place, so M[0][N1] will give you cost and B[0][N1] will give you root node.
Please let me know if am not clear..
The algorithm will work with slight modification,
1) it should consider of swapping all from {2^i to 1} in boundary condition only.
for example : consider the case of 6 element :
1 [2] 3 [4] 5 [6]  {a} b {c} d {e} f
1a [3c] 5e{2b} 4d {6f} < this will not be swaped as there is not matching block to which it can swap this is a modification
1a 2b [5e]{3c 4d} 6f < here [5e] is the only left block so it will choose it, this is a modification.
1a 2b 3c 4d5e 6f
Now consider the case of 7:
1 [2] 3 [4] 5 [6] 7  {a} b {c} d {e} f {g} < {g} will not be swapped
1a [3c] 5e [7]  {2b} 4d {6f} g < [7] wil be swapped here(remember the modification)
1a 2b [5e 6f]  {3c 4d} 7g
1a 2b 3c 4d 5e 6f 7g
ya but it require O(n*log(n)) + O(1) complexity
 sonesh November 22, 2012One condition : data item should be either integer, or float, or char. but not string, or others
then what ever @Abhijit has written is correct, for implementation use following
void swap(Node *N1, Node *N2)
{
N1>data = N1>dataN2>data;
N2>data = N2>data + N1>data;
N1>data = N2>dataN1>data;
}

sonesh
November 22, 2012 @Name , please consider following points
1) It is not a singly linked list
2) your algorithm require o(n*n*n) time, because you are scanning the list n times, in worst case list size size may be reduced by just 1, and then searching in the tree for parent node, that can also require O(n) time in worst case, so total count to O(n*n*n) complexity, certainly not excepted
3) How can you move in singly list from right to left, without using recursion
4) If you are doing it like deleting node from list and inserting into BST, then this will not be excepted at all as per your question because by deletion we can't delete pointer, we only able to delete not data there always be a pointer which is remaining their, If not then, you have to explain how you can move in the list, (one solution could be add element at beginning of list and keep a pointer which tells the start point)
5) and may be more

sonesh
November 22, 2012
RepJames Gulledge, Dev Lead at ADP
Get you driving in comfort and class in Atlanta! Prestige Luxury Rentals offer a wide selection of premium vehicles Our ...
Open Chat in New Window
This is a solution but not optimum one,
 sonesh January 14, 2013