Kartik Kukreja kartikkukreja

kartikkukreja / cycle-in-linked-list-floyd_alt.cpp

Created October 17, 2016 02:09

Detecting cycle in a linked list

	ListNode* detectCycle(ListNode* A) {
	if (A == NULL \|\| A->next == NULL \|\| A->next->next == NULL) return NULL;
	ListNode slow = A, fast = A;
	while (fast->next && fast->next->next) {
	slow = slow->next;
	fast = fast->next->next;
	if (slow == fast)
	break;
	}
	if (slow != fast) return NULL;

kartikkukreja / cycle-in-linked-list-hashset.cpp

Last active October 17, 2016 02:11

Detecting a cycle in a linked list with a hashset

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	ListNode* detectCycle(ListNode* A) {
	unordered_set<ListNode*> seen;

kartikkukreja / cycle-in-linked-list-floyd.cpp

Created October 17, 2016 01:01

Detecting a cycle in a linked list with Floyd's cycle-finding algorithm

	ListNode* detectCycle(ListNode* A) {
	if (A == NULL \|\| A->next == NULL \|\| A->next->next == NULL) return NULL;
	ListNode slow = A, fast = A;
	while (fast->next && fast->next->next) {
	slow = slow->next;
	fast = fast->next->next;
	if (slow == fast)
	break;
	}
	if (slow != fast) return NULL;

kartikkukreja / longest-palindromic-substring-dp.cpp

Created October 15, 2016 20:13

Longest palindromic substring DP solution

	string longestPalindrome(string A) {
	int N = A.size();
	vector<vector<bool> > P(N+1, vector<bool>(N+1, true));
	int start = 0, len = 1;

	for (int k = 1; k < N; ++k) {
	for (int i = 1; i <= N-k; ++i) {
	P[i][i+k] = P[i+1][i+k-1] && (A[i-1] == A[i+k-1]);
	if (P[i][i+k] && k+1 > len)
	start = i-1, len = k+1;

kartikkukreja / longest-palindromic-substring.cpp

Last active October 15, 2016 22:38

longest palindromic substring solution

	int palindromeLengthFromCenter(string& A, int left, int right) {
	int originalLeft = left;
	while (left >= 0 && right < A.size() && A[left] == A[right]) {
	left--;
	right++;
	}
	return originalLeft - left;
	}

	string longestPalindrome(string A) {

kartikkukreja / median-two-sorted-arrays.cpp

Created October 13, 2016 04:59

median of two sorted arrays example

	int getOrderStatistic(const vector<int>& A, int as, int ae, const vector<int>& B, int bs, int be, int k) {
	int n = ae - as + 1, m = be - bs + 1;
	if (n > m)
	return getOrderStatistic(B, bs, be, A, as, ae, k);
	if (n <= 0)
	return B[bs + k - 1];
	if (k == 1)
	return min(A[as], B[bs]);
	int pa = min(k/2, n), pb = k - pa;
	return A[as+pa-1] <= B[bs+pb-1]

kartikkukreja / median-two-sorted-arrays-eg-sol

Last active October 13, 2016 04:58

	Input:
	A = [1,3,5]
	B = [4,7]

	Assume 1-based indexing for simplification.

	Step 1:
	N = 3, M = 2, k = (3+2)/2 + 1 = 3
	pa = 3/2 = 1, pb = 3-1 = 2
	A[1] = 1 <= B[2] = 7

kartikkukreja / median-two-sorted-arrays-eg

Last active October 13, 2016 05:01

median of two sorted arrays example

	Input:
	A = [1,3,5]
	B = [4,7]

	Output:
	4

	Explanation:
	The combined array is [1,3,4,5,7] and the middle element is 4.

kartikkukreja / matrix-median.cpp

Last active October 10, 2017 17:12

matrix-median

	int findMedian(vector<vector<int> > &A) {
	int mn = A[0][0], mx = A[0][0], n = A.size(), m = A[0].size();
	for (int i = 0; i < n; ++i) {
	if (A[i][0] < mn) mn = A[i][j];
	if (A[i][m-1] > mx) mx = A[i][j];
	}

	int desired = (n * m + 1) / 2;
	while (mn < mx) {
	int mid = mn + (mx - mn) / 2;

kartikkukreja / matrix-median example

Last active October 11, 2016 05:40

matrix-median example