CSE Company Interview Questions

PROBLEM : Given a binary tree, return all root-to-leaf paths. For example, given the following binary tree:    1  /   \ 2     3  \   5   All root-to-leaf paths are: ["1->2->5", "1->3"] -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- /**  * Definition for a binary tree node.  * struct TreeNode {  *     int val;  *     TreeNode *left;  *     TreeNode *right;  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}  * };  */ class Solution { public:     vector<string> binaryTreePaths(TreeNode* root) {         vector<string> vec ;         if(root==NULL)             return vec ;                     string str="" ;         CheckAllPaths(root,str,vec) ;         return vec ;     }         void CheckAllPaths(TreeNode *root,string str,vector<string> &

PROBLEM : Given a positive integer, output its complement number. The complement strategy is to flip the bits of its binary representation. Note: The given integer is guaranteed to fit within the range of a 32-bit signed integer. You could assume no leading zero bit in the integer’s binary representation. Example 1: Input: 5 Output: 2 Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2. Example 2: Input: 1 Output: 0 Explanation: The binary representation of 1 is 1 (no leading zero bits), and its complement is 0. So you need to output 0. -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- class Solution { public:     int findComplement(int num) {         int copy=num ;         int pos=0 ;                 while(copy){             num=num^(1<<po

PROBLEM : The Hamming distance between two integers is the number of positions at which the corresponding bits are different. Given two integers x and y, calculate the Hamming distance. Note: 0 = x, y < 2^31. Example: Input: x = 1, y = 4 Output: 2 Explanation: 1   (0 0 0 1) 4   (0 1 0 0)           ^   ^ The above arrows point to positions where the corresponding bits are different. -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- class Solution { public:     int hammingDistance(int x, int y) {         int Xor=(x^y) ;         int diff=0 ;               while(Xor){             Xor=(Xor&(Xor-1)) ;             diff++ ;         }         return diff ;     } }; ---------------------------------------------------------------------------------

PROBLEM : Given a binary search tree, write a function kthSmallest to find the kth smallest element in it. Note: You may assume k is always valid, 1 ? k ? BST's total elements. -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- /**  * Definition for a binary tree node.  * struct TreeNode {  *     int val;  *     TreeNode *left;  *     TreeNode *right;  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}  * };  */ class Solution { public:     int kthSmallest(TreeNode* root, int k) {         int min ;         KthSallestEle(root,&k,&min) ;         return min ;     }         void KthSallestEle(TreeNode *root,int *k,int *min){         if(root->left)             KthSallestEle(root->left,&(*k),&(*min)) ;         (*k)-- ;         if((*k)==0){             (*min)=root->val ;             r

PROBLEM : Given a number (N) of 32 bit size you are required to print the number you get by inverting bits in its binary representation (i.e. 1 is made 0 and 0 is made 1). In other words we are required to negate(~) the number. Input: The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. Each test case contains an integer N. Output: For each test case in a new line print the required output. Constraints: 1<=T<=100 1<=N<=10^8+9 Example: Input: 2 4289384 1 Output: 4290677911 4294967294 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; int main() { int t ; cin>>t ; while(t--){    unsigned int no ;    cin>>no ;      cout<<(~no)<<endl ; } return 0; } ------------------

PROBLEM : Given a number x and two positions (from right side) in binary representation of x, write a program that swaps n bits at given two positions and returns the result. Input: The first line of input contains an integer T denoting the number of test cases. The first line of each test case is X, P1, P2 and N. X is a number, P1 and P2 is two given position and swaps N number of bits at given two position. Output: Print the result. Constraints: 1 = T = 15 1 = X = 200 0 = P1 < P2 = 8 1 = N = 5 Example: Input: 2 47 1 5 3 28 0 3 2 Output: 227 7 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; int SwapBits(int ,int ,int ,int ) ; int main() { int t ; cin>>t ; while(t--){    int no,p1,p2,k ;      cin>>no>>p1>>p2>>k ;  

PROBLEM : Sort a linked list using insertion sort.     -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- /**  * Definition for singly-linked list.  * struct ListNode {  *     int val;  *     ListNode *next;  *     ListNode(int x) : val(x), next(NULL) {}  * };  */ class Solution { public:     ListNode* insertionSortList(ListNode* head) {         if(head==NULL||head->next==NULL)             return head ;                     ListNode* list=NULL ;         ListNode* temp ;                 while(head){             temp=head->next ;             head->next=NULL ;             list=InplaceSort(list,head) ;             head=temp ;         }         return list ;     }         ListNode* InplaceSort(ListNode* list,ListNode* node){         if(list==NULL)             return node ;                 if(list->val>

PROBLEM : You are given an array A containing 2*N+2 positive numbers, out of which N numbers are repeated exactly once and the other two numbers occur exactly once and are distinct. You need to find the other two numbers and print them in ascending order. Input : The first line contains a value T, which denotes the number of test cases. Then T test cases follow .The first line of each test case contains a value N. The next line contains 2*N+2 space separated integers. Output : Print in a new line the two numbers in ascending order. Constraints : 1<=T<=100 1<=N<=10^6 1<=A[i]<=5*10^8 Example: Input : 2 2 1 2 3 2 1 4 1 2 1 3 2 Output : 3 4 1 3     -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; int main() {     int t ;     cin>>t ;     while(t

PROBLEM : Given a number you are required to complete two tasks Task 1 .Generate a new number form the old number by changing  the number of zeroes in the binary representation of that  number to 1 Task  2. Find what will be added to old number to generate the new number . Input: The first line consists of T test cases. Then T test cases follow. The next T lines will consist of a number N. Output: Output the difference between those 2 numbers separated by the new number. Constraints: 1<=T<=10000 1<=N<=100000 Example: Input: 2 8 6 Output: 7 15 1 7 Explanation: For first test case there are 3 zeroes in binary representation of 8 . Changing them to 1 will give 15. Difference between two is 7.     -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; #include<m

PROBLEM : Given a number N, Your task is to find the  length of the longest consecutive 1's in its binary representation. Input: The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. Each test case contains an integer N. Output: For each test case in a new line print the length of the longest consecutive 1's in N's binary representation. Constraints: 1<=T<100 1<=N<=1000 Example: Input 2 14 222 Output 3 4     -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; int main() {     int t ;     cin>>t ;     while(t--){         int no ;         cin>>no ;                 int count=0 ;         while(no){             no=(no&(no<<1)) ;             count++ ;         }         cout&

PROBLEM : Given a number n, the task is to check whether it can be expressed as a sum of two or more consecutive numbers or not. Examples: Input  : n = 10 Output : 1 It can be expressed as sum of two consecutive numbers 1 + 2 + 3 + 4. Input  : n = 16 Output : 0 It cannot be expressed as sum of two consecutive numbers. Input  : n = 5 Output : 1 2 + 3 = 5 Input: The first line contains 'T' denoting the number of test cases. Then follows description of test cases. Each test case contains a single positive integer n. Output: Print "1" if number can be expressed as sum of consecutives else "0". (Without the double quotes) Constraints: 1<=T<=200 0<=N<=10^18 Example: Input : 2 4 5 Output : 0 1     -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream>

PROBLEM : Given two numbers n and k, change the kth bit of the number n to '0' if it is  '1', else return the number n itself. Input: First line of the input contains an intger T denoting the number of test case. Each test contains a single line containg two space seperated integers n and k respectively. Output: For each test case output a single integer. Constraints: 1<=T<=100 1<=N<=106 Example: Input: 2 13 3 13 2 Ouput: 13 9 Explanation: Test Case 1: n = 13 ('1101') k=3 return 13 Test Case 2: n = 13('1101') k=2 return 9('1001')     -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; int main() { int t ; cin>>t ; while(t--){    int no,k ;    cin>>no>>k ;      int temp,count ;

PROBLEM : Given an array of integers, every element appears twice except for one. Find that single one in linear time complexity and without using extra memory. Input: The first line of input consists number of the test cases. The description of T test cases is as follows: The first line of each test case contains the size of the array, and the second line has the elements of the array. Output: In each separate line print the number that appears only once in the array. Constraints: 1 = T = 70 1 = N = 100 0 = A[i] = 100000 Example: Input: 1 11 1 2 4 3 3 2 5 6 1 6 5 Output: 4     -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; int main() {     int t ;     cin>>t ;     while(t--){         int no ;         cin>>no ;                 int arr[no] ;      

PROBLEM : Given an array A[] having n positive elements. The task to create another array B[] such as B[i] is XOR of all elements of array A[] except A[i]. Examples: Input : A[] = {2, 1, 5, 9} Output : B[] = {13, 14, 10, 6} Input : A[] = {2, 1, 3, 6} Output : B[] = {4, 7, 5, 0} Input: The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. Each test case contains an integer N denoting the size of the array. Then in the next line are N space separated values of the array (B[]). Output: For each test case in a new line print the space separated values of the new array (B[]). Constraints: 1<=T<=100 1<=N<=100 1<=A[]<=100 Example: 2 4 2 1 5 9 4 2 1 3 6 Output: 13 14 10 6 4 7 5 0     -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostre

PROBLEM : Given an array ‘A’ of n positive integers. Contents of A[ ] are copied to another array ‘B’, but numbers are shuffled and one element is removed. The task is to find the missing element. Examples: Input : A[] = {4, 8, 1, 3, 7},         B[] = {7, 4, 3, 1} Output : 8 Input : A[] = {12, 10, 15, 23, 11, 30},         B[] = {15, 12, 23, 11, 30} Output : 10 Input: The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. The first line of each test case contains an integers N, where N is the size of array. The second line of each test case contains N space separated integers denoting elements of the array A[ ]. The third line of each test case contains N-1 space separated integers denoting elements of the array B [ ]. Output: Corresponding to each test case, in a new line, print the missing number. Constraints: 1 <= T <=1000 1 <= N <=10000 1 <= A, B <=100000000 Example: Input: 2 5 1 3 5

PROBLEM : Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom. For example: Given the following binary tree,    1            <---  /   \ 2     3         <---  \     \   5     4       <--- You should return [1, 3, 4].     -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- /**  * Definition for a binary tree node.  * struct TreeNode {  *     int val;  *     TreeNode *left;  *     TreeNode *right;  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}  * };  */ class Solution { public:     vector<int> rightSideView(TreeNode* root) {         vector<int> vec ;         if(root==NULL)             return vec ;                     int height=heightTree(root) ;         for(int i=0;i<height;i++){      

PROBLEM : You are given a Double Link List with one pointer of each node pointing to the next node just like in a single link list. The second pointer which is arbitary pointer  which can point to any node in the list and not just the previous node. The task is to complete the function copyList which take one argument the head of the linked list to be copied and should return the head of the copied linked list. Input: You have to complete the method which takes one argument: the head of the linked list. You should not read any input from stdin/console. The struct Node has a data part which stores the data and a next pointer which points to the next element of the linked list and an arbitrary pointer (arb) which points to any arbitrary node . There are multiple test cases. For each test case, this method will be called individually. Output: Your function should return the head of the copied list. Constraints: 1 <=T<= 100 1 <=N<= 100 1 <=Q<= 100 1 &

PROBLEM : Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number. An example is the root-to-leaf path 1->2->3 which represents the number 123. Find the total sum of all root-to-leaf numbers. For example,     1    / \   2   3 The root-to-leaf path 1->2 represents the number 12. The root-to-leaf path 1->3 represents the number 13. Return the sum = 12 + 13 = 25.     -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- /**  * Definition for a binary tree node.  * struct TreeNode {  *     int val;  *     TreeNode *left;  *     TreeNode *right;  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}  * };  */ class Solution { public:     int sumNumbers(TreeNode* root) {         if(root==NULL)             return 0 ;                     if(root->left==N

PROBLEM : Given a binary tree, flatten it to a linked list in-place. For example, Given          1         / \        2   5       / \   \      3   4   6     The flattened tree should look like:    1     \      2       \        3         \          4           \            5             \              6     -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- /**  * Definition for a binary tree node.  * struct TreeNode {  *     int val;  *     TreeNode *left;  *     TreeNode *right;  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}  * };  */ class Solution { public:     void flatten(TreeNode* root) {         while(root){             if(root->left){                 TreeNode *ptr=root->left ;                                 while(ptr->right)                     ptr=ptr->right ;  

PROBLEM : Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum. For example: Given the below binary tree and sum = 22,               5              / \             4   8            /   / \           11  13  4          /  \    / \         7    2  5   1         return [    [5,4,11,2],    [5,8,4,5] ] -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : (Recursive Solution) -------------------------------------------------------------------------------- /**  * Definition for a binary tree node.  * struct TreeNode {  *     int val;  *     TreeNode *left;  *     TreeNode *right;  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}  * };  */ class Solution { public:     vector<vector<int>> pathSum(TreeNode* root, int sum) {         vector<vector<int>> vec ;         vector<int> row ;         PathSumCheck(root,s

PROBLEM : Given inorder and postorder traversal of a tree, construct the binary tree. Note: You may assume that duplicates do not exist in the tree. -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : (Recursive Solution) -------------------------------------------------------------------------------- /**  * Definition for a binary tree node.  * struct TreeNode {  *     int val;  *     TreeNode *left;  *     TreeNode *right;  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}  * };  */ class Solution { public:     TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {         TreeNode* root ;         int size=inorder.size() ;         if(size==0)             return NULL ;                 size-- ;         root=BuiltPostOrderTree(inorder,postorder,0,size,&size) ;         return root ;     }         TreeNode* BuiltPostOrderTree(vector<int> &inord

PROBLEM : Given preorder and inorder traversal of a tree, construct the binary tree. Note: You may assume that duplicates do not exist in the tree. -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : (Recursive Solution) -------------------------------------------------------------------------------- /**  * Definition for a binary tree node.  * struct TreeNode {  *     int val;  *     TreeNode *left;  *     TreeNode *right;  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}  * };  */ class Solution { public:     TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {         TreeNode* root ;         int size=inorder.size() ;         if(size==0)             return NULL ;                 size=0 ;         root=BuiltPostOrderTree(inorder,preorder,0,inorder.size()-1,&size) ;         return root ;     }         TreeNode* BuiltPostOrderTree(vector<int>

PROBLEM : Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between). For example: Given binary tree [3,9,20,null,null,15,7],     3    / \   9  20     /  \    15   7   return its zigzag level order traversal as: [   [3],   [20,9],   [15,7] ] -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- /**  * Definition for a binary tree node.  * struct TreeNode {  *     int val;  *     TreeNode *left;  *     TreeNode *right;  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}  * };  */ class Solution { public:     vector<vector<int>> zigzagLevelOrder(TreeNode* root) {         int height=FindHeight(root) ;               vector<vector<int>> vec(height,vector<int> {});    

PROBLEM : Given a binary tree, return the postorder traversal of its nodes' values. For example: Given binary tree {1,#,2,3},    1     \      2     /    3 return [3,2,1]. Note: Recursive solution is trivial, could you do it iteratively? -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : (Recursive Solution) -------------------------------------------------------------------------------- /**  * Definition for a binary tree node.  * struct TreeNode {  *     int val;  *     TreeNode *left;  *     TreeNode *right;  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}  * };  */ class Solution { public:     vector<int> postorderTraversal(TreeNode* root) {         vector<int> vec ;         if(root==NULL)         return vec ;                 postorder(root,vec) ;         return vec ;     }         void postorder(TreeNode* root,vector<int> &vec){     if(root==NU

PROBLEM : Given a binary tree, return the preorder traversal of its nodes' values. For example: Given binary tree {1,#,2,3},    1     \      2     /    3 return [1,2,3]. Note: Recursive solution is trivial, could you do it iteratively? -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : (Recursive Solution) -------------------------------------------------------------------------------- /**  * Definition for a binary tree node.  * struct TreeNode {  *     int val;  *     TreeNode *left;  *     TreeNode *right;  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}  * };  */ class Solution { public:     vector<int> preorderTraversal(TreeNode* root) {     vector<int> vec ;     if(root==NULL)     return vec ;         preorder(root,vec) ;     return vec ;     }         void preorder(TreeNode* root,vector<int> &vec){     if(root==NULL)     return ;  

PROBLEM : Given two polynomial numbers represented by a linked list. The task is to complete the  function addPolynomial that adds these lists meaning adds the coefficients who have same variable powers. Example: Input:      1st number = 5x^2 + 4x^1 + 2x^0      2nd number = 5x^1 + 5x^0 Output:         5x^2 + 9x^1 + 7x^0 Input:      1st number = 5x^3 + 4x^2 + 2x^0      2nd number = 5x^1 + 5x^0 Output:         5x^3 + 4x^2 + 5x^1 + 7x^0 Input: The first line of input contains an integer T denoting the no of test cases. Then in the next line is an integer N denoting the no of terms of first polynomial. In the next line are N space separated pairs x and y where x denotes the coefficient and y denotes the power. Similarly In the next line is an integer M denoting the no of terms of the second polynomial and in the line following it are N space separated pairs for second polynomial. Output: For each test case in a new line print the required polynomial in decreasing orde

PROBLEM : Given a string, find the length of the longest substring without repeating characters. Examples: Given "abcabcbb", the answer is "abc", which the length is 3. Given "bbbbb", the answer is "b", with the length of 1. Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring. -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- class Solution { public:     int lengthOfLongestSubstring(string s) {         if(s.length()==0)             return 0 ;                     int map[256] ;         int i, LastVisit, CurrLen,MaxLen ;         CurrLen=1 ;         MaxLen=1 ;                 for(i=0;i<256;i++)             map[i]=-1 ;                 map[s[0]]=0 ;        

PROBLEM : Reverse digits of an integer. Example1: x = 123, return 321 Example2: x = -123, return -321 Have you thought about this? Here are some good questions to ask before coding. Bonus points for you if you have already thought through this! If the integer's last digit is 0, what should the output be? ie, cases such as 10, 100. Did you notice that the reversed integer might overflow? Assume the input is a 32-bit integer, then the reverse of 1000000003 overflows. How should you handle such cases? For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows. Note: The input is assumed to be a 32-bit signed integer. Your function should return 0 when the reversed integer overflows. -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- class Solution { public:     int reverse(int

PROBLEM : Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level). For example: Given binary tree [3,9,20,null,null,15,7],     3    / \   9  20     /  \    15   7   return its level order traversal as: [   [3],   [9,20],   [15,7] ] -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION :( Recursive Solution ) -------------------------------------------------------------------------------- /**  * Definition for a binary tree node.  * struct TreeNode {  *     int val;  *     TreeNode *left;  *     TreeNode *right;  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}  * };  */ class Solution { public:     vector<vector<int>> levelOrder(TreeNode* root) {         int height=FindHeight(root) ;                 vector<vector<int>> vec(height,vector<int> {});         LevelTraversal(root,vec,0) ;        

PROBLEM : Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is defined as follows: The left subtree of a node contains only nodes with keys less than the node's key. The right subtree of a node contains only nodes with keys greater than the node's key. Both the left and right subtrees must also be binary search trees. Example 1:     2    / \   1   3 Binary tree [2,1,3], return true. Example 2:     1    / \   2   3 Binary tree [1,2,3], return false. -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION :( Recursive Solution ) -------------------------------------------------------------------------------- /**  * Definition for a binary tree node.  * struct TreeNode {  *     int val;  *     TreeNode *left;  *     TreeNode *right;  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}  * };  */ class Solution { public:     bool isValidBST(TreeNode*