Skip to content

Instantly share code, notes, and snippets.

View mogutou1214's full-sized avatar

mogutou1214

View GitHub Profile
@mogutou1214
mogutou1214 / CC2.4
Created May 30, 2015 22:42
CC2.4 - Write code to partition a linked list around a value x, such that all nodes less than x come before all nodes greater than or equal to x.
public class partitionLinkedList {
public static LinkedListNode Solution(LinkedListNode head, int x) {
if (head == null) return null;
LinkedListNode smaller = new LinkedListNode(0); //dummyhead for list called smaller
LinkedListNode smallerPtr = smaller;
LinkedListNode larger = new LinkedListNode(0); //dummyhead for list called larger
LinkedListNode largerPtr = larger;
LinkedListNode result;
while (head != null) {
if (head.val < x) {
@mogutou1214
mogutou1214 / CC2.2
Created May 30, 2015 18:24
CC2.2 - Implement an algorithm to find the kth to last element of a singly linked list.
public class findKth {
public static LinkedListNode solution(LinkedListNode head, int Kth) {
if (Kth < 0) return null;
if (head == null) return null;
LinkedListNode walker = head;
LinkedListNode runner = head;
for (int i = 0; i < Kth-1; i++) {
if (runner == null) return null;
runner = runner.next;
}
@mogutou1214
mogutou1214 / CC2.1
Last active August 29, 2015 14:22
CC2.1 - Write code to remove duplicates from an unsorted linked list. FOLLOW UP How would you solve this problem if a temporary buffer is not allowed?
import java.util.Hashtable;
public class removeDuplicates {
public static void Solution(LinkedListNode head) {
if (head == null) return;
Hashtable<Integer, Boolean> table = new Hashtable<Integer, Boolean>();
LinkedListNode dummyHead = new LinkedListNode(0);
dummyHead.next = head;
LinkedListNode ptr = dummyHead;
while(ptr.next != null) {
@mogutou1214
mogutou1214 / career2.6.cpp
Created September 19, 2013 23:00
Career 2.6 - Given a circular linked list, implement an algorithm which returns the node at the beginning of the loop. DEFINITION Circular linked list: A (corrupt) linked list in which a node's next pointer points to an earlier node, so as to make a loop in the linked list. EXAMPLE Input: A -> B -> C -> D -> E -> C [the same C as earlier] Output: C
#include "stdafx.h"
#include <iostream>
#include <map>
using namespace std;
template <class T>
struct node{
T data;
node *next;
};
@mogutou1214
mogutou1214 / linkedlistnew.cpp
Created September 19, 2013 21:36
C++ Linked list-generic
// Linkedlist.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
using namespace std;
template <class T>
struct node{
T data;
@mogutou1214
mogutou1214 / linkedlist.cpp
Last active December 23, 2015 11:38
C++ Linked list
// Linkedlist.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
using namespace std;
struct node{
int data;
@mogutou1214
mogutou1214 / careercup3.2
Created September 9, 2013 00:15
Careercup 3.2 - How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push, pop and min should all operate in O(1) time. 1. how to use stack in STL; 2. how to throw an exception;
#include <iostream>
#include <stack>
using namespace std;
class MyException{
public:
MyException(){cout << "the stack is empty" << endl;}
};
@mogutou1214
mogutou1214 / gist:6418613
Created September 3, 2013 01:03
Careercup 2.7 - Implement a function to check if a linked list is a palindrome. use a stack.
bool isPalindrome(node *head){
if(head==NULL) return false;
node *curr = head;
stack<int> s;
while(curr!=NULL){
s.push(curr->data);
curr = curr->next;
}
/*while(!s.empty()){
@mogutou1214
mogutou1214 / gist:6415251
Created September 2, 2013 17:25
Careercup 2.3 - Implement an algorithm to delete a node in the middle of a single linked list, given only access to that node EXAMPLE Input: the node ‘c’ from the linked list a->b->c->d->e Result: nothing is returned, but the new linked list looks like a->b->d->e
void delGivenNode(node *entry){
entry->data = (entry->next)->data;
entry->next = (entry->next)->next;
delete entry->next;
}
@mogutou1214
mogutou1214 / gist:6408080
Last active November 7, 2016 20:09
Careercup 2.1 - Write code to remove duplicates from an unsorted linked list. FOLLOW UP How would you solve this problem if a temporary buffer is not allowed? Note: 1. pay special attention to deleting a node 2. learn to use "map" in C++ STL as a hash table
/*Remove duplicates from an unsorted linked list - cc2.1*/
void removeDuplicate1(node *head){
map<int,bool> table;
node *curr = head;
node *pre = NULL;
while(curr!=NULL){
/*delete the node if it already exists in the map*/
if(table[curr->data]){
pre->next = curr->next;
delete curr;