ms1797’s gists

ms1797 / dijkstras_algo.cpp

Created March 15, 2019 15:13

Find single source shortest path - Dijkstra's algorithm and print the distance as well as path

	/*
	Find single source shortest path - Dijkstra's algo
	and print the distance as well as path
	Input:
	n-vertices , m-edges
	u , v , w - undirected edge with weight w
	9 14
	0 1 4
	0 7 8
	1 7 11

ms1797 / coin_change.cpp

Last active January 4, 2019 07:31

Given a value N, find the number of ways to make change for N cents, if we have infinite supply of each of S = { S1, S2, .. , Sm} valued coins. The order of coins doesn’t matter .

	/*
	Coin Change Problem:

	Given a value N, find the number of ways to make change for N cents, if we have infinite supply of each of
	S = { S1, S2, .. , Sm} valued coins. The order of coins doesn’t matter.
	For example, for N = 4 and S = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}.
	So output should be 4.
	For N = 10 and S = {2, 5, 3, 6}, there are five solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}.
	So the output should be 5.
	*/

ms1797 / BinaryTreeZigzagLevelOrderTraversal.cpp

Created December 8, 2018 15:27

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).

	/*
	Binary Tree Zigzag Level Order Traversal::

	https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/
	https://www.interviewbit.com/problems/zigzag-level-order-traversal-bt/

	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:

ms1797 / kSum_recursive.cpp

Last active November 24, 2018 15:38

given an array of integers in unsorted order , find all the unique set of k elements that sum to a given target. (k>=2)

	#include <bits/stdc++.h>
	using namespace std;

	void display_vector(vector<int> &arr )
	{
	for(int i = 0 ; i<arr.size() ; i++)
	{
	cout<<arr[i]<<" " ;
	}
	cout<<"\n" ;

ms1797 / 76-Minimum_Window_Substring.cpp

Created November 15, 2018 07:25 — forked from sourabh2k15/76-Minimum_Window_Substring.cpp

Leetcode 76. Minimum Window Substring

	class Solution {
	public:
	string minWindow(string s, string t) {
	unordered_map<char, int> table;

	// initialize frequency table for t
	for(char c : t){
	table[c]++;
	}

ms1797 / 4Sum_interviewBit.cpp

Created November 12, 2018 09:26

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.(https://www.interviewbit.com/problems/4-sum/)

	vector<vector<int> > Solution::fourSum(vector<int> &A, int B) {
	int N = A.size();
	//mapping sum value to a vector of pair indices
	unordered_map<int, vector<pair<int, int> > > Hash;
	vector<vector<int> >Ans;

	for(int i = 0; i < N; ++i) {
	for(int j = i + 1; j < N; ++j) {
	//calculate sum with i and j indices
	int Sum = A[i] + A[j];

ms1797 / largestContiguousSequenceZeroSum_intervieBit.cpp

Created November 11, 2018 09:29

Find the largest continuous sequence in a array which sums to zero.(https://www.interviewbit.com/problems/largest-continuous-sequence-zero-sum/)

	/*
	Largest Continuous Sequence Zero Sum :
	(https://www.interviewbit.com/problems/largest-continuous-sequence-zero-sum/)
	Find the largest continuous sequence in a array which sums to zero.

	Example:
	Input: {1 ,2 ,-2 ,4 ,-4}
	Output: {2 ,-2 ,4 ,-4}

	Input: arr[] = {15, -2, 2, -8, 1, 7, 10, 23};

ms1797 / grayCode_leetcode_interviewBit.cpp

Created November 3, 2018 18:41

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. (https://leetcode.com/problems/gray-code/)(https://www.interviewbit.com/problems/gray-code/)

	/*
	The gray code is a binary numeral system where two successive values differ in only one bit.

	Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code.
	A gray code sequence must begin with 0.

	Example 1:

	Input: 2
	Output: [0,1,3,2]

ms1797 / permutationII_leetcode.cpp

Last active November 3, 2018 14:06

Given a collection of numbers that might contain duplicates, return all possible unique permutations.(https://leetcode.com/problems/permutations-ii/)

	/*
	Permutation II ::

	Problem Statement::
	Given a collection of numbers that might contain duplicates, return all possible unique permutations.
	(https://leetcode.com/problems/permutations-ii/)

	Example:

	Input: [1,1,2]

ms1797 / permutations_interviewBit.cpp

Created November 2, 2018 08:31

Given a collection of numbers(unique elements), return all possible permutations. (https://www.interviewbit.com/problems/permutations/)

	/*
	Given a collection of numbers, return all possible permutations.

	Example:

	[1,2,3] will have the following permutations:

	[1,2,3]
	[1,3,2]
	[2,1,3]