sonesh
 0of 0 votes
AnswerQ 7. You are getting a stream of integers, You have to find the median of these in real time(or with minimum complexity).
 sonesh in United States Report Duplicate  Flag
Two Sigma Software Engineer / Developer 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
Two Sigma Software Engineer / Developer Brain Storming technical  0of 0 votes
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
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
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
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
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
Hitachi Data Systems Software Engineer / Developer Trees and Graphs  0of 0 votes
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
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
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
Expedia Software Engineer / Developer String Manipulation  0of 0 votes
AnswerYou are given an integer, print its 4th least significant bit
 sonesh in United States Report Duplicate  Flag
Expedia Software Engineer / Developer Bit Manipulation  0of 0 votes
AnswersYou are given a rotated sorted array of size N. You have to search a given number into it.
 sonesh in United States
Example: [4,6,8,14,90,9,2,0,3], Search 2. Report Duplicate  Flag
Amazon Software Engineer / Developer Algorithm Arrays Sorting  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
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
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
Bloomberg LP Software Engineer / Developer Trees and Graphs  0of 0 votes
AnswersYou are given a vector of integers. You have to delete the odd numbers from it.
 sonesh in United States
Expected complexity is O(N) Time and O(1) space Report Duplicate  Flag
Bloomberg LP Software Engineer / Developer Arrays  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
Amazon Software Engineer / Developer Algorithm  0of 0 votes
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
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
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
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
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
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
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
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
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
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
Microsoft Software Engineer / Developer Algorithm Sorting  1of 1 vote
AnswersRound 5
 sonesh in United States
Question 2 : You are given a 1 GB of numbers, you have to sort them. Tell me the time required in seconds ? Report Duplicate  Flag
Microsoft Software Engineer / Developer Algorithm Sorting  2of 2 votes
AnswersRound 5 (taken by PRINCIPAL GROUP ENG MANAGER)(hiring Manager)
 sonesh in United States
Question 1 : Tell me about your achievements ? Report Duplicate  Flag
Microsoft Software Engineer / Developer General Questions and Comments  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
Microsoft Software Engineer / Developer Brain Storming Data Mining Math & Computation Matrix Probability Testing  0of 2 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
Microsoft Software Engineer / Developer SQL  1of 1 vote
AnswersRound 4
 sonesh in United States
Question 3 : this question was similar to Round 2 Question No 3, which is basically convert row type of data to column type of data Report Duplicate  Flag
Microsoft Software Engineer / Developer Algorithm Arrays Data Structures  1of 1 vote
AnswersRound 4
 sonesh in United States
Question 2 : Why are you switching your job ?, why our team ? Report Duplicate  Flag
Microsoft Software Engineer / Developer General Questions and Comments  1of 1 vote
AnswersRound 4 (taken by PRINCIPAL DATA SCIENTIST)
 sonesh in United States
Question 1 : Tell me about your previous work at Microsoft ?. any work you are proud of ? Report Duplicate  Flag
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
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
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
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
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
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
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
Microsoft Software Engineer / Developer Algorithm Data Structures Trees and Graphs  1of 1 vote
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
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
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
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
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
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
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
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
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
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
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
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
Microsoft Software Engineer / Developer Algorithm Data Mining Data Structures  2of 2 votes
AnswersRound 1 :
 sonesh in India
Q 2 : longest palindrome in a string ? (Need to tell in O(n) time complexity + O(1) space complexity) Report Duplicate  Flag
Microsoft Software Engineer / Developer Algorithm Coding Dynamic Programming String Manipulation  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
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
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
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
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
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
Goldman Sachs Software Engineer / Developer Algorithm  0of 0 votes
Answersgiven a set of coordinates (a,b), (d,e)... etc.
 sonesh in United States
write a program to find Slope and Intercept of a line such that max points from those specified pass through the line. Report Duplicate  Flag
InMobi 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
InMobi Software Engineer / Developer Algorithm
Here are the following thing one has to take care when designing the bookshelf
1) : bookshelf can have different design
2) : books can be placed differently
3) : book can be edited, deleted/inserted/ and read by users at any point of time
For all these here is the design which usages SOLID design principles
BookShelf shape
public interface IBookContainerShape
{
public void Draw(int xCoordinate, int yCoordinate);
}
public class SquareBookShelf : IBookContainerShape
{
int height{get;set;}
int width{get;set;}
public SquareBookShelf(int height, int width)
{
this.height = height;
this.width = width;
}
public void Draw(int xCoordinate, int yCoordinate)
{
// implement the draw function
}
}
public class CircleBookShelf : IBookContainerShape
{
int radius{get;set;}
public SquareBookShelf(int radius)
{
this.radius = radius;
}
public void Draw(int xCoordinate, int yCoordinate)
{
// implement the draw function
}
}
public interface IBookShelfDrawer
{
public void DrawBookShelf();
}
public class RandomBookShelfDrawer : IBookShelfDrawer
{
IBookContainerShape[] bookContainerShapes;
public RandomBookShelfDrawer(IBookContainerShape[] bookContainerShapes)
{
this.bookContainerShapes = bookContainerShapes;
}
public void DrawBookShelf()
{
// draw the bookshelf by randomly putting these bookshelf designs
}
}
public class BigToShortBookShelfDrawer : IBookShelfDrawer
{
IBookContainerShape[] bookContainerShapes;
public BigToShortBookShelfDrawer(IBookContainerShape[] bookContainerShapes)
{
this.bookContainerShapes = bookContainerShapes;
}
public void DrawBookShelf()
{
// draw the bookshelf by putting big bookshelf parts at bottom and shorts at top
}
}
Books display type
public interface IDisplayContent
{
public void DisplayContent(Book book);
}
public class PDFDisplay : IDisplayContent
{
public void DisplayContent(Book book)
{
// implement the pdf book display logic
}
}
public class WordDisplay : IDisplayContent
{
public void DisplayContent(Book book)
{
// implement the word book display logic
}
}
public class ImageDisplay : IDisplayContent
{
public void DisplayContent(Book book)
{
// implement the logic of displaying the images of books pages
}
}
Book definition
public class Book
{
// book details, like bookID, book author, book published date....
IDisplayContent = displayContent;
public void Display()
{
displayContent.DisplayContent(this);
}
}
Book placer which place book differently
public interface IBookPlacer
{
public void BookPlace(Book);
}
public class HarizontalPlacer
{
public void BookPlace(Book)
{
// implement this
}
}
public class VerticalPlacer
{
public void BookPlace(Book)
{
// implement this
}
}
public class AngularPlacer
{
public void BookPlace(Book)
{
// implement this
}
}
And final BookShelf
public class BookShelf
{
IBookContainerShape[] bookContainerShape;
IBookShelfDrawer bookShelfDrawer;
Book[] book;
public BookShelf(IBookContainerShape[] bookContainerShape)
{
this.bookContainerShape = bookContainerShape;
bookShelfDrawer = new RandomBookShelfDrawer(BookContainerShape);
}
public void Draw()
{
bookShelfDrawer.DrawBookShelf();
}
public void AddBooks(IBookPlacer IBookPlacer, IBookContainerShape bookContainerShape)
{
// we can ask draw method to return positions of each bookContainer Shape, and pass them to pace holder to place the book, also add it to book linklist.
}
public void OpenBook(int bookId)
{
//do book lookup and call Book.DisplayContent();
}
}

sonesh
June 29, 2015 and the complexity of this is not O(n), it is O(k*log(k)) time + O(k) space where kth max number is the ask.
and your first solution, modifys the input, we have to copy the input into another array and then apply that median of median so the complexity comes out here is O(n) space + O(n) time.
If the dependencies are based upon resources, we can solve it by droping a process to not execute, in the cycle case, but if it is functional, then i think we will not be able to reach to any particular solution.
If it is resource related dependency, then one should break the c > f link.
here is the solution in this case
W> We Th Fr Sa Su Mo Tu We Thr Fr
T1 CB W ST P JD Y F
T2 MK E VG AN
T3 ZH R

sonesh
June 28, 2015 Here is the code for this algorithm
Main function
public static void StringSearchOptimized(string inputStr, string patternStr)
{
if(string.IsNullOrEmpty(inputStr)  string.IsNullOrEmpty(patternStr))
{
throw new Exception("Input is not valid");
}
int patternLength = patternStr.Length;
var longestPrefixSuffix = FindLongestPrefixSuffix(patternStr);
int inputStrLength = inputStr.Length;
int i=0,j = 0;
bool isFound = false;
while(i < inputStrLength)
{
if(patternStr[j] == inputStr[i])
{
j++;
i++;
}
if(j == patternLength)
{
Console.WriteLine("The pattern string is found between {} and {} of input string", ipatternLength,i);
j = longestPrefixSuffix[j1];
isFound = true;
}
else if(i < N && patternStr[j] != inputStr[i])
{
if(j == 0)
{
i++;
}
else
{
j = longestPrefixSuffix[j1];
}
}
}
if(isFound == false)
{
Console.WriteLine("The pattern string is not found in input string");
}
}
Longest prefix and suffix finder function
public static int[] FindLongestPrefixSuffix(patternStr)
{
int patternLength = patternStr.Length;
int[] longestPrefixSuffix = new int[patternLength];
longestPrefixSuffix[0] = 0;
int j;
for(int i = 1; i < patternLength; i++)
{
j = longestPrefixSuffix[i1];
while(patternStr[i] != patternStr[j+1] && j > 0)
{
j = longestPrefixSuffix[j];
}
if(j == 0 && patternStr[i] != patternStr[j+1])
{
longestPrefixSuffix[i] = 0;
}
else
{
longestPrefixSuffix[i] = j + 1;
}
}
return longestPrefixSuffix;
}

sonesh
June 28, 2015 I have modified his logic little bit and write the code in c# which is working fine now.
The update logic is :
We will find out the histograms row by row from max row to 0, each time, we will calculate the max rectangle area in the input histogram.
using System;
namespace RectangleFinder
{
public static class Program
{
public static void Main(string[] args)
{
var random = new Random();
sbc:
int rowSize = random.Next(1, 10);
int colSize = random.Next(1, 10);
int[][] binaryMatrix = new int[rowSize][];
for (int i = 0; i < rowSize; i++)
{
binaryMatrix[i] = new int[colSize];
}
for (int i = 0; i < rowSize; i++)
{
for (int j = 0; j < colSize; j++)
{
binaryMatrix[i][j] = random.Next(0, 2);
}
}
Print(binaryMatrix);
int maxSize = 0;
int[] oldHistogram = new int[colSize];
int[] newHistogram = new int[colSize];
for (int j = 0; j < colSize; j++)
{
oldHistogram[j] = 0;
}
for (int i = rowSize  1; i >= 0; i)
{
for (int j = 0; j < colSize; j++)
{
if(binaryMatrix[i][j] == 0)
{
newHistogram[j] = 0;
}
else
{
newHistogram[j] = 1 + oldHistogram[j];
}
}
int newMax = FindLargestRectangle(newHistogram);
if (newMax > maxSize)
{
maxSize = newMax;
}
for (int j = 0; j < colSize; j++)
{
oldHistogram[j] = newHistogram[j];
}
}
Console.WriteLine("Max area of the rectangle is : {0}", maxSize);
Console.ReadLine();
goto sbc;
}
public static void Print(int[][] binaryMatrix)
{
int rowCount = binaryMatrix.Length;
int colLength;
for (int i = 0; i < rowCount; i++)
{
Console.Write("[");
colLength = binaryMatrix[i].Length;
for (int j = 0; j < colLength; j++)
{
Console.Write(" {0} ", binaryMatrix[i][j]);
}
Console.WriteLine("]");
}
}
public static int FindLargestRectangle(int[] histogram)
{
int maxArea = 0;
int k,j;
int histLength = histogram.Length;
int isbreak;
for(int i = 0 ; i < histLength; i++)
{
k = i1;j = i+1;
while(true)
{
isbreak = 0;
if(k >= 0 && histogram[k] >= histogram[i])
{
k;
}
else
{
isbreak++;
}
if(j < histLength && histogram[j] >= histogram[i])
{
j++;
}
else
{
isbreak++;
}
if(isbreak == 2)
{
break;
}
}
if(maxArea < (jk1)*histogram[i])
{
maxArea = (jk1)*histogram[i];
}
}
return maxArea;
}
public static bool ExistsAny(bool[] histogramIndexStatus)
{
int histLength = histogramIndexStatus.Length;
for (int i = 0; i < histLength; i++)
{
if (histogramIndexStatus[i])
{
return true;
}
}
return false;
}
}
}
Complexity :
space : O(MAX(rowCount, ColumnCount));
Time : O(m*n*n) for m x n matrix, but we can modify the FindLargestRectangle to run in O(n) to have O(m*n) time complexity.

sonesh
June 27, 2015 Here is what i think one should implement the LRU cache
Plese note that, this solution consider <IPAddress, ServerName> mapping, not <ServerName, IPAddress>.
Declare a Node of a trie
public class Node
{
public Int16 nodeValue; // node will store values from 0 to 9, except root node which will have 1;
public Node[] child;
public bool isTerminal;
public DateTime lastAccessDateTime{get;set;}
public string serverName{get;set;}
public Node(Int16 value, int childCount,bool isTerminal)
{
nodeValue = value;
child = new Node[childCount];
isTerminal = isTerminal;
}
public Node(Int16 value, int childCount)
{
nodeValue = value;
child = new Node[childCount];
isTerminal = false;
}
public Node(Int16 value)
{
nodeValue = value;
child = new Node[10];
isTerminal = false;
}
}
Define two trie, one is to store datetime, another is to store ipaddress
public class IPAddressTrie
{
public Node root;
public IPAddressTrie(Int16 value)
{
root = new Node(value,3);
}
public void Insert(string iPAddress, DateTime accessDateTime)
{
throw new Exception();
}
public void Delete(string iPAddress)
{
throw new Exception();
}
public DateTime Update(string iPAddress, DateTime newAccessDateTime)
{
throw new Exception();
}
public bool Search(string iPAddress, DateTime accessDateTime)
{
throw new Exception();
}
}
public class DateTimeTrie
{
public Node root;
public DateTimeTrie(Int16 value)
{
root = new Node(value,2);
}
public void Insert(DateTime lastAccessDateTime, string serverName)
{
throw new Exception();
}
public string Delete(DateTime lastAccessDateTime)
{
throw new Exception();
}
public void Update(DateTime oldAccessDateTime, DateTime newAccessDateTime)
{
var serverName = Delete(oldAccessDateTime);
Insert(newAccessDateTime, serverName);
}
public string DeleteFirstAccussedElement()
{
throw new Exception();
}
}
Here is how you can write your main class
public class IPAddressLRUCache
{
public static void Main(string[] args)
{
DateTimeTrie dTTrie = new DateTimeTrie(1);
IPAddressTrie iPATrie = new IPAddressTrie(1);
int iPAddressCount = 0;
while(true)
{
string newIPAddress = "temp"; // this is the request generated from the CPU;
DateTime accessDateTime = DateTime.UtcNow; // cpu can give this as well or we can set it to utcnow;
if(iPATrie.Search(newIPAddress, accessDateTime))
{
// apply mutex lock here
var oldDateTime = iPATrie.Update(newIPAddress, accessDateTime);
dTTrie.Update(oldDateTime, accessDateTime);
// release the lock here
}
else // cache miss case
{
// aply mutex lock here
if(iPAddressCount == 1000)
{
var ipaddress = dTTrie.DeleteFirstAccussedElement();
iPATrie.Delete(ipaddress);
iPAddressCount;
}
else
{
<newIPAddress, server> = Disk.Read();
iPATrie.Insert(newIPAddress, accessDateTime);
dTTrie.Insert(accessDateTime, server);
iPAddressCount++;
}
// release mutex here
}
}
}
}
I didn't put much of the thinking for multithreaded main method, so, main may have some issues with multithreading
Complexities
Space : size of the input
Time : Constant, 2 or 3 multiple of 8.

sonesh
June 27, 2015 Here is the code
using System;
namespace DynamicProgramming
{
public class Question
{
public int marks;
public int timeRequiredToComplete; // in minutes
}
public static class Program
{
public static void Main(string[] args)
{
int questionCount = 3;
Question[] questions = new Question[questionCount];
var random = new Random();
for(int i = 0; i < questionCount; i++)
{
questions[i] = new Question() { marks = random.Next(1, 15), timeRequiredToComplete = random.Next(1, 60) };
}
int passingMarks = random.Next(1,20);
FindQuestionswithMinimumTime(questions,passingMarks);
Console.ReadLine();
}
public static void FindQuestionswithMinimumTime(Question[] questions,int passingMarks)
{
if(questions == null)
{
throw new ArgumentNullException();
}
if(passingMarks < 1)
{
Print(null,null);
}
else
{
int questionCount = questions.Length;
int[][] marksTimeMatrix = new int[passingMarks+1][];
int[][][] questonRelation = new int[passingMarks][][];
int[][] questionsattempted = new int[passingMarks+1][];
int totalTime = 0;
for (int i = 0; i < questionCount; i++)
{
totalTime += questions[i].timeRequiredToComplete;
}
for (int i = 0; i < passingMarks; i++)
{
questonRelation[i] = new int[questionCount][];
}
for(int i = 0 ; i < passingMarks; i++)
{
for(int j = 0 ; j < questionCount; j++)
{
questonRelation[i][j] = new int[2];
}
}
for(int i = 0; i <= passingMarks; i++)
{
marksTimeMatrix[i] = new int[questionCount+1];
questionsattempted[i] = new int[questionCount+1];
}
for(int i = 1; i <= passingMarks; i++)
{
marksTimeMatrix[i][0] = totalTime;
questionsattempted[i][0] = questionCount;
}
for(int j = 0; j <= questionCount; j++)
{
marksTimeMatrix[0][j] = 0;
questionsattempted[0][j] = 0;
}
int iTemp,jTemp,optimizedI, optimizedJ;
for(int i = 1 ; i <= passingMarks; i++)
{
for(int j = 1; j <= questionCount; j++)
{
iTemp = iquestions[j1].marks < 0?0:iquestions[j1].marks;
jTemp = j1 < 0?0:j1;
if(marksTimeMatrix[i][j1] < marksTimeMatrix[iTemp][jTemp] + questions[j1].timeRequiredToComplete)
{
marksTimeMatrix[i][j] = marksTimeMatrix[i][j1];
optimizedI = i1;
optimizedJ = j2;
questionsattempted[i][j] = questionsattempted[i][j1];
}
else
{
marksTimeMatrix[i][j] = marksTimeMatrix[iTemp][jTemp] + questions[j1].timeRequiredToComplete;
questionsattempted[i][j] = questionsattempted[iTemp][jTemp] + 1;
optimizedI = iTemp1;
optimizedJ = jTemp1;
}
questonRelation[i1][j1][0] = optimizedI;
questonRelation[i1][j1][1] = optimizedJ;
}
}
Question[] attemptedQuestions = new Question[questionsattempted[passingMarks][questionCount]];
int[] questionNumberArray = new int[questionsattempted[passingMarks][questionCount]];
optimizedI = passingMarks1;
optimizedJ = questionCount1;
int k=0;
while(optimizedJ >= 0 && optimizedI >= 0)
{
if(questonRelation[optimizedI][optimizedJ][0] == optimizedI)
{
optimizedJ = optimizedJ1;
}
else
{
attemptedQuestions[k] = questions[optimizedJ];
questionNumberArray[k] = optimizedJ;
iTemp = questonRelation[optimizedI][optimizedJ][0];
jTemp = questonRelation[optimizedI][optimizedJ][1];
optimizedI = iTemp; optimizedJ = jTemp;
k++;
}
}
Print(attemptedQuestions,questionNumberArray);
}
}
public static void Print(Question[] questions, int[] questionNumberArray)
{
if(questions == null && questionNumberArray == null)
{
Console.WriteLine("No need to attempt any questions");
}
if((questionNumberArray == null && questions != null)  (questionNumberArray != null && questions == null)  (questions.Length != questionNumberArray.Length))
{
throw new Exception("inputs are not valid");
}
else
{
int totaltimerequired = 0;
Console.WriteLine("Minumum number of questions to attempt is {0}", questions.Length);
Console.WriteLine("Here is the questions list");
for(int i = 0 ; i < questions.Length;i++)
{
Console.WriteLine("Question : {0} (Marks : {1}, Time Required To Complete : {2})",questionNumberArray[i],questions[i].marks,questions[i].timeRequiredToComplete);
totaltimerequired += questions[i].timeRequiredToComplete;
}
Console.WriteLine("Minumum time required(in minutes) for these questions is {0}", totaltimerequired);
}
}
}
}

sonesh
June 26, 2015 Here is the C# code for it.
Define the Intervals
public class Interval
{
public int intervalStart;
public int intervalEnd;
public override string ToString()
{
return string.Format("( Interval start at: {0}, IntervaleEnd at: {1} )", intervalStart.ToString(), intervalEnd.ToString());
}
}
Here is the subroutine to find out the max subset.
public static void FindMaxIntervals(Interval[] intervals)
{
if (intervals == null)
throw new Exception("intervals object undefined");
int length = intervals.Length;
for(int i = 0 ; i < length;i++)
{
if (intervals[i] == null)
throw new Exception(string.Format("{0}th interval is undefined", i));
}
Array.Sort<Interval>(intervals, delegate(Interval interval1, Interval interval2) { return interval1.intervalEnd.CompareTo(interval2.intervalEnd); });
//for (int i = 0; i < intervals.Length; i++)
//{
// Console.WriteLine(intervals[i].ToString());
//}
int intervalCount = 1;
int currentIntervalEnd = intervals[0].intervalEnd;
Console.WriteLine(intervals[0].ToString());
for (int i = 1; i < intervals.Length;i++)
{
if(intervals[i].intervalStart >= currentIntervalEnd)
{
intervalCount++;
currentIntervalEnd = intervals[i].intervalEnd;
Console.WriteLine(intervals[i].ToString());
}
}
Console.WriteLine("Count : {0}", intervalCount);
Console.ReadLine();
}
Here is the main method to generate the random intervals
public static void Main(string[] args)
{
Interval[] intervals = new Interval[10];
var rand = new Random();
for(int i = 0; i < 10; i++)
{
int j = rand.Next(0, 10);
intervals[i] = new Interval() { intervalStart = rand.Next(0, 20)  5, intervalEnd = rand.Next(20, 40)  5 };
}
FindMaxIntervals(intervals);
}

sonesh
June 24, 2015 Sort the kids based upon their weights
Start with two pointers, one at the highest weight kid and another is at lowest weight kid
Check if both can be in a single canoe or not, if not, reserve one for higher weight kid, decrement its counter,
if yes, then reserve one for both of them, and increase and decrease the counters of respective kids.
Complexity : O(nlog(n))
Space : O(1)
Here is the logic,
You can think the number of possibilities id dependent on the previous number.
NumCount = (Sum of 1 from 1 to 26) + (Sum of (Sum of 1 from j+1 to 26) from 1 to 26 as j + (Sum of (Sum of (Sum of 1 from j+1 to 26) from i+1 to 26 as j) from 1 to 26 as i + ...
it is like first digit have 26 possibilities, second can only take 26first digit position (example : if first digit is 'e', second can take any value from f to z), similarly third, fourth ...so on
this will go upto inputStr.Length1, but the last string possibilities are based upon the digit.
(for example input is 'eftr' now to calculate four digit possible count, first digit can change from a to e, second can change from first to f, third from second to t, and fourth from third to r).
Now all we have to do it calculate this sum.
Here is the algorithm one can follow
S < Input set
End_time = 0;
Subset_count = 0;
SubSet = {}
Sort the S with non decreasing order of end time
While exists at least one interval whose starttime > end_time
element < Take the first in (non decreasing) order of end time
Subset_count ++;
SubSet.Add(element)
End_time = End_time of the element
Complexity : O(NlogN)
Time : O(1) or O(Result)
The standrad solution of this problem is via sorting,
We have merge sort implementation for large array, which will take O((N/M)*LOG_M(N)) I/O Complexity and O(N*LOG(N)) as Internal memory complexity, where N is input size in bytes, and M is internal memory size, once we do, finding identical is easy
Complexity : O(Nlog(N)) Internal memory complexity
O((N/M)Log_M(N)) I/O Complexity.
Here is the algorithm
Sort nuts based upon their size // non decreasing
Sort Bolts based upon their size // non increasing
i = 0;j = 0;// i for nuts, j for bolts
while(true)
response = FitAPI(Nut[i],Bolt[j]);
if response is equal
print combination
i++;j++; // make it better to take care of duplicate cases
else if response is small
i++;
else if response is large
j++;
break if either i or j crosses there respective limit
end
Complexity
Time : O(nlogn)
Space : O(1)
Here is the algorithm
Sort nuts based upon their size // non decreasing
Sort Bolts based upon their size // non increasing
i = 0;j = 0;// i for nuts, j for bolts
while(true)
response = FitAPI(Nut[i],Bolt[j]);
if response is equal
print combination
i++;j++; // make it better to take care of duplicate cases
else if response is small
i++;
else if response is large
j++;
break if either i or j crosses there respective limit
end
Complexity
Time : O(nlogn)
Space : O(1)
Here is the method which i think will work here.
A, B are input arrays
FindRank(A, i1,j1, B, i2, j2, N)
if i1=j1 then
q = Apply BS in B[i2..j2] for key A[j1], we use nearest value which is less then A[j1] to find this
return B[i2 + N(qi2+2)] as response
else if i2=j2 then
q = Apply BS in A[i1..j1] for key B[j2], we use nearest value which is less then B[j2] to find this
return A[i1 + N(qi1+2)] as response
else
q = (j1+i1)/2
r = Apply BS in B[i2..j2] for key A[q], we use nearest value which is less then A[q] to find this
if N > (ri2 + qi1)
call FindRank(A, q,j1, B, r, j2, N  (ri2 + qi1))
else if N < (ri2 + qi1)
call FindRank(A, i1,q, B, i2, r, N)
else if N = (ri2 + qi1)
return r or q based upon whether A[q] is big or B[r] is big
end
end
end
Complexity
Time : O(Log(n)*Log(n))
Space : O(1)
A simpler but O(N) complexity algorithm can be found using two pointer i, j strting from 0, and moving the samller value pointer until i+j < n.
Here is the method
A, B are two input strings
mismatchCount = 0
if A.Length = B.Length
for i = 1 to A.Length
if A[i] <> B[i]
mismatchCount ++;
end
if mismatchCount = 1 return true else false;
else if A.Length  B.Length = 1
if A.Length is bigger
CheckSame = true
for i = 1 to A.Length1
if CheckSame and A[i] <> B[i] and A[i+1] = B[i]
CheckSame = false;
else if (Not of CheckSame and A[i+1] = B[i] ) or (CheckSame and A[i] = B[i])
do nothing
else
return false;
end
end
else
do the similar thing with B
else return false
Complexity :
Time : O(n)
Space : O(1)
Use DFS here
A[N,M] is the input matrix
C[N,M] is color matrix, whose C[i,j] = 1 for all at the begining.
MaxPondSize = 0;
MaxPondColor = 1
PondStartingColor = 0;
TotalPondSize = 0
For i = 1 to N
For j = 1 to M
IF A[i,j] = 1 and C[i,j] < 0
Start DFS with this node as Starting Node with Final Color as PondStartingColor instead of Black, return FinishTime/2 as pondSize
PondStartingColor = PondStartingColor + 1;
if MaxPondSize < pondSize
MaxPondSize = pondSize
TotalPondSize = TotalPondSize + pondSize
end
end
end
PondStartingColor is the count of number of ponds on the given area.
MaxPondSize is the size of maximum pond and MaxPondColor is the color of that pond,
we can print its location as well.
Number of changes need to have one pond : TotalPondSizeMaxPondSize.
Tomake one pond, we just change the numbers to 0 for all the places whose color is not MaxPondColor
Complexity :
Time : O(N*M)
Space : O(N*M)
i think the question is to figure out the longest subarray from second array which also an subarray of first array.
here is the solution of this problem
Assuming the Array A is sorted in non decreasing order
Figure out the sorted subarrays from Array B and check if they are also present in Array A.
i = 0, j = 0
For i from 0 to A.Size
If A[i] > A[i1]
j++
else
if j > i
check if Array B[i,...j] is alos present in A[1,M]
if Yes, and ji > currentMax then ji is the current max size which is present upto this point
end
i = j;
end
end
Return CurrentMAx and I, J, which are correspond to max
Complexity : Space O(1)
Time : O(M*K) where K is number of sorted subarrays of A.
Apply BFS, Considering A[i,j] <> A[i,j+1] an edge if neither A[i,j] nor A[i,j+1] is marked as 'X'
Similarly consider A[i,j] <> A[i+1,j] as edge if neither A[i,j] nor A[i+1,j] is marked as 'X'
This will also give you shortest path as well
Complexity :
Time : O(Count of vertices which are not marked as 'X')
Space : O(M*N)
Here is the logic to search any element in such a array
You can see that although the array is rotated N times, but actual rotation will happen only N mod L(size of the input array) times.
Assumptions : sorting order is known to us, and so rotation side, (left or right, i am assuming left here)
Find(A, i, j, Key)
If i == j
if A(i) == key
return i;
else return Key Not Found
else if j = i+1
check whether A(i) or A(j) are each to key, if both of them, then return i, if one of them then return that, else return Key Not Found
else
q = i + (ji)/2
if A(i) > A(q)
if key < A(q) or ( key > A(q) and key > A(i))
Call Find (A,i,q1,key);
else if key > A(q) and key < A(i))
Call Find (A,q+1,j,key);
else if key = A(q) and A(q1) <> key
return q;
else if key = A(q)
call Find(A, i, q1, key)
else
if Key > A(q) or (Key < A(q) and key < a(i))
call Find (A,q+1,j,Key)
else if Key < A(q) and key > a(i)
call Find (A,i,q1,Key)
else if key = A(q) and A(q1) <> key
return q;
else if key = A(q)
call Find(A, i, q1, key)
end
end
end
end
Complexity
Time : O(log(n))
Space : O(1)
First answer
Lock the whole take when doing any update/insert/delete operaton, allow reads without any lock, reads will wait if we have any lock on the table, we need to keep a priority queue for the sequence of operations, which will give reads more priority over writes, and within reads or writes, the priority can change based upon requirements and requested time.
Second answer,
We will use row wise lock, instead of whole table lock, we will put lock on only those table which are/will be affected by the current write operations, rest all will be allowed to read.
now whether or not we allow uncommited reads is the question of requirements, we may allow based upon the lock, (we can define the type of lock, in case of delete lock, we can directly return not found kind of response for read query, without making it wait on the lock.
Please note that, each lock will have a priority queue associated with it, when lock is revocked, the queue will not just vanish until all its entries are delete, the read operations in the queue will create multiple thread, and allow them to finish together, until then write awaits, we will finish all the reads first, before we start the write operation, (we can associate a timer as well, which will force the write operation to happen.
Here is the algorithm for this
We need to do two pass to the list, in one pass, we will create the new list, set its next and previous pointers, in the next run, we will set the random pointers
CloneList(List P)
List N = New Empty List;
// Node1 and Node2 are there is keep track of first node of each list.
Node1 = P.FirstNode;
Node2 = N.FirstNode; // this will be null
// This while loop will copy the old list to new list
While Node1 is not null
Create a new Node Node_New;
if Node2 is null then
Node2 = Node_New;Node2.Previous is Null;Node2.Next is null;
else
Node_New.Previous = Node2;
Node_New.Next is null
Node2.Next = New_New;
Node2 = Node_New;
Node2.Random = Node1.Random;
Node1.Random = Node2;
Node1 = Node1.Next;
Node1 = P.FirstNode;
Node2 = N.FirstNode;
// This while loop will set the random node to its correct value
While Node1 is not null
Node2.Random = Node2.Random.Random
Return List N;
Complexity
Time : O(N)
Space O(N) : Need to store the new list
Here is the techinque, took some time to figure it out,
We need some space to figure out this problem, the space required for this problem is n*n, because there will be n*n many intervals, we need this space to save the min/max of an internal and help in figure out the min and max of its near by intervals in o(1) time.
Here is the algorithm
n < size of the array A
define M(n,n) as two value matrix storing both min and max, where M(i,j) repersents min and max between the array i and j, This will a symmetric matrix(M(i,j) = M(j,i)
set M(i,j) = (min = infinity, max = infinity)
For k = 2 to n/2 // as one size sub is always a solution for this problem
for j = 1 to n2k // assuming array from A[1 to n]
if M(j,j+k) is not defined, define it
for i = j+k+1 to nk
if M(i,i+k) is not defined, define it
if M(j,j+k) and M(i,i+k) satisfy the condition,
save k and indexes to return the answer at the end, we will overwrite the old values of k is higher
end
end
end
Here is the condition about which i am talking about
Condition_check((Min1,Max1),(Min2,Max2))
if Max1 < Min2 or Min1 > Max2 then return true else return false
Here is how we define the vales of M
Set_MValues(A,M,i,j)
If Defined(M(i,j1)
Then Min(M(i,j) = Min(A[j], Min(M(i,j1)) and Max(M(i,j) = Max(A[j], Max(M(i,j1))
If Defined(M(i1,j)
Then Min(M(i,j) = Min(A[i], Min(M(i1,j)) and Max(M(i,j) = Max(A[i], Max(M(i1,j))
else figure out min and max between A(i...j].
Complexity
Time : O(n*n*n)
Space : O(n*n)
In such a situation, one should create some indexes on the data, for example B+ tree, where the index node size could be alpha times internal memory size where alpha is less then one, and is decided based upon performance.
so this means, we are actually have alpha times internal memory size of fan out of the tree, which reduces the height of the tree significantly, to Log(N/(Alpha*M))/Log(Alpha*M), where N is the total size of the Daata, and M is the internal memory size.
similarly Insert also, in most cases, untill we have to do some node partitioning which is very rare.and so delete(where we do lazy delete). Full scan any will take same amount of time, we have to read all the data, can't do anything.
We have to use DP to solve this problem, the greedy approch which you have given is not correct
Here is the example
input
Q > 1, 2, 3
M > 6, 7, 14
T > 3, 3.5, 6.5
P = 15
According to your algorithm, the minimum t will be 9.5 and user attempt first and third question
but more optiomal solution is 6.5, when user attempt first and second questions.
So, so solve such cases, we use DP
Here is the logic
M < as input Marks array
T < as input time array
Let C(i,j) repersents the minumum time to get i marks using first j questions.
C(i,j) = Infinity if i > 0 and j = 0
C(i,j) = 0 if i = 0 // Consider negative value of i and j as 0
C(i,j) = min(C(i,j1), C(iM[j],j1) + T[j])
we can use buttom up approch to solve the value C(P,N) if P is the needed marks and N is the size of the array
Complexity: Both space and Time complexity are O(PN)
 sonesh June 06, 2015here is the easy solution
Foreach entry a from the dic employes
out_dic<a.firststring> = 0;
Foreach entry a from the dic employes
out_dic<a.secondstring> = out_dic<a.secondstring> + 1;
Foreach entry a from the dic employes
out_dic<a.secondstring> = out_dic<a.secondstring> + out_dic<a.firststring>;
return out_dic;

sonesh
June 06, 2015 Here is the solution for this problem
LowestNumb(InputStr, n)
if n > InputStr.Length
output = 0;
else
CountArray = Integer array of size 9, each having value 0, indexing from 0 to 9
for index j from 0 to InputStr.Length1
CountArray[InputStr[j].ToInt()]++;
for index j from 9 to 0
if n > CountArray[j]
n = nCountArray[j];
CountArray[j] = 0;
else
CountArray[j] = CountArray[j]  n;
n = 0;
break;
Multiplier = 1;
output = 0;
for index j from 0 to InputStr.Length1
if(CountArray[InputStr[j].ToInt()] > 0)
output = output + InputStr[j].ToInt()*Multiplier;
CountArray[InputStr[j].ToInt()] ;
Multiplier = Multiplier * 10;
print output

sonesh
June 06, 2015 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 Open Chat in New Window
 sonesh June 29, 2015