Coding Interview Questions With Solutions: geeksforgeeks

Showing posts with label geeksforgeeks. 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;
}

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);
}

Leaders in an array

Krishna Chaurasia array, geeksforgeeks, leader 1 comment

An element is leader if it is greater than all the elements to its right side. And the rightmost element is always a leader.
For example int the array {16, 17, 4, 3, 5, 2}, leaders are 17, 5 and 2.

#include <iostream>
using namespace std;

int main(){
    int arr[] = {18, 16, 17, 4, 3, 5, 2};
    int n = sizeof(arr)/sizeof(arr[0]);
    int maxSoFar = arr[n - 1];
    cout << maxSoFar << " ";
    for(int i = n - 2; i >= 0 ; i--){
        if(arr[i] > maxSoFar){
            cout << arr[i] << " ";
            maxSoFar = arr[i];
        }
    }
    cout << endl;
    return 0;
}

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;
}

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

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

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

53. Maximum Subarray

Krishna Chaurasia array, geeksforgeeks, interviewbit, Kadene's algorithm, leetcode, maximum sum No comments

Write an efficient C program to find the sum of contiguous subarray within a one-dimensional array of numbers which has the largest sum.

Approach : Kadene's Algorithm


def max_subarray(A):
max_ending_here = max_so_far = 0
    for x in A:
        max_ending_here = max(0, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

Source: Wikipedia

Solution:

int maxSubArray(int* nums, int numsSize) {
    int curSum, maxSum = INT_MIN;
    curSum = 0;
    for(int i = 0; i < numsSize; i++){
        curSum = curSum + nums[i];
        if(curSum > maxSum){
            maxSum = curSum;
        }
        if(curSum < 0){
            curSum = 0;
        }
    }
    return maxSum;
}

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

13. Roman to Integer

Krishna Chaurasia geeksforgeeks, interview, interviewbit, leetcode No comments

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

Approach:

According to an answer taken from here[1]:

A number written in Arabic numerals can be broken into digits. For example, 1903 is composed of 1 (one thousand), 9 (nine hundreds), 0 (zero tens), and 3 (three units). To write the Roman numeral, each of the non-zero digits should be treated separately. In the above example, 1,000 = M, 900 = CM, and 3 = III. Therefore, 1903 = MCMIII.
The symbols "I", "X", "C", and "M" can be repeated three times in succession, but no more. (They may appear more than three times if they appear non-sequentially, such as XXXIX.) "V", "L", and "D" can never be repeated.
"I" can be subtracted from "V" and "X" only. "X" can be subtracted from "L" and "C" only. "C" can be subtracted from "D" and "M" only. "V", "L", and "D" can never be subtracted.
Only one small-value symbol may be subtracted from any large-value symbol.

Here is the code for the same:

class Solution {
public:
    int romanToInt(string s) {
        map<char, int> m;
        m['I'] = 1;
        m['V'] = 5;
        m['X'] = 10;
        m['L'] = 50;
        m['C'] = 100;
        m['D'] = 500;
        m['M'] = 1000;
        int len = s.length();
        if(len <= 0)
            return 0;
        int result = m[s[len - 1]];
        for(int i = len - 2; i >= 0; i--){
            if(m[s[i]] < m[s[i+1]]){
                result = result - m[s[i]];
            }else{
                result = result + m[s[i]];
            }
        }
        return result;
    }
};

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

66. Plus One

Krishna Chaurasia geeksforgeeks, interviewbit, leetcode, programming No comments

Given a non-negative integer represented as a non-empty array of digits, plus one to the integer. You may assume the integer do not contain any leading zero, except the number 0 itself. The digits are stored such that the most significant digit is at the head of the list.

Example:

If the vector has [1, 2, 3], the returned vector should be [1, 2, 4] as 123 + 1 = 124.

Approach:

Add 1 to the last digit
Forward the carry if exists and continue to the beginning

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int sum, carry = 0, n = digits.size();
        //add 1 to the last digit
        sum = digits[n - 1] + 1;
        //see if there is a carry generated
        if(sum > 9){
            carry = 1;
            digits[n - 1] = sum % 10;
        }else{
            //if no carry, add 1 to lsb and return
            digits[n - 1] = sum;
            return digits;
        }
        //if carry, keep adding till there is no carry
        for(int i = n - 2; i >= 0; i--){
            sum = digits[i] + carry;
            if(sum > 9){
                carry = 1;
                digits[i] = sum % 10;
            }else{
                //if no carry, return
                digits[i] = sum;
                return digits;
            }
        }
        //add 1 to the front if there is carry in the end
        if(carry){
            digits.insert(digits.begin(), 1);       
        }
        return digits;
    }
};

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

26. Remove Duplicates from Sorted Array

Krishna Chaurasia geeksforgeeks, interviewbit, leetcode, programming, sorted array No comments

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,:

Given input array nums = [1,1,2], your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the new length.

Approach:

1. Copy the current element to the current index if it does not match to the previous element, else move to the next element and repeat the same for all elements of the array.

class Solution {
public:
    
    int removeDuplicates(vector<int>& nums) {
        int numsSize = nums.size();
        if(numsSize <= 1)
            return numsSize;
        
        int j = 1;
        for(int i = 1; i < numsSize; i++){
            if(nums[i] != nums[i - 1]){
                nums[j++] = nums[i];
                j++;
            }
        }
        return j;
    }
};

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

58. Length of Last Word

Krishna Chaurasia geeksforgeeks, interviewbit, leetcode, string No comments

Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string. If the last word does not exist, return 0.

Note: A word is defined as a character sequence consists of non-space characters only.

For example, for s = "Hello World", return 5.

Approach: The idea is to start traversing from the right (ignoring the right spaces if any) and continue till a space is not found.

class Solution {
public:
    int lengthOfLastWord(string s) {
        int len = s.length();
        int i = len - 1, j = 0;
        while(s[i] == ' '){
            i--;
        }
        while(i >=0 && ((s[i] >= 'a' && s[i] <= 'z') || (s[i] >= 'A' && s[i] <= 'Z'))){
            i--;
            j++;
        }
        return j;
    }
};

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

21. Merge Two Sorted Lists

Krishna Chaurasia geeksforgeeks, leetcode, linked list, programming No comments

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Approach : Here is the simple recursive solution to solve the problem:

Base case : Return one of the lists if another is NULL
Else recursively call the function with appropriate values of two current nodes' values

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* a, struct ListNode* b) {
    struct ListNode* result = NULL;  
   /* Base cases */  
   if (a == NULL)  
     return(b);  
   else if (b == NULL)  
     return(a);  
   /* Pick either a or b, and recur */  
   if (a->val <= b->val) {  
     result = a;  
     result->next = mergeTwoLists(a->next, b);  
   }else {  
     result = b;  
     result->next = mergeTwoLists(a, b->next);  
   }  
   return(result); 
}

Here is the link to the ideone solution : https://ideone.com/V6zDKA

Saturday, 12 February 2022

Product of Array Except Self

Saturday, 22 January 2022

Reverse String

Saturday, 8 January 2022

Reverse Vowels of a String

Sunday, 12 September 2021

Find Peak Element

Thursday, 29 July 2021

Leaders in an array

Sunday, 13 August 2017

101. Symmetric Tree

104. Maximum Depth of Binary Tree

Saturday, 12 August 2017

83. Remove Duplicates from Sorted List

Friday, 11 August 2017

70. Climbing Stairs

69. Sqrt(x)

Sunday, 6 August 2017

67. Add Binary

Thursday, 20 July 2017

14. Longest Common Prefix

53. Maximum Subarray

13. Roman to Integer

Monday, 17 July 2017

66. Plus One

26. Remove Duplicates from Sorted Array

Friday, 14 July 2017

58. Length of Last Word

21. Merge Two Sorted Lists

Contact Me

Popular Posts

Categories

Blog Archive

| Privacy Policy | Disclaimer | Resume |

| Terms of Use | Contact Us | Site Map |