Hey guys !!! As per demand here are the past 2 years asked questions during the M.Tech Interviews. Special thanks to all my batchmates and juniors who helped me by remembering and sharing the questions.
1. What is 2NF? Identify & Perform 2NF on a given relation.
3. What is AVL tree? Why is it used? Apllications.
4. Given a set of n nuts of different sizes and n bolts of different sizes. There is a one-one mapping
5. What are forks? How are they related to system calls? What are interrupts? How are they used?
6. Given a recursion solve for it's time complexity analysis without using master's theorem. Prove that the derived recurrence is correct.
7. Write a recursive equation to compute power of 2? Can you optimise it?
8. What is heap? Where it is used?
9. What is NP hard?
10. What is difference between conjunctions of disjunctions and disjunctions of conjunctions?
11. What is push down automaton? Mention any real world application of turing machines?
12. Birthday Paradox. How many people must be there in a room to make the probability 100% that at-least two people in the room have same birthday?
13. Number of states of NFA for string of a given length.
14. Given a graph , each edge has a number which is the max height of a truck that can pass from that edge , now we need to find a path from given source and destination such that maximum height truck can go.
15. Suppose we are at intersection of 4 roads and these roads are infinite, there is some treasure in one of those 4 now we need to find that treasure. can you find its complexity, if the treasure is at k distance from centre?
16. Difference between bigO and smallO?
17. KMP/Rabin Karp Matching?
18. Bit Representation of a Number in some given radix.
19. How can you find median of unsorted numbers efficiently? Median of Medians?
20. When to use quicksort over mergesort? Time Complexity of quicksort? Prove it. Can you find the kth largest element in an array using the approach taken by quicksort?
21. Prove that tree is an acyclic graph.
22. Can binary search be applied on linked list? If yes how? Corner case of low+high/2 overflow.
23. Propositional logic symbolic write. Atleast 1 apple, Only 1 apple,..etc.
24. Prove that leaf node has degree 1.
25. Definition of Average time complexity? Given a for loop on board, derive the avg time complexity using probabilities.
26. Draw graph of log function.
27. Write code for insertion sort.
28. How to find the longest path of a given graph?
29. can you make a program to find if the number is prime? Why you write i*i? Can you prove it that we need to go only till root(n) elements?
30. A rectangular grid was drawn and I have to find the number of paths from one corner to another?
32. A processor (which can have infinite number of cores) and then told about a program where the sequential part is 20 percent and rest is parallel. Find the minimum number of cores required to achieve 10 times speed up?
33. Write a program to find product of leaves of a binary tree using recursion.
34. you have an array in which initially elements are in increasing order and after that elements are in decreasing order. find the point where change occured.
35. How will u check whether the tree is a BST ?
36. Difference between binary search and ternary search ? which is bigger logn with base 2 or logn with base 3? Then why we prefer binary search over ternary search ? write recurrence relation for binary search and ternary search? Now find the complexity using those recurrence relation.
37. Questions related to probabilities and linear algebra.
38. Kruskals Algorithm. Correctness of Greedy Algo using exchange argument
39. Find bugs in given code.
40. What do you mean by Query Optimization? Mention some techniques used to do the same.
41. Which is better row major order or column major order? Can you write the code to initialize a single dimensional array with 0. Explain how row major and column major ordering works.In a 2D array how row major and column major work? What is locality of reference?
42. Say you have a mobile and you want to execute 10 processes in that mobile. Describe how this whole thing gonna happen inside.
Answer they were expecting was detailed low level explaination of multiprocessing. Based on the answer they asked other questions like types of interrupt, where do interrupts are stored,what is interrupt service routine, how interrupt service routine address is resolved. And some questions on scheduling.
43. Say u have a function f which takes a real number as input and outputs a real number. Given f is monotonic find real number x where the output of f is zero. Approach and write code for it.
44. Which is the best CPU scheduling strategy?
Considering the waiting time parameter, which one is best? Why?(the intuition behind why it's better than others)
45. What is a semaphore?(Does the definition of a semaphore involve a cyclic argument?) How can it be implemented?(just in software? Or requires support from hardware?
46. Write a Program to find the log of a number and to find the n-th smallest number in an unsorted array. Give Proof of correctness of both the program.
47. Given a graph G, find a recurrence relation that describes the number of possible walks starting at point A. SImilar to this https://math.stackexchange.com/questions/1838063/recurrence-relations-walk-on-a-graph.
48. Whats bipartite, how to check given graph is bipartite or not, algorithm for it. Proof that your algortihm is correct.
I have asked many other friends and juniors. Will be adding more when i get more responses !!!
1. What is 2NF? Identify & Perform 2NF on a given relation.
2. What is CSMA/CA ? Proactive and Reactive Routers? Backoff Algorithm?
3. What is AVL tree? Why is it used? Apllications.
4. Given a set of n nuts of different sizes and n bolts of different sizes. There is a one-one mapping
between nuts and bolts. Match nuts and bolts efficiently.
5. What are forks? How are they related to system calls? What are interrupts? How are they used?
6. Given a recursion solve for it's time complexity analysis without using master's theorem. Prove that the derived recurrence is correct.
7. Write a recursive equation to compute power of 2? Can you optimise it?
8. What is heap? Where it is used?
9. What is NP hard?
10. What is difference between conjunctions of disjunctions and disjunctions of conjunctions?
11. What is push down automaton? Mention any real world application of turing machines?
12. Birthday Paradox. How many people must be there in a room to make the probability 100% that at-least two people in the room have same birthday?
13. Number of states of NFA for string of a given length.
14. Given a graph , each edge has a number which is the max height of a truck that can pass from that edge , now we need to find a path from given source and destination such that maximum height truck can go.
15. Suppose we are at intersection of 4 roads and these roads are infinite, there is some treasure in one of those 4 now we need to find that treasure. can you find its complexity, if the treasure is at k distance from centre?
16. Difference between bigO and smallO?
17. KMP/Rabin Karp Matching?
18. Bit Representation of a Number in some given radix.
19. How can you find median of unsorted numbers efficiently? Median of Medians?
20. When to use quicksort over mergesort? Time Complexity of quicksort? Prove it. Can you find the kth largest element in an array using the approach taken by quicksort?
21. Prove that tree is an acyclic graph.
22. Can binary search be applied on linked list? If yes how? Corner case of low+high/2 overflow.
23. Propositional logic symbolic write. Atleast 1 apple, Only 1 apple,..etc.
24. Prove that leaf node has degree 1.
25. Definition of Average time complexity? Given a for loop on board, derive the avg time complexity using probabilities.
26. Draw graph of log function.
27. Write code for insertion sort.
28. How to find the longest path of a given graph?
29. can you make a program to find if the number is prime? Why you write i*i? Can you prove it that we need to go only till root(n) elements?
30. A rectangular grid was drawn and I have to find the number of paths from one corner to another?
31. Give the mathematical proof for If a number is divisible by 3 then the sum of digits must me divisible by 3 ?
32. A processor (which can have infinite number of cores) and then told about a program where the sequential part is 20 percent and rest is parallel. Find the minimum number of cores required to achieve 10 times speed up?
33. Write a program to find product of leaves of a binary tree using recursion.
34. you have an array in which initially elements are in increasing order and after that elements are in decreasing order. find the point where change occured.
35. How will u check whether the tree is a BST ?
36. Difference between binary search and ternary search ? which is bigger logn with base 2 or logn with base 3? Then why we prefer binary search over ternary search ? write recurrence relation for binary search and ternary search? Now find the complexity using those recurrence relation.
37. Questions related to probabilities and linear algebra.
38. Kruskals Algorithm. Correctness of Greedy Algo using exchange argument
39. Find bugs in given code.
40. What do you mean by Query Optimization? Mention some techniques used to do the same.
41. Which is better row major order or column major order? Can you write the code to initialize a single dimensional array with 0. Explain how row major and column major ordering works.In a 2D array how row major and column major work? What is locality of reference?
42. Say you have a mobile and you want to execute 10 processes in that mobile. Describe how this whole thing gonna happen inside.
Answer they were expecting was detailed low level explaination of multiprocessing. Based on the answer they asked other questions like types of interrupt, where do interrupts are stored,what is interrupt service routine, how interrupt service routine address is resolved. And some questions on scheduling.
43. Say u have a function f which takes a real number as input and outputs a real number. Given f is monotonic find real number x where the output of f is zero. Approach and write code for it.
44. Which is the best CPU scheduling strategy?
Considering the waiting time parameter, which one is best? Why?(the intuition behind why it's better than others)
45. What is a semaphore?(Does the definition of a semaphore involve a cyclic argument?) How can it be implemented?(just in software? Or requires support from hardware?
46. Write a Program to find the log of a number and to find the n-th smallest number in an unsorted array. Give Proof of correctness of both the program.
47. Given a graph G, find a recurrence relation that describes the number of possible walks starting at point A. SImilar to this https://math.stackexchange.com/questions/1838063/recurrence-relations-walk-on-a-graph.
48. Whats bipartite, how to check given graph is bipartite or not, algorithm for it. Proof that your algortihm is correct.
I have asked many other friends and juniors. Will be adding more when i get more responses !!!
Affordable laptop repair service in bhubaneswar.
ReplyDeleteLaptop Hospital
Sir are there opportunities for foreign placement. If so ,how should I prepare for it. What criteria do companies look , for high package. Coding , projects, research work, theoretical knowledge which should I focus more.
ReplyDeleteForeign placements are easy to get in IITs as most of them come on day 3 and onwards.You dont need to do anything for it. haha... Don't look for those pakages, they are actually very low if you take into account the expenses in the country and othe aspects. Indian placements are hard to crack. Try for it.
DeleteRuturaj Sir, Does two year gap matter during placements?
ReplyDeleteI dropped last year but didn't get good rank. So, thinking to give my best next year.
Doesn't matter for selection shortlisting but in final interview round they might ask. Just explain them properly the gap. They would understand. No worries.
DeleteOkay thanks a lot!
Delete