Coding Interview Questions With Solutions: leetcode

Showing posts with label leetcode. Show all posts

Saturday, 12 February 2022

Product of Array Except Self

Krishna Chaurasia array, geeksforgeeks, interview, leetcode, programming 5 comments

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements ofnums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

Approach:

The idea is to traverse the array couple of times from left to right once and right to left once keeping track the accumulated product so far from both the sides.

/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
vector<int> productExceptSelf(vector<int> &nums) {
    int numsSize = nums.size();
    vector<int> result(numsSize);
    int temp = 1;
    // stores the product on the left of each element excluding itself
    for(int i = 0; i < numsSize; i++){
        result[i] = temp;
        temp = temp * nums[i];
    }
    temp = 1;
    // stores the product on the left times product on right of each element excluding itself
    for(int i = numsSize - 1; i >= 0; i--){
        result[i] = result[i] * temp;
        temp = temp * nums[i];
    }
    return result;
}

Reverse String

Krishna Chaurasia geeksforgeeks, interview, leetcode, reversal, string 2 comments

Write a function that takes a string as input and reverse the same.

Example:

Given s = "hello", return "olleh".

Approach: The idea is to swap the last and the first characters till the middle is reached.

string reverseString(string &s) {
    int low = 0, high = s.length() - 1;
    while(low < high){
        char t = s[low];
        s[low] = s[high];
        s[high] = t;
        low++;
        high--;
    }
    return s;
}

Reverse Vowels of a String

Krishna Chaurasia coding, geeksforgeeks, interview, leetcode, reversal, string 3 comments

Write a function that takes a string as input and reverse only the vowels of a string.

Example 1:
Given s = "hello", return "holle".

Approach: The idea is to traverse the string from both ends while skipping the non-vowels characters from both ends.

char* reverseVowels(char* s) {
    int low = 0, high = strlen(s) - 1;
    char c;
    while(low < high){
        //move forward to skip consonant
        while(low < strlen(s) && tolower(s[low]) != 'a' && tolower(s[low]) != 'e' && tolower(s[low]) != 'i' && tolower(s[low]) != 'o' && tolower(s[low]) != 'u'){
            low++;
        }
        //move backward to skip consonant
        while(low < high && tolower(s[high]) != 'a' && tolower(s[high]) != 'e' && tolower(s[high]) != 'i' && tolower(s[high]) != 'o' && tolower(s[high]) != 'u'){
            high--;
        }
        if(low < high){
           c = s[low];
           s[low] = s[high];
           s[high] = c;
           low++;
           high--;
        }
    }
    return s;
}

Move Zeros

Krishna Chaurasia array, interview, leetcode, segregate 2 comments

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

Note:

You must do this in-place without making a copy of the array.
Minimize the total number of operations.

void moveZeroes(int* nums, int numsSize){
    int i = 0, j = 0;
    for(i = 0; i < numsSize; i++){
        //copy non-zero elements
        if(nums[i] != 0){
            nums[j] = nums[i];
            j++;
        }
    }
    //put zeros in the end
    while(j < numsSize){
        nums[j++] = 0;
    }
}

Find Peak Element

Krishna Chaurasia array, binary search, geeksforgeeks, interview, leetcode 7 comments

A peak element is an element that is greater than its neighbors.

Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that num[-1] = num[n] = -∞.

For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.

Approach: Use binary search.

int peakIndex(int *arr, int low, int high){
    if(low == high){
        return low;
    }
    if(low + 1 == high){
        if(arr[low] >= arr[high]){
            return low;
        }else{
            return high;
        }
    }
    int mid = (low + high) / 2;
    if(arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1]){
        return mid;
    }else if(arr[mid] < arr[mid - 1]){
        //peak lies on the left since arr[mid - 1] > arr[mid] && arr[0] = -infinity so there has to be an element which is peak on the left
        return peakIndex(arr, low, mid - 1);
    }else{
        //peak lies on the right
        return peakIndex(arr, mid + 1, high);
    }
}

int findPeakElement(int* nums, int numsSize) {
    return peakIndex(nums, 0, numsSize - 1);
}

Valid Palindrome

Krishna Chaurasia interview, leetcode, palindrome, programming, string 2 comments

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example, "A man, a plan, a canal: Panama" is a palindrome.

"race a car" is not a palindrome.

bool isPalindrome(char* s) {
   int i, j, len;
   len = strlen(s);
   i = 0; j = len - 1;
   while(i < j){

       // skip non alpha chars from start

       while(i < len && !isalnum(s[i])){
           i++;
       }

       // skip non alpha chars from end

       while(j >= 0 && !isalnum(s[j])){
           j--;
       }

       if(i < j && tolower(s[i]) != tolower(s[j])){
           return false;
       }

       i++;
       j--;
   }
   return true;
}

Balanced Binary Tree

Krishna Chaurasia binary tree, height, leetcode, trees 3 comments

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

/**
 * 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 height(TreeNode *root){
        if(root == NULL){
            return 0;
        }
        int leftHeight = height(root->left);
        if(leftHeight == -1){
            return -1;
        }
        int rightHeight = height(root->right);
        if(rightHeight == -1){
            return -1;
        }
        if(abs(leftHeight - rightHeight) > 1){
            return -1;
        }
        return 1 + max(leftHeight, rightHeight);
    }
    
    bool isBalanced(TreeNode* root) {
        if(root == NULL){
            return true;
        }
        if(height(root) == -1){
            return false;
        }
        return true;
    }
};

101. Symmetric Tree

Krishna Chaurasia geeksforgeeks, interview, interviewbit, leetcode, programming 2 comments

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

But the following [1,2,2,null,3,null,3] is not:

Approach : Use the simple recursive solution.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool checkIfSymmetric(struct TreeNode* n1, struct TreeNode* n2){
    if(n1 == NULL && n2 == NULL)
        return true;
    if(n1 == NULL || n2 == NULL)
        return false;
    
    if(n1->val == n2->val){
        return checkIfSymmetric(n1->left, n2->right) && checkIfSymmetric(n1->right, n2->left);
    }
    return false;
}
bool isSymmetric(struct TreeNode* root) {
   if(root == NULL){
       return true;
   }
   return checkIfSymmetric(root->left, root->right);
}

104. Maximum Depth of Binary Tree

Krishna Chaurasia binary tree, geeksforgeeks, leetcode, trees No comments

Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. Height of empty binary tree is 0 and with just root node is 1.

For the above example, the maximum depth is 3 following the path 1-2-5.

Approach : Using the recursive approach as implemented below.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int max(int a, int b){
    return a >= b ? a : b;
}
int maxDepth(struct TreeNode* root) {
    int height;
    //base case
    if(root == NULL){
        return 0;
    }
    //recursively compute left and right height and return the maximum
    height = 1 + max(maxDepth(root->left), maxDepth(root->right));
    return height;
}

83. Remove Duplicates from Sorted List

Krishna Chaurasia duplicate, geeksforgeeks, interviewbit, leetcode, linked list 1 comment

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

Approach : The key to solve the problem is using the right loop condition and maintaining necessary pointers in each loop.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* deleteDuplicates(struct ListNode* head) {
    struct ListNode *cur, *_next;
    if(head == NULL || head->next == NULL){
        return head;
    }
    cur = head;
    while(cur && cur->next){
        //set the pointer of the current next to the next node if duplicate is found
        if(cur->val == cur->next->val){
            _next = cur->next->next;
            free(cur->next);
            cur->next = _next;
        }else{
            //else just move forward to next node
            cur = cur->next;
        }
    }
    return head;
}

100. Same Tree

Krishna Chaurasia binary tree, leetcode, trees No comments

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.
Below are some examples:

Ex. 1:
Tree 1:
10
        20 30
40 50 60 70

Tree 2:
10
        20 30
40 50 60 70
Tree 1 & Tree 2 are identical.

Example 2:
Tree 1:
10
        20 30
40 50 60 70
Tree 2:
10
        20 30
40 60 50 70

Trees 1 & 2 are not identical as their structures are same but values at nodes 50 and 60 differ.

Example 3:
Tree 1:
10
20 30
40 50 60
Tree 2:
10
20 30
40 50 60

Trees 1 & 2 are not identical as the structures are not same as 60 is on left subtree of node 30 in Tree 1 but on right subtree of node 30 in Tree 2.

Approach : Use the simple recursive solution.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    if(p == NULL && q == NULL){
        return true;
    }
    if(p == NULL && q != NULL || p != NULL && q == NULL){
        return false;
    }
    if(p->val == q->val){
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
    return false;
}

70. Climbing Stairs

Krishna Chaurasia geeksforgeeks, interview, leetcode, programming 1 comment

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Approach : The standard recursive solution times out so the idea is to use the iterative solution to find the nth fibonacci number.

int climbStairs(int n) {
    int f1 = 2;
    int f2 = 1;
    if(n == 1) {
        return f2;
    } else if(n == 2) {
        return f1;
    }

    int fn;
    for(int i = 3; i <= n; i++) {
        fn = f1 + f2;
        f2 = f1;
        f1 = fn;
    }
    return fn;
}

Here is the link to the ideone solution : http://ideone.com/ErEU6E

69. Sqrt(x)

Krishna Chaurasia binary search, geeksforgeeks, interviewbit, leetcode No comments

Implement int sqrt(int x).

Return the floor if x is not a perfect square.

Approach : Using binary search making sure that overflow does not happen by taking long long.

class Solution {
public:
    int mySqrt(int x) {
        if(x <= 1){
      return x;
 }
     int low = 0, high = x / 2;
     //long to prevent overflow
 long long mid;
 while(low <= high){
     mid = (low + high) / 2;
     //needs to be long to prevent overflow
     long long t = mid * mid;
     //second part is to return floor if x is not perfect square
     if( t == x || ((t < x) && ((mid + 1) * (mid + 1) > x))){
      break;
     } else if(x < t){
      high = mid - 1;
     }else{
      low = mid + 1;
     }
 }
 return mid;
    }
};

Here is the link to the ideone solution : http://ideone.com/taTCKu

38. Count and Say

Krishna Chaurasia interview, leetcode, programming 1 comment

Problem: The count-and-say sequence is the sequence of integers with the first five terms as following:


1.     1

2.     11
3.     21

4.     1211

5.     111221

1 is read off as "one 1" or 11.


11 is read off as "two 1s" or 21.


21 is read off as "one 2, then one 1" or 1211.

Given an integer n, generate the nth term of the count-and-say sequence.

Note: Each term of the sequence of integers will be represented as a string.

Example 1:


Input: 1

Output: "1"

Example 2:


Input: 4

Output: "1211"

Approach: The solution is straight forward. The appendNext method is run over n times where n is the input.

class Solution {
public:
    public:
 
    string appendNext(string str){
        string str1;
        char ch = str[0];
        int chCount = 1;
        for(int i = 1; i <= str.size(); i++){
            if (str[i] == ch){
                chCount++;
            }
            else {
                char chr = chCount + '0';
                str1 = str1 + chr;
                str1 = str1 + ch;
                ch = str[i];
                chCount = 1;
            }
        }
        return str1;
    }
    
    string countAndSay(int n) {
        if (n == 1) {
            return "1";
        }
        string str1 = "1";
        string strn;
        for (int i = 1; i < n; i++){
            strn = appendNext(str1);
            str1 = strn;
        }
        return strn;
    }
};

Here is the link to the ideone solution : http://ideone.com/tbYXUM

67. Add Binary

Krishna Chaurasia binary, geeksforgeeks, interviewbit, leetcode, string 1 comment

Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100"

Approach : The idea is to start from the right and keep adding digits and forwarding carry (if any). Also, take care of the case when one of them gets exhausted. For that, keep adding zero to the other one and forward carry if required.

string Solution::addBinary(string a, string b) {
    int lenA = a.length(), lenB = b.length();
    int i = lenA - 1, j = lenB - 1;
    int carry = 0;
    stack<char> out;
    int sum = 0;
    while(i >= 0 || j >= 0){
        if(i >= 0 && j >= 0){
            //convert to int and add
            sum = a[i] - '0' + b[j] - '0' + carry;
            i--;
            j--;
        } else{
            //string a is exhausted
            if(i < 0){
                sum = b[j] - '0' + carry;
                j--;
            }
            //string b is exhausted
            else{
                sum = a[i] - '0' + carry;
                i--;
            }
        }
        //setting the carry accordingly
        if(sum > 1){
            carry = 1;
        }else{
            carry = 0;
        }
        sum = sum % 2;
        //convert back to character
        char aChar = '0' + sum;
        out.push(aChar);
    }

    //for final carry
    if(carry){
        out.push('1');
    }
    string res = "";
    //reverse the output
    while(!out.empty()){
        res = res + out.top();
        out.pop();
    }
    return res;
}

Here is the link to the ideone solution : http://ideone.com/o5r3Eq

283. Move Zeroes

Krishna Chaurasia array, interview, leetcode, programming No comments

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

Note:

You must do this in-place without making a copy of the array.
Minimize the total number of operations.

Approach: Bring forward the non-zero values using a for loop and then fill the zeros at the end.

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int j = 0, n = nums.size();
        //move the non-zero elements to the front
        for(int i = 0; i < n; i++){
            if(nums[i] != 0){
                nums[j++] = nums[i];
            }
        }
        //fill the remaining right indices with zeros
        for(int i = j; i < n; i++){
            nums[i] = 0;
        }
    }
};

Here is the link to the ideone solution : http://ideone.com/O0MRQa

14. Longest Common Prefix

Krishna Chaurasia geeksforgeeks, google, interviewbit, leetcode, string No comments

Given an array of strings, the problem is to find out the longest common prefix of all the strings.

Return empty string if no common prefix exists.

Approach:
Use the brute force way approach to solve the problem. First find the shortest string (as the longest common prefix can be of at most this length), minLenStr, which takes O(n) time. Next, compare each string one by one with this minLenStr, and keep an variable which indicates the rightmost index of minLenStr, this loop takes O(mn) where m is the shortest length of all strings.

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string out = "";
        if(strs.size() == 0 ){
            return out;
        }
        //find the minimum length string since the longest common prefix can't be more than that length
        string minLenStr = strs[0];
        for(int i = 1; i < strs.size(); i++){
            if(strs[i].length() < minLenStr.length()){
                minLenStr = strs[i];
            }
        }
        //loop over all string and match all the starting characters, update the maximum size possible based on the starting matching characters
        int end = minLenStr.length();
        for(int i = 0; i < strs.size(); i++){
            int j = 0;
            while(j < end){
                if(minLenStr[j] != strs[i][j]){
                    break;
                }
                j++;
            }
            //update the maximum possible size
            if(j < end){
                end = j;
            }
        }
        return minLenStr.substr(0, end);
    }
};

Here is the link to the ideone solution : http://ideone.com/CWFcI8

Saturday, 12 February 2022

Product of Array Except Self

Saturday, 22 January 2022

Reverse String

Saturday, 8 January 2022

Reverse Vowels of a String

Monday, 4 October 2021

Move Zeros

Sunday, 12 September 2021

Find Peak Element

Tuesday, 7 September 2021

Valid Palindrome

Sunday, 1 August 2021

Balanced Binary Tree

Sunday, 13 August 2017

101. Symmetric Tree

104. Maximum Depth of Binary Tree

Saturday, 12 August 2017

83. Remove Duplicates from Sorted List

100. Same Tree

Friday, 11 August 2017

70. Climbing Stairs

69. Sqrt(x)

Tuesday, 8 August 2017

38. Count and Say

Sunday, 6 August 2017

67. Add Binary

Friday, 21 July 2017

283. Move Zeroes

Thursday, 20 July 2017

14. Longest Common Prefix

Contact Me

Popular Posts

Categories

Blog Archive

| Privacy Policy | Disclaimer | Resume |

| Terms of Use | Contact Us | Site Map |