Rohith Uppala rohith2506

Hakuna Matata

rohith2506 / majority_number_in_an_array.cpp

Created December 31, 2014 05:46

	class Solution {
	public:
	int majorityElement(vector<int> &num) {
	int cnt = 0;
	for(int i=0; i<num.size(); i++){
	if(cnt == 0){
	maj = num[i];
	cnt++;
	}
	else if(maj == num[i])

rohith2506 / 647_div2_500.cpp

Last active August 29, 2015 14:14

	#include <iostream>
	#include <cstring>
	#include <string>
	#include <vector>

	using namespace std;

	class Fragile2{
	public:
	int isSafe(vector<vector<int> > &M, int row, int col, vector<vector<bool> > &visited){

rohith2506 / 648_DIV_2_1000.cpp

Created February 4, 2015 09:44

rohith2506 / llap.cpp

Created February 20, 2015 09:59

Longest Arithmetic progression in an array [UNSOLVED]

	/*
	* Find the longest arithematic progression in an array using DP Method
	* Reference:- geeksforgeeks
	* Author: Rohith
	*/

	#include <iostream>
	#include <vector>
	#include <algorithm>

rohith2506 / 1.cpp

Created February 26, 2015 10:25

Connect Nodes at same level -- (Amazon)

	// http://www.geeksforgeeks.org/connect-nodes-at-same-level/

	void foo(t){
	if(!t) return;
	it(t -> left != NULL){
	if(t->right != NULL){
	t -> left -> next = t -> right;
	}
	else {
	if(t->next->left != NULL){

rohith2506 / 2.cpp

Created February 26, 2015 11:29

Smallest substring with given string ( Optimized approach )

	// Very good problem. But difficult to understand.
	// http://leetcode.com/2010/11/finding-minimum-window-in-s-which.html

	int search(vector<string> txt, vector<string> pat, string s1, string s2){
	for(int i=0; i<s2.length(); i++) pat[(int)(s2[i])]++;
	txt[256] = {0};
	int begin = 0, end = 0;
	while(end < s1.length()){
	if(pat[s1[end]] == 0) continue;
	txt[s1[end]]++l;

rohith2506 / 3.cpp

Created February 26, 2015 12:05

Pancake sorting

	//http://www.geeksforgeeks.org/pancake-sorting/

	void flip(vector<int> v, int i){
	int temp, start = 0;
	while(start < i){
	int temp = v[start];
	v[start] = v[i];
	v[i] = temp;
	start++;
	i--;

rohith2506 / 3.cpp

Created February 26, 2015 12:29

Trie Implementation in c++

http://ideone.com/eF7Nih

rohith2506 / 4.cpp

Created March 2, 2015 08:25

Count the number of possible triangles

	// As though it looks like O(n^3) but it actally is O(n^2). because of k initialized outisde and does not depenv on j value.

	int possible_triangles(vector<int> a){
	int count = 0;
	for(int i=0; i<n-2; i++){
	int k = i+2;
	for(int j=i+1; j<n; j++){
	while(k < n && a[i] + a[j] > a[k]) ++k;
	count = count + (k-j-1);
	}

rohith2506 / 5.cpp

Created March 2, 2015 09:15

count number of inversions in an array (a variation of merge sort)

	/*
	It's a modification of merge sort
	see for explanation:- http://www.geeksforgeeks.org/counting-inversions/
	*/
	int merge_sort(int a[], int low, int high){
	if(high > low){
	int mid = (low + high)/2;
	inv_count = merge_sort(a, low, mid);
	inv_count += merge_sort(a, mid+1, high);
	return merge(a, temp, low, mid, high);