Coding Interview Preparation

A collection of most expected coding problems in technical interviews of Microsoft, Amazon, Google, Facebook, etc. This repository contains relevant links from GeeksForGeeks and LeetCode.

For testing any code in your local system, please provide the input in the input.txt file. The output will be generated in output.txt file. This is implemented for simple testing.

References

• Must do coding questions by GeeksForGeeks
• LeetCode

Table of Contents

1. Arrays
2. Strings
3. Linked List
4. Stacks
5. Queues
6. Trees
7. Heap
8. Graphs
9. Divide And Conquer
10. Greedy
11. Dynamic Programming
12. Backtracking
13. Bit Manipulation

Arrays

• Maximum sum obtained in k operations by choosing start or end element - Question 2 in this link

  • Problem Statement: You are given an array and the only operations are to pick the elements from beginning or from the end. Obtain the maximum possible using exactly the k-operations.

• Minimum Number of Platforms Required for a Railway Station

  • Problem Statement: Given arrival and departure times of all trains that reach a Railway Station, find the minimum number of platforms required for the railway station so that no train waits.

• Trapping Rain Water

  • Problem Statement: Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

• Data Stream as Disjoint Intervals

  • Problem Statement: Given a data stream input of non-negative integers a1, a2, ..., an, ..., summarize the numbers seen so far as a list of disjoint intervals.

• Longest Consecutive Sequence

  • Problem Statement: Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

• Rotate a matrix by 90 degree, no extra space

  • Problem Statement: You are given an n x n 2D matrix. Rotate the image by 90 degrees.

• Print all subsets for a given sum

  • Problem Statement: Given an array of integers and a sum, the task is to print all subsets of given array with sum equal to given sum.

• Set matrix to zero

  • Problem Statement: Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.

• Find the maximum element in an array which is first increasing and then decreasing

  • Problem Statement: Given an array of integers which is initially increasing and then decreasing, find the maximum value in the array.

• Find the duplicate element

  • Problem Statement: Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

• Longest Increasing Subsequence

  • Problem Statement: Given an unsorted array of integers, find the length of longest increasing subsequence.

• Subarray sum equals k

  • Problem Statement: Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

• Search in Rotated Sorted Array

  • Problem Statement: Search a target value K in an array A sorted in ascending order which is rotated at some pivot unknown to you beforehand. If found in the array return its index, otherwise return -1.

• Subarray sum closest to 0

  • Problem Statement: Given an array of both positive and negative numbers, the task is to find out the subarray whose sum is closest to 0.

Strings

• KMP Pattern Matching Algorithm

  • Problem Statement: Given a string S and pattern P, determine if P is a substring of S.
  • Solution: KMP Algorithm in C++

• Longest substring with distinct characters

  • Problem Statement: Given a string, find the length of the longest substring without repeating characters.

• Word Break

  • Problem Statement: Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

• Palindrome Permutation

  • Problem Statement: Given a non-empty string s, determine if it is a permutation of some palindrome p.
  • Solution: Permutation Palindrome

• Sort array of strings by frequency

  • Problem Statement: Given an array of strings, sort the array by the frequency of occurence of strings.
  • Solution: Sort Strings by Frequency

Linked List

• Copy List with Random Pointer

  • Problem Statement: A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
  • GeeksForGeeks Solution

• Reveverse nodes in K Groups

  • Problem Statement: Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

Stacks

Queues

Trees

• Delete Node in BST

  • Problem Statement: Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference of the BST.

• Range Sum Query

  • Problem Statement: Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

• Cousins in a binary tree

  • Problem Statement: Given the root of a binary tree with unique values, and the values x and y of two different nodes in the tree. Return true if and only if the nodes corresponding to the values x and y are cousins.
  • GeeksForGeeks Solution

• Construct Binary Tree from Preorder and Inorder Traversal

  • Problem Statement: Given preorder and inorder traversal of a tree, construct the binary tree.

• Validate BST

  • Problem Statement: Given a binary tree, determine if it is a valid binary search tree (BST).

• Lowest Common Ancestor of a Binary Tree

  • Problem Statement: Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree. The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants.

• Root to leaf path sum

  • Problem Statement: Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

Heap

• K most frequent words

  • Problem Statement: Given a non-empty list of words, return the k most frequent elements. Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, then the word with the lower alphabetical order comes first.

• Merge K sorted lists

  • Problem Statement: Merge k sorted linked lists and return it as one sorted list.

• Kth Largest Element in an Array

  • Problem Statement: Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Graphs

• Snake and Ladder Problem
  • Problem Statement: Given a snake and ladder board, find the minimum number of dice throws required to reach the destination cell from 1st cell.

Divide and Conquer

Greedy

Dynamic Programming

• Number of Paths with at most K turns
  • Problem Statement: Given a M x N matrix, count number of paths to reach bottom right from top left with maximum k turns allowed. Only down and right moves are allowed.

Backtracking

Bit Manipulation

• Element that occurs once

  • Problem Statement: Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.

• Count ways to assign unique cap to every person

  • Problem Statement: There are N different types of caps each having a unique id from 1 to N. There are N persons each having a collection of a variable number of caps. Count the total number of ways such that none of them is wearing the same type of cap.