`
edison0951
  • 浏览: 71755 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

两道比较复杂的轩辕互动面试题(Python实现)

Python面试算法正则表达式编程 
阅读更多
1.平衡点问题
  平衡点：比如int[] numbers = {1,3,5,7,8,25,4,20}; 25前面的总和为24，25后面的总和也是24，25这个点就是平衡点；假如一个数组中的元素，其前面的部分等于后面的部分，那么这个点的位序就是平衡点
要求：返回任何一个平衡点
下面是代码： 
  1 li = [1,3,5,7,8,25,4,20]
  2 def main():
  3     i = 0
  4     length = len(li)
  5     before = 0
  6     after = 0
  7     mark = 0
  8     balance = 0
  9     total = sum(li)
 10     while True:
 11         balance = i + 1
 12         if balance + 1 > length -1:
 13             return -1
 14         if li[i] == li[balance+1]:
 15             mark = balance
 16             return (mark,li[mark])
 17         else:
 18             before = before + li[i]
 19             other = total - before - li[balance]
 20             if before == other:
 21                 mark = balance
 22                 return (mark,li[mark])
 23         i += 1
 24 if __name__ == "__main__":
 25    print  main()

2.支配点问题：
支配数：数组中某个元素出现的次数大于数组总数的一半时就成为支配数，其所在位序成为支配点；比如int[] a = {3,3,1,2,3};3为支配数，0，1，4分别为支配点；
要求：返回任何一个支配点
本问题可归结为众数问题（统计学范畴），即一组数据中出现次数最多的那个数值，它可以没有也可以为多个。
下面是代码，如果你又更号的实现，不吝赐教。 
  1 li = [1,3,4,3,3]
  2 def main():
  3     mid = len(li)/2
  4     for l in li:
  5         count = 0
  6         i = 0
  7         mark = 0
  8         while True:
  9             if l == li[i]:
 10                 count += 1
 11                 temp = i
 12             i += 1
 13             if count > mid:
 14                 mark = temp
 15                 return (mark,li[mark])
 16             if i > len(li) - 1:
 17                 break
 18      else:
 19          return -1
 20 if __name__ == "__main__":
 21    print  main()

最后，还有个一个中位数的问题，在很多笔试中也会遇到。
中位数：即数据从小到大排列，将数据分为两部分，一部分大于该数值，一部分小与该数值。中位数的位置是这样计算的：如果数据长度为奇数，中位数的位置为（N+1）/2,如果为偶数则为第N/2个数与第(N/2)+1的平均数。
分享到：
| 轩辕互动面试题目-----最大递增子序列(Pyt ...
评论
46 楼 wayhome 2010-03-18  
joeycn 写道
如果不考虑运行效率，只考虑写代码的效率的话，为什么不使用api来完成呢...
比如sum, count什么的，很简单呢
比如第二题：
a = [1, 2, 2, 3, 2]
b = set(a)  //去掉重复的元素，也可以不要
for i in b:
  if(a.count(i)>=len(a)/2): 
    print i
    break


不考虑效率的话，两道题都只要一行就够了

第一题: 
>>> s = [1, 3, 5, 7, 8, 25, 4, 20]
>>> filter(lambda x:sum(s[:s.index(x)])==sum(s[s.index(x)+1:]),s)
    [25]
>>> s.append(30)
>>> filter(lambda x:sum(s[:s.index(x)])==sum(s[s.index(x)+1:]),s)
    []


第二题: 
>>> s = [1, 2, 2, 3, 2]
>>> list(set(filter(lambda x:s.count(x)>len(s)/2,s)))
    [2]
45 楼 tianling536 2010-03-17  
tianling536 写道

取所有的，这个不要反复的sum
l = [1,3,5,7,8,25,4,20]
sum_of_list = sum(l)
sum_of_head = 0

for i in range(len(l)):
     if sum_of_head*2 + l[i] == sum_of_list:
         print l[i]
     else:
         sum_of_head += l[i]

想起来最多也就一个。。 

for i in range(len(l)):
    if sum_of_head*2 + l[i] == sum_of_list:
        print l[i]
        break
    elif sum_of_head*2 + l[i] > sum_of_list:
        break
    else:
        sum_of_head += l[i]
44 楼 tianling536 2010-03-17  
第一题
算一个 写简单点，但是需要反复sum 效率要低

l = [1,3,5,7,8,25,4,20]
for i in range(len(l)):
    if sum(l[:i]) == sum(l[i+1:]):
        print l[i]

取所有的，这个不要反复的sum
l = [1,3,5,7,8,25,4,20]
sum_of_list = sum(l)
sum_of_head = 0

for i in range(len(l)):
     if sum_of_head*2 + l[i] == sum_of_list:
         print l[i]
     else:
         sum_of_head += l[i]
43 楼 joeycn 2010-03-15  
如果不考虑运行效率，只考虑写代码的效率的话，为什么不使用api来完成呢...
比如sum, count什么的，很简单呢
比如第二题：
a = [1, 2, 2, 3, 2]
b = set(a)  //去掉重复的元素，也可以不要
for i in b:
  if(a.count(i)>=len(a)/2): 
    print i
    break
42 楼 laomie 2010-03-14  
1.平衡点问题 
# -*- coding: utf-8 -*- 

data = [1, 3, 5, 7, 8, 25, 4, 20]

def main() :

   dataIndex = []
   length = len(data)
   total = sum(data)

   if (length > 2) :
      tempSum = data[0]
      for i in range(1, length - 1) :
         if (tempSum * 2 + data[i] == total) :
            dataIndex.append(i)
         tempSum = tempSum + data[i]   
   
   return dataIndex

if __name__ == "__main__" :
   print(main())


2.支配点问题 
# -*- coding: utf-8 -*-
# 用dictionary实现，key存放所给的数，value为list，存放所给数在数组中的位置
# 一个数可能在数组中出现多次

data = [3, 3, 1, 2, 3]

def main() :
   dataIndex = []
   hashData = {}

   for i in range(0, len(data)) :
      key = data[i]
      if (key in hashData) :
         value = hashData[key]
         value.append(i)
      else :
         value = []
         value.append(i)
         hashData[key] = value

   halfLength = int(len(data) / 2)
   if (len(data) % 2 == 1) :
      halfLength = halfLength + 1

   for key in hashData :
      if (len(hashData[key]) >= halfLength) :
         dataIndex.append(hashData[key])
   
   return dataIndex

if __name__ == "__main__" :
   print(main())

41 楼 Blithe 2010-03-13  
exoweb 要求挺高的么
40 楼 key232323 2010-03-03  
汗，我也做过……可惜代码效率太低了
39 楼 kraft 2010-03-03  
我觉得涉及到算法先把 算法描述一下再写code，因为出题的人主要考的是算法

1 平衡点 就是前后同时遍历求和  复杂度O(N)
2 支配点 可以参考微软的编程之美 的水王问题 利用一个栈来存储临时数据，复杂度也是O(N)
38 楼 xiaozhe 2010-03-03  
递归做起来很容易的 
/**
 * Created by IntelliJ IDEA.
 * User: benlinus
 * Date: 2010-3-3
 * Time: 10:25:44
 *  平衡点：比如int[] numbers = {1,3,5,7,8,25,4,20}; 25前面的总和为24，25后面的总和也是24，
 * 25这个点就是平衡点；假如一个数组中的元素，其前面的部分等于后面的部分，那么这个点的位序就是平衡点
要求：返回任何一个平衡点
 */
public class BalancePoint {
    private int[] numbers;
    private int start;
    private int end;
    
    public BalancePoint(int[] numbers){
        this.numbers = numbers;
        this.start = 0;
        this.end = numbers.length-1;
    }

    public int findBalancePoint(int pos){
        if(pos < end && pos > 0){
            int presum = 0;
            for(int i=0; i<pos; i++){
                presum = presum + numbers[i];
            }
            int postsum = 0;
            for(int i=pos+1; i<=end; i++){
                postsum = postsum + numbers[i];
            }
            if(presum == postsum)
                return pos;
            else
                return findBalancePoint(++pos);
        }else{
            return -1;
        }
    }

    public static void main(String[] args) {
        int number[] = {1,3,5,7,8,25,4,20};
        BalancePoint balancePoint = new BalancePoint(number);
        int pos = balancePoint.findBalancePoint(1);
        if(pos < 0 || pos >= number.length){
            System.out.println("can't find pos");
        }
        else{
            System.out.println("balance point is:"+number[pos]);
        }
    }
}
37 楼 eita 2010-02-28  
平衡点的scheme实现： 
 (define (part-sum lst k) ;列表lst前k个数之和
    (if (and (> (length lst) 0) (> k 0))
        (+ (car lst) (part-sum (cdr lst) (- k 1)))0))

 (define (balanced-point lst)
    (define (balanced-point-helper lst k) 
      ( cond ((>= k (length lst)) 0)
             ((= (part-sum lst k) (part-sum (reverse lst) (- (length lst) (+ k 1)))) k)
             (else (balanced-point-helper lst (+ k 1)))))
    (balanced-point-helper lst 2))


为验证上面代码的正确性，构造如下find-bp过程，随机生成一个长度为200的列表（元素均为小于1000的整数），查找列表的平衡点。若没有平衡点，再生成一个，直到查找到为止。 
(define (find-bp lst) 
    (let ([lst (build-list 200 (lambda (x) (random 1000)))])
    (if (= 0 (balanced-point lst ))
        (find-bp '())
       (begin (display lst) 
              (newline)
              (display (balanced-point lst )))
        )))

运行(find-bp '())，大约30秒钟，生成一个有平衡点的列表：
(396 180 786 440 832 236 354 456 532 518 801 402 613 791 502 259 562 629 696 88 460 690 852 594 541 66 572 734 123 435 412 821 884 840 940 978 742 874 104 531 853 684 119 683 951 902 497 446 102 485 424 796 30 379 450 897 276 793 697 79 202 92 687 517 499 992 847 752 868 73 217 32 869 589 82 273 981 528 458 852 841 664 815 876 929 702 615 503 963 326 619 579 226 637 197 355 607 405 156 86 625 336 601 325 108 956 503 219 691 227 285 929 349 7 859 22 95 129 212 504 146 56 628 816 699 138 284 104 825 75 395 823 680 930 776 112 868 351 198 500 437 92 678 837 600 397 999 323 924 828 395 649 342 697 42 429 756 705 546 991 859 336 274 549 442 180 169 475 843 116 885 850 156 394 243 959 16 371 750 319 489 936 259 942 447 987 829 431 428 56 442 84 79 871 163 523 11 975 632 580)
平衡点为91
36 楼 edison0951 2010-02-26  
  只所以不能够计算［1，2，1］，是因为我把RETURN条件弄成了balance + 2>length -1,改成balance + １>length -1就OK了。之所以犯这个错误主要原因是在写的途中改变了算法，没有仔细检查，该检讨，谢谢指正。
35 楼 edison0951 2010-02-26  
代码有点小问题，要改改。
34 楼 aiyoo521 2010-02-26  
没看全回复，简单说下我的思路

平衡点问题，
1.求所有值的和，并除2，得到sum/2
2.从前往后加，大于sum/2时停止，得到sum_before和最后一个数位置point[n]
3.从停止的地方开始往后加得到sum_after，若相等，则point[n]为平衡点，否则不存在平衡点 
int sum;
int sum_before;
int sum_after;
int point;
int[] array = {*,*,*,*,*,*,*,*,*};

public static void main(String[] args) {
    for(int i = 0; i < array.length(); i++) {
        sum += array[i];
    }

    for(int i = 0; sum_before < sum/2; i++) {
        sum_before += array[i];
        point = i;
    }

    for(int i = point + 1; i < array.length() - point; i++) {
        sum_after += array[i];
    }

    if(sum_after == sum_before) {
        syso(point + "is the num");
    } else {
        syso("none");
    }
}

(未经运行，仅供阅读)
33 楼 dopic 2010-02-25  
lz代码,有问题啊
32 楼 dopic 2010-02-25  
请轻拍!请轻拍!小弟刚学python
31 楼 yangyi 2010-02-25  
yangyi 写道
拙作 
package com.blogspot.yiprogs.algorithms;

public class MiddleNum {
	public static void main(String[] args){
		int[] test = {1,2};
		System.out.println("第" + (showNum(test) + 1) + "个数是中间数");
	}
	
	private static int showNum(int[] array){
		int p = 0;
		int q = array.length - 1;
		int lt = array[p];
		int rt = array[q];
		
		if(p+2 > q){
			return -1000000;
		}
		
		while(p+2 != q){
			if(lt < rt){
				p++;
				lt += array[p];
			}else{
				q--;
				rt += array[q];
			}
		}
		return p + 1;
	}
}

支撑点问题 
package com.blogspot.yiprogs.algorithms;

import java.util.HashMap;

public class FindDatum {

	public static void main(String[] args) {
		int[] test = {3,4,1,2,3};
		System.out.println(find(test) + "是支撑数");
	}
	
	private static int find(int[] data){
		int tmp;
		float m = (float)data.length / 2;
		HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
		
		for(int i=0;i<data.length;i++){
			if(hm.get(data[i]) != null){
				tmp = hm.get(data[i]);
				if(tmp + 1 >= m){
					hm = null;
					return data[i];
				}else{
					hm.put(data[i], tmp + 1);
				}
			}else{
				hm.put(data[i], 1);
			}
		}
		
		return -1;
	}
}
30 楼 dopic 2010-02-25  
<pre name="code" class="python">tuple = [1,3,5,7,8,25,1,5,7,8,3]#1,3,4,3,3]#1, 1, 3, 5, 7, 8, 25, 4, 20, 1] #(1,3,5,7,8,25,4,20)

endIn = len(tuple) - 1
startIn = 0
startSum = 0
endSum = 0
temp = 0
i = endIn+1

while i &gt; 0:
    temp = tuple[startIn]
    end = tuple[endIn]
    if endSum &gt;= startSum and endIn &gt; startIn:
        startSum += temp
        startIn += 1
    elif endSum &lt; startSum:
        endSum += end
        endIn -= 1
    else:
        if endSum!=startSum:
            print 'no found!'
        else:
            print 'ok'
        break;       
    print 'startSum:%s  ' % str(startSum) + str(startIn) + ' endSum:%s ' % str(endSum) + str(endIn)       
    i -= 1


</pre>
<p> </p>
29 楼 yangyi 2010-02-25  
拙作 
package com.blogspot.yiprogs.algorithms;

public class MiddleNum {
	public static void main(String[] args){
		int[] test = {1,2};
		System.out.println("第" + (showNum(test) + 1) + "个数是中间数");
	}
	
	private static int showNum(int[] array){
		int p = 0;
		int q = array.length - 1;
		int lt = array[p];
		int rt = array[q];
		
		if(p+2 > q){
			return -1000000;
		}
		
		while(p+2 != q){
			if(lt < rt){
				p++;
				lt += array[p];
			}else{
				q--;
				rt += array[q];
			}
		}
		return p + 1;
	}
}
28 楼 dmhorse 2010-02-25  
<p>复杂度估计也是O(N)</p>
<p>
</p>
<pre name="code" class="python">list=(1,3,5,7,8,25,4,20)
sump={}

def fib(n):
  global sump
  if n in sump:
    return sump[n]
  if n==0:
    return list[n]
  if n==-1:
    return list[-1]

  if n&gt;0:
    sump[n] = fib(n-1) + list[n]
  else:
    sump[n] = fib(n+1) + list[n]
  return sump[n]

for n in range(1,len(list)-1):
  if fib(n-1) == fib( ( len(list) - n - 1 ) * -1 ):
    print 'found out',n</pre>
 
27 楼 xici_magic 2010-02-25  
又是算法  哎 
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    Python面试题及答案共70道.docx

    Python面试题及答案共70道Python面试题及答案共70道Python面试题及答案共70道Python面试题及答案共70道Python面试题及答案共70道Python面试题及答案共70道Python面试题及答案共70道Python面试题及答案共70道Python...

    Python经典面试题-总结

    Python经典面试题 Python经典面试题 python面试题 python 面试题 Python经典面试题 Python经典面试题 python面试题 python 面试题 Python经典面试题 Python经典面试题 python面试题 python 面试题 Python经典面试题 ...

    python面试题汇总(

    在面试准备过程中，了解和掌握一些常见的Python面试题对于求职者来说至关重要。以下将详细解释上述文件中提到的Python知识点。 1. 利用Python的内置函数sum()可以非常简便地计算序列的总和。例如一行代码`sum(range...

    Python面试合集 史上最全面Python面试题和详解(10套) 完整版

    本文件内含10个文档，文档格式为md，需要用...包含：2019 Python最新面试题及答案16道题、110道Python面试题（上）、最常见的 35 个 Python 面试题及答案（2018 版）、整理的最全 python常见面试题（基本必考）等！

    128道Python面试题.pdf

    "128道Python面试题.pdf" Python基础知识点： 1. 文件操作：文件读写、文件类型、文件权限等。 2. 模块与包：Python中的模块和包、模块的导入、模块的使用等。 3. 日期处理：Python中的日期处理、日期格式化、日期...

    110道Python面试题：.pdf

    Python面试题大全 Python是一种广泛应用于数据科学、人工智能、Web开发等领域的高级编程语言。以下是 Python 面试题大全，涵盖了 Python 的基础知识、语法、标准库、面向对象编程、多线程编程等方面。 1. Python ...

    110道Python面试题汇总.doc

    Python是目前编程领域最受欢迎的语言。...每道题都提供参考答案，希望能够帮助你在2019年求职面试中脱颖而出，找到一份高薪工作。这些面试题涉及Python基础知识、Python编程、数据分析以及Python函数库等多个方面。

    python基础面试题 python程序员面试题

    python基础面试题 python程序员面试题

    Python面试题汇总

    Python面试题汇总 Python 是如何进行内存管理的？ Python 内部使用引用计数机制来保持追踪内存中的对象，所有对象都有引用计数。引用计数增加的情况有：1、一个对象分配一个新名称；2、将其放入一个容器中（如...

    剑指Offer面试题Python实现

    《剑指Offer面试题Python实现》是一份针对Python程序员在面试过程中可能会遇到的常见问题的解答集锦。这个资源主要涵盖了数据结构、算法、编程基础等多个方面，旨在帮助求职者提升技能，顺利通过面试。其中，...

    最新python面试题及答案.doc

    【Python面试知识点详解】 1. **Python标准库**：Python提供了丰富的标准库，例如os、sys、re、math和datetime。os库包含了与操作系统交互的函数，如文件操作和路径处理；sys库常用于处理命令行参数；re库支持正则...

    Python面试经验技巧面试题面试宝典python面试常见问题面试资料

    Python面试经验技巧面试题面试宝典python面试常见问题面试资料： 110道Python面试题.pdf Python面试宝典.pdf python面试常见的25个问题.pdf Python面试必须要看的16个问题.pdf 你不清楚的18个非技术面试题.pdf

    0积分 面经 面试题 python面试题 免费下载

    大数据架构 python基础 数据库 等应有尽有 可免费下载 面经 面试题 python面试题 300多道题 ，可以参考一下 适用人群：大一到大四，正在找工作的各位老哥 ，我相信这份面试题会给你们带来满意的效果 但是切记 不要...

    110道Python面试题汇总_python教程_

    针对“110道Python面试题汇总”的主题，我们可以深入探讨其中可能涵盖的多个知识点，这些知识点是Python开发者在面试中可能会遇到的常见问题。 1. **基础语法**：面试中经常考察Python的基础知识，如变量定义、数据...

    110道Python面试题汇总.rar

    Python是一种广泛使用的高级编程语言，以其简洁明了的语法和强大的功能深受程序员喜爱。...这份"110道Python面试题汇总.pdf"将是你准备面试的重要参考资料，它覆盖了各个层面的问题，帮助你全面复习和巩固Python知识。

    吐血总结!50道Python面试题集锦(附答案)

    Python 面试题集锦 Python 是目前编程领域最受欢迎的语言，本文总结了 Python 面试中最常见的问题，涉及 Python 基础知识、Python 编程、数据分析以及 Python 函数库等多个方面。下面是对这些问题的详细解释： Q1 ...

    python面试题

    ### Python面试题详解 #### Python语言特性 **1. Python的函数参数传递** 在Python中，函数参数的传递实质上是引用的传递。这与C语言中的指针类似，但又有本质的区别。Python中所有变量都是对内存中某个对象的...

    python100道面试题及解答（）全部答案 pycharm 测试过 py3环境）

    python面试题100道答案全部 一般的只写了30个答案题目大概有 1、一行代码实现1--100之和 2、如何在一个函数内部修改全局变量 利用global 修改全局变量 3、列出5个python标准库 os：提供了不少与操作系统相关联的函数...

Magicbox
Global site tag (gtag.js) - Google Analytics