2. Implement a thread-safe blocking queue.
3. 一个嵌套Map， 就是一个HashMap, 它的value可以是一个element也可以是另外一个
嵌套map或是空的map. 实现一个iterator来遍历这个map里面的所有element。 就是类
似树遍历一样的方法
10. Implement List Interface.
18. 两种方法写Singleton
19. 问了Mutex, Semaphore
21. 输入是个stream
class input_stream
{
// Character or -1
int read();
}
每次call read（），返回一个char，如果到头了就是返回-1
25. Celebrity Problem
Given a string of lowercase characters, reorder them such that the same characters are at least distance d from each other.A:
Input: { a, b, b }, distance = 2
Output: { b, a, b }
Input:[1,2,3,4,5,6,7]and k = 3 Output:[5,6,7,1,2,3,4]Explanation: rotate 1 steps to the right:[7,1,2,3,4,5,6]rotate 2 steps to the right:[6,7,1,2,3,4,5]rotate 3 steps to the right:[5,6,7,1,2,3,4]
Input: [-1,-100,3,99] and k = 2
Output: [3,99,-1,-100]
Explanation:
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]
class Solution { public: void rotate(vector<int>& nums, int k) { k = k % nums.size(); reverse(nums.begin(), nums.end()); reverse(nums.begin(), nums.begin()+k); reverse(nums.begin()+k, nums.end()); }};
There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. Solve it without division operator and in O(n).
For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1].
Example:
A: {4, 3, 2, 1, 2}
OUTPUT: {12, 16, 24, 48, 24}
,
private static int[] multi(int[] A) {
// use another matrix to help record its left multiplication result, and right
int n = A.length;
if(n==0){
System.err.print("array should have at least 1");
System.exit(0);
}
int[] left = new int[n];
int[] right = new int[n];
left[0] =1;
for(int i =1;i<n;i++) // calculate the left part
left[i]=left[i-1] * A[i-1];
right[n-1] = 1;
for(int i = n-2;i>=0;i--)
right[i] = right[i+1] * A[i+1];
int[] output = new int[n];
for(int i =0;i<n;i++)
output[i] = left[i] * right[i];
return output;
}
private static int[] multi(int[] A) {
// use another matrix to help record its left multiplication result, and right
int n = A.length;
if(n==0){
System.err.print("array should have at least 1");
System.exit(0);
}
int[] left = new int[n];
int[] right = new int[n];
left[0] =1;
for(int i =1;i<n;i++) // calculate the left part
left[i]=left[i-1] * A[i-1];
right[n-1] = 1;
for(int i = n-2;i>=0;i--)
right[i] = right[i+1] * A[i+1];
for(int i =0;i<n;i++)
right[i] = left[i] * right[i];
return right;
}
private static int[] multi(int[] A) {
// use another matrix to help record its left multiplication result, and right
int n = A.length;
if(n==0){
System.err.print("array should have at least 1");
System.exit(0);
}
int leftTillNow = 1;
// record the multiplication result of its right sided, from i+1 to n-1
int [] output = new int[n];
output[n-1] = 1;
for(int i = n-2;i>=0;i--)
output[i] = output[i+1] * A[i+1];
for(int i =1;i<n;i++){
output[i] = leftTillNow * output[i];
leftTillNow *= A[i-1];
}
return output;
}
static void printLong(long a) {
if (a < 0) {
return;
}
if (a == 0) {
printChar('0');
} else {
int tens = 1;
while (a / tens >= 10) {
tens *= 10;
}
while (tens > 0) {
int b = (int) (a / tens);
printChar((char) (b + '0'));
a = a % tens;
tens /= 10;
}
}
}
static void printChar(char ch) {
System.out.print(ch);
}
static void printLong(long a) {
// assume that input is unsigned integer
if (a < 10) {
printChar((char) (a + '0'));
} else {
printLong(a / 10);
printChar((char) (a % 10 + '0'));// print the last char
}
}
static void printChar(char ch) {
System.out.print(ch);
}
void printReverse(const char *str) {
if (!*str)
return;
printReverse(str + 1);
putchar(*str);
}
Window position Max --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7
Input: A long array A[], and a window width w Output: An array B[], B[i] is the maximum value of from A[i] to A[i+w-1] Requirement: Find a good optimal way to get B[i]
原始链接：
A natural way most people would think is to try to maintain the queue size the same as the window’s size. Try to break away from this thought and try to think outside of the box. Removing redundant elements and storing only elements that need to be considered in the queue is the key to achieve the efficient O(n) solution below.
void maxSlidingWindow(int A[], int n, int w, int B[]) {
deque<int> Q;
for (int i = 0; i < w; i++) {
while (!Q.empty() && A[i] >= A[Q.back()])
Q.pop_back();
Q.push_back(i);
}
for (int i = w; i < n; i++) {
B[i-w] = A[Q.front()];
while (!Q.empty() && A[i] >= A[Q.back()])
Q.pop_back();
while (!Q.empty() && Q.front() <= i-w)
Q.pop_front();
Q.push_back(i);
}
B[n-w] = A[Q.front()];
}
1
/ \
2 3
/ \
4 5
as "[1,2,3,null,null,4,5]", just the same as how LeetCode OJ serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself./**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
String res = "";
if(root == null){
return "#,";
}else{
res += "" + root.val + "," ;
res += serialize(root.left);
res += serialize(root.right);
}
return res;
}
// Decodes your encoded data to tree.
String str = "";
public TreeNode deserialize(String data) {
str = data;
return helper();
}
private TreeNode helper(){
if(str.length()==0)
return null;
if(str.charAt(0)=='#'){
str= str.substring(2);
return null;
}
int iComma = str.indexOf(",");
int rootVal = Integer.parseInt(str.substring(0,iComma));
TreeNode root = new TreeNode(rootVal);
str = str.substring(iComma+1);
root.left = helper();
root.right = helper();
return root;
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));
// Function to return the only odd occurring element
int findOdd(int arr[], int n) {
int res = 0, i;
for (i = 0; i < n; i++)
res ^= arr[i];
return res;
}
int main(void) {
int arr[] = {12, 12, 14, 90, 14, 14, 14};
int n = sizeof(arr)/sizeof(arr[0]);
printf ("The odd occurring element is %d ", findOdd(arr, n));
return 0;
}
// Output: The odd occurring element is 90
int main()
{
int x = 2, y = 5;
(x & y)? printf("True ") : printf("False ");
(x && y)? printf("True ") : printf("False ");
return 0;
}
// Output: False True
int main()
{
int x = 19;
printf ("x << 1 = %d\n", x << 1);
printf ("x >> 1 = %d\n", x >> 1);
return 0;
}
// Output: 38 9
int main()
{
int x = 19;
(x & 1)? printf("Odd"): printf("Even");
return 0;
}
// Output: Odd
// Note that the output of following program is compiler dependent
int main()
{
unsigned int x = 1;
printf("Signed Result %d \n", ~x);
printf("Unsigned Result %ud \n", ~x);
return 0;
}
/* Output:
Signed Result -2
Unsigned Result 4294967294d */
/* C program to print a long int number using putchar() only*/
#include <stdio.h>
void print(long n)
{
// If number is smaller than 0, put a - sign and
// change number to positive
if (n < 0) {
putchar('-');
n = -n;
}
// If number is 0
if (n == 0)
putchar('0');
// Remove the last digit and recur
if (n/10)
print(n/10);
// Print the last digit
putchar(n%10 + '0');
}
Given an input string, reverse the string word by word.
Example 1:
Input: "the sky is blue" Output: "blue is sky the"
Example 2:
Input: " hello world! " Output: "world! hello" Explanation: Your reversed string should not contain leading or trailing spaces.
Example 3:
Input: "a good example" Output: "example good a" Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.
Note:
Follow up:
For C programmers, try to solve it in-place in O(1) extra space.
A:class Solution { public: string reverseWords(string s) { istringstream iss(s); vector<string> res( ( istream_iterator<string>(iss)), istream_iterator<string>() ); string sRes=""; for(int i = res.size()-1; i>=0;i--) sRes += " "+res[i]; if(sRes.length() >0) sRes = sRes.substr(1); return sRes; } };
Threads differ from traditional multitasking operating system processes in that:------------------------------------------------------------------------------------------------------------
- processes are typically independent, while threads exist as subsets of a process
- processes carry considerable state information, whereas multiple threads within a process share state as well as memory and other resources
- processes have separate address spaces, whereas threads share their address space
- processes interact only through system-provided inter-process communication mechanisms.
- Context switching between threads in the same process is typically faster than context switching between processes.
Q. So tell me which segment thread share?The segments are irrelevant to the question, at least on Windows. Threads share the whole address space. There is only 1 stack segment, SS, and it points to the exact same stuff that DS, ES, and CS do [2]. I.e. the whole bloody user space. 0-2GB. Of course, that doesn't mean threads only have 1 stack. Naturally each has its own stack, but x86 segments are not used for this purpose.
ntsd notepad: cs=001b ss=0023 ds=0023 es=0023