Skip to content

Instantly share code, notes, and snippets.

View ThunderXu's full-sized avatar

ThunderXu

5 followers · 2 following
View GitHub Profile
@ThunderXu
ThunderXu / CareerCup5.6.cpp
Created March 30, 2013 14:12
Write a program to swap odd and even bits in an integer with as few instructions as possible (e.g., bit 0 and bit 1 are swapped, bit 2 and bit 3 are swapped, and so on).
#include <iostream>
#include <bitset>
#include <string>
std::bitset<32> Swap(std::bitset<32>);
int main()
{
int num;
std::cin>>num;
@ThunderXu
ThunderXu / CareerCup5.5.cpp
Created March 30, 2013 13:32
Write a function to determine the number of bits required to convert integer A to integer B.
#include <iostream>
#include <bitset>
int GetNumber(int, int);
int main()
{
std::cout<<GetNumber(31,14)<<std::endl;
}
@ThunderXu
ThunderXu / CareerCup5.3.cpp
Last active December 15, 2015 14:39
Given a positive integer, print the next smallest and the next largest number that have the same number of 1 bits in their binary representation.
#include <iostream>
#include <bitset>
int GetNextLargest(int num);
int GetNextSmallest(int num);
int main()
{
int num;
@ThunderXu
ThunderXu / CareerCup5.2.cpp
Created March 24, 2013 07:40
Given a real number between 0 and 1 (e.g., 0.72) that is passed in as a double, print the binary representation. If the number cannot be represented accurately in binary with at most 32 characters, print "ERROR."
#include <iostream>
#include <string>
std::string PrintBinary(float);
int main()
{
std::cout<<PrintBinary(0.81256)<<std::endl;
}
std::string PrintBinary(float num)
@ThunderXu
ThunderXu / CareerCup4.9
Created March 23, 2013 12:26
You are given a binary tree in which each node contains a value. Design an algorithm to print all paths which sum to a given value. Note that a path can start or end anywhere in the tree.
#include <iostream>
#include <vector>
struct Node
{
int data;
Node* left;
Node* right;
Node(int var)
{
@ThunderXu
ThunderXu / CareerCup4.8.cpp
Created March 23, 2013 03:52
You have two very large binary trees: T1, with millions of nodes, and T2, with hundreds of nodes. Create an algorithm to decide if T2 is a subtree of T1. A tree T2 is a subtree of T1 if there exists a node n in T1 such that the subtree of n is identical to T2. That is, if you cut the tree at node n, the two trees would be identical.
#include <iostream>
struct Node
{
int data;
Node* left;
Node* right;
Node(int var)
{
data=var;
@ThunderXu
ThunderXu / careercup4.7.cpp
Created March 18, 2013 13:27
Design an algorithm and write code to find the first common ancestor of two nodes in a binary tree. Avoid storing additional nodes in a data structure. NOTE: This is not necessarily a binary search tree.
#include <iostream>
struct Node
{
int data;
Node* left;
Node* right;
Node()
{
left = NULL;
@ThunderXu
ThunderXu / CareerCup4.6.cpp
Created March 16, 2013 14:57
Write an algorithm to find the ‘next’ node (i.e., in-ordersuccessor) of a given node in a binary search tree. You may assume that eachnode has a link to its parent.
#include <iostream>
struct Node
{
int data;
Node* left;
Node* right;
Node* parent;
Node()
{
@ThunderXu
ThunderXu / CareerCup4.5.cpp
Created March 16, 2013 11:37
Implement a function to check if a binary tree is a binary searchtree.
#include <iostream>
struct Node
{
int data;
Node* leftchild;
Node* rightchild;
Node()
{
leftchild=NULL;
@ThunderXu
ThunderXu / CareerCup4.4.cpp
Created March 16, 2013 10:24
Given a binary tree, design an algorithm which creates alinked list of all the nodes at each depth (e.g., if you have a tree with depthD, you’ll have D linked lists).
#include <iostream>
#include <vector>
#include <list>
struct Node
{
int data;
Node* leftchild;
Node* rightchild;
Node()