Rakuten

# -*- coding: utf-8 -*-

def reverseString(s):
    """
    Q1. Write a function that takes a string as input and returns the string reversed.

    :type s: String
    :rtype: String
    """

    return reduce(lambda p, c: c + p, s, "")


def isPerfectSqunre(n):
    """
    Q2. Given a positive integer num, write a function which returns True if num is a perfect square else False.

    :type n: Int
    :rtype: Bool
    """

    r = n
    while r*r > n:
        r = (r + n/r) / 2
    return r*r == n


def mergeInterval(intervals, newInterval):
    """
    Q3. Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

    :type intervals: List[List]
    :type newInterval: List
    :rtype: List[List]
    """

    res = []
    for interval in intervals:
        if interval[1] < newInterval[0]:
            res.append(interval)
        elif interval[0] > newInterval[1]:
            res.append(newInterval)
            newInterval = interval
        else:
            newInterval = [min(interval[0], newInterval[0]), max(interval[1], newInterval[1])]

    return res + [newInterval]


def dfs(board, word, i, j):
    if not word:
        return True

    if i < 0 or i == len(board) or j < 0 or j == len(board[0]):
        return False

    if not word[0] == board[i][j]:
        return False

    board[i][j] ^= 8

    found = any(dfs(board, word[1:], i + a, j + b) for a, b in [(-1, 0), (1, 0), (0, -1), (0, 1)])

    board[i][j] ^= 8
    return found

def wordSearch(board, word):
    """
    Q4. Given a 2D board and a word, find if the word exists in the grid.

    :type board: List[List]
    :type word: List
    :rtype: Bool
    """

    board = [map(ord, list(s)) for s in board]
    word = map(ord, word)

    return any(dfs(board, word, i, j) for i in range(len(board)) for j in range(len(board[0])))


def sum(n, m):
    """
    Q5. Calculate the sum of two integers a and b, but you are not allowed to use the operator + and

    :type n: Int
    :type m: Int
    :rtype: Int
    """

    while m:
        n, m = (n ^ m), (n & m) << 1
    return n