Cracking the Code
You have been contracted by a terrorist group to crack encrypted transmissions. The only information that the terrorists could give you regarding the encrypted message is that a fixed keylength XORencryption algorithm was used to encode it. After a brief search on the 'Net, you find the following definition of XORencryption:
Assuming that we have a character u[i] from the unencrypted input stream, and a key k of length l with characters k[j], 0 <= j < l, then the encrypted value e[i] is obtained as follows:
e[i] = u[i] XOR k[i MOD l]
where MOD is the remainder after integer division (the % operator in C, C++ and Java), and XOR is the bitwise XOR operator applied to an 8bit character (the ^ operator in C, C++ and Java). XOR encryption is a symmetric encryption scheme, so that the message is decoded by encrypting the encrypted message (a second time) with the same key, so that
u[i] = e[i] XOR k[i MOD l]
You are given four encrypted input streams of 30 000 characters each (that is, a continuous input stream of 120 000 characters). Your program must output the four decrypted stream with no other characters embedded. The streams were encrypted using XOR encryption with fixed length keys of fewer than 30 characters. Each character in the key is unique (appears only once), and is selected from the set a..z merged with 0..9.
Your task is to determine the correct key length, and decrypt the encrypted input stream.
Your terrorist friends provided you with one last vital piece of information: ��The decrypted message will be in English.'��
It is recommended that you write an XOR encryption program first to aid you in testing your solution.
SAMPLE INPUT
The output of the XOR encryption algorithm is not normally printable, since it may contain ASCII codes greater than 127. Therefore, the sampleencrypted message below is shown in numerical ASCII values (in decimal) �C the actual input file contains the ASCII symbols.
If the message "the quick brown fox jumps over the lazy dog" is encrypted using the key "12" (the literal characters "1" and "2", concatenated), the following (binary) file results.
69 90 84 18 64 71 88 81 90 18 83 64 94 69 95 18
87 93 73 18 91 71 92 66 66 18 94 68 84 64 17 70
89 87 17 94 80 72 72 18 85 93 86
If these values are converted to ASCII symbols and stored in a file (the file length should be exactly 43 bytes), it can be used as input to your program. It is recommended that you first write the encryption algorithm.
SAMPLE OUTPUT
Your program should determine the key length to be 2 (you should not output this value), and decrypt the message to yield:
the quick brown fox jumps over the lazy dog
 点赞
 写回答
 关注问题
 收藏
 复制链接分享
 邀请回答
2条回答

采纳
点赞 1 评论 复制链接分享
 采纳
相关推荐
 回答 2 已采纳 You have been contracted by a terrorist group to crack encrypted transmissions. The only information that the terrorists could give you regarding the encrypted message is that a fixed keylength XORencryption algorithm was used to encode it. After a brief search on the 'Net, you find the following definition of XORencryption: Assuming that we have a character u[i] from the unencrypted input stream, and a key k of length l with characters k[j], 0 <= j < l, then the encrypted value e[i] is obtained as follows: e[i] = u[i] XOR k[i MOD l] where MOD is the remainder after integer division (the % operator in C, C++ and Java), and XOR is the bitwise XOR operator applied to an 8bit character (the ^ operator in C, C++ and Java). XOR encryption is a symmetric encryption scheme, so that the message is decoded by encrypting the encrypted message (a second time) with the same key, so that u[i] = e[i] XOR k[i MOD l] You are given four encrypted input streams of 30 000 characters each (that is, a continuous input stream of 120 000 characters). Your program must output the four decrypted stream with no other characters embedded. The streams were encrypted using XOR encryption with fixed length keys of fewer than 30 characters. Each character in the key is unique (appears only once), and is selected from the set a..z merged with 0..9. Your task is to determine the correct key length, and decrypt the encrypted input stream. Your terrorist friends provided you with one last vital piece of information: ��The decrypted message will be in English.'�� It is recommended that you write an XOR encryption program first to aid you in testing your solution. SAMPLE INPUT The output of the XOR encryption algorithm is not normally printable, since it may contain ASCII codes greater than 127. Therefore, the sampleencrypted message below is shown in numerical ASCII values (in decimal) �C the actual input file contains the ASCII symbols. If the message "the quick brown fox jumps over the lazy dog" is encrypted using the key "12" (the literal characters "1" and "2", concatenated), the following (binary) file results. 69 90 84 18 64 71 88 81 90 18 83 64 94 69 95 18 87 93 73 18 91 71 92 66 66 18 94 68 84 64 17 70 89 87 17 94 80 72 72 18 85 93 86 If these values are converted to ASCII symbols and stored in a file (the file length should be exactly 43 bytes), it can be used as input to your program. It is recommended that you first write the encryption algorithm. SAMPLE OUTPUT Your program should determine the key length to be 2 (you should not output this value), and decrypt the message to yield: the quick brown fox jumps over the lazy dog
 4年前回答 1 已采纳 The following problem is somehow related to the final stage of many famous integer factorization algorithms involved in some cryptoanalytical problems, for example cracking wellknown RSA public key system. The most powerful of such algorithms, so called quadratic sieve descendant algorithms utilize the fact that if n = pq where p and q are large unknown primes needed to be found out, then if v2 = w2 (mod n) and u != v (mod n) and u != v (mod n) then gcd(v + w, n) is a factor of n (either p or q). Not getting further in the details of these algorithms, let us consider our problem. Given m integer numbers b1, b2, ... , bm such that all their prime factors are from the set of first t primes, the task is to find such a set S that S is a subset of {1, 2, ... ,m} and b1*b2*...*bS(bi belongs to S, i=1,2..S) is a perfect square i.e. equal to u2 for some integer u. Given such S we get one pair for testing (product of S elements stands for v when w is known from other steps of algorithms which are of no interest to us, testing performed is checking whether pair is nontrivial, i.e. u != v (mod n) and u != v (mod n)). Since we want to factor n with maximum possible probability, we would like to get as many such sets as possible. So the interesting problem could be to calculate the number of all such sets. This is exactly your task. This problem contains multiple test cases! The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks. The output format consists of N output blocks. There is a blank line between output blocks. Input The first line of the input file contains two integers t and m (1 <= t <= 100, 1 <= m <= 100). The second line of the input file contains m integer numbers bi such that all their prime factors are from t first primes (for example, if t = 3 all their prime factors are from the set {2, 3, 5}). 1 <= bi <= 109 for all i. Output Output the number of nonempty subsets of the given set bi, the product of numbers from which is a perfect square. Sample Input 1 3 4 9 20 500 3 Sample Output 3
 回答 2 已采纳 Problem Description Somewhere near the south pole, a number of penguins are standing on a number of ice floes. Being social animals, the penguins would like to get together, all on the same floe. The penguins do not want to get wet, so they have use their limited jump distance to get together by jumping from piece to piece. However, temperatures have been high lately, and the floes are showing cracks, and they get damaged further by the force needed to jump to another floe. Fortunately the penguins are real experts on cracking ice floes, and know exactly how many times a penguin can jump off each floe before it disintegrates and disappears. Landing on an ice floe does not damage it. You have to help the penguins find all floes where they can meet. A sample layout of ice floes with 3 penguins on them. Input On the first line one positive number: the number of testcases, at most 100. After that per testcase: One line with the integer N (1 ≤ N ≤ 100) and a floatingpoint number D (0 ≤ D ≤ 100 000), denoting the number of ice pieces and the maximum distance a penguin can jump. N lines, each line containing xi, yi, ni and mi, denoting for each ice piece its X and Y coordinate, the number of penguins on it and the maximum number of times a penguin can jump off this piece before it disappears (−10 000 ≤ xi, yi ≤ 10 000, 0 ≤ ni ≤ 10, 1 ≤ mi ≤ 200). Output Per testcase: One line containing a spaceseparated list of 0based indices of the pieces on which all penguins can meet. If no such piece exists, output a line with the single number −1. Sample Input 2 5 3.5 1 1 1 1 2 3 0 1 3 5 1 1 5 1 1 1 5 4 0 1 3 1.1 1 0 5 10 0 0 3 9 2 0 1 1 Sample Output 1 2 4 1
 回答 1 已采纳 I have a problem which is really braincracking. I would like to use the $this variable inside a function. As long as it is the function parameter variable, there is no problem. But when I change the code to assign it inside, it is no longer working (blank page when direct opened, AJAX responds with Internal Server Error). The rest of the code inside the function uses the variable $this, and perfectly works in the second way. The full script is an AJAX email sender for a WordPress site, using global $wpdb. Am i missing something or is it too late night to see the mistake? :) NOT WORKING function lookup_product($in){ $this = $in; echo $this; } WORKING function lookup_product($this){ echo $this; }
 4年前回答 1 已采纳 Problem Description The soil is cracking up because of the drought and the rabbit kingdom is facing a serious famine. The RRC(Rabbit Red Cross) organizes the distribution of relief grain in the disaster area. We can regard the kingdom as a tree with n nodes and each node stands for a village. The distribution of the relief grain is divided into m phases. For each phases, the RRC will choose a path of the tree and distribute some relief grain of a certain type for every village located in the path. There are many types of grains. The RRC wants to figure out which type of grain is distributed the most times in every village. Input The input consists of at most 25 test cases. For each test case, the first line contains two integer n and m indicating the number of villages and the number of phases. The following n1 lines describe the tree. Each of the lines contains two integer x and y indicating that there is an edge between the xth village and the yth village. The following m lines describe the phases. Each line contains three integer x, y and z indicating that there is a distribution in the path from xth village to yth village with grain of type z. (1 <= n <= 100000, 0 <= m <= 100000, 1 <= x <= n, 1 <= y <= n, 1 <= z <= 100000) The input ends by n = 0 and m = 0. Output For each test case, output n integers. The ith integer denotes the type that is distributed the most times in the ith village. If there are multiple types which have the same times of distribution, output the minimal one. If there is no relief grain in a village, just output 0. Sample Input 2 4 1 2 1 1 1 1 2 2 2 2 2 2 2 1 5 3 1 2 3 1 3 4 5 3 2 3 3 1 5 2 3 3 3 0 0 Sample Output 1 2 2 3 3 0 2
 7年前回答 3 已采纳 The problem I am given is A child is running up a staircase with n steps, and can hop either 1 step, 2 steps, or 3 steps at a time. Implement a method to count how many possible ways the child can run up the stairs. http://play.golang.org/p/bpjIkMm9jH package main import "fmt" func CountWaysDP(n int, mm map[int]int) int { if n < 0 { return 0 } else if n == 0 { return 1 } else if mm[n] > 1 { return mm[n] } else { mm[n] = CountWaysDP(n1, mm) + CountWaysDP(n2, mm) + CountWaysDP(n3, mm) return mm[n] } } func main() { mm := make(map[int]int) fmt.Println(CountWaysDP(10, mm), mm) } This just gives me 0 map[]. It turns out that the dynamic recursion ends at the following line: else if mm[n] > 1 Then how would I use dynamic programming to solve this problem? This is exactly the same solution as in Cracking the coding interview....
 回答 1 已采纳 Related questions: Am I using PHP's crypt() function correctly? Password storage hash with SHA512 or crypt() with blowfish (bcrypt) I'm trying to figure out how I should safely store a password using PHP. After a little reading I've identified that I should use crypt() instead of hash() and that I should use either the blowfish (bcrypt) or SHA512 algorithms, with I believe bcrypt being recommended more often, though there is significant support for SHA512 based algorithms, too. There are also many suggestions that my salt should be as random as possible, with many suggestions to use openssl_random_pseudo_bytes() over the core rand() and mt_rand(). My main questions are: If I choose to use bcrypt, what load factors should I consider using? I noticed that for PHP 5.5 the default load factor in the new password API is 10 so I would imagine I would want at least that value. How does the load factor correlate to password safety? From what I understand the algorithm will iterate 2^load_factor times, but I'm more interested in how this translates into safety against brute force cracking methods. What does it mean to be "safe"? Does it take 10 years to crack? 5 years? 1 year? Why should I pick bcrypt over a SHA512 based method (or viseversa)? I've heard that SHA512 is designed to be a fast hashing method so over time it won't hold up as well as bcrypt. Is this true? Both methods have salt parameters which allow crypt to iterate multiple times. To the best of my knowledge, I implemented the following test code which generates a bcrypt salt. Is the recommended method? Is there a better way to do it? _ function gen_salt($cost) { return "$2y$" . $cost . "$" . str_replace('+', '.', base64_encode(openssl_random_pseudo_bytes(22))); }
 回答 2 已采纳 Objective: I have been solving question 6 from the book 'Cracking the Coding interview' by using Go. NOTE I DO NOT WAN'T HELP OR SOLUTIONS TO THIS QUESTION 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? Problem: I made an array of arrays to represent the matrix and I created a swap function to swap the elements clockwise in the matrix. For some reason I get this really weird error when trying to compile: ./Q6.go:29: invalid operation: b[N  col  1] (index of type *int) ./Q6.go:30: invalid operation: b[N  row  1] (index of type *int) Where am I getting type *int as an index? In the Go documenation, len(v) returns type int and everything else is in the value of 'N  col  1' is type int so how am I getting type *int index? Code: package main import "fmt" func main() { b := [][]int{{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16}} // 4 by 4 array going from 1 to 16 N := len(b) for row := 0; row < N / 2; row++ { for col := row; col < N  row  1; col++ { a := &b[row][col] b := &b[col][N  row  1] c := &b[N  col  1][col] // < Error here d := &b[N  row  1][N  col  1] // < Error here fourSwap(a, b, c, d) } } for r := range b { for c:= range b[0] { fmt.Print(b[r][c]) } fmt.Print(" ") } } // [a][][][b] [c][][][a] // [][][][] > [][][][] // [][][][] > [][][][] // [c][][][d] [d][][][b] func fourSwap(a, b, c, d *int) { temp := *b *b = *a *a = *c *c = *d *d = temp }
 4年前回答 1 已采纳 Problem Description XYZ is playing an interesting game called "drops". It is played on a r∗c grid. Each grid cell is either empty, or occupied by a waterdrop. Each waterdrop has a property "size". The waterdrop cracks when its size is larger than 4, and produces 4 small drops moving towards 4 different directions (up, down, left and right). In every second, every small drop moves to the next cell of its direction. It is possible that multiple small drops can be at same cell, and they won't collide. Then for each cell occupied by a waterdrop, the waterdrop's size increases by the number of the small drops in this cell, and these small drops disappears. You are given a game and a position (x, y), before the first second there is a waterdrop cracking at position (x, y). XYZ wants to know each waterdrop's status after T seconds, can you help him? 1≤r≤100, 1≤c≤100, 1≤n≤100, 1≤T≤10000 Input The first line contains four integers r, c, n and T. n stands for the numbers of waterdrops at the beginning. Each line of the following n lines contains three integers xi, yi, sizei, meaning that the ith waterdrop is at position (xi, yi) and its size is sizei. (1≤sizei≤4) The next line contains two integers x, y. It is guaranteed that all the positions in the input are distinct. Multiple test cases (about 100 cases), please read until EOF (End Of File). Output n lines. Each line contains two integers Ai, Bi: If the ith waterdrop cracks in T seconds, Ai=0, Bi= the time when it cracked. If the ith waterdrop doesn't crack in T seconds, Ai=1, Bi= its size after T seconds. Sample Input 4 4 5 10 2 1 4 2 3 3 2 4 4 3 1 2 4 3 4 4 4 Sample Output 0 5 0 3 0 2 1 3 0 1
 google/ amazon / microsoft 面试必问
 金小朵的博客 1. 第八章：递归 程序调用自己称为递归。把大问题化成与自身相类似的小问题。递归需要边界条件，递归前进段，递归返回段。当边界条件不满足时，递归前进，当边界条件满足时，递归返回。空间成本&时间成本相对较大。 （1）动态规划： 节约时间&空间，把重复性的计算记录下来。如斐波拉契数列，采用递归的算法复杂度为O(n^2),动态规划为O(n).if(n<=1) return ; fris
 handsomeKyne的博客 本系列是我对cracking the code interviews的c++实现和学习，不足之处欢迎批评指正。 题目：实现一个算法，判断其中的字符是否都不相同。如果不能用数据结构，又该如何实现？ 解：首先得向面试官问清楚是Unicode还是ASCII编码，这里我们假设为ASCII编码。具体代码实现如下： #include #include using namespace std;
 揭示FLAG名企招聘秘密。程序员面试敲门砖，亚马逊超级畅销书
 hyperbolechi的博客 Given two node, find the lowest common ancestor. based on the problem description there are two possible solutions:def covers(root,val): if root==None: return False if root.val==v
 taylorzhangyx的博客 This article is my own thinking and analysis when reading the cracking the code interview 6th edition.
 Cracking the Coding Interview(6th) 英文扫描版Cracking the Coding Interview, 6th Edition is here to help you through this process, teaching you what you need to know and enabling you to perform at your very best. I've coached and interviewed hundreds of software engineers. The result is this book., Learn how to uncover the hints and hidden details in a question, discover how to break down a problem into manageable chunks, develop techniques to unstick yourself when stuck, learn (or relearn)
 weixin_30871701的博客 导语 所有的编程练习都在牛客网OJ提交，链接: https://www.nowcoder.com/ta/crackingthecodinginterview 第八章 面试考题 8.1 数组与字符串 1.1 实现一个算法，确定一个字符串的所有字符是否全都不相同。假设不允许使用额外的数据结构，又该如何处理？ 题解：应该先clarify上面的字符串是 ASCII 还是...
 毛毛星的博客 纸上写代码 简历：对你参与的任何项目或者工作做一个总结，并阐述最难的部分以及最有趣的部分 。 不要记忆解决方案：不是说让你不要记忆，而是要想清楚它的思路，也就不需要记忆了 大声地说出来你的想法 微软面试：聪明，对技术有激情，极客 Be nice to your recruiter 对雇佣你的人要好 因为他们决定了要不要雇佣你 4到
 skywalker_sun的博客 题目意思：你被恐怖分子绑架了，他们要求你帮他们破解密文你知道的信息是，密文是通过一个固定长度的密钥通过抑或运算加密而来，假如e为原文，u为密文,k为密钥，加密规则如下e[i] = u[i] XOR k[i MOD l]由于抑或运算的特性，所以解密规则如下u[i] = e[i] XOR k[i MOD l]恐怖分子给你4段密文，每段用不同密钥加密的，长度为30000字，你的工作是还原这4段密文的原文。最后，恐怖分子告诉你一个关键的信息： The decrypted message will be in Eng
 靖心的博客 不使用运算操作符号，实现加法运算。 这道题，要想出来还是非常有难度的。这种题一般都是使用位操作了。 有两层难度： 1 进位和不进位的结果是可以分开考虑的 2 但是就算可以，那么怎么把进位和不进位的结果加起来呢？ 答案是：使用递归 这题属于思想很难，程序很简单的。