Cracking the coding interview--Q9

最新推荐文章于 2019-06-26 11:19:42 发布

牧风

最新推荐文章于 2019-06-26 11:19:42 发布

阅读量947

点赞数

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

本文链接：https://blog.csdn.net/alex0/article/details/9295905

版权

Chapter 9 | Sorting and Searching

9.1 You are given two sorted arrays, A and B, and A has a large enough buffer at the end to hold B. Write a method to merge B into A in sorted order.

插入排序，需要调整数组，移位。如果链表好做得多。

9.2 Write a method to sort an array of strings so that all the anagrams are next to each other.

先排一次词本身，再排词之间。

9.3 Given a sorted array of n integers that has been rotated an unknown number of times, give an O(log n) algorithm that finds an element in the array. You may assume that the array was originally sorted in increasing order. EXAMPLE: Input: find 5 in array (15 16 19 20 25 1 3 4 5 7 10 14) Output: 8 (the index of 5 in the array)

如原解

9.4 If you have a 2 GB file with one string per line, which sorting algorithm would you use to sort the file and why?

字典树，自然有序。。红黑树也行。

9.5 Given a sorted array of strings which is interspersed with empty strings, write a method to find the location of a given string. Example: find “ball” in [“at”, “”, “”, “”, “ball”, “”, “”, “car”, “”, “”, “dad”, “”, “”] will return 4 Example: find “ballcar” in [“at”, “”, “”, “”, “”, “ball”, “car”, “”, “”, “dad”, “”, “”] will return -1

转换为字典求解。

9.6 Given a matrix in which each row and each column is sorted, write a method to find an element in it.

排除法

9.7 A circus is designing a tower routine consisting of people standing atop one another’s shoulders. For practical and aesthetic reasons, each person must be both shorter and lighter than the person below him or her. Given the heights and weights of each person in the circus, write a method to compute the largest possible number of people in such a tower. EXAMPLE: Input (ht, wt): (65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110) Output: The longest tower is length 6 and includes from top to bottom: (56, 90) (60,95) (65,100) (68,110) (70,150) (75,190)

背包？

博客等级

码龄15年

32
原创

2
点赞

4
收藏

13
粉丝

关注

私信

热门文章

分类专栏

链表 1篇
OpenvSwitch 2篇

展开全部收起

上一篇：: Cracking the coding interview--Q5

下一篇：: 背包复习

最新评论

【OpenvSwitch】1-匹配流程
vinllen: 看了这么多ovs源码，你这个图总结的太赞了
【OpenvSwitch】1-匹配流程
raliny: 你好，问一个问题，dp中的flow作为无状态的流表如何超时？在dp代码中没有发现超时的操作，是vswitchd执行的超时删除flow的操作么？是使用简单的定时器完成的么？
移植linux内核(3.0.13)的链表实现进windows下，VS编译通过。
b21109977: 这个，请教一下，在VS2008下，那个静态内联函数时怎么编译通过的诶？
【OpenvSwitch】1-匹配流程
小刀刀: 您好，Open vSwitch的图可以发一份给我吗？非常感谢您！谢谢！ pengtaonuli@163.com
【OpenvSwitch】1-匹配流程
牧风回复 lafenice_cc: 内核掩码还没看，看一直在反复，可能过一段才有时间研究

最新文章

目录

展开全部

收起

评论

被折叠的条评论为什么被折叠?

到【灌水乐园】发言

查看更多评论

添加红包

成就一亿技术人!

hope_wisdom

发出的红包

实付元

使用余额支付

点击重新获取

扫码支付

钱包余额 0

抵扣说明：

1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载，可以购买VIP、付费专栏及课程。