Skip to content

Instantly share code, notes, and snippets.

View kartikkukreja's full-sized avatar

Kartik Kukreja kartikkukreja

65 followers · 1 following
View GitHub Profile
@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
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
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
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
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
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
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
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
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
kartikkukreja / matrix-median example
Last active October 11, 2016 05:40
matrix-median example
Given matrix =
[1, 5, 7]
[4, 10, 11]
[8, 11, 12]
The sorted array is [1, 4, 5, 7, 8, 10, 11, 11, 12]
and the median is 8.