cruxrebels’s gists

cruxrebels / PrimeNumbers.cpp

Created April 24, 2016 18:49

Given a number N, find all prime numbers upto N ( N included ). Example: if N = 7, all primes till 7 = {2, 3, 5, 7} Make sure the returned array is sorted. Tags: InterviewBit Math Problem https://www.interviewbit.com/problems/prime-numbers/

	vector<int> Solution::sieve(int A) {
	vector<int> result;

	//First approach
	/*for(auto i = 0; i<=A; ++i)
	result.emplace_back(i);
	result[0] = 0;
	result[1] = 0;
	for(auto j = 2; j*j<=A; ++j) //same as condition j<=sqrt(A)
	{

cruxrebels / AntiDiagonals.cpp

Created April 21, 2016 19:04

Give a N*N square matrix, return an array of its anti-diagonals. Look at the example for more details. Example: Input: 1 2 3 4 5 6 7 8 9 Return the following : [ [1], [2, 4], [3, 5, 7], [6, 8], [9] ] Input : 1 2 3 4 Return the following : [ [1], [2, 3], [4] ] Tags: InterviewBit Arrays Problem. https://www.interviewbit.com/problems/anti-diagonals/

	vector<vector<int> > Solution::diagonal(vector<vector<int> > &A) {
	int n = A.size();
	vector<vector<int> > result;
	int l = -1;
	int i = 0;
	int c = 0;

	int r = 0;
	int col = 0;
	for (auto j = 0; j<n; ++j)

cruxrebels / FindMissingInteger.cpp

Created April 20, 2016 16:04

Given an unsorted integer array, find the first missing positive integer. Example: Given [1,2,0] return 3, [3,4,-1,1] return 2, [-8, -7, -6] returns 1 Your algorithm should run in O(n) time and use constant space. Tags: InterviewBit Array Problem https://www.interviewbit.com/problems/first-missing-integer/

	int Solution::firstMissingPositive(vector<int> &A) {
	sort(A.begin(), A.end());
	int c = 1;
	for (auto const& a : A)
	{
	if (a<1)
	continue;
	else if (a==c)
	{
	++c;

cruxrebels / LargestNumber.cpp

Last active July 12, 2021 08:16

Given a list of non negative integers, arrange them such that they form the largest number. For example: Given [3, 30, 34, 5, 9], the largest formed number is 9534330. Note: The result may be very large, so you need to return a string instead of an integer. Tags: InterviewBit Arrays Problem https://www.interviewbit.com/problems/largest-number/


	bool myCompare(const int x, const int y)
	{
	auto tempx = x;
	auto tempy = y;
	auto cx = 0;
	auto cy = 0;
	while(tempx!=0 \|\| tempy!=0)
	{
	if(tempx!=0)

cruxrebels / SetMatrixZeroes.cpp

Created April 18, 2016 17:25

Given an m x n matrix of 0s and 1s, if an element is 0, set its entire row and column to 0. Do it in place. Example Given array A as 1 0 1 1 1 1 1 1 1 On returning, the array A should be : 0 0 0 1 0 1 1 0 1 Note that this will be evaluated on the extra memory used. Try to minimize the space and time complexity. Tags: InterviewBit Arrays Problem h…

	void Solution::setZeroes(vector<vector<int> > &A) {
	int nR = A.size();
	int nC = A[0].size();
	vector<int> r;
	vector<int> c;

	for(int i=0; i<nR; ++i)
	{
	for (int j=0; j<nC; ++j)
	{

cruxrebels / MinStepsInInfiniteGrid.cpp

Last active September 20, 2021 05:20

You are in an infinite 2D grid where you can move in any of the 8 directions : (x,y) to (x+1, y), (x - 1, y), (x, y+1), (x, y-1), (x-1, y-1), (x+1,y+1), (x-1,y+1), (x+1,y-1) You are given a sequence of points and the order in which you need to cover the points. Give the minimum number of steps in which you can achieve it. You start from the firs…

	/*
	You are in an infinite 2D grid where you can move in any of the 8 directions :
	(x,y) to (x+1, y), (x - 1, y), (x, y+1), (x, y-1), (x-1, y-1), (x+1,y+1), (x-1,y+1), (x+1,y-1)
	You are given a sequence of points and the order in which you need to cover the points.
	Give the minimum number of steps in which you can achieve it. You start from the first point.
	Example : Input : [(0, 0), (1, 1), (1, 2)] Output : 2 It takes 1 step to move from (0, 0) to (1, 1).
	It takes one more step to move from (1, 1) to (1, 2).

	This question is intentionally left slightly vague.
	Clarify the question by trying out a few cases in the “See Expected Output” section.

cruxrebels / MergeOverlappingIntervals.cpp

Created April 16, 2016 15:41

Given a collection of intervals, merge all overlapping intervals. For example: Given [1,3],[2,6],[8,10],[15,18], return [1,6],[8,10],[15,18]. Make sure the returned intervals are sorted. Tags: InterviewBit Arrays problem https://www.interviewbit.com/problems/merge-overlapping-intervals/

	/**
	* Definition for an interval.
	* struct Interval {
	* int start;
	* int end;
	* Interval() : start(0), end(0) {}
	* Interval(int s, int e) : start(s), end(e) {}
	* };
	*/

cruxrebels / MergeIntervals.cpp

Created April 14, 2016 19:41

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary). You may assume that the intervals were initially sorted according to their start times. Example 1: Given intervals [1,3],[6,9] insert and merge [2,5] would result in [1,5],[6,9]. Example 2: Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and m…

	/**
	* Definition for an interval.
	* struct Interval {
	* int start;
	* int end;
	* Interval() : start(0), end(0) {}
	* Interval(int s, int e) : start(s), end(e) {}
	* };
	*/
	vector<Interval> Solution::insert(vector<Interval> &intervals, Interval newInterval) {

cruxrebels / WaveArray.cpp

Last active April 14, 2016 16:01

Given an array of integers, sort the array into a wave like array and return it, In other words, arrange the elements into a sequence such that a1 >= a2 <= a3 >= a4 <= a5..... Example Given [1, 2, 3, 4] One possible answer : [2, 1, 4, 3] Another possible answer : [4, 1, 3, 2]. In case of multiple possible answers return the one thats lexicograph…

	vector<int> Solution::wave(vector<int> &A) {
	sort(A.begin(), A.end());
	int s = A.size();
	int i = 0;
	while (i<=s-2)
	{
	swap(A[i], A[i+1]);
	i += 2;
	}
	return A;

cruxrebels / SpiralOrderMatrixI.cpp

Last active July 20, 2021 08:35

Given a matrix of m * n elements (m rows, n columns), return all elements of the matrix in spiral order. Example: Given the following matrix: [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ] You should return [1, 2, 3, 6, 9, 8, 7, 4, 5]. Tags: InterviewBit - Arrays topic (https://www.interviewbit.com/problems/spiral-order-matrix-i/).

	vector<int> Solution::spiralOrder(const vector<vector<int> > &A) {
	vector<int> result;
	// DO STUFF HERE AND POPULATE result
	auto rows = A.size
	if (rows == 0)
	return vector<int> ();
	auto columns = A[0].size();
	int T, B, L, R;
	T = 0, B = rows - 1, L = 0, R = columns - 1;
	int dir = 0;

Abhi cruxrebels