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
Let L1 and L2 are two singly linked list.Let we store sum in L3 an another linked list.
First Step :
Reverse both L1 and L2 by following code
Define curr = head;
prev = NULL;
while(curr)
{
next = curr>right;
curr>right = prev;
prev = curr;
}
head = prev;
second step :
Once that is done start summing both L1 and L2 element wise in following ways
int carry = 0;
while(L1>curr && L2>curr)
{
L3>curr>data = (L1>curr>data + L2>curr>data + carry)%2;
carry = (L1>curr>data + L2>curr>data + carry)/2;
increment 1 step in each
}
if(L1>curr)
{
L3>curr>data = (L1>curr>data + carry)%2;
carry = (L1>curr>data + carry)/2;
increment 1 step in each
}
else if(L2>curr)
{
L3>curr>data = ( L2>curr>data + carry)%2;
carry = ( L2>curr>data + carry)/2;
increment 1 step in each
}
if(carry)
add extra node in L3 with value 1
3rd step :
Reverse all
standard solution :
void permute(char *a, int i, int n) // i is zero in first call and n is size of the string.
{
int j;
if (i == n)
printf("%s\n", a);
else
{
for (j = i; j <= n; j++)
{
swap((a+i), (a+j));
permute(a, i+1, n);
swap((a+i), (a+j)); //backtrack
}
}
}

sonesh
January 29, 2013 I forgot one thing to write here which is that root node is included in both the stacks, as i am checking the condition which is that stack1's element should be smaller then stack2's element, so this will not create any problem, but it solve problems like yours, thanks for that,
here is the execution :
s1 = [7,2]
s2 = [7,20,22]
2+22 < 37
s1 = [7]
s2 = [7,20,22]
7+22 < 37
s1 = [20,12]
s2 = [7,20,22]
12+22 < 37
s1 = [20 17]
s2 = [7,20,22]
17+22 > 37
s1 = [20,17]
s2 = [7,20]
17+20 = 37;
let s1 and s2 are two stack
initially s1 contain : [3,2]
and s2 contain : [5,8,9]
we sum 2 and 9 and compare then with 5.2 and 11 is bigger then 5.2 so we look for left child of 9 which is not there, so we pop 9 from s2
now stacks contains
s1 : [3,2]
s2 : [5,8]
again 2+8 > 5.2 so we pop 8 and push 6
now stacks contain :
s1 : [3,2]
s2 : [5,6]
now again 2+6 > 5.2, we pop 6 from it
now stacks contain :
s1 : [3,2]
s2 : [5]
again 2+5 > 5.2 so we pop 5 from it and push [3,4] into it
now stacks are :
s1 : [3,2]
s2 : [3,4]
again 2+4 > 5.3 so we pop 4 and push 3.1 into it
now stacks contains :
s1 : [3,2];
s2 : [3,3.1]
here 2+3.1 < 5.2 so we pop 2 from s1 and push 2.1 into it
now stack contains :
s1 : [3,2.1]
s2 : [3,3.1]
now 2.1 + 3.1 = 5.2 we get our answer, we print 3.1 and 2.1, if there is a possibility of having multiple pairs, then we won't stop here we go upto the condition that element of s1 is smaller then element of s2.
then take n processors, and divide all these n process of each processors, and execute them parallely, as they are independent jobs, so there wont be any shared data between them. ya but this require you to change your code, make it multithreaded, but if it is then we don't have to do anything, we just need to add more processors, it would be better if we add n processors(for efficiency), but more or less is also fine.
 sonesh January 27, 2013To reverse a linked list we use three pointers, and algorithm is following
Three pointers are : prev,current,next;
set prev = null;
current : head;
while(current && current>data != k)
{
next = current>right;
current>right = prev;
prev = current;
current = next;
}
save prev(as it is the head node of this linked list)
head>right = current;
then travel upto m
while(current && current>data != m)
current = current>right;
again reverse remaining linkedlist.
check if current is null or not. if not then only go next.
set prev = current;
current = current>right;
while(current)
{
next = current>right;
current>right = prev;
prev = current;
current = next;
}
return saved node.

sonesh
January 27, 2013 It depends upon process, If OS does not find enough space in internal memory then it use external memory for that process, or other process, to run that process. as all blocks are not needed at anytime, so OS uses lest required external memory to run that process. but there is no restriction on size. It depends upon OS performance, and and in some sense on processing speed..
 sonesh January 27, 2013solution : having complexity O(n)(time)+O(height of BST)(space)
observation : if we are given a sorted array instead of a BST and the same question was asked then so solve this problem in O(n)+O(1) complexity, we keep two indexes one at start and 2nd one at end, and apply following algo.
if(A[1st_index] + A[2nd_index] < x)
2nd_index;
else if (A[1st_index] + A[2nd_index] > x)
1st_index++;
else
print 1st_index,2nd_index;
do this until 2nd_index > 1st_index
so we apply the same concept here, because we don't have data stored in an array faction, so we need some space, now one way is tot store the data into an array and apply the same, but this require O(n) space, but if you think carefully, then we only require at max 2*height_of_BST, in first array of size height_of_BST, we store all elements which comes from
root>left,root>left>left,.......
and in 2nd array we store
root,root>right,root>right>right,.......
and we start with the last element of these two array, these array's are actually stack. now we get two element do we do the same comparison here also
if(first_stack_element + 2nd_stack_element < x)
check for it's left tree, and store all right going element into stack(2nd stack) and start again
example :
\
6
/
3
/ \
1 4
so we store [.......3,4] after popging 6. because now 4 is the biggest element in the tree.
actually we search for last biggest element here.
else if (first_stack_element + 2nd_stack_element > x)
Here we search for next smallest element, using our 1st stack.
example
/
2
\
6
/ \
3 7
now here we go with 3 for next comparison.and the stack contain [.....,6,3] after popping 2
else
print first_stack_element, 2nd_stack_element;
do this until first_stack_element < 2nd_stack_element

sonesh
January 26, 2013 @prabhat do you think that in heap O(logn) time is required to delete an element ?
we don't want to delete, we just want to search elements, here one more thing is given which is probability. each node have certain probability of being searched. new we need to utilized that probability and create an efficient data structure that minimize the expected search time.
@Messiah :
Yes you are right, actually interviewer define like that,
he first write a simple example and then says that this is the answer and we call this type of problem as left most right cousin problem.
so from their only i have given the example, actually he want to know the left most node of same depth.
we use series expansion of sine and cosine,as
sin(x) = x  x^3/3! + x^5/5!  x^7/7! + .....
cos(x) = 1x^2/2! + x^4/4!  x^6/6! + .....
we calculate both power of x and factorial by power methods,
for example in cos series we first calculate x^2, then each time we just multiply x^2 with current maximum power to get next element.
similarly for sin series also we use the same fact.
Note that here x is in radian.
complexity : approx O(1), or it depends upon accuracy required.
we use array implementation but along with the array we will have an bit array of size size which is useful for deletion, we does not delete any element we just overwrite it, once delete command is executed for an element we set its' bit to zero.
and it is easy to implement array in circular faction as required by question.
inorder traveling require O(n) space, here is O(1) space with same time complexity algorithm
start recursion from root node, in recursion visit all nodes,
during back tracing start verifying from leaf node.
if at all places we get yes, then it is BST, other wise not.
Algorithm :
step 1 : check weather source and destination cell of the matrix having 1 or not, if not output Infinite, else
step 2 : create a boolean matrix of same size, and set all entries to false,
step 3 : start from source, set corresponding boolean matrix entry to true,
Lets M is given matrix and N is boolen matrix, so at any (i,j)th node we do following
if(M[i][j+1]&!N[i][j+1]) add it into queue, similarly others, update matrix M entries such that they repersent distance from source cell using BFS algorithm
then we set N[i][j] = true;
go on to new element from queue.
once queue is empty
then print what is written at destination cell.
your analysis is ok with the example you have given here, but you forget that the probabilities are assigned to some nodes, and the nodes have some values stored in it. so when you do the search, if you use heap, you need to search the whole data, then what is the use of these probabilities, the question is not to arrange the probabilities, but to arrange data items such that expected search time is as minimum as possible.
to make more sense look at your example : 7(0.4), 2(0.2), 5(0.3), 9(0.1)
and you have made following tree
....7
../...\
.2...5
/
9
now i do 10 searches in this tree, and then you please calculate time complexity of these searches and find out weather my structure is optimal or not.
searches are : 5, 7, 2 , 7, 5, 9, 5, 7, 2 ,7 call it array A
now you calculate the time required to search 2,5,7,9, once you have calculated that then we do following sum
sum from i = 1 to 10 (time required to search A[i])*probability of A[i]
and then tell us the value, i will tell you an optimal value for it.
your first step says that find the node from the root node, as because root node is given, we don't have to find it. and while doing do keep track of the parent node, means we store parent node in an array, or if we are in recursion then when we back trace then we can again access them.
your second step says that start inorder traveling from root node not from parent node, (obviously because see the example which i have given in kamy's post) or you mean to say that we start inorder traveling from all parents starting from the parent node of the given node to grand paren node and uoto root node,
Your 3rd step is wrong.
look at this example :
..............8
........../........\
........9........10
....../..\......../...\
...11...3....4....6
.....\....\...../.\..../
......7...1.2..5.12
now call LeftMostRightCousin : LMRC
LMRC are following
elt : their LMRC's
8 : none
9 : 10;
10 ; none;
11 : 3;
3 : 4;
4 : 6;
6 : none;
7 : 1;
1 : 2;
2 : 5;
5 : 12;
12 : none
now think that is your algorithm correct ?
First of all I would like to tell you that the question is for a binary tree, The interviewer just say that the binary tree is given.
your algorithm is correct for BST, but need modifications so that others can also understand. check the cases when we don't have right children, or our node itself is a right children of a node, does the complexity you have stated is correct,
try to think an example when the complexity can go upto O(n).
for your understanding there is nothing like O(2logn), it is O(logn).
Doing BST means nothing, BST is binary search tree, doing it make no sense. anyway, even if you make it complete by adding additional nodes with some value. then also it does not give correct answer, and one more thing you actually didn't tell us how do you check for left most right cousin, actually that is the question ??
if you just check right node, then that may not be the answer for example
...............8
............../...\
............3....4
.........../........\
.........5..........9
Leftmost right cousin of 5 is 9, and of 3 is 4 and and of 9 is no one.
use two variable, one is string and another is int64 M, we start with M = 0, use M till maximum value is hit, then we copy half of it to the string and start start again, if M becoming negative we bring max(M)/2 from string and add it to M, and start again,
for example Max(M) is 1000;
then we start from M = 0; when M is 1000 and one more add come, then we make M to 500 and add 500 to string, when M is 0 and one sub come then we make M to 500 and reduce 500 from string,
so by this way after at least 500 operation we perform one string add/sub. so on an avg we are just doing one add or one sub to integer per operation.
take two indexes put one at start(call it i) and another at end(call it j),
now start from the i;
if A[i] is not zero, then start from j and decrement j until A[j] is zero,when that happens just swap A[i] and A[j], do i++ and j;
if A[i] is zero then just do i++;
do all these until i<j
think the accounts number are the node of a weighted directed graph, and the amount transfer from the account is represented by an outgoing edge, and amount transfer to the account is represented by an incoming edge. so first populate the graph(means adjacency list) and then just sum it up and create new three columns
 sonesh January 21, 2013@zyfo2, here is the solution of your example :
input is 1+2+3*4+5*1
so we create a matrix of size 6*6
with all these operations we get following matrix call it M[1:6,1:6]
1..3..6..24..54..54
....2..5..20..45..45
........3..12..27..27
..............4....9....9
....................5....5
..........................1
Now you man ask me how do i decide the resultant operator, the resultant operator is decided based upon from where we want to split the operation,
for example for calculation of M[1,5] we do following
M[1,5] = max(1+45,3+27,6*9,24+5) = 54
Let me start with an example
A = {0,2,4,5,0,1,2,3,0}
step 1 : sort it
A' = {0,0,0,1,2,2,3,4,5}
step 2 : remove duplicates along with print possible two element sets;
output will be :
sets : {0,0},{2,2}
A'' = {0,1,2,3,4,5}
now apply the simple algorithm to print all 2 element sets
for i=1:sizeof(A'')1
for j=i+1:sizeof(A'')
output {A''[i],A''[j]}
two solution :
1 : sort both, O(max(nlogn,mlogm)); where n and m are the size of arrays;
and then compare with avoiding duplicate's, O(n+m);
total time complexity : O(max(nlogn,mlogm))
2 : use hashing in following way has_map<int , bool>, where int represent data item, and bool variable represent weather an data item is present or not ?
we start reading array one, and if an element present more then once, we don't worry, the bool variable is set to true, Now we go to second array, and we check weather there exist an element in this array whose bool variable is not set, if we are able to find one, print not true, if not, then do the same by first taking second array to populate map and check first array for validation ,if we found one whose bool variable is not set true, we print not true, else we print true
time complexity : O(max(m,n));
We are given a node in the binary tree call it A; and K is the distance given to us;
Now we start from the root node to find the node A,(if we are just given a value, even if we are given the node we need to do this). we set a global variable flag to be false; we start from root node with recursion, and as it is a binary tree, we have to travel in all the direction to find given node.once we find given node, we set flag to be tree, which indicate that the node is found and other recursion must stop here, and they do nothing, but the recursion in which we found the node A, we call a function ""findkthdistancenodes"" which has input as distance and the node from where it starts,
what the function do is written below, now while backtracing also return distance(updated one), in this recursion, every time we backtrace we reduce distance by one, if distance become zero, we print current node and stop backtracing, else call the function findkthdistancenodes(node>child(from which we are not tracing back this child may not be present then we don't), distance1); now it is still possible that we reaches to root node, and still distance is not zero, then obviously after calling our function we stop.
what the function do is : it decrements distance by one every time when it change it's level, and it do the recursive call with all it's children with this newly updated distance, once distance become zero, it print current node.
I can also post the code here if anyone want
we use dynamic programming here,
let's the given matrix of zeros and ones is M and is of size n*m, we create an another matrix N of size (n+1)*(m+1)
and we start from the point (n+1,m+1)(right most corner) and move to point (1,1)(left most corner),
so final algorithm is following :
for i=1 to n+1
N[i][m+1] = 0;
for j=1 to m+1
N[n+1][j] = 0;
for i=n to 1
for j=m to 1
if M[i][j] == 1
N[i][j] = 1 + max(N[i+1][j] , N[i][j+1]);
else
N[i][j] = 0
search max element in matrix, output it.
complexity : O(n*m)(time) + O(n*m)(space)
 sonesh January 21, 2013Assumption : Files/Folders having same name are duplicates
In the cloud server we maintain a database which contain files/folders name with their addresses , when there is a need to syn a file we first check weather it's name is resent in our database, or not, if yes then we just create a shortcut in the file's corresponding folder(in cloud server) and this shortcut point to the corresponding file which is some where in cloud server, Now when we got a folder where all it's file are shortcut, we create shortcut of that folder insteed of having a folder which contain files as shortcut, so this will helps in reduction of further space,
simple solution :
sort the array, take two index keep one at start node, another at end node, call then i and j
count = 0;
if A[i] + A[j] > sum
j;
else if A[i] + A[j] < sum
i++;
else
output i and j and set increment count;
do the same untill j > i
if count == 0 output node present;
complexity : O(nlogn)
 sonesh January 20, 2013As we go from parent node to it's child node in binary tree, we send current path sum to all it's childern, we maintain two global variable one is max_sum and another is count, we set count to be zero and now start from root node, it send it's node value to it's childern, then add it with their value and send final sum to their childerns, whenever someone reaches to end(leaf node), it check weather it's sum is greater or equal or less, if equal then it increment count, if less, then do nothing, if greater then set count = 1 and max_sum to it's sum.
so after one tree trival we get both max_sum and count.
Now if we want to print the paths also then we do following
as we know how many max_sum path exist, Now we create that many arrays of integer element, each array have some unique Id, now we start again with the same procedure but with one difference, we send current sum to childern nodes, but we want something from them, what we want is a structure which contain a integer(which tells how many path having max_sum are having current node in comman) and id's of all arrays., once we get these data from all it;s childerns, then we print the node value in all those arrays, and return total sum and all array's id, which we get from both or one of it's childern. if we get zero as integer value from all childern then we return zero.
but ya here we visit all nodes on the tree 3 times, once when we find out max_count, and second time when we go forward to locate leaf node of all the paths whose sum is max_sum and thrid time when we return from all these leaf node to root node.
All type of likes can not be stored in a single type of data model, so I think facebook does is following :
there are pages or advertisements, where we like them, those type of likes are stored to the user itself, Each user have a list which contain all the pages and advertisements which a user likes, as there can be countable number of pages, but users are finite, so we can store the id's of these pages, or advertisements.
Now what about other likes for example likes for a post(any type of post, text, images, videos etc.), from my thinking likes on these posts are stored with their parent page, along with post liked users id is also stored.
sort each of these given 5 words character wise, for example : apple become : aelpp
Now do following :
1. read next word from queue until start_pointer > end_pointer, call it M
2. sort M character wise;
3. do one to one comparison with each of these 5 sorted words,
4. if M is equal to some of the words, add M to them(in their respective arrays)
5. go to step 1
complexity :
length of max size word in queue : n; and length of max size word in given 5 words is : m
length of queue is : N;
so the complexity is : O(N*(nlogn + 5*max(n,m))(time) + O(N)(space)
I think you are write cyrus, we have to check weather both tree have equal number of leaf nodes or not ?
so
......2
...../.\
....1...2
.../.\
..2...3
......+
......3
...../\
....2.3.2
......= 2
........./..\
.......1....2
...../...\.....\
..2......3....\
...............
..2.....3.....2
...\.........../
.....\......./
.......\..../
.........\/
.........3
this is how they can be merged
so we just have to check leaf node, lets one tree have M number of nodes and other have N number of nodes, so the this require Omega(N+M) time complexity
dynamic programming will give you the solution in O(n*n) + O(n*n) complexity
Here is solution :
lets say you have hexagon( with following 1(15)2(9)3(12)4(1)5(7)6(12)1(15)), where values written in *()* is the value at each node
Now make a 2d matrix of size 6x6, write these values in the main diagonal,
15.24.36..37.44.56
.......9...21.22.29.41
............12.13.20.32
....................1..8..20
........................7..19
.............................12
the right most corner value is the answer
I think we store all the friends of a person into a xml file in the relational database, for example
A(a) has B(b),C(c),D(d),E(e), where small letter represents a unique key for a person
we store as follow
<a, A, <sex info>, <age>, <some other info>,"b,c,d,e(we make this as xml file as attach it with every person)">
Now when i have to find out weather A' is friend of B' , i just have to find out A' in list and then i look at it's xml file for B' it it present then yes, otherwise no, obviously if A's xml file contain B then B's xml also contain A
similarly update, friend deletion ,addition, etx. can be done very efficiently, because these xml files can be searched parallelly also
Hello : it does not matter whether you are finding LCA of a btree or a bst, the concept is same, and the concept is :
Assumption : two values are given
1. start from the root node,
2. search where these two vales lies,
2.1 if they lies(means these two values are present) in two different node, then print current node as answer, if one of these two vales are not present then print 1
2.2 if they lies in same node, go to that node and keep parent node also, because if these two values found in new node then parent will be the answere, other wise go to 2 again
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
@showell30 : I think you guys have wrote enough already, but I just wanna say that First : to find a node in BST does not require a stack, secondly once we found such node, consider that node as root node and apply our inorder algorithm.(Inorder algorithm only require a node and nothing else about tree)
 sonesh February 25, 2013