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
here is the solution
ConvertToInt(inputStr)
length < inputStr.Length
if length > k // k is the size of the maximum integer
Overflow;return;
multiplier = 1;
output = 0;
maxLastNum = r;
for i = length; j > 1; j 
output = output*multiplier + Int(inputStr[i]);
multiplier = multiplier * 10;
if Int(inputStr[length]) > maxLastNum OR Int(inputStr[length])*multiplier > MaxIntoutput
Overflow;return;
else
output = output*multiplier + Int(inputStr[length]);
return output

sonesh
June 06, 2015 Here is the solution
Current <= Root;
while(Current is not null)
if Current > left is not null
Current = Current > Left;
else
Print Current.Value
Current.Printed = true;
If Current > Right is not null
Current = Current > Right;
else
Current = Current > Parent;

sonesh
June 06, 2015 Here is the complete solution for the problem
Please note that, the author has emphasized on the size of data, so we will store the photographs in external memory only.
here is the background and assumptions behind the algorithm
We will use B+ tree to implement this, where all the internal nodes only store the indexes and all the terminal node stores the real data(the photographs)
The indexes will stay in the main memory only where the assumption the indexes can stay in the memory(primary memory), if not, we have to save the indexes also into the secondary memory, which will increase few I/O operations.
we will keep two trees, one to store normal images and another to store favourites
Here is the algorithm for Search(t)
Search(t)
Figure out the memory block where the photographs are stored which are inserted after t both from normal tree and favouritetree.
Node = T.Root;Directive = Next_Comparison_Directive(null); // return year
while(true)
If Node.IsDevisionPresent
Node = Node.Child_a ? Node.Child_a.Year = t.Year(can use BST to figure out the child, as not Year have the child)
Directive = Next_Comparison_Directive(Directive); // return in following order Year > Month > Day > Hour > Minute > Second > MillSecond as so on
else
read Node.Photograph block from secondary memory(we may have to read two blocks)
break;
After that, you can do the BST to find out an images whose insert time is just next to given t
return the one having minimum time
Here is the algorithm for NextFavourite(t)
NextFavourite(t)
Figure out the memory block where the photographs are stored which are inserted after t from favouritetree.
Node = T.Root;Directive = Next_Comparison_Directive(null); // return year
while(true)
If Node.IsDevisionPresent
Node = Node.Child_a ? Node.Child_a.Year = t.Year(can use BST to figure out the child, as not Year have the child)
Directive = Next_Comparison_Directive(Directive); // return in following order Year > Month > Day > Hour > Minute > Second > MillSecond as so on
else
read Node.Photograph block from secondary memory(we may have to read two blocks)
break;
After that, you can do the BST to find out an images whose insert time is just next to given t
return the image.
Here is the algorithm for Insert(x,t,m)
Insert(x,t,m)
Based upon m decide the tree;
Figure out the memory block where the photographs can be stored with t time.
Node = T.Root;Directive = Next_Comparison_Directive(null); // return year
while(true)
If Node.IsDevisionPresent
Node = Node.Child_a ? Node.Child_a.Year = t.Year(can use BST to figure out the child, as not Year have the child)
if(Node is null or no node exists, add a new child to parent node with directive value, and insert this new data into the block of this new node).
Directive = Next_Comparison_Directive(Directive); // return in following order Year > Month > Day > Hour > Minute > Second > MillSecond as so on
else
read Node.Photograph block from secondary memory(we may have to read two blocks)
break;
insert the entry at proper location in bst.
while(node is full) // means the block size is full
set Node.IsDevisionPresent = true;
figure out distinct count of Directive time units from the block;
Create one child for each, and set there IsDevisionPresent = false;
set the list of photographs into each of the child based upon the Directive.
If any of the node is full(actually there will be one only)
set node = node.child which is full.
else
save all the nodes block to secondary memory.
break;
Complexities
Search
Time : Constant(which is the search time) + 4.Log(M), where M is the a memory block size + 4 I/O
NextFavourite
Time : Constant(which is the search time) + 2.Log(M), where M is the a memory block size + 2 I/O
Insert
Time :
Best case : Constant(which is the search time) + Log(M), where M is the a memory block size + 2 I/O, which occur most of the time,
Node spiting case : Constant(which is the search time) + Log(M), where M is the a memory block size + M.I/O
With little modification, we can reduce Node spiting case Complexities to the best case, we can maintain Min and Max insert time of photos which are residing in a block at last internal node(which are just above the terminal node)
Space : O(N) : size of the input in secondary memory + constant size of internal memory.

sonesh
June 05, 2015 Here is what i think of a solution for this problem
First we define the structure of a straw.
Class Straw
{
int X_1, Y_1;// this is to repersent first coordinate of the straw
int X_2,Y_2;//secon coordinate
}
Now we are given N list of straws as input.
Lets first define how two straw are connected to each other or not(we can consider this problem as to figure out whether two lines of 2D are intersecting/touching each or or not).
We are use the Cross product to figure out this.
bool IsIntersect(Straw a, Straw b)
Define P1 = (a.X_1,a.Y_1);P2 = (a.X_2,a.Y_2);
P3 = (b.X_1,b.Y_1);P4 = (b.X_2,b.Y_2);
we can use following cross products to figure out whether these two straws intersecting/touching each other or not
If Cross_Product(P1P2, P1P4) and Cross_Product(P1P2,P1P3) are apposite to each other and Cross_Product(P3P4, P3P1) and Cross_Product(P3P4,P3P2) are also apposite to each other then these two straws are intersecting, other wise if any of the cross_product is zero, which is the case when these two straws are touching each other or are their in a single line, then we just check the vertices of other lines, if any one of thems((p1 or p2) or (p3 or p4))'s x and y coordinate lies between other line's coordinetes.
Now we will start the actual execution.
We will keep three array of indexes, one which will have indexes straws in non decreasing order x coordinate
other two will have non decreasing order of y coordinate of first and second vertices.
now we will figure out the connected component.
Please note that any straw from one connected component will only touch/intersect other straws of the same component.
Here is the algorithm
A < Input straws
Index_x < indexes in nondecreasing order of min of x(from both the vertices of a straw)
Index_y_1 < indexes in nondecreasing order of y_1
Index_y_2 < indexes in nondecreasing order of y_2
In index_x, we also keep one flag to tell whether something is left to try or not
keep a queue Q = empty(normal queue)
while(something left in index_x to try)
take the first untried index, call it j, set tried flag to true;
figure out the list of straws which may intersect/touch with straw j
We can figure out by first figure out the list of untried straws using index_x, where index_x's straw's min x <= j' straws max x.
then we will also figure out the list of untried straws using index_y_1 and index_y_2.where ay straws whose either first y coordinate or second y coordinate lies between J's straws min y and max y coordinate.
we will put all these straws in the Q
while(Q is not empty)
straw_k < Dequeue();
if straw_k and straw_j are connected, then insert k into an array, and set k as tried
figure out all the possible untried straws which may intersect with k using above logic and insert them also into the queue
insert a seperator into the array to defferenciate between connected component.
print the connected component and any two straw from a connected component are touching/intersecting each other directly or indirectly.
the complexity is :
Time : O(n * log(n)) for sorting + O(n * k * log(n)) where k is degree of connectivity of straws,
space : O(n), or more preciously 5N.

sonesh
June 05, 2015 I think, we don't have to actually retate the string, we can just use index update to treat the string rotated for users, Here is one of the example
A < Input String
Current Start index = 0, EndIndex = A.length
If user ask us to rotate the string left by 2, we can update the
start_index to 2
, and
end_Index to 1
, the next index calculation can be done with modulo operation. this code assume string as array of char, but will work fine with normal string variable as well.
Here is the complete set of the code in c#
private static void PrintWithRotation(string inputStr, int rotationCount, string rotationSide)
{
int length = inputStr.Length;
Console.WriteLine("Printing the input string with {0} {1} rotation", rotationCount, rotationSide);
rotationCount = rotationCount % length;
int startPoint = rotationSide == "left" ? rotationCount : length  rotationCount;
for(int i = startPoint;i<length;i++)
{
Console.Write(inputStr[i]);
}
for (int i = 0;i < startPoint;i++)
{
Console.Write(inputStr[i]);
}
Console.WriteLine();
}

sonesh
June 05, 2015 The optimal single threaded solution can be described something like this
implement a routine, which given l element between i,i+l indexes of an array, sort this l size subarray using inplace l x log(l) time algorithm.(options are : heap sort, or quick sort with proper pivot).
Once we have this routine, we can call it n/k times to sort the whole array as explained by @pc.
I am presenting the multithreaded algorithm which can solve this problem in n/r x log(k) time with r as maximum threads systme can allocate to this program.
A < input array, k is the condition as per this question
Step : 1
do Parallel for j = 0; j < n; j = j + 3k
sort(A, j, j+3k1)
Step : 2
do parallel for j = 2; j < n; j = j + 3k;
sort (A, j, j + 2k 1)
I havn't considered the edge cases in both the steps for simplicity, and btw they can only add upto O(k x log(k)) more complexity to the total complaxity.
one can easily check that given r threads, both the steps will only take O(n/r x log(k)) time.
Here is the implementations in c#
We first define the the element class which will have queue element
public class Element
{
public int priority;
public int value;
}
once we have defined the element class, we initialise the queue, and define some common parameters for the queue
public static Element[] minQueue { get; set; }
public static int queueCurrentSize { get; set; }
public static int maxQueueSize { get; set; }
Then we ask use to input the max size of the queue, as we have to define some size for it, although there exits some implementations where the element is added to the queue on the fly, but we have to bear the computational burden, which is heigher, so, mostly you will find that the queue implementation need the size.
After this, we ask user to take an action which he/she want to perform on the queue
Console.WriteLine("Following Action can be taken on the priority queue");
Console.Write("Extract Min(Choose Action : EM){0}Insert(Choose Action : I){0}Get Min(Choose Action : GM){0}Queue Size(Choose Action : QS){0}Print Queue(Choose Action : PQ){0}Clear Queue(Choose Action : CQ){0}Exit(Choose Action : Exit){0}Choose Your Action : ", '\n');
while (true)
{
string action = Console.ReadLine().Trim();
if (action.Equals("EM", StringComparison.InvariantCultureIgnoreCase)
 action.Equals("I", StringComparison.InvariantCultureIgnoreCase)
 action.Equals("GM", StringComparison.InvariantCultureIgnoreCase)
 action.Equals("QS", StringComparison.InvariantCultureIgnoreCase)
 action.Equals("PQ", StringComparison.InvariantCultureIgnoreCase)
 action.Equals("CQ", StringComparison.InvariantCultureIgnoreCase)
 action.Equals("Exit", StringComparison.InvariantCultureIgnoreCase))
{
return action.ToUpperInvariant();
}
else
{
Console.WriteLine("Choose correctly please");
}
}
Once we have the input action from the user, we can use the switch statement to choose between actions and make correct function call
actionTaken = GetUserAction();
switch(actionTaken)
{
case "EM" :
Extract_Min();
break;
case "I" :
Insert();
break;
case "GM" :
Get_Min();
break;
case "QS" :
Console.WriteLine("Queue current size is : {0}",queueCurrentSize);
break;
case "PQ" :
Print_Queue();
break;
case "CQ":
Clear_Queue();
break;
case "EXIT" :
Console.WriteLine("Exiting");
return;
default :
Console.WriteLine("Exiting due to some problem");
return;
}
Here are the implementations of eah of these functions
1) Clearing the queue
private static void Clear_Queue()
{
Console.WriteLine("Clearing the Queue");
queueCurrentSize = 0;
}
2) Printing the queue
private static void Print_Queue()
{
Console.WriteLine("Queue contains following elements");
for(int i = 0; i < queueCurrentSize;i++)
{
Console.WriteLine("(Value : {0}, Priority : {1})", minQueue[i].value, minQueue[i].priority);
}
}
3) Getting the minimum priority element
private static void Get_Min()
{
if (queueCurrentSize > 0)
{
Console.WriteLine("The min priority element is : (Value : {0}, Priority : {1})", minQueue[0].value, minQueue[0].priority);
}
else
{
Console.WriteLine("The queue is empty");
}
}
4) Extracting the minimum(or deleting the minimum priority element)
private static void Extract_Min()
{
if (queueCurrentSize > 0)
{
Element minElement = minQueue[0];
minQueue[0] = minQueue[queueCurrentSize  1];
queueCurrentSize = queueCurrentSize  1;
MaintainTopToButtomQueue();
Console.WriteLine("The extracted min priority element is : (Value : {0}, Priority : {1})", minElement.value, minElement.priority);
}
else
{
Console.WriteLine("The queue is empty");
}
}
private static void MaintainTopToButtomQueue()
{
int parent,lowest,leftChild,rightChild;
parent = 0;leftChild = 1;rightChild = 2;
Element temp = new Element();
while (leftChild < queueCurrentSize)
{
if (minQueue[parent].priority <= minQueue[leftChild].priority)
{
lowest = parent;
}
else
{
lowest = leftChild;
}
if (rightChild < queueCurrentSize && (minQueue[lowest].priority > minQueue[rightChild].priority))
{
lowest = rightChild;
}
if (lowest == parent)
{
break;
}
else
{
temp = minQueue[parent];
minQueue[parent] = minQueue[lowest];
minQueue[lowest] = temp;
parent = lowest;
leftChild = 2 * parent + 1;
rightChild = 2 * parent + 2;
}
}
}
5) Inserting new elements
private static void Insert()
{
if (queueCurrentSize < maxQueueSize)
{
int value, priority;
string strValue, strPriority;
Console.WriteLine("Please enter the details of the element(write exit to go to main queue options)");
Console.Write("Value : ");
while(true)
{
strValue = Console.ReadLine().Trim();
if(strValue.Equals("exit",StringComparison.InvariantCultureIgnoreCase))
{
return;
}
else if(!int.TryParse(strValue,out value))
{
Console.WriteLine("Enter correctly please");
}
else
{
break;
}
}
Console.Write("Priority : ");
while (true)
{
strPriority = Console.ReadLine().Trim();
if (strPriority.Equals("exit", StringComparison.InvariantCultureIgnoreCase))
{
return;
}
else if (!int.TryParse(strPriority, out priority))
{
Console.WriteLine("Enter correctly please");
}
else
{
break;
}
}
Element element = new Element { value = value, priority = priority };
queueCurrentSize = queueCurrentSize + 1;
minQueue[queueCurrentSize  1] = element;
MaintainButtomToTopQueue();
}
else
{
Console.WriteLine("Queue is full, please extract some entries first");
}
}
private static void MaintainButtomToTopQueue()
{
int parent,child;
child = queueCurrentSize1;
Element temp = new Element();
while (child > 0)
{
parent = Convert.ToInt32(Math.Floor((1.0*child  1) / 2));
if(minQueue[parent].priority > minQueue[child].priority)
{
temp = minQueue[parent];
minQueue[parent] = minQueue[child];
minQueue[child] = temp;
child = parent;
}
else
{
break;
}
}
}
we can add more functionalities to the queue like increasing/decreasing the size of the queue, performing the shorting, etc.
 sonesh June 05, 2015Here is the concept :
Start calculating sum from leaf node, and move to root node,
Maintain a minimum weight variable, with a node variable which store minimum weighted node
int minweight(node curr)
{
int left = 0,right = 0;
if(curr)
{
left = minweight(curr>left);
right = minweight(curr>right);
if(MIN > left + right + curr>data)
{
MIN = left + right + curr>data;
NODE = curr;
}
return left + right + curr>data;
}
return 0;
}
output NODE
Complexity : O(n)+O(1), nut require O(height of tree) size run time stack.
We create a tree data structure,
the tree is a general tree with at max 26 children, and
each node also store a bool variable(is used for telling weather number present here or not) and a string (used to tell contact number along with code number).
and choose child function(which uses char to identifies the children)
Here is insert methods
we start with root node, and move from root node to children's according to each char.
for example if user name is "sonesh", then from root node it go to "s"th children, then from "s"th node it go to "o"th children and so on.
when we reach to "h"th node,
In this if at any point we does not get require children, then we create that children, and move to that children.
we set bool variable to true,
and set string variable to sonesh's number.
Now we can easily able to extend it to have multiple contacts with same name, or we can easily able to restrict it, Here we can also consider "space" as a char.
Now get contact can also be implemented very easily,
Here both insert and get have constant complexity(O(1)).
This question may be asking for less then O(n) space algorithm.
Here is the algorithm :
Lets Node definition is
struct Node
{
int data;
Struct Node *left;
Struct Node *right
};
Tree is struct Node *Root;
Now we do following
int ISBST(Node *curr,bool dir);
{
int max = ISBST(curr>left,0);
int min = ISBSDT(curr>right,1);
if max <= curr>data <= min //Here we also have to check for one child nodes leaf node
if dir == 0 for left node
return min;
else if dir == 1 for right node
return max;
else
stop all function, and report not BST;
}
We call this function with curr as root>left and root>right, and check for root, and report.
The complexity of this algorithm is O(n)+O(1),
but as quick sort algorithm, it also require O(height of tree) space in run time stack.(which is not considered generally)
We can have better implementation of this algorithm.
Can you please read the algorithm once again.
M[1] is not that number, it is A, which may be M[1], or may be other.
like here :
1st step : C = 1, A = 5,
2nd step : C = 0, A = 6, which make C = 1, A = 7;
3rd step : C = 2,A = 7;
4th step : C = 3,A = 7;
5th step : C = 4,A = 7;
Now check weather A = 7 is that number, And in this example it is.
Here is the concept :
If a number is lies more then half, then if we increment a counter when that required numbe comes and decrements the counter when any other number come ,then at the end the counter will have positive value.
Now in the problem, even if we have worst case, the counter will be +1, when for every other number we give one valid number, but for a general case, number from other one can also contribute from canceling their effect.
Use a counter (C = 0)and a integer variable (A),
M[1 to n] is given array
C = 1;A = M[1];
for i = 2 to n
if M[i] == A;
c++;
else
C;
if(c == 0)
i++;
if(i > n)
output 1;
C = 1;
A = M[i];
if C > 0
check weather A is that number,
else
output 1;
complexity : O(n) + O(1)
 sonesh March 19, 2013@showell : If the numbers have any kind of relation between them, then they are not random, the term random is define in this way that we can't predict them, they can't follow any pattern even when some one draw infinitely many,
Now there is no way to generate perfect random number, all random number generator(I mentions above), generates only sudo random numbers, but as our computer are not powerful enough to find any patterns in these sudo random numbers, so we generally accept them.
We create following data structure
create a b+tree like structure, where we use date to create child,
at first level we use year,
second level we use months,
and at third level we use day,
and then to hours.
Now these are standard, we join these hours node by linked list. so that we can move easily to another hours.
After that we create categories for URL's, It may be domain's.
here actually we create a trie kind of structure to store URL's in minimum space, and to improve search.
Now the first part is used to find from where to where,we have to search. and once we find interval in tree, we go searching and print output.
One simplest solution is :
Generate sudo random number, using any methods(such as linear congruential generators, Fibonacci generators), or can use inbuilt method. call it x
hash it, if already present then try again, otherwise store it in array, and set hash function true.
Obviously here we require O(n) space, and they will not be following uniform distribution.
 sonesh March 16, 2013We create a skip list, we store data page wise in linked list, and above we create a tree kind of structure,(google skip list for more info), here the insertion time is O(log(#page)) per page.
Insertion procedure :
Here each page is half empty,
Now if we get a page which is more then half empty then we just insert it
and if the newly inserted page have less then half data then we merge it with another near page.
or if both nearer page don't have space to store this new page, then we take items from any one of nearer page and make both of then to have more then half data.

sonesh
March 15, 2013 I solve the problem in following ways
Create a b+ tree,use dates are separating elements,
first level is used for year,
second is for months
and third is day,
and at day store each URL by linked list which is both way, after linked list use hash table to directly file the URL,
this is used to maintain the constrain that each url can only comes only once,
actually this does not happens, like in google crome, they don't have above constrain.
Now when every user click on a url ,
first we check weather the clicked url is present or not ?,
if not present then we insert it into tree and create new entry in hash table,
It is like two indices on a database. so data is same for both indices.
Now if url already present then we remove that element from linked list and create new node at first node and join it.
so this require constant time for insertion, searching , deletion etc.
 sonesh March 15, 2013You are right @showell,
In general we have two different organization of memory, one is shared memory and distributed one,
In shared memory we don't need to pass anything, as all cores share same address space, so for that above solution is ok,
But If we have distributed systems, where each core have different their own memory address space, then we do by MPI, here each core actually have to send their data to another core, so their we have two type of cost
1)computation cost,
2) communication cost.
so the computation cost is same but communication cost vary as it depends upon how distributed system are implemented, for example they all might be connected by a common bus, or they may be connected our a network, then again their software implementation also affect the actual cost.
What ever you are saying in last para is actually comes under vector calculation, here we read not only a single data item but a vector of data item, and in message passing interface also, we have optimize in terms of size of packet.
Ok, loler solution is essentially saying the same thing, he uses another way to say the same thing, using these 3 states, actually 1 represent the elt is in first chosen k number, 1 means it is chosen by next r numbers and 0 means is not being chosen, Yes i didn't wrote the code here, I just explain the algo and the property of the problem
 sonesh March 14, 2013Simple solution :
Let A[1 to 26] is array where all entries are zero except the one given as input. and if some char repeat then the corresponding entry tell the number. for example here f's entry will be 2 but a's entry will be 1
Read words one by one
ans = 0;
for each word (w) :
i =0;flag = false;
while(i++ < length of word)
if A[w[i]])
A[W[i]];
else
flag = true;
break;
if flag
go on reading;
else
ans = max(ans,length of current word);
break;
this require O(n) internal memory operation + O(n/B) file I/O where B is the block size, where one block is read by memory at a time.
Now if we do preprocessing, we form trie with each node except leaf contain a single element, now here we need to do every possible searching, for example at root node we need to go to all possible nodes(at max 7 in above example), again at second level we need to choose at max 6 or 7(in f case) and so on....
so complexity here become O(2*7!),although this is a number but in actual computation it is not smaller. for this above example,
Explanation of why we need some sort of relation on cores and threads per core.
Nowadays each core have 2 hardware threads, so we can have 2 threads per core, but more does not give us any benefit, in terms of performance, because each core can run only two thread in parallel(both are mapped to existing hardware threads), when we create more threads, it increase overhead of their creation, their synchronization, coherency and many other, and the switch time of c.p.u. because now same work is done by more threads, so when you create more then 2 thread per processor, it actually reduce performance, (in terms of actual time).
Now to increase performance we increase core, here is the algorithm to sum n numbers with n/2 core.
Let A[1 to n] is the given array
they sum in binary tree form,
example :
...................23
..........12.............11
...6...........6........11
1...5.....2.....4...5...6
at i th thread or at ceil(i/2)th core
read(A[i],a);
write(a,B[i]);
for h = 1 to log(n)
if i <= n/2^h
read(B(2*i1),x)
read(B(2*i),y);
z = x+y;
write(z,B(i));
if i=1
print B(i);
this require O(log(n)) time and O(1) space complexity per core.but overall it require O(n) + O(n),
But here we consider(in parallel program) complexity per core.
Now if number of core are limited, means we can only create let say P threads only then what ?
so here we create (n/P) number set and sum them at each thread which require O(n/p) time then we apply above procedure which require O(log(p))
so total complexity become O(n/p) + O(log(p))
We go by tree,
We consider a tree in which each node can have at max 4 children. and each children contain a range in "x" and "y", which decide weather the value lies in this node or someone else.we go upon the point where each child get only a single point. and we know that here linear case does not exist, always search, delete,insert complexities goes down to O(logn).
The question require DP
here is the algorithm
Let me first draw the matrix here for above example
2 1 0 0 0
1 2 0 0
3 1 1
4 2
2
and output is upper rightmost point whose index is i=0;j = n;
Here is algo
same matrix multiplication DP program with one difference which is here you have to apply abs(sub(M[i][k],M[k][j])) instead of addition and multiplication.
min function is again here,
complexity : O(n*n) + O(n*n)
if we also want to know the sign of each number in the case of minimum sum, then we require one more matrix of size n*n.
I think the problem is NP complete problem and we don't have any polynomial solution we can possibly check for all combination,
so what we need to do is to calculate
choose k numbers and sum them,
choose r numbers from remaining ones and sum them
and calculate difference.
Now this k vary from 1 to N and r vary from 1 to Nk,
so the complexity goes to exponential.

sonesh
March 13, 2013 Let A = max(abs(x),abs(y));
Num = (2*A+1)*(2*A+1);
If (x,y) lies in first quadrant
If x > y
Num = (2*(A1)+1)*(2*(A1)+1) + xy;
else if x < y
Num = Num (yx);
else if (x,y) lies in 2nd quadrant
similarly define here too
and actually this is the function. you give any (x,y) it will give the number correspond to it in this matrix.
complexity is O(1);
n + n/2;where n is total number of monster. here i am assuming 10 A monster and 10 B monster. so h is 20
for example :
6(n) steps from here to
AAA*BBB
AA*ABBB
AABA*BB
A*BAABB
ABBAA*B
*BBAAAB
BBBAAA*
here
now 3(n/2) steps from here to
BBBAA*A
BBBA*AA
BBB*AAA
here
so total is 3*n/2;
We use general tree kind of structure,in which root node is does not contain any any data but it contain pointers between 1 to 9, depending upon numbers distribution.For example suppose India have numbers starting from 9,8,7 then root node contain 3 pointer pointing the sub trees each containing a int data point and at max 10 pointers.
search : O(1);
insert : O(1);
delete : O(1);
If the number can also have different countries then at root node we add an additional layer which tell information's about country code.
this does not increase complexity.
The Algorithm is following
Let A[i=1 to N] is the daily stock price process and initally we don't own any stock.
start = 1;
while(start <= N)
find first element such that next element is bigger then that. set it buying price of stock.
find first element such that next element is lesser then it. set it selling price.
find profit and add it to sum and set new start to selling price element index + 1
For Example : Here in this case we will have {3,7}, {4,11},{4,8} are the buying selling tuples, and net profit is 4 + 7 + 4 = 15.

sonesh
March 13, 2013 Algorithm is here :
Take two pointer P and Q;
Move P twice as Q, and move Q one step at once.
start with P = Head = Q;
Q = Q>next;
P = P>next>next;  check condition of termination(case when no loop)
repeat until P == Q;
Complexity : O(Length of linked list)
Prove is here :
It is easy to see that if the linked list has a loop then after some time both the pointer will be in the loop.
Consider the time when they are in the loop. Now let First pointer is at Ith node, and Second pointer is at Jth node in linked list. Lets assume that node at Ith place is faster one. So Ith node require JI+1 move in order to reach to Jth node, and we know that First pointer is moving 1 node relative to second one.which mean it move one node nearer to second in every step. so in JI+1 step's it will reaches to node second. Hence proved.
Here is the algorithm :
minima( x1, x2)
mid = (x1+x2)/2;M = convex(mid);
lmid = (x1+mid)/2;L = convex(lmid);
rmid = (mid+x2)/2; R = convex(rmid);
If M < R && L
then x1 = lmid;x2 = rmid;
else if M < L && M > R
then x1 = lmid;
else if M < R && M > L
then x2 = rmid;
go to line number 2;
if (x2x1) < 1E10
output (x1+x2)/2;
break;
If function is non decreasing or non increasing then we also use <=.
Complexity : Depends upon accuracy.
@showell :
If tree is
2
/\
1 3
and i need to find nodes between 1 and 3, then the root node which is 2 is the node from where we start in order algo.
if tree is
6
/ \
4 8
/ \ / \
2 5 7 10
Now in this question if the range is [1 5] then at root node which 6 in not belong to [1,5] and is greater then 5, so we go left, Now 4 is in [1,5], so we consider 4 as root and start inorder traveling
How ?
Here is how, If we consider 4 as root, then the new tree is
4
/ \
2 5
so we can see that all 2,4,5 are inside [1,5].
 sonesh March 03, 2013Here is the algorithm
Let string 1 is A[nx1] and string 2 is B[mx1]
Now take M[n+1,m+1];
for i = 0 to n
M[i][0] = 0;
for j = 0 to m
M[0][j] = 0;
for i = 1 to n
for j = 1 to m
if A[i1] = B[j1]
M[i][j] = 1 + M[i1][j1];
else
M[i][j] = Max(M[i1][j],M[i][j1])
output M[n][m];

sonesh
March 01, 2013 Hint : Use BFS here. Here is algo
Lets say A is boolean matrix. consider each A[i][j] as node and the bool value as there value and it is connected with all its 2 to 4 nearer node.
Now run BSE on it. Here BFS is just used for visiting nodes with value true. in BFS we provide a source node whose value is true,
Here is sample code
for i=1 to n
for j=1 to m
if A[i][j] is not visited and is true
count++;
run BFS with source node A[i][j]
Now BFS only visit to new nodes having true value.
complexity O(m*n), same algo can also be used to calculate largest size pound of true values, or other related questions.
 sonesh February 25, 2013Use two index/pointers, one lets say P1 & P2, Now enhance P1 to n lines, if it already reaches to end of file and then print the file with 2nd pointer. If not then
start both pointer, enhance both one by one, means enhance P2 by one line and then enhance P1 by one line(starting with first line),
when we P2 reaches to end of file, then we print lines with the help of P1.
Actually I forget to write one more thing and is applied to both the algo, which is "compression", We compress the string first, in first move along with length calculation, for example
if input is a1b1c2 then after first step string will be abc2 with length 4
if input is a2b1c1d5e1f4g0h1i5 then after first step it will be a2bcd5ef4hi5 with length 20. then we apply the same.
this step also require O(n) time

sonesh
February 25, 2013 This problem can be of two type :
First : all integer in given input are lies between 0 to 9.
Here is the algo :
 In first pass to input string, find the sum of all integer by testing each char by isnum(), and summing integer value into sum variable.
 Now we keep one pointer at sum and another the end of input string, we find integer and char and populate it at first pointer. move second by 2 and first by the value of integer,
 keep going with this process.
2nd : the integer might have value greater then 9.
Here is the algo :
 We use atoi() function along with isalpha() to calculate output string length,
 Isalpha() is to find weather we reach to next integer from last one,
 Atoi() is to find current integer before next char.
For example : current input is 110f10g
then Isalpha give false, and atoi() give 110, then by the help of isalpha we move our next pointer on input string.
 we apply same concept while outputting.
Actually I forget to write one more thing and is applied to both the algo, which is "compression", We compress the string first, in first move along with length calculation, for example
if input is a1b1c2 then after first step string will be abc2 with length 4
if input is a2b1c1d5e1f4g0h1i5 then after first step it will be a2bcd5ef4hi5 with length 20. then we apply the same.
this step also require O(input length) time
complexity : O(length of output string)
 sonesh February 25, 2013
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
Here is the solution for this problem
 sonesh June 06, 2015