frank4565’s gists

frank4565 / 2.1.cpp

Last active August 29, 2015 13:56

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?

	#include<iostream>
	#include<unordered_set>

	using namespace std;

	struct Node
	{
	int data;
	Node *next;

frank4565 / 1.8.cpp

Created February 13, 2014 05:33

1.8 Assume you have a method isSubstring which checks if one word is a substring of another. Given two strings, s1 and s2, write code to check if s2 is a rotation of si using only one call to isSubstring (e.g.,"waterbottle"is a rota- tion of"erbottlewat").

	#include<iostream>

	using namespace std;

	bool isSubstring(const string &s1, const string &s2)
	{
	return s1.find(s2) != string::npos;
	}

	bool isRotation(const string &s1, const string &s2)

frank4565 / 1.7.cpp

Created February 13, 2014 04:48

1.7 Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column are set to 0.

	#include<iostream>

	using namespace std;

	const int M = 3;
	const int N = 4;

	void setZeros(int matrix[][N])
	{
	int row[M/sizeof(int)+1]{};

frank4565 / 1.6.cpp

Last active August 29, 2015 13:56

1.6 Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place?

	#include<iostream>

	using namespace std;

	const int N = 4;

	void rotate(int matrix[][N])
	{
	for (int i = 0; i < N/2; i++) {
	for (int j = i; j < N-1-i; j++) {

frank4565 / 1.5.cpp

Last active August 29, 2015 13:56

1.5 Implement a method to perform basic string compression using the counts of repeated characters. For example, the string aabcccccaaa would become a2blc5a3. If the "compressed" string would not become smaller than the original string, your method should return the original string.

	#include <iostream>

	string compress(const string &s)
	{
	string ns{};
	char last = s[0];
	unsigned count = 1;
	for (int i = 1; i <= s.size(); i++) {
	if (i != s.size() && s[i] == last)
	count++;

frank4565 / 1.4.cpp

Created February 12, 2014 04:15

1.4 Write a method to replace all spaces in a string with '%20'. Youmay assume that the string has sufficient space at the end of the string to hold the additional characters, and that you are given the "true" length of the string. (Note: if implementing in Java, please usea character array so that you can perform this operation inplace.)

	#include<iostream>

	using namespace std;

	void replace(char *s, unsigned l)
	{
	if (s == nullptr) return;
	unsigned sp = 0;
	for (int i = 0; i < l; i++)
	if (s[i] == ' ')

frank4565 / 1.3.cpp

Last active August 29, 2015 13:56

1.3 Given two strings, write a method to decide if one is a permutation of the other.

	#include<iostream>

	using namespace std;

	unsigned const NUM_CHAR = 256;

	bool isPermutation1(string str1, string str2)
	{
	sort(str1.begin(), str1.end());
	sort(str2.begin(), str2.end());

frank4565 / 1.2.cpp

Last active August 29, 2015 13:56

1.2 Implement a function void reverse(char* str) in C or C++ which reverses a null- terminated string.

	#include<iostream>

	void reverse(char *str) {
	if (str == nullptr) return;

	// find the end of the string
	char *end = str;
	char temp;
	while (*end != '\0') ++end;
	--end;

frank4565 / 1.1.cpp

Last active August 29, 2015 13:56

1.1 Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures?

	#include<iostream>

	const unsigned NUM_CHAR = 256;

	bool hasAllUniqueChar (std::string s)
	{
	if (s.size() > NUM_CHAR) return false;

	// init array
	unsigned array[NUM_CHAR/sizeof(int)+1] = {};

frank4565 / readnumbers.c

Last active December 30, 2015 03:19

Read a file line by line and put all numbers in one line to an array.

	#include "stdio.h"
	#include "stdlib.h"
	#include "string.h"

	/* Sample Input *** input_vectors.txt
	0 1
	1 1
	0 1
	1 1
	0 1

Junlu Cheng frank4565