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 SDE-2 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 SDE-2 design - 4of 4 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 SDE-2 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 SDE-2 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(ts1-ts2) <= 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 multi-threaded
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 SDE-3 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 vice-versa.
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 sub-array 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 non-decreasing 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 non-decreasing 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 k-1 and from k+1 to n-1.
- 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 k-subsequence 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 k-subsequences.
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 up-to 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/0B6-TjTC-KfTqQThBamxPa0NwNGM/view?usp=sharing
You have to write a program to provide a solution for this.
- sonesh in United States| Report Duplicate | Flag | PURGE
Microsoft SDE-2 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 check-list/to-do you will do before start of your project.
1.c : how will you go over each and every check-list/to-do
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 SDE-2 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 SDE-2 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 SDE-2 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
Language C#
public class TreeNode
{
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val)
{
this.val = val;
}
}
public class Solution
{
public TreeNode inOrderSucccessor(TreeNode root, TreeNode input)
{
SuccessorTreeNode successorNode = null;
successorNode = inOrderSucccessor(root, input, successorNode);
}
private SuccessorTreeNode inOrderSucccessor(TreeNode root, TreeNode input, SuccessorTreeNode successorNode)
{
if(root == null)
{
return null;
}
SuccessorTreeNode node = inOrderSucccessor(root.left, input, successorNode);
if(node != null && node.isFound && node.successorNode == null)
{
node.successorNode = root;
return node;
}
else if(node != null && node.isFound)
{
return node;
}
if(root == input)
{
successorNode = new SuccessorTreeNode(true);
}
return inOrderSucccessor(root.right, input, successorNode);
}
}
public class SuccessorTreeNode
{
public TreeNode successorNode;
public bool isFound;
public SuccessorTreeNode()
{
isFound = false;
successorNode = null;
}
public SuccessorTreeNode(bool isFound)
{
this.isFound = isFound;
}
}
Complexity : O(N) + O(1)
- sonesh May 01, 2017Here is how we will go
public class Node
{
public char label;
public List<Node> neighbors;
public Node(char x)
{
label = x;
neighbors = new List<Node>();
}
}
public class Solution
{
// we are assuming that the whole graph is given to us in list of nodes, not just the root nodes.
public boolean Exists(List<Node> nodes, string word)
{
if(String.IsNullOrWhiteSpace(word))
{
return false;
}
bool found = false;
foreach(Node node in nodes)
{
if(node.label == word[0] && IsExistsReuseLabel(node, word))
{
return true;
}
}
return false;
}
/// Lets assume we can use same label more then once.
private boolean IsExistsReuseLabel(Node node, string word)
{
if(String.IsNullOrWhiteSpace(word))
{
return true;
}
if(node.label == word[0])
{
string remainingWord = word.Remove(0,1);
foreach(Node neighbor in node.neighbors)
{
if(IsExists(neighbor, remainingWord))
{
return true;
break;
}
}
}
return false;
}
/// Lets assume, we can't use same label more then once.
private boolean IsExistsNoReuseLabel(Node node, string word)
{
Dictionary<Node, bool> usedNodeMap = new Dictionary<Node, bool>();
return IsExistsDFS(Node node, word, usedNodeMap);
}
private boolean IsExistsDFS(Node node, string word, Dictionary<Node, bool> usedNodeMap)
{
if(!usedNodeMap.ContainsKey(node))
{
usedNodeMap.Add(node, true);
}
else if(usedNodeMap.ContainsKey(node) && !usedNodeMap[node])
{
usedNodeMap[node] = true;
}
else
{
return false;
}
string remainingWord = word.Remove(0,1);
if(remainingWord.Length > 0)
{
foreach(Node neighbor in node.neighbors)
{
if(neighbor.label == remainingWord[0] && IsExistsDFS(neighbor, remainingWord, usedNodeMap))
{
return true;
}
}
}
else
{
return true;
}
usedNodeMap[node] = false;
return false;
}
}
Complexity
Time: O(N + V), where N is number of nodes in the tree and V is number of edges in the graph.
Space: O(N) for nonreuse method, O(1) for resume method.
Simple Recursive solution is following
FindElement(int[] arr, int MaxTillNow, int currentIndex)
{
if(currentIndex == 0)
{
return FindElement(arr, arr[currentIndex], currentIndex + 1);
}
if(currentIndex == arr.Length-1)
{
return arr[currentIndex];
}
int minTillNow = FindElement(arr, Math.Max(MaxTillNow, arr[currentIndex]), currentIndex + 1)
if(arr[currentIndex] > MaxTillNow && arr[currentIndex] < minTillNow)
{
Console.WriteLine(arr[currentIndex]);
}
return Math.Min(minTillNow, arr[currentIndex]);
}
Complexity : O(N), we are only doing one pass to the array.
Space complexity is O(1).
Q4: we will do following
public static int MinimumSumArray(int[] arr)
{
Array.Sort(arr);
int currentMin = arr[0];
int sum = arr[0];
int currentElement = arr[0];
int i = 1, j = 1;
while (i < arr.Length)
{
if (arr[i] == currentElement)
{
while (true)
{
if (j < arr.Length)
{
if (arr[j] == currentElement)
{
j++;
}
else if (arr[j] == currentMin+1)
{
while (j < arr.Length && arr[j] == currentMin + 1)
{
j++;
}
currentMin++;
}
else
{
break;
}
}
else
{
currentMin++;
break;
}
}
arr[i] = currentMin;
}
else
{
currentElement = arr[i];
}
sum += arr[i];
i++;
if (j < i)
{
j = i;
}
}
return sum;
}
Complexity of this O(Nlog(N)) + O(1);
- sonesh April 25, 2017Step 1 is the count of the number of nodes in the BST.
public static int GetNodeCountBST(Node root)
{
if(root == null)
{
return 0;
}
Node currentNode = root;
return GetNodeCountBSTRec(currentNode);
}
private static int GetNodeCountBST(Node node)
{
if(node == null)
{
return 0;
}
return GetNodeCountBST(node.left) + 1 + GetNodeCountBST(node.right);
}
Step 2 is to find the median
public static double? FindMedian(Node root, int nodeCount)
{
if(root == null || nodeCount <= 0)
{
return null;
}
Int median= 0;
Node currentNode = root;
FindMedianRec(currentNode, nodeCount, 0, out median);
return median;
}
private static int FindMedianRec(Node node, int totalCount, int nodeCount, out double median)
{
if(node == null)
{
return nodeCount;
}
int leftNodeCount = FindMedianRec(node.left, totalCount, nodeCount, out median);
if(leftNodeCount == (TotalCount-1)/2)
{
median = node.data;
}
if(leftNodeCount == (TotalCount/2))
{
if(TotalCount % 2 == 0)
{
median = (median + (double)node.data)/2;
}
}
return FindMedianRec(node.right, totalCount, nodeCount + 1 + leftNodeCount, out median);
}
Complexity of both the steps is O(N) and space complexity is O(1) only.
- sonesh April 25, 2017Check this out.
// Design Locker Type
public enum LockerType
{
X-Small = 0,
Small = 1,
Medium = 2,
Large = 3,
X-Large = 4,
}
// Design Locker Class
public class Locker
{
public Guid lockerId;
public LockerType type;
public int LocalId;
public Locker(Guid id, LockerType type)
{
lockerId = id;
this.type = type;
}
public Locker(Guid id, LockerType type, int localId)
{
this.lockerId = id;
this.type = type;
this.localId = localId;
}
}
// Design Locker Manager
public class LockerManager
{
private Guid lockerManagerId;
private Dictionary<Locker, Guid?> lockers;
public Address lockerAddress;
private static LockerManager manager;
private LockerManager(Guid managerId)
{
lockerManagerId = managerId;
lockers = GetLockersByManager(managerId);
lockerAddress = GetLockerManagerAddress(managerId);
}
public LockerManager GetInstance(Guid managerId)
{
if(manager == null)
{
manager = new LockerManager(managerId);
}
if(managerId != lockerManagerId)
{
throw new InvalidArgumentException("Invalid value Exception");
}
return manager;
}
public List<Locker> GetEmptyLockers()
{
return lockers.Where(x => x.Value == null).Select(x => x.Key).ToList<Locker>();
}
public Locker GetSingleEmptyLockerBytype(LockerType type)
{
return lockers.Where(x => (x.Value == null && x.Key.type = type)).Select(x => x.Key).FirstOrDefault();
}
public bool EmptyLocker(Guid lockerId)
{
var locker = lockers.Where(x => x.Key.lockerId == lockerId).Select(x => x.Key).FirstOrDefault();
if(locker != null)
{
lockers[locker] = null;
return true;
}
return false;
}
public bool EmptyLocker(Locker locker)
{
if(locker != null && lockers.ContainsKey(locker))
{
lockers[locker] = null;
return true;
}
return false;
}
public bool EmptyLockerByProduct(Guid productCatalogId)
{
var locker = lockers.Where(x => x.Value == productCatalogId).Select(x => x.Key).FirstOrDefault();
if(locker != null)
{
lockers[locker] = null;
return true;
}
return false;
}
public bool FillLocker(Locker locker, Guid productCatalogId)
{
if(locker != null && lockers.ContainsKey(locker) && lockers[locker] == null)
{
lockers[locker] = productCatalogId;
return true;
}
return false;
}
private Dictionary<Locker, bool> GetLockersByManager(Guid managerId)
{
var lockers = new Dictionary<Locker, bool>();
var rowSets = GetLockersDetails(managerId);
foreach(Row row in rowSets)
{
lockers.Add(
new Locker(Guid.Parse(row[0]), Enum.Parse(row[1], typeof(LockerType)), Boolean.Parse(row[2]), Int32.PArse(row[3]))
, Guid.Parse(row[4]));
}
return lockers;
}
}
// Amazon Locker class
public class AmazonLocker
{
// User Requests
public List<LockerManager> ShowMeLockers(Address userAddress)
{
// we use the address to list down top 10 nearest locker managers to the users. We can use Trie to implement this. Can use ZipCode or general address to navigate in the Trie.
once a user selects Locker Manager, we get locker Manager Id.
We initialize this locker Manager with Id or can use this Id to comminute with the locker manager.
}
lockerManager = LockerManager.GetInstance(managerId);
var locker = lockerManager.GetSingleEmptyLockerBytype(LockerType.Medium); // type will be provided by the user, or Amazon can also determine type by the product calalog.
lockerManager.FillLocker(locker, productCatalogId) // productCatalogId will be provided by the user.
// when amazon guy comes in and remove the item, they call, EmptyLocker(Locker locker) from the locker manager itself to empty that locker.
}
Commplexity
Assigning a locker: O(N) + O(height of Trie) where N is the size of local manager's locker count. (generally 10-15), and height is the search required to search for a locker.
Emptying a locker: O(1)
Adding new locker: O(1)
Removing a locker: O(1)
public static Main(string[] args)
{
public VotingSystem votingSystem = VotingSystem.GetInstance();
while(true)
{
// Add candidates
break;
}
while(true)
{
// Add people vote.
}
var candidate = votingSystem.GetWinner();
int winnerVoteCount = votingSystem.GetVoteCount(candidate);
}
public class VotingSystem
{
private Dictionary<Candidate, int> candidatesVoteCount;
private VotingSystem votingSystem;
private VotingSystem()
{
candidatesVoteCount = GetExistingCandidateInformationFromDB();
}
public VotingSystem GetInstance()
{
if(votingSystem === null)
{
votingSystem = new VotingSystem();
}
return votingSystem;
}
public bool AddCandidate(string name, PartyName partyName)
{
var candidate = new Candidate(name, partyName);
if(candidatesVoteCount.ContainsKey(candidate))
{
throw new InvalidArgumentException("input candidate is already present");
}
candidatesVoteCount.Add(candidate, 0);
return true;
}
public bool Remove(string name, PartyName partyName)
{
var candidate = new Candidate(name, partyName);
if(candidatesVoteCount.ContainsKey(candidate))
{
candidatesVoteCount.Remove(candidate);
return true;
}
throw new InvalidArgumentException("Input Candidate is not present in the system");
}
public bool AddVote(string name, PartyName partyName)
{
var candidate = new Candidate(name, partyName);
if(candidatesVoteCount.ContainsKey(candidate))
{
candidatesVoteCount[candidate]++;
return true;
}
throw new InvalidArgumentException("Input Candidate is not present in the system");
}
public Candidate GetWinner()
{
candidatesVoteCount.Aggregate((l, r) => l.Value > r.Value ? l : r).Key;
}
public int GetVoteCount(string name, PartyName partyName)
{
var candidate = new Candidate(name, partyName);
if(candidatesVoteCount.ContainsKey(candidate))
{
return candidatesVoteCount[candidate];
}
throw new InvalidArgumentException("Input Candidate is not present in the system");
}
public int GetVoteCount(Candidate candidate)
{
if(candidatesVoteCount.ContainsKey(candidate))
{
return candidatesVoteCount[candidate];
}
throw new InvalidArgumentException("Input Candidate is not present in the system");
}
public GetTotalVoteCount()
{
return candidatesVoteCount.Sum(x => x.Value);
}
private Dictionary<Candidate, int> GetExistingCandidateInformationFromDB()
{
var map = new Dictionary<Candidate, int>();
var rowSets = GetExistingCandidates(); // this method will call its internal db and return informations about the candidates
foreach(Row row in rowSets)
{
map.Add(new Candidate(row[0], Enum.Parse(row[1], typeof(PartyName))),Int32.Parse(row[2]));
}
return map;
}
}
public class Candidate
{
public string name;
public PartyName partyName;
public Candidate(string name, PartyName partyName)
{
this.name = name;
this.partyName = partyName;
}
}
public Enum PartyName
{
"a" = 1,
"b" = 2
}
Complexities are
Add Candidate: O(1)
Add Vote: O(1)
Delete Candidate: O(1)
GetWinner : O(N), N is total candidate count // least used
GetCandidateVoteCount : O(1)
GetTotalVoteCount : O(N), can be made O(1) easily. It is scalable, can store data into the database and while we restart the machine, it can read data from the DB and initialize itself. We can very well optimize GetWinner call as well, to return output in O(1) time. To do that, we have to store, the candidate vote count in a LinkedList and in the dictionary, we will store candidate information and corresponding LinkedList node for the vote count. We will also store maxVoteCount variable outside of all these, and when the current candidate vote count become more then maxVoteCount, then we update maxVoteCount and put that node in the first of the LinkedList. By this way, we will be able to answer GetWinner as well in O(1), just that insert and delete will take more time not in terms of complexity but in terms of more computer operations.
Failure conditions are all taken care of.
So, This is what, I would do.
Let's define an abstract entity for identifications, and storing the unique key in the database.
public abstract class Entity
{
public Guid UserId;
public Guid bookId;
}
public class SharableBooks : Entity
{
private IntervalTree sharableParts;
public double allowedShareablePart = 9876.45; // 10% of a given book
public SharableBooks(bookId, userId): base(userid, bookid)
{
sharableParts = new IntervalTree();
}
public bool Read(int startpnum, int startpindex, int endpnum, int endpindex)
{
if(sharableParts.GetTotalSharableCountAfterInsert(startpnum, startpindex, endpnum, endpindex) > allowedShareablePart)
{
return false;
}
sharableParts.Insert(startpnum, startpindex, endpnum, endpindex);
return true;
}
}
public class IntervalTree
{
private Node root;
private double sharedPageCount;
public IntervalTree()
{
root = null;
sharedPageCount = 0.0;
}
public double SharedPageCounts()
{
return sharedPageCount;
}
public double GetTotalSharableCountAfterInsert(int startpnum, int startpindex, int endpnum, int endpindex)
{
return sharedPageCount + Insert(startpnum, startpindex, endpnum, endpindex, false);
}
public bool Insert(int startpnum, int startpindex, int endpnum, int endpindex)
{
sharedPageCount += Insert(startpnum, startpindex, endpnum, endpindex, true);
return true;
}
public double Insert(int startpnum, int startpindex, int endpnum, int endpindex, bool isInsert)
{
if(root == null)
{
if(isInsert)
{
root = new Node(startpnum, startpindex, endpnum, endpindex);
}
return CountPage(startpnum, startpindex, endpnum, endpindex);
}
Node newNode = root;
return InsertInternal(newNode, startpnum, startpindex, endpnum, endpindex, isInsert);
}
private double InsertInternal(Node node, int startpnum, int startpindex, int endpnum, int endpindex, bool isInsert)
{
Node newNode = node;
Node parentNode = newNode;
while(newNode != null)
{
parentNode = newNode;
if(endpnum < newNode.startPageNum || (endpnum == newNode.startPageNum && endpindex < newNode.startPageIndex))
{
newNode = newNode.left;
}
else if(startpnum > newNode.endPageNum || (startpnum == newNode.endPageNum && startpindex > newNode.endPageIndex))
{
newNode = newNode.right;
}
else
{
break;
}
}
if(newNode == null)
{
if(endpnum < parentNode.startPageNum || (endpnum == parentNode.startPageNum && endpindex <= parentNode.startPageIndex))
{
if(isInsert)
{
parentNode.left = new Node(startpnum, startpindex, endpnum, endpindex);
}
return CountPage(startpnum, startpindex, endpnum, endpindex);
}
else if(startpnum > parentNode.endPageNum || (startpnum == parentNode.endPageNum && startpindex >= parentNode.endPageIndex))
{
if(isInsert)
{
parentNode.right = new Node(startpnum, startpindex, endpnum, endpindex);
}
return CountPage(startpnum, startpindex, endpnum, endpindex);
}
}
else
{
if(ContainedInCurrentNode(newNode, startpnum, startpindex, endpnum, endpindex))
{
return 0.0;
}
else
{
if((startpnum > newNode.startPageNum && startpnum < newNode.endPageNum) ||
(startpnum == newNode.startPageNum && startpindex > newNode.startPageIndex) ||
(startpnum == newNode.endPageNum && startpindex < newNode.endPageIndex))
{
if(newNode.right == null)
{
if(isInsert)
{
newNode.right = new Node(newNode.endPageNum, newNode.endPageIndex, endpnum, endpindex);
}
return CountPage(newNode.endPageNum, newNode.endPageIndex, endpnum, endpindex);
}
return InsertInternal(newNode.right, newNode.endPageNum, newNode.endPageIndex, endpnum, endpindex, isInsert);
}
else
{
if(newNode.left == null)
{
if(isInsert)
{
newNode.left = new Node(startpnum, startpindex, newNode.startPageNum, newNode.startPageIndex);
}
return CountPage(startpnum, startpindex, newNode.startPageNum, newNode.startPageIndex);
}
return InsertInternal(newNode.left, startpnum, startpindex, newNode.startPageNum, newNode.startPageIndex, isInsert);
}
}
}
}
private bool ContainedInCurrentNode(Node node, int startpnum, int startpindex, int endpnum, int endpindex)
{
return ((node.startPageNum < startpnum || (node.startPageNum == startpnum && node.startPageIndex <= startpindex)) &&
(node.endPageNum > endpnum || (node.endPageNum == endpnum && node.endPageIndex >= endpindex)));
}
public static double CountPage(int startpnum, int startpindex, int endpnum, int endpindex)
{
int count = 0;
if(endpnum > startpnum+1)
{
count += endpnum - startpnum;
startpnum = endpnum - 1;
}
if(endpnum = startpnum + 1 && startpindex <= endpindex)
{
count += 1.0;
startpnum = endpnum;
}
if(startpnum == endpnum)
{
count += ((double)endpindex - (double)startpindex)/Math.Max(endpindex - startpindex, 1000);
}
else if(endpnum = startpnum + 1)
{
count += (Math.Max(startpindex - endpindex, 1000.0) - ((double)startpindex - (double)endpindex))/Math.Max(startpindex - endpindex, 1000);
}
return count;
}
}
public class Node
{
public int startPageNum;
public int startPageIndex;
public int endPageNum;
public int endPageIndex;
public Node left;
public Node right;
public Node(int startpnum, int startpindex, int endpnum, int endpindex)
{
startPageNum = startpnum;
startPageIndex = startpindex;
endPageNum = endpnum;
endPageIndex = endpindex;
left = null;
right = null;
}
}
Complexity of this O(height) of interval tree for any search and read operation.
- sonesh April 24, 2017We will use recursion here, as one has to print event sequence possible, which would require to access it, which means, time goes to exponential.
public static void PrintRec(List<int> data, int sum, int n)
{
if(n == 0)
{
if(sum == data.Sum())
{
PrintList(data);
}
return;
}
if(n == 1)
{
var newList = new List<int>();
newList.AddRange(data);
PrintRec(newList.Add(sum - data.Sum()),sum,0);
return;
}
for(int i = 0; i <= (sum - data.Sum()); i++)
{
var newList = new List<int>();
newList.AddRange(data);
PrintRec(newList.Add(i),sum, n-1);
}
}
public static void PrintPermutation(int sum, int n)
{
if(n < 0 || sum < 0)
{
return;
}
PrintRec(new List<int>(),sum,n);
}
public static void PrintList(List<int> data)
{
foreach(var val in data)
{
Console.Write("{0},",val);
}
Console.WriteLine();
}
The complexity of this O(sum^n), although the actual number is much lower than this.
Space complexity os O(N*N)
public class LogInfo
{
public string fun_name;
public int first_enter_time;
public int last_exit_time;
public int fun_remaining_exit_count;
public LogInfo(string name, string time)
{
fun_name = name;
first_enter_time = time;
fun_remaining_exit_count = 1;
}
public UpdateLogInfo(string action, int time)
{
if(action.Equals("enter"))
{
if(fun_remaining_exit_count == 0)
{
first_enter_time = time;
}
fun_remaining_exit_count++;
}
else if(action.Equals("exit"))
{
if(fun_remaining_exit_count == 0)
{
throw new Exception("Invalid Log Entry");
}
last_exit_time = time;
fun_remaining_exit_count--;
if(fun_remaining_exit_count == 0)
{
PrintLogInfo();
}
}
else
{
throw new Exception("Invalid request");
}
}
public void PrintLogInfo()
{
if(fun_remaining_exit_count == 0)
{
int inclusive_time = last_exit_time - first_enter_time;
Console.WriteLine("{0}: inclusive time = {1}, exclusive time = {2}"
,fun_name
,inclusive_time > 0 ? inclusive_time : inclusive_time == 0 ? 1 : "Invalid"
,inclusive_time > 1 ? inclusive_time-1 : inclusive_time == 1 ? 1 :"Invalid")
}
else
{
throw new Exception("Incomplete data entry");
}
}
}
public void printInclusiveAndExclusiveTime (List<Log> logs)
{
var logMap = new Dictionary<string,LogInfo>();
foreach(var log in logs)
{
if(logMap.ContainsKey(log.fun_name))
{
logMap[fun_name].UpdateLogInfo(log.enterorExit, log.time);
}
else if(log.enterorExit.Equals("enter"))
{
logMap.Add(fun_name, new LogInfo(fun_name, log.time));
}
else
{
throw new Exception("Invalid Log Entry");
}
}
}
Complexity : O(N) + O(K), where N is the size of Logs, and K is the distinct entries of the log function names.
- sonesh April 24, 2017Here is how we will do this in two moves.
public static Node DeepCopy(Node root)
{
if(root == null)
{
return null;
}
Node currentNode = root;
// this loop will create all the new nodes in the same input linkedlist.
while(currentNode != null)
{
Node temp = new Node(currentNode.data);
temp.next = currentNode.next;
currentNode.next = temp;
currentNode = temp.next;
}
currentNode = root;
Node newList = currentNode.next;
Node newCurrentNode = currentNode.next;
while(currentNode != null)
{
newCurrentNode = currentNode.next;
if(currentNode.random != null)
{
newCurrentNode.random = currentNode.random.next;
}
currentNode.next = newCurrentNode.next;
currentNode = newCurrentNode.next;
newCurrentNode.next = currentNode.next;
}
return newList;
}
Complexity is O(n) + O(1).
- sonesh April 20, 2017If I take the question as it is, here is what I would do.
public static Node Merge(Node leftRoot, Node rightRoot)
{
Node currentNode = leftRoot;
while(currentNode.left != null)
{
currentNode = currentNode.left;
}
currentNode.left = rightRoot;
return leftRoot;
}
Complexity : O(log(n)) + O(1).
Now, If there have preconditions such as the data should be merged one after another, like some sort of close merge, or if the tree is binary search tree. I would do the following.
public static Node Merge(Node leftRoot, Node rightRoot)
{
Node leftList = CovertTreeToDoublyLinkedList(leftRoot);
Node rightList = CovertTreeToDoublyLinkedList(rightRoot);
// if the tree is BST, I will do the merging in sorted maner, and If it is just binary, I will put elements one after another.
// I will consider BST
Node mergedList = MergeList(leftList, rightList);
Node start = mergedList;
Node end = mergedList;
while(end.right != null)
{
end = end.right;
}
Node root = ConvertIntoTree(start, end);
return root;
}
public static Node ConvertIntoTree(Node start, Node end)
{
if(start.data > end.data)
{
return null;
}
if(start == end)
{
start.left = null;
start.right = null;
return start;
}
Node currentNode, nextNode;
currentNode = start;nextNode = start;
while(nextNode.right != null)
{
currentNode = currentNode.right;
nextNode = nextNode.right.right;
}
currentNode.left = ConvertIntoTree(start, currentNode.left);
currentNode.right = ConvertIntoTree(currentNode.right, right);
return currentNode;
}
public static Node MergeList(Node left, Node right)
{
if(left == null || right == null)
{
return left==null?right:left;
}
Node currentNode = left;
while(true)
{
if(right == null)
{
while(left.left != null)
{
left = left.left;
}
return left;
}
if(currentNode.right == null)
{
currentNode.right = right;
right.left = currentNode;
while(left.left != null)
{
left = left.left;
}
return left;
}
if(currentNode.data < right.data)
{
currentNode = currentNode.right;
}
else
{
if(currentNode.left == null)
{
Node temp = right;
right = right.right;
temp.right = currentNode;
currentNode.left = temp;
}
else
{
Node currentLeft = currentNode.left;
currentLeft.right = right;
right.left = currentLeft;
currentNode.left = right;
Node temp = right;
right = right.right;
temp.right = currentNode;
}
}
}
}
public static Node CovertTreeToDoublyLinkedList(Node node)
{
if(node.left != null)
{
Node temp = CovertTreeToDoublyLinkedList(node.left);
temp.right = node;
node.left = temp;
}
if(node.right != null)
{
Node temp = CovertTreeToDoublyLinkedList(node.right);
node.right = temp;
temp.left = node;
while(node.right != null)
{
node = node.right;
}
}
return node;
}
Complexity of this is O(n+m) + O(1).
- sonesh April 18, 2017All you have to do is to maintain a dictionary of customerID and the list od dates.
You read the file line by line and for each line, put an entry into the dictionary.
Now, let's assume that data are sorted in the file by the date.assuming each date are written in the file in increasing order only.
You will start like this.
Public static List<int> GetConsecutiveCustomer(string filepath)
{
var customeDateMap = new Dictionary<int,List<Date>>();
var streamReader = new StreamReader(new FileStream(filepath, FileMode.Open, FileAccess.Read), Encoding.UTF8);
var consecutiveCustomers = new HashSet<int>();
while((var line = streamReader.ReadLine()) != null)
{
var customerId = Int32.Parse(line.Split('\t')[1]);
var date = Date.Parse(line.Split('\t')[0]);
if(customeDateMap.ContainsKey(customerId)
{
if(customeDateMap[customerId].Length == 3)
{
customeDateMap[customerId].RemoveAt(2);
}
customeDateMap[customerId].Add(date);
if(!consecutiveCustomers.Contains(customerId))
{
if(customeDateMap[customerId].Length == 3
&& customeDateMap[customerId][0] == customeDateMap[customerId][1].AddDays(1)
&& customeDateMap[customerId][0] == customeDateMap[customerId][2].AddDays(2))
{
consecutiveCustomers.Add(customerId);
}
}
}
else
{
customeDateMap.Add(customerId, new List<date>(){date});
}
}
return consecutiveCustomers.ToList<int>();
}
The time complaxity of this Algorithm is O(N) and the space complexity is O(N) only. Where N is is number of lines in the file.
- sonesh April 18, 2017The partition method of the quick sort will give you your required answer. use three pointers i, j , k, where start to i-1 will be the array containing elements smaller then pivot element, j to end will be containing bigger then pivot and i to j-1 will be containing equal to pivot element, and if i == j then, we found our a unique element. now we will check if we can find unique in left subarray, then that would be first, if not, we will check the current pivot and if that is also not hold true, we will check in the right side.
- sonesh April 13, 2017C#
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleApp4
{
class Program
{
static void Main(string[] args)
{
var nodeMap = new Dictionary<int, Node>();
var list = new LinkedList();
int T = Int32.Parse(Console.ReadLine().Trim());
while(T-- > 0)
{
int action = Int32.Parse(Console.ReadLine().Trim());
if(action == 1)
{
int data = Int32.Parse(Console.ReadLine().Trim());
if(!nodeMap.ContainsKey(data))
{
nodeMap.Add(data, list.InsertFront(data));
}
else
{
list.Delete(nodeMap[data]);
nodeMap.Remove(data);
nodeMap.Add(data, list.InsertFront(data));
}
}
else
{
list.Print();
}
}
Console.ReadLine();
}
}
public class LinkedList
{
public Node root;
public LinkedList()
{
root = null;
}
public Node InsertFront(int val)
{
Node temp = new Node(val);
temp.right = root;
if(root != null)
{
root.left = temp;
}
root = temp;
return temp;
}
public void Delete(Node temp)
{
if(temp.right != null)
{
temp.right.left = temp.left;
}
if(temp.left != null)
{
temp.left.right = temp.right;
}
}
public void Print()
{
Node temp = root;
while(temp != null)
{
Console.Write("{0} -> ", temp.val);
temp = temp.right;
}
Console.WriteLine();
}
}
public class Node
{
public int val;
public Node left;
public Node right;
public Node(int data)
{
val = data;
left = null;
right = null;
}
}
}
Here is what we do in C#
public static void PrintArray(Array arr)
{
if(arr.Rank > 1)
{
foreach(Array i in arr)
{
PrintArray(i);
}
}
else
{
foreach(int i in arr)
{
Console.WriteLine(i);
}
}
}
This will print each array right from their distance from 0th element.
I think a whole array is stored at the same place in the memory, that is the reason, we are able to access any element of an array directly by indexing. But when array dimensions increases, I think it will store each subarray together, by that, you can say if our array was a 4 dimension array, then, it will store each two dimensions array together.
@theProgrammer
No, when you look at the pop() method, we will not be deleting the value from minstack, the deletion happens only when we remove min value itself from the stack. When we get two minimum values in the stack, we insert both of them to minstack.
More loose version of this is to have equal number of values in minstack that of in stack, which means, for every new insert in stack, we will insert min(minstack.peek(), newvalue) to minstack, and for deletion, we delete top value from both. this will also give you an answer,
In my solution, i just compressed the minstack.
You can implement that in O(1) operation using two stacks
Here is the implementation
public class Stack
{
List<int> stack;
List<int> minStack;
public Stack()
{
stack = new List<int>();
minStack = new List<int>();
}
public bool Push(int data)
{
stack.Add(data);
if(Count() == 0)
{
minStack.Add(data);
}
else
{
if(minStack[minStack.Count-1] >= data)
{
minStack.Add(data);
}
}
return true;
}
public int Pop()
{
if(stack.Count > 0)
{
int data = stack[stack.Count -1];
stack.RemoveAt(stack.Count - 1);
if(data == minStack[minStack.Count-1])
{
minStack.RemoveAt(minStack.Count - 1);
}
return data;
}
else
{
return -1;
}
}
public int Min()
{
if(stack.Count > 0)
{
return minStack[minStack.Count-1];
}
else
{
return -1;
}
}
public int Count()
{
return stack.Count;
}
}
Pop() : O(1)
Push : O(1)
Min : O(1)
we can solve this problem using two arrays, which store the count of open brackets and close brackets till current point and based on these two arrays, it finds out the value of K
FindK(string brackets)
{
if(String.IsNullOrWhiteSpace(brackets))
{
return -1; // -1 when you don't find the value of K
}
var openBracketsArray = new int[brackets.Length];
var closeBracketsArray = new int[brackets.Length];
if(brackets[0] == '(')
{
openBracketsArray[0] = 1;
closeBracketsArray[0] = 0;
}
else
{
openBracketsArray[0] = 0;
closeBracketsArray[0] = 1;
}
for(int i = 1; i < brackets.Length; i++)
{
if(brackets[i] == '(')
{
openBracketsArray[i] = openBracketsArray[i-1] + 1;
closeBracketsArray[i] = closeBracketsArray[i-1];
}
else
{
openBracketsArray[i] = openBracketsArray[i-1];
closeBracketsArray[i] = closeBracketsArray[i-1] + 1;
}
}
if(closeBracketsArray[brackets.Length-1] == 0)
{
return 0;
}
for(int i = 0; i < brackets.Length; i++)
{
if(openBracketsArray[i] == closeBracketsArray[brackets.Length-1] - closeBracketsArray[i])
{
return i+1;
}
}
return -1;
}
Complexity of this algorithm is O(N) + O(N).
If we want to remove the space complexity, what we can do it that from each i (ranging from 0 to n-1), check if brackets[0, i] and brackets[i+1, n-1] satisfy the above condition.
but in this, the complexity goes to O(N*N) + O(1).
what about this one
using System;
namespace Helloworld
{
class Program
{
static void Main(string[] args)
{
int N = 250;
PrintLexicographicRes(1,N);
}
public static void PrintLexicographicRes(int i, int N)
{
Console.WriteLine(i);
if(i*10 <= N)
{
PrintLexicographicRes(i*10, N);
}
int j = i + 1;
if(j <= N && j%10 != 0)
{
PrintLexicographicRes(j, N);
}
}
}
}
Complexity of this is O(N) + O(1).
- sonesh April 02, 2017Check this out
public static int FindFirstOccurrence(string str1, string str2)
{
// error condition checks
var charcount = Dictionary<char,int>();
for(int i = 0 ; i < str2.Length;i++)
{
if(!charcount.Contains(str2[i]))
{
charcount[str2[i]] = 1;
}
else
{
charcount[str2[i]]++;
}
}
for(int i = 0 ; i < str1.length;i++)
{
if(charcount.Contains(str1[i])
{
return i;
}
}
return -1;
}
Complexity of this is O(n) + O(1), as the char count is constant.
- sonesh April 01, 2017Actually, one can use logarithmic series to solve this problem.
Check this out
T(n) = n(T(n/2)^2)
Log(T(n)) = Log(n(T(n/2)^2)) => Log(n) + 2Log(T(n/2))
Log(T(n)) = Log(n) + 2(Log(n/2) + 2Log(T(n/4)) and so on which you can write as
Log(T(n)) = Sum(i = 0 to k)(2^i * Log(n/2^i) where k is Log(n)
Now, If you see the values of this sequence varies from Log(n) to n.
Worst case would be that the sum is nLog(n) only, considering every value to n, and i varies from 0 to Log(n), so that sum.
Log(T(n)) = nLog(n)
T(n) = 2^(nLog(n)) = n2^n.
and so this does not have asymtotic bound.
Now we know that the sum would always be more than n, which itself make the
T(n) = 2^n
and so, this does not have any asymptotic lower bound, and so it does not have tight asympotatic bound.
- sonesh April 01, 2017To prove the complexity, use geometric series sum
Here is the logic
public class Set
{
public List<string>() setStrings;
// Constructors and all will come here.
public void PrintPowerSet()
{
// Error conditions such as setStrings is null or does not any data will come here
LinkedList<Set> powerSet = new LinkedList<Set>();
powerSet.AddFirst(new Set(this.setStrings); // adding the first element
foreach(var element in this.setStrings)
{
var enumerator = powerSet.GetEnumerator();
while(enumerator.MoveNext())
{
powerSet.AddFirst(new Set(enumerator.Current.setStrings.Remove(element)); // adding the first element
}
}
var enumerator = powerSet.GetEnumerator();
while(enumerator.MoveNext())
{
Print(enumerator.Current);
}
}
}
public void Print(Set set)
{
Console.WriteLine("{" + set.setStrings + "}");
}
Now complexity of this is 2^0 + 2^1 + 2^2.....2^n-1 = 2^n as per Geometric Series. so the time complexity is O(2^n), space complexity is O(2^n) because, we are storing all the data here PROVIDED that removing an entry from the list take only constant time, which i doubt :).
- sonesh April 01, 2017Stock ticker store Company Stock name and their values, it also keeps tracks of trends as well.
I think what interviewer want to know is to produce one such trend, for example, increment since x in constant time,
One way to do this is to store the data in the dictionary with following format.
var stockticker = new Dictionary<string,Dictionary<DateTime ,double>>();
Now, we can store as many data as possible, and when asked from given point what is current trend, we can call the following function
public static double CurrentTrend(DateTime time)
{
// error conditions and time is not valid input goes here.
return ((dictionary[this.Name][this.LatestEntry] - dictionary[this.Name][time])/dictionary[this.Name][this.LastestEntry])*100; // for % result.
}
Both Name and LatestEntry are available in the Company class. This method will be implemented inside the Company class. StockTicker, will work as collection class here, which will call indivisual class based upon the requirement.
The the insert complexity is O(1), Figuring out any ratio between two times is also O(1) here.
Here you go
public string compressString(string input)
{
if(input == null)
{
throw new ArgumentException();
}
var output = new StringBuilder();
char currentchar;
int occurance = 0;
for(int i = 0;i<input.Length;i++)
{
occurance = 1;
if(input[i] < 48 && input[i] > 57)
{
currentchar = input[i];
for(int j = i; j < input.Length;j++)
{
if(input[j] == currentchar)
{
occurance++;
}
else
{
break;
}
}
output.Append(occurance);
output.Append(currentchar);
i = j-1;
}
output.Append(input[i]);
}
return output.ToString();
}
The complexity of this algorithm is O(N) + O(N).
Still looking for O(N) inplace for this problem, general input are all having worst case O(N) space complexity
If the input is fixed, then we will do the following to produce the required output
public static string[] RecentlyUsedURLs(string[] urls)
{
if(urls == null)
{
throw new ArgumentException()
}
var hashset = new HashSet();
var outputUrls = new List<string>();
for(int i = urls.Length-1;i>=0;i--)
{
if(String.IsNullOrWhiteSpace(urls[i]))
{
Console.WriteLine("the" + i + "th url is invalid");
Continue;
}
if(hashset.Contains(urls[i]))
{
Continue;
}
outputUrls.Add(urls[i]);
hashset.Add(urls[i]);
}
return outputUrls.ToArray();
}
Complexity of this algorithm is O(N) + O(N). Now this is the initial cost. lets say, we are getting these urls dynamically, with each sucessive url, we have to put it in the frond of the array(or list) and we also have to remove the existing one from the array(list).
Inserting a new url would not be difficult, but deleting is, as data re not sorted, one has to traverse the whole array(list) to figure out the location of the old url, and if found, need to delete it and move others accordingly.
All this will require O(N) time for each new url, which is expensive if we are doing lots of insertions.
Now, to overcome this, we will use linkedlist, and to make deletion faster, we have to somehow store the location of the node where particular url is saved.
public static string[] RecentlyUsedURLs(string[] urls)
{
if(urls == null)
{
throw new ArgumentException()
}
var hashtable = new HashTable<string,LinkedList<string>.Enumerator>();
var outputUrls = new LinkedList<string>();
for(int i = 0;i<urls.Length;i++)
{
if(String.IsNullOrWhiteSpace(urls[i]))
{
Console.WriteLine("the" + i + "th url is invalid");
Continue;
}
if(hashtable.Contains(urls[i]))
{
outputUrls.Remove(hashtable[urls[i]].MoveNext);
}
outputUrls.AddFirst(urls[i]);
hashtable.Add(urls[i], outputUrls.GetEnumerator());
}
return outputUrls.ToArray();
}
Now here, the initial set will take O(N) + O(N) complexity, and even after that, every new addition, will only require O(1) + O(1) complexity. The GetEnumerator returns current element which is actually element before the first element of the linkedlist, thatwhy, using MoveNext method to get the correct node(the first one).
- sonesh March 31, 2017Here you go
This will give you the first index of such occurrence
public static int FirstOccurrence(string inputString)
{
if(String.IsNullOrWhiteSpace(inputString)
{
throw new ArgumentException()
}
int j = 0;
boolean foundFirstDigitOccurrence = true;
for(int i = 0 ; i < inputString.Length;i++)
{
j = i;
foundFirstDigitOccurrence = true;
while(j < inputString.Length && inputString[j] != '.')
{
if(inputString[j] < 48 && inputString[j] > 57)
{
foundFirstDigitOccurrence = false;
}
j++;
}
if(foundFirstDigitOccurrence && j != i)
{
return i;
}
i = j;
}
}
This will give you the index of first such digits. You can always print it from i to j.
The complexity is O(N) + O(1) here.
Simple implementation would be like this.
#include System;
#include System.Threading;
#include System.Timers;
public class ThreadSafeTimer
{
private Object thisLock = new Object();
public static void Main()
{
public static Timer t = new Timer();
StartTimer(t);
StopTimer(t);
ResetTimer(t);
}
public static void StartTimer(Timer t)
{
lock(thisLock)
{
if(!t.Enabled)
{
t.Start();
}
}
}
public static void StopTimer(Timer t)
{
lock(thislock)
{
if(t.Enabled)
{
t.Stop();
}
}
}
public static void ResetTimer(Timer t)
{
lock(thisLock)
{
if(!t.Enabled)
{
t.Reset();
}
}
}
}
one can solve this problem in the following way
First Problem
public static int RandomElement(int[] inputArray)
{
if(inputArray == null || inputArray.Length ==0)
{
throw new ArgumentException()
}
else
{
return inputArray[(new Random()).Next(inputArray.Length)];
}
}
This is O(1) time and O(1) space complexity method.
For the second problem, we can do following.
public static int FindRandomElement(int[] inputArray, int[] feq)
{
if(inputArray == null || feq == null || inputArray.Length == 0 || feq;Length == 0 || inputArray.Length != feq.Length)
{
throw new ArgumentException()
}
else
{
int sum = 0;
for(int i = 0 ; i < feq.Length; i++)
{
sum = sum + feq[i];
}
int rand = (new Random()).Next(sum);
for(int i = 0; i < feq.Length;i++)
{
if(rand - feq[i] <= 0)
{
return inputArray[i];
}
else
{
rand = rand - feq[i];
}
}
}
}
The time complexity of this algorithm is O(N) and space complexity is O(1). But algorithm has interger overflow problem, which we can solve by following logic
public static int FindRandomElement(int[] inputArray, int[] feq)
{
if(inputArray == null || feq == null || inputArray.Length == 0 || feq;Length == 0 || inputArray.Length != feq.Length)
{
throw new ArgumentException()
}
else
{
int randsum = 0;
int j = 0;
for(int i = 0 ; i < feq.Length; i++)
{
randsum = randsum + (new Random()).Next(feq[i]);
while(j < feq.Length)
{
if(randsum - feq[j] > 0)
{
randsum = randsum - feq[j];
j++;
}
else
{
break;
}
}
}
while(j < feq.Length)
{
if(randsum - feq[j] > 0)
{
randsum = randsum - feq[j];
j++;
}
else
{
break;
}
}
return inputArray[j];
}
}
The time complexity of this algorithm is again O(N) and space complexity is O(1), and this does not have interger overflow problem.
- sonesh March 30, 2017We can figure out this by keeping two variable one is WasAbsent and ContinousLateCount, and if WasAbsent is true when we found a new Absent, return false, or if ContinousLateCount is 2 when he/she is Late, return false.
Here is how we will write the code
public static boolean ShouldbeRewarded(string attendance)
{
if(String.IsNullOrWhiteSpace(attendance))
{
return true;
}
boolean wasAbsent = false;
int continousLateCount = 0;
boolean WasLateLastDate = false;
for(int i = 0 ; i < attendance.Length;i++)
{
if(attendance[i] == 'A')
{
if(wasAbsent || continousLateCount >= 2)
{
return false;
}
wasAbsent = true;
continousLateCount++;
}
else if(attendance[i] == 'L')
{
if(continousLateCount >= 2)
{
return false;
}
continousLateCount++;
}
else
{
continousLateCount = 0;
}
}
return true;
}
a basic approach would be to traverse the string from the beginning and add new character as needed.
Here is how it goes
public string transformString(string input)
{
if(String.IsNullOrWhiteSpace(input))
{
return input;
}
StringBuilder s = new StringBuilder();
int num = 0;
int j = 0;
while(j < input.Length && (input[j] >= 48 && input[j] <= 57))
{
s.Append(input[j]);
j++;
}
for(int i = j; i < input.Length;i++)
{
num = 0;
j = i+1;
while((j < input.Length) && (input[j] >= 48 && input[j] <= 57))
{
num = num*10 + (input[j] - 48);
j++;
}
while(num-- > 0)
{
s.Append(input[i]);
}
i = j;
}
return s.ToString();
}
Complexity is O(N) in Time and O(N) in space where N is the new size of the string(which is the size of the output string).
- sonesh March 30, 2017Classical example of how a medium of something can be utilized to solve many complex problems
Idea is to stay as close ass possible to medium.
Here is how we will solve it
public static int MinimumDifference(int n, int[] oilmines)
{
if(oilmines != null && oilmines.Length > 0 && n > 0)
{
int mediumMineValue = oilmines.Sum()/n;
int[] companyMineAllocation = new int[n];
int j = 0;
int maxallocation = 0, minallocation=0;
for(int i = 0 ; i < n;i++)
{
companyMineAllocation[i] = 0
while(j < oilmines.Length && companyMineAllocation[i] < mediumMineValue)
{
companyMineAllocation[i]+ = oilmines[j];
j++;
}
if(j < oilmines.Length)
{
if((companyMineAllocation[i] - mediumMineValue) > (mediumMineValue - (companyMineAllocation[i] - oilmines[j-1]))) // making sure we stay as close as possible to medium
{
companyMineAllocation[i] = companyMineAllocation[i]- oilmines[j-1];
j--;
}
}
else if((companyMineAllocation[i] - mediumMineValue) > (mediumMineValue - (companyMineAllocation[i] - oilmines[j-1]))) // making sure we stay as close as possible to medium
{
companyMineAllocation[i] = companyMineAllocation[i]- oilmines[j-1];
j--;
}
else
{
break;
}
if(companyMineAllocation[i] > maxallocation)
{
maxallocation = companyMineAllocation[i];
}
if(companyMineAllocation[i] < minallocation)
{
minallocation = companyMineAllocation[i];
}
}
return maxallocation-minallocation;
}
throw new Exception("invalid input")
}
Complexity : O(N) in time and O(1) in space. It is of type Greedy Algorithms
- sonesh March 30, 2017The string may be consisting of imbalanced(unbalanced) parenthesis but is complete, I mean, for every open parenthesis, there is a corresponding closing parenthesis, If it is not, we will try out best to make it complete till possible.
Here is how we would do it
public string MakeBalanced(sting parenthesis)
{
Stack s = new Stack();
Queue s = new Queue();
if(String.IsNullOrWhiteSpace(parenthesis))
{
return parenthesis;
}
StringBuilder newString = new StringBuilder();
for(int i = 0 ; i < parenthesis.Length;i++)
{
if(parenthesis[i] == '{' || parenthesis[i] == '(' || parenthesis[i] == '[')
{
newString.Append(parenthesis[i]);
if(OpositeParenthesis(q.Peek()) == parenthesis[i])
{
newString.Append(OpositeParenthesis(q.Dequeue()));
}
else
{
s.Push(parenthesis[i]);
}
}
else if(parenthesis[i] == '}' || parenthesis[i] == ')' || parenthesis[i] == ']')
{
if(OpositeParenthesis(s.Peek()) == parenthesis[i])
{
newString.Append(OpositeParenthesis(s.Pop()));
}
else
{
q.Enqueue(parenthesis[i]);
}
}
}
if(s.Count > 0)
{
while(s.Count > 0 && q.Count > 0)
{
if(q.Contains(OpositeParenthesis(s.Peek())))
{
While(q.Peek() != OpositeParenthesis(s.Peek()))
{
q.Enqueue(q.Dequeue());
}
s.Pop();
newString.Append(q.Dequeue());
}
}
}
else
{
newString.Append(q.ToString());
}
return newString.ToString();
}
public char OpositeParenthesis(char parenthesis)
{
if(parenthesis == '{')
{
return '}';
}
else if(parenthesis == '(')
{
return ')';
}
else if(parenthesis == '[')
{
return ']';
}
else if(parenthesis == '}')
{
return '{';
}
else if(parenthesis == ')')
{
return '(';
}
else if(parenthesis == ']')
{
return '[';
}
else
{
return parenthesis;
}
}
Complexity : O(N) space complexity and O(N) if Parenthesis are not randomly placed, if they are, it will require O(N*N) time complexity
- sonesh March 30, 2017If I understood the question properly, here is what interviewer wants
1) Find the number of rows which have any number duplicate column(s)
2) Find the number of rows which have the specific number of duplicate column(s).
Here is how we would do it
Public static int FindDuplicateRowCount(int[][] data, int operationid, int duplicatecolumncount)
{
int duplicaterowcount = 0;
for(int i = 0 ; i < data.length;i++)
{
if(hasDuplicate(data[i],operationid, duplicatecolumncount))
{
duplicaterowcount++
}
}
return duplicaterowcount==0?-1:duplicaterowcount;
}
public static bool hasDuplicate(int[] data, int operationid, int duplicatecolumncount)
{
if((data != null) && (data.length > 1))
{
data = QuickSort(data);
int currentdataelement = data[0];
int currentduplicatecolumncount = 0
for(int j = 1; j < data.length; j++)
{
if(data[j] == currentdataelement)
{
currentduplicatecolumncount++;
while(j < data.length && data[j] == currentdataelement)
{
j++;
}
j--;
}
else
{
currentdataelement = data[j];
}
}
if((currentduplicatecolumncount > 0 && operationid == 1) || (currentduplicatecolumncount >= duplicatecolumncount && operationid == 2))
{
return true;
}
return false;
}
return false;
}
Complexity of this algorithm is O(MNLogN) in time and O(1) in space.
If we use HashSet or std::hash, we can reduce time complexity to O(MN) but the space complexity will increase to O(N).
In this case, the HashSet will be used for figuring out the duplicate elements only.
Basic design is to let database handle everything
You can design the backend in following ways
API -> GetListOfCities() - will go to DB and fetch list of cities into City Class
API -> GetListOfEventsByCity(CityId) - when user select city, this API will return a list of events in Event Class, which can be extended into multiple types of events such as movies, shows, or festivals etc.
API -> GetLocationsByCity(CityId) - This api will return list of locations(theaters, event grounds etc) based upon the city chosen by the user.
API -> GetLocationsByEventandCity(cityid, eventid) - when user select event, we know the eventid and we already know the cityid, we can make this API call to get locations where the event is getting played/organized.
API -> GetEventsByLocationandCity(CityId, LocationId) - this API will return list of events given the locationid and the city id, we are using cityid here to not create different locationid for same theaters in multiple cities.
API -> GetShowTiming(eventid,locationid) - when user select the location, we know the locationid, system will call this API to get the available show timings
API - > GetAvailableSeats(eventid,locationid,showtimeid) - user will select the showtime, and UI will let user select number of seats in next page, we call this API when user has selected the seat count, until this point everything was read-only, so no issue with concurrent calls, but from this point, we have the concurrency issue. this API will only show currently available seats, which can change in future, once the user has selected the seats, we will call this new API
API -> VarifyUserSelectedSeatsAvailable(eventid,locationid,showtimeid,seats) - this will tell us whether all the chosen seats are available or not, if not, we call GetAvailableSeats again for new available seats.
Once VarifyUserSelectedSeatsAvailable passes, we will block those seats for the user, and move the call to the payment gateway. if payment is failed for whatever reason, we will let the user do one more try, and then unblock those seats if not successful.
We will use SQL database in the backend,
City Table
{
CityId
Name
Other properties if needed
}
Event Table
{
EventId
Event Name
Other properties if needed
}
Location Table
{
LocationId
Location Name // like theater name
Other properties if needed
}
ShowTime Table
{
ShowTimeId
ShowTime other details
}
CityEventLocation Table
{
CityEventLocationID
CityId
LocationId
EventId
Custom Properties if needed
}
EventShowTime Table
{
EventShowId
CityEventLocationID
ShowTimeId
Custom Details specific to show times of the cityeventlocationid
}
Seats details are not stored with bookmyshow, once, they have showtime details, they will call custom apis provided by the theaters to get the seats current status.
If they don't have APIs, then, they have two solutions
one is that they manually call those theaters to book the tickets, other would be to save seats details in bookmyshow only and let those theaters book seats based upon bookmyshow page availability, (like, bookmyshow can provide admin page to those theaters to book windows tickets using admin page of bookmyshow only).
Following are the properties of the binary tree
1) each node can have at max two children.
2) each node in the tree has only one path from the root node reaching to it.
For this questions, we also have to make sure it is only one tree, not a set of trees, so the answer would be yes only when all the input nodes can be formed as one tree satisfying above two properties
Now, we can have two solutions
First one has O(N) time complexity and O(1) space complexity but it makes updates in tree data.
Here is how it goes
public boolean canForm(TreeNode[] Node)
{
int lowestval = 0;
foreach(TreeNode node in Node)
{
if (lowestval > node.val)
{
lowestval = node.val;
}
}
lowestval = lowestval - 100; // putting more lower value is not present in any of the nodes
foreach(TreeNode node in Node)
{
if(node.left != null)
{
if(node.left.val != lowestval)
{
node.left.val = lowestval;
}
else
{
return false;
}
}
if(node.right != null)
{
if(node.right.val != lowestval)
{
node.right.val = lowestval;
}
else
{
return false;
}
}
}
int rootnode = 0;
foreach(TreeNode node in Node)
{
if (node.val != lowestval)
{
rootnode++;
}
}
if(rootnode != 1)
{
return false;
}
return true;
}
The Second one has O(N) time complexity and O(N) space complexity where it does not updates in tree data.
Here is how it goes
public boolean canForm(TreeNode[] Node)
{
HashSet<TreeNode> hashset = new HashSet<TreeNode>();
foreach(TreeNode node in Node)
{
if(node.left != null)
{
if(hashset.Contains(node.left))
{
return false;
}
else
{
hashset.Add(node.left);
}
}
if(node.right != null)
{
if(hashset.Contains(node.right))
{
return false;
}
else
{
hashset.Add(node.right);
}
}
}
int rootnode = 0;
foreach(TreeNode node in Node)
{
if(!hashset.Contains(node))
{
rootnode++;
}
}
if(rootnode != 1)
{
return false;
}
return true;
}
start from first index, move towards end, keep a flag which will tell if all the numbers are 9 or not,
we will stop at end, and see if the flag is true, if no, we increment the number and if it goes to 10, we set it to 0 and move back with 1,
if the flag is true, we increase the size of the array by one, and set all the numbers to 0 except first one, we set that to 1.
Here is the strategy one can follows
Lets say Kindle is used for reading materials. and we have the data with us stored in the cloud.
Two point we have keep in the mind are following
Need to give priority to user previous searches
Need to give different priority to cloud entities
An entities are the reading materials
Here is the storage plan for Kindle locally
We will create trie of searches, Whenever user do a search, we store that information into the trie, if it is already present in the trie, we increment it's search count.
Each node in the trie have an integer value which tells how much time a search lead to this point.
Here is how we keep cloud data.
We create trie in the cloud as well, which is readonly from the user prospective, and can only be updated by internal systems. this makes multiple reads easier.
Here each node store the popularity index for an entity represented upto this point.
Now here is how we fulfil user ask for autocomplete result.
Whenever user start typing, start searching in internal data, and we show the result which are searched maximum times by this user, along with that we also do parallel search in cloud, and get the data from that as well, as soon as we go out of our internal band, we start showing cloud data, now because cloud data were searched along with local data, user will not see any delay, other then, the time our service is taking from getting data from the cloud for further queries.
Now here we can trade off, based upon business requirement, which is like, lets say someone launches a new book and want amazon to tell his kindle users, we can priorities this book more then others.
Complexity : O(length of user query search) Time + O(data stored in kindle)
Now here we can optimized the search in the trie by telling it where to go and fine maximum searched item, but for that we have to store one more entity at each node which will tell where to go to find max, this will increase our insert time to little extend.
Consider each person as one node, and start from your self, keep one queue, which will keep the list of friends of friends.
Q <= Priority Queue which store lowest hop person on top
Insert me into the Q with hop = 0;
While(Q is not empty)
Node current = take the top node from the queue.
Search Node in Hierarchy and figure out its Friends, (We may even store that in the queue, but this increase queue size in case of large system
Insert all its friend with hop one more then current.
If any of the friend is the required person, we store the algorithm and report the hop.
Complexity : Depends upon friends count and search efficiency in the hierarchy.
- sonesh July 16, 2015Quick Algorithm
For each statement, Library X depends Library Y, Create an entry if not created already in a Dictionary for X. else add Y to it.
While(Dictionary is not empty)
Take first element which is having null list or empty list if exists, delete it from the dictionary, and delete all its presence in any other nodes last as well.
If not, then there is a cycle here, and you can report it and exit.
Complexity : O(number of relations) Time.
- sonesh July 16, 2015Update the tree to have to know how many node under any node including parent.
Once we know that, all we have to do it generate a random number using random() function between 1 to N(noth inclusive), then go that element and return it.
Preprocessing time :
Space : O(N)
Time : O(N)
Per request time : O(Log(N)) time + O(1) space.
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 ...
From your example, it looks like they only care for the length of the path.
We will do following
Worst case Complexity is O(n*n) + O(nlog(n)), as we will be looking for all possible path. Although the avg case complexity would be O(n) + O(log(n)).
- sonesh May 01, 2017