Do lot of hard work and practice of Data Structures and Algorithms based questions. I personally recommend you Coding Ninjas and Geeks For Geeks for interview preparation.
Make your resume short and try to make it of one page only and do mention all your skills which you are confident of in your resume.
Given a “2 x n” board and tiles of size “2 x 1”, count the number of ways to tile the given board using the 2 x 1 tiles. A tile can either be placed horizontally i.e., as a 1 x 2 tile or vertically i.e., as 2 x 1 tile.
Examples:
Input n = 3
Output: 3
Explanation:
We need 3 tiles to tile the board of size 2 x 3.
We can tile the board ...
Given an encoded string where repetitions of substrings are represented as substring followed by count of substrings. For example, if encrypted string is “ab2cd2” and k=4 , so output will be ‘b’ because decrypted string is “ababcdcd” and 4th character is ‘b’.
Note: Frequency of encrypted substring can be of more than one digit. For example, in “ab12c3”, ab is repeated 12 time...
I simply decrypt the string by reading substring and their frequency and append current substring to the decrypted string and after the end of traversal of given string our answer will be kth element of the decrypted string.
Given an array of positive and negative integers, print x if +x and -x are present in the array.
I asked for some clarifications whether I should print all distinct x‘s or if I should print an x if a pair of +x and -x is encountered. The first approach I told was to use a map and I was keeping a flag for +x and -x if it’s found once. Later he asked me to print all pairs, so I stored the frequencies of all the elements in the map and iterated through the negative elements and for each eleme...
Here the interviewer told me about an app called splitwise which i had used once. In the application each user adds the amount he spends and it’s shared equally among users of the app. The aim is to minimise the number of give and take operations. I initially thought of a very naive approach where I wanted to create classes for each person and expenditure and iterate through the expenditures of...
At the beginning of this round, the interviewer asked me about the data structures I knew. Linked lists, trees, graphs, arrays etc. was my answer. He asked me how well I knew Dynamic Programming. I said I wasn’t strong in that and he said that he would ask me a question on dynamic programming for sure.
Given a generic tree, find the count of all special nodes. A node is a special node if there is a path from root to that node with all distinct elements. The input was not a pointer to a tree. He’d give me an adjacency list and an array of values where the value of ith node in the adjacency list is the ith element in the values array. He asked me not a create a tree out of the given information...
I suggested to do a depth first search keeping a set which contains all elements upto a given node. Once I reach a particular node, I check if it’s already in the set. If its already in the set, I return because that element has already been visited and is not a special node. Otherwise, I increase the count of a global variable by 1 and push that element to the set. Then I go through the adjace...
Given an integer array, find the longest subsequence with adjacent numbers having a digit in common. Eg: 1 12 44 29 33 96 89 . The longest subsequence here is { 1 12 29 96 89} and the answer is 5.
I initially tried a 2D DP solution where dp[i][j] indicates the length of the longest sequence with ending at i containing j as a digit. It’s a N X 10 DP matrix. The interviewer asked me why I needed a 2D DP solution and I struggled to convince him. I wrote the code for it. I...
The interviewer asked me if I was comfortable with the interview process so far and how the previous interviews were. I said it was good and he gave me the first problem to solve.
Given a binary tree, modify the tree satisfying the following constrains :
Value at root must be the sum of left child and right child (not subtrees).
You can’t reduce the value at any node. You can only increase it.
Value of root node must be minimum
I drew a few trees and asked him the output for those examples. He asked me to say it myself and I did. I thought of doing a post-order traversal as we need to visit the root’s left and right child before visiting root. In the post-order traversal, we keep the sum of root’s left and right child in a variable sum. We take the difference of this sum and root data. If the sum is greater than root’...
Given an array A of size N containing 0s, 1s, and 2s; you need to sort the array in ascending order. You can scan the array only once.
I solved this question using three-pointers and this problem was a variation of dutch national flag problem. The interviewer was satisfied by my approach as this was the most optimal approach.
The interviewer asked me some Computer Science fundamentals in this round as well as some behavioural questions.
This is most basic question of OS and I explained it very well using a tabular representation.
I firstly told him necessary conditions for deadlock and then explained him that if we don’t let all conditions fulfilled for deadlock then it may be prevented.
Implement a Trie data structure and write functions to insert and search for a few words in it.
I wrote a class to implement a character Trie using a vector of nodes as children. He asked me to improve on space. So I used a hashmap to store the child nodes only if a child exists. I wrote the code for insertion and finding a word and walked him through.
Given two strings a and b consisting of lowercase characters. The task is to check whether two given strings are anagram of each other or not. An anagram of a string is another string that contains same characters, only the order of characters can be different. For example, “act” and “tac” are anagram of each other.
I implemented it first by sorting two strings and comparing them. He asked me to write a better approach. So I used a hashmap to do it.
Thank You So much. For the splitwise question DP something like subset sum will work.
Count special nodes in Generic tree Solution